kakoune

Fork of kakoune, an acceptable text editor
git clone git://git.laack.co/kakoune.git
Log | Files | Refs

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 }