Line data Source code
1 : #include "fd_util_base.h"
2 : #include "bits/fd_bits.h"
3 :
4 : /* A cleaner implementation of xxhash-r39 (Open Source BSD licensed). */
5 : #if FD_HAS_AVX512 && defined(__AVX512DQ__) && defined(__AVX512VL__)
6 : #include "simd/fd_avx.h"
7 : #endif
8 :
9 1790334 : #define ROTATE_LEFT(x,r) (((x)<<(r)) | ((x)>>(64-(r))))
10 3135170 : #define C1 (11400714785074694791UL)
11 1243282 : #define C2 (14029467366897019727UL)
12 645565 : #define C3 ( 1609587929392839161UL)
13 1942553 : #define C4 ( 9650029242287828579UL)
14 606054 : #define C5 ( 2870177450012600261UL)
15 :
16 : static inline FD_FN_UNUSED FD_FN_PURE ulong
17 : fd_hash_generic( ulong seed,
18 : void const * buf,
19 0 : ulong sz ) {
20 0 : uchar const * p = ((uchar const *)buf);
21 0 : uchar const * stop = p + sz;
22 0 :
23 0 : ulong h;
24 0 :
25 0 : if( sz<32 ) h = seed + C5;
26 0 : else {
27 0 : uchar const * stop32 = stop - 32;
28 0 : ulong w = seed + (C1+C2);
29 0 : ulong x = seed + C2;
30 0 : ulong y = seed;
31 0 : ulong z = seed - C1;
32 0 :
33 0 : do { /* All complete blocks of 32 */
34 0 : w += FD_LOAD( ulong, p )*C2; w = ROTATE_LEFT( w, 31 ); w *= C1;
35 0 : x += FD_LOAD( ulong, p+ 8 )*C2; x = ROTATE_LEFT( x, 31 ); x *= C1;
36 0 : y += FD_LOAD( ulong, p+16 )*C2; y = ROTATE_LEFT( y, 31 ); y *= C1;
37 0 : z += FD_LOAD( ulong, p+24 )*C2; z = ROTATE_LEFT( z, 31 ); z *= C1;
38 0 : p += 32;
39 0 : } while( p<=stop32 );
40 0 :
41 0 : h = ROTATE_LEFT( w, 1 ) + ROTATE_LEFT( x, 7 ) + ROTATE_LEFT( y, 12 ) + ROTATE_LEFT( z, 18 );
42 0 :
43 0 : w *= C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = h*C1 + C4;
44 0 : x *= C2; x = ROTATE_LEFT( x, 31 ); x *= C1; h ^= x; h = h*C1 + C4;
45 0 : y *= C2; y = ROTATE_LEFT( y, 31 ); y *= C1; h ^= y; h = h*C1 + C4;
46 0 : z *= C2; z = ROTATE_LEFT( z, 31 ); z *= C1; h ^= z; h = h*C1 + C4;
47 0 : }
48 0 :
49 0 : h += ((ulong)sz);
50 0 :
51 0 : while( (p+8)<=stop ) { /* Last 1 to 3 complete ulong's */
52 0 : ulong w = FD_LOAD( ulong, p );
53 0 : w *= C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = ROTATE_LEFT( h, 27 )*C1 + C4;
54 0 : p += 8;
55 0 : }
56 0 :
57 0 : if( (p+4)<=stop ) { /* Last complete uint */
58 0 : ulong w = ((ulong)FD_LOAD( uint, p ));
59 0 : w *= C1; h ^= w; h = ROTATE_LEFT( h, 23 )*C2 + C3;
60 0 : p += 4;
61 0 : }
62 0 :
63 0 : while( p<stop ) { /* Last 1 to 3 uchar's */
64 0 : ulong w = ((ulong)(p[0]));
65 0 : w *= C5; h ^= w; h = ROTATE_LEFT( h, 11 )*C1;
66 0 : p++;
67 0 : }
68 0 :
69 0 : /* Final avalanche */
70 0 : h ^= h >> 33;
71 0 : h *= C2;
72 0 : h ^= h >> 29;
73 0 : h *= C3;
74 0 : h ^= h >> 32;
75 0 :
76 0 : return h;
77 0 : }
78 :
79 : #if FD_HAS_AVX512 && defined(__AVX512DQ__) && defined(__AVX512VL__)
80 : static inline FD_FN_UNUSED FD_FN_PURE ulong
81 : fd_hash_avx512dq( ulong seed,
82 : void const * buf,
83 496464 : ulong sz ) {
84 496464 : uchar const * p = ((uchar const *)buf);
85 496464 : uchar const * stop = p + sz;
86 496464 : ulong h;
87 :
88 496464 : if( sz<32 ) h = seed + C5;
89 336209 : else {
90 336209 : uchar const * stop32 = stop - 32;
91 336209 : ulong w, x, y, z;
92 336209 : wv_t state_vec = wv_add( wv_bcast( seed ), wv( C1 + C2, C2, 0UL, 0UL - C1 ) );
93 336209 : wv_t c1_vec = wv_bcast( C1 );
94 336209 : wv_t c2_vec = wv_bcast( C2 );
95 124454103 : do { /* All complete blocks of 32 */
96 124454103 : wv_t input_vec = wv_ldu( p );
97 124454103 : input_vec = wv_mul( input_vec, c2_vec );
98 124454103 : state_vec = wv_add( state_vec, input_vec );
99 124454103 : state_vec = wv_rol( state_vec, 31 );
100 124454103 : state_vec = wv_mul( state_vec, c1_vec );
101 124454103 : p += 32;
102 124454103 : } while( p<=stop32 );
103 336209 : wv_t h_vec = wv_rol_vector( state_vec, wv( 1UL, 7UL, 12UL, 18UL ) );
104 336209 : h = wv_extract( h_vec, 0 )
105 336209 : + wv_extract( h_vec, 1 )
106 336209 : + wv_extract( h_vec, 2 )
107 336209 : + wv_extract( h_vec, 3 );
108 336209 : state_vec = wv_mul( state_vec, c2_vec );
109 336209 : state_vec = wv_rol( state_vec, 31 );
110 336209 : state_vec = wv_mul( state_vec, c1_vec );
111 336209 : w = wv_extract( state_vec, 0 );
112 336209 : x = wv_extract( state_vec, 1 );
113 336209 : y = wv_extract( state_vec, 2 );
114 336209 : z = wv_extract( state_vec, 3 );
115 336209 : h ^= w; h = h*C1 + C4;
116 336209 : h ^= x; h = h*C1 + C4;
117 336209 : h ^= y; h = h*C1 + C4;
118 336209 : h ^= z; h = h*C1 + C4;
119 336209 : }
120 :
121 496464 : h += sz;
122 :
123 1094181 : while( (p+8)<=stop ) { /* Last 1 to 3 complete ulong's */
124 597717 : ulong w = FD_LOAD( ulong, p );
125 597717 : w *= C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = ROTATE_LEFT( h, 27 )*C1 + C4;
126 597717 : p += 8;
127 597717 : }
128 :
129 496464 : if( (p+4)<=stop ) { /* Last complete uint */
130 149101 : ulong w = ((ulong)FD_LOAD( uint, p ));
131 149101 : w *= C1; h ^= w; h = ROTATE_LEFT( h, 23 )*C2 + C3;
132 149101 : p += 4;
133 149101 : }
134 :
135 942263 : while( p<stop ) { /* Last 1 to 3 uchar's */
136 445799 : ulong w = ((ulong)(p[0]));
137 445799 : w *= C5; h ^= w; h = ROTATE_LEFT( h, 11 )*C1;
138 445799 : p++;
139 445799 : }
140 :
141 : /* Final avalanche */
142 496464 : h ^= h >> 33;
143 496464 : h *= C2;
144 496464 : h ^= h >> 29;
145 496464 : h *= C3;
146 496464 : h ^= h >> 32;
147 :
148 496464 : return h;
149 496464 : }
150 : #endif
151 :
152 : ulong
153 : fd_hash( ulong seed,
154 : void const * buf,
155 496460 : ulong sz ) {
156 496460 : #if FD_HAS_AVX512 && defined(__AVX512DQ__) && defined(__AVX512VL__)
157 496460 : return fd_hash_avx512dq( seed, buf, sz );
158 : #else
159 : return fd_hash_generic( seed, buf, sz );
160 : #endif
161 496460 : }
162 :
163 : ulong
164 : fd_hash_memcpy( ulong seed,
165 : void * FD_RESTRICT dst,
166 : void const * FD_RESTRICT src,
167 0 : ulong sz ) {
168 0 : uchar * FD_RESTRICT q = ((uchar *)dst);
169 0 : uchar const * FD_RESTRICT p = ((uchar const *)src);
170 0 : uchar const * FD_RESTRICT stop = p + sz;
171 :
172 0 : ulong h;
173 :
174 0 : if( sz<32 ) h = seed + C5;
175 0 : else {
176 0 : uchar const * FD_RESTRICT stop32 = stop - 32;
177 0 : ulong w = seed + (C1+C2);
178 0 : ulong x = seed + C2;
179 0 : ulong y = seed;
180 0 : ulong z = seed - C1;
181 :
182 0 : do { /* All complete blocks of 32 */
183 0 : ulong p0 = FD_LOAD( ulong, p );
184 0 : ulong p1 = FD_LOAD( ulong, p+ 8 );
185 0 : ulong p2 = FD_LOAD( ulong, p+16 );
186 0 : ulong p3 = FD_LOAD( ulong, p+24 );
187 0 : w += p0*C2; w = ROTATE_LEFT( w, 31 ); w *= C1;
188 0 : x += p1*C2; x = ROTATE_LEFT( x, 31 ); x *= C1;
189 0 : y += p2*C2; y = ROTATE_LEFT( y, 31 ); y *= C1;
190 0 : z += p3*C2; z = ROTATE_LEFT( z, 31 ); z *= C1;
191 0 : FD_STORE( ulong, q, p0 );
192 0 : FD_STORE( ulong, q+ 8, p1 );
193 0 : FD_STORE( ulong, q+16, p2 );
194 0 : FD_STORE( ulong, q+24, p3 );
195 0 : p += 32;
196 0 : q += 32;
197 0 : } while( p<=stop32 );
198 :
199 0 : h = ROTATE_LEFT( w, 1 ) + ROTATE_LEFT( x, 7 ) + ROTATE_LEFT( y, 12 ) + ROTATE_LEFT( z, 18 );
200 :
201 0 : w *= C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = h*C1 + C4;
202 0 : x *= C2; x = ROTATE_LEFT( x, 31 ); x *= C1; h ^= x; h = h*C1 + C4;
203 0 : y *= C2; y = ROTATE_LEFT( y, 31 ); y *= C1; h ^= y; h = h*C1 + C4;
204 0 : z *= C2; z = ROTATE_LEFT( z, 31 ); z *= C1; h ^= z; h = h*C1 + C4;
205 0 : }
206 :
207 0 : h += ((ulong)sz);
208 :
209 0 : while( (p+8)<=stop ) { /* Last 1 to 3 complete ulong's */
210 0 : ulong p0 = FD_LOAD( ulong, p );
211 0 : ulong w = p0*C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = ROTATE_LEFT( h, 27 )*C1 + C4;
212 0 : FD_STORE( ulong, q, p0 );
213 0 : p += 8;
214 0 : q += 8;
215 0 : }
216 :
217 0 : if( (p+4)<=stop ) { /* Last complete uint */
218 0 : uint p0 = FD_LOAD( uint, p );
219 0 : ulong w = ((ulong)p0)*C1; h ^= w; h = ROTATE_LEFT( h, 23 )*C2 + C3;
220 0 : FD_STORE( uint, q, p0 );
221 0 : p += 4;
222 0 : q += 4;
223 0 : }
224 :
225 0 : while( p<stop ) { /* Last 1 to 3 uchar's */
226 0 : uchar p0 = p[0];
227 0 : ulong w = ((ulong)p0)*C5; h ^= w; h = ROTATE_LEFT( h, 11 )*C1;
228 0 : q[0] = p0;
229 0 : p++;
230 0 : q++;
231 0 : }
232 :
233 : /* Final avalanche */
234 0 : h ^= h >> 33;
235 0 : h *= C2;
236 0 : h ^= h >> 29;
237 0 : h *= C3;
238 0 : h ^= h >> 32;
239 :
240 0 : return h;
241 0 : }
242 :
243 : #undef C5
244 : #undef C4
245 : #undef C3
246 : #undef C2
247 : #undef C1
248 : #undef ROTATE_LEFT
|
