xxhash32_constexpr.cpp

// A C++11 constexpr implementation of xxhash32
// Jonathan Adamczewski / https://twitter.com/twoscomplement
// A reimplementation of code from https://github.com/Cyan4973/xxHash


// Foundation functions / commonly used patterns

// Read four chars and construct uint32_t (little endian)
constexpr uint32_t xxh_read32(const char* input)
{ 
  return (input[0] << 0) | (input[1] << 8) | (input[2] << 16) | (input[3] << 24);
}

// rotate left 32
constexpr uint32_t xxh_rotl32(uint32_t x, uint32_t r)
{ 
  return ((x << r) | (x >> (32 - r)));
}

constexpr uint32_t xxh_shiftxor32(uint32_t h, uint32_t s)
{ 
  return h ^ (h >> s);
}

constexpr uint32_t xxh_rotmul32(uint32_t h, uint32_t r, uint32_t m)
{ 
  return xxh_rotl32(h, r) * m;
}

// pattern used repeatedly on four byte groups
constexpr uint32_t xxh_apply32(uint32_t h, const char* input, uint32_t m0, uint32_t s, uint32_t m1)
{ 
  return xxh_rotmul32(xxh_read32(input) * m0 + h, s, m1);
}

constexpr uint32_t PRIME32_1 = 2654435761U;
constexpr uint32_t PRIME32_2 = 2246822519U;
constexpr uint32_t PRIME32_3 = 3266489917U;
constexpr uint32_t PRIME32_4 =  668265263U;
constexpr uint32_t PRIME32_5 =  374761393U;

// Recursive function that processes last 1-3 bytes
constexpr uint32_t xxh32_1(uint32_t h, const char* input, size_t len)
{ 
  return len == 0
         ? 
           h
         : 
           // similar to xxh_apply32(), but on one byte only
           xxh32_1(xxh_rotmul32(h + (*input * PRIME32_5), 11, PRIME32_1), input + 1, len - 1);
}

// Recursive function that processes last 1-3 four byte groups, then calls xxh32_1() to handle remainder
constexpr uint32_t xxh32_4(uint32_t h, const char* input, size_t len)
{ 
  return len < 4
         ? 
           xxh32_1(h, input, len)
         : 
           xxh32_4(xxh_apply32(h, input, PRIME32_3, 17, PRIME32_4), input + 4, len - 4);
}

// Recursive function that processes 16 byte groups.
constexpr uint32_t xxh32_16(uint32_t v0, uint32_t v1, uint32_t v2, uint32_t v3, const char* input, size_t len)
{ 
  return len >= 16
         ? 
           xxh32_16(xxh_apply32(v0, input, PRIME32_2, 13, PRIME32_1),
                    xxh_apply32(v1, input+4, PRIME32_2, 13, PRIME32_1),
                    xxh_apply32(v2, input+8, PRIME32_2, 13, PRIME32_1),
                    xxh_apply32(v3, input+12, PRIME32_2, 13, PRIME32_1),
                    input + 16, len - 16)
         : 
           xxh_rotl32(v0, 1) + xxh_rotl32(v1, 7) + xxh_rotl32(v2, 12) + xxh_rotl32(v3, 18);
}

// Final steps (separate function to aid legibility) 
constexpr uint32_t xxh32_finalize(uint32_t h)
{
  return xxh_shiftxor32(xxh_shiftxor32(xxh_shiftxor32(h, 15) * PRIME32_2, 13) * PRIME32_3, 16);
}

constexpr uint32_t XXH32Const(const char* input, size_t len, uint32_t seed)
{
  return xxh32_finalize(
           xxh32_4(
             len >= 16
             ?
               xxh32_16(seed + PRIME32_1 + PRIME32_2, seed + PRIME32_2, seed + 0, seed - PRIME32_1, input, len) + len
             :
               seed + PRIME32_5 + len,
             input + ((len / 16) * 16), // skip elems consumed by xxh32_16()
             len % 16));
}