bloom.c

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