lib/bloom.c

   1 /*
   2  *  Copyright (c) 2012-2019, Jyri J. Virkki
   3  *  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright
  10  * notice, this list of conditions and the following disclaimer.
  11  *
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  * notice, this list of conditions and the following disclaimer in the
  14  * documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /* Obtained from https://github.com/jvirkki/libbloom */
  30
  31 /*
  32  * Refer to bloom.h for documentation on the public interfaces.
  33  */
  34
  35 #include <assert.h>
  36 #include <fcntl.h>
  37 #include <math.h>
  38 #include <stdint.h>
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41 #include <string.h>
  42 #include <sys/stat.h>
  43 #include <sys/types.h>
  44 #include <unistd.h>
  45
  46 #include "bloom.h"
  47 #include "murmurhash2.h"
  48
  49 #define MAKESTRING(n) STRING(n)
  50 #define STRING(n) #n
  51
  52
  53 inline static int test_bit_set_bit(unsigned char * buf,
  54                                    unsigned int x, int set_bit)
  55 {
  56   unsigned int byte = x >> 3;
  57   unsigned char c = buf[byte];        // expensive memory access
  58   unsigned int mask = 1 << (x % 8);
  59
  60   if (c & mask) {
  61     return 1;
  62   } else {
  63     if (set_bit) {
  64       buf[byte] = c | mask;
  65     }
  66     return 0;
  67   }
  68 }
  69
  70
  71 static int bloom_check_add(struct bloom * bloom,
  72                            const void * buffer, int len, int add)
  73 {
  74   if (bloom->ready == 0) {
  75     printf("bloom at %p not initialized!\n", (void *)bloom);
  76     return -1;
  77   }
  78
  79   int hits = 0;
  80   register unsigned int a = murmurhash2(buffer, len, bloom->seed);
  81   register unsigned int b = murmurhash2(buffer, len, a);
  82   register unsigned int x;
  83   register unsigned int i;
  84
  85   for (i = 0; i < bloom->hashes; i++) {
  86     x = (a + i*b) % bloom->bits;
  87     if (test_bit_set_bit(bloom->bf, x, add)) {
  88       hits++;
  89     } else if (!add) {
  90       // Don't care about the presence of all the bits. Just our own.
  91       return 0;
  92     }
  93   }
  94
  95   if (hits == bloom->hashes) {
  96     return 1;                // 1 == element already in (or collision)
  97   }
  98
  99   return 0;
 100 }
 101
 102
 103 int bloom_init_size(struct bloom * bloom, int entries, double error,
 104                     unsigned int cache_size)
 105 {
 106   return bloom_init(bloom, entries, error);
 107 }
 108
 109
 110 int bloom_init(struct bloom * bloom, int entries, double error)
 111 {
 112   bloom->ready = 0;
 113
 114   bloom->seed = arc4random();
 115
 116   if (entries < 1000 || error == 0) {
 117     return 1;
 118   }
 119
 120   bloom->entries = entries;
 121   bloom->error = error;
 122
 123   double num = log(bloom->error);
 124   double denom = 0.480453013918201; // ln(2)^2
 125   bloom->bpe = -(num / denom);
 126
 127   double dentries = (double)entries;
 128   bloom->bits = (int)(dentries * bloom->bpe);
 129
 130   if (bloom->bits % 8) {
 131     bloom->bytes = (bloom->bits / 8) + 1;
 132   } else {
 133     bloom->bytes = bloom->bits / 8;
 134   }
 135
 136   bloom->hashes = (int)ceil(0.693147180559945 * bloom->bpe);  // ln(2)
 137
 138   bloom->bf = (unsigned char *)calloc(bloom->bytes, sizeof(unsigned char));
 139   if (bloom->bf == NULL) {                                   // LCOV_EXCL_START
 140     return 1;
 141   }                                                          // LCOV_EXCL_STOP
 142
 143   bloom->ready = 1;
 144   return 0;
 145 }
 146
 147
 148 int bloom_check(struct bloom * bloom, const void * buffer, int len)
 149 {
 150   return bloom_check_add(bloom, buffer, len, 0);
 151 }
 152
 153
 154 int bloom_add(struct bloom * bloom, const void * buffer, int len)
 155 {
 156   return bloom_check_add(bloom, buffer, len, 1);
 157 }
 158
 159
 160 void bloom_print(struct bloom * bloom)
 161 {
 162   printf("bloom at %p\n", (void *)bloom);
 163   printf(" ->entries = %d\n", bloom->entries);
 164   printf(" ->error = %f\n", bloom->error);
 165   printf(" ->bits = %d\n", bloom->bits);
 166   printf(" ->bits per elem = %f\n", bloom->bpe);
 167   printf(" ->bytes = %d\n", bloom->bytes);
 168   printf(" ->hash functions = %d\n", bloom->hashes);
 169 }
 170
 171
 172 void bloom_free(struct bloom * bloom)
 173 {
 174   if (bloom->ready) {
 175     free(bloom->bf);
 176   }
 177   bloom->ready = 0;
 178 }
 179
 180
 181 int bloom_reset(struct bloom * bloom)
 182 {
 183   if (!bloom->ready) return 1;
 184   memset(bloom->bf, 0, bloom->bytes);
 185   return 0;
 186 }