### Author Topic: Routines to convert binary to BCD in C code  (Read 13695 times)

0 Members and 1 Guest are viewing this topic.

#### Picuino

• Frequent Contributor
• Posts: 995
• Country:
##### Routines to convert binary to BCD in C code
« on: March 27, 2024, 12:37:41 pm »
Binary to decimal BCD conversion routines have many applications. The first application I give them in new systems is to send by UART binary numbers to the computer in decimal format.
The code is written in C for Arduino, but is easily translatable to another environment.

16 bits binary to 5 digits BCD:

Code: (C) [Select]
#define BINARY_DIGITS   16#define DECIMAL_DIGITS  5void bin16_to_str(char *str, unsigned int bin) {   char maxdig, digcnt, bitcnt;   static char *p, carry;    // Clear string   p = str;   digcnt = DECIMAL_DIGITS + 1;   do { *p++ = 0; } while (--digcnt);    // Transform binary to BCD   bitcnt = BINARY_DIGITS;   maxdig = (DECIMAL_DIGITS - 1);   str += (DECIMAL_DIGITS - 1);   do {      // Shift left binary number with carry      carry = 0;      if (bin & (1L<<(BINARY_DIGITS-1)))         carry |= 1;      bin <<= 1;      // Shift left decimal number with carry      p = str;      digcnt = DECIMAL_DIGITS - maxdig;      do {         carry = (*p<<1) + carry;         if (carry >= 10) {            *p-- = carry - 10;            carry = 1;            if (digcnt == 1) {               maxdig--;               digcnt++;            }         }         else {            *p-- = carry;            carry = 0;         }      } while(--digcnt);   } while(--bitcnt);   // Transform BCD to ASCII   digcnt = DECIMAL_DIGITS;   do *str-- += '0'; while (--digcnt);}void setup() {   Serial.begin(9600);}void loop() {   unsigned long timeit;   unsigned long bin;   char strnum[DECIMAL_DIGITS + 1];   strnum[DECIMAL_DIGITS] = 0; // End of char   timeit = millis();   for(bin=10000; bin<11000; bin++) {      bin16_to_str(strnum, bin);   }   timeit = millis() - timeit;   Serial.print("1 conversion in ");   Serial.print(timeit);   Serial.println(" microseconds");   delay(5000);      for(bin=0; bin<50000; bin++) {      bin16_to_str(strnum, bin);      Serial.println(strnum);   }}
Output:
Code: [Select]
1 Conversion in 61 microseconds000000000100002000030000400005000060000700008000090001000011000120001300014000150001600017000180001900020000210002200023000240002500026000270002800029000300003100032000330003400035000360003700038000390004000041000420004300044000450004600047000480004900050000510005200053000540005500056000570005800059000600006100062000630006400065000660006700068000690007000071000720007300074000750007600077000780007900080000810008200083000840008500086000870008800089000900009100092000930009400095000960009700098000990010000101001020010300104001050010600107001080010900110001110011200113001140011500116001170011800119001200012100122001230012400125001260012700128001290013000131001320013300134001350013600137001380013900140
Size of flash memory (function bin16_to_str) = 2084 - 1916 = 168 Bytes

=======================================================

32 bits binary to 10 digits BCD:

Code: (C) [Select]
#define BINARY_DIGITS   32#define DECIMAL_DIGITS  10void bin32_to_str(char *str, unsigned long bin) {   char maxdig, digcnt, bitcnt;   static char *p, carry;    // Clear string   p = str;   digcnt = DECIMAL_DIGITS + 1;   do { *p++ = 0; } while (--digcnt);    // Transform binary to BCD   bitcnt = BINARY_DIGITS;   maxdig = (DECIMAL_DIGITS - 1);   str += (DECIMAL_DIGITS - 1);   do {      // Shift left binary number with carry      carry = 0;      if (bin & (1L<<(BINARY_DIGITS-1)))         carry |= 1;      bin <<= 1;      // Shift left decimal number with carry      p = str;      digcnt = DECIMAL_DIGITS - maxdig;      do {         carry = (*p<<1) + carry;         if (carry >= 10) {            *p-- = carry - 10;            carry = 1;            if (digcnt == 1) {               maxdig--;               digcnt++;            }         }         else {            *p-- = carry;            carry = 0;         }      } while(--digcnt);   } while(--bitcnt);   // Transform BCD to ASCII   digcnt = DECIMAL_DIGITS;   do *str-- += '0'; while (--digcnt);}void setup() {   Serial.begin(9600);}void loop() {   unsigned long timeit;   unsigned long bin;   char strnum[DECIMAL_DIGITS + 1];   strnum[DECIMAL_DIGITS] = 0; // End of char   timeit = millis();   for(bin=0x80000000; bin<0x80000000+1000; bin++) {      bin32_to_str(strnum, bin);   }   timeit = millis() - timeit;   Serial.print("1 Conversion in ");   Serial.print(timeit);   Serial.println(" microseconds");   delay(5000);      for(bin=0; bin<100000; bin++) {      bin32_to_str(strnum, bin);      Serial.println(strnum);   }}
Output:
Code: [Select]
1 Conversion in 234 microseconds00000000000000000001000000000200000000030000000004000000000500000000060000000007000000000800000000090000000010000000001100000000120000000013000000001400000000150000000016000000001700000000180000000019000000002000000000210000000022000000002300000000240000000025000000002600000000270000000028000000002900000000300000000031000000003200000000330000000034000000003500000000360000000037000000003800000000390000000040000000004100000000420000000043000000004400000000450000000046000000004700000000480000000049000000005000000000510000000052000000005300000000540000000055
Size of flash memory (function bin32_to_str)= 2154 - 1926 = 228 Bytes
« Last Edit: March 27, 2024, 07:46:18 pm by Picuino »

#### Picuino

• Frequent Contributor
• Posts: 995
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #1 on: March 27, 2024, 01:02:09 pm »
8 bits binary to 3 digits BCD:

Code: [Select]
#define BINARY_DIGITS   8#define DECIMAL_DIGITS  3void bin8_to_str(char *str, unsigned char bin) {   char maxdig, digcnt, bitcnt;   static char *p, carry;    // Clear string   p = str;   digcnt = DECIMAL_DIGITS + 1;   do { *p++ = 0; } while (--digcnt);    // Transform binary to BCD   bitcnt = BINARY_DIGITS;   maxdig = (DECIMAL_DIGITS - 1);   str += (DECIMAL_DIGITS - 1);   do {      // Shift left binary number with carry      carry = 0;      if (bin & (1L<<(BINARY_DIGITS-1)))         carry |= 1;      bin <<= 1;      // Shift left decimal number with carry      p = str;      digcnt = DECIMAL_DIGITS - maxdig;      do {         carry = (*p<<1) + carry;         if (carry >= 10) {            *p-- = carry - 10;            carry = 1;            if (digcnt == 1) {               maxdig--;               digcnt++;            }         }         else {            *p-- = carry;            carry = 0;         }      } while(--digcnt);   } while(--bitcnt);   // Transform BCD to ASCII   digcnt = DECIMAL_DIGITS;   do *str-- += '0'; while (--digcnt);}void setup() {   Serial.begin(9600);}void loop() {   unsigned long timeit;   unsigned char bin;   char strnum[DECIMAL_DIGITS + 1];   strnum[DECIMAL_DIGITS] = 0; // End of char   timeit = millis();   for(bin=0; bin<255; bin++) {      bin8_to_str(strnum, bin);   }   timeit = millis() - timeit;   Serial.print("1 conversion in ");   Serial.print(timeit/2.55);   Serial.println(" microseconds");   delay(5000);      for(bin=0; bin<255; bin++) {      bin8_to_str(strnum, bin);      Serial.println(strnum);   }}

Code: [Select]
1 conversion in 2.75 microseconds000001002003004005006007008009010011012013014015016017018019020021022023024025026027028029030031032033034035036037038039040041042043044045046047048049050051052053054055056057058059060061062063064065066067068069070071072073074075076077078079080081082083084085086087088089090091092093094095096097098099100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254

#### tridac

• Regular Contributor
• Posts: 115
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #2 on: March 27, 2024, 03:05:19 pm »
This is one of my standrd library functions. Edit as required...

/* Convert Binary to Bcd, Msd First */
/* -------------------------------- */
void vBin2Bcd (U32 u32Value, U8 *pu8BcdArray, U8 u8Count) {         /* BcdArray has msd at array[0] on return */

U8 u8Index;

if (u32Value > 0) {
for (u8Index = 1; u8Index <= u8Count; u8Index++) {
pu8BcdArray [u8Count - u8Index] = (U8) (u32Value % 10);       /* Buffer remainder */
u32Value /= 10;                                               /* Next decade */
}
}

else {                                                              /* Don't convert zero */
for (u8Index = 0; u8Index < u8Count; u8Index++) {
pu8BcdArray [u8Index] = 0;                                    /* Clear output */
}
}

A printing version:

/* Convert and Display 32 Bit Value as Decimal */
/* ------------------------------------------- */
void vPutDecimal (U32 u32Value) {

U8 u8Count = BUF_SIZE - 1;

u8Buffer [u8Count--] = 0x00;                                            /* Terminate string */

do {                                                                    /* First, split number into individual digits */
u8Buffer [u8Count--] = (U8) ((u32Value % 10) + 0x30);                /* Get remainder, asciify & buffer */
} while ((u32Value /= 10) > 0 && u8Count > 0);                       /* Next decade, trap buffer overflow */

u8Count++;                                                              /* Correct count */
vPutString (&u8Buffer [u8Count]);                                       /* Display, left justified */
}
« Last Edit: March 27, 2024, 03:49:08 pm by tridac »
Test gear restoration, hardware and software projects...

#### Picuino

• Frequent Contributor
• Posts: 995
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #3 on: March 27, 2024, 03:30:24 pm »
This is one of my standrd library functions. Edit as required...

/* Convert Binary to Bcd, Msd First */
/* -------------------------------- */
void vBin2Bcd (U32 u32Value, U8 *pu8BcdArray, U8 u8Count) {         /* BcdArray has msd at array[0] on return */

U8 u8Index;

if (u32Value > 0) {
for (u8Index = 1; u8Index <= u8Count; u8Index++) {
pu8BcdArray [u8Count - u8Index] = (U8) (u32Value % 10);       /* Buffer remainder */
u32Value /= 10;                                               /* Next decade */
}
}

else {                                                              /* Don't convert zero */
for (u8Index = 0; u8Index < u8Count; u8Index++) {
pu8BcdArray [u8Index] = 0;                                    /* Clear output */
}
}

Good and very short and simple routine.

My rutine, on the other hand, it does not make use of integer arithmetic ( value%10 and value /= 10) it only makes use of binary number shifts.
This means that it can generate shorter and faster assembly code, especially on small micros that do not have large ALUs nor FPUs.

#### Picuino

• Frequent Contributor
• Posts: 995
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #4 on: March 27, 2024, 03:41:37 pm »
My routine of 32 bits use at Arduino: 228 bytes of flash,  234us/conversion

Other routine of 32 bits use at Arduino: 156 bytes of flash,  380us/conversion

It seems that in the end the routine with divisions by 10 is shorter, despite the integer arithmetic required.

The following users thanked this post: tridac

#### tridac

• Regular Contributor
• Posts: 115
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #5 on: March 27, 2024, 04:03:04 pm »
Iirc, originally used that sort of idea in 6502 asm, but yes, like the old debate around integer divide and multiply, the old shift and add / subtract method can save a lot of memory, math lib inclusion etc. Modern micros are not so encumbered though, orders or magnitude faster, perhaps integer multiply and divide, and more flash space, so tend to think clarity rather than memory economy.
« Last Edit: March 27, 2024, 04:07:44 pm by tridac »
Test gear restoration, hardware and software projects...

• Super Contributor
• Posts: 3506
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #6 on: March 27, 2024, 05:31:33 pm »
Here is simple 32-bit binary to 8-digit BCD (32-bit) conversion:
Code: [Select]
uint32_t bin2bcd(uint32_t bin) {    uint32_t bcd = 0;    uint32_t factor = 1;    while (bin) {        bcd += (bin % 10) * factor;        bin /= 10;        factor <<= 4;    }    return bcd;}
just wonder how much memory it will consume on Arduino and what is execution time in comparison to previously posted code.

Does your microcontroller supports hardware multiplication and divide for integer?
« Last Edit: March 27, 2024, 05:42:25 pm by radiolistener »

#### Picuino

• Frequent Contributor
• Posts: 995
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #7 on: March 27, 2024, 07:37:52 pm »
32 bits binary to 10 digits BCD (with division value/10):
Code: [Select]
#define DECIMAL_DIGITS  10void bin32_to_str(char *bcdArray, unsigned long value) {  unsigned char index;  if (value > 0) {    for (index = 1; index <= DECIMAL_DIGITS; index++) {      bcdArray[DECIMAL_DIGITS - index] = ((unsigned char) (value % 10)) + '0';      value /= 10;    }  }  else {    for (index = 0; index < DECIMAL_DIGITS; index++) {      bcdArray[index] = '0';    }  }}void setup() {  Serial.begin(9600);}void loop() {  unsigned long timeit;  unsigned long bin;  char strnum[DECIMAL_DIGITS + 1];  strnum[DECIMAL_DIGITS] = 0; // End of char  timeit = millis();  for (bin = 0x80000000; bin < 0x80000000 + 1000; bin++) {    bin32_to_str(strnum, bin);  }  timeit = millis() - timeit;  Serial.print("1 Conversion in ");  Serial.print(timeit);  Serial.println(" microseconds");  delay(5000);  for (bin = 0; bin < 100000; bin++) {    bin32_to_str(strnum, bin);    Serial.println(strnum);  }}
Code: [Select]
1 Conversion in 386 microseconds0000000000000000000100000000020000000003000000000400000000050000000006000000000700000000080000000009000000001000000000110000000012000000001300000000140000000015000000001600000000170000000018000000001900000000200000000021000000002200000000230000000024000000002500000000260000000027000000002800000000290000000030000000003100000000320000000033000000003400000000350000000036000000003700000000380000000039000000004000000000410000000042000000004300000000440000000045000000004600000000470000000048000000004900000000500000000051000000005200000000530000000054000000005500000000560000000057000000005800000000590000000060000000006100000000620000000063000000006400000000650000000066000000006700000000680000000069000000007000000000710000000072000000007300000000740000000075000000007600000000770000000078000000007900000000800000000081000000008200000000830000000084000000008500000000860000000087000000008800000000890000000090000000009100000000920000000093000000009400000000950000000096000000009700000000980000000099000000010000000001010000000102000000010300000001040000000105000000010600000001070000000108000000010900000001100000000111000000011200000001130000000114000000011500000001160000000117000000011800000001190000000120000000012100000001220000000123000000012400000001250000000126000000012700000001280000000129000000013000000001310000000132000000013300000001340000000135000000013600000001370000000138000000013900000001400000000141000000014200000001430000000144000000014500000001460000000147000000014800000001490000000150000000015100000001520000000153000000015400000001550000000156000000015700000001580000000159000000016000000001610000000162000000016300000001640000000165000000016600000001670000000168000000016900000001700000000171000000017200000001730000000174
Total flash memory code (function bin32_to_str): 2092-1926 =  166 bytes
« Last Edit: March 27, 2024, 07:39:50 pm by Picuino »

#### Nominal Animal

• Super Contributor
• Posts: 6457
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #8 on: March 27, 2024, 07:41:37 pm »
For 8-bit microcontrollers like AVRs, I'd suggest repeated substraction instead.  For example,
Code: [Select]
// SPDX-License-Identifier: CC0-1.0#include <stdint.h>static const uint32_t  u32_dec[20] = {    UINT32_C(1),    UINT32_C(3),    UINT32_C(10),    UINT32_C(30),    UINT32_C(100),    UINT32_C(300),    UINT32_C(1000),    UINT32_C(3000),    UINT32_C(10000),    UINT32_C(30000),    UINT32_C(100000),    UINT32_C(300000),    UINT32_C(1000000),    UINT32_C(3000000),    UINT32_C(10000000),    UINT32_C(30000000),    UINT32_C(100000000),    UINT32_C(300000000),    UINT32_C(1000000000),    UINT32_C(3000000000),};// Little-endian byte order#define  BYTEINDEX(n, m)  (n)// Big-endian byte order// #define  BYTEINDEX(n, m)  ((m)-(n))// Little-endian byte orderstatic const uint8_t  u32_bcd[20][2] = {    { BYTEINDEX(0, 4), 0x01 },    { BYTEINDEX(0, 4), 0x03 },    { BYTEINDEX(0, 4), 0x10 },    { BYTEINDEX(0, 4), 0x30 },    { BYTEINDEX(1, 4), 0x01 },    { BYTEINDEX(1, 4), 0x03 },    { BYTEINDEX(1, 4), 0x10 },    { BYTEINDEX(1, 4), 0x30 },    { BYTEINDEX(2, 4), 0x01 },    { BYTEINDEX(2, 4), 0x03 },    { BYTEINDEX(2, 4), 0x10 },    { BYTEINDEX(2, 4), 0x30 },    { BYTEINDEX(3, 4), 0x01 },    { BYTEINDEX(3, 4), 0x03 },    { BYTEINDEX(3, 4), 0x10 },    { BYTEINDEX(3, 4), 0x30 },    { BYTEINDEX(4, 4), 0x01 },    { BYTEINDEX(4, 4), 0x03 },    { BYTEINDEX(4, 4), 0x10 },    { BYTEINDEX(4, 4), 0x30 },};void binary32_to_bcd(uint8_t dst[5], uint32_t src){    dst[0] = dst[1] = dst[2] = dst[3] = dst[4] = 0;    int8_t i = 20;    while (i-->0)        while (src >= u32_dec[i]) {            src -= u32_dec[i];            dst[u32_bcd[i][0]] += u32_bcd[i][1];        }}takes about 258 bytes of Flash on AVR (gcc-5.4.0 -O2 -mmcu=atmega32u4), with the slowest case being 2888888888, 38 iterations of the inner loop total.

If you don't mind increasing the slowest case to 3999999999, 85 iterations of the inner loop total, you can use
Code: [Select]
// SPDX-License-Identifier: CC0-1.0#include <stdint.h>static const uint32_t  u32_dec[10] = {    UINT32_C(1),    UINT32_C(10),    UINT32_C(100),    UINT32_C(1000),    UINT32_C(10000),    UINT32_C(100000),    UINT32_C(1000000),    UINT32_C(10000000),    UINT32_C(100000000),    UINT32_C(1000000000),};// Little-endian byte order#define  BYTEINDEX(n, m)  (n)// Big-endian byte order// #define  BYTEINDEX(n, m)  ((m)-(n))// Little-endian byte orderstatic const uint8_t  u32_bcd[10][2] = {    { BYTEINDEX(0, 4), 0x01 },    { BYTEINDEX(0, 4), 0x10 },    { BYTEINDEX(1, 4), 0x01 },    { BYTEINDEX(1, 4), 0x10 },    { BYTEINDEX(2, 4), 0x01 },    { BYTEINDEX(2, 4), 0x10 },    { BYTEINDEX(3, 4), 0x01 },    { BYTEINDEX(3, 4), 0x10 },    { BYTEINDEX(4, 4), 0x01 },    { BYTEINDEX(4, 4), 0x10 },};void binary32_to_bcd(uint8_t dst[5], uint32_t src){    dst[0] = dst[1] = dst[2] = dst[3] = dst[4] = 0;    int8_t i = sizeof u32_dec / sizeof u32_dec[0];    while (i-->0)        while (src >= u32_dec[i]) {            src -= u32_dec[i];            dst[u32_bcd[i][0]] += u32_bcd[i][1];        }}which compiles to 198 bytes of flash (gcc-5.4.0, -O2 -mmcu=atmega32u4).

#### cv007

• Frequent Contributor
• Posts: 835
##### Re: Routines to convert binary to BCD in C code
« Reply #9 on: March 27, 2024, 08:48:35 pm »
Quote
The first application I give them in new systems is to send by UART binary numbers to the computer in decimal format.
The first thing I get any new mcu to do is to use the pins, then use the uart via printf or similar. Once in place you are set for any kind of formatting you want, with no need to create bits and pieces of code that attempts to do the same. The size, once in place, remains the same so the cost is one time and 'free' to use after the first use so use it everywhere you can.

https://godbolt.org/z/cMffYMzf4
A little over 2k in size, of which printf is probably 3/4 of that. If my avr couldn't handle the extra 1.5k, I would move up to the next avr flash size. Having this is place is much more valuable than the loss of 1.5k (of which you replace with your bits/pieces of code anyway, so more like 1k).

I also have a C++ header for cout style printing, and the example above would be like so (and be about 500 bytes smaller in size)-
Code: [Select]
uart, '[', dec_(10,millis()), "] i: ", i++, endl; // using , instead of <<  and  dec_ is decimal with width of 10 and leading spacesa header with about 500 lines of code, but is basically 2 relatively simple functions that do the work (excluding floating point, which is another function)- format a number to something readable using already set formatting options and output a string, again using width/align options already in place (everything ends up in this).

Unless you like the challenge of fitting max code into a small mcu (like 2k), just get a printf in place and output whatever you desire and you can spend more time doing things like learning printf syntax.

#### SiliconWizard

• Super Contributor
• Posts: 14697
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #10 on: March 27, 2024, 11:34:07 pm »
Note that unless you have to deal with a lot of digits, on small targets, a very simple approach is often not just much simpler, but also actually faster.
You just need to count each digit by powers of ten. It's a very crude division algorithm, but for this purpose it works quite well. Nominal showed an improved version of that, but one that will take less flash (likely) is just to directly count in decimal.
If you just need a few digits, no need to get more complicated than this. You just need an array of the powers of 10 corresponding to the number of digits you need to deal with. It can even be unrolled if the number of digit is small. Say for 4 digits:

nDigit1000 = 0;
while (n >= 1000)
{
nDigit1000++;
n -= 1000;
}

nDigit100 = 0;
while (n >= 100)
{
nDigit100++;
n -= 100;
}

... and so on. If the number of digits is greater than this, or you want something more compact and easier to scale up, you can use arrays instead of this loop unrolling.
You can use Nominal's approach for something a bit more efficient.

But the direct decimal subtraction is often the simplest and fastest one on small targets that don't even have a hardware multiplier (or that have one that's pretty slow) with which optimizing compilers will usually implement the dvision by 10, if you go for the mod 10, divide by 10 approach. It may look more appropriate, but it rarely is on small embedded targets.

« Last Edit: March 28, 2024, 12:26:40 am by SiliconWizard »

#### Nominal Animal

• Super Contributor
• Posts: 6457
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #11 on: March 28, 2024, 06:54:11 am »
There are several threads on related interesting topics in the Programming child board; just browse the thread titles for a few dozen pages past.

#### rhodges

• Frequent Contributor
• Posts: 307
• Country:
• Available for embedded projects.
##### Re: Routines to convert binary to BCD in C code
« Reply #12 on: April 04, 2024, 02:48:41 am »
For every architecture, I write binary to BCD and ASCII in the native assember. After three decades, I don't find the idea too hard. My approach is to use or emulate the DAA. I recently posted my code on the thread called "comments".

I consider the divide a "no go" unless the CPU has a quick hardware divide. For example, the STM8 has a hardware divide that makes the conversion fast for small numbers. Otherwise, I suggest the shift and "DAA" method.
Currently developing STM8 and STM32. Past includes 6809, Z80, 8086, PIC, MIPS, PNX1302, and some 8748 and 6805. Check out my public code on github. https://github.com/unfrozen

#### T3sl4co1l

• Super Contributor
• Posts: 21874
• Country:
• Expert, Analog Electronics, PCB Layout, EMC
##### Re: Routines to convert binary to BCD in C code
« Reply #13 on: April 04, 2024, 05:04:36 am »
Have probably posted this before somewhere in the past, but as long as it's topical...

You can divide by multiplying by a reciprocal, assuming the reciprocal is known of course.  This even allows obtaining the remainder.

Something I wrote years ago:

Code: [Select]
;;     uDivTen;; Unsigned division by ten.  45 words, takes 60 cycles (plus rcall).;; Input:;   r17:r16 = operand; Output:;   r1:r0 = quotient;   r3:r2 = remainder;   (r16 = 10, r17 = 0);uDivTen: push r7 ; register usage: push r6 ; r7:r6 = operand (in[0..1]) push r5 ; r5:r4:r3:r2 = 40 bit accumulator, D[1..3] (byte 0 discarded) push r4 ; r1:r0 = partial products movw r6, r16 ; r16 = temp, r17 = zero clr r17 ; (but first, save operand) ; multiply by K = 2^20 * 16 / 10 to make D[0..3] = in[0..1] * K[0..2] ; (implicitly discarding D[0]) ldi r16, (((exp2(24) / 10) + 1) & (0x0000ff << 16)) >> 16 mul r7, r16 ; in[1] * K[2] movw r4, r0 ; save high word ldi r16, (((exp2(24) / 10) + 1) & (0x0000ff << 0)) >> 0 mul r7, r16 ; in[1] * K[0] movw r2, r0 ; save low word mul r6, r16 ; in[0] * K[0] add r2, r1 ; accumulate to D[1] (discard lowest byte) adc r3, r17 adc r4, r17 adc r5, r17 ldi r16, (((exp2(24) / 10) + 1) & (0x0000ff << 8)) >> 8 mul r6, r16 ; in[0] * K[1] add r2, r0 ; accumulate to D[1..2] adc r3, r1 adc r4, r17 adc r5, r17 mul r7, r16 ; in[1] * K[1] add r3, r0 ; accumulate to D[2..3] adc r4, r1 adc r5, r17 ldi r16, (((exp2(24) / 10) + 1) & (0x0000ff << 16)) >> 16 mul r6, r16 ; in[0] * K[2] add r3, r0 ; accumulate to D[2..3] adc r4, r1 adc r5, r17; dig remainder out of the fractional part ldi r16, 0x10 ; rounding bit add r3, r16 ldi r16, 10 mul r3, r16 ; frac * 10 mov r2, r1 clr r3 movw r0, r4 ; quotient out; r3 = 0, r2 = [0...9], r1:r0 = [0...6553] pop r4 pop r5 pop r6 pop r7 ret; END PROC uDivTen
Using an ad-hoc / non-standard ABI, but that's easily adapted by those in the know.  That "40 bit" accumulator in the middle seems intimidating, or over-the-top, but IIRC, one or two extra bits are required to complete the full result (including remainder) and making use of the register is most likely better than any bit twiddling hacks you might do otherwise.  (And, good luck getting the compiler to generate that..!)

I've never cared for BCD, and just do the x / 10, x % 10 loop to generate decimals.  You'd have to be running a lot of digits to need any kind of speed.  You're most likely doing it in the main() loop at a low refresh rate, for which any method will do -- my most recent codebases just let the C compiler figure it out, or use a library call such as itoa().  I haven't ran out of Flash or SRAM in a long time (...or ever?), not that I do very large projects, but still, a typical 64k AVR can hold a lot of crufty code no problem.

Tim
Seven Transistor Labs, LLC
Electronic design, from concept to prototype.
Bringing a project to life?  Send me a message!

#### bson

• Supporter
• Posts: 2295
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #14 on: April 08, 2024, 09:10:06 pm »
For ARM, shift-and-add/subtract is probably the most efficient since it can do both in a single instruction.

I have a small utility at https://github.com/bson/divfac which factors unsigned integer division by a constant into shift-and-add.  For example:

Code: [Select]
\$ divfac.py 10 div10template <typename T>static inline T div10(const T& val) {  return (val >> 3) - (val >> 5) + (val >> 7) - (val >> 9) + (val >> 11) - (val >> 13) + (val >> 15) - (val >> 17) + (val >> 19) - (val >> 21) + (val >> 23) - (val >> 25) + (val >> 27) - (val >> 29) + (val >> 31);}
Obviously it spits out C++ in a way to allow running it from makefiles to easily generate header files to be included for common divisors.

There's clearly a pattern here that would make it easy to manually extend to 64 bits, but personally I've never had a use for that.  For smaller T's like uint16_t, many of the terms are 0 and get eliminated during optimization.

With inline ARM assembly, a 32-bit divide-by-10 could look something like:

Code: [Select]
#include <stdint.h>static inline uint32_t div10(const uint32_t value) {    uint32_t result;    asm("lsr   %0, %1, #3\n\t"        "sub   %0, %1, lsr #5\n\t"        "add   %0, %1, lsr #7\n\t"        "sub   %0, %1, lsr #9\n\t"        "add   %0, %1, lsr #11\n\t"        "sub   %0, %1, lsr #13\n\t"        "add   %0, %1, lsr #15\n\t"        "sub   %0, %1, lsr #17\n\t"        "add   %0, %1, lsr #19\n\t"        "sub   %0, %1, lsr #21\n\t"        "add   %0, %1, lsr #23\n\t"        "sub   %0, %1, lsr #25\n\t"        "add   %0, %1, lsr #27\n\t"        "sub   %0, %1, lsr #29\n\t"        "add   %0, %1, lsr #31"        : "+r" (result)        : "r" (value));    return result;}
Of course, a 16-bit divide would be shorter since half the terms can be removed.
« Last Edit: April 08, 2024, 09:40:30 pm by bson »

#### Doctorandus_P

• Super Contributor
• Posts: 3483
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #15 on: April 16, 2024, 01:31:08 pm »
I would use ldiv( ) It does a division, and returns both the answer, and the remainer in a structure. You can also use a standard function such as itoa( ) (Integer to Ascii). Also studying the code in the standard libraries (from an Open Source compiler such as GCC) can be an excellent educational tool for leaning different types of algorithms used in programming.

Below a function I wrote years ago. Most of it is house keeping and ascii formatting (sings, dots, etc) to convert an integer into a  fixed point interpretated ascii string. The while loop in the middle does the actual conversion with ldiv( ). Do note it writes the result "backwards" to the destination string (array).

// String Print a number with Fixed width and precision (decimal point).
// Signed version.
char* SPrintFixed( char* Buf, int32_t n, int8_t length, int8_t Precision) {
char Sign, *pEnd = Buf + length;
ldiv_t   Number;

if( n < 0) {
n = -n;
Sign = '-';
}
else
Sign = ' ';

Buf[ length] = 0x00;
Number.quot = n;
do {
Number = ldiv( Number.quot, 10);
Buf[--length] = Number.rem + '0';
if( --Precision == 0)
Buf[--length] = '.';
}while( (length > 0) && ((Number.quot) || (Precision >= 0)) );

if( Sign == '-') {
if( length > 0) {
Buf[--length] = '-';
}
}

while( length > 0) {   // Fill remaining space with spaces.
Buf[--length] = ' ';
}
return pEnd;
}
« Last Edit: April 16, 2024, 01:40:36 pm by Doctorandus_P »

#### cv007

• Frequent Contributor
• Posts: 835
##### Re: Routines to convert binary to BCD in C code
« Reply #16 on: April 16, 2024, 06:06:59 pm »
Quote
I would use ldiv( )
You will be better off letting the compiler handle it. It can figure out when you are needing quotient/remainder and then call a divmod library function which is already optimized for the particular mcu. Forcing the use of ldiv when the compiler could have done something better (much better depending on mcu) means you are crippling the more capable mcu's.

So like most things, write code that is clear and easy to understand and let the compiler optimize, which it does quite well.

#### Doctorandus_P

• Super Contributor
• Posts: 3483
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #17 on: April 23, 2024, 02:46:29 am »
Do you mean with this that the compiler will optimize separate remeainer and division operations but not an ldiv?
And how do you know that ldiv is not optimized?

Saying this as a blanket statement  is not very trustworthy. Modern compilers do weird things to code during optimisation, and if performance really is that important you should do some benchmarking on the uC / compiler you use.

And as for readability, I'd say my posted code is very readable, but I'm biased of course.
At least ldiv is interesting enough to mention in this thread.

#### cv007

• Frequent Contributor
• Posts: 835
##### Re: Routines to convert binary to BCD in C code
« Reply #18 on: April 24, 2024, 07:18:22 pm »
Quote
Do you mean with this that the compiler will optimize separate remeainer and division operations but not an ldiv?
I mean compiler writers are not unaware of these things and may already generate optimal code given simple directions in the form of user code. In the case of an mcu with hardware division, letting the compiler decide means you will be letting the compiler use the hardware division instead of forcing a call to an ldiv library function, or some other user created division function, which will be much slower and therefore defeats the purpose of the extra effort to optimize on your own.

Simple example for an avr-
https://godbolt.org/z/TsvWeTof4
They both make a single call to __divmodhi4 and the compiler sees the need for both q/r in the 'normal' version even though the div/mod statements were separated by code. Writing straight forward code in this case results in (almost) exactly the same code.

A second example, but for a cortex-m
https://godbolt.org/z/GEbY8n1nn
In this case, the compiler for whatever reason needs the divisor in a global var before it will do only the single __aeabi_idivmod call, else will get an additional __aeabi_idiv call. Even if you do not know this quirk and end up with 2 division calls its not something to worry about- you will not notice any effects that your formatting code is not optimal. Once you move over to an M3 and above, the compiler will start using hardware division and you had to do nothing to get that, where the ldiv (or any custom code) user will still be using the slow library call as the compiler will be forced to use it. (You can change the command line option to cortex-m3,m4,m33,etc. and see what you get for both functions).

So as I suggested, spend your time getting the high level code to be both readable and reliable and let the compiler handle optimization. In the case of formatting, there is little need to worry about perfect optimization.
« Last Edit: April 24, 2024, 07:19:53 pm by cv007 »

#### Nominal Animal

• Super Contributor
• Posts: 6457
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #19 on: April 24, 2024, 08:42:59 pm »
At least ldiv is interesting enough to mention in this thread.
Absolutely!

Do you mean with this that the compiler will optimize separate remeainer and division operations but not an ldiv?
Considering the abstract machine model the C standard is based on, I'd say C compilers have more opportunities to optimize the integer-divide-and-modulo expressions compared to the div()/ldiv()/lldiv()/imaxdiv() function call.

If you use e.g. Compiler Explorer to examine the code generated at different optimization levels for different architectures from
Code: [Select]
typedef  unsigned int  uint;typedef struct {    uint           quotient;    unsigned char  remainder;} pair;pair div10(uint n) { return (pair){ .quotient = n / 10, .remainder = n % 10 }; }you'll see it varies depending on optimization options.

For example, for 8-bit AVR (ATmega32U4) using GCC 13.2.0 and -Os, it compiles to a simple __udivmodhi4 call.  With -O2, it is open-coded.  For 32-bit architectures using GCC and Clang and -O2, it typically compiles to a multiplication by 0xcccccccd ("0.1"); with -Os, to a division by 10 (wherever the instruction set has a 32-bit unsigned divide instruction).

This does not mean that /% produces better code, though; only that the compiler has more opportunities for optimization.

I do not believe in micro-optimizations, or optimizing specific functions.  Hot functions should get inlined, and there the opportunities for optimization tend to matter more.  It is not just the operation itself, you see, but everything else surrounding and supporting the computation operation.

The best illustration of a similar issue I know of, is Radix-sorting IEEE 754 double-precision floating point numbers (double).  When their byte order is the same as unsigned integers, one only needs a preprocessing pass of flipping all bits if the sign bit is set, or only the sign bit if it is not set, to make all finite values sort in the same order as the 64-bit unsigned integer representation (after the bit flipping).  Depending on the L1-cache/D-cache size, you do four to eight passes, plus the final unflipping-bits pass.  This scales linearly: as it is a radix sort, it indeed sorts the finite floating-point values in O(N) time complexity.  However, its cache footprint is horrible, evicting basically everything else from the L1/D-cache, so using it slows all other code running after the sort, because it ends up having to refill the cache.  Thus, you need to have hundreds of millions of numbers or more, before it ends up being faster/better than QuickSort and other O(N²) and O(N log N) time complexity (but typically fast) sorting algorithms.  And if the other stuff is cache-sensitive, maybe not even then; while the sort may be done faster, the other code needed to do the actual real-world task may take correspondingly longer time (due to the cache misses).  (Similarly, when multiplying a pair of dense matrices, you don't need very large matrices before it becomes worthwhile to copy the data so that they are both accessed in as compact order as possible, for maximum cache locality.)

#### T3sl4co1l

• Super Contributor
• Posts: 21874
• Country:
• Expert, Analog Electronics, PCB Layout, EMC
##### Re: Routines to convert binary to BCD in C code
« Reply #20 on: April 25, 2024, 04:58:19 am »
The best illustration of a similar issue I know of, is Radix-sorting IEEE 754 double-precision floating point numbers (double).  When their byte order is the same as unsigned integers, one only needs a preprocessing pass of flipping all bits if the sign bit is set, or only the sign bit if it is not set, to make all finite values sort in the same order as the 64-bit unsigned integer representation (after the bit flipping).  Depending on the L1-cache/D-cache size, you do four to eight passes, plus the final unflipping-bits pass.  This scales linearly: as it is a radix sort, it indeed sorts the finite floating-point values in O(N) time complexity.  However, its cache footprint is horrible, evicting basically everything else from the L1/D-cache, so using it slows all other code running after the sort, because it ends up having to refill the cache.  Thus, you need to have hundreds of millions of numbers or more, before it ends up being faster/better than QuickSort and other O(N²) and O(N log N) time complexity (but typically fast) sorting algorithms.  And if the other stuff is cache-sensitive, maybe not even then; while the sort may be done faster, the other code needed to do the actual real-world task may take correspondingly longer time (due to the cache misses).  (Similarly, when multiplying a pair of dense matrices, you don't need very large matrices before it becomes worthwhile to copy the data so that they are both accessed in as compact order as possible, for maximum cache locality.)

Related perspective shift: CPU time is essentially free these days, and often this is the case on more historic platforms too (most anything with slow RAM, caches, etc.).  Doing float comparisons might be relatively onerous in raw cycle count (depending on platform; they've certainly improved over the years), and the integer hack is so greedily tempting.  But if you're spending all your time fetching and storing, that... doesn't matter at all.

Tim
Seven Transistor Labs, LLC
Electronic design, from concept to prototype.
Bringing a project to life?  Send me a message!

The following users thanked this post: Nominal Animal

#### John Coloccia

• Super Contributor
• Posts: 1217
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #21 on: April 26, 2024, 01:00:38 am »
Depends on the processor. Some processors fall flat on their face with floating point calculations.

But yes, many cases of poor performance are due to IO bounds, not computation.

Is there an actual problem that's trying to be solved here?

#### Nominal Animal

• Super Contributor
• Posts: 6457
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #22 on: April 26, 2024, 02:15:52 am »
Is there an actual problem that's trying to be solved here?
Not really.  Binary to decimal conversion is considered "slow" and requiring "surprisingly much" machine-level code, compared to arithmetic operations, so these can be useful in some cases, but that's about it.

Library implementations, especially various printf() implementations, are written for correctness and not for efficiency, so when you work with smaller microcontrollers, especially 8-bit ones (AVRs, PICs, 8051s), a custom implementation can be useful.  More annoyingly, most standard library functions use arbitrary precision arithmetic and dynamic memory allocation during conversion of floating-point numbers.

Even on fully hosted C environments, it turns out that if you read numeric data from text files, the standard C library string-to-number conversions (strtod(), strtol(), scanf() and their variants) become the bottleneck, when you have enough (megabytes) of data.  Then, too, "optimized" conversion functions can reduce the load times to a fraction of what they would be using standard C conversion functions.

#### SiliconWizard

• Super Contributor
• Posts: 14697
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #23 on: April 26, 2024, 03:39:04 am »
Is there an actual problem that's trying to be solved here?
Not really.  Binary to decimal conversion is considered "slow" and requiring "surprisingly much" machine-level code, compared to arithmetic operations, so these can be useful in some cases, but that's about it.

Library implementations, especially various printf() implementations, are written for correctness and not for efficiency, so when you work with smaller microcontrollers, especially 8-bit ones (AVRs, PICs, 8051s), a custom implementation can be useful.  More annoyingly, most standard library functions use arbitrary precision arithmetic and dynamic memory allocation during conversion of floating-point numbers.

Even on fully hosted C environments, it turns out that if you read numeric data from text files, the standard C library string-to-number conversions (strtod(), strtol(), scanf() and their variants) become the bottleneck, when you have enough (megabytes) of data.  Then, too, "optimized" conversion functions can reduce the load times to a fraction of what they would be using standard C conversion functions.

Yep. scanf() being the absolute dog of them all.

And sometimes the "simplest" solution is actually also the most efficient. As I said before, the simple approach to count powers of ten, requiring "only" up to 9 iterations per digit with just a subtraction and an increment per iteration, will be faster on most targets that do not have a hardware multiplier (with which most optimizing compiler will implement the divide by 10), or on which the hardware multiplier is a multi-cycle operation. In particular, I've used the solution I mentioned earlier on AVR targets and it led to a lot smaller code size, and much faster too. Don't let the fact that it looks too "naive" deter you - looking at the generated assembly if in doubt will help picking the most efficient approach, in simple cases like this.

#### Picuino

• Frequent Contributor
• Posts: 995
• Country:
##### Re: Routines to convert binary to BCD in C code
« Reply #24 on: April 26, 2024, 11:49:49 am »
Performing the binary-to-decimal conversion with custom routines has helped me to be able to dump huge numbers (48 bits long) from the counter of an 8-bit microcontroller that counted 10MHz pulses for long periods of time and dumped the count by UART every second.

Smf