test-gsimm.c

   1 #include <unistd.h>
   2 #include <stdlib.h>
   3 #include <fcntl.h>
   4 #include <libgen.h>
   5 #include <stdio.h>
   6 #include <assert.h>
   7 #include <math.h>
   8 #include <string.h>
   9 #include <sys/types.h>
  10 #include <sys/stat.h>
  11 #include <sys/mman.h>
  12
  13 #include "rabinpoly.h"
  14 #include "gsimm.h"
  15
  16 #define MIN(x,y) ((y)<(x) ? (y) : (x))
  17 #define MAX(x,y) ((y)>(x) ? (y) : (x))
  18
  19 /* The RABIN_WINDOW_SIZE is the size of fingerprint window used by
  20    Rabin algorithm. This is not a modifiable parameter.
  21
  22    The first RABIN_WINDOW_SIZE - 1 bytes are skipped, in order to ensure
  23    fingerprints are good hashes. This does somewhat reduce the
  24    influence of the first few bytes in the file (they're part of
  25    fewer windows, like the last few bytes), but that actually isn't
  26    so bad as files often start with fixed content that may bias comparisons.
  27 */
  28
  29 typedef struct fileinfo
  30 { char          *name;
  31   size_t        length;
  32   u_char        md[MD_LENGTH];
  33   int           match;
  34 } File;
  35
  36 int flag_verbose = 0;
  37 int flag_debug = 0;
  38 char *flag_relative = 0;
  39
  40 char cmd[12] = "        ...";
  41 char md_strbuf[MD_LENGTH * 2 + 1];
  42 u_char relative_md [MD_LENGTH];
  43
  44 File *file;
  45 int    file_count;
  46 size_t file_bytes;
  47
  48 char hex[17] = "0123456789abcdef";
  49
  50 void usage()
  51 {  fprintf (stderr, "usage: %s [-dhvw] [-r fingerprint] file ...\n", cmd);
  52    fprintf (stderr, " -d\tdebug output, repeate for more verbosity\n");
  53    fprintf (stderr, " -h\tshow this usage information\n");
  54    fprintf (stderr, " -r\tshow distance relative to fingerprint "
  55                     "(%u hex digits)\n", MD_LENGTH * 2);
  56    fprintf (stderr, " -v\tverbose output, repeat for even more verbosity\n");
  57    fprintf (stderr, " -w\tenable warnings for suspect statistics\n");
  58    exit (1);
  59 }
  60
  61 int dist (u_char *l, u_char *r)
  62 { int j, k;
  63   int d = 0;
  64
  65   for (j = 0; j < MD_LENGTH; j++)
  66   { u_char ch = l[j] ^ r[j];
  67
  68     for (k = 0; k < 8; k++) d += ((ch & (1<<k)) > 0);
  69   }
  70
  71   return d;
  72 }
  73
  74 char *md_to_str(u_char *md)
  75 { int j;
  76
  77   for (j = 0; j < MD_LENGTH; j++)
  78   { u_char ch = md[j];
  79
  80     md_strbuf[j*2] = hex[ch >> 4];
  81     md_strbuf[j*2+1] = hex[ch & 0xF];
  82   }
  83
  84   md_strbuf[j*2] = 0;
  85   return md_strbuf;
  86 }
  87
  88 void process_file (char *name)
  89 { int fd;
  90   struct stat fs;
  91   u_char *data;
  92   File *fi = file+file_count;;
  93
  94   fd = open (name, O_RDONLY, 0);
  95   if (fd < 0)
  96   { perror (name);
  97     exit (2);
  98   }
  99
 100   if (fstat (fd, &fs))
 101   { perror (name);
 102     exit (2);
 103   }
 104
 105   if (fs.st_size >= MIN_FILE_SIZE
 106       && fs.st_size <= MAX_FILE_SIZE)
 107   { fi->length = fs.st_size;
 108     fi->name = name;
 109
 110     data = (u_char *) mmap (0, fs.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
 111
 112     if (data == (u_char *) -1)
 113     { perror (name);
 114       exit (2);
 115     }
 116
 117     gb_simm_process (data, fs.st_size, fi->md);
 118     if (flag_relative)
 119     { int d = dist (fi->md, relative_md);
 120       double sim = 1.0 - MIN (1.0, (double) (d) / (MD_LENGTH * 4 - 1));
 121       fprintf (stdout, "%s %llu %u %s %u %3.1f\n",
 122                md_to_str (fi->md), (long long unsigned) 0,
 123                (unsigned) fs.st_size, name,
 124                d, 100.0 * sim);
 125     }
 126     else
 127     {
 128       fprintf (stdout, "%s %llu %u %s\n",
 129                md_to_str (fi->md), (long long unsigned) 0,
 130                (unsigned) fs.st_size, name);
 131     }
 132     munmap (data, fs.st_size);
 133     file_bytes += fs.st_size;
 134     file_count++;
 135   } else if (flag_verbose)
 136   { fprintf (stdout, "skipping %s (size %llu)\n", name, (long long unsigned) fs.st_size); }
 137
 138   close (fd);
 139 }
 140
 141 u_char *str_to_md(char *str, u_char *md)
 142 { int j;
 143
 144   if (!md || !str) return 0;
 145
 146   bzero (md, MD_LENGTH);
 147
 148   for (j = 0; j < MD_LENGTH * 2; j++)
 149   { char ch = str[j];
 150
 151     if (ch >= '0' && ch <= '9')
 152     { md [j/2] = (md [j/2] << 4) + (ch - '0');
 153     }
 154     else
 155     { ch |= 32;
 156
 157       if (ch < 'a' || ch > 'f') break;
 158       md [j/2] = (md[j/2] << 4) + (ch - 'a' + 10);
 159   } }
 160
 161   return (j != MD_LENGTH * 2 || str[j] != 0) ? 0 : md;
 162 }
 163
 164 int main (int argc, char *argv[])
 165 { int ch, j;
 166
 167   strncpy (cmd, basename (argv[0]), 8);
 168
 169   while ((ch = getopt(argc, argv, "dhr:vw")) != -1)
 170   { switch (ch)
 171     { case 'd': flag_debug++;
 172                 break;
 173       case 'r': if (!optarg)
 174                 { fprintf (stderr, "%s: missing argument for -r\n", cmd);
 175                   return 1;
 176                 }
 177                 if (str_to_md (optarg, relative_md)) flag_relative = optarg;
 178                 else
 179                 { fprintf (stderr, "%s: not a valid fingerprint\n", optarg);
 180                   return 1;
 181                 }
 182                 break;
 183       case 'v': flag_verbose++;
 184                 break;
 185       case 'w': break;
 186       default : usage();
 187                 return (ch != 'h');
 188   } }
 189
 190   argc -= optind;
 191   argv += optind;
 192
 193   if (argc == 0) usage();
 194
 195   rabin_reset ();
 196   if (flag_verbose && flag_relative)
 197   { fprintf (stdout, "distances are relative to %s\n", flag_relative);
 198   }
 199
 200   file = (File *) calloc (argc, sizeof (File));
 201
 202   for (j = 0; j < argc; j++) process_file (argv[j]);
 203
 204   if (flag_verbose)
 205   { fprintf (stdout, "%li bytes in %i files\n", (long) file_bytes, file_count);
 206   }
 207
 208   return 0;
 209 }