/Users/deen/code/yugabyte-db/src/yb/gutil/hash/jenkins.cc

Source (jump to first uncovered line)
// Copyright 2011 Google Inc. All Rights Reserved.
//
// The following only applies to changes made to this file as part of YugaByte development.
//
// Portions Copyright (c) YugaByte, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
// in compliance with the License.  You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software distributed under the License
// is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
// or implied.  See the License for the specific language governing permissions and limitations
// under the License.
//
// 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 "yb/gutil/hash/jenkins.h"

#include "yb/gutil/integral_types.h"
#include <glog/logging.h>
#include "yb/gutil/hash/jenkins_lookup2.h"
#include "yb/gutil/macros.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, size_t len, uint32 c) {
  uint32 a, b;
  size_t 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; FALLTHROUGH_INTENDED;
    case 10: c += char2unsigned(s[9]) << 16; FALLTHROUGH_INTENDED;
    case 9 : c += char2unsigned(s[8]) << 8; FALLTHROUGH_INTENDED;
      // 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; FALLTHROUGH_INTENDED;
    case 6 : b += char2unsigned(s[5]) << 8; FALLTHROUGH_INTENDED;
    case 5 : b += char2unsigned(s[4]); FALLTHROUGH_INTENDED;
    case 4 : a += Google1At(s);  break;
    case 3 : a += char2unsigned(s[2]) << 16; FALLTHROUGH_INTENDED;
    case 2 : a += char2unsigned(s[1]) << 8; FALLTHROUGH_INTENDED;
    case 1 : a += char2unsigned(s[0]);
      // case 0 : nothing left to add
  }
  mix(a, b, c);
  return c;
}


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

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

  size_t 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; FALLTHROUGH_INTENDED;
        case 2 : a += char2unsigned(s[1]) << 8; FALLTHROUGH_INTENDED;
        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; FALLTHROUGH_INTENDED;
        case 10: c += char2unsigned(s[9]) << 16; FALLTHROUGH_INTENDED;
        case 9 : c += char2unsigned(s[8]) << 8; FALLTHROUGH_INTENDED;
        case 8 : b += Google1At(s+4);  a += word32AtOffset0;  break;
        case 7 : b += char2unsigned(s[6]) << 16; FALLTHROUGH_INTENDED;
        case 6 : b += char2unsigned(s[5]) << 8; FALLTHROUGH_INTENDED;
        case 5 : b += char2unsigned(s[4]); FALLTHROUGH_INTENDED;
        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; FALLTHROUGH_INTENDED;
      case 10: c += char2unsigned(s[9]) << 16; FALLTHROUGH_INTENDED;
      case 9 : c += char2unsigned(s[8]) << 8; FALLTHROUGH_INTENDED;
      case 8 : b += Google1At(s+4);  a += Google1At(s);  break;
      case 7 : b += char2unsigned(s[6]) << 16; FALLTHROUGH_INTENDED;
      case 6 : b += char2unsigned(s[5]) << 8; FALLTHROUGH_INTENDED;
      case 5 : b += char2unsigned(s[4]); FALLTHROUGH_INTENDED;
      case 4 : a += Google1At(s);  break;
      case 3 : a += char2unsigned(s[2]) << 16; FALLTHROUGH_INTENDED;
      case 2 : a += char2unsigned(s[1]) << 8; FALLTHROUGH_INTENDED;
      case 1 : a += char2unsigned(s[0]);
    }
  }
  mix(a, b, c);
  return c;
}

uint64 Hash64StringWithSeed(const char *s, size_t len, uint64 c) {
  uint64 a, b;
  size_t 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)15.2M ) {
    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; FALLTHROUGH_INTENDED;
    case 22: c += char2unsigned64(s[21]) << 48; FALLTHROUGH_INTENDED;
    case 21: c += char2unsigned64(s[20]) << 40; FALLTHROUGH_INTENDED;
    case 20: c += char2unsigned64(s[19]) << 32; FALLTHROUGH_INTENDED;
    case 19: c += char2unsigned64(s[18]) << 24; FALLTHROUGH_INTENDED;
    case 18: c += char2unsigned64(s[17]) << 16; FALLTHROUGH_INTENDED;
    case 17: c += char2unsigned64(s[16]) << 8; FALLTHROUGH_INTENDED;
      // 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; FALLTHROUGH_INTENDED;
    case 14: b += char2unsigned64(s[13]) << 40; FALLTHROUGH_INTENDED;
    case 13: b += char2unsigned64(s[12]) << 32; FALLTHROUGH_INTENDED;
    case 12: b += char2unsigned64(s[11]) << 24; FALLTHROUGH_INTENDED;
    case 11: b += char2unsigned64(s[10]) << 16; FALLTHROUGH_INTENDED;
    case 10: b += char2unsigned64(s[ 9]) << 8; FALLTHROUGH_INTENDED;
    case  9: b += char2unsigned64(s[ 8]) ; FALLTHROUGH_INTENDED;
    case  8: a += Word64At(s);  break;
    case  7: a += char2unsigned64(s[ 6]) << 48; FALLTHROUGH_INTENDED;
    case  6: a += char2unsigned64(s[ 5]) << 40; FALLTHROUGH_INTENDED;
    case  5: a += char2unsigned64(s[ 4]) << 32; FALLTHROUGH_INTENDED;
    case  4: a += char2unsigned64(s[ 3]) << 24; FALLTHROUGH_INTENDED;
    case  3: a += char2unsigned64(s[ 2]) << 16; FALLTHROUGH_INTENDED;
    case  2: a += char2unsigned64(s[ 1]) << 8; FALLTHROUGH_INTENDED;
    case  1: a += char2unsigned64(s[ 0]);
      // case 0: nothing left to add
  }
  mix(a, b, c);
  return c;
}

YugabyteDB (2.13.1.0-b60, 21121d69985fbf76aa6958d8f04a9bfa936293b5)

Coverage Report

Created: 2022-03-22 16:43

Line	Count	Source (jump to first uncovered line)
1		// Copyright 2011 Google Inc. All Rights Reserved.
2		//
3		// The following only applies to changes made to this file as part of YugaByte development.
4		//
5		// Portions Copyright (c) YugaByte, Inc.
6		//
7		// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
8		// in compliance with the License. You may obtain a copy of the License at
9		//
10		// http://www.apache.org/licenses/LICENSE-2.0
11		//
12		// Unless required by applicable law or agreed to in writing, software distributed under the License
13		// is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
14		// or implied. See the License for the specific language governing permissions and limitations
15		// under the License.
16		//
17		// Contains the legacy Bob Jenkins Lookup2-based hashing routines. These need to
18		// always return the same results as their values have been recorded in various
19		// places and cannot easily be updated.
20		//
21		// Original Author: Sanjay Ghemawat
22		//
23		// This is based on Bob Jenkins newhash function
24		// see: http://burtleburtle.net/bob/hash/evahash.html
25		// According to http://burtleburtle.net/bob/c/lookup2.c,
26		// his implementation is public domain.
27		//
28		// The implementation here is backwards compatible with the google1
29		// implementation. The google1 implementation used a 'signed char *'
30		// to load words from memory a byte at a time. See gwshash.cc for an
31		// implementation that is compatible with Bob Jenkins' lookup2.c.
32
33		#include "yb/gutil/hash/jenkins.h"
34
35		#include "yb/gutil/integral_types.h"
36		#include <glog/logging.h>
37		#include "yb/gutil/hash/jenkins_lookup2.h"
38		#include "yb/gutil/macros.h"
39
40	180M	static inline uint32 char2unsigned(char c) {
41	180M	return static_cast<uint32>(static_cast<unsigned char>(c));
42	180M	}
43
44	255M	static inline uint64 char2unsigned64(char c) {
45	255M	return static_cast<uint64>(static_cast<unsigned char>(c));
46	255M	}
47
48	0	uint32 Hash32StringWithSeedReferenceImplementation(const char *s, size_t len, uint32 c) {
49	0	uint32 a, b;
50	0	size_t keylen;
51
52	0	a = b = 0x9e3779b9UL; // the golden ratio; an arbitrary value
53
54	0	for ( keylen = len; keylen >= 3*sizeof(a);
55	0	keylen -= static_cast<uint32>(3sizeof(a)), s += 3sizeof(a) ) {
56	0	a += Google1At(s);
57	0	b += Google1At(s + sizeof(a));
58	0	c += Google1At(s + sizeof(a)*2);
59	0	mix(a, b, c);
60	0	}
61
62	0	c += len;
63	0	switch ( keylen ) { // deal with rest. Cases fall through
64	0	case 11: c += char2unsigned(s[10]) << 24; FALLTHROUGH_INTENDED;
65	0	case 10: c += char2unsigned(s[9]) << 16; FALLTHROUGH_INTENDED;
66	0	case 9 : c += char2unsigned(s[8]) << 8; FALLTHROUGH_INTENDED;
67		// the first byte of c is reserved for the length
68	0	case 8 : b += Google1At(s+4); a += Google1At(s); break;
69	0	case 7 : b += char2unsigned(s[6]) << 16; FALLTHROUGH_INTENDED;
70	0	case 6 : b += char2unsigned(s[5]) << 8; FALLTHROUGH_INTENDED;
71	0	case 5 : b += char2unsigned(s[4]); FALLTHROUGH_INTENDED;
72	0	case 4 : a += Google1At(s); break;
73	0	case 3 : a += char2unsigned(s[2]) << 16; FALLTHROUGH_INTENDED;
74	0	case 2 : a += char2unsigned(s[1]) << 8; FALLTHROUGH_INTENDED;
75	0	case 1 : a += char2unsigned(s[0]);
76		// case 0 : nothing left to add
77	0	}
78	0	mix(a, b, c);
79	0	return c;
80	0	}
81
82
83	124M	uint32 Hash32StringWithSeed(const char *s, size_t len, uint32 c) {
84	124M	uint32 a, b;
85
86	124M	a = b = 0x9e3779b9UL; // the golden ratio; an arbitrary value
87
88	124M	size_t keylen = len;
89	124M	if (keylen >= 4 * sizeof(a)) {
90	9.16M	uint32 word32AtOffset0 = Google1At(s);
91	9.18M	do {
92	9.18M	a += word32AtOffset0;
93	9.18M	b += Google1At(s + sizeof(a));
94	9.18M	c += Google1At(s + sizeof(a) * 2);
95	9.18M	s += 3 * sizeof(a);
96	9.18M	word32AtOffset0 = Google1At(s);
97	9.18M	mix(a, b, c);
98	9.18M	keylen -= 3 * static_cast<uint32>(sizeof(a));
99	9.18M	} while (keylen >= 4 * sizeof(a));
100	9.16M	if (keylen >= 3 * sizeof(a)) {
101	515k	a += word32AtOffset0;
102	515k	b += Google1At(s + sizeof(a));
103	515k	c += Google1At(s + sizeof(a) * 2);
104	515k	s += 3 * sizeof(a);
105	515k	mix(a, b, c);
106	515k	keylen -= 3 * static_cast<uint32>(sizeof(a));
107	515k	DCHECK_LT(keylen, sizeof(a));
108	515k	c += len;
109	515k	switch ( keylen ) { // deal with rest. Cases fall through
110	238k	case 3 : a += char2unsigned(s[2]) << 16; FALLTHROUGH_INTENDED;
111	477k	case 2 : a += char2unsigned(s[1]) << 8; FALLTHROUGH_INTENDED;
112	477k	case 1 : a += char2unsigned(s[0]);
113	515k	}
114	8.64M	} else {
115	8.64M	DCHECK(sizeof(a) <= keylen && keylen < 3 * sizeof(a));
116	8.64M	c += len;
117	8.64M	switch ( keylen ) { // deal with rest. Cases fall through
118	269k	case 11: c += char2unsigned(s[10]) << 24; FALLTHROUGH_INTENDED;
119	527k	case 10: c += char2unsigned(s[9]) << 16; FALLTHROUGH_INTENDED;
120	2.36M	case 9 : c += char2unsigned(s[8]) << 8; FALLTHROUGH_INTENDED;
121	3.84M	case 8 : b += Google1At(s+4); a += word32AtOffset0; break;
122	364k	case 7 : b += char2unsigned(s[6]) << 16; FALLTHROUGH_INTENDED;
123	1.02M	case 6 : b += char2unsigned(s[5]) << 8; FALLTHROUGH_INTENDED;
124	2.15M	case 5 : b += char2unsigned(s[4]); FALLTHROUGH_INTENDED;
125	4.81M	case 4 : a += word32AtOffset0; break;
126	8.64M	}
127	8.64M	}
128	115M	} else {
129	115M	if (keylen >= 3 * sizeof(a)) {
130	20.3M	a += Google1At(s);
131	20.3M	b += Google1At(s + sizeof(a));
132	20.3M	c += Google1At(s + sizeof(a) * 2);
133	20.3M	s += 3 * sizeof(a);
134	20.3M	mix(a, b, c);
135	20.3M	keylen -= 3 * static_cast<uint32>(sizeof(a));
136	20.3M	}
137	115M	c += len;
138	115M	switch ( keylen ) { // deal with rest. Cases fall through
139	8.76M	case 11: c += char2unsigned(s[10]) << 24; FALLTHROUGH_INTENDED;
140	17.9M	case 10: c += char2unsigned(s[9]) << 16; FALLTHROUGH_INTENDED;
141	29.6M	case 9 : c += char2unsigned(s[8]) << 8; FALLTHROUGH_INTENDED;
142	38.9M	case 8 : b += Google1At(s+4); a += Google1At(s); break;
143	8.16M	case 7 : b += char2unsigned(s[6]) << 16; FALLTHROUGH_INTENDED;
144	12.5M	case 6 : b += char2unsigned(s[5]) << 8; FALLTHROUGH_INTENDED;
145	29.0M	case 5 : b += char2unsigned(s[4]); FALLTHROUGH_INTENDED;
146	35.1M	case 4 : a += Google1At(s); break;
147	7.67M	case 3 : a += char2unsigned(s[2]) << 16; FALLTHROUGH_INTENDED;
148	23.7M	case 2 : a += char2unsigned(s[1]) << 8; FALLTHROUGH_INTENDED;
149	35.7M	case 1 : a += char2unsigned(s[0]);
150	115M	}
151	115M	}
152	124M	mix(a, b, c);
153	124M	return c;
154	124M	}
155
156	58.5M	uint64 Hash64StringWithSeed(const char *s, size_t len, uint64 c) {
157	58.5M	uint64 a, b;
158	58.5M	size_t keylen;
159
160	58.5M	a = b = GG_ULONGLONG(0xe08c1d668b756f82); // the golden ratio; an arbitrary value
161
162	73.8M	for ( keylen = len; keylen >= 3 * sizeof(a);
163	58.5M	keylen -= 3 * static_cast<uint32>(sizeof(a)), s += 3 * sizeof(a)15.2M ) {
164	15.2M	a += Word64At(s);
165	15.2M	b += Word64At(s + sizeof(a));
166	15.2M	c += Word64At(s + sizeof(a) * 2);
167	15.2M	mix(a, b, c);
168	15.2M	}
169
170	58.5M	c += len;
171	58.5M	switch ( keylen ) { // deal with rest. Cases fall through
172	1.74k	case 23: c += char2unsigned64(s[22]) << 56; FALLTHROUGH_INTENDED;
173	2.44k	case 22: c += char2unsigned64(s[21]) << 48; FALLTHROUGH_INTENDED;
174	47.2k	case 21: c += char2unsigned64(s[20]) << 40; FALLTHROUGH_INTENDED;
175	128k	case 20: c += char2unsigned64(s[19]) << 32; FALLTHROUGH_INTENDED;
176	143k	case 19: c += char2unsigned64(s[18]) << 24; FALLTHROUGH_INTENDED;
177	192k	case 18: c += char2unsigned64(s[17]) << 16; FALLTHROUGH_INTENDED;
178	7.98M	case 17: c += char2unsigned64(s[16]) << 8; FALLTHROUGH_INTENDED;
179		// the first byte of c is reserved for the length
180	13.6M	case 16: b += Word64At(s+8); a += Word64At(s); break;
181	2.23M	case 15: b += char2unsigned64(s[14]) << 48; FALLTHROUGH_INTENDED;
182	33.9M	case 14: b += char2unsigned64(s[13]) << 40; FALLTHROUGH_INTENDED;
183	33.9M	case 13: b += char2unsigned64(s[12]) << 32; FALLTHROUGH_INTENDED;
184	34.1M	case 12: b += char2unsigned64(s[11]) << 24; FALLTHROUGH_INTENDED;
185	34.3M	case 11: b += char2unsigned64(s[10]) << 16; FALLTHROUGH_INTENDED;
186	34.4M	case 10: b += char2unsigned64(s[ 9]) << 8; FALLTHROUGH_INTENDED;
187	34.4M	case 9: b += char2unsigned64(s[ 8]) ; FALLTHROUGH_INTENDED;
188	34.9M	case 8: a += Word64At(s); break;
189	62.1k	case 7: a += char2unsigned64(s[ 6]) << 48; FALLTHROUGH_INTENDED;
190	72.0k	case 6: a += char2unsigned64(s[ 5]) << 40; FALLTHROUGH_INTENDED;
191	176k	case 5: a += char2unsigned64(s[ 4]) << 32; FALLTHROUGH_INTENDED;
192	9.76M	case 4: a += char2unsigned64(s[ 3]) << 24; FALLTHROUGH_INTENDED;
193	9.78M	case 3: a += char2unsigned64(s[ 2]) << 16; FALLTHROUGH_INTENDED;
194	9.96M	case 2: a += char2unsigned64(s[ 1]) << 8; FALLTHROUGH_INTENDED;
195	9.98M	case 1: a += char2unsigned64(s[ 0]);
196		// case 0: nothing left to add
197	58.5M	}
198	58.5M	mix(a, b, c);
199	58.5M	return c;
200	58.5M	}