1 /*
2  *  Copyright (c) 2012-2019, Jyri J. Virkki
3  *  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are
7  * met:
8  * 
9  * 1. Redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer.
11  * 
12  * 2. Redistributions in binary form must reproduce the above copyright
13  * notice, this list of conditions and the following disclaimer in the
14  * documentation and/or other materials provided with the distribution.
15  * 
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 /* Obtained from https://github.com/jvirkki/libbloom */
30 
31 /*
32  * Refer to bloom.h for documentation on the public interfaces.
33  */
34 
35 #include <assert.h>
36 #include <fcntl.h>
37 #include <math.h>
38 #include <stdint.h>
39 #include <stdio.h>
40 #include <stdlib.h>
41 #include <string.h>
42 #include <sys/stat.h>
43 #include <sys/types.h>
44 #include <unistd.h>
45 
46 #include "bloom.h"
47 #include "murmurhash2.h"
48 
49 #define MAKESTRING(n) STRING(n)
50 #define STRING(n) #n
51 
52 
53 inline static int test_bit_set_bit(unsigned char * buf,
54                                    unsigned int x, int set_bit)
55 {
56   unsigned int byte = x >> 3;
57   unsigned char c = buf[byte];        // expensive memory access
58   unsigned int mask = 1 << (x % 8);
59 
60   if (c & mask) {
61     return 1;
62   } else {
63     if (set_bit) {
64       buf[byte] = c | mask;
65     }
66     return 0;
67   }
68 }
69 
70 
71 static int bloom_check_add(struct bloom * bloom,
72                            const void * buffer, int len, int add)
73 {
74   if (bloom->ready == 0) {
75     printf("bloom at %p not initialized!\n", (void *)bloom);
76     return -1;
77   }
78 
79   int hits = 0;
80   register unsigned int a = murmurhash2(buffer, len, bloom->seed);
81   register unsigned int b = murmurhash2(buffer, len, a);
82   register unsigned int x;
83   register unsigned int i;
84 
85   for (i = 0; i < bloom->hashes; i++) {
86     x = (a + i*b) % bloom->bits;
87     if (test_bit_set_bit(bloom->bf, x, add)) {
88       hits++;
89     } else if (!add) {
90       // Don't care about the presence of all the bits. Just our own.
91       return 0;
92     }
93   }
94 
95   if (hits == bloom->hashes) {
96     return 1;                // 1 == element already in (or collision)
97   }
98 
99   return 0;
100 }
101 
102 
103 int bloom_init_size(struct bloom * bloom, int entries, double error,
104                     unsigned int cache_size)
105 {
106   return bloom_init(bloom, entries, error);
107 }
108 
109 
110 int bloom_init(struct bloom * bloom, int entries, double error)
111 {
112   bloom->ready = 0;
113 
114   bloom->seed = arc4random();
115 
116   if (entries < 1000 || error == 0) {
117     return 1;
118   }
119 
120   bloom->entries = entries;
121   bloom->error = error;
122 
123   double num = log(bloom->error);
124   double denom = 0.480453013918201; // ln(2)^2
125   bloom->bpe = -(num / denom);
126 
127   double dentries = (double)entries;
128   bloom->bits = (int)(dentries * bloom->bpe);
129 
130   if (bloom->bits % 8) {
131     bloom->bytes = (bloom->bits / 8) + 1;
132   } else {
133     bloom->bytes = bloom->bits / 8;
134   }
135 
136   bloom->hashes = (int)ceil(0.693147180559945 * bloom->bpe);  // ln(2)
137 
138   bloom->bf = (unsigned char *)calloc(bloom->bytes, sizeof(unsigned char));
139   if (bloom->bf == NULL) {                                   // LCOV_EXCL_START
140     return 1;
141   }                                                          // LCOV_EXCL_STOP
142 
143   bloom->ready = 1;
144   return 0;
145 }
146 
147 
148 int bloom_check(struct bloom * bloom, const void * buffer, int len)
149 {
150   return bloom_check_add(bloom, buffer, len, 0);
151 }
152 
153 
154 int bloom_add(struct bloom * bloom, const void * buffer, int len)
155 {
156   return bloom_check_add(bloom, buffer, len, 1);
157 }
158 
159 
160 void bloom_print(struct bloom * bloom)
161 {
162   printf("bloom at %p\n", (void *)bloom);
163   printf(" ->entries = %d\n", bloom->entries);
164   printf(" ->error = %f\n", bloom->error);
165   printf(" ->bits = %d\n", bloom->bits);
166   printf(" ->bits per elem = %f\n", bloom->bpe);
167   printf(" ->bytes = %d\n", bloom->bytes);
168   printf(" ->hash functions = %d\n", bloom->hashes);
169 }
170 
171 
172 void bloom_free(struct bloom * bloom)
173 {
174   if (bloom->ready) {
175     free(bloom->bf);
176   }
177   bloom->ready = 0;
178 }
179 
180 
181 int bloom_reset(struct bloom * bloom)
182 {
183   if (!bloom->ready) return 1;
184   memset(bloom->bf, 0, bloom->bytes);
185   return 0;
186 }