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