fix comment for array implementation
[~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 #define NUM_BLOCKHASHES 31
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 SSDEEP_BS(index). The h and halfh members are the
94  * FNV hashes, where halfh stops to be reset after digest is SPAMSUM_LENGTH/2
95  * long. The halfh hash is needed be able to truncate digest for the second
96  * output hash to stay compatible with ssdeep output. */
97 struct blockhash_context {
98         uint32_t h, halfh;
99         char digest[SPAMSUM_LENGTH];
100         unsigned int dlen;
101 };
102
103 struct ssdeep_context {
104         unsigned int bhstart, bhend;
105         struct blockhash_context bh[NUM_BLOCKHASHES];
106         size_t total_size;
107         struct roll_state roll;
108 };
109
110 #define SSDEEP_BS(index) (((uint32_t)MIN_BLOCKSIZE) << (index))
111
112 static /*@only@*/ /*@null@*/ struct ssdeep_context *ssdeep_new(void) {
113         struct ssdeep_context *self;
114         if(NULL == (self = malloc(sizeof(struct ssdeep_context))))
115                 return NULL;
116         self->bhstart = 0;
117         self->bhend = 1;
118         self->bh[0].h = HASH_INIT;
119         self->bh[0].halfh = HASH_INIT;
120         self->bh[0].dlen = 0;
121         self->total_size = 0;
122         roll_init(&self->roll);
123         return self;
124 }
125
126 static void ssdeep_try_fork_blockhash(struct ssdeep_context *self) {
127         struct blockhash_context *obh, *nbh;
128         if(self->bhend >= NUM_BLOCKHASHES)
129                 return;
130         assert(self->bhend > 0);
131         obh = self->bh + (self->bhend - 1);
132         nbh = obh + 1;
133         nbh->h = obh->h;
134         nbh->halfh = obh->halfh;
135         nbh->dlen = 0;
136         ++self->bhend;
137 }
138
139 static void ssdeep_try_reduce_blockhash(struct ssdeep_context *self) {
140         assert(self->bhstart < self->bhend);
141         if(self->bhend - self->bhstart < 2)
142                 /* Need at least two working hashes. */
143                 return;
144         if((size_t)SSDEEP_BS(self->bhstart) * SPAMSUM_LENGTH >=
145                         self->total_size)
146                 /* Initial blocksize estimate would select this or a smaller
147                  * blocksize. */
148                 return;
149         if(self->bh[self->bhstart + 1].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->bhstart;
155 }
156
157 static const char *b64 =
158         "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
159
160 static void ssdeep_engine_step(struct ssdeep_context *self, unsigned char c) {
161         size_t h;
162         unsigned int i;
163         /* At each character we update the rolling hash and the normal hashes.
164          * When the rolling hash hits a reset value then we emit a normal hash
165          * as a element of the signature and reset the normal hash. */
166         roll_hash(&self->roll, c);
167         h = roll_sum(&self->roll);
168
169         for(i = self->bhstart; i < self->bhend; ++i) {
170                 self->bh[i].h = sum_hash(c, self->bh[i].h);
171                 self->bh[i].halfh = sum_hash(c, self->bh[i].halfh);
172         }
173
174         for(i = self->bhstart; i < self->bhend; ++i) {
175                 /* With growing blocksize almost no runs fail the next test. */
176                 if(likely(h % SSDEEP_BS(i) != SSDEEP_BS(i) - 1))
177                         /* Once this condition is false for one bs, it is
178                          * automatically false for all further bs. I.e. if
179                          * h === -1 (mod 2*bs) then h === -1 (mod bs). */
180                         break;
181                 /* We have hit a reset point. We now emit hashes which are
182                  * based on all characters in the piece of the message between
183                  * the last reset point and this one */
184                 if(unlikely(0 == self->bh[i].dlen)) {
185                         /* Can only happen 30 times. */
186                         /* First step for this blocksize. Clone next. */
187                         ssdeep_try_fork_blockhash(self);
188                 }
189                 if(self->bh[i].dlen < SPAMSUM_LENGTH - 1) {
190                         /* We can have a problem with the tail overflowing. The
191                          * easiest way to cope with this is to only reset the
192                          * normal hash if we have room for more characters in
193                          * our signature. This has the effect of combining the
194                          * last few pieces of the message into a single piece
195                          * */
196                         self->bh[i].digest[self->bh[i].dlen++] =
197                                 b64[self->bh[i].h % 64];
198                         self->bh[i].h = HASH_INIT;
199                         if(self->bh[i].dlen < SPAMSUM_LENGTH / 2)
200                                 self->bh[i].halfh = HASH_INIT;
201                 } else
202                         ssdeep_try_reduce_blockhash(self);
203         }
204 }
205
206 static int ssdeep_engine(struct ssdeep_context *self,
207                 const unsigned char *buffer, size_t buffer_size) {
208         self->total_size += buffer_size;
209         for( ;buffer_size > 0; ++buffer, --buffer_size)
210                 ssdeep_engine_step(self, *buffer);
211         return 0;
212 }
213
214 static int ssdeep_digest(const struct ssdeep_context *self,
215                 /*@out@*/ char *result) {
216         unsigned int bi = self->bhstart;
217         uint32_t h = roll_sum(&self->roll);
218         int i, remain = FUZZY_MAX_RESULT - 1;
219         /* Verify that our elimination was not overeager. */
220         assert(bi == 0 || (size_t)SSDEEP_BS(bi) / 2 * SPAMSUM_LENGTH <
221                         self->total_size);
222
223         /* Initial blocksize guess. */
224         while((size_t)SSDEEP_BS(bi) * SPAMSUM_LENGTH < self->total_size) {
225                 ++bi;
226                 if(bi >= self->bhend)
227                         /* The input exceeds data types. */
228                         return -1;
229         }
230         /* Adapt blocksize guess to actual digest length. */
231         while(bi > self->bhstart && self->bh[bi].dlen < SPAMSUM_LENGTH / 2)
232                 --bi;
233         assert(!(bi > 0 && self->bh[bi].dlen < SPAMSUM_LENGTH / 2));
234
235         i = snprintf(result, (size_t)remain, "%u:", SSDEEP_BS(bi));
236         if(i <= 0)
237                 return -1;
238         assert(i < remain);
239         remain -= i;
240         result += i;
241         i = (int)self->bh[bi].dlen;
242         if(i > remain)
243                 i = remain;
244         memcpy(result, self->bh[bi].digest, (size_t)i);
245         result += i;
246         remain -= i;
247         if(remain > 0 && h != 0) {
248                 *result++ = b64[self->bh[bi].h % 64];
249                 --remain;
250         }
251         if(remain > 0) {
252                 *result++ = ':';
253                 --remain;
254         }
255         if(bi < self->bhend - 1) {
256                 ++bi;
257                 i = (int)self->bh[bi].dlen;
258                 if(i > SPAMSUM_LENGTH / 2 - 1)
259                         i = SPAMSUM_LENGTH / 2 - 1;
260                 if(i > remain)
261                         i = remain;
262                 memcpy(result, self->bh[bi].digest, (size_t)i);
263                 result += i;
264                 remain -= i;
265                 if(remain > 0 && h != 0) {
266                         *result++ = b64[self->bh[bi].halfh % 64];
267                         --remain;
268                 }
269         } else if(remain > 0 && h != 0) {
270                 assert(self->bh[bi].dlen == 0);
271                 *result++ = b64[self->bh[bi].h % 64];
272                 --remain;
273         }
274         *result = '\0';
275         return 0;
276 }
277
278 static void ssdeep_free(/*@only@*/ struct ssdeep_context *self) {
279         free(self);
280 }
281
282 int fuzzy_hash_buf(const unsigned char *buf, uint32_t buf_len,
283                 /*@out@*/ char *result) {
284         struct ssdeep_context *ctx;
285         int ret = -1;
286         if(NULL == (ctx = ssdeep_new()))
287                 return -1;
288         if(ssdeep_engine(ctx, buf, buf_len) < 0)
289                 goto out;
290         if(ssdeep_digest(ctx, result) < 0)
291                 goto out;
292         ret = 0;
293 out:
294         ssdeep_free(ctx);
295         return ret;
296 }
297
298 int fuzzy_hash_stream(FILE *handle, /*@out@*/ char *result) {
299         struct ssdeep_context *ctx;
300         unsigned char buffer[4096];
301         size_t n;
302         int ret = -1;
303         if(NULL == (ctx = ssdeep_new()))
304                 return -1;
305         for(;;) {
306                 n = fread(buffer, 1, 4096, handle);
307                 if(0 == n)
308                         break;
309                 if(ssdeep_engine(ctx, buffer, n) < 0)
310                         goto out;
311         }
312         if(ferror(handle) != 0)
313                 goto out;
314         if(ssdeep_digest(ctx, result) < 0)
315                 goto out;
316         ret = 0;
317 out:
318         ssdeep_free(ctx);
319         return ret;
320 }
321
322 #ifdef S_SPLINT_S
323 typedef size_t off_t;
324 int fseeko(FILE *, off_t, int);
325 off_t ftello(FILE *);
326 #endif
327
328 int fuzzy_hash_file(FILE *handle, /*@out@*/ char *result) {
329         off_t fpos;
330         int status;
331         fpos = ftello(handle);
332         if(fseek(handle, 0, SEEK_SET) < 0)
333                 return -1;
334         status = fuzzy_hash_stream(handle, result);
335         if(status == 0)
336                 if(fseeko(handle, fpos, SEEK_SET) < 0)
337                         return -1;
338         return status;
339 }
340
341 int fuzzy_hash_filename(const char *filename, /*@out@*/ char *result) {
342         int status;
343         FILE *handle = fopen(filename, "rb");
344         if(NULL == handle)
345                 return -1;
346         status = fuzzy_hash_stream(handle, result);
347         /* We cannot do anything about an fclose failure. */
348         (void)fclose(handle);
349         return status;
350 }
351