Line data    Source code

       1             : #include "fd_bloom.h"
       2             : 
       3             : #include "../../util/log/fd_log.h"
       4             : #if FD_HAS_AVX512
       5             : #include "../../util/simd/fd_avx512.h"
       6             : #endif
       7             : 
       8             : #include <math.h>
       9             : 
      10             : static const double FD_BLOOM_LN_2 = 0.69314718055994530941723212145818;
      11             : FD_FN_CONST ulong
      12           0 : fd_bloom_align( void ) {
      13           0 :   return FD_BLOOM_ALIGN;
      14           0 : }
      15             : 
      16             : FD_FN_CONST ulong
      17             : fd_bloom_footprint( double false_positive_rate,
      18           0 :                     ulong  max_bits ) {
      19           0 :   if( FD_UNLIKELY( false_positive_rate<=0.0 ) ) return 0UL;
      20           0 :   if( FD_UNLIKELY( false_positive_rate>=1.0 ) ) return 0UL;
      21             : 
      22           0 :   if( FD_UNLIKELY( max_bits<1UL || max_bits>32768UL ) ) return 0UL;
      23             : 
      24           0 :   ulong num_keys = (ulong)( round( (double)max_bits*FD_BLOOM_LN_2 ) );
      25             : 
      26           0 :   ulong l;
      27           0 :   l = FD_LAYOUT_INIT;
      28           0 :   l = FD_LAYOUT_APPEND( l, FD_BLOOM_ALIGN, sizeof(fd_bloom_t) );
      29           0 :   l = FD_LAYOUT_APPEND( l, 8UL,            num_keys*sizeof(ulong) );
      30           0 :   l = FD_LAYOUT_APPEND( l, 8UL,            (max_bits+7UL)/8UL );
      31           0 :   return FD_LAYOUT_FINI( l, FD_BLOOM_ALIGN );
      32           0 : }
      33             : 
      34             : void *
      35             : fd_bloom_new( void *     shmem,
      36             :               fd_rng_t * rng,
      37             :               double     false_positive_rate,
      38           0 :               ulong      max_bits ) {
      39             : 
      40           0 :   if( FD_UNLIKELY( !shmem ) ) {
      41           0 :     FD_LOG_WARNING(( "NULL shmem" ));
      42           0 :     return NULL;
      43           0 :   }
      44             : 
      45           0 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_bloom_align() ) ) ) {
      46           0 :     FD_LOG_WARNING(( "misaligned shmem" ));
      47           0 :     return NULL;
      48           0 :   }
      49             : 
      50           0 :   if( FD_UNLIKELY( false_positive_rate<=0.0 ) ) return NULL;
      51           0 :   if( FD_UNLIKELY( false_positive_rate>=1.0 ) ) return NULL;
      52             : 
      53           0 :   if( FD_UNLIKELY( max_bits<1UL || max_bits>32768UL ) ) return NULL;
      54             : 
      55           0 :   if( FD_UNLIKELY( !rng ) ) return NULL;
      56             : 
      57           0 :   ulong num_keys = (ulong)( round( (double)max_bits*FD_BLOOM_LN_2 ) );
      58             : 
      59           0 :   FD_SCRATCH_ALLOC_INIT( l, shmem );
      60           0 :   fd_bloom_t * bloom = FD_SCRATCH_ALLOC_APPEND( l, FD_BLOOM_ALIGN, sizeof(fd_bloom_t) );
      61           0 :   void * _keys       = FD_SCRATCH_ALLOC_APPEND( l, 8UL, num_keys*sizeof(ulong) );
      62           0 :   void * _bits       = FD_SCRATCH_ALLOC_APPEND( l, 8UL, (max_bits+7UL)/8UL );
      63           0 :   FD_TEST( FD_SCRATCH_ALLOC_FINI( l, FD_BLOOM_ALIGN ) == (ulong)shmem + fd_bloom_footprint( false_positive_rate, max_bits ) );
      64             : 
      65           0 :   bloom->keys      = (ulong *)_keys;
      66           0 :   bloom->keys_len  = 0UL;
      67           0 :   bloom->bits      = (ulong *)_bits;
      68           0 :   bloom->bits_len  = 0UL;
      69             : 
      70           0 :   bloom->hash_seed = 0UL;
      71           0 :   bloom->rng       = rng;
      72             : 
      73           0 :   bloom->false_positive_rate = false_positive_rate;
      74           0 :   bloom->max_bits = max_bits;
      75             : 
      76           0 :   FD_COMPILER_MFENCE();
      77           0 :   FD_VOLATILE( bloom->magic ) = FD_BLOOM_MAGIC;
      78           0 :   FD_COMPILER_MFENCE();
      79             : 
      80           0 :   return (void *)bloom;
      81           0 : }
      82             : 
      83             : fd_bloom_t *
      84           0 : fd_bloom_join( void * shbloom ) {
      85           0 :   if( FD_UNLIKELY( !shbloom ) ) {
      86           0 :     FD_LOG_WARNING(( "NULL shbloom" ));
      87           0 :     return NULL;
      88           0 :   }
      89             : 
      90           0 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shbloom, fd_bloom_align() ) ) ) {
      91           0 :     FD_LOG_WARNING(( "misaligned shbloom" ));
      92           0 :     return NULL;
      93           0 :   }
      94             : 
      95           0 :   fd_bloom_t * bloom = (fd_bloom_t *)shbloom;
      96             : 
      97           0 :   if( FD_UNLIKELY( bloom->magic!=FD_BLOOM_MAGIC ) ) {
      98           0 :     FD_LOG_WARNING(( "bad magic" ));
      99           0 :     return NULL;
     100           0 :   }
     101             : 
     102           0 :   return bloom;
     103           0 : }
     104             : 
     105             : void
     106             : fd_bloom_initialize( fd_bloom_t * bloom,
     107           0 :                      ulong        num_items ) {
     108           0 :   double num_bits = ceil( ((double)num_items * log( bloom->false_positive_rate )) / log( 1.0 / pow( 2.0, log( 2.0 ) ) ) );
     109           0 :   num_bits = fmax( 1.0, fmin( (double)bloom->max_bits, num_bits ) );
     110             : 
     111           0 :   ulong num_keys;
     112           0 :   if( FD_UNLIKELY( num_items == 0UL ) ) {
     113           0 :     num_keys = 0UL;
     114           0 :   } else {
     115           0 :     num_keys = fd_ulong_max( 1UL, (ulong)( round( ((double)num_bits/(double)num_items) * FD_BLOOM_LN_2 ) ) );
     116           0 :   }
     117           0 :   for( ulong i=0UL; i<num_keys; i++ ) bloom->keys[ i ] = fd_rng_ulong( bloom->rng );
     118             : 
     119           0 :   bloom->keys_len = num_keys;
     120           0 :   bloom->bits_len = (ulong)num_bits;
     121           0 :   fd_memset( bloom->bits, 0, (ulong)((num_bits+7UL)/8UL) );
     122           0 : }
     123             : 
     124             : static inline ulong
     125             : fnv_hasher( uchar const * ele,
     126             :             ulong         ele_sz,
     127           0 :             ulong         key ) {
     128           0 :   for( ulong i=0UL; i<ele_sz; i++ ) key = (key^(ulong)ele[i])*1099511628211UL;
     129           0 :   return key;
     130           0 : }
     131             : 
     132             : static inline void
     133             : fnv_hasher4( uchar const * ele,
     134             :              ulong         ele_sz,
     135             :              ulong const * keys,
     136             :              ulong         key_cnt,
     137           0 :              ulong         out[ static 4 ] ) {
     138           0 :   ulong h0 = keys[ 0 ];
     139           0 :   ulong h1 = keys[ fd_ulong_if( key_cnt>1UL, 1UL, 0UL ) ];
     140           0 :   ulong h2 = keys[ fd_ulong_if( key_cnt>2UL, 2UL, 0UL ) ];
     141           0 :   ulong h3 = keys[ fd_ulong_if( key_cnt>3UL, 3UL, 0UL ) ];
     142           0 :   for( ulong i=0UL; i<ele_sz; i++ ) {
     143           0 :     ulong b = (ulong)ele[i];
     144           0 :     h0 = (h0^b)*1099511628211UL;
     145           0 :     h1 = (h1^b)*1099511628211UL;
     146           0 :     h2 = (h2^b)*1099511628211UL;
     147           0 :     h3 = (h3^b)*1099511628211UL;
     148           0 :   }
     149           0 :   out[0] = h0; out[1] = h1; out[2] = h2; out[3] = h3;
     150           0 : }
     151             : 
     152             : void
     153             : fd_bloom_insert( fd_bloom_t *  bloom,
     154             :                  uchar const * key,
     155           0 :                  ulong         key_sz ) {
     156           0 :   if( FD_UNLIKELY( !bloom->bits_len ) ) return;
     157           0 :   if( FD_UNLIKELY( bloom->keys_len==1UL ) ) { /* one chain, not four */
     158           0 :     ulong bit = fnv_hasher( key, key_sz, bloom->keys[ 0 ] ) % bloom->bits_len;
     159           0 :     bloom->bits[ bit / 64UL ] |= (1UL << (bit % 64UL));
     160           0 :     return;
     161           0 :   }
     162           0 :   for( ulong i=0UL; i<bloom->keys_len; i+=4UL ) {
     163           0 :     ulong cnt = fd_ulong_min( bloom->keys_len-i, 4UL );
     164           0 :     ulong h[4];
     165           0 :     fnv_hasher4( key, key_sz, bloom->keys+i, cnt, h );
     166           0 :     for( ulong j=0UL; j<cnt; j++ ) {
     167           0 :       ulong bit = h[ j ] % bloom->bits_len;
     168           0 :       bloom->bits[ bit / 64UL ] |= (1UL << (bit % 64UL));
     169           0 :     }
     170           0 :   }
     171           0 : }
     172             : 
     173             : int
     174             : fd_bloom_contains( fd_bloom_t *  bloom,
     175             :                    uchar const * key,
     176           0 :                    ulong         key_sz ) {
     177           0 :   if( FD_UNLIKELY( !bloom->keys_len || !bloom->bits_len ) ) return 0;
     178           0 :   if( FD_UNLIKELY( bloom->keys_len==1UL ) ) {
     179           0 :     ulong bit = fnv_hasher( key, key_sz, bloom->keys[ 0 ] ) % bloom->bits_len;
     180           0 :     return !!(bloom->bits[ bit / 64UL ] & (1UL << (bit % 64UL)));
     181           0 :   }
     182           0 :   for( ulong i=0UL; i<bloom->keys_len; i+=4UL ) {
     183           0 :     ulong cnt = fd_ulong_min( bloom->keys_len-i, 4UL );
     184           0 :     ulong h[4];
     185           0 :     fnv_hasher4( key, key_sz, bloom->keys+i, cnt, h );
     186           0 :     for( ulong j=0UL; j<cnt; j++ ) {
     187           0 :       ulong bit = h[ j ] % bloom->bits_len;
     188           0 :       if( !(bloom->bits[ bit / 64UL ] & (1UL << (bit % 64UL))) ) {
     189           0 :         return 0;
     190           0 :       }
     191           0 :     }
     192           0 :   }
     193           0 :   return 1;
     194           0 : }
     195             : 
     196             : #if FD_HAS_AVX512 && FD_HAS_INT128
     197             : 
     198             : /* bloom_bit is h%bits_len.  magic is floor((2^64-1)/bits_len), which
     199             :    makes q floor(h/bits_len) or one less. */
     200             : 
     201             : static inline ulong
     202             : bloom_bit( ulong bits_len,
     203             :            ulong magic,
     204           0 :            ulong h ) {
     205           0 :   ulong q   = (ulong)(((uint128)h*(uint128)magic)>>64);
     206           0 :   ulong bit = h - q*bits_len;
     207           0 :   return fd_ulong_if( bit>=bits_len, bit-bits_len, bit );
     208           0 : }
     209             : 
     210             : static inline void
     211             : bloom_set( ulong * bits,
     212             :            ulong   bits_len,
     213             :            ulong   magic,
     214           0 :            ulong   h ) {
     215           0 :   ulong bit = bloom_bit( bits_len, magic, h );
     216           0 :   bits[ bit/64UL ] |= 1UL<<(bit%64UL);
     217           0 : }
     218             : 
     219             : static inline int
     220             : bloom_test( ulong const * bits,
     221             :             ulong         bits_len,
     222             :             ulong         magic,
     223           0 :             ulong         h ) {
     224           0 :   ulong bit = bloom_bit( bits_len, magic, h );
     225           0 :   return (int)((bits[ bit/64UL ]>>(bit%64UL)) & 1UL);
     226           0 : }
     227             : 
     228             : /* bloom_transpose8 loads the 8 contiguous 32 byte elements at ele so
     229             :    that wq[k] lane j holds the k-th 8 byte word of element ele8_lane(j).
     230             :    The lane to element map, 0,2,1,3,4,6,5,7, is an involution, so
     231             :    bloom_lane_mask converts a bit set both ways. */
     232             : 
     233             : static inline void
     234             : bloom_transpose8( uchar const * ele,
     235           0 :                   wwv_t         wq[ static 4 ] ) {
     236           0 :   wwv_t r0 = wwv_ldu( ele       ); wwv_t r1 = wwv_ldu( ele+ 64UL );
     237           0 :   wwv_t r2 = wwv_ldu( ele+128UL ); wwv_t r3 = wwv_ldu( ele+192UL );
     238           0 :   wwv_t t0 = _mm512_unpacklo_epi64( r0, r1 ); wwv_t t1 = _mm512_unpackhi_epi64( r0, r1 );
     239           0 :   wwv_t t2 = _mm512_unpacklo_epi64( r2, r3 ); wwv_t t3 = _mm512_unpackhi_epi64( r2, r3 );
     240           0 :   wwv_t lo = wwv( 0UL, 1UL, 4UL, 5UL,  8UL,  9UL, 12UL, 13UL );
     241           0 :   wwv_t hi = wwv( 2UL, 3UL, 6UL, 7UL, 10UL, 11UL, 14UL, 15UL );
     242           0 :   wq[0] = wwv_select( lo, t0, t2 ); wq[1] = wwv_select( lo, t1, t3 );
     243           0 :   wq[2] = wwv_select( hi, t0, t2 ); wq[3] = wwv_select( hi, t1, t3 );
     244           0 : }
     245             : 
     246             : static inline uint
     247           0 : bloom_lane_mask( uint m ) {
     248           0 :   return (m&0x99U) | ((m&0x22U)<<1) | ((m&0x44U)>>1);
     249           0 : }
     250             : 
     251             : /* bloom_fnv8x4 is fnv_hasher4 of the 8 transposed elements in wq: h[c]
     252             :    lane j is the FNV of element ele8_lane(j) under keys[c], one zmm
     253             :    chain per key.  Lanes past cnt repeat key 0. */
     254             : 
     255             : static inline void
     256             : bloom_fnv8x4( wwv_t const * wq,
     257             :               ulong const * keys,
     258             :               ulong         cnt,
     259           0 :               ulong         h[ static 4 ][ 8 ] ) {
     260           0 :   wwv_t prime = wwv_bcast( 1099511628211UL );
     261           0 :   wwv_t h0 = wwv_bcast( keys[ 0 ] );
     262           0 :   wwv_t h1 = wwv_bcast( keys[ fd_ulong_if( cnt>1UL, 1UL, 0UL ) ] );
     263           0 :   wwv_t h2 = wwv_bcast( keys[ fd_ulong_if( cnt>2UL, 2UL, 0UL ) ] );
     264           0 :   wwv_t h3 = wwv_bcast( keys[ fd_ulong_if( cnt>3UL, 3UL, 0UL ) ] );
     265           0 :   for( ulong k=0UL; k<4UL; k++ ) {
     266           0 :     for( ulong b=0UL; b<8UL; b++ ) {
     267           0 :       wwv_t x = wwv_and( wwv_shr( wq[ k ], 8UL*b ), wwv_bcast( 0xffUL ) );
     268           0 :       h0 = wwv_mul( wwv_xor( h0, x ), prime );
     269           0 :       h1 = wwv_mul( wwv_xor( h1, x ), prime );
     270           0 :       h2 = wwv_mul( wwv_xor( h2, x ), prime );
     271           0 :       h3 = wwv_mul( wwv_xor( h3, x ), prime );
     272           0 :     }
     273           0 :   }
     274           0 :   wwv_st( h[0], h0 ); wwv_st( h[1], h1 ); wwv_st( h[2], h2 ); wwv_st( h[3], h3 );
     275           0 : }
     276             : 
     277             : /* bloom_fnv8x4x2 is bloom_fnv8x4 of two transposed 8 element blocks
     278             :    under the same keys, 8 chains interleaved: 4 dependent multiplies
     279             :    per byte do not fill the multiplier's pipeline, 8 nearly do. */
     280             : 
     281             : static inline void
     282             : bloom_fnv8x4x2( wwv_t const * wqa,
     283             :                 wwv_t const * wqb,
     284             :                 ulong const * keys,
     285             :                 ulong         cnt,
     286             :                 ulong         ha[ static 4 ][ 8 ],
     287           0 :                 ulong         hb[ static 4 ][ 8 ] ) {
     288           0 :   wwv_t prime = wwv_bcast( 1099511628211UL );
     289           0 :   wwv_t k0 = wwv_bcast( keys[ 0 ] );
     290           0 :   wwv_t k1 = wwv_bcast( keys[ fd_ulong_if( cnt>1UL, 1UL, 0UL ) ] );
     291           0 :   wwv_t k2 = wwv_bcast( keys[ fd_ulong_if( cnt>2UL, 2UL, 0UL ) ] );
     292           0 :   wwv_t k3 = wwv_bcast( keys[ fd_ulong_if( cnt>3UL, 3UL, 0UL ) ] );
     293           0 :   wwv_t a0 = k0; wwv_t a1 = k1; wwv_t a2 = k2; wwv_t a3 = k3;
     294           0 :   wwv_t b0 = k0; wwv_t b1 = k1; wwv_t b2 = k2; wwv_t b3 = k3;
     295           0 :   for( ulong k=0UL; k<4UL; k++ ) {
     296           0 :     for( ulong b=0UL; b<8UL; b++ ) {
     297           0 :       wwv_t xa = wwv_and( wwv_shr( wqa[ k ], 8UL*b ), wwv_bcast( 0xffUL ) );
     298           0 :       wwv_t xb = wwv_and( wwv_shr( wqb[ k ], 8UL*b ), wwv_bcast( 0xffUL ) );
     299           0 :       a0 = wwv_mul( wwv_xor( a0, xa ), prime ); b0 = wwv_mul( wwv_xor( b0, xb ), prime );
     300           0 :       a1 = wwv_mul( wwv_xor( a1, xa ), prime ); b1 = wwv_mul( wwv_xor( b1, xb ), prime );
     301           0 :       a2 = wwv_mul( wwv_xor( a2, xa ), prime ); b2 = wwv_mul( wwv_xor( b2, xb ), prime );
     302           0 :       a3 = wwv_mul( wwv_xor( a3, xa ), prime ); b3 = wwv_mul( wwv_xor( b3, xb ), prime );
     303           0 :     }
     304           0 :   }
     305           0 :   wwv_st( ha[0], a0 ); wwv_st( ha[1], a1 ); wwv_st( ha[2], a2 ); wwv_st( ha[3], a3 );
     306           0 :   wwv_st( hb[0], b0 ); wwv_st( hb[1], b1 ); wwv_st( hb[2], b2 ); wwv_st( hb[3], b3 );
     307           0 : }
     308             : 
     309             : static inline void
     310             : bloom_set8( ulong *       bits,
     311             :             ulong         bits_len,
     312             :             ulong         magic,
     313             :             ulong         h[ static 4 ][ 8 ],
     314             :             ulong         cnt,
     315           0 :             uint          lane_mask ) {
     316           0 :   for( uint m=lane_mask; m; m&=m-1U ) {
     317           0 :     ulong j = (ulong)fd_uint_find_lsb( m );
     318           0 :     for( ulong c=0UL; c<cnt; c++ ) bloom_set( bits, bits_len, magic, h[ c ][ j ] );
     319           0 :   }
     320           0 : }
     321             : 
     322             : void
     323             : fd_bloom_insert8( fd_bloom_t *  bloom,
     324             :                   uchar const * ele,
     325           0 :                   uint          lanes ) {
     326           0 :   ulong bits_len = bloom->bits_len;
     327           0 :   if( FD_UNLIKELY( !bits_len || !lanes ) ) return;
     328           0 :   ulong magic = ULONG_MAX/bits_len;
     329             : 
     330           0 :   wwv_t wq[4];
     331           0 :   bloom_transpose8( ele, wq );
     332           0 :   uint lane_mask = bloom_lane_mask( lanes );
     333             : 
     334           0 :   for( ulong i=0UL; i<bloom->keys_len; i+=4UL ) {
     335           0 :     ulong cnt = fd_ulong_min( bloom->keys_len-i, 4UL );
     336           0 :     ulong h[4][8] __attribute__((aligned(64)));
     337           0 :     bloom_fnv8x4( wq, bloom->keys+i, cnt, h );
     338           0 :     bloom_set8( bloom->bits, bits_len, magic, h, cnt, lane_mask );
     339           0 :   }
     340           0 : }
     341             : 
     342             : void
     343             : fd_bloom_insert16( fd_bloom_t *  bloom,
     344             :                    uchar const * ele_a,
     345             :                    uint          lanes_a,
     346             :                    uchar const * ele_b,
     347           0 :                    uint          lanes_b ) {
     348           0 :   ulong bits_len = bloom->bits_len;
     349           0 :   if( FD_UNLIKELY( !bits_len ) ) return;
     350           0 :   if( FD_UNLIKELY( !lanes_a ) ) { fd_bloom_insert8( bloom, ele_b, lanes_b ); return; }
     351           0 :   if( FD_UNLIKELY( !lanes_b ) ) { fd_bloom_insert8( bloom, ele_a, lanes_a ); return; }
     352           0 :   ulong magic = ULONG_MAX/bits_len;
     353             : 
     354           0 :   wwv_t wqa[4]; wwv_t wqb[4];
     355           0 :   bloom_transpose8( ele_a, wqa );
     356           0 :   bloom_transpose8( ele_b, wqb );
     357           0 :   uint lane_mask_a = bloom_lane_mask( lanes_a );
     358           0 :   uint lane_mask_b = bloom_lane_mask( lanes_b );
     359             : 
     360           0 :   for( ulong i=0UL; i<bloom->keys_len; i+=4UL ) {
     361           0 :     ulong cnt = fd_ulong_min( bloom->keys_len-i, 4UL );
     362           0 :     ulong ha[4][8] __attribute__((aligned(64)));
     363           0 :     ulong hb[4][8] __attribute__((aligned(64)));
     364           0 :     bloom_fnv8x4x2( wqa, wqb, bloom->keys+i, cnt, ha, hb );
     365           0 :     bloom_set8( bloom->bits, bits_len, magic, ha, cnt, lane_mask_a );
     366           0 :     bloom_set8( bloom->bits, bits_len, magic, hb, cnt, lane_mask_b );
     367           0 :   }
     368           0 : }
     369             : 
     370             : uint
     371             : fd_bloom_contains8( fd_bloom_t const * bloom,
     372           0 :                     uchar const *      ele ) {
     373           0 :   ulong bits_len = bloom->bits_len;
     374           0 :   ulong keys_len = bloom->keys_len;
     375           0 :   if( FD_UNLIKELY( !keys_len || !bits_len ) ) return 0U;
     376           0 :   ulong magic = ULONG_MAX/bits_len;
     377             : 
     378           0 :   wwv_t wq[4];
     379           0 :   bloom_transpose8( ele, wq );
     380             : 
     381             :   /* Lanes whose element has had every key so far set; a lane leaves
     382             :      on its first clear bit, as fd_bloom_contains returns there. */
     383           0 :   uint alive = 0xffU;
     384           0 :   for( ulong i=0UL; i<keys_len && alive; i+=4UL ) {
     385           0 :     ulong cnt = fd_ulong_min( keys_len-i, 4UL );
     386           0 :     ulong h[4][8] __attribute__((aligned(64)));
     387           0 :     bloom_fnv8x4( wq, bloom->keys+i, cnt, h );
     388           0 :     for( uint m=alive; m; m&=m-1U ) {
     389           0 :       ulong j = (ulong)fd_uint_find_lsb( m );
     390           0 :       for( ulong c=0UL; c<cnt; c++ ) {
     391           0 :         if( !bloom_test( bloom->bits, bits_len, magic, h[ c ][ j ] ) ) { alive &= ~(1U<<j); break; }
     392           0 :       }
     393           0 :     }
     394           0 :   }
     395           0 :   return bloom_lane_mask( alive );
     396           0 : }
     397             : 
     398           0 : #define BLOOM_MULTI_CHAIN_CNT (5UL) /* 40 lanes: 12 active set peers with 3 keys each */
     399             : 
     400             : uint
     401             : fd_bloom_contains_multi( fd_bloom_t * const * blooms,
     402             :                          ulong                cnt,
     403             :                          uchar const *        key,
     404           0 :                          ulong                key_sz ) {
     405             :   /* One lane per (bloom, key) pair.  A bloom with no keys or bits
     406             :      contains nothing (fd_bloom_contains) and takes no lane. */
     407           0 :   ulong keys[ 8UL*BLOOM_MULTI_CHAIN_CNT ];
     408           0 :   ulong off [ 32UL ];
     409           0 :   ulong tot = 0UL;
     410           0 :   for( ulong b=0UL; b<cnt; b++ ) {
     411           0 :     fd_bloom_t const * bloom = blooms[ b ];
     412           0 :     off[ b ] = tot;
     413           0 :     if( FD_UNLIKELY( !bloom->keys_len || !bloom->bits_len ) ) continue;
     414           0 :     if( FD_UNLIKELY( tot+bloom->keys_len>8UL*BLOOM_MULTI_CHAIN_CNT ) ) {
     415           0 :       uint hit = 0U;
     416           0 :       for( ulong i=0UL; i<cnt; i++ ) hit |= (uint)fd_bloom_contains( blooms[ i ], key, key_sz )<<i;
     417           0 :       return hit;
     418           0 :     }
     419           0 :     for( ulong k=0UL; k<bloom->keys_len; k++ ) keys[ tot++ ] = bloom->keys[ k ];
     420           0 :   }
     421           0 :   if( FD_UNLIKELY( !tot ) ) return 0U;
     422           0 :   for( ulong i=tot; i<8UL*BLOOM_MULTI_CHAIN_CNT; i++ ) keys[ i ] = 0UL;
     423             : 
     424             :   /* The key bytes go into every lane; the chains are independent so
     425             :      the multiply latency is hidden across them. */
     426           0 :   wwv_t prime = wwv_bcast( 1099511628211UL );
     427           0 :   wwv_t h[ BLOOM_MULTI_CHAIN_CNT ];
     428           0 :   for( ulong c=0UL; c<BLOOM_MULTI_CHAIN_CNT; c++ ) h[ c ] = wwv_ldu( keys+8UL*c );
     429           0 :   for( ulong i=0UL; i<key_sz; i++ ) {
     430           0 :     wwv_t x = wwv_bcast( (ulong)key[ i ] );
     431           0 :     for( ulong c=0UL; c<BLOOM_MULTI_CHAIN_CNT; c++ ) h[ c ] = wwv_mul( wwv_xor( h[ c ], x ), prime );
     432           0 :   }
     433           0 :   ulong hash[ 8UL*BLOOM_MULTI_CHAIN_CNT ] __attribute__((aligned(64)));
     434           0 :   for( ulong c=0UL; c<BLOOM_MULTI_CHAIN_CNT; c++ ) wwv_st( hash+8UL*c, h[ c ] );
     435             : 
     436           0 :   uint hit = 0U;
     437           0 :   for( ulong b=0UL; b<cnt; b++ ) {
     438           0 :     fd_bloom_t const * bloom = blooms[ b ];
     439           0 :     if( FD_UNLIKELY( !bloom->keys_len || !bloom->bits_len ) ) continue;
     440           0 :     ulong k=0UL;
     441           0 :     for( ; k<bloom->keys_len; k++ ) {
     442           0 :       ulong bit = hash[ off[ b ]+k ] % bloom->bits_len;
     443           0 :       if( !(bloom->bits[ bit/64UL ] & (1UL<<(bit%64UL))) ) break;
     444           0 :     }
     445           0 :     hit |= (uint)(k==bloom->keys_len)<<b;
     446           0 :   }
     447           0 :   return hit;
     448           0 : }
     449             : 
     450             : #else
     451             : 
     452             : void
     453             : fd_bloom_insert8( fd_bloom_t *  bloom,
     454             :                   uchar const * ele,
     455             :                   uint          lanes ) {
     456             :   for( ulong i=0UL; i<8UL; i++ ) {
     457             :     if( lanes & (1U<<i) ) fd_bloom_insert( bloom, ele+32UL*i, 32UL );
     458             :   }
     459             : }
     460             : 
     461             : void
     462             : fd_bloom_insert16( fd_bloom_t *  bloom,
     463             :                    uchar const * ele_a,
     464             :                    uint          lanes_a,
     465             :                    uchar const * ele_b,
     466             :                    uint          lanes_b ) {
     467             :   fd_bloom_insert8( bloom, ele_a, lanes_a );
     468             :   fd_bloom_insert8( bloom, ele_b, lanes_b );
     469             : }
     470             : 
     471             : uint
     472             : fd_bloom_contains8( fd_bloom_t const * bloom,
     473             :                     uchar const *      ele ) {
     474             :   uint hit = 0U;
     475             :   for( ulong i=0UL; i<8UL; i++ ) hit |= (uint)fd_bloom_contains( (fd_bloom_t *)bloom, ele+32UL*i, 32UL )<<i;
     476             :   return hit;
     477             : }
     478             : 
     479             : uint
     480             : fd_bloom_contains_multi( fd_bloom_t * const * blooms,
     481             :                          ulong                cnt,
     482             :                          uchar const *        key,
     483             :                          ulong                key_sz ) {
     484             :   uint hit = 0U;
     485             :   for( ulong i=0UL; i<cnt; i++ ) hit |= (uint)fd_bloom_contains( blooms[ i ], key, key_sz )<<i;
     486             :   return hit;
     487             : }
     488             : 
     489             : #endif
     490             : 
     491             : int
     492             : fd_bloom_init_inplace( ulong *      keys,
     493             :                        ulong *      bits,
     494             :                        ulong        keys_len,
     495             :                        ulong        bits_len,
     496             :                        ulong        hash_seed,
     497             :                        fd_rng_t *   rng,
     498             :                        double       false_positive_rate,
     499           0 :                        fd_bloom_t * out_bloom ) {
     500           0 :   if( FD_UNLIKELY( !keys || !bits || !out_bloom ) ) {
     501           0 :     FD_LOG_ERR(( "NULL keys, bits or out_bloom" ));
     502           0 :     return -1;
     503           0 :   }
     504           0 :   out_bloom->keys                = keys;
     505           0 :   for( ulong i=0UL; i<keys_len; i++ ) out_bloom->keys[ i ] = fd_rng_ulong( rng );
     506             : 
     507           0 :   out_bloom->keys_len            = keys_len;
     508           0 :   out_bloom->bits                = bits;
     509           0 :   out_bloom->bits_len            = bits_len;
     510           0 :   out_bloom->hash_seed           = hash_seed;
     511           0 :   out_bloom->rng                 = rng;
     512           0 :   out_bloom->false_positive_rate = false_positive_rate;
     513           0 :   out_bloom->max_bits            = bits_len;
     514             : 
     515           0 :   return 0;
     516           0 : }