suricata
util-bloomfilter.c
Go to the documentation of this file.
1 /* Copyright (C) 2007-2010 Open Information Security Foundation
2  *
3  * You can copy, redistribute or modify this Program under the terms of
4  * the GNU General Public License version 2 as published by the Free
5  * Software Foundation.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * version 2 along with this program; if not, write to the Free Software
14  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
15  * 02110-1301, USA.
16  */
17 
18 /**
19  * \file
20  *
21  * \author Victor Julien <victor@inliniac.net>
22  *
23  * Bitwise bloom filter implementation
24  */
25 
26 #include "suricata-common.h"
27 #include "util-bloomfilter.h"
28 #include "util-unittest.h"
29 
30 BloomFilter *BloomFilterInit(uint32_t size, uint8_t iter,
31  uint32_t (*Hash)(const void *, uint16_t, uint8_t, uint32_t)) {
32  BloomFilter *bf = NULL;
33 
34  if (size == 0 || iter == 0)
35  goto error;
36 
37  if (Hash == NULL) {
38  //printf("ERROR: BloomFilterInit no Hash function\n");
39  goto error;
40  }
41 
42  /* setup the filter */
43  bf = SCMalloc(sizeof(BloomFilter));
44  if (unlikely(bf == NULL))
45  goto error;
46  memset(bf,0,sizeof(BloomFilter));
47  bf->bitarray_size = size;
48  bf->hash_iterations = iter;
49  bf->Hash = Hash;
50 
51  /* setup the bitarray */
52  bf->bitarray = SCMalloc((bf->bitarray_size/8)+1);
53  if (bf->bitarray == NULL)
54  goto error;
55  memset(bf->bitarray,0,(bf->bitarray_size/8)+1);
56 
57  return bf;
58 
59 error:
60  if (bf != NULL) {
61  if (bf->bitarray != NULL)
62  SCFree(bf->bitarray);
63 
64  SCFree(bf);
65  }
66  return NULL;
67 }
68 
70 {
71  if (bf != NULL) {
72  if (bf->bitarray != NULL)
73  SCFree(bf->bitarray);
74 
75  SCFree(bf);
76  }
77 }
78 
80 {
81  printf("\n---------- Bloom Filter Stats -----------\n");
82  printf("Buckets: %" PRIu32 "\n", bf->bitarray_size);
83  printf("Memory size: %" PRIu32 " bytes\n", bf->bitarray_size/8 + 1);
84  printf("Hash function pointer: %p\n", bf->Hash);
85  printf("Hash functions: %" PRIu32 "\n", bf->hash_iterations);
86  printf("-----------------------------------------\n");
87 }
88 
89 int BloomFilterAdd(BloomFilter *bf, const void *data, uint16_t datalen)
90 {
91  uint8_t iter = 0;
92  uint32_t hash = 0;
93 
94  if (bf == NULL || data == NULL || datalen == 0)
95  return -1;
96 
97  for (iter = 0; iter < bf->hash_iterations; iter++) {
98  hash = bf->Hash(data, datalen, iter, bf->bitarray_size);
99  bf->bitarray[hash/8] |= (1<<hash%8);
100  }
101 
102  return 0;
103 }
104 
106 {
107  if (bf == NULL)
108  return 0;
109 
110  return 2;
111 }
112 
114 {
115  if (bf == NULL)
116  return 0;
117 
118  return (sizeof(BloomFilter) + (bf->bitarray_size/8) + 1);
119 }
120 
121 /*
122  * ONLY TESTS BELOW THIS COMMENT
123  */
124 
125 #ifdef UNITTESTS
126 static uint32_t BloomFilterTestHash(const void *data, uint16_t datalen, uint8_t iter, uint32_t hash_size)
127 {
128  uint8_t *d = (uint8_t *)data;
129  uint32_t i;
130  uint32_t hash = 0;
131 
132  for (i = 0; i < datalen; i++) {
133  if (i == 0) hash += (((uint32_t)*d++));
134  else if (i == 1) hash += (((uint32_t)*d++) * datalen);
135  else hash *= (((uint32_t)*d++) * i);
136  }
137 
138  hash *= (iter + datalen);
139  hash %= hash_size;
140  return hash;
141 }
142 
143 static int BloomFilterTestInit01 (void)
144 {
145  BloomFilter *bf = BloomFilterInit(1024, 4, BloomFilterTestHash);
146  if (bf == NULL)
147  return 0;
148 
149  BloomFilterFree(bf);
150  return 1;
151 }
152 
153 /* no hash function, so it should fail */
154 static int BloomFilterTestInit02 (void)
155 {
156  BloomFilter *bf = BloomFilterInit(1024, 4, NULL);
157  if (bf == NULL)
158  return 1;
159 
160  BloomFilterFree(bf);
161  return 0;
162 }
163 
164 static int BloomFilterTestInit03 (void)
165 {
166  int result = 0;
167  BloomFilter *bf = BloomFilterInit(1024, 4, BloomFilterTestHash);
168  if (bf == NULL)
169  return 0;
170 
171  if (bf->Hash == BloomFilterTestHash)
172  result = 1;
173 
174  BloomFilterFree(bf);
175  return result;
176 }
177 
178 static int BloomFilterTestInit04 (void)
179 {
180  BloomFilter *bf = BloomFilterInit(1024, 0, BloomFilterTestHash);
181  if (bf == NULL)
182  return 1;
183 
184  BloomFilterFree(bf);
185  return 0;
186 }
187 
188 static int BloomFilterTestInit05 (void)
189 {
190  BloomFilter *bf = BloomFilterInit(0, 4, BloomFilterTestHash);
191  if (bf == NULL)
192  return 1;
193 
194  BloomFilterFree(bf);
195  return 0;
196 }
197 
198 static int BloomFilterTestAdd01 (void)
199 {
200  int result = 0;
201  BloomFilter *bf = BloomFilterInit(1024, 4, BloomFilterTestHash);
202  if (bf == NULL)
203  return 0;
204 
205  int r = BloomFilterAdd(bf, "test", 0);
206  if (r == 0)
207  goto end;
208 
209  /* all is good! */
210  result = 1;
211 end:
212  if (bf != NULL) BloomFilterFree(bf);
213  return result;
214 }
215 
216 static int BloomFilterTestAdd02 (void)
217 {
218  int result = 0;
219  BloomFilter *bf = BloomFilterInit(1024, 4, BloomFilterTestHash);
220  if (bf == NULL)
221  return 0;
222 
223  int r = BloomFilterAdd(bf, NULL, 4);
224  if (r == 0)
225  goto end;
226 
227  /* all is good! */
228  result = 1;
229 end:
230  if (bf != NULL) BloomFilterFree(bf);
231  return result;
232 }
233 
234 static int BloomFilterTestFull01 (void)
235 {
236  int result = 0;
237  BloomFilter *bf = BloomFilterInit(32, 4, BloomFilterTestHash);
238  if (bf == NULL)
239  goto end;
240 
241  int r = BloomFilterAdd(bf, "test", 4);
242  if (r != 0)
243  goto end;
244 
245  r = BloomFilterTest(bf, "test", 4);
246  if (r != 1)
247  goto end;
248 
249  /* all is good! */
250  result = 1;
251 end:
252  if (bf != NULL) BloomFilterFree(bf);
253  return result;
254 }
255 
256 static int BloomFilterTestFull02 (void)
257 {
258  int result = 0;
259  BloomFilter *bf = BloomFilterInit(32, 4, BloomFilterTestHash);
260  if (bf == NULL)
261  goto end;
262 
263  int r = BloomFilterTest(bf, "test", 4);
264  if (r != 0)
265  goto end;
266 
267  /* all is good! */
268  result = 1;
269 end:
270  if (bf != NULL) BloomFilterFree(bf);
271  return result;
272 }
273 #endif /* UNITTESTS */
274 
276 {
277 #ifdef UNITTESTS
278  UtRegisterTest("BloomFilterTestInit01", BloomFilterTestInit01);
279  UtRegisterTest("BloomFilterTestInit02", BloomFilterTestInit02);
280  UtRegisterTest("BloomFilterTestInit03", BloomFilterTestInit03);
281  UtRegisterTest("BloomFilterTestInit04", BloomFilterTestInit04);
282  UtRegisterTest("BloomFilterTestInit05", BloomFilterTestInit05);
283 
284  UtRegisterTest("BloomFilterTestAdd01", BloomFilterTestAdd01);
285  UtRegisterTest("BloomFilterTestAdd02", BloomFilterTestAdd02);
286 
287  UtRegisterTest("BloomFilterTestFull01", BloomFilterTestFull01);
288  UtRegisterTest("BloomFilterTestFull02", BloomFilterTestFull02);
289 #endif /* UNITTESTS */
290 }
291 
uint32_t BloomFilterMemoryCnt(BloomFilter *bf)
#define unlikely(expr)
Definition: util-optimize.h:35
uint32_t bitarray_size
uint32_t BloomFilterMemorySize(BloomFilter *bf)
int BloomFilterAdd(BloomFilter *bf, const void *data, uint16_t datalen)
void UtRegisterTest(const char *name, int(*TestFn)(void))
Register unit test.
void BloomFilterPrint(BloomFilter *bf)
uint8_t hash_iterations
uint32_t(* Hash)(const void *, uint16_t, uint8_t, uint32_t)
void BloomFilterRegisterTests(void)
#define SCMalloc(a)
Definition: util-mem.h:166
uint8_t * bitarray
#define SCFree(a)
Definition: util-mem.h:228
void BloomFilterFree(BloomFilter *bf)
BloomFilter * BloomFilterInit(uint32_t size, uint8_t iter, uint32_t(*Hash)(const void *, uint16_t, uint8_t, uint32_t))