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>
13 #include "rabinpoly.h"
14 #include "gsimm.h"
16 #define MIN(x,y) ((y)<(x) ? (y) : (x))
17 #define MAX(x,y) ((y)>(x) ? (y) : (x))
19 /* The RABIN_WINDOW_SIZE is the size of fingerprint window used by
20 Rabin algorithm. This is not a modifiable parameter.
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 */
29 typedef struct fileinfo
30 { char *name;
31 size_t length;
32 u_char md[MD_LENGTH];
33 int match;
34 } File;
36 int flag_verbose = 0;
37 int flag_debug = 0;
38 char *flag_relative = 0;
40 char cmd[12] = " ...";
41 char md_strbuf[MD_LENGTH * 2 + 1];
42 u_char relative_md [MD_LENGTH];
44 File *file;
45 int file_count;
46 size_t file_bytes;
48 char hex[17] = "0123456789abcdef";
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 }
61 int dist (u_char *l, u_char *r)
62 { int j, k;
63 int d = 0;
65 for (j = 0; j < MD_LENGTH; j++)
66 { u_char ch = l[j] ^ r[j];
68 for (k = 0; k < 8; k++) d += ((ch & (1<<k)) > 0);
69 }
71 return d;
72 }
74 char *md_to_str(u_char *md)
75 { int j;
77 for (j = 0; j < MD_LENGTH; j++)
78 { u_char ch = md[j];
80 md_strbuf[j*2] = hex[ch >> 4];
81 md_strbuf[j*2+1] = hex[ch & 0xF];
82 }
84 md_strbuf[j*2] = 0;
85 return md_strbuf;
86 }
88 void process_file (char *name)
89 { int fd;
90 struct stat fs;
91 u_char *data;
92 File *fi = file+file_count;;
94 fd = open (name, O_RDONLY, 0);
95 if (fd < 0)
96 { perror (name);
97 exit (2);
98 }
100 if (fstat (fd, &fs))
101 { perror (name);
102 exit (2);
103 }
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;
110 data = (u_char *) mmap (0, fs.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
112 if (data == (u_char *) -1)
113 { perror (name);
114 exit (2);
115 }
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); }
138 close (fd);
139 }
141 u_char *str_to_md(char *str, u_char *md)
142 { int j;
144 if (!md || !str) return 0;
146 bzero (md, MD_LENGTH);
148 for (j = 0; j < MD_LENGTH * 2; j++)
149 { char ch = str[j];
151 if (ch >= '0' && ch <= '9')
152 { md [j/2] = (md [j/2] << 4) + (ch - '0');
153 }
154 else
155 { ch |= 32;
157 if (ch < 'a' || ch > 'f') break;
158 md [j/2] = (md[j/2] << 4) + (ch - 'a' + 10);
159 } }
161 return (j != MD_LENGTH * 2 || str[j] != 0) ? 0 : md;
162 }
164 int main (int argc, char *argv[])
165 { int ch, j;
167 strncpy (cmd, basename (argv[0]), 8);
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 } }
190 argc -= optind;
191 argv += optind;
193 if (argc == 0) usage();
195 rabin_reset ();
196 if (flag_verbose && flag_relative)
197 { fprintf (stdout, "distances are relative to %s\n", flag_relative);
198 }
200 file = (File *) calloc (argc, sizeof (File));
202 for (j = 0; j < argc; j++) process_file (argv[j]);
204 if (flag_verbose)
205 { fprintf (stdout, "%li bytes in %i files\n", (long) file_bytes, file_count);
206 }
208 return 0;
209 }