Merge branch 'arm-detect-pmull' of https://github.com/sitsofe/fio
[fio.git] / 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 }