bloom.c

   1 /*
   2  * Copyright (C) 2008 Andre Noll <maan@tuebingen.mpg.de>
   3  *
   4  * Licensed under the GPL v2. For licencing details see COPYING.
   5  */
   6
   7 /** \file bloom.c Simple bloom filter implementation. */
   8
   9 #include "adu.h"
  10 #include "string.h"
  11 #include "bloom.h"
  12
  13 #ifdef TEST_BLOOM
  14 void *adu_calloc(size_t size)
  15 {
  16         void *ret = malloc(size);
  17
  18         if (!ret)
  19                 exit(EXIT_FAILURE);
  20         memset(ret, 0, size);
  21         return ret;
  22 }
  23 #undef INFO_LOG
  24 #define INFO_LOG printf
  25 #endif
  26
  27 static inline uint64_t filter_bits(struct bloom *b)
  28 {
  29         return 1ULL << b->order;
  30 }
  31
  32 /*
  33  * SuperFastHash, by Paul Hsieh.
  34  * http://www.azillionmonkeys.com/qed/hash.html
  35  */
  36
  37 /** \cond */
  38 #if (defined(__GNUC__) && defined(__i386__))
  39 #define get16bits(d) (*((const uint16_t *) (d)))
  40 #else
  41 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
  42                        +(uint32_t)(((const uint8_t *)(d))[0]) )
  43 #endif
  44 /** \endcond */
  45
  46 static uint32_t super_fast_hash(const uint8_t *data, uint32_t len, uint32_t hash)
  47 {
  48         uint32_t tmp;
  49         int rem = len & 3;
  50
  51         len >>= 2;
  52
  53         for (;len > 0; len--) {
  54                 hash  += get16bits (data);
  55                 tmp    = (get16bits (data+2) << 11) ^ hash;
  56                 hash   = (hash << 16) ^ tmp;
  57                 data  += 2*sizeof (uint16_t);
  58                 hash  += hash >> 11;
  59         }
  60
  61         /* Handle end cases */
  62         switch (rem) {
  63         case 3:
  64                 hash += get16bits (data);
  65                 hash ^= hash << 16;
  66                 hash ^= data[sizeof (uint16_t)] << 18;
  67                 hash += hash >> 11;
  68                 break;
  69         case 2:
  70                 hash += get16bits (data);
  71                 hash ^= hash << 11;
  72                 hash += hash >> 17;
  73                 break;
  74         case 1:
  75                 hash += *data;
  76                 hash ^= hash << 10;
  77                 hash += hash >> 1;
  78         }
  79         /* Force "avalanching" of final 127 bits */
  80         hash ^= hash << 3;
  81         hash += hash >> 5;
  82         hash ^= hash << 4;
  83         hash += hash >> 17;
  84         hash ^= hash << 25;
  85         hash += hash >> 6;
  86         return hash;
  87 }
  88
  89 static int test_and_set_bit(uint64_t bitnum, struct bloom *b)
  90 {
  91         uint64_t byte = bitnum / 8;
  92         uint8_t bit = 1 << (bitnum % 8);
  93         int ret = b->filter[byte] & bit;
  94
  95         b->filter[byte] |= bit;
  96
  97         if (!ret)
  98                 b->num_set_bits++;
  99         return ret;
 100 }
 101
 102 /**
 103  * Insert data to the given bloom filter.
 104  *
 105  * This function computes \a k hashes from the given data where \a k is the
 106  * number of hash functions of the filter \a b. Each hash value corresponds to
 107  * a position in the bit array of the filter and each of these bits are being
 108  * tested and set.  If not all \a k bits were already set, the given data was
 109  * not yet contained in the filter and the function returns non-zero.
 110  *
 111  * Otherwise either (a) the same data has already been inserted previously or
 112  * (b) a hash collision occurred or (c) the \a k bits are set due to previous
 113  * insertion of other data (i.e. a false positive occurred). It is impossible
 114  * to distinguish these cases.
 115  *
 116  * \param data The data to insert.
 117  * \param len Number of bytes of \a data.
 118  * \param b The filter to insert to.
 119  *
 120  * \return Zero if the entry was already contained in the filter (or in case of
 121  * false positives), non-zero otherwise.
 122  */
 123 int bloom_insert(const uint8_t *data, size_t len, struct bloom *b)
 124 {
 125         int i, ret = 0;
 126         uint32_t h = 0xb11924e1; /* some arbitrary value */
 127
 128         for (i = 1; i < b->num_hash_functions; i++) {
 129                 uint64_t bitnum = super_fast_hash(data, len, h);
 130                 h = bitnum;
 131                 if (b->order > 32) {
 132                         bitnum = bitnum << 32;
 133                         h = super_fast_hash(data, len, h);
 134                         bitnum |= h;
 135                 }
 136                 bitnum &= filter_bits(b) - 1;
 137                 ret |= !test_and_set_bit(bitnum, b);
 138         }
 139         if (ret)
 140                 b->num_entries++;
 141         return !ret;
 142 }
 143
 144 /**
 145  * Deallocate a bloom filter.
 146  *
 147  * \param b The filter to deallocate.
 148  */
 149 void bloom_free(struct bloom *b)
 150 {
 151         if (!b)
 152                 return;
 153         free(b->filter);
 154         free(b);
 155 }
 156
 157 /**
 158  * Allocate and initialize a new bloom filter.
 159  *
 160  * \param order Use a filter containing 2^order bits.
 161  * \param num_hash_functions Set that many bits in the filter per entry.
 162  *
 163  * \return This function either returns a freshly allocated and initialized
 164  * bloom filter or does not return at all (if the underlying malloc() failed).
 165  */
 166 struct bloom *bloom_new(unsigned order, unsigned num_hash_functions)
 167 {
 168         struct bloom *b = adu_calloc(sizeof(*b));
 169
 170         INFO_LOG("allocating bloom filter (order: %u, %u hash functions)\n",
 171                 order, num_hash_functions);
 172         b->order = order;
 173         b->num_hash_functions = num_hash_functions;
 174         b->filter = adu_calloc(filter_bits(b) / 8);
 175         return b;
 176 }
 177
 178 #ifdef TEST_BLOOM
 179
 180 int bloom_insert_string(const char *str, struct bloom *b)
 181 {
 182         uint32_t len = strlen(str);
 183
 184         return bloom_insert((const uint8_t *)str, len, b);
 185 }
 186
 187 void add_stdin(struct bloom *b)
 188 {
 189         char buf[255];
 190         unsigned false_positives = 0;
 191
 192         while (fgets(buf, sizeof(buf) - 1, stdin)) {
 193                 size_t len = strlen(buf);
 194                 if (!len)
 195                         continue;
 196                 if (buf[len - 1] == '\n')
 197                         buf[len - 1] = '\0';
 198                 if (bloom_insert_string(buf, b))
 199                         false_positives++;
 200         }
 201         INFO_LOG("filter contains %llu entries\n", b->num_entries);
 202         printf("%u possible false positives\n", false_positives);
 203 }
 204
 205 int main(int argc, char **argv)
 206 {
 207         struct bloom *b;
 208
 209         if (argc != 3) {
 210                 printf("usage: $0 j k\n");
 211                 printf("j: set bloom filter size to m=2^j bits\n");
 212                 printf("k: # of hash functions to use\n");
 213                 exit(1);
 214         }
 215         b = bloom_new(atoi(argv[1]), atoi(argv[2]));
 216         add_stdin(b);
 217         INFO_LOG("%u%% of bits are set\n", (unsigned)
 218                 (b->num_set_bits * 100ULL / filter_bits(b)));
 219         return 1;
 220 }
 221
 222 #endif /* TEST_BLOOM */