June 2003 massmind newsletter

SX Radix Routines

Introduction

This application note presents programming techniques for performing commonly found radix (base) conversions.

A solution commonly passed off on young engineers

If you go to school, they will tell you: "An efficient technique for binary-to-BCD conversion is that of the so called ADD-3 algorithm, and will convert the original binary number into three BCD digits (HUNDREDS, TENS, UNITS)." The algorithm can be expressed as follows:

1. Set HUNDREDS=0, TENS=0, UNITS=0, COUNT=8.

2. If any BCD digit is 5 or greater, add three to that digit.

3. Decrement COUNT and shift left. The bit shifted from the 8 bit binary is carried into UNITS, the bit shifted from UNITS is carried to TENS, etc.

4. If count not equal to 0, to step 2, else STOP.

Example:

Result 1111 1111₂ = FF₁₆ = 255₁₀

Thank goodness none of these routines do that.

Binary to BCD packed 8 bit to 2 digit

From: Ken Mathis

;Purpose: Convert an 8 bit number to BCD
;so value can be sent to a 7447 seven segment display driver
;I/O pin hungry, requires 8 bits to send data out.
;temp1 holds binary value
;BCD result in temp1
;$32 (50 decimal) becomes or %01010000
hex_to_bcd
	clr		temp0	;clear register
convert
	inc		temp0	;increment number of 10’s
	mov		w,#$0A	
	sub		temp1,w	;subtract 10 from temp1
	snc			;skip next instruction if underflow occurs
	jmp		convert	;repeat
	mov		w,#$A		
	add		temp1,w	;restore temp1. number of 1’s after restored
	dec		temp0	;correction to the number of 10’s
	swap		temp0	;swap upper and lower nibble of temp0
	add		temp1,temp0	;place number of 10’s in upper nibble of temp1
	ret				;temp1 now hold BCD value of $32

Binary to BCD half-packed 8 bit to 3 digit

From: Scott Dattalo, notes

Translated and optimized for the Ubicom SX by Nikolai Golovchenko

;********************************
;binary_to_bcd - 8-bits
;
;Input
;  bin  - 8-bit binary number
;       A1*16+A0
;Outputs
; hundreds - the hundreds digit of the BCD conversion
; tens_and_ones - the tens and ones digits of the BCD conversion
binary_to_bcd:

        clr     hundreds
        mov     W, <>bin                ;w  = A0*16+A1
        add     W, bin                  ;w  = A0+A1
        and     W, #00001111b           ;w  = A0+A1 % 16

        mov     tens_and_ones, W        ;tens_and_ones = A0+A1 % 16
        mov     W, #$16
        snb     DC                      ;if A0+A1 > 16
        add     tens_and_ones, W        ;  tens_and_ones  += 16
        mov     W, #$06
        snb     DC                      ;if tens_and_ones % 16 > 10
        add     tens_and_ones, W        ;  tens_and_ones  += 6

        add     tens_and_ones, W        ;tens_and_ones  += 6
        sb      DC                      ;if tens_and_ones < 10
        sub     tens_and_ones, W        ;  tens_and_ones  -= 6

        mov     W, #$16 - 1 + $6
        snb     bin.4
        add     tens_and_ones, W
        mov     W, #-$06
        sb      DC
        add     tens_and_ones, W
        mov     W, #$30
        snb     bin.5
        add     tens_and_ones, W

        mov     W, #$20
        snb     bin.7
        add     tens_and_ones, W

        mov     W, #$60
        snb     bin.6
        add     tens_and_ones, W

        add     tens_and_ones, W

        rl      hundreds
        sb      hundreds.0
        sub     tens_and_ones, W

        snb     bin.7
        inc     hundreds

Notes from Scott Dattalo on converting a Byte to BCD quickly:

[The routine I have implemented is] based on binary comparisons. It takes advantage of this little trick to quickly ascertain the ones' digit:

If you look at the ones' digit for 2^N you see this pattern:
         n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11 ...
  2^n % 10 = 1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8 ...
2^n in hex = 0, 2, 4, 8,10,20,40,80, ...

If it wasn't for the annoying 6's, you could simply sum the nibbles to get and get the ones' digit (after a relatively simple binary to BCD conversion). For example, the ones' digit for 2^5 = 0x20 is 2 (because 0x20 = 32 decimal). This sum-of-digits trick works even if the binary number is not a perfect power of 2.
For example, consider 0xef:

0xef = 239 base 10, the one's digit is '9'

0xe + 0xf = 0x1d

A binary to bcd conversion of 0x1d yields 0x29 (because 1d hex is 29 decimal). And the one's digit is '9', just like the one's digit of 0xef.

Now, this trick only works if bit 4 is not set. (notice my contrived example has every bit set except for that one). It's simple enough to test if bit 4, (and bit 8 for 16-bit conversions) and to subtract 1 and then add 6 (or simply add 5) if it is.

The second observation is that the sum of all of the tens' digits of 2^n (for n<8) is less than 16, and thus can fit into one nibble. This simplifies having to deal with overflow until after all of the digits have been added together. (What I'm saying is simply that if you look at the eight 2^n numbers 1,2,4,8,0x10,0x20,0x40,0x80 and sum all of the upper nibbles together: 0x10 + 0x20 + 0x40 + 0x80 you get 0xf0 which doesn't cause a carry.)

The third observation is that the BCD result is greater than 200 only if the most significant bit is set. Note, that this is necessary but not sufficient condition. e.g. 0x80 has the msb set, but is only 128, but 200 is 0xc8.

Binary to BCD unpacked 8 bit to 3 digits

From: @spam@wunnerful1TakeThisOuT at KILLspammsn.com

conv_high, mid and low contain the converted BCD components of a single $byte; the_val is the
input value containing the hexadecimal value to be converted.

#hundreds = #100
#tens	  =  #10
#ones	  =   #1


bcd_conv 
		clr	conv_low	zero out temp storage for new conversion
		clr	conv_mid
		clr	conv_high

hun
		stc			;set carry flag for test
		sub	the_val,#hundreds  ;subtract and check flag
		jnc	ten		; if =0, done with hundreds conversion
		inc	conv_high	;carry is set, so inc high bcd byte
		jmp	hun		;check again to see if over 200 in value

ten
		clc			;clear carry first (carryx)
		add	the_val,#hundreds ;need to correct for underrun first
ten_a		stc			;set carry flag for test
		sub	the_val,#tens	;subtract and check flag
		jnc	one		; if =0, done with tens conversion
		inc	conv_mid	;carry is set, so inc middle bcd byte
		jmp	ten_a		;check again to see if any more 10s value

one
		clc			;clear carry first (carryx)
		add	the_val,#tens	;correct for underrun but in tens now.
one_a		stc			;set carry flag for test
		sub	the_val,#ones	;subtract and check flag
		jnc	ascii_correct	;if =0, done with 1s conversion-prepare for ascii
		inc	conv_low	;carry is set, so inc low bcd byte
		jmp	one_a		;check again to see if any 1s left in value

ascii_correct
		clc			;adds $30 to each bcd digit for correct output to lcd
		add	conv_high,#$30	;now should display on lcd correctly
		clc			;since carryx, clear c
		add	conv_mid,#$30
		clc
		add	conv_low,#$30

		clc			;house cleaning clear the carry
		clz			;clear the zero flag

Binary to BCD unpacked 16 bit to 5 digit

From: John Payson via Scott Dattalo

[ed: quick guess at speed is that about 200 instructions will be executed and 50 instructions + 7 registers used]

;Takes hex number in NumH:NumL  Returns decimal in ;TenK:Thou:Hund:Tens:Ones
;written by John Payson

;input
;=A3*163 + A2*162 + A1*161 + A0*160
;=A3*4096 + A2*256 + A1*16 + A0
NumH    DS      1       ;A3*16+A2
NumL    DS      1       ;A1*16+A0
;output
;=B4*104 + B3*103 + B2*102 + B1*101 + B0*100
;=B4*10000 + B3*1000 + B2*100 + B1*10 + B0
TenK    DS      1       ;B4
Thou    DS      1       ;B3
Hund    DS      1       ;B2
Tens    DS      1       ;B1
Ones    DS      1       ;B0

        mov     W, <>NumH       ;w  = A2*16+A3
        or      W, #$F0         ;w  = A3-16
        mov     Thou, W         ;B3 = A3-16
        add     Thou, W         ;B3 = 2*(A3-16) = 2A3 - 32
        mov     Hund, W
        mov     W, #$E2
        add     Hund, W         ;B2 = A3-16 - 30 = A3-46
        mov     W, #$32
        add     W, Hund
        mov     Ones, W         ;B0 = A3-46 + 50 = A3+4

        mov     W, NumH         ;w  = A3*16+A2
        and     W, #$0F         ;w  = A2
        add     Hund, W         ;B2 = A3-46 + A2 = A3+A2-46
        add     Hund, W         ;B2 = A3+A2-46  + A2 = A3+2A2-46
        add     Ones, W         ;B0 = A3+4 + A2 = A3+A2+4

        mov     Tens, W
        mov     W, #$E9
        add     Tens, W         ;B1 = A2-23
        mov     W, Tens
        add     Tens, W         ;B1 = 2*(A2-23)
        add     Tens, W         ;B1 = 3*(A2-23) = 3A2-69 (Doh! thanks NG)

        mov     W, <>NumL       ;w  = A0*16+A1
        and     W, #$0F         ;w  = A1
        add     Tens, W         ;B1 = 3A2-69 + A1 = 3A2+A1-69 range -69...-9
        add     Ones, W         ;B0 = A3+A2+4 + A1 = A3+A2+A1+4 and Carry = 0 (thanks NG)

        rl      Tens            ;B1 = 2*(3A2+A1-69) + C = 6A2+2A1-138 and Carry is now 1 as tens register had to be negative
        rl      Ones            ;B0 = 2*(A3+A2+A1+4) + C = 2A3+2A2+2A1+9 (+9 not +8 due to the carry from prev line, Thanks NG)
        not     Ones            ;B0 = ~(2A3+2A2+2A1+9) = -2A3-2A2-2A1-10 (ones complement plus 1 is twos complement. Thanks SD)
;;Nikolai Golovchenko [golovchenko at MAIL.RU] says: complement [not Ones] can be regarded like:
;;      not     Ones
;;      inc     Ones
;;      dec     Ones
;;First two instructions make up negation. So,
;;Ones  = -Ones - 1
;;      = - 2 * (A3 + A2 + A1) - 9 - 1
;;      = - 2 * (A3 + A2 + A1) - 10
        rl      Ones            ;B0 = 2*(-2A3-2A2-2A1-10) = -4A3-4A2-4A1-20

        mov     W, NumL         ;w  = A1*16+A0
        and     W, #$0F         ;w  = A0
        add     Ones, W         ;B0 = -4A3-4A2-4A1-20 + A0 = A0-4(A3+A2+A1)-20 range -215...-5 Carry=0
        rl      Thou            ;B3 = 2*(2A3 - 32) = 4A3 - 64

        mov     W, #$07         ;w  = 7
        mov     TenK, W         ;B4 = 7

;B0 = A0-4(A3+A2+A1)-20,  -5...-200
;B1 = 6A2+2A1-138,       -18...-138
;B2 = A3+2A2-46,         -1...-46
;B3 = 4A3-64,            -4...-64
;B4 = 7,                 7

; At this point, the original number is
; equal to TenK*10000+Thou*1000+Hund*100+Tens*10+Ones
; if those entities are regarded as two's compliment
; binary.  To be precise, all of them are negative
; except TenK.  Now the number needs to be normal-
; ized, but this can all be done with simple byte
; arithmetic.

        mov     W, #$0A         ;w  = 10
Lb1:                            ;do
        add     Ones, W         ; B0 += 10
        dec     Tens            ; B1 -= 1
        sb      3.0
        ;skip no carry
        jmp     Lb1             ; while B0 < 0
        ;jmp carry
Lb2:                            ;do
        add     Tens, W         ; B1 += 10
        dec     Hund            ; B2 -= 1
        sb      3.0
        jmp     Lb2             ; while B1 < 0
Lb3:                            ;do
        add     Hund, W         ; B2 += 10
        dec     Thou            ; B3 -= 1
        sb      3.0
        jmp     Lb3             ; while B2 < 0
Lb4:                            ;do
        add     Thou, W         ; B3 += 10
        dec     TenK            ; B4 -= 1
        sb      3.0
        jmp     Lb4             ; while B3 < 0

        ret

A few notes (stolen shamelessly from Scott Dattalos' website) on how this works: Please take a pre-emptive asprin before reading. <GRIN>

If you have a 4 digit hexadecimal number, it may be written as

N = a_3*16^3 + a_2*16^2 + a_1*16 + a_0

where a_i, i=0,1,2,3 are the four hexadecimal digits. If you 
wish to convert this to decimal, then you need to express N as

N = b_4*10^4 + b_3*10^3 + b_2*10^2 + b_1*10 + b_0

Where b_j, j=0,1,2,3,4 are the five decimal digits.
The reason there are 5 digits in the decimal representation
is because the maximum four digit hexadecimal number (0xffff)
requires 5 decimal digits (65535). Now the goal is to find
a set of equations that allow the b_j's to be expressed in
terms of the a_i's. There are infinitely many ways to do this.
Here are two of probably the simplest expressions.
  First, expand the 16^i's and then collect all coefficients
of the 10^j's:

N = a_3*4096 + a_2*256 + a_1*16 + a_0
  = a_3*4*10^3  + a_2*2*10^2 + (a_3*9 + a_2*5 + a_1)*10 +
    6*(a_3 + a_2 + a_1) + a_0


This gives us five equations:

b_0 = 6*(a_3 + a_2 + a_1) + a_0
b_1 = a_3*9 + a_2*5 + a_1
b_2 = 2*a_2
b_3 = 4*a_3
b_4 = 0

Which as John says, must be "normalized". Normalization in
this context means we need to reduce the b_j's such that
  0 <= b_j <= 9

In other words we need to find:

c_0 = b_0 mod 10

b_1 = (b_1 + (b_0 - c_0)/10)
c_1 =  b_1 mod 10

b_2 = (b_2 + (b_1 - c_1)/10) 
c_2 = b_2 mod 10

b_3 = (b_3 + (b_2 - c_2)/10)
c_3 = b_3 mod 10

c_4 = (b_4 + (b_3 - c_3)/10) mod 10
    = (b_2 - c_2)/10

Division by 10 can be done quite efficiently (as was shown
in another thread several months ago). However, it does require
a significant amount of code space compared to say repeated
subtractions. Unfortunately, there can be very many subtractions
that are required. For example, b_1 could be as large as 15*16,
or 240. 10 would have to be subtracted 24 times if you wish to
compute 240 mod 10. I presume John realized this inefficiency
and thus sought to express N so that repeated subtractions
could be used and that the total number of subtractions are
minimized. This leads to the next way that N can be expressed:

N = a_3*(4100 - 4) + a_2*(260 - 4) + a_1*(20-4) + a_0
  = 4*a_3*10^3 + (a_3 + 2*a_2)*10^2 + (6*a_2 + 2*a_1)*10 +
    a_0 - 4*(a_3 + a_2 + a_1)

This gives five new equations for the b_j's. 

b_0 = a_0 - 4*(a_3 + a_2 + a_1)
b_1 = 6*a_2 + 2*a_1
b_2 = a_3 + 2*a_2
b_3 = 4*a_3
b_4 = 0

However, these equations are still not conducive to the 
repeated subtraction algorithm, at least the way John has 
done it. In other words, it is possible to pre-condition 
each of the b_j's so that they are less than zero. Then 
the repeated subtractions can simultaneously perform the
"mod 10" and "/10" operations shown above. Consider the
equation b_0 for example, 

b_0 = a_0 - 4*(a_3 + a_2 + a_1)

Since each a_i must satisfy:  0 <= a_i <= 15, then b_0 
ranges:

 -60 <= b_0 <= 15

We can make b_0 negative by subtracting any number greater than
15. A logical choice is 20. This is because if we subtract 20
from b_0, we can add 2 to b_1 to keep the net result the same.
The reason we add "2" can be seen:

 b_1*10 + b_0 = b_1*10 + b_0 + 20 - 20
              = (b_1 + 2)*10 + b_0 - 20

Carrying this concept out for the rest of the b_i's we have.

b_0 = a_0 - 4*(a_3 + a_2 + a_1) - 20
b_1 = 6*a_2 + 2*a_1 + 2 - 140
    = 6*a_2 + 2*a_1 - 138
b_2 = a_3 + 2*a_2 + 14 - 60
    = a_3 + 2*a_2 - 46
b_3 = 4*a_3 + 6 - 70
    = 4*a_3 - 64
b_4 = 0 + 7
    = 7

And if you look at John's code closely, you will see this is
how he has expressed the b_j's.

Summary

As you can see, there are many ways to "skin the cat" and most of the time someone else has taken the time and has the education to find the better way. Learning from others is a "good thing" and a wonderful way to justify higher education; especially math.

Challenge

Here are some tables of decimal and binary "hotspots." Can you see a pattern?

Code:

  .