1 | /* Copyright 2015 The TensorFlow Authors. All Rights Reserved. |
---|---|
2 | |
3 | Licensed under the Apache License, Version 2.0 (the "License"); |
4 | you may not use this file except in compliance with the License. |
5 | You may obtain a copy of the License at |
6 | |
7 | http://www.apache.org/licenses/LICENSE-2.0 |
8 | |
9 | Unless required by applicable law or agreed to in writing, software |
10 | distributed under the License is distributed on an "AS IS" BASIS, |
11 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 | See the License for the specific language governing permissions and |
13 | limitations under the License. |
14 | ==============================================================================*/ |
15 | |
16 | #include "tensorflow/tsl/platform/hash.h" |
17 | |
18 | #include <string.h> |
19 | |
20 | #include "tensorflow/tsl/platform/macros.h" |
21 | #include "tensorflow/tsl/platform/raw_coding.h" |
22 | #include "tensorflow/tsl/platform/types.h" |
23 | |
24 | namespace tsl { |
25 | |
26 | // 0xff is in case char is signed. |
27 | static inline uint32 ByteAs32(char c) { return static_cast<uint32>(c) & 0xff; } |
28 | static inline uint64 ByteAs64(char c) { return static_cast<uint64>(c) & 0xff; } |
29 | |
30 | uint32 Hash32(const char* data, size_t n, uint32 seed) { |
31 | // 'm' and 'r' are mixing constants generated offline. |
32 | // They're not really 'magic', they just happen to work well. |
33 | |
34 | const uint32 m = 0x5bd1e995; |
35 | const int r = 24; |
36 | |
37 | // Initialize the hash to a 'random' value |
38 | uint32 h = seed ^ n; |
39 | |
40 | // Mix 4 bytes at a time into the hash |
41 | while (n >= 4) { |
42 | uint32 k = core::DecodeFixed32(data); |
43 | |
44 | k *= m; |
45 | k ^= k >> r; |
46 | k *= m; |
47 | |
48 | h *= m; |
49 | h ^= k; |
50 | |
51 | data += 4; |
52 | n -= 4; |
53 | } |
54 | |
55 | // Handle the last few bytes of the input array |
56 | |
57 | switch (n) { |
58 | case 3: |
59 | h ^= ByteAs32(data[2]) << 16; |
60 | TF_FALLTHROUGH_INTENDED; |
61 | case 2: |
62 | h ^= ByteAs32(data[1]) << 8; |
63 | TF_FALLTHROUGH_INTENDED; |
64 | case 1: |
65 | h ^= ByteAs32(data[0]); |
66 | h *= m; |
67 | } |
68 | |
69 | // Do a few final mixes of the hash to ensure the last few |
70 | // bytes are well-incorporated. |
71 | |
72 | h ^= h >> 13; |
73 | h *= m; |
74 | h ^= h >> 15; |
75 | |
76 | return h; |
77 | } |
78 | |
79 | uint64 Hash64(const char* data, size_t n, uint64 seed) { |
80 | const uint64 m = 0xc6a4a7935bd1e995; |
81 | const int r = 47; |
82 | |
83 | uint64 h = seed ^ (n * m); |
84 | |
85 | while (n >= 8) { |
86 | uint64 k = core::DecodeFixed64(data); |
87 | data += 8; |
88 | n -= 8; |
89 | |
90 | k *= m; |
91 | k ^= k >> r; |
92 | k *= m; |
93 | |
94 | h ^= k; |
95 | h *= m; |
96 | } |
97 | |
98 | switch (n) { |
99 | case 7: |
100 | h ^= ByteAs64(data[6]) << 48; |
101 | TF_FALLTHROUGH_INTENDED; |
102 | case 6: |
103 | h ^= ByteAs64(data[5]) << 40; |
104 | TF_FALLTHROUGH_INTENDED; |
105 | case 5: |
106 | h ^= ByteAs64(data[4]) << 32; |
107 | TF_FALLTHROUGH_INTENDED; |
108 | case 4: |
109 | h ^= ByteAs64(data[3]) << 24; |
110 | TF_FALLTHROUGH_INTENDED; |
111 | case 3: |
112 | h ^= ByteAs64(data[2]) << 16; |
113 | TF_FALLTHROUGH_INTENDED; |
114 | case 2: |
115 | h ^= ByteAs64(data[1]) << 8; |
116 | TF_FALLTHROUGH_INTENDED; |
117 | case 1: |
118 | h ^= ByteAs64(data[0]); |
119 | h *= m; |
120 | } |
121 | |
122 | h ^= h >> r; |
123 | h *= m; |
124 | h ^= h >> r; |
125 | |
126 | return h; |
127 | } |
128 | |
129 | } // namespace tsl |
130 |