fd.c: Avoid gcc warning regarding fchdir().
[adu.git] / bloom.c
1 /*
2 * Copyright (C) 2008 Andre Noll <maan@tuebingen.mpg.de>
3 *
4 * Licensed under the GPL v2. For licencing details see COPYING.
5 */
6
7 /** \file bloom.c Simple bloom filter implementation. */
8
9 #include "adu.h"
10 #include "string.h"
11 #include "bloom.h"
12
13 #ifdef TEST_BLOOM
14 void *adu_calloc(size_t size)
15 {
16 void *ret = malloc(size);
17
18 if (!ret)
19 exit(EXIT_FAILURE);
20 memset(ret, 0, size);
21 return ret;
22 }
23 #undef INFO_LOG
24 #define INFO_LOG printf
25 #endif
26
27 static inline uint64_t filter_bits(struct bloom *b)
28 {
29 return 1ULL << b->order;
30 }
31
32 /*
33 * SuperFastHash, by Paul Hsieh.
34 * http://www.azillionmonkeys.com/qed/hash.html
35 */
36
37 /** \cond */
38 #if (defined(__GNUC__) && defined(__i386__))
39 #define get16bits(d) (*((const uint16_t *) (d)))
40 #else
41 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
42 +(uint32_t)(((const uint8_t *)(d))[0]) )
43 #endif
44 /** \endcond */
45
46 static uint32_t super_fast_hash(const uint8_t *data, uint32_t len, uint32_t hash)
47 {
48 uint32_t tmp;
49 int rem = len & 3;
50
51 len >>= 2;
52
53 for (;len > 0; len--) {
54 hash += get16bits (data);
55 tmp = (get16bits (data+2) << 11) ^ hash;
56 hash = (hash << 16) ^ tmp;
57 data += 2*sizeof (uint16_t);
58 hash += hash >> 11;
59 }
60
61 /* Handle end cases */
62 switch (rem) {
63 case 3:
64 hash += get16bits (data);
65 hash ^= hash << 16;
66 hash ^= data[sizeof (uint16_t)] << 18;
67 hash += hash >> 11;
68 break;
69 case 2:
70 hash += get16bits (data);
71 hash ^= hash << 11;
72 hash += hash >> 17;
73 break;
74 case 1:
75 hash += *data;
76 hash ^= hash << 10;
77 hash += hash >> 1;
78 }
79 /* Force "avalanching" of final 127 bits */
80 hash ^= hash << 3;
81 hash += hash >> 5;
82 hash ^= hash << 4;
83 hash += hash >> 17;
84 hash ^= hash << 25;
85 hash += hash >> 6;
86 return hash;
87 }
88
89 static int test_and_set_bit(uint64_t bitnum, struct bloom *b)
90 {
91 uint64_t byte = bitnum / 8;
92 uint8_t bit = 1 << (bitnum % 8);
93 int ret = b->filter[byte] & bit;
94
95 b->filter[byte] |= bit;
96
97 if (!ret)
98 b->num_set_bits++;
99 return ret;
100 }
101
102 /**
103 * Insert data to the given bloom filter.
104 *
105 * This function computes \a k hashes from the given data where \a k is the
106 * number of hash functions of the filter \a b. Each hash value corresponds to
107 * a position in the bit array of the filter and each of these bits are being
108 * tested and set. If not all \a k bits were already set, the given data was
109 * not yet contained in the filter and the function returns non-zero.
110 *
111 * Otherwise either (a) the same data has already been inserted previously or
112 * (b) a hash collision occurred or (c) the \a k bits are set due to previous
113 * insertion of other data (i.e. a false positive occurred). It is impossible
114 * to distinguish these cases.
115 *
116 * \param data The data to insert.
117 * \param len Number of bytes of \a data.
118 * \param b The filter to insert to.
119 *
120 * \return Zero if the entry was already contained in the filter (or in case of
121 * false positives), non-zero otherwise.
122 */
123 int bloom_insert(const uint8_t *data, size_t len, struct bloom *b)
124 {
125 int i, ret = 0;
126 uint32_t h = 0xb11924e1; /* some arbitrary value */
127
128 for (i = 1; i < b->num_hash_functions; i++) {
129 uint64_t bitnum = super_fast_hash(data, len, h);
130 h = bitnum;
131 if (b->order > 32) {
132 bitnum = bitnum << 32;
133 h = super_fast_hash(data, len, h);
134 bitnum |= h;
135 }
136 bitnum &= filter_bits(b) - 1;
137 ret |= !test_and_set_bit(bitnum, b);
138 }
139 if (ret)
140 b->num_entries++;
141 return !ret;
142 }
143
144 /**
145 * Deallocate a bloom filter.
146 *
147 * \param b The filter to deallocate.
148 */
149 void bloom_free(struct bloom *b)
150 {
151 if (!b)
152 return;
153 free(b->filter);
154 free(b);
155 }
156
157 /**
158 * Allocate and initialize a new bloom filter.
159 *
160 * \param order Use a filter containing 2^order bits.
161 * \param num_hash_functions Set that many bits in the filter per entry.
162 *
163 * \return This function either returns a freshly allocated and initialized
164 * bloom filter or does not return at all (if the underlying malloc() failed).
165 */
166 struct bloom *bloom_new(unsigned order, unsigned num_hash_functions)
167 {
168 struct bloom *b = adu_calloc(sizeof(*b));
169
170 INFO_LOG("allocating bloom filter (order: %u, %u hash functions)\n",
171 order, num_hash_functions);
172 b->order = order;
173 b->num_hash_functions = num_hash_functions;
174 b->filter = adu_calloc(filter_bits(b) / 8);
175 return b;
176 }
177
178 #ifdef TEST_BLOOM
179
180 int bloom_insert_string(const char *str, struct bloom *b)
181 {
182 uint32_t len = strlen(str);
183
184 return bloom_insert((const uint8_t *)str, len, b);
185 }
186
187 void add_stdin(struct bloom *b)
188 {
189 char buf[255];
190 unsigned false_positives = 0;
191
192 while (fgets(buf, sizeof(buf) - 1, stdin)) {
193 size_t len = strlen(buf);
194 if (!len)
195 continue;
196 if (buf[len - 1] == '\n')
197 buf[len - 1] = '\0';
198 if (bloom_insert_string(buf, b))
199 false_positives++;
200 }
201 INFO_LOG("filter contains %llu entries\n", b->num_entries);
202 printf("%u possible false positives\n", false_positives);
203 }
204
205 int main(int argc, char **argv)
206 {
207 struct bloom *b;
208
209 if (argc != 3) {
210 printf("usage: $0 j k\n");
211 printf("j: set bloom filter size to m=2^j bits\n");
212 printf("k: # of hash functions to use\n");
213 exit(1);
214 }
215 b = bloom_new(atoi(argv[1]), atoi(argv[2]));
216 add_stdin(b);
217 INFO_LOG("%u%% of bits are set\n", (unsigned)
218 (b->num_set_bits * 100ULL / filter_bits(b)));
219 return 1;
220 }
221
222 #endif /* TEST_BLOOM */