| // 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 "kudu/gutil/hash/jenkins.h" |
| |
| #include <glog/logging.h> |
| |
| #include "kudu/gutil/hash/jenkins_lookup2.h" |
| #include "kudu/gutil/integral_types.h" |
| #include "kudu/gutil/port.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)); |
| } |
| |
| ATTRIBUTE_NO_SANITIZE_INTEGER |
| 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; |
| } |
| |
| |
| ATTRIBUTE_NO_SANITIZE_INTEGER |
| 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; |
| } |
| |
| ATTRIBUTE_NO_SANITIZE_INTEGER |
| 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; |
| } |