Converting to ASCII in C

The obvious solution is not to convert the data to ASCII at all but store it in binary format. That way all you need to worry about is the endianness of the data. If the system performing the later analysis is far more powerful than your embedded target, then it would make sense to let that deal with the conversion and and byte order.

On the other hand, it is possible that the execution time of the / and % is insignificant compared to the time taken to transfer the data to the SD card; so make sure that you are optimising the right thing.

There's certainly a much faster way: have an array of 1024 pre-computed strings. Then you can just do bounds checking, followed by an index into the array.

It's unclear from your question whether your code is running on the microcontroller though. If that's the case, you may not have enough memory for this approach.

I agree with what Clifford said, that you shouldn't worry about optimizing it if you don't have to, and that you can push the log cleanup to your analysis platform, rather than worrying about formatting in an embedded application.

That being said, here's an article that might be useful to you. It uses a loop, shifts, additions and branches, with linear/constant complexity: http://www.johnloomis.org/ece314/notes/devices/binary_to_BCD/bin_to_bcd.html

Also, I thought it would be fun to make some code that doesn't perform any divides, multiplies, or branches, but still gives the correct answer [0 - 1024). No promises that this is any faster than other options. This sort of code is just an option to explore.

I'd love to see if anyone can provide some tricks to make the code smaller, require less memory, or require fewer operations, while keeping the rest of the counts equal, or shrinking them :)

Stats:

• 224 bytes in constants (no idea on the code size)
• 5 bit-shift-rights
• 3 subtracts
• 5 bitwise-ands
• 4 bitwise-ors
• 1 greater-than comparison

Perf:

Using the perf comparisons and itoa routines in Jonathan Leffler's answer, here are the stats I got:

• Division 2.15
• Subtraction 4.87
• My solution 1.56
• Brute force lookup 0.36

I increased the iteration count to 200000 to ensure I didn't have any problems with timing resolution, and had to add volatile to the function signatures so that the compiler didn't optimize out the loop. I used VS2010 express w/ vanilla "release" settings, on a 3ghz dual core 64 bit Windows 7 machine (tho it compiled to 32 bit).

The code:

#include "stdlib.h"
#include "stdio.h"
#include "assert.h"

void itoa_ten_bits(int n, char s[])
{
  static const short thousands_digit_subtract_map[2] =
  {
    0, 1000,
  };

  static const char hundreds_digit_map[128] =
  {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
    4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
    9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
    0, 0, 0,
  };

  static const short hundreds_digit_subtract_map[10] =
  {
    0, 100, 200, 300, 400, 500, 600, 700, 800, 900,
  };

  static const char tens_digit_map[12] =
  {
    0, 1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 9,
  };

  static const char ones_digit_map[44] =
  {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
    0, 1, 2, 3
  };

  /* Compiler should optimize out appX constants, % operations, and + operations */
  /* If not, use this:
    static const char ones_digit_append_map[16] =
    {
      0, 6, 2, 8, 4, 10, 6, 12, 8, 14, 10, 16, 12, 18, 14, 20,
    };
  */
  static const char a1 = 0x10 % 10, a2 = 0x20 % 10, a3 = 0x40 % 10, a4 = 0x80 % 10;
  static const char ones_digit_append_map[16] =
  {
    0, a1, a2, a1 + a2,
    a3, a1 + a3, a2 + a3, a1 + a2 + a3,
    a4, a1 + a4, a2 + a4, a1 + a2 + a4,
    a3 + a4, a1 + a3 + a4, a2 + a3 + a4, a1 + a2 + a3 + a4,
  };

  char thousands_digit, hundreds_digit, tens_digit, ones_digit;

  assert(n >= 0 && n < 1024 && "n must be between [0, 1024)");
  /* n &= 0x3ff; can use this instead of the assert */

  thousands_digit = (n >> 3 & 0x7f) > 0x7c;
  n -= thousands_digit_subtract_map[thousands_digit];

  ones_digit = ones_digit_map[
    (n & 0xf)
      + ones_digit_append_map[n >> 4 & 0xf]
      + ones_digit_append_map[n >> 8 & 0x3]
    ];
  n -= ones_digit;

  hundreds_digit = hundreds_digit_map[n >> 3 & 0x7f];
  n -= hundreds_digit_subtract_map[hundreds_digit];

  tens_digit = tens_digit_map[n >> 3];

  s[0] = '0' | thousands_digit;
  s[1] = '0' | hundreds_digit;
  s[2] = '0' | tens_digit;
  s[3] = '0' | ones_digit;
  s[4] = '\0';
}

int main(int argc, char* argv)
{
  int i;
  for(i = 0; i < 1024; ++i)
  {
    char blah[5];
    itoa_ten_bits(i, blah);
    if(atoi(blah) != i)
      printf("failed %d %s\n", i, blah);
  }
}