be/src/gutil/hash/jenkins.cc

// Copyright 2011 Google Inc. All Rights Reserved.
//
// Contains the legacy Bob Jenkins Lookup2-based hashing routines. These need to
// always return the same results as their values have been recorded in various
// places and cannot easily be updated.
//
// Original Author: Sanjay Ghemawat
//
// This is based on Bob Jenkins newhash function
// see: http://burtleburtle.net/bob/hash/evahash.html
// According to http://burtleburtle.net/bob/c/lookup2.c,
// his implementation is public domain.
//
// The implementation here is backwards compatible with the google1
// implementation.  The google1 implementation used a 'signed char *'
// to load words from memory a byte at a time.  See gwshash.cc for an
// implementation that is compatible with Bob Jenkins' lookup2.c.

#include "gutil/hash/jenkins.h"

#include "gutil/integral_types.h"
#include <common/logging.h>
#include "gutil/logging-inl.h"
#include "gutil/hash/jenkins_lookup2.h"

static inline uint32 char2unsigned(char c) {
  return static_cast<uint32>(static_cast<unsigned char>(c));
}

static inline uint64 char2unsigned64(char c) {
  return static_cast<uint64>(static_cast<unsigned char>(c));
}

uint32 Hash32StringWithSeedReferenceImplementation(const char *s, uint32 len,
                                                   uint32 c) {
  uint32 a, b;
  uint32 keylen;

  a = b = 0x9e3779b9UL;           // the golden ratio; an arbitrary value

  for ( keylen = len;  keylen >= 3*sizeof(a);
        keylen -= static_cast<uint32>(3*sizeof(a)), s += 3*sizeof(a) ) {
    a += Google1At(s);
    b += Google1At(s + sizeof(a));
    c += Google1At(s + sizeof(a)*2);
    mix(a,b,c);
  }

  c += len;
  switch ( keylen ) {           // deal with rest.  Cases fall through
    case 11: c += char2unsigned(s[10]) << 24;
    case 10: c += char2unsigned(s[9]) << 16;
    case 9 : c += char2unsigned(s[8]) << 8;
      // the first byte of c is reserved for the length
    case 8 : b += Google1At(s+4);  a += Google1At(s);  break;
    case 7 : b += char2unsigned(s[6]) << 16;
    case 6 : b += char2unsigned(s[5]) << 8;
    case 5 : b += char2unsigned(s[4]);
    case 4 : a += Google1At(s);  break;
    case 3 : a += char2unsigned(s[2]) << 16;
    case 2 : a += char2unsigned(s[1]) << 8;
    case 1 : a += char2unsigned(s[0]);
      // case 0 : nothing left to add
  }
  mix(a,b,c);
  return c;
}


uint32 Hash32StringWithSeed(const char *s, uint32 len, uint32 c) {
  uint32 a, b;
  uint32 keylen;

  a = b = 0x9e3779b9UL;           // the golden ratio; an arbitrary value

  keylen = len;
  if (keylen >= 4 * sizeof(a)) {
    uint32 word32AtOffset0 = Google1At(s);
    do {
      a += word32AtOffset0;
      b += Google1At(s + sizeof(a));
      c += Google1At(s + sizeof(a) * 2);
      s += 3 * sizeof(a);
      word32AtOffset0 = Google1At(s);
      mix(a, b, c);
      keylen -= 3 * static_cast<uint32>(sizeof(a));
    } while (keylen >= 4 * sizeof(a));
    if (keylen >= 3 * sizeof(a)) {
      a += word32AtOffset0;
      b += Google1At(s + sizeof(a));
      c += Google1At(s + sizeof(a) * 2);
      s += 3 * sizeof(a);
      mix(a, b, c);
      keylen -= 3 * static_cast<uint32>(sizeof(a));
      DCHECK_LT(keylen, sizeof(a));
      c += len;
      switch ( keylen ) {           // deal with rest.  Cases fall through
        case 3 : a += char2unsigned(s[2]) << 16;
        case 2 : a += char2unsigned(s[1]) << 8;
        case 1 : a += char2unsigned(s[0]);
      }
    } else {
      DCHECK(sizeof(a) <= keylen && keylen < 3 * sizeof(a));
      c += len;
      switch ( keylen ) {           // deal with rest.  Cases fall through
        case 11: c += char2unsigned(s[10]) << 24;
        case 10: c += char2unsigned(s[9]) << 16;
        case 9 : c += char2unsigned(s[8]) << 8;
        case 8 : b += Google1At(s+4);  a += word32AtOffset0;  break;
        case 7 : b += char2unsigned(s[6]) << 16;
        case 6 : b += char2unsigned(s[5]) << 8;
        case 5 : b += char2unsigned(s[4]);
        case 4 : a += word32AtOffset0;  break;
      }
    }
  } else {
    if (keylen >= 3 * sizeof(a)) {
      a += Google1At(s);
      b += Google1At(s + sizeof(a));
      c += Google1At(s + sizeof(a) * 2);
      s += 3 * sizeof(a);
      mix(a, b, c);
      keylen -= 3 * static_cast<uint32>(sizeof(a));
    }
    c += len;
    switch ( keylen ) {           // deal with rest.  Cases fall through
      case 11: c += char2unsigned(s[10]) << 24;
      case 10: c += char2unsigned(s[9]) << 16;
      case 9 : c += char2unsigned(s[8]) << 8;
      case 8 : b += Google1At(s+4);  a += Google1At(s);  break;
      case 7 : b += char2unsigned(s[6]) << 16;
      case 6 : b += char2unsigned(s[5]) << 8;
      case 5 : b += char2unsigned(s[4]);
      case 4 : a += Google1At(s);  break;
      case 3 : a += char2unsigned(s[2]) << 16;
      case 2 : a += char2unsigned(s[1]) << 8;
      case 1 : a += char2unsigned(s[0]);
    }
  }
  mix(a, b, c);
  return c;
}

uint64 Hash64StringWithSeed(const char *s, uint32 len, uint64 c) {
  uint64 a, b;
  uint32 keylen;

  a = b = GG_ULONGLONG(0xe08c1d668b756f82);   // the golden ratio; an arbitrary value

  for ( keylen = len;  keylen >= 3 * sizeof(a);
	keylen -= 3 * static_cast<uint32>(sizeof(a)), s += 3 * sizeof(a) ) {
    a += Word64At(s);
    b += Word64At(s + sizeof(a));
    c += Word64At(s + sizeof(a) * 2);
    mix(a,b,c);
  }

  c += len;
  switch ( keylen ) {           // deal with rest.  Cases fall through
    case 23: c += char2unsigned64(s[22]) << 56;
    case 22: c += char2unsigned64(s[21]) << 48;
    case 21: c += char2unsigned64(s[20]) << 40;
    case 20: c += char2unsigned64(s[19]) << 32;
    case 19: c += char2unsigned64(s[18]) << 24;
    case 18: c += char2unsigned64(s[17]) << 16;
    case 17: c += char2unsigned64(s[16]) << 8;
      // the first byte of c is reserved for the length
    case 16: b += Word64At(s+8);  a += Word64At(s);  break;
    case 15: b += char2unsigned64(s[14]) << 48;
    case 14: b += char2unsigned64(s[13]) << 40;
    case 13: b += char2unsigned64(s[12]) << 32;
    case 12: b += char2unsigned64(s[11]) << 24;
    case 11: b += char2unsigned64(s[10]) << 16;
    case 10: b += char2unsigned64(s[ 9]) << 8;
    case  9: b += char2unsigned64(s[ 8]) ;
    case  8: a += Word64At(s);  break;
    case  7: a += char2unsigned64(s[ 6]) << 48;
    case  6: a += char2unsigned64(s[ 5]) << 40;
    case  5: a += char2unsigned64(s[ 4]) << 32;
    case  4: a += char2unsigned64(s[ 3]) << 24;
    case  3: a += char2unsigned64(s[ 2]) << 16;
    case  2: a += char2unsigned64(s[ 1]) << 8;
    case  1: a += char2unsigned64(s[ 0]) ;
      // case 0: nothing left to add
   }
   mix(a,b,c);
   return c;
}