It is currently Wed Dec 13, 2017 7:41 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 30 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: binary to decimal
PostPosted: Fri Feb 25, 2005 1:28 pm 
Online
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
Hi
The NES has no BCD mode wich is a usefull feature in the process of binary to decimal convertion. But the games must do it somehow, to display scores, health, items, etc.
How do most games achieve this convertion? That is, if there is a convertion at all, 'couse I was told that some times it is better to do the whole math already in decimal.
The best method I found so far, is to repeatedly subtract 10000s, 1000s, 100s and 10s to get the digits. Does anyone use a better method?


Top
 Profile  
 
 Post subject:
PostPosted: Fri Feb 25, 2005 2:37 pm 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7314
Location: Chexbres, VD, Switzerland
No, this is the best method. I looked at the scource of a game (Final Fantasy) and there was one routine to decode 6 digits, one to decode 5 digits, etc... Each one was calling two others routines. The first one does substract the value 10n for each digit and storing them into ram (the routine to decode 6 ditits takes the whole algorithm, but the one who decodes only 5 digits skips one substraction, etc...). The segond routine does remove all unused zeroes (stuff like 000947 will become ___947).

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


Top
 Profile  
 
 Post subject:
PostPosted: Fri Feb 25, 2005 10:31 pm 
Offline
Site Admin
User avatar

Joined: Mon Sep 20, 2004 6:04 am
Posts: 3487
Location: Indianapolis
I do it the cheap way.. one byte per digit. And just wrap it around if it goes past the 9 character.

But I can see where storing in hex would save lots of memory, in an RPG or other game that displays a lot of numbers.


Top
 Profile  
 
 Post subject:
PostPosted: Fri Feb 25, 2005 11:42 pm 
Online
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
Memblers wrote:
I do it the cheap way.. one byte per digit. And just wrap it around if it goes past the 9 character.


This is probably the best thing to do if you don't have to do any sort of complex calculations with the number. Like the score in a game, that you just have to add to it, then I think it works quite well. Just copy those bytes to the name table and you're done!

Memblers wrote:
But I can see where storing in hex would save lots of memory, in an RPG or other game that displays a lot of numbers.


Yeah, I guess. This could eat a lot of memory in an RPG.

I searched the net for info on this, and found a pretty interesting way of doing binary->BCD convertion:
http://www.engr.udayton.edu/faculty/jlo ... o_BCD.html

But my implementation of it in 6502 assembly for an 8-bit number took longer then the worst case in my 16-bit 10000s, 1000s, etc. subtractor. That must be because I like code that takes a fixed ammount of cycles to run regardless of the input. The subtraction method isn't uniform, but the other one is.


Top
 Profile  
 
 Post subject:
PostPosted: Fri Feb 25, 2005 11:45 pm 
Online
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
Bregalad wrote:
No, this is the best method. I looked at the scource of a game (Final Fantasy) and there was one routine to decode 6 digits, one to decode 5 digits, etc... Each one was calling two others routines. The first one does substract the value 10n for each digit and storing them into ram (the routine to decode 6 ditits takes the whole algorithm, but the one who decodes only 5 digits skips one substraction, etc...). The segond routine does remove all unused zeroes (stuff like 000947 will become ___947).


People have told me this is the best way, but I had to ask the actual NES programmers what they used! =D
Could you tell me the addresses of these routines? I've been looking into the sources of other games too but couldn't find such things.


Top
 Profile  
 
 Post subject:
PostPosted: Sat Feb 26, 2005 10:32 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7314
Location: Chexbres, VD, Switzerland
Okay. First, FF1 swaps the 16kb ROM bank n°14 (#$0e) into $8000-$bfff during every menu/shop opperation, so the programm doing this is in this rombank. Before calling thoose routines, a 8 bit number is stored intp $10, or a 16 bit number into $10-$11, or a 24 bit number into $10-$12 ($12 MSB, $10 LSB).
For example, to convert the gils from binary to decimal, this is done at the adress $8e4a that will copy your 24-bit money value (into $601c-$601e) to the temporary values $10-$12 then jump to the 6 digits conversion routine.
The adresses are :
1 digit : $8e5c
2 digits : $8e66
3 digits : $8e70
4 digits : $8e7a
5 digits : $8e84
6 digits : $8e8e
The result data's adress is at [$3e]. The format is directly FF1's pattern table numbers (such as $80-$89 for 0-9) and if unused zeroes were there (i.e. 00240 -> __240) the space will be $ff.

Note that exactly the same routines are found in FF2 and FF3, but not at the same adress.

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


Top
 Profile  
 
 Post subject:
PostPosted: Sun Jul 24, 2005 7:00 am 
Old topic, I know, but if you have code for division and modulus displaying numbers is really simple. Zero out 5 bytes or so in RAM. Take the low 4 bits, if they're less than 10, put them into the 5th byte, otherwise subtract 10, put that in the 5th byte and put 1 in the 4th byte. Then get the next 4 bits and repeat, moving up a byte. Whenever you store a number add what's already there. Basically you break it down into the basic steps, like 1234 = 4 + 30 + 200 + 1000.

As for trimming leading zeros, the code just scans each byte, and doesn't print anything until it hits a nonzero digit. It counts how many digits it prints and will print zeros if at least one digit has printed. Finally, if it's hit the end and nothing has been printed (the value is 0), it just spits out a zero so you don't end up with a blank spot on the screen.

I'd supply code, but it's not NES code. :P


Top
  
 
 Post subject:
PostPosted: Wed Jul 27, 2005 12:41 pm 
Bleh wrote:
Old topic, I know, but if you have code for division and modulus displaying numbers is really simple. Zero out 5 bytes or so in RAM. Take the low 4 bits, if they're less than 10, put them into the 5th byte, otherwise subtract 10, put that in the 5th byte and put 1 in the 4th byte. Then get the next 4 bits and repeat, moving up a byte. Whenever you store a number add what's already there. Basically you break it down into the basic steps, like 1234 = 4 + 30 + 200 + 1000.


This is a nice way of solving the problem... However there is one more check you need to do that might make things a little slow: when you get a "9" from the 4 bits and you have to add it to a space that already has a "1", you must check for this overflow.

Also I don't know if I got this right... I tried it here and it didn't make much sense... Take, like, $2D. Get the "D" -> 13 is bigger than 10, so take ten, store the 3 in the last space and a 1 in the previous. Now get the "2", 2 is smaller than 10 so add it to the 1 that was already in the second space and you get 3. Thats 33, not 45 as it should be... The "2" became "20" and not "32" as it should...

I guess there is something missing here, but if this process involves any actual division (you said something about division), then it is not worth it... Maybe it uses repeated subtraction like the method described earlier...?

Bleh wrote:
I'd supply code, but it's not NES code. :P


Could you, anyway? Just to clarify things!? =)


Top
  
 
 Post subject:
PostPosted: Thu Aug 25, 2005 4:22 pm 
Online
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
Hey!

Sorry to get back at this, but I was never satisfied with the stuff I got from this topic (many subtractions, that proved to be a reeeeealy slow - not so much, it seems...- method)... and now I found what the best way to perform BINARY TO DECIMAL conversion is (IMO).

This is a routine I just coded, based on something I saw at 6502.org, only I changed it to generate unpacked BCD digits (wich is good for us NES developers, as all we want in the end is the damn tile index):

Code:
BIN = $00
BCD = $01

   .ORG $8000

   LDA #$FF   ;Some value to test.
   STA BIN

B2D_0   LDA #$00   ;Clear all BCD digits.
   STA BCD+0
   STA BCD+1
   STA BCD+2
   LDX #$08   ;Set the shift counter.
B2D_1
   ASL BIN      ;Shift from the binary into the decimal.
   ROL BCD+0
   ROL BCD+1
   ROL BCD+2

   DEX      ;Check if it was the last shift.
   BEQ B2D_END

   LDA BCD+0   ;Compare UNITS to 5.
   CMP #$05
   BMI B2D_2

   CLC      ;If 5 or more, force a decimal overflow.
   ADC #$7B
   STA BCD+0
B2D_2
   LDA BCD+1   ;Compare TENS to 5.
   CMP #$05
   BMI B2D_1

   CLC      ;If 5 or more, force the overflow.
   ADC #$7B
   STA BCD+1

   JMP B2D_1   ;Do it all again.
B2D_END


I did a few tests with it and it worked fine! And quite fast in my opinion, although this only converts an 8-bit number to 3 decimal digits. I'll try a larger version later, to check the execution times. Also, this code can be converted to fixed execution time, if we use a small table instead of actual additions. Don't know if it would be any faster, though.

The idea behind this code is the following:
.Shift the binary number into the decimal one, from the right;
.When any of the decimal places has a value equal or greater than 5 (wich means a *decimal* overflow is going to happen during the next shift) we add 123 ($7B) to it, forcing our decimal overflow to become a binary one, wich is the only kind the NES' CPU cares about;
.The reason we add before the shifting is because we don't have to handle any carry, the shifting will take care of it in the next step. So, instead of adding the actual value that will cause a carry when the decimal place has a value over 9, we add half that value when the place has a value over 4;

Well, that's it. Just wanted to share! =)

EDIT: Man, I just checked the link I posted when the topic was fresh and it describes the exact method I just *rediscovered*... I guess I was just too stupid to understand it back then, and that's why my previous implementation was so bad. Actually, I can't even tell if the new one is any good yet! Anyway, this method certainly deserves some attention, and I'll keep trying to improve it.

EDIT2: Shit! Most of the time it is still faster to subtract repeatedly... But I just hate how uneven the execution times are with that... Anyway, sorry to bug you people with my personal conflicts! =)


Top
 Profile  
 
 Post subject:
PostPosted: Fri Aug 26, 2005 8:32 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7314
Location: Chexbres, VD, Switzerland
Well, I didn't understand this method, but it looks like slower than substracting, but still the code is shorter.

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


Top
 Profile  
 
 Post subject:
PostPosted: Fri Aug 26, 2005 11:05 pm 
Online
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
Yes, with this implementation it really is slower. But this method is SO interesting I can't just ignore it (also, I already got better implementations by now, wich I'll talk about at the bottom of this post). Let me show you a quick example (using nibbles, instead of bytes, for simplicity):
Code:
Let's say we want to convert the binary number 1100 (12, in decimal). We reserve the space for the decimal digits we are going to fill, and then start shifting. Our initial set-up looks like this (T = TENS, U = UNITS):

T    U    BINARY
0000 0000 1100

Now, the first shift:

T    U    BINARY
0000 0001 100x

The value in UNITS is smaller than 5, so we just shift again:

T    U    BINARY
0000 0011 00xx

Still smaller, shift for the third time:

T    U    BINARY
0000 0110 0xxx

Now, this is where it gets interesting. Our nibble will only overflow (cause a carry to the next one) when it's value is over 15. But we want to simulate the decimal system, where the carries are supposed to happen on values greater than 9. So, the trick in this method is to detect when the digit goes over 9, and force a carry in this case by adding 6 to our digit. Why 6? Well, suppose our UNITS nibble reached a value of 10, wich is over the limit for decimal, but not for hex (where it could be represented with an "A"). So, what do we do? Force it to be over the limit. 10 + 6 equals 16 ($10), wich is over the limit in hex, and will cause a carry to the next nibble, the TENS nibble. So, 10(decimal) becomes 10(hex), wich is the correct representation we want.

However, it is not practical to detect if the digit has gone over 9 after it does so, since we wold waste precious time propagating the carry to the next nibble/byte. So, we detect the overflow BEFORE it happens. If a digit has a value of 5 or more, it will sure be over the limit AFTER the next shift (wich will double the number, thus resulting in a number larger than 9). And since we are detecting it in advance, the value we add must also be adjusted: instead of 6, we add 3 (wich will also be doubled after the shift, resulting in an effective 6). This saves us the trouble of propagating carries.

Just watch the rest of the example. The value in UNITS went over 4 (it's 110, wich is 6 in decimal), so we add 3 to it:

T    U    BINARY
0000 1001 0xxx

And we get this new value (1001) in the UNITS. Now, just watch as in the next shift, the most significant bit (now set) is tranfered to the TENS digit (without us propagating it during the adition, it gets propagated during the shift):

T    U    BINARY
0001 0010 xxxx

Now, look at that! After the last shift we get the exact digits we wanted, 1(TENS) and 2(UNITS), making up a perfect decimal 12!

The code I posted above is just modified to work with BYTES instead of NIBBLES, so we add 123 instead of 3 to have the carry placed correctly.

And I recently did an upgrade to the code. I replaced the ADC's with a small lookup table of 10 bytes, and unrolled the loop, wich resulted in a code with no branching at all, and it wasn't very large either. This would be impossible with the other method. It would result in a VERY large code and you could never abandon the branches. I also took out unnecessary operations, used for the general case, but can be deleted if you know something is NEVER going to happen at an specific point, when unrolling loops.

The result is a piece of code wich now can compete with the subtraction method. When comparing both methods, I got the following results:

Cycles taken to convert an 1-byte value:
REPEATED SUBTRACTION: best case(1): 130 cycles; worst case(199): 260 cycles;
"ADD 123" METHOD: fixed 160 cycles;

By this result, I conclude that the new method is better, as it's execution time is constant and is faster than the average speed of the other method. Of course, these results are from my (sometimes crude) implementation of the algorithms.

I'll soon code an optimized version of the new method working on larger numbers (16-bit, 24-bit, etc) and test both algorithms further.

Am I insisting on something that isn't really a big deal here? I happen to find this topic quite interesting... If any of you guys think this is beyond the scope of this board just say so and I'll keep testing quiet here, ok? please! =)

-tokumaru-


Top
 Profile  
 
 Post subject:
PostPosted: Fri Aug 26, 2005 11:24 pm 
Offline
User avatar

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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.


Top
 Profile  
 
 Post subject:
PostPosted: Fri Aug 26, 2005 11:41 pm 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7314
Location: Chexbres, VD, Switzerland
Well, unless you're able to do it in 16-bit and 24-bit, this isn't really significant. I'm pretty sure that the simpler method for 8 bit is :
Code:
lda #$00
sta Hundreds
sta Tens
lda Number
_loop
cmp #100
bcc _next
sbc #100
inc Hundreds
bne _loop
_next
_loop2
cmp #10
bcc _next2
sbc #10
inc Tens
bne _loop2
_next2
sta Units
rts

It inolves few variables and the loops are quite short for bytes and time (190-199 would probably be the worst case ?). Trough, a better method is needed when more than one single byte consist the number.
Your method looks interesting, but I'm still pretty confused, it looks like to work fine. But what about 24-bit conversion ?

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


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 27, 2005 12:21 am 
Bregalad wrote:
Well, unless you're able to do it in 16-bit and 24-bit, this isn't really significant.


Sure you can handle larger numbers! =) I just haven't coded such a version yet.

Quote:
I'm pretty sure that the simpler method for 8 bit is :
Code:
lda #$00
sta Hundreds
sta Tens
lda Number
_loop
cmp #100
bcc _next
sbc #100
inc Hundreds
bne _loop
_next
_loop2
cmp #10
bcc _next2
sbc #10
inc Tens
bne _loop2
_next2
sta Units
rts

It inolves few variables and the loops are quite short for bytes and time (190-199 would probably be the worst case ?). Trough, a better method is needed when more than one single byte consist the number.

This actually performs very fast! But as you said, you'll have problems with values larger than a byte, since you can't CMP values that large in one step... you'll probably end up having to perform a full subtraction...
But this short version easily beats the fastest version of the "add 123" method so far. In the other hand, expanding the "add 123" method does not make an impact as great in speed as in this case, I believe.

Also, I find very annoying how much execution time varies with the subtraction method. Your code converts a "1" in around 29 cycles, but takes around 177 cycles to convert "199". That's like, 6 times more! I don't like this variation. If we could have a more "constant time" routine, at the speed of at least the average of the subtraction method, I would be happy. I'm a big fan of constant timing, it avoids surprises!

I'll just keep trying to improve the algorithm, and in the end we benchmark both methods.

Quote:
Your method looks interesting, but I'm still pretty confused, it looks like to work fine. But what about 24-bit conversion ?


It took me a while to understand it too. There was no explanation at all, people just said "when this happens, do this". And in fact the logic worked, but I don't feel well using stuff I don't undertand. So, the other day I decided to just sit down and understand it. And then I did! =)
I'm sure you'll understand too, if you feel like it, of course. It may not even be of your interest, as you're already happy with the routine you have! =)


Top
  
 
 Post subject:
PostPosted: Sat Aug 27, 2005 1:25 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7314
Location: Chexbres, VD, Switzerland
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.
Anonymous wrote:
Sure you can handle larger numbers! =) I just haven't coded such a version yet.

Well, I'm glad to see witch method beats witch other for large numbers.
Quote:
Also, I find very annoying how much execution time varies with the subtraction method. Your code converts a "1" in around 29 cycles, but takes around 177 cycles to convert "199". That's like, 6 times more! I don't like this variation. If we could have a more "constant time" routine, at the speed of at least the average of the subtraction method, I would be happy. I'm a big fan of constant timing, it avoids surprises!

The method I described is just standard. Well, variable speed is needed anyway in any kind of algorithms... But I agree that could make bad susrpises.

Quote:
It took me a while to understand it too. There was no explanation at all, people just said "when this happens, do this". And in fact the logic worked, but I don't feel well using stuff I don't undertand. So, the other day I decided to just sit down and understand it. And then I did! =)
I'm sure you'll understand too, if you feel like it, of course. It may not even be of your interest, as you're already happy with the routine you have! =)

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.

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


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

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 7 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