bloom.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <inttypes.h>
   4 #include <string.h>
   5 #include <assert.h>
   6
   7 #include "adu.h"
   8 #include "string.h"
   9 #include "bloom.h"
  10
  11 #ifdef TEST_BLOOM
  12 void *adu_calloc(size_t size)
  13 {
  14         void *ret = malloc(size);
  15         memset(ret, 0, size);
  16         return ret;
  17 }
  18 #undef INFO_LOG
  19 #define INFO_LOG printf
  20 #endif
  21
  22 static inline uint64_t filter_bits(struct bloom *b)
  23 {
  24         return 1ULL << b->order;
  25 }
  26
  27 /*
  28  * SuperFastHash, by Paul Hsieh.
  29  * http://www.azillionmonkeys.com/qed/hash.html
  30  */
  31
  32 #if (defined(__GNUC__) && defined(__i386__))
  33 #define get16bits(d) (*((const uint16_t *) (d)))
  34 #else
  35 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
  36                        +(uint32_t)(((const uint8_t *)(d))[0]) )
  37 #endif
  38
  39
  40 static uint32_t super_fast_hash(const uint8_t *data, uint32_t len, uint32_t hash)
  41 {
  42         uint32_t tmp;
  43         int rem = len & 3;
  44
  45         len >>= 2;
  46
  47         for (;len > 0; len--) {
  48                 hash  += get16bits (data);
  49                 tmp    = (get16bits (data+2) << 11) ^ hash;
  50                 hash   = (hash << 16) ^ tmp;
  51                 data  += 2*sizeof (uint16_t);
  52                 hash  += hash >> 11;
  53         }
  54
  55         /* Handle end cases */
  56         switch (rem) {
  57         case 3:
  58                 hash += get16bits (data);
  59                 hash ^= hash << 16;
  60                 hash ^= data[sizeof (uint16_t)] << 18;
  61                 hash += hash >> 11;
  62                 break;
  63         case 2:
  64                 hash += get16bits (data);
  65                 hash ^= hash << 11;
  66                 hash += hash >> 17;
  67                 break;
  68         case 1:
  69                 hash += *data;
  70                 hash ^= hash << 10;
  71                 hash += hash >> 1;
  72         }
  73         /* Force "avalanching" of final 127 bits */
  74         hash ^= hash << 3;
  75         hash += hash >> 5;
  76         hash ^= hash << 4;
  77         hash += hash >> 17;
  78         hash ^= hash << 25;
  79         hash += hash >> 6;
  80         return hash;
  81 }
  82
  83 static int test_and_set_bit(uint64_t bitnum, struct bloom *b)
  84 {
  85         uint64_t byte = bitnum / 8;
  86         uint8_t bit = 1 << (bitnum % 8);
  87         int ret = b->filter[byte] & bit;
  88
  89         b->filter[byte] |= bit;
  90
  91         if (!ret)
  92                 b->num_set_bits++;
  93         return ret;
  94 }
  95
  96 int bloom_test_and_insert(const uint8_t *data, size_t len, struct bloom *b)
  97 {
  98         int i, ret = 0;
  99         uint32_t h = 0xb11924e1; /* some arbitrary value */
 100
 101         for (i = 1; i < b->num_hash_functions; i++) {
 102                 uint64_t bitnum = super_fast_hash(data, len, h);
 103                 h = bitnum;
 104                 if (b->order > 32) {
 105                         bitnum = bitnum << 32;
 106                         h = super_fast_hash(data, len, h);
 107                         bitnum |= h;
 108                 }
 109                 bitnum &= filter_bits(b) - 1;
 110                 ret |= !test_and_set_bit(bitnum, b);
 111         }
 112         if (ret)
 113                 b->num_entries++;
 114         return !ret;
 115 }
 116
 117 int bloom_test_and_insert_string(const char *str, struct bloom *b)
 118 {
 119         uint32_t len = strlen(str);
 120
 121         return bloom_test_and_insert((const uint8_t *)str, len, b);
 122 }
 123
 124 void bloom_free(struct bloom *b)
 125 {
 126         if (!b)
 127                 return;
 128         free(b->filter);
 129         free(b);
 130 }
 131
 132 int bloom_init(unsigned order, unsigned num_hash_functions,
 133                 struct bloom **result)
 134 {
 135         struct bloom *b = adu_calloc(sizeof(*b));
 136
 137         INFO_LOG("allocating bloom filter (order: %u, %u hash functions)\n",
 138                 order, num_hash_functions);
 139         b->order = order;
 140         b->num_hash_functions = num_hash_functions;
 141         b->filter = adu_calloc(filter_bits(b) / 8);
 142         *result = b;
 143         return 1;
 144 }
 145
 146 #ifdef TEST_BLOOM
 147
 148 void add_stdin(struct bloom *b)
 149 {
 150         char buf[255];
 151         unsigned false_positives = 0;
 152
 153         while (fgets(buf, sizeof(buf) - 1, stdin)) {
 154                 size_t len = strlen(buf);
 155                 if (!len)
 156                         continue;
 157                 if (buf[len - 1] == '\n')
 158                         buf[len - 1] = '\0';
 159                 if (bloom_test_and_insert_string(buf, b))
 160                         false_positives++;
 161         }
 162         INFO_LOG("filter contains %llu entries\n", b->num_entries);
 163         printf("%u possible false positives\n", false_positives);
 164 }
 165
 166 int main(int argc, char **argv)
 167 {
 168         struct bloom *b;
 169
 170         if (argc != 3) {
 171                 printf("usage: $0 j k\n");
 172                 printf("j: set bloom filter size to m=2^j bits\n");
 173                 printf("k: # of hash functions to use\n");
 174                 exit(1);
 175         }
 176         bloom_init(atoi(argv[1]), atoi(argv[2]), &b);
 177         add_stdin(b);
 178         INFO_LOG("%u%% of bits are set\n", (unsigned)
 179                 (b->num_set_bits * 100ULL / filter_bits(b)));
 180         return 1;
 181 }
 182
 183 #endif /* TEST_BLOOM */