lib/bitsig.c

   1 /*
   2  *      Bit Array Signatures -- A Dubious Detector of Duplicates
   3  *
   4  *      (c) 2002 Martin Mares <mj@ucw.cz>
   5  *
   6  *      FIXME: Ref to the original article.
   7  *
   8  *      This data structure provides a very compact representation
   9  *      of a set of strings with insertion and membership search,
  10  *      but with a certain low probability it cheats by incidentally
  11  *      reporting a non-member as a member. Generally the larger you
  12  *      create the structure, the lower this probability is.
  13  *
  14  *      How does it work: the structure is just an array of M bits
  15  *      and each possible element is hashed to a set of (at most) L
  16  *      bit positions. For each element of the represented set, we
  17  *      set its L bits to ones and we report as present all elements
  18  *      whose all L bits ar set.
  19  *
  20  *      Analysis: Let's assume N items have already been stored and let A
  21  *      denote L/M (density of the hash function). The probability that
  22  *      a fixed bit of the array is set by any of the N items is
  23  *      1 - (1-1/M)^(NL) = 1 - ((1-1/M)^M)^NA = approx. 1 - e^-NA.
  24  *      This is minimized by setting A=(ln 2)/N (try taking derivative).
  25  *      Given a non-present item, the probability that all of the bits
  26  *      corresponding to this item are set by the other items (that is,
  27  *      the structure gives a false answer) is (1-e^-NA)^L = 2^-L.
  28  *      Hence, if we want to give false answers with probability less
  29  *      than epsilon, we take L := -log_2 epsilon, M := 1.45*N*L.
  30  *
  31  *      Example: For a set of 10^7 items with P[error] < 10^-6, we set
  32  *      L := 20 and M :=  290*10^6 bits = cca 34.5 MB (29 bits per item).
  33  *
  34  *      We leave L and an upper bound for N as parameters set during
  35  *      creation of the structure. Currently, the structure is limited
  36  *      to 4 Gb = 512 MB.
  37  */
  38
  39 #include "lib/lib.h"
  40 #include "lib/bitsig.h"
  41 #include "lib/md5.h"
  42
  43 #include <string.h>
  44
  45 struct bitsig {
  46   uns l, m, n, maxn, max_m_mult;
  47   u32 tmp;
  48   byte array[0];
  49 };
  50
  51 struct bitsig *
  52 bitsig_init(uns perrlog, uns maxn)
  53 {
  54   struct bitsig *b;
  55   u64 m;
  56   uns mbytes;
  57
  58   m = ((u64) maxn * perrlog * 145 + 99) / 100;
  59   if (m >= (u64) 1 << 32)
  60     die("bitsig_init: bitsig array too large (maximum is 4 Gb)");
  61   mbytes = (m + 7) >> 3U;
  62   b = xmalloc(sizeof(struct bitsig) + mbytes);
  63   b->l = perrlog;
  64   b->m = m;
  65   b->n = 0;
  66   b->maxn = maxn;
  67   b->max_m_mult = (0xffffffff / m) * m;
  68   bzero(b->array, mbytes);
  69   log(L_DEBUG, "Initialized bitsig array with l=%d, m=%u (%u KB), expecting %d items", b->l, b->m, (mbytes+1023)/1024, maxn);
  70   return b;
  71 }
  72
  73 static void
  74 bitsig_hash_init(struct bitsig *b, byte *item)
  75 {
  76   struct MD5Context c;
  77   u32 digest[4];
  78
  79   MD5Init(&c);
  80   MD5Update(&c, item, strlen(item));
  81   MD5Final((byte *) digest, &c);
  82   b->tmp = digest[0];
  83 }
  84
  85 static inline uns
  86 bitsig_hash_bit(struct bitsig *b)
  87 {
  88   do
  89     {
  90       /* FIXME: Check */
  91       b->tmp *= 3006477127U;
  92     }
  93   while (b->tmp >= b->max_m_mult);
  94   return b->tmp % b->m;
  95 }
  96
  97 int
  98 bitsig_member(struct bitsig *b, byte *item)
  99 {
 100   uns i, bit;
 101
 102   bitsig_hash_init(b, item);
 103   for (i=0; i<b->l; i++)
 104     {
 105       bit = bitsig_hash_bit(b);
 106       if (!(b->array[bit >> 3] & (1 << (bit & 7))))
 107         return 0;
 108     }
 109   return 1;
 110 }
 111
 112 int
 113 bitsig_insert(struct bitsig *b, byte *item)
 114 {
 115   uns i, bit, was;
 116
 117   bitsig_hash_init(b, item);
 118   was = 1;
 119   for (i=0; i<b->l; i++)
 120     {
 121       bit = bitsig_hash_bit(b);
 122       if (!(b->array[bit >> 3] & (1 << (bit & 7))))
 123         {
 124           was = 0;
 125           b->array[bit >> 3] |= (1 << (bit & 7));
 126         }
 127     }
 128   if (!was && b->n++ == b->maxn+1)
 129     log(L_ERROR, "bitsig: Too many items inserted, error rate will be higher than estimated!");
 130   return was;
 131 }
 132
 133 #ifdef TEST
 134
 135 #include <stdio.h>
 136
 137 int main(void)
 138 {
 139   struct bitsig *b = bitsig_init(10, 23000);
 140   byte buf[1024];
 141
 142   while (fgets(buf, 1024, stdin))
 143     printf("%d\n", bitsig_insert(b, buf));
 144
 145   return 0;
 146 }
 147
 148 #endif