1 // Copyright 2010-2021 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
17 #include "ortools/base/integral_types.h"
18
19 namespace operations_research {
MixTwoUInt64(uint64_t fp1,uint64_t fp2)20 inline uint64_t MixTwoUInt64(uint64_t fp1, uint64_t fp2) {
21 // Two big prime numbers.
22 const uint64_t kMul1 = 0xc6a4a7935bd1e995ULL;
23 const uint64_t kMul2 = 0x228876a7198b743ULL;
24 uint64_t 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.
ThoroughHash(const char * bytes,size_t len)33 inline uint64_t ThoroughHash(const char* bytes, size_t len) {
34 // Some big prime numer.
35 uint64_t fp = 0xa5b85c5e198ed849ULL;
36 const char* end = bytes + len;
37 while (bytes + 8 <= end) {
38 fp = MixTwoUInt64(fp, *(reinterpret_cast<const uint64_t*>(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_t 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_
54