cangrepp

Some cryptographic attacks
Log | Files | Refs | README

bloom.c (2350B)

      1 #include "bloom.h"
      2 
      3 static inline void
      4 bitvec_init(bitvec_t *bv, const size_t size)
      5 {
      6   assert(size < (0xffffffff - 7));
      7 
      8   const size_t size_bytes = (size + 7) >> 3;
      9 
     10   bv->n = size;
     11   bv->buffer = calloc(size_bytes, sizeof(*bv->buffer));
     12 }
     13 
     14 static inline void
     15 bitvec_clear(bitvec_t *bv)
     16 {
     17   free(bv->buffer);
     18 }
     19 
     20 static inline void
     21 bitvec_set(bitvec_t *bv, const size_t index)
     22 {
     23   assert(index < bv->n);
     24 
     25   const size_t byte_index = index >> 3;
     26   const size_t bit_index = index % 8;
     27   const uint8_t mask = 0x80 >> bit_index;
     28 
     29   bv->buffer[byte_index] |= mask;
     30 }
     31 
     32 /*
     33 void
     34 bitvec_unset(bitvec_t *bv, const size_t index)
     35 {
     36   assert(index < bv->n);
     37 
     38   const size_t byte_index = index >> 3;
     39   const size_t bit_index = index % 8;
     40   const uint8_t pre_mask = 0x80 >> bit_index;
     41   const uint8_t mask = 0xff ^ pre_mask;
     42 
     43   bv->buffer[byte_index] &= mask;
     44 }
     45 */
     46 
     47 static int
     48 bitvec_is_set(const bitvec_t *bv, const size_t index)
     49 {
     50   assert(index < bv->n);
     51 
     52   const size_t byte_index = index >> 3;
     53   const size_t bit_index = index % 8;
     54   const uint8_t mask = 0x80 >> bit_index;
     55 
     56   if ((bv->buffer[byte_index] & mask) != 0) {
     57     return 1;
     58   }
     59 
     60   return 0;
     61 }
     62 
     63 static inline void
     64 mix64(uint64_t *out, uint64_t in)
     65 {
     66   *out += in * 0x9E3779B97F4A7C15;
     67   *out ^= *out >> 30;
     68   *out *= 0xBF58476D1CE4E5B9;
     69   *out ^= *out >> 27;
     70   *out *= 0x94D049BB133111EB;
     71   *out ^= *out >> 31;
     72 }
     73 
     74 static inline uint64_t
     75 hash_fmpz(uint64_t seed, const fmpz_t n)
     76 {
     77   size_t i;
     78   uint64_t ret = seed;
     79   mpz_ptr p;
     80   mp_srcptr limbs;
     81   size_t msize;
     82 
     83   if (COEFF_IS_MPZ(n[0]) != 0) {
     84     p = COEFF_TO_PTR(n[0]);
     85     msize = mpz_size(p);
     86     limbs = mpz_limbs_read(p);
     87     for (i = 0; i < msize; i++) {
     88       mix64(&ret, (uint64_t)limbs[i]);
     89     }
     90   } else {
     91     mix64(&ret, (uint64_t)n[0]);
     92   }
     93 
     94   return ret;
     95 }
     96 
     97 void
     98 bloom_init(bloom_t *bloom, const size_t k, const size_t m)
     99 {
    100   bloom->k = k;
    101   bitvec_init(&bloom->bv, m);
    102 }
    103 
    104 void
    105 bloom_clear(bloom_t *bloom)
    106 {
    107   bitvec_clear(&bloom->bv);
    108 }
    109 
    110 void
    111 bloom_insert(bloom_t *bloom, const fmpz_t n)
    112 {
    113   uint64_t i;
    114 
    115   for (i = 0; i < bloom->k; i++) {
    116     bitvec_set(&bloom->bv, hash_fmpz(i, n) % bloom->bv.n);
    117   }
    118 }
    119 
    120 int
    121 bloom_prob_contains(const bloom_t *bloom, const fmpz_t n)
    122 {
    123   uint64_t i;
    124 
    125   for (i = 0; i < bloom->k; i++) {
    126     if (!bitvec_is_set(&bloom->bv, hash_fmpz(i, n) % bloom->bv.n)) {
    127       return 0;
    128     }
    129   }
    130 
    131   return 1;
    132 }