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
19namespace operations_research {
20inline 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.
33inline 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 ThoroughHash(const char *bytes, size_t len)
Definition: thorough_hash.h:33
uint64 MixTwoUInt64(uint64 fp1, uint64 fp2)
Definition: thorough_hash.h:20