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