Page 1 of 2
BinToBcd
Posted: Wed Apr 28, 2021 7:01 am
by rudla.kudla
Hi,
recently i improved my routine for converting binary numbers to BCD and maybe it may useful to somebody else. So here it is. It uses BCD mode, so no luck for NES users.
It repeatedly divides the binary number by 2, and multiplies BCD number by 2 (by BCD adding it to itself) adding the carry. (I found the algorithm in some book when I was just the beginning 6502 programmer and could not understand it then
Numbers of arbitrary length can be converted and the routine will automatically compute the minimal number of bytes necessary to represent the number in BCD. (1 for 99, 2 for 100 etc.).
After conversion, it is easy to print the number using hexadecimal number printing routine.
Any optimizations are always welcome of course
Rudla
Code: Select all
NUM = 131
FORMAT_BUF = $4000
org $2000
;123456789045 = $1c $be $99 $1a $35
lda #$35
sta NUM
lda #$1a
sta NUM+1
lda #$99
sta NUM+2
lda #$be
sta NUM+3
lda #$1c
sta NUM+4
lda #5
jsr BinToBcd
;a = 5 buf = $45 $90 $78 $56 $34 $12
lda #99
sta NUM
lda #1
jsr BinToBcd
;a = 1 buf = $99
rts
BinToBcd
;Convert binary number to BCD.
;Arbitrary number sizes are supported.
;In:
; NUM buffer with number to convert
; a number of bytes in the number
;Out:
; FORMAT_BUF output buffer
; a number of BCD bytes (at least 1)
;Uses:
; x,y, t1,t1_h, t2
bcd_size = 128
num_size = 129
b = 130
ldx #0 ; initial result is 0, 1 byte size
stx FORMAT_BUF
inx
stx bcd_size
;---Skip leading zeroes in the number (this may be removed, it we need the routine smaller)
tay
iny
skip dey
beq done ;the number is zero, we are done
lda NUM-1,y
beq skip
sty num_size
sed
;--- Process one byte at a time
next_byte
ldy num_size
lda NUM-1,y
sta b
sec ;set top bit of the mask to 1
bcs loop
shift_byte
;--- BCD = BCD * 2 + CARRY
ldy #1
ldx bcd_size
mul2
lda FORMAT_BUF-1,y
adc FORMAT_BUF-1,y
sta FORMAT_BUF-1,y
iny
dex
bne mul2
bcc loop
;--- BCD must be one byte bigger (we need to store our extra 1 in CARRY there)
lda #1
sta FORMAT_BUF-1,y
sty bcd_size ;as the x is 1 based, we can directly store is as new bcd_size
;we cound use INC here, it would be slower, however.
clc
loop rol b ;Divide by two, if result is 0, end. As we initially set the 0 bit to 1, this is in fact loop to 8.
bne shift_byte
;--- Repeat for all bytes in the number
dec num_size
bne next_byte
cld
done
lda bcd_size
rts
Re: BcdToBin
Posted: Wed Apr 28, 2021 7:21 am
by BillG
Off the top of my head, there are three other common ways to convert a binary number to BCD:
* repeated divide the number by 10 to extract digits
* repeated subtraction of powers of ten, 10000, 1000, 100 and 10 to extract digits
* double dabble
https://en.wikipedia.org/wiki/Double_dabble
It will be interesting to see further comparison and analysis between them.
Re: BinToBcd
Posted: Wed Apr 28, 2021 10:34 am
by IamRob
The double dabble was a neat read.
But the math is clear.
The subtraction method only goes through the loop once for each digit. (for a 12-digit number is 12 times)
The division method has too much latency from the division.
This method goes through the loop once for each bit and also at least 1-# of digits for the addition (5-bytes = 40 bits, at least 40 times through the loop) (plus the instruction of adding the digits which with a 12-digit number averages 6 times for each bit processed) (40 * 6 = 240 times through the loop).
Double Dabble has a very high latency of separating each nybble and seeing if it is 5 or greater and adding 3 to each nybble. Where is a 4-bit computer when you need one?
Note: my math may be subject to errors as I am not a computer.
Re: BinToBcd
Posted: Wed Apr 28, 2021 1:39 pm
by BillG
It repeatedly divides the binary number by 2, and multiplies BCD number by 2 (by BCD adding it to itself) adding the carry. (I found the algorithm in some book when I was just the beginning 6502 programmer and could not understand it then
Upon closer examination, your approach essentially does what double dabble does, but with a clearer explanation.
From the wiki page about double dabble:
Essentially, the algorithm operates by doubling the BCD value on the left each iteration and adding either one or zero according to the original bit pattern. Shifting left accomplishes both tasks simultaneously. If any digit is five or above, three is added to ensure the value "carries" in base 10.
Edit: double dabble does not depend upon hardware having a decimal mode or decimal adjust instruction hence all that stuff about checking the values of nybbles and adding a correction factor.
Re: BinToBcd
Posted: Thu Apr 29, 2021 6:02 am
by GARTHWILSON
Re: BinToBcd
Posted: Thu Apr 29, 2021 6:55 am
by rudla.kudla
The basic principle of the routine is not a new thing. The interesting thing about this routine is, that it can accept numbers of arbitrary length.
Re: BinToBcd
Posted: Thu Apr 29, 2021 9:10 am
by rudla.kudla
The double dabble was a neat read.
But the math is clear.
The subtraction method only goes through the loop once for each digit. (for a 12-digit number is 12 times)
Wouldn't subtraction method do a loop of 1..9 steps for each digit (repeatedly subtracting 10, 100, 1000 etc?) That would make it 12*5 times for 12 digit number in average? Am I missing something?
Re: BinToBcd
Posted: Thu Apr 29, 2021 4:32 pm
by IamRob
The double dabble was a neat read.
But the math is clear.
The subtraction method only goes through the loop once for each digit. (for a 12-digit number is 12 times)
Wouldn't subtraction method do a loop of 1..9 steps for each digit (repeatedly subtracting 10, 100, 1000 etc?) That would make it 12*5 times for 12 digit number in average? Am I missing something?
The subtraction method that is on the web can be streamlined even more to give better results. The, "once through the loop per digit" can be achieved by a larger table.
First I tried to double the speed by doubling the table size and inserting intermediary values, the table then consists of 10, 50, 100, 500, 1000, 5000, 10000, 50000 ... etc. This basically creates a value table that can reduce the loop from 1-9 to 1-4 for an average of 2 or 3 times through the loop for each digit. Subtracting 5000 would be the same as subtracting 1000 x 5 times.
When this worked, I realized I could get a 1:1 ratio, but at a cost to memory.
The table could be expanded even more. 10,20,30 .. 90, 100,200,300 .. 900, 1000,2000,3000 .. 9000 ... etc.
This method would give a 1:1 digit per loop.
Re: BinToBcd
Posted: Thu Apr 29, 2021 6:21 pm
by rudla.kudla
That would not be so effective. For example in case of 3000, you would first have to try decrement by 9000, realize the value is not big enough and retry for smaller value.
So you just 'flip' the loop and instead of doing more smaller subtractions, you would do more overflowing ones.
Re: BinToBcd
Posted: Thu Apr 29, 2021 8:14 pm
by barrym95838
My point of view may be in the minority, but I would value compactness of code over execution speed in this application (which may likely be for a human-targeted display), unless there is some kind of hard real-time requirement. In the absence of that requirement "fast enough" and "small enough" are subjective qualities.
I haven't fleshed out my strategy yet, but I think I might employ a version of my little "divmod10" routine and form the BCD result from the remainder right-to-left a nybble at a time, repeating until the quotient is zero. It certainly wouldn't be a speed champion, but I can imagine the whole thing fitting in a few dozen bytes of code without the need for any look-up tables.
Re: BinToBcd
Posted: Thu Apr 29, 2021 9:45 pm
by GARTHWILSON
Responding to Mike's post immediately above:
The intro article for the section of my website on large look-up tables for ultrafast scaled-integer arithmetic has this paragraph:
- For converting hex numbers to other bases for output (which will normally be a string), initialize a blank string. You will build it from right to left. Divide your number by what's in variable BASE, and use the remainder to add a text digit to the build, even if it's a 0. Keep doing that until there's 0 in the number. You can add a decimal point or other characters between digits, e.g. 12.345 or 12:36:40 (actually you might want to change BASE from 10 to 6 and back for the time readout, if you started with a number of seconds!)
The Forth code repeated for each digit is only six instructions (twelve bytes), and works for converting hex to any base:
Code: Select all
: # ( d1 -- d2 )
BASE @ UD/MOD
ROT >DIGIT HOLD ;
Re: BinToBcd
Posted: Fri Apr 30, 2021 5:56 am
by IamRob
That would not be so effective. For example in case of 3000, you would first have to try decrement by 9000, realize the value is not big enough and retry for smaller value.
So you just 'flip' the loop and instead of doing more smaller subtractions, you would do more overflowing ones.
Not quite. I will try to put the way I think it could work into words.
The idea would be to check the highest byte of each value before doing the subtraction. That way the loop is very short ( just decrementing the x-reg for each hi-byte in the table ) and the subtraction is only done when the search finds the table value is less than or equal to the current value being subtracted from. Only one subtraction then would need to be done for the hex bytes of that value to get each digit.
There should be a bit of a speed increase when doing comparisons to get the top value to subtract, rather than subtracting a multiple each time.
Re: BinToBcd
Posted: Fri Apr 30, 2021 8:46 am
by John West
The idea would be to check the highest byte of each value before doing the subtraction. That way the loop is very short ( just decrementing the x-reg for each hi-byte in the table ) and the subtraction is only done when the search finds the table value is less than or equal to the current value being subtracted from. Only one subtraction then would need to be done for the hex bytes of that value to get each digit.
It has to do two subtractions in many cases. For example, if the input number is 79999 ($1387f), the loop on the first byte will get down to 80000 ($13880), see that the first byte matches, and conclude that that first digit might be 8. It has do the comparison all the way to the lowest byte to find that it isn't. But even with that it does look like an improvement over the "subtract powers of 10" version.
I'm still fond of double-dabble for its simplicity and versatility. Change the "half" and "double" parts, and it can handle conversions between any two formats, including mixed radix ones like HH:MM:SS for time.
Re: BinToBcd
Posted: Sat May 01, 2021 2:07 am
by JimBoyd
- For converting hex numbers to other bases for output (which will normally be a string), initialize a blank string. You will build it from right to left. Divide your number by what's in variable BASE, and use the remainder to add a text digit to the build, even if it's a 0. Keep doing that until there's 0 in the number. You can add a decimal point or other characters between digits, e.g. 12.345 or 12:36:40 (actually you might want to change BASE from 10 to 6 and back for the time readout, if you started with a number of seconds!)
Something like this?
Code: Select all
: :00 ( D1 -- D2 )
RB DECIMAL # 6 BASE ! #
ASCII : HOLD ;
: .TIME ( D -- )
RB DECIMAL
<# # ASCII . HOLD
:00 :00 #S #>
TYPE SPACE ;
Note: RB is a word in Fleet Forth that causes the word it is in to restore the value of base to what it was prior to executing ( calling ) RB .
The Forth code repeated for each digit is only six instructions (twelve bytes), and works for converting hex to any base:
Code: Select all
: # ( d1 -- d2 )
BASE @ UD/MOD
ROT >DIGIT HOLD ;
Fleet Forth does not have the word >DIGIT . Its functionality incorporated in # . Do you see a lot of use for it outside of # ?
Re: BinToBcd
Posted: Sat May 01, 2021 2:13 am
by GARTHWILSON
Fleet Forth does not have the word >DIGIT . Its functionality incorporated in # . Do you see a lot of use for it outside of # ?