Thought Clutter

Recently, I have been working on a project with the Make Controller. The Make Controller has been a handy platform for me to explore the ARM architecture, and the libraries distributed by MakingThings make it easy. While screwing around with the build of FreeRTOS included with the software, I stumbled across a piece of the C standard library that has bit me in the ass before. I figured I'd blog about it here so others don't fall into the same trap I did, or at least can get themselves out when they do.

Often while developing embedded systems, I am a bit picky about understanding all the lines of code in the system. As processors have increased in memory and performance, this is becoming less of an issue, and should certainly be true for the ARM architecture. However, I was surprised to discover that a minimal FreeRTOS build (with the MakingThings configuration) on the ARM was clocking in at around 30kBytes. Digging into the map file, I was shocked to discover that the RTOS build was including the floating point libraries. Unable to explain why an RTOS needs floating point libraries, I dug until I came across the following innocuous line in tasks.c, and it all became clear:

 
sprintf( pcStatusString, ( portCHAR * ) "%s\t\t%c\t%u\t%u\t%u\r\n", /*SNIP*/ );
 

Nothing is obviously suspicious about the above line. We are just formatting a set of strings and unsigned integers. However, if we consider how sprintf and it's ilk need to work, it becomes clear why the floating point libraries were included in the FreeRTOS build. The standard library function sprintf determines data types by parsing the format string. When sprintf was compiled, the code for "%f" was compiled as well as the "%u" formatter. As a result, the floating point libraries will be linked in.

In this case, the fix was easy. MakingThings distributed the FreeRTOS build with trace enabled, which resulted in the call to sprintf. By just disabling FreeRTOS's trace feature, we remove the call to sprintf and reduce the code size to about 7kBytes.

At this point, you might be thinking, "But I actually wanted to get the strings for those numbers." If so, you easily could write your own unsigned integer formatting function:

 
void MySprintfU(char *inStr, unsigned inVal)
{
    unsigned i, j;
 
    // Setup the values
    i = j = 0;
 
    // Find base 10 ASCII representation (reverse order in string)
    while(inVal)
    {
        unsigned temp;
        temp = inVal / 10;
        inStr[i++] = inVal - (temp * 10) + '0';
        inVal = temp;
    }
 
    // Handle 0
    if (i == 0)
        inStr[i++] = '0';
 
    // Null terminate
    inStr[i] = 0;
 
    // Reverse the inString
    while(j < i)
    {
        char c = inStr[--i];
        inStr[i] = inStr[j];
        inStr[j++] = c;
    }
}
 

But, even this has it's drawbacks. Mainly, the following line:

 
temp = inVal / 10;
 

Many embedded processors don't have a divide intrinsic (I'm looking at you DSPs), so the divide function is implemented as a serious of divide primitives. The divide could end up taking 16-32 extra instructions per iteration of the while() loop. Clearly this could be unacceptable if we need the ASCII string often enough (insert the standard warning about profiling your code).

Fear not my gentle reader. I have encountered this problem before and I present the solution to you in the form of fixed-point math:

 
void MySprintfU(char *inStr, unsigned inVal)
{
    unsigned i, j;
 
    // Setup the values
    i = j = 0;
 
    // Find base 10 ASCII representation (reverse order in string)
    while(inVal)
    {
        unsigned temp;
        temp = ((unsigned long long)inVal *
                (unsigned long long)0xCCCCCCCD) >> 35;
        inStr[i++] = inVal - (temp * 10) + '0';
        inVal = temp;
    }
 
    // Handle 0
    if (i == 0)
        inStr[i++] = '0';
 
    // Null terminate
    inStr[i] = 0;
 
    // Reverse the inString
    while(j < i)
    {
        char c = inStr[--i];
        inStr[i] = inStr[j];
        inStr[j++] = c;
    }
}
 

Although the above code has "hack" written all over it, the performance is based on sound mathematical principles. Basically, we take our number as an 32 bit integer and multiply it by a 35-bit fractional representation of 1/10 (the high 3 bits are 0). The result is a 64 bit number, where the low 35 bits are less than 0. Shifting them out, gives us our number divided by 10. On some compilers and processors, I've seen the divide optimize into two instructions.