1/* Copyright 2015 The TensorFlow Authors. All Rights Reserved.
2
3Licensed under the Apache License, Version 2.0 (the "License");
4you may not use this file except in compliance with the License.
5You may obtain a copy of the License at
6
7 http://www.apache.org/licenses/LICENSE-2.0
8
9Unless required by applicable law or agreed to in writing, software
10distributed under the License is distributed on an "AS IS" BASIS,
11WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12See the License for the specific language governing permissions and
13limitations 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
24namespace tsl {
25
26// 0xff is in case char is signed.
27static inline uint32 ByteAs32(char c) { return static_cast<uint32>(c) & 0xff; }
28static inline uint64 ByteAs64(char c) { return static_cast<uint64>(c) & 0xff; }
29
30uint32 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
79uint64 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