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