Integer to BCD conversion works...but why?

[+slx]

I found the following code to convert a two-byte integer to BCD:

 

; Convert an 16 bit binary value into a 24bit BCD value
BIN2BCD LDA #0          ;Clear the result area
        STA RES+0
        STA RES+1
        STA RES+2
        LDX #16         ;Setup the bit counter
        SED             ;Enter decimal mode
_LOOP   ASL VAL+0       ;Shift a bit out of the binary
        ROL VAL+1       ;... value
        LDA RES+0       ;And add it into the result, doubling
        ADC RES+0       ;... it at the same time
        STA RES+0
        LDA RES+1
        ADC RES+1
        STA RES+1
        LDA RES+2
        ADC RES+2
        STA RES+2
        DEX             ;More bits to process?
        BNE _LOOP
        CLD             ;Leave decimal mode

This works but I completely fail to understand why and how. Is anyone able to enlighten me?

 

[Rybags]

At first glance it looks like it wouldn't work.

But it's processing the high bit first and doubling the output value every loop iteration.

So by the end of the loop everything should be correct.

 

Sample input value of 49152 unsigned binary (which is 2 high bits set, $C000)

First loop, output = 1

Second loop, output = 2+1 = 3

Third loop, output = 6+0 = 6

Fourth loop, output = 12+0 = 12

Then 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576.

Last loop, output = 49152 which is the correct value.

 

Whether this is the most efficient means, disregarding unrolling the loop or using lots of memory for another method, I don't know.

Edited February 27, 2020 by Rybags

[globe]

In cases like this it really helps to trace what the program does step by step.

 

Example binary value we want to convert to BCD: 32770

 

Initial values:

 

VAL1 = $80
VAL0 = $02

RES+0 = $00
RES+1 = $00
RES+2 = $00

 

Since we ASL/ROL VAL0 and VAL1 each loop it's easier to understand if we look at their binary value:

 

VAL1             VAL0
10000000    00000010

 

Important: all our additions happen in DECIMAL mode so when you add $06 + $06 you get $12 not $0C as a result.

 

--------------------beginning of loop-----------------------------------------------------------------------------
1st loop
ASL/ROL: SETS CARRY to 1			<- this is where most significant bit from VAL1 enters our decimal addition loop
VAL1		VAL0
00000000	00000100
RES+0 = $01				1
---------------------------------------------
2nd loop
ASL/ROL: CARRY = 0
VAL1		VAL0
00000000	00001000
RES+0 = $02				2
---------------------------------------------
3rd loop
ASL/ROL: CARRY = 0
VAL1		VAL0
00000000	00010000
RES+0 = $04				4
---------------------------------------------
4th loop
ASL/ROL: CARRY = 0
VAL1		VAL0
00000000	00100000
RES+0 = $08				8
---------------------------------------------
5th loop
ASL/ROL: CARRY = 0
VAL1		VAL0
00000000	01000000
RES+0 = $16				16	<- notice the result of decimal mode addition, without decimal mode we'd get $10 in RES+0
---------------------------------------------

skipping ...

---------------------------------------------
7th loop
ASL/ROL: CARRY = 0
VAL1		VAL0
00000001	00000000
RES+0 = $64				64
---------------------------------------------
8th loop
ASL/ROL: CARRY = 0
VAL1		VAL0
00000010	00000000
RES+1 = $01, RES+0 = $28		128	<- and another one, this time we carried over to RES+1, without decimal flag active we'd get $80 in RES+0 only
---------------------------------------------

skipping some more ...

---------------------------------------------
14th loop
ASL/ROL: CARRY = 0
VAL1		VAL0
10000000	00000000
RES+1 = $81, RES+0 = $92		8192
---------------------------------------------
15th loop
ASL/ROL: CARRY = 1				<- this is the 1 from VAL0 that was finally rolled all the way left and reached CARRY
VAL1		VAL0
00000000	00000000
RES+2 = $01, RES+1 = $63, RES+0 = $85	16385	<- and one more, we already have value in RES+2 - BCD 10K+ territory
---------------------------------------------
16th loop (the last one)
ASL/ROL: CARRY = 0
VAL1		VAL0
00000000	00000000
RES+2 = $03, RES+1 = $27, RES+0 = $70	32770
---------------------------------------------

BCD RESULT: 03 27 70 = 32770

--------------------end of loop-----------------------------------------------------------------------------------

So how does this work?

 

We add value of each bit to RES+0 - RES+2 but instead of using a table with BCD representation of bit values we start with most significant bit and double it with each iteration while using decimal mode addition.
So most significant bit from VAL1 gets doubled 16 times, the one next to it 15 etc... till we reach least significant in VAL0 and that one only gets added.
All those bits doubled and added together in decimal mode give as BCD coded RES+0 - RES+2 as a result.

[ChildOfCv]

Yeah it's just doubling the output number and adding the next input bit.  If it were still in binary mode, the output would end up exactly the same as the input.  But since it's using decimal mode to add, each doubling happens in decimal mode.

 

Note that without 3 output bytes, it will overflow after 9999.

[thorfdbg]

9 hours ago, slx said:

This works but I completely fail to understand why and how. Is anyone able to enlighten me?

This is essentially a 16+24 bit big shift register. The carry that is rotated out of VAL,VAL+1 is rotated back into RES,RES+1,RES+2. After 16 rotations, the number in VAL,VAL+1 moved out of the lower part and is now completely in the upper bits. As rotation is identical to doubling, the algorithm works, except that doubling is here done in decimal instead of binary.

 

[Rybags]

3 output bytes in plain BCD (no sign or exp) actually gives 6 digits so 999,999 which easily accomodates our 16-bit input.

[ChildOfCv]

8 hours ago, Rybags said:

3 output bytes in plain BCD (no sign or exp) actually gives 6 digits so 999,999 which easily accomodates our 16-bit input.

D'oh.  I only saw 2 output bytes.

[+slx]

Thanks for all the explanations. Very clever, I would never have come up with this.