lib/bloom.c

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