Skienna hash

skinna_hash32.c

#define PHI 0x585f14dULL

static inline uint32_t
_skiena_hash32 (const uint8_t *msg, size_t msg_len)
{
  static uint16_t rand_map[UCHAR_MAX] = {
    0x144, 0x1ab, 0x13c, 0x028, 0x1c3, 0x107, 0x193, 0x174, 0x00c, 0x160,
    0x142, 0x0fe, 0x01f, 0x1b0, 0x198, 0x160, 0x10f, 0x185, 0x015, 0x051,
    0x057, 0x138, 0x17e, 0x199, 0x1f5, 0x01e, 0x1f2, 0x01f, 0x174, 0x0b7,
    0x085, 0x0a5, 0x200, 0x14d, 0x188, 0x168, 0x1e4, 0x1ef, 0x15c, 0x14e,
    0x0b1, 0x11f, 0x056, 0x0e5, 0x1ae, 0x044, 0x0f4, 0x0ac, 0x0de, 0x034,
    0x133, 0x14c, 0x074, 0x182, 0x17a, 0x13d, 0x191, 0x0e2, 0x0ef, 0x077,
    0x177, 0x057, 0x0c6, 0x1a9, 0x11b, 0x1c9, 0x0e4, 0x0f9, 0x0bc, 0x156,
    0x1ac, 0x156, 0x055, 0x053, 0x018, 0x01e, 0x1fb, 0x1a5, 0x120, 0x0af,
    0x054, 0x071, 0x036, 0x03d, 0x046, 0x0f6, 0x144, 0x1c1, 0x0d8, 0x140,
    0x041, 0x168, 0x1e1, 0x0ff, 0x119, 0x0ea, 0x0f9, 0x0ac, 0x058, 0x01e,
    0x1a7, 0x09b, 0x169, 0x0f1, 0x172, 0x0f6, 0x132, 0x12b, 0x14e, 0x05c,
    0x04d, 0x151, 0x023, 0x137, 0x13b, 0x10f, 0x035, 0x0dd, 0x039, 0x0f6,
    0x0ae, 0x00d, 0x0d7, 0x191, 0x1d0, 0x03f, 0x1c9, 0x186, 0x0cf, 0x1d4,
    0x175, 0x1a0, 0x1ba, 0x052, 0x0f0, 0x03e, 0x00a, 0x123, 0x0d0, 0x1e9,
    0x1db, 0x145, 0x0eb, 0x04d, 0x1bf, 0x12d, 0x1e2, 0x0cb, 0x0ef, 0x18e,
    0x06d, 0x04c, 0x04a, 0x096, 0x069, 0x0ae, 0x0ef, 0x113, 0x078, 0x0df,
    0x199, 0x196, 0x040, 0x06c, 0x0be, 0x0c8, 0x1a9, 0x0f4, 0x05b, 0x0d4,
    0x0a4, 0x17b, 0x00d, 0x10e, 0x0fa, 0x00f, 0x177, 0x0be, 0x0cd, 0x02c,
    0x153, 0x055, 0x0ff, 0x1b9, 0x02b, 0x015, 0x112, 0x0b3, 0x191, 0x0be,
    0x0d5, 0x10c, 0x02e, 0x0b3, 0x10b, 0x19d, 0x19e, 0x1c0, 0x1c2, 0x150,
    0x0bf, 0x099, 0x144, 0x15b, 0x071, 0x07f, 0x1cb, 0x085, 0x1bf, 0x1f5,
    0x1ef, 0x0c1, 0x1d0, 0x1da, 0x103, 0x142, 0x1fa, 0x0e9, 0x1e3, 0x193,
    0x133, 0x1e0, 0x081, 0x03e, 0x049, 0x080, 0x03e, 0x138, 0x1cf, 0x055,
    0x059, 0x12e, 0x010, 0x09e, 0x12b, 0x01b, 0x06a, 0x14f, 0x06a, 0x0a0,
    0x1ae, 0x1b3, 0x066, 0x1c9, 0x121, 0x1ac, 0x0f6, 0x0db, 0x01b, 0x1eb,
    0x1c2, 0x1f3, 0x057, 0x154, 0x184, 0x086,
  };

  uint32_t hash = 0;
  size_t i = 0;
  while (i++ < msg_len)
    hash += msg[msg_len - (i + 1)] * rand_map[msg[i]];
  return hash;
}

static inline uint32_t
_knuth_hash32 (const uint8_t *msg, size_t msg_len, size_t log2)
{
  return ((uint32_t)(PHI * (uint64_t)_skiena_hash32 (msg, msg_len)))
         >> (32 - log2);
}