1// Definition of _Hash_bytes. -*- C++ -*-
2
3// Copyright (C) 2010-2017 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
37namespace
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
66namespace 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.
142 const int len_aligned = len & ~0x7;
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
199