OR-Tools  8.2
thorough_hash.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #ifndef OR_TOOLS_BASE_THOROUGH_HASH_H_
15 #define OR_TOOLS_BASE_THOROUGH_HASH_H_
16 
18 
19 namespace operations_research {
20 inline uint64 MixTwoUInt64(uint64 fp1, uint64 fp2) {
21  // Two big prime numbers.
22  const uint64 kMul1 = 0xc6a4a7935bd1e995ULL;
23  const uint64 kMul2 = 0x228876a7198b743ULL;
24  uint64 a = fp1 * kMul1 + fp2 * kMul2;
25  // Note: The following line also makes sure we never return 0 or 1, because we
26  // will only add something to 'a' if there are any MSBs (the remaining bits
27  // after the shift) being 0, in which case wrapping around would not happen.
28  return a + (~a >> 47);
29 }
30 
31 // This should be better (collision-wise) than the default hash<string>, without
32 // being much slower. It never returns 0 or 1.
33 inline uint64 ThoroughHash(const char* bytes, size_t len) {
34  // Some big prime numer.
35  uint64 fp = 0xa5b85c5e198ed849ULL;
36  const char* end = bytes + len;
37  while (bytes + 8 <= end) {
38  fp = MixTwoUInt64(fp, *(reinterpret_cast<const uint64*>(bytes)));
39  bytes += 8;
40  }
41  // Note: we don't care about "consistency" (little or big endian) between
42  // the bulk and the suffix of the message.
43  uint64 last_bytes = 0;
44  while (bytes < end) {
45  last_bytes += *bytes;
46  last_bytes <<= 8;
47  bytes++;
48  }
49  return MixTwoUInt64(fp, last_bytes);
50 }
51 } // namespace operations_research
52 
53 #endif // OR_TOOLS_BASE_THOROUGH_HASH_H_
uint64_t uint64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
uint64 MixTwoUInt64(uint64 fp1, uint64 fp2)
Definition: thorough_hash.h:20
uint64 ThoroughHash(const char *bytes, size_t len)
Definition: thorough_hash.h:33