You are currently browsing the monthly archive for October 2007.

I got into a discussion with a friend today about some C++ hackery using either template meta-programming or clever macro tricks. Essentially, I’m abusing the heck out of a set of header files by defining my own grammar to create constants. It takes 3 passes to go through it entirely.

  1. Interface, constants declared as extern. Everyone can include this.
  2. Implementation, constants defined locally. Only one file should use this. If you use switch statements on these constants, they must be defined in the same compilation unit, so whatever source code wants to use switch statements should have this.
  3. Stringification, where I use global static structures with constructor side-effects to populate a std::map, and a single function that maps unsigned integer values to the variable names (useful mostly for debugging). This part is definitely the biggest hack.

Why didn’t I just use enums? Because I want users to be able to inject their own constants into this set. Logically, it is an enum, but the implementation jumps through these silly hoops in order to make it extensible and add the name lookups.

This is a hack. It is a weakness that the language doesn’t provide an easier way to do extensible enumerations. It is awful to explain to a new person. But it’s beautiful in how it actually ends up working.

The next logical step, of course, is to add a way to convert these integers into their ASCII representation. The most obvious approach goes something like this:

std::string itoa(unsigned int i) {
    std::istringstream is;
    is << i;
    return is.str();
}

But that’s dog-slow. I want something faster (ok… maybe I don’t need anything faster, but it’s time to throw down the gauntlet and try!) Here’s where the template meta-programming comes in. I need two things:

  • A count of the digits of a given number (e.g. count(9999) = 4)
  • A way to represent fixed-precision numbers (up to the maximum number of digits representable in 32-bits, in this case).

Solution, Part 1

template <unsigned int N>
struct count_digits
{
    const static unsigned int value = count_digits<N/10>::value + 1;
};

#define COUNT_DIGITS_BASE_CASE(N)           \
template <>                                 \
struct count_digits<N>                      \
{                                           \
    const static unsigned int value = 1;    \
};
COUNT_DIGITS_BASE_CASE(0);
COUNT_DIGITS_BASE_CASE(1);
COUNT_DIGITS_BASE_CASE(2);
COUNT_DIGITS_BASE_CASE(3);
COUNT_DIGITS_BASE_CASE(4);
COUNT_DIGITS_BASE_CASE(5);
COUNT_DIGITS_BASE_CASE(6);
COUNT_DIGITS_BASE_CASE(7);
COUNT_DIGITS_BASE_CASE(8);
COUNT_DIGITS_BASE_CASE(9);

Ok. 10 base cases because we’re counting in base-10, and a recursive case that divides by 10 and adds one. Sounds like a logarithm, right? Good.

Solution, Part 2

Now I need to generate the actual strings:

 template <unsigned int N>
struct static_itoa
{
    // individual digits
    const static char digits[11];

    // string length
    const static unsigned int size = count_digits<N>::value;

    // valid NULL-terminated string
    const static char *value;
};

template <unsigned int N>
const char static_itoa<N>::digits[11] = {
    ((N / 1000000000) % 10) + '0',
    ((N / 100000000) % 10) + '0',
    ((N / 10000000) % 10) + '0',
    ((N / 1000000) % 10) + '0',
    ((N / 100000) % 10) + '0',
    ((N / 10000) % 10) + '0',
    ((N / 1000) % 10) + '0',
    ((N / 100) % 10) + '0',
    ((N / 10) % 10) + '0',
    ((N / 1) % 10) + '0',
    0
};
template <unsigned int N>
const char *static_itoa<N>::value = digits + sizeof(digits) - size - 1;

There it is. Works with GCC 4.0.3 when being referenced in a single location. I need to play more to see if I can make it work as a general header file without incurring the wrath of the linker (multiply-defined symbols!), but this works quite nicely:

int main() {
    const unsigned int x = 16;
    printf("%u: size = %u, str = %s\n", x,
        static_itoa<x>::size, static_itoa<x>::value);
    return 0;
}