hashfunctions.c (3346B)
1 2 #include "libsheepyObject.h" 3 #include "hashfunctions.h" 4 5 /** 6 * FNV 1-a string hash. 7 */ 8 u32 strHashFNV1A(char *k) { 9 u32 hash = 2166136261U; 10 for (const u8* ptr = (const u8*)k; *ptr; ptr++) { 11 hash = (hash ^ *ptr) * 16777619U; 12 } 13 return hash; 14 } 15 16 /** 17 * FNV 1-a string 64 bit hash. 18 */ 19 u64 strHashFNV1A64(char *k) { 20 u64 hash = 14695981039346656073ULL; 21 for (const u8* ptr = (const u8*)k; *ptr; ptr++) { 22 hash = (hash ^ *ptr) * 1099511628211ULL; 23 } 24 return hash; 25 } 26 27 /** 28 * FNV 1-a buffer hash. 29 */ 30 u32 bHashFNV1A(void *k, size_t size) { 31 u32 hash = 2166136261U; 32 const u8* ptr = (const u8*)k; 33 loop(size) { 34 hash = (hash ^ *ptr) * 16777619U; 35 ptr++; 36 } 37 return hash; 38 } 39 40 /** 41 * FNV 1-a buffer 64 bit hash. 42 */ 43 u64 bHashFNV1A64(void *k, size_t size) { 44 u64 hash = 14695981039346656073ULL; 45 const u8* ptr = (const u8*)k; 46 loop(size) { 47 hash = (hash ^ *ptr) * 1099511628211ULL; 48 ptr++; 49 } 50 return hash; 51 } 52 53 /** 54 * Integer reversible hash function for 32 bits. 55 * Implementation of the Robert Jenkins "4-byte Integer Hashing", 56 * from http://burtleburtle.net/bob/hash/integer.html 57 */ 58 u32 u32Hash(u32 k) { 59 k -= k << 6; 60 k ^= k >> 17; 61 k -= k << 9; 62 k ^= k << 4; 63 k -= k << 3; 64 k ^= k << 10; 65 k ^= k >> 15; 66 return k; 67 } 68 69 /** 70 * Integer reversible hash function for 64 bits. 71 * Implementation of the Thomas Wang "Integer Hash Function", 72 * from http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm 73 */ 74 u64 u64Hash(u64 k) { 75 k = ~k + (k << 21); 76 k = k ^ (k >> 24); 77 k = k + (k << 3) + (k << 8); 78 k = k ^ (k >> 14); 79 k = k + (k << 2) + (k << 4); 80 k = k ^ (k >> 28); 81 k = k + (k << 31); 82 return k; 83 } 84 85 /** 86 * murmur2 lite 87 */ 88 u32 murmur2hash(const unsigned char *b, size_t len) 89 { 90 const u32 seed = 0xbc9f1d34; 91 const u32 m = 0xc6a4a793; 92 93 u32 h = seed ^ len * m; 94 while (len >= 4) { 95 h += b[0] | (b[1] << 8) | (b[2] << 16) | (b[3] << 24); 96 h *= m; 97 h ^= h >> 16; 98 b += 4; 99 len -= 4; 100 } 101 102 switch (len) { 103 case 3: 104 h += b[2] << 16; 105 case 2: 106 h += b[1] << 8; 107 case 1: 108 h += b[0]; 109 h *= m; 110 h ^= h >> 24; 111 } 112 return h; 113 } 114 115 /** 116 * Jump consistent hashing 117 * 118 * From the paper "A Fast, Minimal Memory, Consistent Hash Algorithm" by John Lamping, Eric Veach (2014, Google). 119 * http://arxiv.org/abs/1406.2294 120 */ 121 /* Original from paper in C style - added () around double */ 122 /* 128 bit key version? > hash key to 64bit */ 123 /* 124 int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) { 125 int64_t b = -1, j = 0; 126 while (j < num_buckets) { 127 b = j; 128 key = key * 2862933555777941757ULL + 1; 129 j = (b + 1) * ((double)(1LL << 31) / (double)((key >> 33) +1)); 130 } 131 return b; 132 } 133 */ 134 135 /** 136 * jump consistent hash 137 * 138 * \param 139 * key key to store in a bucket 140 * \param 141 * bucketCount number of buckets in the hashring 142 * \return 143 * bucket number 144 * -1 error 145 */ 146 i32 jumpConsistentHash(u64 key, i32 bucketCount) { 147 /* b for bucket, j for jump */ 148 i64 b = -1, j = 0; 149 while (j < bucketCount) { 150 b = j; 151 /* PRNG with key as seed */ 152 key = key * 2862933555777941757ULL + 1; 153 j = (b + 1) * ((f64)(1LL << 31) / (f64)((key >> 33) +1)); 154 } 155 return b; 156 } 157 158 bool checkLibsheepyVersionHashfunctions(const char *currentLibsheepyVersion) { 159 return eqG(currentLibsheepyVersion, LIBSHEEPY_VERSION); 160 } 161