This application note presents programming techniques for performing commonly found radix (base) conversions.
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.
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 10s 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 1s after restored dec temp0 ;correction to the number of 10s swap temp0 ;swap upper and lower nibble of temp0 add temp1,temp0 ;place number of 10s 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 = 0x1dA 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.
From: KILLspamwunnerful1-Remove- at 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
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.
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.
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/10/7 17:28,
98.80.143.34:LOG IN ©2024 PLEASE DON'T RIP! THIS SITE CLOSES OCT 28, 2024 SO LONG AND THANKS FOR ALL THE FISH!
|
©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? <A HREF="http://www.massmind.org/techref/new/letter/news0306.htm"> June 2003 SXList.com newsletter - SX radix routines</A> |
Did you find what you needed? |
Welcome to massmind.org! |
Welcome to www.massmind.org! |
.