Can C Compile-Time String Hashing Be Achieved Efficiently?

Can String Hashing Be Performed at Compile Time?

In C 11, speculation arose regarding the feasibility of calculating a string's hash at compile time using its new string literals.

Operator Syntax

The specifics of the operator's syntax for performing compile-time string hashing remain unclear. The proposed code sample showcasing its use cases suggests that the operator may resemble the fictional "std::hash(value)" shown below:

void foo(const std::string& value)
{
   switch( std::hash(value) )
   {
      case "one"_hash: one(); break;
      case "two"_hash: two(); break;
      /*many more cases*/
      default: other(); break;
   }
}

Implementation Challenges

Despite the apparent switch statement, there are implementation hurdles to overcome. Constant strings in C 11 are const char* and not std::strings. This requires additional conversion steps, potentially hampering efficiency.

Successful Implementation

A groundbreaking implementation of a compile-time CRC32 function was achieved using constexpr, but it's limited to GCC compilers at present. This implementation leverages a CRC32 table and recursive constexpr functions to compute the hash:

constexpr uint32_t crc32(const char * str, size_t idx = 0)
{
    return (crc32(str, idx-1) >> 8) ^ crc_table[(crc32(str, idx-1) ^ str[idx]) & 0x000000FF];
}
constexpr uint32_t crc32(const char * str, size_t(-1))
{
    return 0xFFFFFFFF;
}
#define COMPILE_TIME_CRC32_STR(x) (crc32(x) ^ 0xFFFFFFFF)

Using this implementation, one can calculate the compile-time CRC32 hash of a string like so:

enum TestEnum
{
    CrcVal01 = COMPILE_TIME_CRC32_STR("stack-overflow"),
};

This assigns the value 0x335CC04A to CrcVal01, demonstrating the practical application of compile-time string hashing.

The above is the detailed content of Can C Compile-Time String Hashing Be Achieved Efficiently?. For more information, please follow other related articles on the PHP Chinese website!