Decimal to Binary Conversion

BitWise · Post by **BitWise** » Wed Mar 03, 2004 12:56 pm

After reading the thread on binary to decimal I tried implementing the reverse algorithm trying to avoid lookup tables and/or multiply by 10 routines. This is what I came up with.

Code: Select all

; Extracts a 16 bit binary number from a 24 bit BCD value.
;
; If the BCD value was bigger than 65535 then some bits will be left in
; BCD area at the end of of the conversion.
        
BCD2BIN LDX #16     ;Set the bit count
.OUTER  LDY #2      ;Set BCD byte count
        CLC         ;Ensure that C=0 on first shift
.INNER  LDA BCDW,Y  ;Divide the BCD byte by two
        ROR
        PHP         ;Save the bit that was shifted out
        .IF __65C02__
        BIT #$80    ;Does the hi nybble need correction?
        BEQ *+5
        SEC
        SBC #$30
        BIT #$08    ;Does the lo nybble need correction?
        BEQ *+5
        SEC
        SBC #$03
        .ELSE
        BIT BIT7    ;Does the hi nybble need correction?
        BEQ *+5
        SEC
        SBC #$30
        BIT BIT3    ;Does the lo nybble need correction?
        BEQ *+5
        SEC
        SBC #$03
        .ENDIF
        PLP         ;Finally recover the carry
        STA BCDW,Y
        DEY         ;Repeat for next BCD byte
        BPL .INNER
        ROR BINW+1  ;Catch the remainder
        ROR BINW+0
        DEX         ;And repeat
        BNE .OUTER
        
        BRK

; 6502 does not support BIT with immediate data so we must deposit
; these constants.

        .IF __6502__
        
BIT7    .DB $80
BIT3    .DB $08

        .ENDIF

bogax · Post by **bogax** » Wed Mar 03, 2004 11:34 pm

Can't say I've really thought it through, but my first thought is that it's a
shame to do all that correction in the code when the 6502 is already set up
to do it in the hardware.

You could do you're divisions by two in a more "conventional" manner by
shifting the decimal out the left by doubling it (similar to the way it's done
in the hex to decimal routine you just posted in the hex to decimal thread)
(which, incidently, is the double-dabble use of decimal mode I refered
to in another thread) and subtracting the BCD equivalent of the binary (in
BCD of course)

However it would introduce the problem of restoring (just as with a more
conventional shift and subtract division) so I don't know if it would end up
saving you anything.

But it might be something to investigate.
(and if you're really adventurous you could try doing a nonrestoring
version

)

BitWise · Post by **BitWise** » Thu Mar 04, 2004 7:15 am

I'd never heard of the BIN>BCD algorithm being called 'Double-Dabble' before. It might be a term that never made it across the pond. A quick troll of the internet turned up this:

Quote:

The Double-Dabble Method

We can use this method to convert base two numerals to base 10.

When we see a 1 we dabble: that is we double and add 1.

When we see a 0 we double: that is we double the number we have.

Try: 1 1 0 0 1 1 1 0 1

We start with the first 1. The next 1 means we dabble, so 1 x 2 + 1 = 3. Next we have a 0 so we double: 3 x 2 = 6. Again we have a 0, so we double: 2 x 6 = 12. Now we have a 1, so we dabble 2 x 12 + 1 = 25. Another 1, another dabble: 2 x 25 + 1 = 52. Another 1, another dabble: 2 x 52 + 1 = 105. Next we have a 0, so we double: 2 x 105 = 210. Lastly, we have a 1 so we dabble: 2 x 210 + 1 = 421.

GARTHWILSON · Post by **GARTHWILSON** » Thu Mar 04, 2004 8:09 am

Thankyou for the explanation, BitWise. 110011101B is 413, not 421, but the method does work. The only error was in doubling 25 and adding 1 and getting 52 instead of 51.

BitWise · Post by **BitWise** » Thu Mar 04, 2004 9:46 am

I copied the text from some a university lecture notes. Just goes to show the quality of education material these days.

bogax · Post by **bogax** » Thu Mar 04, 2004 6:12 pm

Gee whiz

Sorry guys.

Guess I should have explained.

I didn't realize the term "double dabble" was so obscure. It was, like, the first
thing they taught us after they explained binary. I just kind of assumed any
one who knew binary would be familiar with (the term) "double dabble"

Do I need to explain nonrestoring division?

kc5tja · Post by **kc5tja** » Fri Mar 05, 2004 1:24 am

bogax wrote:

Do I need to explain nonrestoring division?

I'm not sure if you're serious about this, or if you're being condescending. The term 'double dabble' is utterly unheard of where I live. I apologize, but, well, that's just the way it is.

As far as non-restoring division is concerned, to bring things back on topic, does this refer to division that doesn't require an error-corrective "add" at the end of the division loop? If not, then you might want to provide links to some information. It might prove educational to some here.

bogax · Post by **bogax** » Fri Mar 05, 2004 5:12 am

"
I'm not sure if you're serious about this, or if you're being condescending.
"

No, I didn't mean to be condescending. More like trying to get my bearings.
I would have thought that "double dabble" would be better known than
"nonrestoring division" but I don't (didn't) think of either of them as
particularly obscure.

For division by shifting and subtracting, you align the most significant bits
of the remainder (dividend) and the divisor by shifting the remainder
left and then you subtracting the divisor from it. If the result is negative you,
"restore" the remainder by adding the divisor back in and shifting again
and then do your subtraction. You keep the remainder positive and
reduce it towards zero

For nonrestoring you keep the negative remainder and continue to shift,
reducing it towards zero by adding the divisor if the remainder is negative
and subtracting the divisor if the remainder is positive. If the remainder is
negative when you're done with your shifting, you have to fix things up.

Having said that, I was half joking when I suggested nonrestoring in BCD.
I'm sure it can be done, and it would probably be an interesting exercise,
but I suspect and/or assume it would be more trouble than it would be
worth (how ever I don't know that)

I didn't find anything on line that looked very good but here's a couple links

http://cs.uns.edu.ar/~jechaiz/arquitect ... oring.html

http://www.computer-engineering.org/alg ... ision.html

"Programing the 6502" by Rodnay Zaks Has some code in it. I haven't
tryed it. (and I've heard that some of the code from that book is no good)
I'll dig it out and post it here.

GARTHWILSON · Post by **GARTHWILSON** » Fri Mar 05, 2004 7:21 am

Remember that the doubling and adding 1 in the double/dabble method must be done in the target base, which in this case is ten. You can't just do ASL to double, or INC to add 1. This makes the method take just a couple of bytes more memory and anywhere from 1.24 to 3.00 times as long to execute as what I posted at http://www.6502.org/source/integers/hex2dec.htm The speed of this one depends on how many zeroes and ones it finds, being faster at the zeroes. These speed comparison numbers are for converting a single-byte input, with a range of 00-FF.

My 6502 and 65816 division routines are at http://www.6502.org/source/integers/umm ... modfix.htm

Mats · Post by **Mats** » Sun Mar 07, 2004 3:29 pm

The reversal of Garth's algorithm is clearly:

Code: Select all

TABLE1     .BYTE  $01
           .BYTE  $02
           .BYTE  $04
           .BYTE  $08
           .BYTE  $16
           .BYTE  $32
           .BYTE  $64
           .BYTE  $28
TABLE2     .BYTE  $00
           .BYTE  $00
           .BYTE  $00
           .BYTE  $00
           .BYTE  $00
           .BYTE  $00
           .BYTE  $00
           .BYTE  $01
HTDR    SED
        STZ HTDR_OUT     ; Inititalize output word as 0.
        LDX #$07         ; X decrements from 7 to 0 for 8 bits
loop    SEC
        LDA HTDR_IN+1
        SBC TABLE1,X
        STA WORK
        LDA HTDR_IN
        SBC TABLE2,X
        BCC L
        STA HTDR_IN
        LDA WORK
        STA HTDR_IN+1
L       ROL HTDR_OUT
        DEX
        BPL loop
        CLD
        RTS

Just as simple and straightforward (and efficient) as the transformation in the other direction!

The idea in words:

The BCD representations of 1,2,4,8,16,32,64,128 are kept in the tables. When transforming to BCD the table entries corresponding to the individual bits are added together. When transforming from BCD to binary these entries are subtracted from the input value instead.

For comparison I would write Garth's algorithm as follows:

Code: Select all

TABLE1     .BYTE  $01
           .BYTE  $02
           .BYTE  $04
           .BYTE  $08
           .BYTE  $16
           .BYTE  $32
           .BYTE  $64
           .BYTE  $28
TABLE2     .BYTE  $00
           .BYTE  $00
           .BYTE  $00
           .BYTE  $00
           .BYTE  $00
           .BYTE  $00
           .BYTE  $00
           .BYTE  $01
HTD     SED             ; Output gets added up in decimal.
        STZ HTD_OUT     ; Inititalize output word as 0.
        STZ HTD_OUT+1   ; (NMOS 6502 will need LDA#0, STA ...)

        LDX #$07        ; X decrements from 7 to 0 for 8 bits
loop    ASL HTD_IN      ; Look at next high bit.  If it's 0,
        BCC htd1$       ; don't add anything to the output for this bit.
        LDA HTD_OUT     ; Otherwise get the running output sum
        CLC
        ADC TABLE1,X     ; and add the appropriate value for this bit
        STA HTD_OUT     ; from the table, and store the new sum.
        LDA HTD_OUT+1   ; After low byte, do high byte.
        ADC TABLE2,X
        STA HTD_OUT+1
htd1$   DEX             ; Go down to next bit value to loop again.
        BPL loop        ; If still not done, go back for another loop.
        CLD
        RTS