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 :
6 11620154 : #define ROTATE_LEFT(x,r) (((x)<<(r)) | ((x)>>(64-(r))))
7 11632488 : #define C1 (11400714785074694791UL)
8 11611472 : #define C2 (14029467366897019727UL)
9 6379 : #define C3 ( 1609587929392839161UL)
10 27167 : #define C4 ( 9650029242287828579UL)
11 288 : #define C5 ( 2870177450012600261UL)
12 :
13 : ulong
14 : fd_hash( ulong seed,
15 : void const * buf,
16 6303 : ulong sz ) {
17 6303 : uchar const * p = ((uchar const *)buf);
18 6303 : uchar const * stop = p + sz;
19 :
20 6303 : ulong h;
21 :
22 6303 : if( sz<32 ) h = seed + C5;
23 6167 : else {
24 6167 : uchar const * stop32 = stop - 32;
25 6167 : ulong w = seed + (C1+C2);
26 6167 : ulong x = seed + C2;
27 6167 : ulong y = seed;
28 6167 : ulong z = seed - C1;
29 :
30 2891398 : do { /* All complete blocks of 32 */
31 2891398 : w += FD_LOAD( ulong, p )*C2; w = ROTATE_LEFT( w, 31 ); w *= C1;
32 2891398 : x += FD_LOAD( ulong, p+ 8 )*C2; x = ROTATE_LEFT( x, 31 ); x *= C1;
33 2891398 : y += FD_LOAD( ulong, p+16 )*C2; y = ROTATE_LEFT( y, 31 ); y *= C1;
34 2891398 : z += FD_LOAD( ulong, p+24 )*C2; z = ROTATE_LEFT( z, 31 ); z *= C1;
35 2891398 : p += 32;
36 2891398 : } while( p<=stop32 );
37 :
38 6167 : h = ROTATE_LEFT( w, 1 ) + ROTATE_LEFT( x, 7 ) + ROTATE_LEFT( y, 12 ) + ROTATE_LEFT( z, 18 );
39 :
40 6167 : w *= C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = h*C1 + C4;
41 6167 : x *= C2; x = ROTATE_LEFT( x, 31 ); x *= C1; h ^= x; h = h*C1 + C4;
42 6167 : y *= C2; y = ROTATE_LEFT( y, 31 ); y *= C1; h ^= y; h = h*C1 + C4;
43 6167 : z *= C2; z = ROTATE_LEFT( z, 31 ); z *= C1; h ^= z; h = h*C1 + C4;
44 6167 : }
45 :
46 6303 : h += ((ulong)sz);
47 :
48 8802 : while( (p+8)<=stop ) { /* Last 1 to 3 complete ulong's */
49 2499 : ulong w = FD_LOAD( ulong, p );
50 2499 : w *= C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = ROTATE_LEFT( h, 27 )*C1 + C4;
51 2499 : p += 8;
52 2499 : }
53 :
54 6303 : if( (p+4)<=stop ) { /* Last complete uint */
55 76 : ulong w = ((ulong)FD_LOAD( uint, p ));
56 76 : w *= C1; h ^= w; h = ROTATE_LEFT( h, 23 )*C2 + C3;
57 76 : p += 4;
58 76 : }
59 :
60 6455 : while( p<stop ) { /* Last 1 to 3 uchar's */
61 152 : ulong w = ((ulong)(p[0]));
62 152 : w *= C5; h ^= w; h = ROTATE_LEFT( h, 11 )*C1;
63 152 : p++;
64 152 : }
65 :
66 : /* Final avalanche */
67 6303 : h ^= h >> 33;
68 6303 : h *= C2;
69 6303 : h ^= h >> 29;
70 6303 : h *= C3;
71 6303 : h ^= h >> 32;
72 :
73 6303 : return h;
74 6303 : }
75 :
76 : ulong
77 : fd_hash_memcpy( ulong seed,
78 : void * FD_RESTRICT dst,
79 : void const * FD_RESTRICT src,
80 0 : ulong sz ) {
81 0 : uchar * FD_RESTRICT q = ((uchar *)dst);
82 0 : uchar const * FD_RESTRICT p = ((uchar const *)src);
83 0 : uchar const * FD_RESTRICT stop = p + sz;
84 :
85 0 : ulong h;
86 :
87 0 : if( sz<32 ) h = seed + C5;
88 0 : else {
89 0 : uchar const * FD_RESTRICT stop32 = stop - 32;
90 0 : ulong w = seed + (C1+C2);
91 0 : ulong x = seed + C2;
92 0 : ulong y = seed;
93 0 : ulong z = seed - C1;
94 :
95 0 : do { /* All complete blocks of 32 */
96 0 : ulong p0 = FD_LOAD( ulong, p );
97 0 : ulong p1 = FD_LOAD( ulong, p+ 8 );
98 0 : ulong p2 = FD_LOAD( ulong, p+16 );
99 0 : ulong p3 = FD_LOAD( ulong, p+24 );
100 0 : w += p0*C2; w = ROTATE_LEFT( w, 31 ); w *= C1;
101 0 : x += p1*C2; x = ROTATE_LEFT( x, 31 ); x *= C1;
102 0 : y += p2*C2; y = ROTATE_LEFT( y, 31 ); y *= C1;
103 0 : z += p3*C2; z = ROTATE_LEFT( z, 31 ); z *= C1;
104 0 : FD_STORE( ulong, q, p0 );
105 0 : FD_STORE( ulong, q+ 8, p1 );
106 0 : FD_STORE( ulong, q+16, p2 );
107 0 : FD_STORE( ulong, q+24, p3 );
108 0 : p += 32;
109 0 : q += 32;
110 0 : } while( p<=stop32 );
111 :
112 0 : h = ROTATE_LEFT( w, 1 ) + ROTATE_LEFT( x, 7 ) + ROTATE_LEFT( y, 12 ) + ROTATE_LEFT( z, 18 );
113 :
114 0 : w *= C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = h*C1 + C4;
115 0 : x *= C2; x = ROTATE_LEFT( x, 31 ); x *= C1; h ^= x; h = h*C1 + C4;
116 0 : y *= C2; y = ROTATE_LEFT( y, 31 ); y *= C1; h ^= y; h = h*C1 + C4;
117 0 : z *= C2; z = ROTATE_LEFT( z, 31 ); z *= C1; h ^= z; h = h*C1 + C4;
118 0 : }
119 :
120 0 : h += ((ulong)sz);
121 :
122 0 : while( (p+8)<=stop ) { /* Last 1 to 3 complete ulong's */
123 0 : ulong p0 = FD_LOAD( ulong, p );
124 0 : ulong w = p0*C2; w = ROTATE_LEFT( w, 31 ); w *= C1; h ^= w; h = ROTATE_LEFT( h, 27 )*C1 + C4;
125 0 : FD_STORE( ulong, q, p0 );
126 0 : p += 8;
127 0 : q += 8;
128 0 : }
129 :
130 0 : if( (p+4)<=stop ) { /* Last complete uint */
131 0 : uint p0 = FD_LOAD( uint, p );
132 0 : ulong w = ((ulong)p0)*C1; h ^= w; h = ROTATE_LEFT( h, 23 )*C2 + C3;
133 0 : FD_STORE( uint, q, p0 );
134 0 : p += 4;
135 0 : q += 4;
136 0 : }
137 :
138 0 : while( p<stop ) { /* Last 1 to 3 uchar's */
139 0 : uchar p0 = p[0];
140 0 : ulong w = ((ulong)p0)*C5; h ^= w; h = ROTATE_LEFT( h, 11 )*C1;
141 0 : q[0] = p0;
142 0 : p++;
143 0 : q++;
144 0 : }
145 :
146 : /* Final avalanche */
147 0 : h ^= h >> 33;
148 0 : h *= C2;
149 0 : h ^= h >> 29;
150 0 : h *= C3;
151 0 : h ^= h >> 32;
152 :
153 0 : return h;
154 0 : }
155 :
156 : #undef C5
157 : #undef C4
158 : #undef C3
159 : #undef C2
160 : #undef C1
161 : #undef ROTATE_LEFT
|
