Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_gossip_fd_bloom_h
       2             : #define HEADER_fd_src_flamenco_gossip_fd_bloom_h
       3             : 
       4             : #include "../../util/rng/fd_rng.h"
       5             : 
       6             : #include <math.h>
       7             : 
       8           0 : #define FD_BLOOM_ALIGN     (64UL)
       9             : #define FD_BLOOM_FOOTPRINT (128UL)
      10             : 
      11           0 : #define FD_BLOOM_MAGIC (0xF17EDA2CE8100800) /* FIREDANCE BLOOM V0 */
      12             : 
      13             : struct __attribute__((aligned(FD_BLOOM_ALIGN))) fd_bloom_private {
      14             :   ulong * keys;
      15             :   ulong   keys_len;  /* ulong count */
      16             : 
      17             :   ulong * bits;
      18             :   ulong   bits_len;  /* bit count */
      19             : 
      20             :   ulong   hash_seed;
      21             :   fd_rng_t * rng;
      22             : 
      23             :   ulong   max_bits;
      24             :   double  false_positive_rate;
      25             : 
      26             :   ulong magic; /* ==FD_BLOOM_MAGIC */
      27             : };
      28             : 
      29             : typedef struct fd_bloom_private fd_bloom_t;
      30             : 
      31             : FD_PROTOTYPES_BEGIN
      32             : 
      33             : FD_FN_CONST ulong
      34             : fd_bloom_align( void );
      35             : 
      36             : FD_FN_CONST ulong
      37             : fd_bloom_footprint( double false_positive_rate,
      38             :                     ulong  max_bits );
      39             : 
      40             : void *
      41             : fd_bloom_new( void *     shmem,
      42             :               fd_rng_t * rng,
      43             :               double     false_positive_rate,
      44             :               ulong      max_bits );
      45             : 
      46             : fd_bloom_t *
      47             : fd_bloom_join( void * shbloom );
      48             : 
      49             : void
      50             : fd_bloom_initialize( fd_bloom_t * bloom,
      51             :                      ulong        num_items );
      52             : 
      53             : void
      54             : fd_bloom_insert( fd_bloom_t *  bloom,
      55             :                  uchar const * key,
      56             :                  ulong         key_sz );
      57             : 
      58             : /* fd_bloom_insert8 inserts up to 8 32 byte elements stored contiguously
      59             :    at ele (8*32 bytes are read).  Element i is inserted if bit i of
      60             :    lanes is set.  Sets the same bits as calling fd_bloom_insert on each
      61             :    inserted element. */
      62             : 
      63             : void
      64             : fd_bloom_insert8( fd_bloom_t *  bloom,
      65             :                   uchar const * ele,
      66             :                   uint          lanes );
      67             : 
      68             : /* fd_bloom_insert16 sets the same bits as fd_bloom_insert8 of ele_a
      69             :    then of ele_b, hashing both blocks with interleaved chains. */
      70             : 
      71             : void
      72             : fd_bloom_insert16( fd_bloom_t *  bloom,
      73             :                    uchar const * ele_a,
      74             :                    uint          lanes_a,
      75             :                    uchar const * ele_b,
      76             :                    uint          lanes_b );
      77             : 
      78             : int
      79             : fd_bloom_contains( fd_bloom_t *  bloom,
      80             :                    uchar const * key,
      81             :                    ulong         key_sz );
      82             : 
      83             : /* fd_bloom_contains8 tests the 8 32 byte elements stored contiguously
      84             :    at ele (8*32 bytes are read) and returns the bit set of those bloom
      85             :    contains: bit i is fd_bloom_contains( bloom, ele+32*i, 32 ). */
      86             : 
      87             : uint
      88             : fd_bloom_contains8( fd_bloom_t const * bloom,
      89             :                     uchar const *      ele );
      90             : 
      91             : /* fd_bloom_contains_multi tests one key against cnt (<=32) blooms and
      92             :    returns the bit set of those that contain it: bit i is
      93             :    fd_bloom_contains( blooms[i], key, key_sz ).  The key is hashed once
      94             :    under every bloom's keys. */
      95             : 
      96             : uint
      97             : fd_bloom_contains_multi( fd_bloom_t * const * blooms,
      98             :                          ulong                cnt,
      99             :                          uchar const *        key,
     100             :                          ulong                key_sz );
     101             : 
     102             : int
     103             : fd_bloom_init_inplace( ulong *      keys,
     104             :                        ulong *      bits,
     105             :                        ulong        keys_len,
     106             :                        ulong        bits_len,
     107             :                        ulong        hash_seed,
     108             :                        fd_rng_t *   rng,
     109             :                        double       false_positive_rate,
     110             :                        fd_bloom_t * out_bloom );
     111             : 
     112             : static inline double
     113             : fd_bloom_max_items( double max_bits,
     114             :                     double num_keys,
     115           0 :                     double false_positive_rate ) {
     116           0 :   return ceil( max_bits / ( -num_keys / log( 1.0 - exp( log( false_positive_rate ) / num_keys ) )));
     117           0 : }
     118             : 
     119             : static inline ulong
     120             : fd_bloom_num_bits( double num_items,
     121             :                    double false_positive_rate,
     122           0 :                    double max_bits ) {
     123           0 :   double num_bits = ceil( ((double)num_items * log( false_positive_rate )) / log( 1.0 / pow( 2.0, log( 2.0 ) )));
     124           0 :   return (ulong)fmax( 1.0, fmin( max_bits, num_bits ) );
     125           0 : }
     126             : 
     127             : /* Compute optimal number of bloom hash functions for a given number of
     128             :    bits and items.  Matches Agave's Bloom::num_keys. */
     129             : 
     130             : static inline ulong
     131             : fd_bloom_num_keys( double num_bits,
     132           0 :                    double num_items ) {
     133           0 :   if( num_items==0.0 ) return 0UL;
     134           0 :   return (ulong)fmax( 1.0, round( (num_bits / num_items) * log( 2.0 ) ) );
     135           0 : }
     136             : 
     137             : FD_PROTOTYPES_END
     138             : 
     139             : #endif /* HEADER_fd_src_flamenco_gossip_fd_bloom_h */