hash.cc (1898B)
1 #include "hash.hh" 2 3 #include <cstdint> 4 #include <cstring> 5 6 #include "unit_tests.hh" 7 #include "assert.hh" 8 9 namespace Kakoune 10 { 11 12 [[gnu::always_inline]] 13 static inline uint32_t rotl(uint32_t x, int8_t r) 14 { 15 return (x << r) | (x >> (32 - r)); 16 } 17 18 [[gnu::always_inline]] 19 static inline uint32_t fmix(uint32_t h) 20 { 21 h ^= h >> 16; 22 h *= 0x85ebca6b; 23 h ^= h >> 13; 24 h *= 0xc2b2ae35; 25 h ^= h >> 16; 26 27 return h; 28 } 29 30 // based on https://github.com/PeterScott/murmur3 31 size_t murmur3(const char* input, size_t len) 32 { 33 const uint8_t* data = reinterpret_cast<const uint8_t*>(input); 34 uint32_t hash = 0x1235678; 35 constexpr uint32_t c1 = 0xcc9e2d51; 36 constexpr uint32_t c2 = 0x1b873593; 37 38 const ptrdiff_t nblocks = len / 4; 39 const uint8_t* blocks = data + nblocks*4; 40 41 for (ptrdiff_t i = -nblocks; i; ++i) 42 { 43 uint32_t key; 44 key = (blocks[4*i + 3] << 24) | (blocks[4*i + 2] << 16) | (blocks[4*i + 1] << 8) | blocks[4*i]; 45 key *= c1; 46 key = rotl(key, 15); 47 key *= c2; 48 49 hash ^= key; 50 hash = rotl(hash, 13); 51 hash = hash * 5 + 0xe6546b64; 52 } 53 54 const uint8_t* tail = data + nblocks * 4; 55 uint32_t key = 0; 56 switch (len & 0b11) 57 { 58 case 3: key ^= tail[2] << 16; [[fallthrough]]; 59 case 2: key ^= tail[1] << 8; [[fallthrough]]; 60 case 1: key ^= tail[0]; 61 key *= c1; 62 key = rotl(key,15); 63 key *= c2; 64 hash ^= key; 65 } 66 67 hash ^= len; 68 hash = fmix(hash); 69 70 return hash; 71 } 72 73 UnitTest test_murmur_hash{[] { 74 { 75 constexpr char data[] = "Hello, World!"; 76 kak_assert(murmur3(data, strlen(data)) == 0xf816f95b); 77 } 78 { 79 constexpr char data[] = "xxxxxxxxxxxxxxxxxxxxxxxxxxxx"; 80 kak_assert(murmur3(data, strlen(data)) == 3551113186); 81 } 82 kak_assert(murmur3("", 0) == 2572747774); 83 }}; 84 85 }