hash.h

Go to the documentation of this file.

/* Copyright Benoit Hudson 2007 */
#ifndef details_hash_HEADER
#define details_hash_HEADER

#ifdef HAVE_CONFIG_H
 #include <config.h>
#endif

#include <limits.h> // CHAR_BIT
BOOST_STATIC_ASSERT(CHAR_BIT == 8);
#include <assert.h>

namespace hudson { namespace details {

  /************************************************************
   * Paul Hsieh's hash function, 32-bit only.
   *
   * This operates a word at a time, and is often reported to
   * be faster than Jenkin's function.
   ************************************************************/
  template <class iterator, class hashfn>
  uint32_t hsieh(iterator begin, const iterator& end, hashfn h) {
    BOOST_STATIC_ASSERT(sizeof(h(*begin)) * CHAR_BIT == 32);
    uint32_t hash = 0, tmp;

    if (begin == end) return 0;

    /* Main loop */
    for( ; begin != end; ++begin) {
      uint32_t hashed = h(*begin);
      uint32_t hi = hashed >> 16;
      uint32_t lo = hashed & ( (1<<16) - 1);
      hash += hi;
      tmp   = (lo << 11) ^ hash;
      hash  = (hash << 16) ^ tmp;
      hash += hash >> 11;
    }

    /* Force "avalanching" of final 127 bits */
    hash ^= hash << 3;
    hash += hash >> 5;
    hash ^= hash << 4;
    hash += hash >> 17;
    hash ^= hash << 25;
    hash += hash >> 6;

    return hash;
  }

  /************************************************************
   * Bob Jenkin's hash functions, 32- and 64-bit.
   * These are adapted to drop the assumption that we're hashing
   * characters.
   * @{
   ************************************************************/
  template <class Int> Int rot(Int x, unsigned k) {
    size_t nbits = sizeof(Int) * CHAR_BIT;
    return (x << k) | (x >> (nbits - k));
  }

  template <size_t wordsize> class mixer;

  template <> struct mixer<4> {
    typedef uint32_t word;

    static void mix(uint32_t& a, uint32_t& b, uint32_t& c) {
      a -= c;  a ^= rot(c, 4);  c += b;
      b -= a;  b ^= rot(a, 6);  a += c;
      c -= b;  c ^= rot(b, 8);  b += a;
      a -= c;  a ^= rot(c,16);  c += b;
      b -= a;  b ^= rot(a,19);  a += c;
      c -= b;  c ^= rot(b, 4);  b += a;
    }

    static uint32_t final(uint32_t a, uint32_t b, uint32_t c) {
      c ^= b; c -= rot(b,14);
      a ^= c; a -= rot(c,11);
      b ^= a; b -= rot(a,25);
      c ^= b; c -= rot(b,16);
      a ^= c; a -= rot(c,4);
      b ^= a; b -= rot(a,14);
      c ^= b; c -= rot(b,24);
      return c;
    }

    static uint32_t startvalue(uint32_t length) {
      return 0xdeadbeef + (((uint32_t)length)<<2);
    }
  };


  template <> struct mixer<8> {
    typedef uint64_t word;

    static void mix(uint64_t& a, uint64_t& b, uint64_t& c) {
      a -= b; a -= c; a ^= (c>>43);
      b -= c; b -= a; b ^= (a<<9);
      c -= a; c -= b; c ^= (b>>8);
      a -= b; a -= c; a ^= (c>>38);
      b -= c; b -= a; b ^= (a<<23);
      c -= a; c -= b; c ^= (b>>5);
      a -= b; a -= c; a ^= (c>>35);
      b -= c; b -= a; b ^= (a<<49);
      c -= a; c -= b; c ^= (b>>11);
      a -= b; a -= c; a ^= (c>>12);
      b -= c; b -= a; b ^= (a<<18);
      c -= a; c -= b; c ^= (b>>22);
    }

    static uint64_t final(uint64_t a, uint64_t b, uint64_t c) {
      mix(a,b,c);
      return c;
    }

    static uint64_t startvalue(uint64_t /*length*/) {
      return 0x9e3779b97f4a7c13LL;
    }
  };


  template <class iterator, class hasher>
  size_t
  jenkins(iterator begin, iterator end, const hasher& hash) {
    typedef mixer<sizeof(size_t)> M;

    M::word a,b,c;
    size_t length = (end - begin); // ideally we wouldn't need this

    /* Set up the internal state */
    a = b = c = M::startvalue(length);

    /* Handle most of the key */
    while (length > 3) {
      a += hash(*begin); ++begin;
      b += hash(*begin); ++begin;
      c += hash(*begin); ++begin;
      M::mix(a,b,c);
      length -= 3;
    }

    /* Handle the last 3 items */
    switch(length) {
      case 3: a += hash(*begin); ++begin; // fall-through
      case 2: b += hash(*begin); ++begin; // fall-through
      case 1: c += hash(*begin); //++begin;
              return M::final(a,b,c);
      case 0: return c;
    }
    /* Can't get here. */
    assert(0);
    return 0;
  }

  /************************************************************
   * Hash functions for a single word at a time.
   * @{
   ************************************************************/

  template <size_t wordsize> class hash_single;

  template <> struct hash_single<4> {
    /* Thomas Wang's 32-bit hash.  Jenkins claims it's good.
     * Should take a mere 9 cycles. */
    static uint32_t hash( uint32_t a) {
      a = (a ^ 61) ^ (a >> 16);
      a = a + (a << 3);
      a = a ^ (a >> 4);
      a = a * 0x27d4eb2d;
      a = a ^ (a >> 15);
      return a;
    }

#if 0
    /* Renamed from jenkins' 6-shift 4-byte integer hash function.
     * This is a good hash for a gappy integer value (like a pointer).
     * Should take 12 cycles.  */
    static uint32_t hash(uint32_t a) {
      a = (a+0x7ed55d16) + (a<<12);
      a = (a^0xc761c23c) ^ (a>>19);
      a = (a+0x165667b1) + (a<<5);
      a = (a+0xd3a2646c) ^ (a<<9);
      a = (a+0xfd7046c5) + (a<<3);
      a = (a^0xb55a4f09) ^ (a>>16);
      return a;
    }
#endif
  };

  template <> struct hash_single<8> {
    static uint64_t hash(uint64_t a) {
      a = (~a) + (a << 21); // a = (a << 21) - a - 1;
      a = a ^ (a >> 24);
      a = (a + (a << 3)) + (a << 8); // a * 265
      a = a ^ (a >> 14);
      a = (a + (a << 2)) + (a << 4); // a * 21
      a = a ^ (a >> 28);
      a = a + (a << 31);
      return a;
    }
  };

  /************************************************************
   * Hash functions for a pair of words.
   * In 32 bits, we can use the 64-bit word-at-a-time hash.
   * In 64 bits, I use Jenkin's function, which is overkill.
   * @{
   ************************************************************/
  template <size_t nbytes> struct hash_pair;

  template <> struct hash_pair<4> {
    static uint32_t hash(uint32_t a, uint32_t b) {
      // hash as a 64-bit quantity, then return the lower 32 bits
      uint64_t ab = (((uint64_t)a) << 32) | (uint64_t)b;
      uint64_t h = hash_single<8>::hash(ab);
      return (uint32_t) h;
    }
  };

  template <> struct hash_pair<8> {
    static uint64_t hash(uint64_t a, uint64_t b) {
      // The answer is to run jenkins' hash with a third value of 42
      return mixer<8>::final(a, b, 42);
    }
  };

  /************************************************************
   * Hash functions for a range of items.
   *
   * @{
   ************************************************************/
  template <size_t nbytes> struct hash_range;

  template <> struct hash_range<4> {
    template <class iterator, class hasher>
    static uint32_t hash(const iterator& begin, const iterator& end,
        const hasher& h) {
      return hsieh(begin, end, h);
    }
  };

  template <> struct hash_range<8> {
    template <class iterator, class hasher>
    static uint64_t hash(const iterator& begin, const iterator& end,
        const hasher& h) {
      return jenkins(begin, end, h);
    }
  };

} } // close namespace hudson::details

#endif

---