How to convert 38bit Byte Array to ASCII Decimal

I am writing a routine and an AVR ATMEGA88 to read FDX RFID tags using the TI TM3705A chip and transmit that over UART to another processor. This chip uses 15625 baud while the other processor will receive the data at 19200 baud.

The idea is to read the incoming data (38 bits of ID number - e.g. 00 11 E3 D6 7C), CRC check it and then output it as a friendly 12 digit decimal number (000300144252) that represents the unique ID of the tag.

So far I have this 38 bit number in an array:

The actual number I'm interested in sits in elements 2:6. The 2 MSB's of no. 6 should be ignored because they are the start of the next block of data.

i   Dec Hex Bin
0   80  50  01010000
1   126 7E  01111110
2   124 7C  01111100
3   214 D6  11010110
4   227 E3  11100011
5   17  11  00010001
6   192 C0  11000000
7   237 ED  11101101
8   0   00  00000000
9   128 80  10000000
10  97  61  01100001
11  103 67  01100111
12  126 7E  01111110
13  0   00  00000000
14  0   00  00000000

I'm looking for an efficient way to output the bytes in the array as decimal "000300144252".

I've tried packing it into a long long type and then use sprintf %d but it seems to choke on temp = data << 32 for example. I don't know if sprintf will even handle that size number yet. I'll admit I've gotten really spoiled with C# and other lazy languages for this kind of stuff :)

Is there a way to convert to decimal "as you go" - in other words, read from the most significant dig开发者_开发百科it (6) and output the decimal ASCII digits on the UART, then 5,4,3,2 without large intermediate buffers and the like? Memory is a little constrained on these chips.

Conversion to decimal is computationally expensive -- whether you do it yourself or delegate it to a library function such as sprintf() does not change it. What makes it more complex here is that it is a relatively large value: 38 bits, that's bigger than 32 bits.

With sprintf(), use "%lld" to print a long long. If the compiler supports the long long type but sprintf() does not, then you can do it by hand:

static void
convert_to_decimal(char[] dst, unsigned long long src)
{
    int i;

    for (i = 0; i < 12; i ++) {
        dst[11 - i] = '0' + (int)(src % 10);
        src /= 10;
    }
    dst[12] = 0;
}

This function writes out the 12-char result in dst[] (with a terminating NUL). Note that this implies a division by 10, which the compiler will translate into the inclusion of a relatively complex function.

If your compiler does not support the long long type (or chokes on trying to make a division) then you will have to implement that operation yourself, which will require a bit of mathematical knowledge. Ultimately, this article may be useful -- or not.

After a lot of searching and trial and error, I found a solution.

I misinterpreted the error I was seeing and Thomas is right. The function was too big for the chip when added to my own functions.

The obvious choices didn't go anywhere, but I'll list them here to help other noobs when they hit this problem.

itoa() - 16 bit and ultoa() - 32 bit are implemented but too small.

sprintf(%d) is too small and sprintf(%lld) is not implemented in WinAVR (AVR-GCC).

This code works (with caveat):

void main()
{
    unsigned long long tagid;
    char tagid_str[12];

    tagid = 109876543210ull

    convert_to_decimal(tagid_str, tagid);
}

void convert_to_decimal(char* dst, unsigned long long src) 
{     
    int i;
    for (i = 0; i < 12; i ++) 
    {         
        dst[11 - i] = '0' + (int)(src % 10);
        src /= 10;     
    }     

    dst[12] = 0; 
} 

But look at the stats:

Program: 7358 bytes (89.8% Full) (.text + .data + .bootloader)

Data: 256 bytes (25.0% Full) (.data + .bss + .noinit)

The culprit is the % operator. I can't explain why using it with a long long generates almost 8k of code!

Here is a working alternative. I modified it to only use unsigned long long (64 bits) up to 12 decimal digits to fit the RFID reader format I'm using.

void main()
{
    unsigned long long tagid;
    char tagid_str[12];

    tagid = 000000000000ull;
    ulltostr((unsigned long long)tagid, tagid_str);

    tagid = 000000000001ull;
    ulltostr((unsigned long long)tagid, tagid_str);

    tagid = 109876543210ull;
    ulltostr((unsigned long long)tagid, tagid_str);

    tagid = 900000000000ull;
    ulltostr((unsigned long long)tagid, tagid_str);

    tagid = 999999999999ull;
    ulltostr((unsigned long long)tagid, tagid_str);
}

//http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&t=31199

void ulltostr(unsigned long long val, char *s ) 
{ 
  char *p; 
  unsigned char d, i; 
  unsigned char zero; 
  unsigned long long test; 
  unsigned long long uval = val; 

  p = s; 

  zero = 1; 

  i = 12; 
  do{ 
    i--;    
    if ( i==0)   test =10; 
    else if ( i==1) test =100; 
    else if ( i==2) test =1000; 
    else if ( i==3) test =10000; 
    else if ( i==4) test =100000; 
    else if ( i==5) test =1000000; 
    else if ( i==6) test =10000000; 
    else if ( i==7) test =100000000; 
    else if ( i==8) test =1000000000; 
    else if ( i==9) test =10000000000; 
    else if ( i==10) test=100000000000; 
    else if ( i==11) test=1000000000000; 
    else if ( i==12) test=10000000000000; 

    for( d = '0'; uval >= test; uval -= test ) 
    { 
      d++; 
      zero = 0; 
    } 
    if( zero == 0 ) 
      *p++ = d ; 
  }while( i ); 

  *p++ = (unsigned char)uval + '0'; 
}

And the stats:

Program: 758 bytes (9.3% Full) (.text + .data + .bootloader)

Data: 0 bytes (0.0% Full) (.data + .bss + .noinit)

Much better :)

I spent most of my time with Douglas Jones, but the answer finally came from AVR Freaks.