xref: /openssl/crypto/lhash/lhash.c (revision b6461792)
1 /*
2  * Copyright 1995-2024 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the Apache License 2.0 (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9 
10 #include <stdio.h>
11 #include <string.h>
12 #include <stdlib.h>
13 #include <openssl/crypto.h>
14 #include <openssl/lhash.h>
15 #include <openssl/err.h>
16 #include "crypto/ctype.h"
17 #include "crypto/lhash.h"
18 #include "lhash_local.h"
19 
20 /*
21  * A hashing implementation that appears to be based on the linear hashing
22  * algorithm:
23  * https://en.wikipedia.org/wiki/Linear_hashing
24  *
25  * Litwin, Witold (1980), "Linear hashing: A new tool for file and table
26  * addressing", Proc. 6th Conference on Very Large Databases: 212-223
27  * https://hackthology.com/pdfs/Litwin-1980-Linear_Hashing.pdf
28  *
29  * From the Wikipedia article "Linear hashing is used in the BDB Berkeley
30  * database system, which in turn is used by many software systems such as
31  * OpenLDAP, using a C implementation derived from the CACM article and first
32  * published on the Usenet in 1988 by Esmond Pitt."
33  *
34  * The CACM paper is available here:
35  * https://pdfs.semanticscholar.org/ff4d/1c5deca6269cc316bfd952172284dbf610ee.pdf
36  */
37 
38 #undef MIN_NODES
39 #define MIN_NODES       16
40 #define UP_LOAD         (2*LH_LOAD_MULT) /* load times 256 (default 2) */
41 #define DOWN_LOAD       (LH_LOAD_MULT) /* load times 256 (default 1) */
42 
43 static int expand(OPENSSL_LHASH *lh);
44 static void contract(OPENSSL_LHASH *lh);
45 static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh, const void *data, unsigned long *rhash);
46 
OPENSSL_LH_set_thunks(OPENSSL_LHASH * lh,OPENSSL_LH_HASHFUNCTHUNK hw,OPENSSL_LH_COMPFUNCTHUNK cw,OPENSSL_LH_DOALL_FUNC_THUNK daw,OPENSSL_LH_DOALL_FUNCARG_THUNK daaw)47 OPENSSL_LHASH *OPENSSL_LH_set_thunks(OPENSSL_LHASH *lh,
48                                      OPENSSL_LH_HASHFUNCTHUNK hw,
49                                      OPENSSL_LH_COMPFUNCTHUNK cw,
50                                      OPENSSL_LH_DOALL_FUNC_THUNK daw,
51                                      OPENSSL_LH_DOALL_FUNCARG_THUNK daaw)
52 {
53 
54     if (lh == NULL)
55         return NULL;
56     lh->compw = cw;
57     lh->hashw = hw;
58     lh->daw = daw;
59     lh->daaw = daaw;
60     return lh;
61 }
62 
OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h,OPENSSL_LH_COMPFUNC c)63 OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c)
64 {
65     OPENSSL_LHASH *ret;
66 
67     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
68         return NULL;
69     if ((ret->b = OPENSSL_zalloc(sizeof(*ret->b) * MIN_NODES)) == NULL)
70         goto err;
71     ret->comp = ((c == NULL) ? (OPENSSL_LH_COMPFUNC)strcmp : c);
72     ret->hash = ((h == NULL) ? (OPENSSL_LH_HASHFUNC)OPENSSL_LH_strhash : h);
73     ret->num_nodes = MIN_NODES / 2;
74     ret->num_alloc_nodes = MIN_NODES;
75     ret->pmax = MIN_NODES / 2;
76     ret->up_load = UP_LOAD;
77     ret->down_load = DOWN_LOAD;
78     return ret;
79 
80 err:
81     OPENSSL_free(ret->b);
82     OPENSSL_free(ret);
83     return NULL;
84 }
85 
OPENSSL_LH_free(OPENSSL_LHASH * lh)86 void OPENSSL_LH_free(OPENSSL_LHASH *lh)
87 {
88     if (lh == NULL)
89         return;
90 
91     OPENSSL_LH_flush(lh);
92     OPENSSL_free(lh->b);
93     OPENSSL_free(lh);
94 }
95 
OPENSSL_LH_flush(OPENSSL_LHASH * lh)96 void OPENSSL_LH_flush(OPENSSL_LHASH *lh)
97 {
98     unsigned int i;
99     OPENSSL_LH_NODE *n, *nn;
100 
101     if (lh == NULL)
102         return;
103 
104     for (i = 0; i < lh->num_nodes; i++) {
105         n = lh->b[i];
106         while (n != NULL) {
107             nn = n->next;
108             OPENSSL_free(n);
109             n = nn;
110         }
111         lh->b[i] = NULL;
112     }
113 
114     lh->num_items = 0;
115 }
116 
OPENSSL_LH_insert(OPENSSL_LHASH * lh,void * data)117 void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data)
118 {
119     unsigned long hash;
120     OPENSSL_LH_NODE *nn, **rn;
121     void *ret;
122 
123     lh->error = 0;
124     if ((lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)) && !expand(lh))
125         return NULL;        /* 'lh->error++' already done in 'expand' */
126 
127     rn = getrn(lh, data, &hash);
128 
129     if (*rn == NULL) {
130         if ((nn = OPENSSL_malloc(sizeof(*nn))) == NULL) {
131             lh->error++;
132             return NULL;
133         }
134         nn->data = data;
135         nn->next = NULL;
136         nn->hash = hash;
137         *rn = nn;
138         ret = NULL;
139         lh->num_items++;
140     } else {                    /* replace same key */
141         ret = (*rn)->data;
142         (*rn)->data = data;
143     }
144     return ret;
145 }
146 
OPENSSL_LH_delete(OPENSSL_LHASH * lh,const void * data)147 void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data)
148 {
149     unsigned long hash;
150     OPENSSL_LH_NODE *nn, **rn;
151     void *ret;
152 
153     lh->error = 0;
154     rn = getrn(lh, data, &hash);
155 
156     if (*rn == NULL) {
157         return NULL;
158     } else {
159         nn = *rn;
160         *rn = nn->next;
161         ret = nn->data;
162         OPENSSL_free(nn);
163     }
164 
165     lh->num_items--;
166     if ((lh->num_nodes > MIN_NODES) &&
167         (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)))
168         contract(lh);
169 
170     return ret;
171 }
172 
OPENSSL_LH_retrieve(OPENSSL_LHASH * lh,const void * data)173 void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data)
174 {
175     unsigned long hash;
176     OPENSSL_LH_NODE **rn;
177 
178     if (lh->error != 0)
179         lh->error = 0;
180 
181     rn = getrn(lh, data, &hash);
182 
183     return *rn == NULL ? NULL : (*rn)->data;
184 }
185 
doall_util_fn(OPENSSL_LHASH * lh,int use_arg,OPENSSL_LH_DOALL_FUNC_THUNK wfunc,OPENSSL_LH_DOALL_FUNC func,OPENSSL_LH_DOALL_FUNCARG func_arg,OPENSSL_LH_DOALL_FUNCARG_THUNK wfunc_arg,void * arg)186 static void doall_util_fn(OPENSSL_LHASH *lh, int use_arg,
187                           OPENSSL_LH_DOALL_FUNC_THUNK wfunc,
188                           OPENSSL_LH_DOALL_FUNC func,
189                           OPENSSL_LH_DOALL_FUNCARG func_arg,
190                           OPENSSL_LH_DOALL_FUNCARG_THUNK wfunc_arg,
191                           void *arg)
192 {
193     int i;
194     OPENSSL_LH_NODE *a, *n;
195 
196     if (lh == NULL)
197         return;
198 
199     /*
200      * reverse the order so we search from 'top to bottom' We were having
201      * memory leaks otherwise
202      */
203     for (i = lh->num_nodes - 1; i >= 0; i--) {
204         a = lh->b[i];
205         while (a != NULL) {
206             n = a->next;
207             if (use_arg)
208                 wfunc_arg(a->data, arg, func_arg);
209             else
210                 wfunc(a->data, func);
211             a = n;
212         }
213     }
214 }
215 
OPENSSL_LH_doall(OPENSSL_LHASH * lh,OPENSSL_LH_DOALL_FUNC func)216 void OPENSSL_LH_doall(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNC func)
217 {
218     if (lh == NULL)
219         return;
220 
221     doall_util_fn(lh, 0, lh->daw, func, (OPENSSL_LH_DOALL_FUNCARG)NULL,
222                   (OPENSSL_LH_DOALL_FUNCARG_THUNK)NULL, NULL);
223 }
224 
OPENSSL_LH_doall_arg(OPENSSL_LHASH * lh,OPENSSL_LH_DOALL_FUNCARG func,void * arg)225 void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh,
226                           OPENSSL_LH_DOALL_FUNCARG func, void *arg)
227 {
228     if (lh == NULL)
229         return;
230 
231     doall_util_fn(lh, 1, (OPENSSL_LH_DOALL_FUNC_THUNK)NULL,
232                   (OPENSSL_LH_DOALL_FUNC)NULL, func, lh->daaw, arg);
233 }
234 
OPENSSL_LH_doall_arg_thunk(OPENSSL_LHASH * lh,OPENSSL_LH_DOALL_FUNCARG_THUNK daaw,OPENSSL_LH_DOALL_FUNCARG fn,void * arg)235 void OPENSSL_LH_doall_arg_thunk(OPENSSL_LHASH *lh,
236                                 OPENSSL_LH_DOALL_FUNCARG_THUNK daaw,
237                                 OPENSSL_LH_DOALL_FUNCARG fn, void *arg)
238 {
239     doall_util_fn(lh, 1, (OPENSSL_LH_DOALL_FUNC_THUNK)NULL,
240                   (OPENSSL_LH_DOALL_FUNC)NULL, fn, daaw, arg);
241 }
242 
expand(OPENSSL_LHASH * lh)243 static int expand(OPENSSL_LHASH *lh)
244 {
245     OPENSSL_LH_NODE **n, **n1, **n2, *np;
246     unsigned int p, pmax, nni, j;
247     unsigned long hash;
248 
249     nni = lh->num_alloc_nodes;
250     p = lh->p;
251     pmax = lh->pmax;
252     if (p + 1 >= pmax) {
253         j = nni * 2;
254         n = OPENSSL_realloc(lh->b, sizeof(OPENSSL_LH_NODE *) * j);
255         if (n == NULL) {
256             lh->error++;
257             return 0;
258         }
259         lh->b = n;
260         memset(n + nni, 0, sizeof(*n) * (j - nni));
261         lh->pmax = nni;
262         lh->num_alloc_nodes = j;
263         lh->p = 0;
264     } else {
265         lh->p++;
266     }
267 
268     lh->num_nodes++;
269     n1 = &(lh->b[p]);
270     n2 = &(lh->b[p + pmax]);
271     *n2 = NULL;
272 
273     for (np = *n1; np != NULL;) {
274         hash = np->hash;
275         if ((hash % nni) != p) { /* move it */
276             *n1 = (*n1)->next;
277             np->next = *n2;
278             *n2 = np;
279         } else
280             n1 = &((*n1)->next);
281         np = *n1;
282     }
283 
284     return 1;
285 }
286 
contract(OPENSSL_LHASH * lh)287 static void contract(OPENSSL_LHASH *lh)
288 {
289     OPENSSL_LH_NODE **n, *n1, *np;
290 
291     np = lh->b[lh->p + lh->pmax - 1];
292     lh->b[lh->p + lh->pmax - 1] = NULL; /* 24/07-92 - eay - weird but :-( */
293     if (lh->p == 0) {
294         n = OPENSSL_realloc(lh->b,
295                             (unsigned int)(sizeof(OPENSSL_LH_NODE *) * lh->pmax));
296         if (n == NULL) {
297             /* fputs("realloc error in lhash", stderr); */
298             lh->error++;
299         } else {
300             lh->b = n;
301         }
302         lh->num_alloc_nodes /= 2;
303         lh->pmax /= 2;
304         lh->p = lh->pmax - 1;
305     } else
306         lh->p--;
307 
308     lh->num_nodes--;
309 
310     n1 = lh->b[(int)lh->p];
311     if (n1 == NULL)
312         lh->b[(int)lh->p] = np;
313     else {
314         while (n1->next != NULL)
315             n1 = n1->next;
316         n1->next = np;
317     }
318 }
319 
getrn(OPENSSL_LHASH * lh,const void * data,unsigned long * rhash)320 static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh,
321                                const void *data, unsigned long *rhash)
322 {
323     OPENSSL_LH_NODE **ret, *n1;
324     unsigned long hash, nn;
325 
326     if (lh->hashw != NULL)
327         hash = lh->hashw(data, lh->hash);
328     else
329         hash = lh->hash(data);
330 
331     *rhash = hash;
332 
333     nn = hash % lh->pmax;
334     if (nn < lh->p)
335         nn = hash % lh->num_alloc_nodes;
336 
337     ret = &(lh->b[(int)nn]);
338     for (n1 = *ret; n1 != NULL; n1 = n1->next) {
339         if (n1->hash != hash) {
340             ret = &(n1->next);
341             continue;
342         }
343 
344         if (lh->compw != NULL) {
345             if (lh->compw(n1->data, data, lh->comp) == 0)
346                 break;
347         } else {
348             if (lh->comp(n1->data, data) == 0)
349                 break;
350         }
351         ret = &(n1->next);
352     }
353     return ret;
354 }
355 
356 /*
357  * The following hash seems to work very well on normal text strings no
358  * collisions on /usr/dict/words and it distributes on %2^n quite well, not
359  * as good as MD5, but still good.
360  */
OPENSSL_LH_strhash(const char * c)361 unsigned long OPENSSL_LH_strhash(const char *c)
362 {
363     unsigned long ret = 0;
364     long n;
365     unsigned long v;
366     int r;
367 
368     if ((c == NULL) || (*c == '\0'))
369         return ret;
370 
371     n = 0x100;
372     while (*c) {
373         v = n | (*c);
374         n += 0x100;
375         r = (int)((v >> 2) ^ v) & 0x0f;
376         /* cast to uint64_t to avoid 32 bit shift of 32 bit value */
377         ret = (ret << r) | (unsigned long)((uint64_t)ret >> (32 - r));
378         ret &= 0xFFFFFFFFL;
379         ret ^= v * v;
380         c++;
381     }
382     return (ret >> 16) ^ ret;
383 }
384 
385 /*
386  * Case insensitive string hashing.
387  *
388  * The lower/upper case bit is masked out (forcing all letters to be capitals).
389  * The major side effect on non-alpha characters is mapping the symbols and
390  * digits into the control character range (which should be harmless).
391  * The duplication (with respect to the hash value) of printable characters
392  * are that '`', '{', '|', '}' and '~' map to '@', '[', '\', ']' and '^'
393  * respectively (which seems tolerable).
394  *
395  * For EBCDIC, the alpha mapping is to lower case, most symbols go to control
396  * characters.  The only duplication is '0' mapping to '^', which is better
397  * than for ASCII.
398  */
ossl_lh_strcasehash(const char * c)399 unsigned long ossl_lh_strcasehash(const char *c)
400 {
401     unsigned long ret = 0;
402     long n;
403     unsigned long v;
404     int r;
405 #if defined(CHARSET_EBCDIC) && !defined(CHARSET_EBCDIC_TEST)
406     const long int case_adjust = ~0x40;
407 #else
408     const long int case_adjust = ~0x20;
409 #endif
410 
411     if (c == NULL || *c == '\0')
412         return ret;
413 
414     for (n = 0x100; *c != '\0'; n += 0x100) {
415         v = n | (case_adjust & *c);
416         r = (int)((v >> 2) ^ v) & 0x0f;
417         /* cast to uint64_t to avoid 32 bit shift of 32 bit value */
418         ret = (ret << r) | (unsigned long)((uint64_t)ret >> (32 - r));
419         ret &= 0xFFFFFFFFL;
420         ret ^= v * v;
421         c++;
422     }
423     return (ret >> 16) ^ ret;
424 }
425 
OPENSSL_LH_num_items(const OPENSSL_LHASH * lh)426 unsigned long OPENSSL_LH_num_items(const OPENSSL_LHASH *lh)
427 {
428     return lh ? lh->num_items : 0;
429 }
430 
OPENSSL_LH_get_down_load(const OPENSSL_LHASH * lh)431 unsigned long OPENSSL_LH_get_down_load(const OPENSSL_LHASH *lh)
432 {
433     return lh->down_load;
434 }
435 
OPENSSL_LH_set_down_load(OPENSSL_LHASH * lh,unsigned long down_load)436 void OPENSSL_LH_set_down_load(OPENSSL_LHASH *lh, unsigned long down_load)
437 {
438     lh->down_load = down_load;
439 }
440 
OPENSSL_LH_error(OPENSSL_LHASH * lh)441 int OPENSSL_LH_error(OPENSSL_LHASH *lh)
442 {
443     return lh->error;
444 }
445