]>
Commit | Line | Data |
---|---|---|
e7f72940 MA |
1 | // Definition of _Hash_bytes. -*- C++ -*- |
2 | ||
3 | // Copyright (C) 2010 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 <cstring> | |
36 | #include <bits/functional_hash.h> | |
37 | ||
38 | namespace | |
39 | { | |
40 | inline std::size_t | |
41 | unaligned_load(const char* p) | |
42 | { | |
43 | std::size_t result; | |
44 | std::memcpy(&result, p, sizeof(result)); | |
45 | return result; | |
46 | } | |
47 | ||
48 | // Loads n bytes, where 1 <= n < 8. | |
49 | inline std::size_t | |
50 | load_bytes(const char* p, int n) | |
51 | { | |
52 | 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 | } | |
64 | ||
65 | namespace std | |
66 | { | |
67 | #if __SIZEOF_SIZE_T__ == 4 | |
68 | ||
69 | // Implementation of Murmur hash for 32-bit size_t. | |
70 | size_t | |
71 | _Hash_bytes(const void* ptr, size_t len, size_t seed) | |
72 | { | |
73 | const size_t m = 0x5bd1e995; | |
74 | size_t hash = seed ^ len; | |
75 | const char* buf = static_cast<const char*>(ptr); | |
76 | ||
77 | // Mix 4 bytes at a time into the hash. | |
78 | while(len >= 4) | |
79 | { | |
80 | size_t k = unaligned_load(buf); | |
81 | k *= m; | |
82 | k ^= k >> 24; | |
83 | k *= m; | |
84 | hash *= m; | |
85 | hash ^= k; | |
86 | buf += 4; | |
87 | len -= 4; | |
88 | } | |
89 | ||
90 | // Handle the last few bytes of the input array. | |
91 | switch(len) | |
92 | { | |
93 | case 3: | |
94 | hash ^= static_cast<unsigned char>(buf[2]) << 16; | |
95 | case 2: | |
96 | hash ^= static_cast<unsigned char>(buf[1]) << 8; | |
97 | case 1: | |
98 | hash ^= static_cast<unsigned char>(buf[0]); | |
99 | hash *= m; | |
100 | }; | |
101 | ||
102 | // Do a few final mixes of the hash. | |
103 | hash ^= hash >> 13; | |
104 | hash *= m; | |
105 | hash ^= hash >> 15; | |
106 | return hash; | |
107 | } | |
108 | ||
109 | // Implementation of FNV hash for 32-bit size_t. | |
110 | size_t | |
111 | _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash) | |
112 | { | |
113 | const char* cptr = static_cast<const char*>(ptr); | |
114 | for (; len; --len) | |
115 | { | |
116 | hash ^= static_cast<size_t>(*cptr++); | |
117 | hash *= static_cast<size_t>(16777619UL); | |
118 | } | |
119 | return hash; | |
120 | } | |
121 | ||
122 | #elif __SIZEOF_SIZE_T__ == 8 | |
123 | ||
124 | // Implementation of Murmur hash for 64-bit size_t. | |
125 | size_t | |
126 | _Hash_bytes(const void* ptr, size_t len, size_t seed) | |
127 | { | |
128 | static const size_t mul = (0xc6a4a793UL << 32UL) + 0x5bd1e995UL; | |
129 | const char* const buf = static_cast<const char*>(ptr); | |
130 | ||
131 | // Remove the bytes not divisible by the sizeof(size_t). This | |
132 | // allows the main loop to process the data as 64-bit integers. | |
133 | const int len_aligned = len & ~0x7; | |
134 | const char* const end = buf + len_aligned; | |
135 | size_t hash = seed ^ (len * mul); | |
136 | for (const char* p = buf; p != end; p += 8) | |
137 | { | |
138 | const size_t data = shift_mix(unaligned_load(p) * mul) * mul; | |
139 | hash ^= data; | |
140 | hash *= mul; | |
141 | } | |
142 | if ((len & 0x7) != 0) | |
143 | { | |
144 | const size_t data = load_bytes(end, len & 0x7); | |
145 | hash ^= data; | |
146 | hash *= mul; | |
147 | } | |
148 | hash = shift_mix(hash) * mul; | |
149 | hash = shift_mix(hash); | |
150 | return hash; | |
151 | } | |
152 | ||
153 | // Implementation of FNV hash for 64-bit size_t. | |
154 | size_t | |
155 | _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash) | |
156 | { | |
157 | const char* cptr = static_cast<const char*>(ptr); | |
158 | for (; len; --len) | |
159 | { | |
160 | hash ^= static_cast<size_t>(*cptr++); | |
161 | hash *= static_cast<size_t>(1099511628211ULL); | |
162 | } | |
163 | return hash; | |
164 | } | |
165 | ||
166 | #else | |
167 | ||
168 | // Dummy hash implementation for unusual sizeof(size_t). | |
169 | size_t | |
170 | _Hash_bytes(const void* ptr, size_t len, size_t seed) | |
171 | { | |
172 | size_t hash = seed; | |
173 | const char* cptr = reinterpret_cast<const char*>(ptr); | |
174 | for (; clength; --clength) | |
175 | hash = (hash * 131) + *cptr++; | |
176 | return hash; | |
177 | } | |
178 | ||
179 | size_t | |
180 | _Fnv_hash_bytes(const void* ptr, size_t len, size_t seed) | |
181 | { return _Hash_bytes(ptr, len, seed); } | |
182 | ||
183 | #endif /* __SIZEOF_SIZE_T__ */ | |
184 | } |