It is currently Sun Dec 17, 2017 10:18 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 30 posts ]  Go to page Previous  1, 2
Author Message
 Post subject:
PostPosted: Sat Aug 27, 2005 3:16 am 
Offline
Site Admin
User avatar

Joined: Mon Sep 20, 2004 6:04 am
Posts: 3488
Location: Indianapolis
Bregalad wrote:
Well, no need to make a post to say you weren't logged in, I saw it. This personally never happened to me yet, and I ask myself why this happen so often to everyone else.


That happens to me all the time. I'll be on the main index and be logged in, and can see which forums have new posts. Then I click on a forum, and suddenly I'm a 'guest'. So I log in again, and it acts like I've already read all the new posts (very annoying, because I often find myself missing some posts that way, usually only noticing it once there's another reply). It's odd though, because it never happens to me on any other forum using phpBB.

/end OT rant

This binary to decimal code sounds pretty nice. I know I'd prefer a technique that always takes the same amount of cycles, I think it's best to optimize for the worst-case.


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 27, 2005 5:16 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7320
Location: Chexbres, VD, Switzerland
Memblers wrote:
That happens to me all the time. I'll be on the main index and be logged in, and can see which forums have new posts. Then I click on a forum, and suddenly I'm a 'guest'.

Well, I think there is a checkbox when you log in that should be thicked if you want to "automatically" log-in. Of course, you can't do this at work or something, but you can on your home computer. Else, bugs and stuff should be reported to the phpBB team.

Quote:
So I log in again, and it acts like I've already read all the new posts (very annoying, because I often find myself missing some posts that way, usually only noticing it once there's another reply). It's odd though, because it never happens to me on any other forum using phpBB.

This happens to me very often. I'm just logged in, see a new post, go to it, then read it and possibly aswer to it, but when I come back, sometimes all others new post aren't marked as new anymore, sometimes not. It's really crap, effectively.
Another crap thing is that sometimes it shows a new post, but actually the new post is just mine.

Quote:
This binary to decimal code sounds pretty nice. I know I'd prefer a technique that always takes the same amount of cycles, I think it's best to optimize for the worst-case.

Well, I think it's better to be short sometimes and medium sometimes than long anyway.

_________________
Life is complex: it has both real and imaginary components.


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 27, 2005 10:56 am 
Offline
User avatar

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
Worst-case performance is what matters most, because it's what determines whether you have slow-down in a game (unless you can guarantee that worst-case performance of one routine always occurs during the best-case performance of another). For real-time applications, you don't mind reducing best-case performance if it increases worst-case.


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 27, 2005 1:48 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10172
Location: Rio de Janeiro - Brazil
If anyone is curious, this is the 8-bit routine, unrolled and optimized as far as I could so far. There are no conditional branches, so execution time is constant - around 150 cycles (I say around because there is the set-up, returning and all and I'm never really sure if we should count these in when measuring cycles). I have not bothered to make it as a subroutine yet, I'm just doing things directly for now, for testing purposes.

This runs faster than the worst case of Bregalad's routine (only a little bit faster), but still much slower than it's best case.

If anyone wants to try, here it is (it is quite longer when unrolled!):
Code:
BNUM = $00 ;8-bit binary number.
DNUM = $01 ;3-digit decimal number.

   .ORG $8000

   LDA #199   ;Test value.
   STA BNUM

BIN2DEC
   LDA #$00   ;1's start at 0, using the accumulator until the end.
   STA DNUM+1   ;Clear 10's. Will use memory.
   STA DNUM+2   ;Clear 100's. Will use memory.

   ASL BNUM   ;Shift 1st bit from binary number
   ROL      ;into the 1's digit.

   ASL BNUM   ;Shift 2nd bit from binary number
   ROL      ;into the 1's digit.

   ASL BNUM   ;Shift 3rd bit from binary number
   ROL      ;into the 1's digit.

   TAX      ;This is the 1st time 1's may have gone over
   LDA TABLE, X   ;the limit. Get the correct value from TABLE.

   ASL BNUM   ;Shift 4th bit from binary number
   ROL      ;into the 1's digit.
   ROL DNUM+1   ;Propagate to the 10's digit.

   TAX      ;1's may have gone over the limit.
   LDA TABLE, X   ;Get corrected value from TABLE.

   ASL BNUM   ;Shift 5th bit from binary number
   ROL      ;into the 1's digit.
   ROL DNUM+1   ;Propagate to the 10's digit.

   TAX      ;1's may have gone over the limit.
   LDA TABLE, X   ;Get corrected value from TABLE.

   ASL BNUM   ;Shift 6th bit from binary number
   ROL      ;into the 1's digit.
   ROL DNUM+1   ;Propagate to the 10's digit.

   TAX      ;1's may have gone over the limit.
   LDA TABLE, X   ;Get corrected value from TABLE.

   LDX DNUM+1   ;This is the 1st time 10's may have gone over
   LDY TABLE, X   ;the limit. Get corrected value from TABLE.
   STY DNUM+1   ;Overwrite.

   ASL BNUM   ;Shift 7th bit from binary number
   ROL      ;into the 1's digit.
   ROL DNUM+1   ;Propagate to the 10's digit.
   ROL DNUM+2   ;Propagate to the 100's digit.

   TAX      ;1's may have gone over the limit.
   LDA TABLE, X   ;Get corrected value from TABLE.

   LDX DNUM+1   ;10's may have gone over the limit.
   LDY TABLE, X   ;Get corrected value from TABLE.
   STY DNUM+1   ;Overwrite.

   ASL BNUM   ;Shift 8th bit from binary number
   ROL      ;into the 1's digit.
   ROL DNUM+1   ;Propagate any carry to the 10's digit.
   ROL DNUM+2   ;Propagate any carry to the 100's digit.

   STA DNUM+0   ;Store the 1's digit.

   BRK

   .ORG $C000
TABLE
   .DB $00, $01, $02, $03, $04, $80, $81, $82, $83, $84

I'm extending it to 16 bits right now, and then things might get interesting. I'll try to optimize it further, looking for unncessary operations or faster ways to do the necessary ones... putting the lookup table on zero-page may speed up things a bit, but I don't think anyone will want to waste 10 bytes of zero-page, me included.

When a 16-bit version is ready, I'll try it against Bregalad's method, also extended to 16 bits.

There is one thing I really like about Bregalad's method, though: you could jump to the middle of the routine if you were interested in converting smaller numbers. Both methods are nice, but I'm trying hard to make this one perform faster.

-tokumaru-


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 27, 2005 2:02 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10172
Location: Rio de Janeiro - Brazil
Bregalad wrote:
Well, I think it's not that complicated. Before shifting, you have to check if the shift will override 10, and if so, you have to add 123 to the number so the Most Significan Bit will overwrite into the next one. I'm just unsure that will work for larger-than 8-bit number so easily.


No, it is not complicated at all - the way the routine works I mean. But one's got to be pretty smart to first come up with an idea like this. I alway read about these revolutionary ways to do stuff but can never seem to come up with one of those! =)

I understood HOW it worked as soon as I read about it, what I didn't understand at first was WHY it worked! Once that was also understood, I could come up with new ways to use the idea, instead of blindly using something someone else discovered and not even know what I was doing.


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 27, 2005 2:08 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10172
Location: Rio de Janeiro - Brazil
blargg wrote:
I love this kind of thing. Optimizing an algorithm in assembly is the most fun since it involves programming at the lowest level while thinking in terms of very pure math concepts. The discussion forum on 6502.org sometimes has some interesting threads along these lines, for example the recent "Fast CRC without tables" thread.

Yeah, I find it very interesting too! However my math skills aren't that great, and sometimes I miss many chances for optimizations.

I visit the 6502.org forum from time to time, and they do have some very interesting stuff in there. However, with this subject I wasn't very lucky. They have good ways to perform BIN to DEC conversions, ways that deserve more studying, but most use the BCD mode of the 6502, wich the NES lacks. I don't think people there care much about "modified" 6502's. =)


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 27, 2005 11:41 pm 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7320
Location: Chexbres, VD, Switzerland
tokumaru wrote:
This runs faster than the worst case of Bregalad's routine (only a little bit faster), but still much slower than it's best case.

Mine also is much shorter and waste probably about 3 times less ROM.

Quote:
When a 16-bit version is ready, I'll try it against Bregalad's method, also extended to 16 bits.

Hey, the get number from the table thing is cool !
Scince you usually don't want to converse dozens of large number in a single frame, this probably won't cause any slowdown in gamaplay when just converting the score once when the player kills a monster. If you want to keep the score refresh every frame, this will surely be negligable scince you only have one number to convert. The only case I can see where it would be significant, if you're making a RPG and if you want to keep the HP, Max HP, MP, Max MP of all characters and *all* this refreshed every frame, this may be significant (if there is 4 party member, this makes 16 16-bit numbers). Anyway, this would eat a lot of VRAM update during VBlank, so I think it's better to upload the value only when you're sure the player lost/recovered some HP or use/recovered some MP.


Quote:
There is one thing I really like about Bregalad's method, though: you could jump to the middle of the routine if you were interested in converting smaller numbers. Both methods are nice, but I'm trying hard to make this one perform faster.

Yeah, this is cool, but keep in mind this is not my method, it's also here everywhere else.

_________________
Life is complex: it has both real and imaginary components.


Top
 Profile  
 
 Post subject:
PostPosted: Sun Aug 28, 2005 7:25 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10172
Location: Rio de Janeiro - Brazil
Bregalad wrote:
Mine also is much shorter and waste probably about 3 times less ROM.

Oh, yeah. This thing can get pretty large when unrolled.

Quote:
Hey, the get number from the table thing is cool !

It saves you the CMP's and make constant timing possible. And is faster than actual addition. However, the traditional method WILL SKIP some aditions, killing constant timing, but speeding up things sometimes.

Quote:
Scince you usually don't want to converse dozens of large number in a single frame, this probably won't cause any slowdown in gamaplay when just converting the score once when the player kills a monster. If you want to keep the score refresh every frame, this will surely be negligable scince you only have one number to convert. The only case I can see where it would be significant, if you're making a RPG and if you want to keep the HP, Max HP, MP, Max MP of all characters and *all* this refreshed every frame, this may be significant (if there is 4 party member, this makes 16 16-bit numbers). Anyway, this would eat a lot of VRAM update during VBlank, so I think it's better to upload the value only when you're sure the player lost/recovered some HP or use/recovered some MP.

You're probably right. I gess the best way is to update only when the numbers change, so the impact on overall speed is much smaller.

Quote:
Yeah, this is cool, but keep in mind this is not my method, it's also here everywhere else.

I know, as much as the other one isn't mine either! =) I just call it that because you presented some code for it and all, and seemed to like it and used since this thread first started. So, by "Bregalad's method" I actally mean "the method Bregalad uses". =)


Top
 Profile  
 
 Post subject:
PostPosted: Sun Aug 28, 2005 10:20 am 
Offline
User avatar

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
Bregalad wrote:
Yeah, this is cool, but keep in mind this is not my method, it's also here everywhere else.


tokumaru wrote:
I know, as much as the other one isn't mine either! =) I just call it that because you presented some code for it and all, and seemed to like it and used since this thread first started. So, by "Bregalad's method" I actally mean "the method Bregalad uses". =)


I'm always careful about how I refer to things people present here, in order to avoid encouraging identification with the topics, since that leads to defensiveness. Often when people start referring to so-and-so's idea, they act as if so-and-so is stuck with that idea alone and won't try anything different (apologies to anyone named so-and-so).

I'd call it "the method Bregalad described earlier" or come up with a short descriptive phrase for the method itself (perhaps "repeated subtract-and-compare").


Top
 Profile  
 
 Post subject:
PostPosted: Sun Aug 28, 2005 12:39 pm 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7320
Location: Chexbres, VD, Switzerland
That's pretty much it, I'm not against the shift method, but I think the substation/comparison is much more flexible and easily implementable in a game that should convert both huge and small numbers. I'm still waiting the results for 16-bit and 24-bit version of the shift method, it may be faster and may not. And I really think unrolling the loop and stuff is worthless because you'll definitely not convert a lot of number. Optimal and constant timing is much more needed for monster AI or sprite engine implementation, or scrooling engine, and eventually the sound engine (that is typically much more slower when all chanells plays a new note, than if all of them are just disabled and ignored, heh).

_________________
Life is complex: it has both real and imaginary components.


Top
 Profile  
 
 Post subject:
PostPosted: Tue Jan 31, 2006 10:58 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19355
Location: NE Indiana, USA (NTSC)
I just posted a 16-bit binary to decimal converter on the wiki. It should take about 700 cycles. Now you can easily display your character's gold.


Top
 Profile  
 
 Post subject: my algorithm
PostPosted: Fri Apr 21, 2006 5:30 pm 
Offline
User avatar

Joined: Thu Feb 02, 2006 7:07 am
Posts: 117
Location: Chile (South America), Quilpué
2 algorithms for 6502 simulator

just i want sharing my algorithm, sacrifices 200 bytes for faster..

Code:
; bin 8 bits to 2 digits bcd, worst case around 22 cycles
; best case around 22 cycles.
; the price are 200 bytes of rom.
; input: load a with hex to convert

   .ORG $0003   ; Store machine code starting here   
   
hundreds_bcd  = $03   ; memory addresses      
tens_bcd      = $04
units_bcd     = $05        
   
start:
   LDA #99
   JSR bin8to_bcd
   
   BRK
   
bin8to_bcd:                  
            
.work_tens_units
   TAY            
   LDX table_tens,y   
   STX tens_bcd      
   LDX table_units,y   
   STX units_bcd      
            
   RTS

   .ORG $8000   
table_tens:
   .DB $00, $00, $00, $00, $00, $00, $00, $00, $00, $00
   .DB $01, $01, $01, $01, $01, $01, $01, $01, $01, $01
   .DB $02, $02, $02, $02, $02, $02, $02, $02, $02, $02
   .DB $03, $03, $03, $03, $03, $03, $03, $03, $03, $03
   .DB $04, $04, $04, $04, $04, $04, $04, $04, $04, $04
   .DB $05, $05, $05, $05, $05, $05, $05, $05, $05, $05
   .DB $06, $06, $06, $06, $06, $06, $06, $06, $06, $06
   .DB $07, $07, $07, $07, $07, $07, $07, $07, $07, $07
   .DB $08, $08, $08, $08, $08, $08, $08, $08, $08, $08
   .DB $09, $09, $09, $09, $09, $09, $09, $09, $09, $09   
   
table_units:
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09

_________________
Good day to nesdev people. Lord..
Author of nothing =P
UTFSM Sansano programmer.. lord_Chile
Saludos a la Sede JMC de la UTFSM... Viña del Mar, CHILE


Top
 Profile  
 
 Post subject: my another algorithm
PostPosted: Fri Apr 21, 2006 5:32 pm 
Offline
User avatar

Joined: Thu Feb 02, 2006 7:07 am
Posts: 117
Location: Chile (South America), Quilpué
Code:
; bin 8 bits to 3 digits bcd, worst case around 43 cycles
; best case around 37 cycles.
; the price are 200 bytes of rom.
; input: load a with hex to convert

   .ORG $0003   ; Store machine code starting here   
   
hundreds_bcd  = $03   ; memory addresses      
tens_bcd      = $04
units_bcd     = $05        
   
start:
   LDA #199
   JSR bin8to_bcd
   
   BRK
   
bin8to_bcd:         
   LDX #$00      
   STX hundreds_bcd
   
   CMP #200
   BCC .nextHundCheck
   SBC #200
   LDX #$02
   STX hundreds_bcd
   
   BCS .work_tens_units
   
.nextHundCheck   
   CMP #100
   BCC .work_tens_units ; number is 0 hundreds
   
   SBC #100
   LDX #$01
   STX hundreds_bcd            
                     
.work_tens_units
   TAY            
   LDX table_tens,y   
   STX tens_bcd      
   LDX table_units,y
   STX units_bcd   
            
   RTS

   .ORG $8000   
table_tens:
   .DB $00, $00, $00, $00, $00, $00, $00, $00, $00, $00
   .DB $01, $01, $01, $01, $01, $01, $01, $01, $01, $01
   .DB $02, $02, $02, $02, $02, $02, $02, $02, $02, $02
   .DB $03, $03, $03, $03, $03, $03, $03, $03, $03, $03
   .DB $04, $04, $04, $04, $04, $04, $04, $04, $04, $04
   .DB $05, $05, $05, $05, $05, $05, $05, $05, $05, $05
   .DB $06, $06, $06, $06, $06, $06, $06, $06, $06, $06
   .DB $07, $07, $07, $07, $07, $07, $07, $07, $07, $07
   .DB $08, $08, $08, $08, $08, $08, $08, $08, $08, $08
   .DB $09, $09, $09, $09, $09, $09, $09, $09, $09, $09   
   
table_units:
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09
   .DB $00, $01, $02, $03, $04, $05, $06, $07, $08, $09

_________________
Good day to nesdev people. Lord..
Author of nothing =P
UTFSM Sansano programmer.. lord_Chile
Saludos a la Sede JMC de la UTFSM... Viña del Mar, CHILE


Top
 Profile  
 
 Post subject:
PostPosted: Fri Apr 21, 2006 10:19 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10172
Location: Rio de Janeiro - Brazil
Hi, lord_Chile! I'm glad to see that you are practicing and all... very good!

Just want to say one thing you are doing wrong here. Your code starts at $0003, but so do your variables! If you look in the memory window, the beginning of the code is overwritten by the result of the routine... The simulator allows this, because the code is overwritten after it has already run, but in a real life situation that would be impossible, because you can't define code in RAM (unless you have a routine to copy code from ROM to RAM, wich isn't the case, you're using .org) and you can't have variables in ROM. So what you did there is a little paradox...!

Just make sure you separate code from the variables. In your program the variables could easily use $00, $01 and $02, and then program begins at $03, as it already does.

When writing NES stuff you'll probably use .org $8000 or .org $c000 for code.

Again, I'm really glad you are figuring this stuff out!


Top
 Profile  
 
 Post subject: mmmmm
PostPosted: Wed Apr 26, 2006 2:46 pm 
Offline
User avatar

Joined: Thu Feb 02, 2006 7:07 am
Posts: 117
Location: Chile (South America), Quilpué
yes, i understand.. it's for 6502 simulator. i did implement it for nesasm, and all ok. just i keep my tables and code in rom, then i use ram for variables. see you. thanks to you for teaching me any important things

_________________
Good day to nesdev people. Lord..
Author of nothing =P
UTFSM Sansano programmer.. lord_Chile
Saludos a la Sede JMC de la UTFSM... Viña del Mar, CHILE


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 30 posts ]  Go to page Previous  1, 2

All times are UTC - 7 hours


Who is online

Users browsing this forum: Revenant, Yahoo [Bot] and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group