Line data Source code
1 : #include "fd_bloom.h"
2 :
3 : #include "../../util/log/fd_log.h"
4 :
5 : #include <math.h>
6 :
7 : static const double FD_BLOOM_LN_2 = 0.69314718055994530941723212145818;
8 : static ulong
9 : fnv_hasher( uchar const * ele,
10 : ulong ele_sz,
11 60 : ulong key ) {
12 846 : for( ulong i=0UL; i<ele_sz; i++ ) {
13 786 : key ^= (ulong)ele[i];
14 786 : key *= 1099511628211UL; /* FNV prime */
15 786 : }
16 60 : return key;
17 60 : }
18 :
19 : FD_FN_CONST ulong
20 1830 : fd_bloom_align( void ) {
21 1830 : return FD_BLOOM_ALIGN;
22 1830 : }
23 :
24 : FD_FN_CONST ulong
25 : fd_bloom_footprint( double false_positive_rate,
26 15 : ulong max_bits ) {
27 15 : if( FD_UNLIKELY( false_positive_rate<=0.0 ) ) return 0UL;
28 15 : if( FD_UNLIKELY( false_positive_rate>=1.0 ) ) return 0UL;
29 :
30 15 : if( FD_UNLIKELY( max_bits<1UL || max_bits>32768UL ) ) return 0UL;
31 :
32 15 : ulong num_keys = (ulong)( round( (double)max_bits*FD_BLOOM_LN_2 ) );
33 :
34 15 : ulong l;
35 15 : l = FD_LAYOUT_INIT;
36 15 : l = FD_LAYOUT_APPEND( l, FD_BLOOM_ALIGN, sizeof(fd_bloom_t) );
37 15 : l = FD_LAYOUT_APPEND( l, 8UL, num_keys*sizeof(ulong) );
38 15 : l = FD_LAYOUT_APPEND( l, 8UL, (max_bits+7UL)/8UL );
39 15 : return FD_LAYOUT_FINI( l, FD_BLOOM_ALIGN );
40 15 : }
41 :
42 : void *
43 : fd_bloom_new( void * shmem,
44 : fd_rng_t * rng,
45 : double false_positive_rate,
46 909 : ulong max_bits ) {
47 :
48 909 : if( FD_UNLIKELY( !shmem ) ) {
49 0 : FD_LOG_WARNING(( "NULL shmem" ));
50 0 : return NULL;
51 0 : }
52 :
53 909 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_bloom_align() ) ) ) {
54 0 : FD_LOG_WARNING(( "misaligned shmem" ));
55 0 : return NULL;
56 0 : }
57 :
58 909 : if( FD_UNLIKELY( false_positive_rate<=0.0 ) ) return NULL;
59 909 : if( FD_UNLIKELY( false_positive_rate>=1.0 ) ) return NULL;
60 :
61 909 : if( FD_UNLIKELY( max_bits<1UL || max_bits>32768UL ) ) return NULL;
62 :
63 909 : if( FD_UNLIKELY( !rng ) ) return NULL;
64 :
65 909 : ulong num_keys = (ulong)( round( (double)max_bits*FD_BLOOM_LN_2 ) );
66 :
67 909 : FD_SCRATCH_ALLOC_INIT( l, shmem );
68 909 : fd_bloom_t * bloom = FD_SCRATCH_ALLOC_APPEND( l, FD_BLOOM_ALIGN, sizeof(fd_bloom_t) );
69 909 : void * _keys = FD_SCRATCH_ALLOC_APPEND( l, 8UL, num_keys*sizeof(ulong) );
70 909 : void * _bits = FD_SCRATCH_ALLOC_APPEND( l, 8UL, (max_bits+7UL)/8UL );
71 :
72 0 : bloom->keys = (ulong *)_keys;
73 909 : bloom->keys_len = 0UL;
74 909 : bloom->bits = (ulong *)_bits;
75 909 : bloom->bits_len = 0UL;
76 :
77 909 : bloom->hash_seed = 0UL;
78 909 : bloom->rng = rng;
79 :
80 909 : bloom->false_positive_rate = false_positive_rate;
81 909 : bloom->max_bits = max_bits;
82 :
83 909 : FD_COMPILER_MFENCE();
84 909 : FD_VOLATILE( bloom->magic ) = FD_BLOOM_MAGIC;
85 909 : FD_COMPILER_MFENCE();
86 :
87 909 : return (void *)bloom;
88 909 : }
89 :
90 : fd_bloom_t *
91 909 : fd_bloom_join( void * shbloom ) {
92 909 : if( FD_UNLIKELY( !shbloom ) ) {
93 0 : FD_LOG_WARNING(( "NULL shbloom" ));
94 0 : return NULL;
95 0 : }
96 :
97 909 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shbloom, fd_bloom_align() ) ) ) {
98 0 : FD_LOG_WARNING(( "misaligned shbloom" ));
99 0 : return NULL;
100 0 : }
101 :
102 909 : fd_bloom_t * bloom = (fd_bloom_t *)shbloom;
103 :
104 909 : if( FD_UNLIKELY( bloom->magic!=FD_BLOOM_MAGIC ) ) {
105 0 : FD_LOG_WARNING(( "bad magic" ));
106 0 : return NULL;
107 0 : }
108 :
109 909 : return bloom;
110 909 : }
111 :
112 : void
113 : fd_bloom_initialize( fd_bloom_t * bloom,
114 18 : ulong num_items ) {
115 18 : double num_bits = ceil( ((double)num_items * log( bloom->false_positive_rate )) / log( 1.0 / pow( 2.0, log( 2.0 ) ) ) );
116 18 : num_bits = fmax( 1.0, fmin( (double)bloom->max_bits, num_bits ) );
117 :
118 18 : ulong num_keys;
119 18 : if( FD_UNLIKELY( num_items == 0UL ) ) {
120 3 : num_keys = 0UL;
121 15 : } else {
122 15 : num_keys = fd_ulong_max( 1UL, (ulong)( round( ((double)num_bits/(double)num_items) * FD_BLOOM_LN_2 ) ) );
123 15 : }
124 66 : for( ulong i=0UL; i<num_keys; i++ ) bloom->keys[ i ] = fd_rng_ulong( bloom->rng );
125 :
126 18 : bloom->keys_len = num_keys;
127 18 : bloom->bits_len = (ulong)num_bits;
128 18 : fd_memset( bloom->bits, 0, (ulong)((num_bits+7UL)/8UL) );
129 18 : }
130 :
131 : void
132 : fd_bloom_insert( fd_bloom_t * bloom,
133 : uchar const * key,
134 9 : ulong key_sz ) {
135 36 : for( ulong i=0UL; i<bloom->keys_len; i++ ) {
136 27 : ulong bit = fnv_hasher( key, key_sz, bloom->keys[ i ] ) % bloom->bits_len;
137 27 : bloom->bits[ bit / 64UL ] |= (1UL << (bit % 64UL));
138 27 : }
139 9 : }
140 :
141 : int
142 : fd_bloom_contains( fd_bloom_t * bloom,
143 : uchar const * key,
144 15 : ulong key_sz ) {
145 42 : for( ulong i=0UL; i<bloom->keys_len; i++ ) {
146 33 : ulong bit = fnv_hasher( key, key_sz, bloom->keys[ i ]) % bloom->bits_len;
147 33 : if( !(bloom->bits[ bit / 64UL ] & (1UL << (bit % 64UL))) ) {
148 6 : return 0;
149 6 : }
150 33 : }
151 9 : return 1;
152 15 : }
153 :
154 : int
155 : fd_bloom_init_inplace( ulong * keys,
156 : ulong * bits,
157 : ulong keys_len,
158 : ulong bits_len,
159 : ulong hash_seed,
160 : fd_rng_t * rng,
161 : double false_positive_rate,
162 0 : fd_bloom_t * out_bloom ) {
163 0 : if( FD_UNLIKELY( !keys || !bits || !out_bloom ) ) {
164 0 : FD_LOG_ERR(( "NULL keys, bits or out_bloom" ));
165 0 : return -1;
166 0 : }
167 0 : out_bloom->keys = keys;
168 0 : for( ulong i=0UL; i<keys_len; i++ ) out_bloom->keys[ i ] = fd_rng_ulong( rng );
169 :
170 0 : out_bloom->keys_len = keys_len;
171 0 : out_bloom->bits = bits;
172 0 : out_bloom->bits_len = bits_len;
173 0 : out_bloom->hash_seed = hash_seed;
174 0 : out_bloom->rng = rng;
175 0 : out_bloom->false_positive_rate = false_positive_rate;
176 0 : out_bloom->max_bits = bits_len;
177 :
178 0 : return 0;
179 0 : }
|
