Jump to content
Sign in to follow this  
RobG

Converting binary to decimal (BCD)

Recommended Posts

EDIT: the final versions of converter are here

Until now, I could get away with wasting clock cycles in my code.
My current project however requires from me writing efficient code and saving every possible clock cycle that I can.
I started to optimize my code with binary to decimal conversion piece.
My usual way of doing conversion, modulus + division, is the easiest but at the same time most clock cycle consuming method.
I found few suggestions on the net, like using C's div function, which returns structure with quotient and remainder eliminating the need for modulus operation.
Another way of converting I found is to use shifts and additions, much faster, but there is still room for improvement.

I figured to get better results, I will need to use some hardware feature, but the value line does not come with MPY module. There's one instruction that can help speed up decimal conversion, not available in C directly, but available through intrinsic function or asm. I decided to give it a try and the results are very positive.

I created 5 different functions to convert 10 bit(ADC's resolution) binary into an array of decimal numbers.
The range is 0-999 and there's no logic to handle overflow (10 bits range is 0-1023,) I didn't want to complicate this for testing purposes.

Here are the results (clock cycles) for the numbers 9, 99, and 999:

1. Modulus+divide ----- 346 - 657 - 973
2. C's div ------------ 293 - 575 - 886
3. Shift+add ---------- 248 - 274 - 327
4. S+a with my mods --- 139 - 233 - 234
5. My converter ------- 133 - 141 - 162
6. My conv with cond -- 98 -- 134 - 193


Shift and add becomes slow when binary > 9. It is also limited, adding 4th digit or increasing the number of binary bits would affect the performance. This is true for modulus+divide method as well, but updating it for higher bit number is pretty easy.

The thing about my converter is that it produces BCD integer which then is converted into an array. If you don't need an array, you can save another 41 cycles! Expanding it to 12 or 16 bits would have little effect on performance in comparison with other methods. Using conditionals speeds up conversion of small numbers by about 25%, but it slows down conversion of large numbers by about 20% (10 bit conversion.) And there is still room for improvement, it can be re-written in asm.

#include "msp430g2231.h"
#include 

void modAndDiv(unsigned int n);
void modAndDivAlt(unsigned int n);
void versionOfHackersDelight(unsigned int n);
unsigned int decimalAdd(unsigned int n);
unsigned int decimalAddAlt(unsigned int n);

unsigned char decimalResults[3] = {0,0,0};

void main(void) {
WDTCTL = WDTPW + WDTHOLD;

unsigned int result; //BCD

result = decimalAdd(999); //121
decimalResults[2] = result & 0x000F;//8
decimalResults[1] = (result & 0x00F0)>>4;//24
decimalResults[0] = (result & 0x0F00)>>8;//9
//total 162

result = decimalAdd(99);//100
decimalResults[2] = result & 0x000F;//8
decimalResults[1] = (result & 0x00F0)>>4;//24
decimalResults[0] = (result & 0x0F00)>>8;//9
//total 141

result = decimalAdd(9);//92
decimalResults[2] = result & 0x000F;//8
decimalResults[1] = (result & 0x00F0)>>4;//24
decimalResults[0] = (result & 0x0F00)>>8;//9
//total 133

result = decimalAddAlt(999); //152
decimalResults[2] = result & 0x000F;//8
decimalResults[1] = (result & 0x00F0)>>4;//24
decimalResults[0] = (result & 0x0F00)>>8;//9
//total 193

result = decimalAddAlt(99);//93
decimalResults[2] = result & 0x000F;//8
decimalResults[1] = (result & 0x00F0)>>4;//24
decimalResults[0] = (result & 0x0F00)>>8;//9
//total 134

result = decimalAddAlt(9);//57
decimalResults[2] = result & 0x000F;//8
decimalResults[1] = (result & 0x00F0)>>4;//24
decimalResults[0] = (result & 0x0F00)>>8;//9
//total 98

modAndDiv(999);
//total 973
modAndDiv(99);
//total 657
modAndDiv(9);
//total 346

modAndDivAlt(999);
//total 886
modAndDivAlt(99);
//total 575
modAndDivAlt(9);
//total 293

versionOfHackersDelight(999);
//total 234 (original 327)
versionOfHackersDelight(99);
//total 233 (original 274)
versionOfHackersDelight(9);
//total 139 (original 248)
}

unsigned int decimalAdd(unsigned int n) {
unsigned int result = 0;
result = _bcd_add_short(result, (n & 0x0007));
if(n & 0x0008)
result = _bcd_add_short(result, 0x0008);
if(n & 0x0010)
result = _bcd_add_short(result, 0x0016);
if(n & 0x0020)
result = _bcd_add_short(result, 0x0032);
if(n & 0x0040)
result = _bcd_add_short(result, 0x0064);
if(n & 0x0080)
result = _bcd_add_short(result, 0x0128);
if(n & 0x0100)
result = _bcd_add_short(result, 0x0256);
if(n & 0x0200)
result = _bcd_add_short(result, 0x0512);
return result;
}

void modAndDiv(unsigned int n) {
decimalResults[0] = 0;
decimalResults[1] = 0;
decimalResults[2] = 0;
unsigned char charIndex = 2;
while(n > 0) {
decimalResults[charIndex] = n % 10;
n /= 10;
charIndex--;
}
}

void modAndDivAlt(unsigned int n) {
decimalResults[0] = 0;
decimalResults[1] = 0;
decimalResults[2] = 0;
unsigned char charIndex = 2;
div_t d;
while(n > 0) {
d = div(n,10);
decimalResults[charIndex] = d.rem;
n= d.quot;
charIndex--;
}
}

void versionOfHackersDelight(unsigned int n) {
static const unsigned int rem[12] = {
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1
};
unsigned int q1, q2, q3, q, r;
decimalResults[0] = 0;
decimalResults[1] = 0;
decimalResults[2] = 0;

q1 = (n >> 1) + (n >> 2);
q1 += q1 >> 4;
q1 += q1 >> 8;
q2 = q1 >> 3;
r = n - ((q2 << 3) + q2 + q2); // originally r = n - q2 * 10;
q = q2 + (r > 9);
decimalResults[2] = rem[r];

if(n<10) // added this condition to exit when n<10, following calculations are just a waste
return;

q3 = (q >> 1) + (q >> 2);
q3 += q3 >> 4;
q3 = q3 >> 3;
r = q - ((q3 << 3) + q3 + q3); // originally r = q - q3 * 10;
decimalResults[0] = q3 + (r > 9);
decimalResults[1] = rem[r];
}

unsigned int decimalAddAlt(unsigned int n) {
unsigned int result = 0;
result = _bcd_add_short(result, (n & 0x0007));
if(n & 0x0008) {
result = _bcd_add_short(result, 0x0008);
if(n<16)
return result;
}
if(n & 0x0010) {
result = _bcd_add_short(result, 0x0016);
if(n<32)
return result;
}
if(n & 0x0020) {
result = _bcd_add_short(result, 0x0032);
if(n<64)
return result;
}
if(n & 0x0040) {
result = _bcd_add_short(result, 0x0064);
if(n<128)
return result;
}
if(n & 0x0080) {
result = _bcd_add_short(result, 0x0128);
if(n<256)
return result;
}
if(n & 0x0100) {
result = _bcd_add_short(result, 0x0256);
if(n<512)
return result;
}
if(n & 0x0200)
result = _bcd_add_short(result, 0x0512);

return result;
}



Here's the actual binary to BCD converter, both versions:

result = convertToBinary(binary);
result = convertToBinaryAlt(binary);
decimalResults[3] = result & 0x000F;
decimalResults[2] = (result & 0x00F0)>>4;
decimalResults[1] = (result & 0x0F00)>>8;
decimalResults[0] = (result & 0xF000)>>12;


unsigned int convertToBinary(unsigned int n) {
unsigned int result = 0;
result = _bcd_add_short(result, (n & 0x0007));
if(n & 0x0008)
result = _bcd_add_short(result, 0x0008);
if(n & 0x0010)
result = _bcd_add_short(result, 0x0016);
if(n & 0x0020)
result = _bcd_add_short(result, 0x0032);
if(n & 0x0040)
result = _bcd_add_short(result, 0x0064);
if(n & 0x0080)
result = _bcd_add_short(result, 0x0128);
if(n & 0x0100)
result = _bcd_add_short(result, 0x0256);
if(n & 0x0200)
result = _bcd_add_short(result, 0x0512);
return result;
}

//alternate version with conditionals
unsigned int convertToBinaryAlt(unsigned int n) {
unsigned int result = 0;
result = _bcd_add_short(result, (n & 0x0007));
if(n & 0x0008) {
result = _bcd_add_short(result, 0x0008);
if(n<16)
return result;
}
if(n & 0x0010) {
result = _bcd_add_short(result, 0x0016);
if(n<32)
return result;
}
if(n & 0x0020) {
result = _bcd_add_short(result, 0x0032);
if(n<64)
return result;
}
if(n & 0x0040) {
result = _bcd_add_short(result, 0x0064);
if(n<128)
return result;
}
if(n & 0x0080) {
result = _bcd_add_short(result, 0x0128);
if(n<256)
return result;
}
if(n & 0x0100) {
result = _bcd_add_short(result, 0x0256);
if(n<512)
return result;
}
if(n & 0x0200)
result = _bcd_add_short(result, 0x0512);

return result;
}

Share this post


Link to post
Share on other sites
;
; Convert 16 bit binary to 24 bit packed BCD
; C prototype: unsigned long bin2bcd(unsigned x)
;
       clr     R13
       clr     R14
       swpb    R12
       tst.b   R12
       jz      lsb
       swpb    R12
       rla     R12
       dadd    R14, R14
       rla     R12
       dadd    R14, R14
       rla     R12
       dadd    R14, R14
       rla     R12
       dadd    R14, R14
       rla     R12
       dadd    R14, R14
       rla     R12
       dadd    R14, R14
       rla     R12
       dadd    R14, R14
       rla     R12
       dadd    R14, R14
lsb
       rla     R12
       dadd    R14, R14
       rla     R12
       dadd    R14, R14
       rla     R12
       dadd    R14, R14
       rla     R12
       dadd    R14, R14
       rla     R12
       dadd    R14, R14
       rla     R12
       dadd    R14, R14
       dadd    R13, R13
       rla     R12
       dadd    R14, R14
       dadd    R13, R13
       rla     R12
       dadd    R14, R14
       dadd    R13, R13
       mov     R14, R12
       ret

Share this post


Link to post
Share on other sites

Test case and commented code for binary to packed BCD and binary to unpacked BCD

 

This could be tweaked for 3 or 4 digits if you really need maximum speed and compactness.

 

#include "msp430g2211.h"

unsigned long bin2pbcd(unsigned bin);  // Binary to packed BCD
void bin2bcd(unsigned bin, char * bcd); // Binary to unpacked BCD

int main(void)
{
   unsigned long pbcd;
   char bcd[5];

   WDTCTL = WDTPW + WDTHOLD;             // Stop watchdog timer

   pbcd = bin2pbcd(0);                 // 43 cycles
   pbcd = bin2pbcd(1);                 // 43 cycles
   pbcd = bin2pbcd(9);                 // 44 cycles
   pbcd = bin2pbcd(99);                // 44 cycles
   pbcd = bin2pbcd(999);               // 61 cycles
   pbcd = bin2pbcd(9999);              // 61 cycles    
   pbcd = bin2pbcd(65535);             // 60 cycles

   bin2bcd(0, bcd);                    // 77 cycles
   bin2bcd(1, bcd);                    // 77 cycles
   bin2bcd(9, bcd);                    // 78 cycles
   bin2bcd(99, bcd);                   // 78 cycles
   bin2bcd(999, bcd);                  // 95 cycles
   bin2bcd(9999, bcd);                 // 95 cycles
   bin2bcd(12345, bcd);                // 95 cycles
   bin2bcd(54321, bcd);                // 95 cycles
   bin2bcd(65535, bcd);                // 94 cycles
}

; bin2bcd.asm

          .cdecls C, LIST, "msp430g2211.h"  ; Include device header file

           .text
           .global bin2pbcd
           .global bin2bcd

;
; Convert 16 bit binary to 20 bit packed BCD
; C prototype: unsigned long bin2pbcd(unsigned bin)
;
bin2pbcd
       clr     R13                     ; Clear BCD result
       clr     R14                     ;
       swpb    R12                     ; Swap upper/lower byte
       tst.b   R12                     ; Check if upper byte is zero
       jz      lsb                     ; Yes, skip upper byte
       swpb    R12                     ; Sway upper/lower bytes back
       rla     R12                     ; Test msb of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       rla     R12                     ; Test bit 14 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       rla     R12                     ; Test bit 13 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       rla     R12                     ; Test bit 12 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       rla     R12                     ; Test bit 11 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       rla     R12                     ; Test bit 10 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       rla     R12                     ; Test bit 9 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       rla     R12                     ; Test bit 8 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
lsb
       rla     R12                     ; Test bit 7 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       rla     R12                     ; Test bit 6 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       rla     R12                     ; Test bit 5 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       rla     R12                     ; Test bit 4 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       rla     R12                     ; Test bit 3 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       rla     R12                     ; Test bit 2 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       dadd    R13, R13                ;
       rla     R12                     ; Test bit 1 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       dadd    R13, R13                ;
       rla     R12                     ; Test bit 0 of binary
       dadd    R14, R14                ; Multiply BCD by 2 and add binary bit
       dadd    R13, R13                ;
       mov     R14, R12                ; Move LSW in to proper register
       ret                             ; Return

; Convert 16 bit binary to 5 characters of BCD
; C prototype: void bin2bcd(unsigned bin, char * bcd)
;
bin2bcd
       mov     R13, R15                ; Save BCD pointer
       call    #bin2pbcd               ; Convert to packed BCD
       mov     R12, R14                ; Copy digits 2 -> 5
       and     #0x0F0F, R12            ; Mask digits 3 & 5
       mov.b   R12, 4(R15)             ; Move digit 5 to bcd[4]
       swpb    R12                     ; Swap digits 3 & 5
       mov.b   R12, 2(R15)             ; Move digit 3 to bcd[2]
       rra     R14                     ; Shift digits 2 & 4 to lower nibble
       rra     R14                     ;
       rra     R14                     ;
       rra     R14                     ;
       and     #0x0F0F, R14            ; Mask digits 2 & 4
       mov.b   R14, 3(R15)             ; Move digit 4 to bcd[3]
       swpb    R14                     ; Swap digits 2 & 4
       mov.b   R14, 1(R15)             ; Move digit 2 to bcd[1]
       mov.b   R13, 0(R15)             ; Move digit 1 to bcd[0]
       ret                             ; Return

Share this post


Link to post
Share on other sites

oPossum,

 

This is good stuff. Please keep it coming.

 

Is there a repository of assembly code snippets like this somewhere? You know, like the PIC code repository at PICLIST, but for MSP430?

 

Cheerful regards, Mike

Share this post


Link to post
Share on other sites
hmm.. the code vault was meant for that. This way you get support and code, both together.

 

The oldest post in "the code vault" seems to be from August 2010. Is that when TI came out with the MSP430?

Share this post


Link to post
Share on other sites

Now I am thinking I have approached this all wrong.

I wanted to stick with C and that's why I searched for C examples, and that's why I came up with my C routine.

Instead, I should have abandoned C all together or at least for the parts that are inefficient and use asm.

 

Quick search on Google and I found what I was looking for (I knew this was done already, just couldn't find it.)

 

slaa151

msp430x11x1_ca_07.s43

and many more, like thermometer code examples

 

;------------------------------------------------------------------------------
bin2bcd;     Subroutine for converting 16 bit binary to BCD
;              Input: R12 is 16 bit binary
;            Working: R15 is used and not saved
;             Output: R14|R13 5 digit BCD
;------------------------------------------------------------------------------
            mov #16,R15
            clr R14
            clr R13
L$1          rla R12
            dadd R13,R13
            dadd R14,R14
            dec R15
            jnz L$1
            ret

 

Since loops are used, this is not the most efficient code but it's not that bad, and it is very close in efficiency to my C routine.

That said, those who do not want to use asm, use my routine, it's the fastest I know of written in C.

 

@Mac and bluehash, the reason for this thread in Code Vault is just that, share the code :)

Share this post


Link to post
Share on other sites
... @Mac and bluehash, the reason for this thread in Code Vault is just that, share the code :)

 

The emphasis (in code vault) seems to be C and there's nothing here more than a year old. I'm looking for assembly language examples like the program listing you found which was dated February 2005. Thanks for posting, btw...

 

You should recognize oPossum's code as an "unrolled" and optimized version of the loop routine you posted. Just for fun, I rolled it back up into a loop to characterize a four digit (0..9999) version yesterday;

 

;
;  bin2bcd, 16 bit binary to 4 digit packed bcd (0..9999)
;
       clr.w   R14             ; 8 words, 83 cycles
       mov.w   #1, R13         ;                      (1)
xlp     rla.w   R12             ;                      (1)
       dadd.w  R14, R14        ;                      (1)
       rla.w   R13             ;                      (1)
       jnz     xlp             ;                      (2)
       mov.w   R14, R12        ; return pbcd in R12   (2)

 

Cheerful regards, Mike McLaren, K8LH

Share this post


Link to post
Share on other sites
hmm.. the code vault was meant for that. This way you get support and code, both together.

 

The oldest post in "the code vault" seems to be from August 2010. Is that when TI came out with the MSP430?

 

Yes. But TI came out with the MSP430 much earlier. 43oh was created when the Launchpad was released as there were alot of questions floating on the web unanswered.

The only places where you will find code for the MSP430 arch is the TI web site or here. The TI site is a very good repository of code, but strewed all across the site and do not come up in searches.

 

You are free to post anything interesting you find on the TI site, here.

Share this post


Link to post
Share on other sites
... @Mac and bluehash, the reason for this thread in Code Vault is just that, share the code :)

The emphasis (in code vault) seems to be C and there's nothing here more than a year old. I'm looking for assembly language examples like the program listing you found which was dated February 2005. Thanks for posting, btw...

Well, here's our chance to start one :)

Share this post


Link to post
Share on other sites

Yeah, I came across that one too, it's not only code but also hardware design gold mine. Didn't have time to process that one yet, 1000+ pages of good stuff, like converters, power meters, ADC, PWM, triacs, you name it.

I think the link to that document belongs in it's own post.

I guess some things are timeless.

Share this post


Link to post
Share on other sites

I noticed something interesting in that document.

 

The author keeps saying that the example circuit is for a MSP430C3xx series device.

 

I looked into that and discovered that their input voltage can range between 2.7 and 5.5 Volts.

 

Therefore, the example hardware circuits will need to change to adapt to the lower voltages of the newer devices.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×