lib/finger.c

   1 /*
   2  *      Sherlock Library -- String Fingerprints
   3  *
   4  *      (c) 2001--2003 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 /*
  11  *  We use a hashing function to map all the URL's and other
  12  *  hairy strings we work with to a much simpler universe
  13  *  of constant length bit strings (currently 96-bit ones).
  14  *  With a random hashing function (which is equivalent to
  15  *  having a fixed function and random input), the probability
  16  *  of at least one collision happening is at most c*n^2/m
  17  *  where n is the number of strings we hash, m is the size
  18  *  of our bit string universe (2^96) and c is a small constant.
  19  *  We set m sufficiently large and expect no collisions
  20  *  to occur. On the other hand, the worst thing which could
  21  *  be caused by a collision is mixing up two strings or labels
  22  *  of two documents which is relatively harmless.
  23  */
  24
  25 #include "lib/lib.h"
  26 #include "lib/index.h"
  27 #include "lib/md5.h"
  28
  29 #include <string.h>
  30
  31 void
  32 fingerprint(byte *string, struct fingerprint *fp)
  33 {
  34   struct MD5Context c;
  35   byte digest[16];
  36
  37   MD5Init(&c);
  38   MD5Update(&c, string, strlen(string));
  39   MD5Final(digest, &c);
  40   memcpy(fp->hash, digest, 12);
  41 }