|
111
|
1 // Definition of _Hash_bytes. -*- C++ -*-
|
|
|
2
|
|
145
|
3 // Copyright (C) 2010-2020 Free Software Foundation, Inc.
|
|
111
|
4 //
|
|
|
5 // This file is part of the GNU ISO C++ Library. This library is free
|
|
|
6 // software; you can redistribute it and/or modify it under the
|
|
|
7 // terms of the GNU General Public License as published by the
|
|
|
8 // Free Software Foundation; either version 3, or (at your option)
|
|
|
9 // any later version.
|
|
|
10
|
|
|
11 // This library is distributed in the hope that it will be useful,
|
|
|
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
14 // GNU General Public License for more details.
|
|
|
15
|
|
|
16 // Under Section 7 of GPL version 3, you are granted additional
|
|
|
17 // permissions described in the GCC Runtime Library Exception, version
|
|
|
18 // 3.1, as published by the Free Software Foundation.
|
|
|
19
|
|
|
20 // You should have received a copy of the GNU General Public License and
|
|
|
21 // a copy of the GCC Runtime Library Exception along with this program;
|
|
|
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
|
|
|
23 // <http://www.gnu.org/licenses/>.
|
|
|
24
|
|
|
25 // This file defines Hash_bytes, a primitive used for defining hash
|
|
|
26 // functions. Based on public domain MurmurHashUnaligned2, by Austin
|
|
|
27 // Appleby. http://murmurhash.googlepages.com/
|
|
|
28
|
|
|
29 // This file also defines _Fnv_hash_bytes, another primitive with
|
|
|
30 // exactly the same interface but using a different hash algorithm,
|
|
|
31 // Fowler / Noll / Vo (FNV) Hash (type FNV-1a). The Murmur hash
|
|
|
32 // function apears to be better in both speed and hash quality, and
|
|
|
33 // FNV is provided primarily for backward compatibility.
|
|
|
34
|
|
|
35 #include <bits/hash_bytes.h>
|
|
|
36
|
|
|
37 namespace
|
|
|
38 {
|
|
|
39 inline std::size_t
|
|
|
40 unaligned_load(const char* p)
|
|
|
41 {
|
|
|
42 std::size_t result;
|
|
|
43 __builtin_memcpy(&result, p, sizeof(result));
|
|
|
44 return result;
|
|
|
45 }
|
|
|
46
|
|
|
47 #if __SIZEOF_SIZE_T__ == 8
|
|
|
48 // Loads n bytes, where 1 <= n < 8.
|
|
|
49 inline std::size_t
|
|
|
50 load_bytes(const char* p, int n)
|
|
|
51 {
|
|
|
52 std::size_t result = 0;
|
|
|
53 --n;
|
|
|
54 do
|
|
|
55 result = (result << 8) + static_cast<unsigned char>(p[n]);
|
|
|
56 while (--n >= 0);
|
|
|
57 return result;
|
|
|
58 }
|
|
|
59
|
|
|
60 inline std::size_t
|
|
|
61 shift_mix(std::size_t v)
|
|
|
62 { return v ^ (v >> 47);}
|
|
|
63 #endif
|
|
|
64 }
|
|
|
65
|
|
|
66 namespace std
|
|
|
67 {
|
|
|
68 _GLIBCXX_BEGIN_NAMESPACE_VERSION
|
|
|
69
|
|
|
70 #if __SIZEOF_SIZE_T__ == 4
|
|
|
71
|
|
|
72 // Implementation of Murmur hash for 32-bit size_t.
|
|
|
73 size_t
|
|
|
74 _Hash_bytes(const void* ptr, size_t len, size_t seed)
|
|
|
75 {
|
|
|
76 const size_t m = 0x5bd1e995;
|
|
|
77 size_t hash = seed ^ len;
|
|
|
78 const char* buf = static_cast<const char*>(ptr);
|
|
|
79
|
|
|
80 // Mix 4 bytes at a time into the hash.
|
|
|
81 while(len >= 4)
|
|
|
82 {
|
|
|
83 size_t k = unaligned_load(buf);
|
|
|
84 k *= m;
|
|
|
85 k ^= k >> 24;
|
|
|
86 k *= m;
|
|
|
87 hash *= m;
|
|
|
88 hash ^= k;
|
|
|
89 buf += 4;
|
|
|
90 len -= 4;
|
|
|
91 }
|
|
|
92
|
|
|
93 // Handle the last few bytes of the input array.
|
|
|
94 switch(len)
|
|
|
95 {
|
|
|
96 case 3:
|
|
|
97 hash ^= static_cast<unsigned char>(buf[2]) << 16;
|
|
|
98 [[gnu::fallthrough]];
|
|
|
99 case 2:
|
|
|
100 hash ^= static_cast<unsigned char>(buf[1]) << 8;
|
|
|
101 [[gnu::fallthrough]];
|
|
|
102 case 1:
|
|
|
103 hash ^= static_cast<unsigned char>(buf[0]);
|
|
|
104 hash *= m;
|
|
|
105 };
|
|
|
106
|
|
|
107 // Do a few final mixes of the hash.
|
|
|
108 hash ^= hash >> 13;
|
|
|
109 hash *= m;
|
|
|
110 hash ^= hash >> 15;
|
|
|
111 return hash;
|
|
|
112 }
|
|
|
113
|
|
|
114 // Implementation of FNV hash for 32-bit size_t.
|
|
|
115 // N.B. This function should work on unsigned char, otherwise it does not
|
|
|
116 // correctly implement the FNV-1a algorithm (see PR59406).
|
|
|
117 // The existing behaviour is retained for backwards compatibility.
|
|
|
118 size_t
|
|
|
119 _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash)
|
|
|
120 {
|
|
|
121 const char* cptr = static_cast<const char*>(ptr);
|
|
|
122 for (; len; --len)
|
|
|
123 {
|
|
|
124 hash ^= static_cast<size_t>(*cptr++);
|
|
|
125 hash *= static_cast<size_t>(16777619UL);
|
|
|
126 }
|
|
|
127 return hash;
|
|
|
128 }
|
|
|
129
|
|
|
130 #elif __SIZEOF_SIZE_T__ == 8
|
|
|
131
|
|
|
132 // Implementation of Murmur hash for 64-bit size_t.
|
|
|
133 size_t
|
|
|
134 _Hash_bytes(const void* ptr, size_t len, size_t seed)
|
|
|
135 {
|
|
|
136 static const size_t mul = (((size_t) 0xc6a4a793UL) << 32UL)
|
|
|
137 + (size_t) 0x5bd1e995UL;
|
|
|
138 const char* const buf = static_cast<const char*>(ptr);
|
|
|
139
|
|
|
140 // Remove the bytes not divisible by the sizeof(size_t). This
|
|
|
141 // allows the main loop to process the data as 64-bit integers.
|
|
145
|
142 const size_t len_aligned = len & ~(size_t)0x7;
|
|
111
|
143 const char* const end = buf + len_aligned;
|
|
|
144 size_t hash = seed ^ (len * mul);
|
|
|
145 for (const char* p = buf; p != end; p += 8)
|
|
|
146 {
|
|
|
147 const size_t data = shift_mix(unaligned_load(p) * mul) * mul;
|
|
|
148 hash ^= data;
|
|
|
149 hash *= mul;
|
|
|
150 }
|
|
|
151 if ((len & 0x7) != 0)
|
|
|
152 {
|
|
|
153 const size_t data = load_bytes(end, len & 0x7);
|
|
|
154 hash ^= data;
|
|
|
155 hash *= mul;
|
|
|
156 }
|
|
|
157 hash = shift_mix(hash) * mul;
|
|
|
158 hash = shift_mix(hash);
|
|
|
159 return hash;
|
|
|
160 }
|
|
|
161
|
|
|
162 // Implementation of FNV hash for 64-bit size_t.
|
|
|
163 // N.B. This function should work on unsigned char, otherwise it does not
|
|
|
164 // correctly implement the FNV-1a algorithm (see PR59406).
|
|
|
165 // The existing behaviour is retained for backwards compatibility.
|
|
|
166 size_t
|
|
|
167 _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash)
|
|
|
168 {
|
|
|
169 const char* cptr = static_cast<const char*>(ptr);
|
|
|
170 for (; len; --len)
|
|
|
171 {
|
|
|
172 hash ^= static_cast<size_t>(*cptr++);
|
|
|
173 hash *= static_cast<size_t>(1099511628211ULL);
|
|
|
174 }
|
|
|
175 return hash;
|
|
|
176 }
|
|
|
177
|
|
|
178 #else
|
|
|
179
|
|
|
180 // Dummy hash implementation for unusual sizeof(size_t).
|
|
|
181 size_t
|
|
|
182 _Hash_bytes(const void* ptr, size_t len, size_t seed)
|
|
|
183 {
|
|
|
184 size_t hash = seed;
|
|
|
185 const char* cptr = reinterpret_cast<const char*>(ptr);
|
|
|
186 for (; len; --len)
|
|
|
187 hash = (hash * 131) + *cptr++;
|
|
|
188 return hash;
|
|
|
189 }
|
|
|
190
|
|
|
191 size_t
|
|
|
192 _Fnv_hash_bytes(const void* ptr, size_t len, size_t seed)
|
|
|
193 { return _Hash_bytes(ptr, len, seed); }
|
|
|
194
|
|
|
195 #endif /* __SIZEOF_SIZE_T__ */
|
|
|
196
|
|
|
197 _GLIBCXX_END_NAMESPACE_VERSION
|
|
|
198 } // namespace
|
