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 5954502841 : #define ROTATE_LEFT(x,r) (((x)<<(r)) | ((x)>>(64-(r))))
10 6759955183 : #define C1 (11400714785074694791UL)
11 5727347137 : #define C2 (14029467366897019727UL)
12 325037883 : #define C3 ( 1609587929392839161UL)
13 1273741980 : #define C4 ( 9650029242287828579UL)
14 64241217 : #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 200715590 : ulong sz ) {
20 200715590 : uchar const * p = ((uchar const *)buf);
21 200715590 : uchar const * stop = p + sz;
22 0 :
23 200715590 : ulong h;
24 0 :
25 200715590 : if( sz<32 ) h = seed + C5;
26 199909086 : else {
27 199909086 : uchar const * stop32 = stop - 32;
28 199909086 : ulong w = seed + (C1+C2);
29 199909086 : ulong x = seed + C2;
30 199909086 : ulong y = seed;
31 199909086 : ulong z = seed - C1;
32 0 :
33 968139184 : do { /* All complete blocks of 32 */
34 968139184 : w += FD_LOAD( ulong, p )*C2; w = ROTATE_LEFT( w, 31 ); w *= C1;
35 968139184 : x += FD_LOAD( ulong, p+ 8 )*C2; x = ROTATE_LEFT( x, 31 ); x *= C1;
36 968139184 : y += FD_LOAD( ulong, p+16 )*C2; y = ROTATE_LEFT( y, 31 ); y *= C1;
37 968139184 : z += FD_LOAD( ulong, p+24 )*C2; z = ROTATE_LEFT( z, 31 ); z *= C1;
38 968139184 : p += 32;
39 968139184 : } while( p<=stop32 );
40 0 :
41 199909086 : h = ROTATE_LEFT( w, 1 ) + ROTATE_LEFT( x, 7 ) + ROTATE_LEFT( y, 12 ) + ROTATE_LEFT( z, 18 );
42 0 :
43 199909086 : w *= C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = h*C1 + C4;
44 199909086 : x *= C2; x = ROTATE_LEFT( x, 31 ); x *= C1; h ^= x; h = h*C1 + C4;
45 199909086 : y *= C2; y = ROTATE_LEFT( y, 31 ); y *= C1; h ^= y; h = h*C1 + C4;
46 199909086 : z *= C2; z = ROTATE_LEFT( z, 31 ); z *= C1; h ^= z; h = h*C1 + C4;
47 199909086 : }
48 0 :
49 200715590 : h += ((ulong)sz);
50 0 :
51 239503576 : while( (p+8)<=stop ) { /* Last 1 to 3 complete ulong's */
52 38787986 : ulong w = FD_LOAD( ulong, p );
53 38787986 : w *= C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = ROTATE_LEFT( h, 27 )*C1 + C4;
54 38787986 : p += 8;
55 38787986 : }
56 0 :
57 200715590 : if( (p+4)<=stop ) { /* Last complete uint */
58 12977108 : ulong w = ((ulong)FD_LOAD( uint, p ));
59 12977108 : w *= C1; h ^= w; h = ROTATE_LEFT( h, 23 )*C2 + C3;
60 12977108 : p += 4;
61 12977108 : }
62 0 :
63 239677394 : while( p<stop ) { /* Last 1 to 3 uchar's */
64 38961804 : ulong w = ((ulong)(p[0]));
65 38961804 : w *= C5; h ^= w; h = ROTATE_LEFT( h, 11 )*C1;
66 38961804 : p++;
67 38961804 : }
68 0 :
69 0 : /* Final avalanche */
70 200715590 : h ^= h >> 33;
71 200715590 : h *= C2;
72 200715590 : h ^= h >> 29;
73 200715590 : h *= C3;
74 200715590 : h ^= h >> 32;
75 0 :
76 200715590 : return h;
77 200715590 : }
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 100357798 : ulong sz ) {
84 100357798 : uchar const * p = ((uchar const *)buf);
85 100357798 : uchar const * stop = p + sz;
86 100357798 : ulong h;
87 :
88 100357798 : if( sz<32 ) h = seed + C5;
89 99954546 : else {
90 99954546 : uchar const * stop32 = stop - 32;
91 99954546 : ulong w, x, y, z;
92 99954546 : wv_t state_vec = wv_add( wv_bcast( seed ), wv( C1 + C2, C2, 0UL, 0UL - C1 ) );
93 99954546 : wv_t c1_vec = wv_bcast( C1 );
94 99954546 : wv_t c2_vec = wv_bcast( C2 );
95 484069750 : do { /* All complete blocks of 32 */
96 484069750 : wv_t input_vec = wv_ldu( p );
97 484069750 : input_vec = wv_mul( input_vec, c2_vec );
98 484069750 : state_vec = wv_add( state_vec, input_vec );
99 484069750 : state_vec = wv_rol( state_vec, 31 );
100 484069750 : state_vec = wv_mul( state_vec, c1_vec );
101 484069750 : p += 32;
102 484069750 : } while( p<=stop32 );
103 99954546 : wv_t h_vec = wv_rol_vector( state_vec, wv( 1UL, 7UL, 12UL, 18UL ) );
104 99954546 : h = wv_extract( h_vec, 0 )
105 99954546 : + wv_extract( h_vec, 1 )
106 99954546 : + wv_extract( h_vec, 2 )
107 99954546 : + wv_extract( h_vec, 3 );
108 99954546 : state_vec = wv_mul( state_vec, c2_vec );
109 99954546 : state_vec = wv_rol( state_vec, 31 );
110 99954546 : state_vec = wv_mul( state_vec, c1_vec );
111 99954546 : w = wv_extract( state_vec, 0 );
112 99954546 : x = wv_extract( state_vec, 1 );
113 99954546 : y = wv_extract( state_vec, 2 );
114 99954546 : z = wv_extract( state_vec, 3 );
115 99954546 : h ^= w; h = h*C1 + C4;
116 99954546 : h ^= x; h = h*C1 + C4;
117 99954546 : h ^= y; h = h*C1 + C4;
118 99954546 : h ^= z; h = h*C1 + C4;
119 99954546 : }
120 :
121 100357798 : h += sz;
122 :
123 119751791 : while( (p+8)<=stop ) { /* Last 1 to 3 complete ulong's */
124 19393993 : ulong w = FD_LOAD( ulong, p );
125 19393993 : w *= C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = ROTATE_LEFT( h, 27 )*C1 + C4;
126 19393993 : p += 8;
127 19393993 : }
128 :
129 100357798 : if( (p+4)<=stop ) { /* Last complete uint */
130 6488554 : ulong w = ((ulong)FD_LOAD( uint, p ));
131 6488554 : w *= C1; h ^= w; h = ROTATE_LEFT( h, 23 )*C2 + C3;
132 6488554 : p += 4;
133 6488554 : }
134 :
135 119838700 : while( p<stop ) { /* Last 1 to 3 uchar's */
136 19480902 : ulong w = ((ulong)(p[0]));
137 19480902 : w *= C5; h ^= w; h = ROTATE_LEFT( h, 11 )*C1;
138 19480902 : p++;
139 19480902 : }
140 :
141 : /* Final avalanche */
142 100357798 : h ^= h >> 33;
143 100357798 : h *= C2;
144 100357798 : h ^= h >> 29;
145 100357798 : h *= C3;
146 100357798 : h ^= h >> 32;
147 :
148 100357798 : return h;
149 100357798 : }
150 : #endif
151 :
152 : ulong
153 : fd_hash( ulong seed,
154 : void const * buf,
155 301073388 : ulong sz ) {
156 100357798 : #if FD_HAS_AVX512 && defined(__AVX512DQ__) && defined(__AVX512VL__)
157 100357798 : return fd_hash_avx512dq( seed, buf, sz );
158 : #else
159 200715590 : return fd_hash_generic( seed, buf, sz );
160 200715590 : #endif
161 301073388 : }
162 :
163 : ulong
164 : fd_hash_memcpy( ulong seed,
165 : void * FD_RESTRICT dst,
166 : void const * FD_RESTRICT src,
167 3000000 : ulong sz ) {
168 3000000 : uchar * FD_RESTRICT q = ((uchar *)dst);
169 3000000 : uchar const * FD_RESTRICT p = ((uchar const *)src);
170 3000000 : uchar const * FD_RESTRICT stop = p + sz;
171 :
172 3000000 : ulong h;
173 :
174 3000000 : if( sz<32 ) h = seed + C5;
175 2907993 : else {
176 2907993 : uchar const * FD_RESTRICT stop32 = stop - 32;
177 2907993 : ulong w = seed + (C1+C2);
178 2907993 : ulong x = seed + C2;
179 2907993 : ulong y = seed;
180 2907993 : ulong z = seed - C1;
181 :
182 62548641 : do { /* All complete blocks of 32 */
183 62548641 : ulong p0 = FD_LOAD( ulong, p );
184 62548641 : ulong p1 = FD_LOAD( ulong, p+ 8 );
185 62548641 : ulong p2 = FD_LOAD( ulong, p+16 );
186 62548641 : ulong p3 = FD_LOAD( ulong, p+24 );
187 62548641 : w += p0*C2; w = ROTATE_LEFT( w, 31 ); w *= C1;
188 62548641 : x += p1*C2; x = ROTATE_LEFT( x, 31 ); x *= C1;
189 62548641 : y += p2*C2; y = ROTATE_LEFT( y, 31 ); y *= C1;
190 62548641 : z += p3*C2; z = ROTATE_LEFT( z, 31 ); z *= C1;
191 62548641 : FD_STORE( ulong, q, p0 );
192 62548641 : FD_STORE( ulong, q+ 8, p1 );
193 62548641 : FD_STORE( ulong, q+16, p2 );
194 62548641 : FD_STORE( ulong, q+24, p3 );
195 62548641 : p += 32;
196 62548641 : q += 32;
197 62548641 : } while( p<=stop32 );
198 :
199 2907993 : h = ROTATE_LEFT( w, 1 ) + ROTATE_LEFT( x, 7 ) + ROTATE_LEFT( y, 12 ) + ROTATE_LEFT( z, 18 );
200 :
201 2907993 : w *= C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = h*C1 + C4;
202 2907993 : x *= C2; x = ROTATE_LEFT( x, 31 ); x *= C1; h ^= x; h = h*C1 + C4;
203 2907993 : y *= C2; y = ROTATE_LEFT( y, 31 ); y *= C1; h ^= y; h = h*C1 + C4;
204 2907993 : z *= C2; z = ROTATE_LEFT( z, 31 ); z *= C1; h ^= z; h = h*C1 + C4;
205 2907993 : }
206 :
207 3000000 : h += ((ulong)sz);
208 :
209 7473501 : while( (p+8)<=stop ) { /* Last 1 to 3 complete ulong's */
210 4473501 : ulong p0 = FD_LOAD( ulong, p );
211 4473501 : ulong w = p0*C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = ROTATE_LEFT( h, 27 )*C1 + C4;
212 4473501 : FD_STORE( ulong, q, p0 );
213 4473501 : p += 8;
214 4473501 : q += 8;
215 4473501 : }
216 :
217 3000000 : if( (p+4)<=stop ) { /* Last complete uint */
218 1498833 : uint p0 = FD_LOAD( uint, p );
219 1498833 : ulong w = ((ulong)p0)*C1; h ^= w; h = ROTATE_LEFT( h, 23 )*C2 + C3;
220 1498833 : FD_STORE( uint, q, p0 );
221 1498833 : p += 4;
222 1498833 : q += 4;
223 1498833 : }
224 :
225 7496748 : while( p<stop ) { /* Last 1 to 3 uchar's */
226 4496748 : uchar p0 = p[0];
227 4496748 : ulong w = ((ulong)p0)*C5; h ^= w; h = ROTATE_LEFT( h, 11 )*C1;
228 4496748 : q[0] = p0;
229 4496748 : p++;
230 4496748 : q++;
231 4496748 : }
232 :
233 : /* Final avalanche */
234 3000000 : h ^= h >> 33;
235 3000000 : h *= C2;
236 3000000 : h ^= h >> 29;
237 3000000 : h *= C3;
238 3000000 : h ^= h >> 32;
239 :
240 3000000 : return h;
241 3000000 : }
242 :
243 : #undef C5
244 : #undef C4
245 : #undef C3
246 : #undef C2
247 : #undef C1
248 : #undef ROTATE_LEFT
|
