1// Copyright 2022 Peter Dimov
2// Distributed under the Boost Software License, Version 1.0.
3// https://www.boost.org/LICENSE_1_0.txt
4
5#ifndef BOOST_HASH_DETAIL_HASH_RANGE_HPP
6#define BOOST_HASH_DETAIL_HASH_RANGE_HPP
7
8#include <boost/container_hash/hash_fwd.hpp>
9#include <boost/container_hash/detail/mulx.hpp>
10#include <type_traits>
11#include <cstdint>
12#include <iterator>
13#include <limits>
14#include <cstddef>
15#include <climits>
16#include <cstring>
17
18namespace boost
19{
20namespace hash_detail
21{
22
23template<class T> struct is_char_type: public std::false_type {};
24
25#if CHAR_BIT == 8
26
27template<> struct is_char_type<char>: public std::true_type {};
28template<> struct is_char_type<signed char>: public std::true_type {};
29template<> struct is_char_type<unsigned char>: public std::true_type {};
30
31#if defined(__cpp_char8_t) && __cpp_char8_t >= 201811L
32template<> struct is_char_type<char8_t>: public std::true_type {};
33#endif
34
35#if defined(__cpp_lib_byte) && __cpp_lib_byte >= 201603L
36template<> struct is_char_type<std::byte>: public std::true_type {};
37#endif
38
39#endif
40
41// generic version
42
43template<class It>
44inline typename std::enable_if<
45 !is_char_type<typename std::iterator_traits<It>::value_type>::value,
46std::size_t >::type
47 hash_range( std::size_t seed, It first, It last )
48{
49 for( ; first != last; ++first )
50 {
51 hash_combine<typename std::iterator_traits<It>::value_type>( seed, *first );
52 }
53
54 return seed;
55}
56
57// specialized char[] version, 32 bit
58
59template<class It> inline std::uint32_t read32le( It p )
60{
61 // clang 5+, gcc 5+ figure out this pattern and use a single mov on x86
62 // gcc on s390x and power BE even knows how to use load-reverse
63
64 std::uint32_t w =
65 static_cast<std::uint32_t>( static_cast<unsigned char>( p[0] ) ) |
66 static_cast<std::uint32_t>( static_cast<unsigned char>( p[1] ) ) << 8 |
67 static_cast<std::uint32_t>( static_cast<unsigned char>( p[2] ) ) << 16 |
68 static_cast<std::uint32_t>( static_cast<unsigned char>( p[3] ) ) << 24;
69
70 return w;
71}
72
73#if defined(_MSC_VER) && !defined(__clang__)
74
75template<class T> inline std::uint32_t read32le( T* p )
76{
77 std::uint32_t w;
78
79 std::memcpy( &w, p, 4 );
80 return w;
81}
82
83#endif
84
85inline std::uint64_t mul32( std::uint32_t x, std::uint32_t y )
86{
87 return static_cast<std::uint64_t>( x ) * y;
88}
89
90template<class It>
91inline typename std::enable_if<
92 is_char_type<typename std::iterator_traits<It>::value_type>::value &&
93 std::is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value &&
94 std::numeric_limits<std::size_t>::digits <= 32,
95std::size_t>::type
96 hash_range( std::size_t seed, It first, It last )
97{
98 It p = first;
99 std::size_t n = static_cast<std::size_t>( last - first );
100
101 std::uint32_t const q = 0x9e3779b9U;
102 std::uint32_t const k = 0xe35e67b1U; // q * q
103
104 std::uint64_t h = mul32( x: static_cast<std::uint32_t>( seed ) + q, y: k );
105 std::uint32_t w = static_cast<std::uint32_t>( h & 0xFFFFFFFF );
106
107 h ^= n;
108
109 while( n >= 4 )
110 {
111 std::uint32_t v1 = read32le( p );
112
113 w += q;
114 h ^= mul32( x: v1 + w, y: k );
115
116 p += 4;
117 n -= 4;
118 }
119
120 {
121 std::uint32_t v1 = 0;
122
123 if( n >= 1 )
124 {
125 std::size_t const x1 = ( n - 1 ) & 2; // 1: 0, 2: 0, 3: 2
126 std::size_t const x2 = n >> 1; // 1: 0, 2: 1, 3: 1
127
128 v1 =
129 static_cast<std::uint32_t>( static_cast<unsigned char>( p[ static_cast<std::ptrdiff_t>( x1 ) ] ) ) << x1 * 8 |
130 static_cast<std::uint32_t>( static_cast<unsigned char>( p[ static_cast<std::ptrdiff_t>( x2 ) ] ) ) << x2 * 8 |
131 static_cast<std::uint32_t>( static_cast<unsigned char>( p[ 0 ] ) );
132 }
133
134 w += q;
135 h ^= mul32( x: v1 + w, y: k );
136 }
137
138 w += q;
139 h ^= mul32( x: static_cast<std::uint32_t>( h & 0xFFFFFFFF ) + w, y: static_cast<std::uint32_t>( h >> 32 ) + w + k );
140
141 return static_cast<std::uint32_t>( h & 0xFFFFFFFF ) ^ static_cast<std::uint32_t>( h >> 32 );
142}
143
144template<class It>
145inline typename std::enable_if<
146 is_char_type<typename std::iterator_traits<It>::value_type>::value &&
147 !std::is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value &&
148 std::numeric_limits<std::size_t>::digits <= 32,
149std::size_t>::type
150 hash_range( std::size_t seed, It first, It last )
151{
152 std::size_t n = 0;
153
154 std::uint32_t const q = 0x9e3779b9U;
155 std::uint32_t const k = 0xe35e67b1U; // q * q
156
157 std::uint64_t h = mul32( x: static_cast<std::uint32_t>( seed ) + q, y: k );
158 std::uint32_t w = static_cast<std::uint32_t>( h & 0xFFFFFFFF );
159
160 std::uint32_t v1 = 0;
161
162 for( ;; )
163 {
164 v1 = 0;
165
166 if( first == last )
167 {
168 break;
169 }
170
171 v1 |= static_cast<std::uint32_t>( static_cast<unsigned char>( *first ) );
172 ++first;
173 ++n;
174
175 if( first == last )
176 {
177 break;
178 }
179
180 v1 |= static_cast<std::uint32_t>( static_cast<unsigned char>( *first ) ) << 8;
181 ++first;
182 ++n;
183
184 if( first == last )
185 {
186 break;
187 }
188
189 v1 |= static_cast<std::uint32_t>( static_cast<unsigned char>( *first ) ) << 16;
190 ++first;
191 ++n;
192
193 if( first == last )
194 {
195 break;
196 }
197
198 v1 |= static_cast<std::uint32_t>( static_cast<unsigned char>( *first ) ) << 24;
199 ++first;
200 ++n;
201
202 w += q;
203 h ^= mul32( x: v1 + w, y: k );
204 }
205
206 h ^= n;
207
208 w += q;
209 h ^= mul32( x: v1 + w, y: k );
210
211 w += q;
212 h ^= mul32( x: static_cast<std::uint32_t>( h & 0xFFFFFFFF ) + w, y: static_cast<std::uint32_t>( h >> 32 ) + w + k );
213
214 return static_cast<std::uint32_t>( h & 0xFFFFFFFF ) ^ static_cast<std::uint32_t>( h >> 32 );
215}
216
217// specialized char[] version, 64 bit
218
219template<class It> inline std::uint64_t read64le( It p )
220{
221 std::uint64_t w =
222 static_cast<std::uint64_t>( static_cast<unsigned char>( p[0] ) ) |
223 static_cast<std::uint64_t>( static_cast<unsigned char>( p[1] ) ) << 8 |
224 static_cast<std::uint64_t>( static_cast<unsigned char>( p[2] ) ) << 16 |
225 static_cast<std::uint64_t>( static_cast<unsigned char>( p[3] ) ) << 24 |
226 static_cast<std::uint64_t>( static_cast<unsigned char>( p[4] ) ) << 32 |
227 static_cast<std::uint64_t>( static_cast<unsigned char>( p[5] ) ) << 40 |
228 static_cast<std::uint64_t>( static_cast<unsigned char>( p[6] ) ) << 48 |
229 static_cast<std::uint64_t>( static_cast<unsigned char>( p[7] ) ) << 56;
230
231 return w;
232}
233
234#if defined(_MSC_VER) && !defined(__clang__)
235
236template<class T> inline std::uint64_t read64le( T* p )
237{
238 std::uint64_t w;
239
240 std::memcpy( &w, p, 8 );
241 return w;
242}
243
244#endif
245
246template<class It>
247inline typename std::enable_if<
248 is_char_type<typename std::iterator_traits<It>::value_type>::value &&
249 std::is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value &&
250 (std::numeric_limits<std::size_t>::digits > 32),
251std::size_t>::type
252 hash_range( std::size_t seed, It first, It last )
253{
254 It p = first;
255 std::size_t n = static_cast<std::size_t>( last - first );
256
257 std::uint64_t const q = 0x9e3779b97f4a7c15;
258 std::uint64_t const k = 0xdf442d22ce4859b9; // q * q
259
260 std::uint64_t w = mulx( x: seed + q, y: k );
261 std::uint64_t h = w ^ n;
262
263 while( n >= 8 )
264 {
265 std::uint64_t v1 = read64le( p );
266
267 w += q;
268 h ^= mulx( x: v1 + w, y: k );
269
270 p += 8;
271 n -= 8;
272 }
273
274 {
275 std::uint64_t v1 = 0;
276
277 if( n >= 4 )
278 {
279 v1 = static_cast<std::uint64_t>( read32le( p + static_cast<std::ptrdiff_t>( n - 4 ) ) ) << ( n - 4 ) * 8 | read32le( p );
280 }
281 else if( n >= 1 )
282 {
283 std::size_t const x1 = ( n - 1 ) & 2; // 1: 0, 2: 0, 3: 2
284 std::size_t const x2 = n >> 1; // 1: 0, 2: 1, 3: 1
285
286 v1 =
287 static_cast<std::uint64_t>( static_cast<unsigned char>( p[ static_cast<std::ptrdiff_t>( x1 ) ] ) ) << x1 * 8 |
288 static_cast<std::uint64_t>( static_cast<unsigned char>( p[ static_cast<std::ptrdiff_t>( x2 ) ] ) ) << x2 * 8 |
289 static_cast<std::uint64_t>( static_cast<unsigned char>( p[ 0 ] ) );
290 }
291
292 w += q;
293 h ^= mulx( x: v1 + w, y: k );
294 }
295
296 return mulx( x: h + w, y: k );
297}
298
299template<class It>
300inline typename std::enable_if<
301 is_char_type<typename std::iterator_traits<It>::value_type>::value &&
302 !std::is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value &&
303 (std::numeric_limits<std::size_t>::digits > 32),
304std::size_t>::type
305 hash_range( std::size_t seed, It first, It last )
306{
307 std::size_t n = 0;
308
309 std::uint64_t const q = 0x9e3779b97f4a7c15;
310 std::uint64_t const k = 0xdf442d22ce4859b9; // q * q
311
312 std::uint64_t w = mulx( x: seed + q, y: k );
313 std::uint64_t h = w;
314
315 std::uint64_t v1 = 0;
316
317 for( ;; )
318 {
319 v1 = 0;
320
321 if( first == last )
322 {
323 break;
324 }
325
326 v1 |= static_cast<std::uint64_t>( static_cast<unsigned char>( *first ) );
327 ++first;
328 ++n;
329
330 if( first == last )
331 {
332 break;
333 }
334
335 v1 |= static_cast<std::uint64_t>( static_cast<unsigned char>( *first ) ) << 8;
336 ++first;
337 ++n;
338
339 if( first == last )
340 {
341 break;
342 }
343
344 v1 |= static_cast<std::uint64_t>( static_cast<unsigned char>( *first ) ) << 16;
345 ++first;
346 ++n;
347
348 if( first == last )
349 {
350 break;
351 }
352
353 v1 |= static_cast<std::uint64_t>( static_cast<unsigned char>( *first ) ) << 24;
354 ++first;
355 ++n;
356
357 if( first == last )
358 {
359 break;
360 }
361
362 v1 |= static_cast<std::uint64_t>( static_cast<unsigned char>( *first ) ) << 32;
363 ++first;
364 ++n;
365
366 if( first == last )
367 {
368 break;
369 }
370
371 v1 |= static_cast<std::uint64_t>( static_cast<unsigned char>( *first ) ) << 40;
372 ++first;
373 ++n;
374
375 if( first == last )
376 {
377 break;
378 }
379
380 v1 |= static_cast<std::uint64_t>( static_cast<unsigned char>( *first ) ) << 48;
381 ++first;
382 ++n;
383
384 if( first == last )
385 {
386 break;
387 }
388
389 v1 |= static_cast<std::uint64_t>( static_cast<unsigned char>( *first ) ) << 56;
390 ++first;
391 ++n;
392
393 w += q;
394 h ^= mulx( x: v1 + w, y: k );
395 }
396
397 h ^= n;
398
399 w += q;
400 h ^= mulx( x: v1 + w, y: k );
401
402 return mulx( x: h + w, y: k );
403}
404
405} // namespace hash_detail
406} // namespace boost
407
408#endif // #ifndef BOOST_HASH_DETAIL_HASH_RANGE_HPP
409

source code of boost/libs/container_hash/include/boost/container_hash/detail/hash_range.hpp