lib/bloom.c

   1 #include <stdlib.h>
   2
   3 #include "bloom.h"
   4 #include "../hash.h"
   5 #include "../crc/xxhash.h"
   6 #include "../crc/murmur3.h"
   7 #include "../crc/crc32c.h"
   8 #include "../crc/fnv.h"
   9
  10 struct bloom {
  11         uint64_t nentries;
  12
  13         uint32_t *map;
  14 };
  15
  16 #define BITS_PER_INDEX  (sizeof(uint32_t) * 8)
  17 #define BITS_INDEX_MASK (BITS_PER_INDEX - 1)
  18
  19 struct bloom_hash {
  20         unsigned int seed;
  21         uint32_t (*fn)(const void *, uint32_t, uint32_t);
  22 };
  23
  24 static uint32_t bloom_crc32c(const void *buf, uint32_t len, uint32_t seed)
  25 {
  26         return fio_crc32c(buf, len);
  27 }
  28
  29 static uint32_t bloom_fnv(const void *buf, uint32_t len, uint32_t seed)
  30 {
  31         return fnv(buf, len, seed);
  32 }
  33
  34 #define BLOOM_SEED      0x8989
  35
  36 static struct bloom_hash hashes[] = {
  37         {
  38                 .seed = BLOOM_SEED,
  39                 .fn = jhash,
  40         },
  41         {
  42                 .seed = BLOOM_SEED,
  43                 .fn = XXH32,
  44         },
  45         {
  46                 .seed = BLOOM_SEED,
  47                 .fn = murmurhash3,
  48         },
  49         {
  50                 .seed = BLOOM_SEED,
  51                 .fn = bloom_crc32c,
  52         },
  53         {
  54                 .seed = BLOOM_SEED,
  55                 .fn = bloom_fnv,
  56         },
  57 };
  58
  59 #define N_HASHES        5
  60
  61 struct bloom *bloom_new(uint64_t entries)
  62 {
  63         struct bloom *b;
  64         size_t no_uints;
  65
  66         crc32c_arm64_probe();
  67         crc32c_intel_probe();
  68
  69         b = malloc(sizeof(*b));
  70         b->nentries = entries;
  71         no_uints = (entries + BITS_PER_INDEX - 1) / BITS_PER_INDEX;
  72         b->map = calloc(no_uints, sizeof(uint32_t));
  73         if (!b->map) {
  74                 free(b);
  75                 return NULL;
  76         }
  77
  78         return b;
  79 }
  80
  81 void bloom_free(struct bloom *b)
  82 {
  83         free(b->map);
  84         free(b);
  85 }
  86
  87 static bool __bloom_check(struct bloom *b, const void *data, unsigned int len,
  88                           bool set)
  89 {
  90         uint32_t hash[N_HASHES];
  91         int i, was_set;
  92
  93         for (i = 0; i < N_HASHES; i++) {
  94                 hash[i] = hashes[i].fn(data, len, hashes[i].seed);
  95                 hash[i] = hash[i] % b->nentries;
  96         }
  97
  98         was_set = 0;
  99         for (i = 0; i < N_HASHES; i++) {
 100                 const unsigned int index = hash[i] / BITS_PER_INDEX;
 101                 const unsigned int bit = hash[i] & BITS_INDEX_MASK;
 102
 103                 if (b->map[index] & (1U << bit))
 104                         was_set++;
 105                 else if (set)
 106                         b->map[index] |= 1U << bit;
 107                 else
 108                         break;
 109         }
 110
 111         return was_set == N_HASHES;
 112 }
 113
 114 bool bloom_set(struct bloom *b, uint32_t *data, unsigned int nwords)
 115 {
 116         return __bloom_check(b, data, nwords * sizeof(uint32_t), true);
 117 }
 118
 119 bool bloom_string(struct bloom *b, const char *data, unsigned int len,
 120                   bool set)
 121 {
 122         return __bloom_check(b, data, len, set);
 123 }