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