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