BCD math routines instead of using division and modulo (using MSP430F427 MCU)

Question

I am using MSP430F427 MCU, I have this code below to extract, ones digit (d5), tens digit (d4), and hundreds digit (d3). I am expecting a 4-digit value, like 1000+, but have to display only 3-digit (hundreds, tens, ones). i.e count = 1783, I have to display only the 783. The code below works already.

However, during compilation there is a warning to get rid of division and modulo operation when doing this as this is power intensive. (Description Resource Path Location (ULP 5.1) Detected modulo operation(s). Recommend moving them to RAM during run time or not using as these are processing/power intensive)

void updateDisplay(signed long counter_value) {

    if (count<0)
    {
        NEG_ON;
    }

    else
    {
        NEG_OFF;
    }

    D3_NULL;
    D4_NULL;
    D5_NULL;

    // Ensure that counter_value is positive or zero for further processing
    counter_value = abs(counter_value);

    // Display the appropriate digit on the LCD based on the count value
    uint8_t d3= (counter_value/100)%10;
    uint8_t d4= (counter_value/10)%10;
    uint8_t d5= counter_value%10;

    if (d3 != 0)
    {
        switch (d3)
        {
            case 1: DIGIT3_DISP_1; break;
            case 2: DIGIT3_DISP_2; break;
            case 3: DIGIT3_DISP_3; break;
            case 4: DIGIT3_DISP_4; break;
            case 5: DIGIT3_DISP_5; break;
            case 6: DIGIT3_DISP_6; break;
            case 7: DIGIT3_DISP_7; break;
            case 8: DIGIT3_DISP_8; break;
            case 9: DIGIT3_DISP_9; break;
        }
    }
    else
    {
        DIGIT3_OFF;
    }

    if (d4 != 0 || d3 != 0)
    {
        switch (d4)
        {
            case 0: DIGIT4_DISP_0; break;
            case 1: DIGIT4_DISP_1; break;
            case 2: DIGIT4_DISP_2; break;
            case 3: DIGIT4_DISP_3; break;
            case 4: DIGIT4_DISP_4; break;
            case 5: DIGIT4_DISP_5; break;
            case 6: DIGIT4_DISP_6; break;
            case 7: DIGIT4_DISP_7; break;
            case 8: DIGIT4_DISP_8; break;
            case 9: DIGIT4_DISP_9; break;
        }
    }

    else if (d3 != 0)
    {
        DIGIT4_DISP_0;
    }

    switch (d5)
    {
        case 0: DIGIT5_DISP_0; break;
        case 1: DIGIT5_DISP_1; break;
        case 2: DIGIT5_DISP_2; break;
        case 3: DIGIT5_DISP_3; break;
        case 4: DIGIT5_DISP_4; break;
        case 5: DIGIT5_DISP_5; break;
        case 6: DIGIT5_DISP_6; break;
        case 7: DIGIT5_DISP_7; break;
        case 8: DIGIT5_DISP_8; break;
        case 9: DIGIT5_DISP_9; break;
    }
}

I want to learn how to save a single digit to a variable. i.e count 674 so d3 = 6, d4 = 7, and d5 = 4. This is what I think I should do. However, I am a bit sluggish in implementing bit shifting and bitwise operation to change the code. Any help would be appreciated.

Answer 1

Given:

unsigned divu10( unsigned n) 
{
    unsigned q, r;
    q = (n >> 1) + (n >> 2);
    q = q + (q >> 4);
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;
    r = n - (((q << 2) + q) << 1);
    return q + (r > 9);
}

(From Divide by 10 using bit shifts?)

And noting that MSP430 also lacks a hardware multiplier so also:

unsigned mulu10( unsigned multiplicand )
{
    return (multiplicand << 3) + (multiplicand  << 1) ;
}

then:

uint8_t* toBCD( unsigned value, uint8_t* bcd, size_t digits )
{
    for( size_t i = digits - 1; 
         i >= 0 && value != 0; 
         i-- )
    {
        unsigned a = divu10( value ) ;
        bcd[i] = value - mulu10( a ) ;
        value = a ;
    }

    return bcd ;
}

You can get the least significant three digits on a value in BCD as follows:

uint8_t bcd[3] ;
toBCD( abs(counter_value), bcd, sizeof(bcd) ) ;

Then (if you really must):

uint8_t d3= bcd[0] ;
uint8_t d4= bcd[1] ;
uint8_t d5= bcd[2] ;

But that really has no particular benefit over simply using the bcd digits directly e.g.:

switch( bcd[0] )
    ...

Whether that is truly more power efficient that using % and / operators would require testing. The operators are generalised whereas these functions are specialised for multiply/divide by 10, so likely to generate less code even without resorting to assembly. I would expect a reasonable compiler to generate near optimal code for such simple operations.

Answer 2

I've attempted to make use of the fact that 0 <= n < 10,000 but using 16 bit arithmetic which I believe your processor performs. Hopefully it will generate more efficient machine instructions than using longs or even ints. I've borrowed Clifford's divu10 function, but one of the lines can be omitted saving a few operations on each division.

uint16_t counter_value16 = abs(counter_value);
uint16_t temp = divu10(counter_value16);
uint8_t d5 = counter_value16 - (temp << 1) - (temp << 3);
uint16_t temp2 = divu10(temp);
uint8_t d4 = temp - (temp2 << 1) - (temp2 << 3);
temp = divu10(temp2);
uint8_t d3 = temp2 - (temp << 1) - (temp << 3);

where the following line can safely be commented out.

uint16_t divu10(uint16_t n) 
{
    uint16_t q, r;
    q = (n >> 1) + (n >> 2);
    q = q + (q >> 4);
    q = q + (q >> 8);
    //q = q + (q >> 16);
    q = q >> 3;
    r = n - (((q << 2) + q) << 1);
    return q + (r > 9);
}

I posted a 'double dabble' function earlier which you can see in the edit history but its performance is terrible, which was surprising as I thought that algorithm was often used for BCD. Maybe that was the algorithm you were thinking of when you asked the question, but I wouldn't bother with it.

Answer 3

Here's an implementation of "Double Dabble" binary to BCD for 16 bit unsigned integers. It's composed of a number of mask and shift operations with easy stuff like adding two values. No need to "divide by 10, multiply by 10, then subtract" to isolate each decimal digit.

SO, it seems, IS a free code writing service sometimes...

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

void toBCD( uint16_t val ) {
    const int decSize = 10; // big enough for "65535"
    char decDgt[ decSize ] = { 0 }; // decimal digits as binary 'nibbles'.
    int curPow10 = 0;

    for( uint16_t bit = 0x8000; bit; bit >>= 1 ) {

        for( int ii = curPow10; ii >= 0; ii-- ) {
            if( decDgt[ ii ] >= 5 ) // "dabble" algorithm step
                decDgt[ ii ] += 3;

            decDgt[ ii ] <<= 1; // "double" algorithm step

            if( decDgt[ ii ] & 0x10 ) { // Carry high bit?
                decDgt[ ii + 1 ] |= 0x1;
                if( ii == curPow10 ) // new power of 10?
                    curPow10++;
                decDgt[ ii ] &= 0xF; // dealing in 'nibbles'
            }
        }
        decDgt[ 0 ] |= ( ( val & bit ) != 0 ); // truth value 0 or 1
    }

    for( int ii = curPow10; ii >= 0; ii-- )
        putchar( decDgt[ ii ] + '0' );
    putchar( '\n' );
}

int main( void ) {
    toBCD( 0x000F );
    toBCD( 0x00FF );
    toBCD( 0x0100 );
    toBCD( 0x0401 );
    toBCD( 0x1000 );
    toBCD( 0xFFFF );

    return 0;
}

Output:

15
255
256
1025
4096
65535

Note: Base10 digits are accumulated in reverse order in the array (that is NOT null terminated.) Notice how they are retrieved and converted to ASCII digits. (This is a stripped down version of a version that handled Base2 values of as many bits/bytes as were desired.) Ignoring digits above "999" and prepending leading zeros, if required, is left as an exercise for the OP.