# 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:

 HUNDREDS TENS UNITS BINARY 0000 0000 0000 1111 1111 Start 0000 0000 0001 1111 1110 Shift 1 0000 0000 0011 1111 1100 Shift 2 0000 0000 0111 1111 1000 Shift 3 0000 0000 1010 1111 0000 ADD-3 to UNITS 0000 0001 0101 1111 0000 Shift 4 0000 0001 1000 1111 0000 ADD-3 to UNITS 0000 0011 0001 1110 0000 Shift 5 0000 0110 0011 1100 0000 Shift 6 0000 1001 0011 1100 0000 ADD-3 to TENS 0001 0010 0111 1000 0000 Shift 7 0001 0010 1010 1000 0000 ADD-3 to UNITS 0010 0101 0101 0000 0000 Shift 8

Result 1111 11112 = FF16 = 25510

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
mov     W, #-\$06
sb      DC
mov     W, #\$30
snb     bin.5

mov     W, #\$20
snb     bin.7

mov     W, #\$60
snb     bin.6

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

```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
clc

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
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?

Decimal Binary
60000 001110101001100000
50000 001100001101010000
40000 001001110001000000
30000 111010100110000
20000 100111000100000
10000 010011100010000
9000 010001100101000
8000 001111101000000
7000 001101101011000
6000 001011101110000
5000 001001110001000
4000 111110100000
3000 101110111000
2000 011111010000
1000 001111101000
900 001110000100
800 001100100000
700 001010111100
600 001001011000
500 111110100
400 110010000
300 100101100
200 011001000
100 001100100
90 001011010
80 001010000
70 001000110
60 111100
50 110010
40 101000
30 011110
20 010100
10 001010
Decimal Binary
59999 001110101001011111
49999 001100001101001111
39999 001001110000111111
29999 111010100101111
19999 100111000011111
9999 010011100001111
8999 010001100100111
7999 001111100111111
6999 001101101010111
5999 001011101101111
4999 001001110000111
3999 111110011111
2999 101110110111
1999 011111001111
999 001111100111
899 001110000011
799 001100011111
699 001010111011
599 001001010111
499 111110011
399 110001111
299 100101011
199 011000111
99 001100011
89 001011001
79 001001111
69 001000101
59 111011
49 110001
39 100111
29 011101
19 010011
9 001001
Decimal Binary
60000 001110101001100000
59999 001110101001011111
50000 001100001101010000
49999 001100001101001111
40000 001001110001000000
39999 001001110000111111
30000 111010100110000
29999 111010100101111
20000 100111000100000
19999 100111000011111
10000 010011100010000
9999 010011100001111
9000 010001100101000
8999 010001100100111
8000 001111101000000
7999 001111100111111
7000 001101101011000
6999 001101101010111
6000 001011101110000
5999 001011101101111
5000 001001110001000
4999 001001110000111
4000 111110100000
3999 111110011111
3000 101110111000
2999 101110110111
2000 011111010000
1999 011111001111
1000 001111101000
999 001111100111
900 001110000100
899 001110000011
800 001100100000
799 001100011111
700 001010111100
699 001010111011
600 001001011000
599 001001010111
500 111110100
499 111110011
400 110010000
399 110001111
300 100101100
299 100101011
200 011001000
199 011000111
100 001100100
99 001100011
90 001011010
89 001011001
80 001010000
79 001001111
70 001000110
69 001000101
60 111100
59 111011
50 110010
49 110001
40 101000
39 100111
30 011110
29 011101
20 010100
19 010011
10 001010
9 001001

Code:

 file: /Techref/new/letter/news0306.htm, 33KB, , updated: 2006/2/27 09:20, local time: 2024/8/4 23:23, TOP NEW HELP FIND:  44.220.50.41:LOG IN

 ©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?Please DO link to this page! Digg it! / MAKE! June 2003 SXList.com newsletter - SX radix routines

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type a nice message (short messages are blocked as spam) in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.

Link? Put it here:
if you want a response, please enter your email address:
Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
 Did you find what you needed? "No. I'm looking for: " "No. Take me to the search page." "No. Take me to the top so I can drill down by catagory" "No. I'm willing to pay for help, please refer me to a qualified consultant"

 PICList 2024 contributors: o List host: MIT, Site host massmind.org, Top posters @none found - Page Editors: James Newton, David Cary, and YOU! * Roman Black of Black Robotics donates from sales of Linistep stepper controller kits. * Ashley Roll of Digital Nemesis donates from sales of RCL-1 RS232 to TTL converters. * Monthly Subscribers: Gregg Rew. on-going support is MOST appreciated! * Contributors: Richard Seriani, Sr.

.