please dont rip this site

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:

 

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
        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: KILLspamwunnerful1 at ~NOSPAM~msn.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?

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 08:20, local time: 2024/12/22 23:46,
TOP NEW HELP FIND: 
18.117.254.202: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!

<A HREF="http://sxlist.com/Techref/new/letter/news0306.htm"> June 2003 SXList.com newsletter - SX radix routines</A>

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?

 

Welcome to sxlist.com!


Site supported by
sales, advertizing,
& kind contributors
just like you!

Please don't rip/copy
(here's why

Copies of the site on CD
are available at minimal cost.
 

Welcome to sxlist.com!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  .