]>
Commit | Line | Data |
---|---|---|
1 | // Definition of _Hash_bytes. -*- C++ -*- | |
2 | ||
3 | // Copyright (C) 2010-2016 Free Software Foundation, Inc. | |
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 | size_t | |
116 | _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash) | |
117 | { | |
118 | const char* cptr = static_cast<const char*>(ptr); | |
119 | for (; len; --len) | |
120 | { | |
121 | hash ^= static_cast<size_t>(*cptr++); | |
122 | hash *= static_cast<size_t>(16777619UL); | |
123 | } | |
124 | return hash; | |
125 | } | |
126 | ||
127 | #elif __SIZEOF_SIZE_T__ == 8 | |
128 | ||
129 | // Implementation of Murmur hash for 64-bit size_t. | |
130 | size_t | |
131 | _Hash_bytes(const void* ptr, size_t len, size_t seed) | |
132 | { | |
133 | static const size_t mul = (((size_t) 0xc6a4a793UL) << 32UL) | |
134 | + (size_t) 0x5bd1e995UL; | |
135 | const char* const buf = static_cast<const char*>(ptr); | |
136 | ||
137 | // Remove the bytes not divisible by the sizeof(size_t). This | |
138 | // allows the main loop to process the data as 64-bit integers. | |
139 | const int len_aligned = len & ~0x7; | |
140 | const char* const end = buf + len_aligned; | |
141 | size_t hash = seed ^ (len * mul); | |
142 | for (const char* p = buf; p != end; p += 8) | |
143 | { | |
144 | const size_t data = shift_mix(unaligned_load(p) * mul) * mul; | |
145 | hash ^= data; | |
146 | hash *= mul; | |
147 | } | |
148 | if ((len & 0x7) != 0) | |
149 | { | |
150 | const size_t data = load_bytes(end, len & 0x7); | |
151 | hash ^= data; | |
152 | hash *= mul; | |
153 | } | |
154 | hash = shift_mix(hash) * mul; | |
155 | hash = shift_mix(hash); | |
156 | return hash; | |
157 | } | |
158 | ||
159 | // Implementation of FNV hash for 64-bit size_t. | |
160 | size_t | |
161 | _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash) | |
162 | { | |
163 | const char* cptr = static_cast<const char*>(ptr); | |
164 | for (; len; --len) | |
165 | { | |
166 | hash ^= static_cast<size_t>(*cptr++); | |
167 | hash *= static_cast<size_t>(1099511628211ULL); | |
168 | } | |
169 | return hash; | |
170 | } | |
171 | ||
172 | #else | |
173 | ||
174 | // Dummy hash implementation for unusual sizeof(size_t). | |
175 | size_t | |
176 | _Hash_bytes(const void* ptr, size_t len, size_t seed) | |
177 | { | |
178 | size_t hash = seed; | |
179 | const char* cptr = reinterpret_cast<const char*>(ptr); | |
180 | for (; len; --len) | |
181 | hash = (hash * 131) + *cptr++; | |
182 | return hash; | |
183 | } | |
184 | ||
185 | size_t | |
186 | _Fnv_hash_bytes(const void* ptr, size_t len, size_t seed) | |
187 | { return _Hash_bytes(ptr, len, seed); } | |
188 | ||
189 | #endif /* __SIZEOF_SIZE_T__ */ | |
190 | ||
191 | _GLIBCXX_END_NAMESPACE_VERSION | |
192 | } // namespace |