💾 Archived View for gmi.noulin.net › gitRepositories › hashfunctions › file › hashfunctions.c.gmi captured on 2023-07-10 at 15:54:55. Gemini links have been rewritten to link to archived content

View Raw

More Information

⬅️ Previous capture (2023-01-29)

-=-=-=-=-=-=-

hashfunctions

Log

Files

Refs

LICENSE

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