Fix zlib CVE-2016-9840.
[rsync.git] / hashtable.c
1 /*
2  * Routines to provide a memory-efficient hashtable.
3  *
4  * Copyright (C) 2007-2019 Wayne Davison
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 3 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 along
17  * with this program; if not, visit the http://fsf.org website.
18  */
19
20 #include "rsync.h"
21
22 #define HASH_LOAD_LIMIT(size) ((size)*3/4)
23
24 struct hashtable *hashtable_create(int size, int key64)
25 {
26         int req = size;
27         struct hashtable *tbl;
28         int node_size = key64 ? sizeof (struct ht_int64_node)
29                               : sizeof (struct ht_int32_node);
30
31         /* Pick a power of 2 that can hold the requested size. */
32         if (size & (size-1) || size < 16) {
33                 size = 16;
34                 while (size < req)
35                         size *= 2;
36         }
37
38         if (!(tbl = new(struct hashtable))
39          || !(tbl->nodes = new_array0(char, size * node_size)))
40                 out_of_memory("hashtable_create");
41         tbl->size = size;
42         tbl->entries = 0;
43         tbl->node_size = node_size;
44         tbl->key64 = key64 ? 1 : 0;
45
46         if (DEBUG_GTE(HASH, 1)) {
47                 char buf[32];
48                 if (req != size)
49                         snprintf(buf, sizeof buf, "req: %d, ", req);
50                 else
51                         *buf = '\0';
52                 rprintf(FINFO, "[%s] created hashtable %lx (%ssize: %d, keys: %d-bit)\n",
53                         who_am_i(), (long)tbl, buf, size, key64 ? 64 : 32);
54         }
55
56         return tbl;
57 }
58
59 void hashtable_destroy(struct hashtable *tbl)
60 {
61         if (DEBUG_GTE(HASH, 1)) {
62                 rprintf(FINFO, "[%s] destroyed hashtable %lx (size: %d, keys: %d-bit)\n",
63                         who_am_i(), (long)tbl, tbl->size, tbl->key64 ? 64 : 32);
64         }
65         free(tbl->nodes);
66         free(tbl);
67 }
68
69 /* This returns the node for the indicated key, either newly created or
70  * already existing.  Returns NULL if not allocating and not found. */
71 void *hashtable_find(struct hashtable *tbl, int64 key, int allocate_if_missing)
72 {
73         int key64 = tbl->key64;
74         struct ht_int32_node *node;
75         uint32 ndx;
76
77         if (key64 ? key == 0 : (int32)key == 0) {
78                 rprintf(FERROR, "Internal hashtable error: illegal key supplied!\n");
79                 exit_cleanup(RERR_MESSAGEIO);
80         }
81
82         if (allocate_if_missing && tbl->entries > HASH_LOAD_LIMIT(tbl->size)) {
83                 void *old_nodes = tbl->nodes;
84                 int size = tbl->size * 2;
85                 int i;
86
87                 if (!(tbl->nodes = new_array0(char, size * tbl->node_size)))
88                         out_of_memory("hashtable_node");
89                 tbl->size = size;
90                 tbl->entries = 0;
91
92                 if (DEBUG_GTE(HASH, 1)) {
93                         rprintf(FINFO, "[%s] growing hashtable %lx (size: %d, keys: %d-bit)\n",
94                                 who_am_i(), (long)tbl, size, key64 ? 64 : 32);
95                 }
96
97                 for (i = size / 2; i-- > 0; ) {
98                         struct ht_int32_node *move_node = HT_NODE(tbl, old_nodes, i);
99                         int64 move_key = HT_KEY(move_node, key64);
100                         if (move_key == 0)
101                                 continue;
102                         node = hashtable_find(tbl, move_key, 1);
103                         node->data = move_node->data;
104                 }
105
106                 free(old_nodes);
107         }
108
109         if (!key64) {
110                 /* Based on Jenkins One-at-a-time hash. */
111                 uchar buf[4], *keyp = buf;
112                 int i;
113
114                 SIVALu(buf, 0, key);
115                 for (ndx = 0, i = 0; i < 4; i++) {
116                         ndx += keyp[i];
117                         ndx += (ndx << 10);
118                         ndx ^= (ndx >> 6);
119                 }
120                 ndx += (ndx << 3);
121                 ndx ^= (ndx >> 11);
122                 ndx += (ndx << 15);
123         } else {
124                 /* Based on Jenkins hashword() from lookup3.c. */
125                 uint32 a, b, c;
126
127                 /* Set up the internal state */
128                 a = b = c = 0xdeadbeef + (8 << 2);
129
130 #define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k))))
131 #if SIZEOF_INT64 >= 8
132                 b += (uint32)(key >> 32);
133 #endif
134                 a += (uint32)key;
135                 c ^= b; c -= rot(b, 14);
136                 a ^= c; a -= rot(c, 11);
137                 b ^= a; b -= rot(a, 25);
138                 c ^= b; c -= rot(b, 16);
139                 a ^= c; a -= rot(c, 4);
140                 b ^= a; b -= rot(a, 14);
141                 c ^= b; c -= rot(b, 24);
142 #undef rot
143                 ndx = c;
144         }
145
146         /* If it already exists, return the node.  If we're not
147          * allocating, return NULL if the key is not found. */
148         while (1) {
149                 int64 nkey;
150
151                 ndx &= tbl->size - 1;
152                 node = HT_NODE(tbl, tbl->nodes, ndx);
153                 nkey = HT_KEY(node, key64);
154
155                 if (nkey == key)
156                         return node;
157                 if (nkey == 0) {
158                         if (!allocate_if_missing)
159                                 return NULL;
160                         break;
161                 }
162                 ndx++;
163         }
164
165         /* Take over this empty spot and then return the node. */
166         if (key64)
167                 ((struct ht_int64_node*)node)->key = key;
168         else
169                 node->key = (int32)key;
170         tbl->entries++;
171         return node;
172 }
173
174 #ifndef WORDS_BIGENDIAN
175 # define HASH_LITTLE_ENDIAN 1
176 # define HASH_BIG_ENDIAN 0
177 #else
178 # define HASH_LITTLE_ENDIAN 0
179 # define HASH_BIG_ENDIAN 1
180 #endif
181
182 /*
183  -------------------------------------------------------------------------------
184  lookup3.c, by Bob Jenkins, May 2006, Public Domain.
185
186  These are functions for producing 32-bit hashes for hash table lookup.
187  hash_word(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
188  are externally useful functions.  Routines to test the hash are included
189  if SELF_TEST is defined.  You can use this free for any purpose.  It's in
190  the public domain.  It has no warranty.
191
192  You probably want to use hashlittle().  hashlittle() and hashbig()
193  hash byte arrays.  hashlittle() is is faster than hashbig() on
194  little-endian machines.  Intel and AMD are little-endian machines.
195  On second thought, you probably want hashlittle2(), which is identical to
196  hashlittle() except it returns two 32-bit hashes for the price of one.
197  You could implement hashbig2() if you wanted but I haven't bothered here.
198
199  If you want to find a hash of, say, exactly 7 integers, do
200    a = i1;  b = i2;  c = i3;
201    mix(a,b,c);
202    a += i4; b += i5; c += i6;
203    mix(a,b,c);
204    a += i7;
205    final(a,b,c);
206  then use c as the hash value.  If you have a variable length array of
207  4-byte integers to hash, use hash_word().  If you have a byte array (like
208  a character string), use hashlittle().  If you have several byte arrays, or
209  a mix of things, see the comments above hashlittle().
210
211  Why is this so big?  I read 12 bytes at a time into 3 4-byte integers,
212  then mix those integers.  This is fast (you can do a lot more thorough
213  mixing with 12*3 instructions on 3 integers than you can with 3 instructions
214  on 1 byte), but shoehorning those bytes into integers efficiently is messy.
215 */
216
217 #define hashsize(n) ((uint32_t)1<<(n))
218 #define hashmask(n) (hashsize(n)-1)
219 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
220
221 /*
222  -------------------------------------------------------------------------------
223  mix -- mix 3 32-bit values reversibly.
224
225  This is reversible, so any information in (a,b,c) before mix() is
226  still in (a,b,c) after mix().
227
228  If four pairs of (a,b,c) inputs are run through mix(), or through
229  mix() in reverse, there are at least 32 bits of the output that
230  are sometimes the same for one pair and different for another pair.
231  This was tested for:
232  * pairs that differed by one bit, by two bits, in any combination
233    of top bits of (a,b,c), or in any combination of bottom bits of
234    (a,b,c).
235  * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
236    the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
237    is commonly produced by subtraction) look like a single 1-bit
238    difference.
239  * the base values were pseudorandom, all zero but one bit set, or
240    all zero plus a counter that starts at zero.
241
242  Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
243  satisfy this are
244      4  6  8 16 19  4
245      9 15  3 18 27 15
246     14  9  3  7 17  3
247  Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
248  for "differ" defined as + with a one-bit base and a two-bit delta.  I
249  used http://burtleburtle.net/bob/hash/avalanche.html to choose
250  the operations, constants, and arrangements of the variables.
251
252  This does not achieve avalanche.  There are input bits of (a,b,c)
253  that fail to affect some output bits of (a,b,c), especially of a.  The
254  most thoroughly mixed value is c, but it doesn't really even achieve
255  avalanche in c.
256
257  This allows some parallelism.  Read-after-writes are good at doubling
258  the number of bits affected, so the goal of mixing pulls in the opposite
259  direction as the goal of parallelism.  I did what I could.  Rotates
260  seem to cost as much as shifts on every machine I could lay my hands
261  on, and rotates are much kinder to the top and bottom bits, so I used
262  rotates.
263  -------------------------------------------------------------------------------
264 */
265 #define mix(a,b,c) \
266 { \
267   a -= c;  a ^= rot(c, 4);  c += b; \
268   b -= a;  b ^= rot(a, 6);  a += c; \
269   c -= b;  c ^= rot(b, 8);  b += a; \
270   a -= c;  a ^= rot(c,16);  c += b; \
271   b -= a;  b ^= rot(a,19);  a += c; \
272   c -= b;  c ^= rot(b, 4);  b += a; \
273 }
274
275 /*
276  -------------------------------------------------------------------------------
277  final -- final mixing of 3 32-bit values (a,b,c) into c
278
279  Pairs of (a,b,c) values differing in only a few bits will usually
280  produce values of c that look totally different.  This was tested for
281  * pairs that differed by one bit, by two bits, in any combination
282    of top bits of (a,b,c), or in any combination of bottom bits of
283    (a,b,c).
284  * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
285    the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
286    is commonly produced by subtraction) look like a single 1-bit
287    difference.
288  * the base values were pseudorandom, all zero but one bit set, or
289    all zero plus a counter that starts at zero.
290
291  These constants passed:
292   14 11 25 16 4 14 24
293   12 14 25 16 4 14 24
294  and these came close:
295    4  8 15 26 3 22 24
296   10  8 15 26 3 22 24
297   11  8 15 26 3 22 24
298  -------------------------------------------------------------------------------
299 */
300 #define final(a,b,c) \
301 { \
302   c ^= b; c -= rot(b,14); \
303   a ^= c; a -= rot(c,11); \
304   b ^= a; b -= rot(a,25); \
305   c ^= b; c -= rot(b,16); \
306   a ^= c; a -= rot(c,4);  \
307   b ^= a; b -= rot(a,14); \
308   c ^= b; c -= rot(b,24); \
309 }
310
311
312 /*
313  -------------------------------------------------------------------------------
314  hashlittle() -- hash a variable-length key into a 32-bit value
315    k       : the key (the unaligned variable-length array of bytes)
316    length  : the length of the key, counting by bytes
317    val2    : IN: can be any 4-byte value OUT: second 32 bit hash.
318  Returns a 32-bit value.  Every bit of the key affects every bit of
319  the return value.  Two keys differing by one or two bits will have
320  totally different hash values.  Note that the return value is better
321  mixed than val2, so use that first.
322
323  The best hash table sizes are powers of 2.  There is no need to do
324  mod a prime (mod is sooo slow!).  If you need less than 32 bits,
325  use a bitmask.  For example, if you need only 10 bits, do
326    h = (h & hashmask(10));
327  In which case, the hash table should have hashsize(10) elements.
328
329  If you are hashing n strings (uint8_t **)k, do it like this:
330    for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
331
332  By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
333  code any way you wish, private, educational, or commercial.  It's free.
334
335  Use for hash table lookup, or anything where one collision in 2^^32 is
336  acceptable.  Do NOT use for cryptographic purposes.
337  -------------------------------------------------------------------------------
338 */
339
340 uint32_t hashlittle(const void *key, size_t length)
341 {
342   uint32_t a,b,c;                                          /* internal state */
343   union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */
344
345   /* Set up the internal state */
346   a = b = c = 0xdeadbeef + ((uint32_t)length);
347
348   u.ptr = key;
349   if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
350     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
351     const uint8_t  *k8;
352
353     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
354     while (length > 12)
355     {
356       a += k[0];
357       b += k[1];
358       c += k[2];
359       mix(a,b,c);
360       length -= 12;
361       k += 3;
362     }
363
364     /*----------------------------- handle the last (probably partial) block */
365     k8 = (const uint8_t *)k;
366     switch(length)
367     {
368     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
369     case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
370     case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
371     case 9 : c+=k8[8];                   /* fall through */
372     case 8 : b+=k[1]; a+=k[0]; break;
373     case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
374     case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
375     case 5 : b+=k8[4];                   /* fall through */
376     case 4 : a+=k[0]; break;
377     case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
378     case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
379     case 1 : a+=k8[0]; break;
380     case 0 : return c;
381     }
382   } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
383     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
384     const uint8_t  *k8;
385
386     /*--------------- all but last block: aligned reads and different mixing */
387     while (length > 12)
388     {
389       a += k[0] + (((uint32_t)k[1])<<16);
390       b += k[2] + (((uint32_t)k[3])<<16);
391       c += k[4] + (((uint32_t)k[5])<<16);
392       mix(a,b,c);
393       length -= 12;
394       k += 6;
395     }
396
397     /*----------------------------- handle the last (probably partial) block */
398     k8 = (const uint8_t *)k;
399     switch(length)
400     {
401     case 12: c+=k[4]+(((uint32_t)k[5])<<16);
402              b+=k[2]+(((uint32_t)k[3])<<16);
403              a+=k[0]+(((uint32_t)k[1])<<16);
404              break;
405     case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
406     case 10: c+=k[4];
407              b+=k[2]+(((uint32_t)k[3])<<16);
408              a+=k[0]+(((uint32_t)k[1])<<16);
409              break;
410     case 9 : c+=k8[8];                      /* fall through */
411     case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
412              a+=k[0]+(((uint32_t)k[1])<<16);
413              break;
414     case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
415     case 6 : b+=k[2];
416              a+=k[0]+(((uint32_t)k[1])<<16);
417              break;
418     case 5 : b+=k8[4];                      /* fall through */
419     case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
420              break;
421     case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
422     case 2 : a+=k[0];
423              break;
424     case 1 : a+=k8[0];
425              break;
426     case 0 : return c;                     /* zero length requires no mixing */
427     }
428
429   } else {                        /* need to read the key one byte at a time */
430     const uint8_t *k = (const uint8_t *)key;
431
432     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
433     while (length > 12)
434     {
435       a += k[0];
436       a += ((uint32_t)k[1])<<8;
437       a += ((uint32_t)k[2])<<16;
438       a += ((uint32_t)k[3])<<24;
439       b += k[4];
440       b += ((uint32_t)k[5])<<8;
441       b += ((uint32_t)k[6])<<16;
442       b += ((uint32_t)k[7])<<24;
443       c += k[8];
444       c += ((uint32_t)k[9])<<8;
445       c += ((uint32_t)k[10])<<16;
446       c += ((uint32_t)k[11])<<24;
447       mix(a,b,c);
448       length -= 12;
449       k += 12;
450     }
451
452     /*-------------------------------- last block: affect all 32 bits of (c) */
453     switch(length)                   /* all the case statements fall through */
454     {
455     case 12: c+=((uint32_t)k[11])<<24;
456              /* FALLTHROUGH */
457     case 11: c+=((uint32_t)k[10])<<16;
458              /* FALLTHROUGH */
459     case 10: c+=((uint32_t)k[9])<<8;
460              /* FALLTHROUGH */
461     case 9 : c+=k[8];
462              /* FALLTHROUGH */
463     case 8 : b+=((uint32_t)k[7])<<24;
464              /* FALLTHROUGH */
465     case 7 : b+=((uint32_t)k[6])<<16;
466              /* FALLTHROUGH */
467     case 6 : b+=((uint32_t)k[5])<<8;
468              /* FALLTHROUGH */
469     case 5 : b+=k[4];
470              /* FALLTHROUGH */
471     case 4 : a+=((uint32_t)k[3])<<24;
472              /* FALLTHROUGH */
473     case 3 : a+=((uint32_t)k[2])<<16;
474              /* FALLTHROUGH */
475     case 2 : a+=((uint32_t)k[1])<<8;
476              /* FALLTHROUGH */
477     case 1 : a+=k[0];
478              break;
479     case 0 : return c;
480     }
481   }
482
483   final(a,b,c);
484   return c;
485 }