nostrdb

an unfairly fast embedded nostr database backed by lmdb
git clone git://jb55.com/nostrdb
Log | Files | Refs | Submodules | README | LICENSE

hash.h (2742B)

      1 #ifndef HASH_H
      2 #define HASH_H
      3 
      4 /* Misc. hash functions that do not comply to a specific interface. */
      5 
      6 #include <stdlib.h>
      7 
      8 #ifdef _MSC_VER
      9 /* `inline` only advisory anyway. */
     10 #pragma warning(disable: 4710) /* function not inlined */
     11 #endif
     12 
     13 static inline uint32_t hash_fnv1a32_update(uint32_t seed, uint8_t *buf, size_t len)
     14 {
     15     uint8_t *p = buf;
     16 #ifndef FNV1A_NOMUL
     17     const uint64_t prime = UINT32_C(0x1000193);
     18 #endif
     19     uint64_t hash = seed;
     20 
     21     while (len--) {
     22         hash ^= (uint64_t)*p++;
     23 #ifndef FNV1A_NOMUL
     24         hash *= prime;
     25 #else
     26         hash += (hash << 1) + (hash << 4) + (hash << 7) +
     27             (hash << 8) + (hash << 24);
     28 #endif
     29     }
     30     return hash;
     31 }
     32 
     33 static inline uint32_t hash_fnv1a32(uint8_t *buf, size_t len)
     34 {
     35     return hash_fnv1a32_update(UINT32_C(0x811c9dc5), buf, len);
     36 }
     37 
     38 static inline uint64_t hash_fnv1a64_update(uint64_t v, uint8_t *buf, size_t len)
     39 {
     40     uint8_t *p = buf;
     41 #ifndef FNV1A_NOMUL
     42     const uint64_t prime = UINT64_C(0x100000001b3);
     43 #endif
     44     uint64_t hash = v;
     45 
     46     while (len--) {
     47         hash ^= (uint64_t)*p++;
     48 #ifndef FNV1A_NOMUL
     49         hash *= prime;
     50 #else
     51         hash += (hash << 1) + (hash << 4) + (hash << 5) +
     52 		    (hash << 7) + (hash << 8) + (hash << 40);
     53 #endif
     54     }
     55     return hash;
     56 }
     57 
     58 static inline uint64_t hash_fnv1a64(uint8_t *buf, size_t len)
     59 {
     60     return hash_fnv1a64_update(UINT64_C(0xcbf29ce484222325), buf, len);
     61 }
     62 
     63 /*
     64  * MurmurHash 3 final mix with seed to handle 0.
     65  *
     66  * Width is number of bits of the value to return.
     67  * http://stackoverflow.com/a/12996028
     68  */
     69 static inline uint32_t hash_bucket32(uint32_t v,  size_t width)
     70 {
     71     uint32_t x = v + UINT32_C(0x2f693b52);
     72 
     73     x = ((x >> 16) ^ x) * UINT32_C(0x45d9f3b);
     74     x = ((x >> 16) ^ x) * UINT32_C(0x45d9f3b);
     75     x = ((x >> 16) ^ x);
     76     return x >> (32 - width);
     77 }
     78 
     79 /*
     80  * SplitMix64 - can be used to disperse fnv1a hash, to hash
     81  * an integer, or as a simple non-cryptographic prng.
     82  *
     83  * Width is number of bits of the value to return.
     84  * http://stackoverflow.com/a/12996028
     85  */
     86 static inline uint64_t hash_bucket64(uint64_t v, size_t width)
     87 {
     88     uint64_t x = v + UINT64_C(0x9e3779b97f4a7c15);
     89     
     90     x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
     91     x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
     92     x = x ^ (x >> 31);
     93     return x >> (64 - width);
     94 }
     95 
     96 static inline uint64_t hash_random64(uint64_t *state)
     97 {
     98     uint64_t x;
     99 
    100     x = hash_bucket64(*state, 64);
    101     *state = x;
    102     return x;
    103 }
    104 
    105 /*
    106  * Faster, less random hash bucket compared to hash_bucket32, but works
    107  * for smaller integers.
    108  */
    109 static inline uint32_t hash_mult32(uint32_t v, size_t width)
    110 {
    111     /* Knuth's multiplicative hash. */
    112     return (v * UINT32_C(2654435761)) >> (32 - width);
    113 }
    114 
    115 #endif /* HASH_H */