Converting hex to integer

Question

What's the fastest way of doing this?

int hextoint(char number) {
    if (number == '0') {
        return 0;
    }
    if (number == '1') {
        return 1;
    }
    if (number == '2') {
        return 2;
    }
    /*
     *  3 through 8
     */
    if (number == '9') {
        return 9;
    }
    if (number == 'a') {
        return 10;
    }
    if (number == 'b') {
        return 11;
    }
    if (number == 'c') {
        return 12;
    }
    if (number == 'd') {
        return 13;
    }
    if (number == 'e') {
        return 14;
    }
    if (number == 'f') {
        return 15;
    }
    return -1;
}

Answer 1

It seems that RippeR isn't going to write a full answer, so here's my take (especially as my comments to another answer got deleted together with the little jewel that proposed std::unordered_map).

First of all, the performance charactistics of a small function like hex digit conversion depend heavily on the context where it is used, and so it's impossible to say what's fastest until a concrete usage context has been specified.

The problem of hex digit conversion is a bit special in that it has a particular solution - the lookup table - which has excellent performance characteristics across a wide range of usages, and the smallest possible code footprint at the same time. It does, however, impose a bit of overhead for the initialisation of the lookup table, either in the form of static initialisation or initialisation with code.

Anyway: regardless of how the lookup table gets initialised, it will usually be used via a litte function wrapper (or member function, if wrapped in a class):

enum {  NOT_A_DIGIT = (1 << CHAR_BIT) - 1  };
typedef unsigned char byte;
byte DigitValue[1 << CHAR_BIT];

// ...

unsigned hex_digit_value_v3 (char c)
{
   return DigitValue[byte(c)];
}

The cast to byte (i.e. unsigned char) is necessary because char can be - and often is - signed.

Modern compilers will usually inline the code even if it resides in a .cpp somewhere, so there's no need to get cute. In an actual implementation the lookup table could be integrated with the character classification table for the scanner/lexer, but here I filled all non-digit slots with NOT_A_DIGIT. For completeness' sake, here's the initialisation code I used:

void set_lookup_range_ (byte base_value, char lo, char hi)
{
   for (byte c = byte(lo); ; ++c)
   {
      DigitValue[c] = byte(base_value + (c - byte(lo)));  // cast needed since ari widens to int

      if (c >= byte(hi))
         return;
   }
}

void initialise_lookup_table ()
{
   std::memset(DigitValue, NOT_A_DIGIT, sizeof(DigitValue));
   set_lookup_range_( 0, '0', '9');
   set_lookup_range_(10, 'A', 'F');
   set_lookup_range_(10, 'a', 'f');
}

It takes more space than static initialisation but it's more flexible, which is good for experimentation. It also makes the code independent from the execution character set in the sense that it's not necessary to know up front which character maps to which code point.

To get some timings I pitted the function against three other versions. To make the test realistic, I adapted a function from a high-performance scanner:

// to be called with read_ptr pointing at a hex digit; digits that don't fit into an unsigned get
// dropped quietly (i.e. they shifted out at the upper end)

template<unsigned hex_digit_value (char c)>
DECLSPEC_NOINLINE
unsigned extract_hex_unsigned (char const **read_ptr)
{
   char const *p = *read_ptr;
   unsigned value = hex_digit_value(*p);
   unsigned digit;

   while ((digit = hex_digit_value(*++p)) < 16)
      value = (value << 4) + digit;

   *read_ptr = p;

   return value;
}

Besides allowing tests with a bunch of 8-digit hex strings, it can also be called with huge strings to get a different take on performance characteristics. Excess digits are lost because they get shifted out but hex_digit_value() gets called for each of them and that's what matters for the timings.

The first contender is the OP's own solution:

unsigned hex_digit_value_v0 (char c)
{
   if (c == '0')  return  0;  
   if (c == '1')  return  1;  
   // ... 18 more not shown ...
   if (c == 'e')  return 14;
   if (c == 'f')  return 15;

   return NOT_A_DIGIT;
}

The second contender looks almost the same but it uses a switch statement instead of conditionals. If you think that it has little merit then you may be in for a little surprise when you look at the timings:

unsigned hex_digit_value_v1 (char c)
{
   switch (c)
   {
      case '0':  return  0;
      case '1':  return  1;
      // ... 18 more not shown ...
      case 'e':  return 14;
      case 'f':  return 15;
   }

   return NOT_A_DIGIT;
}

Last but not least, a reasonably straightforward solution where I lent helping hand to the compiler regarding the math (something we used to do a lot with older compilers):

unsigned hex_digit_value_v2 (char c)
{
   switch (c)
   {
      case '0': case '1': case '2': case '3': case '4':
      case '5': case '6': case '7': case '8': case '9':
         return byte(c - '0');
      case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
         return byte(c - 'A' + 10);
      case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
         return byte(c - 'a' + 10);
   }

   return NOT_A_DIGIT;
}

Note, however, that this depends on three character ranges being contiguous and hence might not work with execution character sets that aren't based on ASCII and its descendants. The other three solutions are completely immune to such problems.

The test frame fills a big string with random hex digits (including upper case and lower case) or with a given number of 8-digit words separated by a blank. Timings are taken with the Windows high performance counter, which is essentially the CPU's time stamp counter divided by 256.

At this low resolution the fastest version needed only 3 ticks to go through a thousand digits, hence the big test data sizes. Using the TSC directly would have been better but then the code wouldn't have been portable across compilers.

In order to exclude to vagaries caused by caches and task switches, each test was repeated a number of times and the median of the measurements returned as result. This also means that the times that got printed refer to hot caches. A global sink variable was used to make the compiler think that the produced values were actually used somehow, to keep it from simply eliding the code altogether or reducing it to bumping the read pointer.

template<unsigned digit_value_vx (char c)>
double test_m (unsigned repeats = 10)
{
   std::vector<zrbj::Timer::Ticks> measurements;
   zrbj::Timer t;

   for (unsigned repeats_left = repeats; repeats_left--; )
   {
      char const *p = test_string.c_str(), *e = p + test_string.length();
      unsigned x = 0; 
      t.Start();
      while (p < e)
      {
         x += extract_hex_unsigned<digit_value_vx>(&p);
         ++p;  // skip the character that caused the scanning to stop
      }
      t.Stop();
      g_sink += x;
      measurements.push_back(t.Elapsed());
   }

   std::sort(measurements.begin(), measurements.end());

   return t.ms(measurements[measurements.size() / 2]) * 1000;
}

So here's the timings in microseconds for three compilers; the test sizes are given as (number of strings) x (string length).

*** BC++ 7.10 (RX/Seattle) 64 *** CLANG 3.3.1 (35465.f352ad3.17344af)

1 x   1000:           9.9 v0         13.2 v1          4.2 v2          1.9 v3
1 x  10000:         135.4 v0        147.6 v1         87.9 v2         18.9 v3
1 x 100000:        1359.6 v0       1472.6 v1        964.4 v2        192.5 v3
   100 x 8:           7.4 v0         10.6 v1          3.5 v2          1.9 v3
  1000 x 8:         110.4 v0        114.2 v1         74.1 v2         18.9 v3
 10000 x 8:        1124.5 v0       1182.5 v1        825.2 v2        183.5 v3

*** VC++ 12.0 (x64) *** RTTI _CPPUNWIND 180031101.0

1 x   1000:           8.3 v0          5.5 v1          2.2 v2          0.6 v3
1 x  10000:         118.4 v0        122.9 v1         60.3 v2          5.5 v3
1 x 100000:        1214.6 v0       1250.9 v1        623.0 v2         51.3 v3
   100 x 8:           6.4 v0          3.5 v1          1.9 v2          0.6 v3
  1000 x 8:          96.6 v0        120.9 v1         48.1 v2          5.5 v3
 10000 x 8:         961.5 v0        995.5 v1        553.1 v2         56.5 v3

*** g++ 4.8.1 64 ***

1 x   1000:           3.2 v0          0.6 v1          1.3 v2          0.6 v3
1 x  10000:          88.9 v0          6.7 v1         45.9 v2          5.5 v3
1 x 100000:         940.3 v0         70.3 v1        484.8 v2         52.6 v3
   100 x 8:           2.2 v0          0.6 v1          1.3 v2          0.3 v3
  1000 x 8:          67.1 v0          5.8 v1         33.4 v2          3.2 v3
 10000 x 8:         723.5 v0         58.7 v1        390.4 v2         33.4 v3

As you can see, the version with the lookup table (v3) performs best with all three compilers. And gcc manages to make v1 (with the simple switch case '0': return 0; and so on) almost as fast as the lookup-based version. I was a bit disappointed with the other two for not doing the same, though. VC++ is normally quite decent at sorting out the messy stuff under the hood without a lot of hand-holding by the programmer, and I'd have expected more of Emborlandero's clang-based compiler, after the long years of waiting for it.

As regards code size, v3 wins hands-down as it compiles to at most two machine instructions and so there's no need to keep over-eager compilers from bloating the code with overly aggressive inlining.

Answer 2

The fastest way is almost certainly using a table lookup:

int hex_digit_to_int(char digit) {
    static int values[] = {
         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0,  // 0-9
         0,10,11,12,13,14,15, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // A-F
         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0,10,11,12,13,14,15, 0, 0, 0, 0, 0, 0, 0, 0, 0,  // a-f
         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
    };

    return values[digit];
}

That said, I doubt any version of this (unless it's particularly egregious) wil end up being a bottleneck in the performance of your code.