ed1e212d577bc43193f827743d725c6842252734
[~helmut/ssdeep.git] / fuzzy.c
1 /* ssdeep
2  * Copyright (C) 2002 Andrew Tridgell <tridge@samba.org>
3  * Copyright (C) 2006 ManTech International Corporation
4  * Copyright (C) 2013 Helmut Grohne <helmut@subdivi.de>
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
19  *
20  * Earlier versions of this code were named fuzzy.c and can be found at:
21  *     http://www.samba.org/ftp/unpacked/junkcode/spamsum/
22  *     http://ssdeep.sf.net/
23  */
24
25 #include <assert.h>
26 #include <stdint.h>
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30
31 #if defined(__GNUC__) && __GNUC__ >= 3
32 #define likely(x)       __builtin_expect(!!(x), 1)
33 #define unlikely(x)     __builtin_expect(!!(x), 0)
34 #else
35 #define likely(x) x
36 #define unlikely(x) x
37 #endif
38
39 #define SPAMSUM_LENGTH 64
40 #define FUZZY_MAX_RESULT (SPAMSUM_LENGTH + (SPAMSUM_LENGTH/2 + 20))
41 #define ROLLING_WINDOW 7
42 #define MIN_BLOCKSIZE 3
43 #define HASH_PRIME 0x01000193
44 #define HASH_INIT 0x28021967
45
46 struct roll_state {
47         unsigned char window[ROLLING_WINDOW];
48         uint32_t h1, h2, h3;
49         uint32_t n;
50 };
51
52 static void roll_init(/*@out@*/ struct roll_state *self) {
53         memset(self, 0, sizeof(struct roll_state));
54 }
55
56 /*
57  * a rolling hash, based on the Adler checksum. By using a rolling hash
58  * we can perform auto resynchronisation after inserts/deletes
59
60  * internally, h1 is the sum of the bytes in the window and h2
61  * is the sum of the bytes times the index
62
63  * h3 is a shift/xor based rolling hash, and is mostly needed to ensure that
64  * we can cope with large blocksize values
65  */
66 static void roll_hash(struct roll_state *self, unsigned char c) {
67         self->h2 -= self->h1;
68         self->h2 += ROLLING_WINDOW * (uint32_t)c;
69
70         self->h1 += (uint32_t)c;
71         self->h1 -= (uint32_t)self->window[self->n % ROLLING_WINDOW];
72
73         self->window[self->n % ROLLING_WINDOW] = c;
74         self->n++;
75
76         /* The original spamsum AND'ed this value with 0xFFFFFFFF which
77          * in theory should have no effect. This AND has been removed
78          * for performance (jk) */
79         self->h3 <<= 5;
80         self->h3 ^= c;
81 }
82
83 static uint32_t roll_sum(const struct roll_state *self) {
84         return self->h1 + self->h2 + self->h3;
85 }
86
87 /* A simple non-rolling hash, based on the FNV hash. */
88 static uint32_t sum_hash(unsigned char c, uint32_t h) {
89         return (h * HASH_PRIME) ^ c;
90 }
91
92 /* A blockhash contains a signature state for a specific (implicit) blocksize.
93  * The blocksize is given by the start_blocksize from ssdeep_context times two
94  * to the power of the position of the element in the blockhashes member of
95  * ssdeep_context (head position = 0). The h and halfh members are the FNV
96  * hashes, where halfh stops to be reset after digest is SPAMSUM_LENGTH/2 long.
97  * The halfh hash is needed be able to truncate digest for the second output
98  * hash to stay compatible with ssdeep output. */
99 struct blockhash_context {
100         uint32_t h, halfh;
101         char digest[SPAMSUM_LENGTH];
102         unsigned int dlen;
103         /*@null@*/ /*@only@*/ struct blockhash_context *next;
104 };
105
106 static int blockhash_fork(struct blockhash_context *bh) {
107         struct blockhash_context *nbh;
108         if(NULL == (nbh = malloc(sizeof(struct blockhash_context))))
109                 return -1;
110         nbh->h = bh->h;
111         nbh->halfh = bh->halfh;
112         nbh->dlen = 0;
113         nbh->next = NULL;
114         assert(NULL == bh->next);
115         bh->next = nbh;
116         return 0;
117 }
118
119 struct ssdeep_context {
120         unsigned int start_blocksize;
121         /*@only@*/ struct blockhash_context *blockhashes;
122         size_t total_size;
123         struct roll_state roll;
124 };
125
126 static int ssdeep_init(/*@out@*/ struct ssdeep_context *self) {
127         self->blockhashes = malloc(sizeof(struct blockhash_context));
128         if(NULL == self->blockhashes)
129                 return -1;
130         self->start_blocksize = MIN_BLOCKSIZE;
131         self->blockhashes->h = HASH_INIT;
132         self->blockhashes->halfh = HASH_INIT;
133         self->blockhashes->dlen = 0;
134         self->blockhashes->next = NULL;
135         self->total_size = 0;
136         roll_init(&self->roll);
137         return 0;
138 }
139
140 static void ssdeep_try_reduce_blockhash(struct ssdeep_context *self) {
141         struct blockhash_context *bh;
142         if(NULL == (bh = self->blockhashes->next))
143                 /* Cannot remove last hash. */
144                 return;
145         if((size_t)self->start_blocksize * SPAMSUM_LENGTH >= self->total_size)
146                 /* Initial blocksize estimate would select this or a smaller
147                  * blocksize. */
148                 return;
149         if(bh->dlen < SPAMSUM_LENGTH / 2)
150                 /* Estimate adjustment would select this blocksize. */
151                 return;
152         /* At this point we are clearly no longer interested in the
153          * start_blocksize. Get rid of it. */
154         self->start_blocksize *= 2;
155         free(self->blockhashes);
156         self->blockhashes = bh;
157 }
158
159 static const char *b64 =
160         "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
161
162 static int ssdeep_engine_step(struct ssdeep_context *self, unsigned char c) {
163         size_t h;
164         unsigned int bs;
165         struct blockhash_context *bh;
166         /* At each character we update the rolling hash and the normal hashes.
167          * When the rolling hash hits a reset value then we emit a normal hash
168          * as a element of the signature and reset the normal hash. */
169         roll_hash(&self->roll, c);
170         h = roll_sum(&self->roll);
171
172         for(bh = self->blockhashes; NULL != bh; bh = bh->next) {
173                 bh->h = sum_hash(c, bh->h);
174                 bh->halfh = sum_hash(c, bh->halfh);
175         }
176
177         bs = self->start_blocksize;
178         bh = self->blockhashes;
179         while(bh != NULL) {
180                 /* With growing blocksize almost no runs fail the next test. */
181                 if(likely(h % bs != bs - 1))
182                         /* Once this condition is false for one bs, it is
183                          * automatically false for all further bs. I.e. if
184                          * h === -1 (mod 2*bs) then h === -1 (mod bs). */
185                         break;
186                 /* We don't need bs until next iteration. Update now, so we
187                  * don't forget about it. */
188                 bs *= 2;
189                 /* We have hit a reset point. We now emit hashes which are
190                  * based on all characters in the piece of the message between
191                  * the last reset point and this one */
192                 if(unlikely(0 == bh->dlen)) /* Can only happen 30 times. */
193                         /* First step for this blocksize. Clone next. */
194                         if(blockhash_fork(bh) < 0)
195                                 return -1;
196                 if(bh->dlen < SPAMSUM_LENGTH - 1) {
197                         /* We can have a problem with the tail overflowing. The
198                          * easiest way to cope with this is to only reset the
199                          * normal hash if we have room for more characters in
200                          * our signature. This has the effect of combining the
201                          * last few pieces of the message into a single piece
202                          * */
203                         bh->digest[bh->dlen++] = b64[bh->h % 64];
204                         bh->h = HASH_INIT;
205                         if(bh->dlen < SPAMSUM_LENGTH / 2)
206                                 bh->halfh = HASH_INIT;
207                 } else {
208                         /* The reduction might free bh. */
209                         bh = bh->next;
210                         ssdeep_try_reduce_blockhash(self);
211                         continue;
212                 }
213                 bh = bh->next;
214         }
215         ++self->total_size;
216         return 0;
217 }
218
219 static int ssdeep_engine(struct ssdeep_context *self,
220                 const unsigned char *buffer, size_t buffer_size) {
221         for( ;buffer_size > 0; ++buffer, --buffer_size)
222                 if(ssdeep_engine_step(self, *buffer) < 0)
223                         return -1;
224         return 0;
225 }
226
227 static void ssdeep_digest(const struct ssdeep_context *self,
228                 /*@out@*/ char *result) {
229         unsigned int bs = self->start_blocksize;
230         uint32_t h = roll_sum(&self->roll);
231         int i, remain = FUZZY_MAX_RESULT - 1;
232         const struct blockhash_context *bh = self->blockhashes, *bhp;
233         /* Verify that our elimination was not overeager. */
234         assert(bs == MIN_BLOCKSIZE ||
235                         (size_t)bs / 2 * SPAMSUM_LENGTH < self->total_size);
236
237         /* Initial blocksize guess. */
238         while((size_t)bs * SPAMSUM_LENGTH < self->total_size) {
239                 bs *= 2;
240                 assert(bh->next != NULL);
241                 bh = bh->next;
242         }
243         /* Adapt blocksize guess to actual digest length. */
244         while(bs > self->start_blocksize && bh->dlen < SPAMSUM_LENGTH / 2) {
245                 bs /= 2;
246                 /* Slow version of bh = bh->prev; */
247                 for(bhp = self->blockhashes; bhp->next != bh; bhp = bhp->next)
248                         ;
249                 bh = bhp;
250         }
251         assert(bh != NULL);
252         assert(!(bs > MIN_BLOCKSIZE && bh->dlen < SPAMSUM_LENGTH / 2));
253
254         i = snprintf(result, (size_t)remain, "%u:", bs);
255         /* In theory snprintf can fail. It is unclear how though, so we assume
256          * that it doesn't for simplicity. */
257         assert(i > 0);
258         assert(i < remain);
259         remain -= i;
260         result += i;
261         i = (int)bh->dlen;
262         if(i > remain)
263                 i = remain;
264         memcpy(result, bh->digest, (size_t)i);
265         result += i;
266         remain -= i;
267         if(remain > 0 && h != 0) {
268                 *result++ = b64[bh->h % 64];
269                 --remain;
270         }
271         if(remain > 0) {
272                 *result++ = ':';
273                 --remain;
274         }
275         if(NULL != bh->next) {
276                 bh = bh->next;
277                 i = (int)bh->dlen;
278                 if(i > SPAMSUM_LENGTH / 2 - 1)
279                         i = SPAMSUM_LENGTH / 2 - 1;
280                 if(i > remain)
281                         i = remain;
282                 memcpy(result, bh->digest, (size_t)i);
283                 result += i;
284                 remain -= i;
285                 if(remain > 0 && h != 0) {
286                         *result++ = b64[bh->halfh % 64];
287                         --remain;
288                 }
289         } else if(remain > 0 && h != 0) {
290                 assert(bh->dlen == 0);
291                 *result++ = b64[bh->h % 64];
292                 --remain;
293         }
294         *result = '\0';
295 }
296
297 static void ssdeep_clear(struct ssdeep_context *self) {
298         struct blockhash_context *bh, *bhn;
299         bh = self->blockhashes;
300         while(bh) {
301                 bhn = bh->next;
302                 free(bh);
303                 bh = bhn;
304         }
305 }
306
307 int fuzzy_hash_buf(const unsigned char *buf, uint32_t buf_len,
308                 /*@out@*/ char *result) {
309         struct ssdeep_context ctx[1];
310         if(ssdeep_init(ctx) < 0)
311                 return -1;
312         if(ssdeep_engine(ctx, buf, buf_len) < 0) {
313                 ssdeep_clear(ctx);
314                 return -1;
315         }
316         ssdeep_digest(ctx, result);
317         ssdeep_clear(ctx);
318         return 0;
319 }
320
321 int fuzzy_hash_stream(FILE *handle, /*@out@*/ char *result) {
322         struct ssdeep_context ctx[1];
323         unsigned char buffer[4096];
324         size_t n;
325         if(ssdeep_init(ctx) < 0)
326                 return -1;
327         for(;;) {
328                 n = fread(buffer, 1, 4096, handle);
329                 if(0 == n)
330                         break;
331                 if(ssdeep_engine(ctx, buffer, n) < 0)
332                         goto errout;
333         }
334         if(ferror(handle) != 0)
335                 goto errout;
336         ssdeep_digest(ctx, result);
337         ssdeep_clear(ctx);
338         return 0;
339 errout:
340         ssdeep_clear(ctx);
341         return -1;
342 }
343
344 #ifdef S_SPLINT_S
345 typedef size_t off_t;
346 #endif
347
348 int fuzzy_hash_file(FILE *handle, /*@out@*/ char *result) {
349         off_t fpos;
350         int status;
351         fpos = ftello(handle);
352         if(fseek(handle, 0, SEEK_SET) < 0)
353                 return -1;
354         status = fuzzy_hash_stream(handle, result);
355         if(status == 0)
356                 if(fseeko(handle, fpos, SEEK_SET) < 0)
357                         return -1;
358         return status;
359 }
360
361 int fuzzy_hash_filename(const char *filename, /*@out@*/ char *result) {
362         int status;
363         FILE *handle = fopen(filename, "rb");
364         if(NULL == handle)
365                 return -1;
366         status = fuzzy_hash_stream(handle, result);
367         /* We cannot do anything about an fclose failure. */
368         (void)fclose(handle);
369         return status;
370 }
371
372 #ifdef S_SPLINT_S
373 extern /*@only@*/ /*@null@*/ char *realpath(const char *,
374                 /*@null@*/ const char *);
375 #endif
376
377 int main(int argc, char **argv) {
378         char digest[FUZZY_MAX_RESULT], *p;
379         int i;
380         puts("ssdeep,1.1--blocksize:hash:hash,filename");
381         for(i = 1; i < argc; ++i) {
382                 p = realpath(argv[i], NULL);
383                 if(p == NULL)
384                         return 1;
385                 if(fuzzy_hash_filename(argv[i], digest) < 0) {
386                         free(p);
387                         return 1;
388                 }
389                 printf("%s,\"%s\"\n", digest, p);
390                 free(p);
391         }
392         return 0;
393 }