/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) ) {
    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.0.0-b42, bfc6a6643e7399ac8a0e81d06a3ee6d6571b33ab)

Coverage Report

Created: 2022-03-09 17:30

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	97.4M	static inline uint32 char2unsigned(char c) {
41	97.4M	return static_cast<uint32>(static_cast<unsigned char>(c));
42	97.4M	}
43
44	47.5M	static inline uint64 char2unsigned64(char c) {
45	47.5M	return static_cast<uint64>(static_cast<unsigned char>(c));
46	47.5M	}
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	70.2M	uint32 Hash32StringWithSeed(const char *s, size_t len, uint32 c) {
84	70.2M	uint32 a, b;
85
86	70.2M	a = b = 0x9e3779b9UL; // the golden ratio; an arbitrary value
87
88	70.2M	size_t keylen = len;
89	70.2M	if (keylen >= 4 * sizeof(a)) {
90	6.95M	uint32 word32AtOffset0 = Google1At(s);
91	6.96M	do {
92	6.96M	a += word32AtOffset0;
93	6.96M	b += Google1At(s + sizeof(a));
94	6.96M	c += Google1At(s + sizeof(a) * 2);
95	6.96M	s += 3 * sizeof(a);
96	6.96M	word32AtOffset0 = Google1At(s);
97	6.96M	mix(a, b, c);
98	6.96M	keylen -= 3 * static_cast<uint32>(sizeof(a));
99	6.96M	} while (keylen >= 4 * sizeof(a));
100	6.95M	if (keylen >= 3 * sizeof(a)) {
101	462k	a += word32AtOffset0;
102	462k	b += Google1At(s + sizeof(a));
103	462k	c += Google1At(s + sizeof(a) * 2);
104	462k	s += 3 * sizeof(a);
105	462k	mix(a, b, c);
106	462k	keylen -= 3 * static_cast<uint32>(sizeof(a));
107	462k	DCHECK_LT(keylen, sizeof(a));
108	462k	c += len;
109	462k	switch ( keylen ) { // deal with rest. Cases fall through
110	222k	case 3 : a += char2unsigned(s[2]) << 16; FALLTHROUGH_INTENDED;
111	444k	case 2 : a += char2unsigned(s[1]) << 8; FALLTHROUGH_INTENDED;
112	444k	case 1 : a += char2unsigned(s[0]);
113	462k	}
114	6.49M	} else {
115	6.49M	DCHECK(sizeof(a) <= keylen && keylen < 3 * sizeof(a));
116	6.49M	c += len;
117	6.49M	switch ( keylen ) { // deal with rest. Cases fall through
118	263k	case 11: c += char2unsigned(s[10]) << 24; FALLTHROUGH_INTENDED;
119	494k	case 10: c += char2unsigned(s[9]) << 16; FALLTHROUGH_INTENDED;
120	1.00M	case 9 : c += char2unsigned(s[8]) << 8; FALLTHROUGH_INTENDED;
121	1.97M	case 8 : b += Google1At(s+4); a += word32AtOffset0; break;
122	217k	case 7 : b += char2unsigned(s[6]) << 16; FALLTHROUGH_INTENDED;
123	858k	case 6 : b += char2unsigned(s[5]) << 8; FALLTHROUGH_INTENDED;
124	1.91M	case 5 : b += char2unsigned(s[4]); FALLTHROUGH_INTENDED;
125	4.51M	case 4 : a += word32AtOffset0; break;
126	63.2M	}
127	63.2M	}
128	63.2M	} else {
129	63.2M	if (keylen >= 3 * sizeof(a)) {
130	12.2M	a += Google1At(s);
131	12.2M	b += Google1At(s + sizeof(a));
132	12.2M	c += Google1At(s + sizeof(a) * 2);
133	12.2M	s += 3 * sizeof(a);
134	12.2M	mix(a, b, c);
135	12.2M	keylen -= 3 * static_cast<uint32>(sizeof(a));
136	12.2M	}
137	63.2M	c += len;
138	63.2M	switch ( keylen ) { // deal with rest. Cases fall through
139	6.09M	case 11: c += char2unsigned(s[10]) << 24; FALLTHROUGH_INTENDED;
140	11.6M	case 10: c += char2unsigned(s[9]) << 16; FALLTHROUGH_INTENDED;
141	17.2M	case 9 : c += char2unsigned(s[8]) << 8; FALLTHROUGH_INTENDED;
142	22.6M	case 8 : b += Google1At(s+4); a += Google1At(s); break;
143	3.42M	case 7 : b += char2unsigned(s[6]) << 16; FALLTHROUGH_INTENDED;
144	5.32M	case 6 : b += char2unsigned(s[5]) << 8; FALLTHROUGH_INTENDED;
145	13.5M	case 5 : b += char2unsigned(s[4]); FALLTHROUGH_INTENDED;
146	19.2M	case 4 : a += Google1At(s); break;
147	3.51M	case 3 : a += char2unsigned(s[2]) << 16; FALLTHROUGH_INTENDED;
148	12.5M	case 2 : a += char2unsigned(s[1]) << 8; FALLTHROUGH_INTENDED;
149	18.3M	case 1 : a += char2unsigned(s[0]);
150	63.2M	}
151	63.2M	}
152	70.2M	mix(a, b, c);
153	70.2M	return c;
154	70.2M	}
155
156	16.7M	uint64 Hash64StringWithSeed(const char *s, size_t len, uint64 c) {
157	16.7M	uint64 a, b;
158	16.7M	size_t keylen;
159
160	16.7M	a = b = GG_ULONGLONG(0xe08c1d668b756f82); // the golden ratio; an arbitrary value
161
162	27.3M	for ( keylen = len; keylen >= 3 * sizeof(a);
163	10.5M	keylen -= 3 * static_cast<uint32>(sizeof(a)), s += 3 * sizeof(a) ) {
164	10.5M	a += Word64At(s);
165	10.5M	b += Word64At(s + sizeof(a));
166	10.5M	c += Word64At(s + sizeof(a) * 2);
167	10.5M	mix(a, b, c);
168	10.5M	}
169
170	16.7M	c += len;
171	16.7M	switch ( keylen ) { // deal with rest. Cases fall through
172	64	case 23: c += char2unsigned64(s[22]) << 56; FALLTHROUGH_INTENDED;
173	93	case 22: c += char2unsigned64(s[21]) << 48; FALLTHROUGH_INTENDED;
174	8.29k	case 21: c += char2unsigned64(s[20]) << 40; FALLTHROUGH_INTENDED;
175	9.17k	case 20: c += char2unsigned64(s[19]) << 32; FALLTHROUGH_INTENDED;
176	11.2k	case 19: c += char2unsigned64(s[18]) << 24; FALLTHROUGH_INTENDED;
177	18.6k	case 18: c += char2unsigned64(s[17]) << 16; FALLTHROUGH_INTENDED;
178	3.88M	case 17: c += char2unsigned64(s[16]) << 8; FALLTHROUGH_INTENDED;
179		// the first byte of c is reserved for the length
180	7.28M	case 16: b += Word64At(s+8); a += Word64At(s); break;
181	1.45M	case 15: b += char2unsigned64(s[14]) << 48; FALLTHROUGH_INTENDED;
182	3.13M	case 14: b += char2unsigned64(s[13]) << 40; FALLTHROUGH_INTENDED;
183	3.14M	case 13: b += char2unsigned64(s[12]) << 32; FALLTHROUGH_INTENDED;
184	3.28M	case 12: b += char2unsigned64(s[11]) << 24; FALLTHROUGH_INTENDED;
185	3.52M	case 11: b += char2unsigned64(s[10]) << 16; FALLTHROUGH_INTENDED;
186	3.57M	case 10: b += char2unsigned64(s[ 9]) << 8; FALLTHROUGH_INTENDED;
187	3.61M	case 9: b += char2unsigned64(s[ 8]) ; FALLTHROUGH_INTENDED;
188	4.04M	case 8: a += Word64At(s); break;
189	47.8k	case 7: a += char2unsigned64(s[ 6]) << 48; FALLTHROUGH_INTENDED;
190	51.1k	case 6: a += char2unsigned64(s[ 5]) << 40; FALLTHROUGH_INTENDED;
191	122k	case 5: a += char2unsigned64(s[ 4]) << 32; FALLTHROUGH_INTENDED;
192	5.38M	case 4: a += char2unsigned64(s[ 3]) << 24; FALLTHROUGH_INTENDED;
193	5.38M	case 3: a += char2unsigned64(s[ 2]) << 16; FALLTHROUGH_INTENDED;
194	5.44M	case 2: a += char2unsigned64(s[ 1]) << 8; FALLTHROUGH_INTENDED;
195	5.46M	case 1: a += char2unsigned64(s[ 0]);
196		// case 0: nothing left to add
197	16.7M	}
198	16.7M	mix(a, b, c);
199	16.7M	return c;
200	16.7M	}