]>
Commit | Line | Data |
---|---|---|
b1322259 | 1 | /* |
b6461792 | 2 | * Copyright 1995-2024 The OpenSSL Project Authors. All Rights Reserved. |
d02b48c6 | 3 | * |
8573be06 | 4 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
b1322259 RS |
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 | |
d02b48c6 RE |
8 | */ |
9 | ||
d02b48c6 RE |
10 | #include <stdio.h> |
11 | #include <string.h> | |
12 | #include <stdlib.h> | |
ec577822 BM |
13 | #include <openssl/crypto.h> |
14 | #include <openssl/lhash.h> | |
fe1128dc | 15 | #include <openssl/err.h> |
25f2138b DMSP |
16 | #include "crypto/ctype.h" |
17 | #include "crypto/lhash.h" | |
706457b7 | 18 | #include "lhash_local.h" |
739a1eb1 | 19 | |
4ce8bebc MC |
20 | /* |
21 | * A hashing implementation that appears to be based on the linear hashing | |
c2969ff6 | 22 | * algorithm: |
4ce8bebc MC |
23 | * https://en.wikipedia.org/wiki/Linear_hashing |
24 | * | |
25 | * Litwin, Witold (1980), "Linear hashing: A new tool for file and table | |
b4d0fa49 | 26 | * addressing", Proc. 6th Conference on Very Large Databases: 212-223 |
c2969ff6 | 27 | * https://hackthology.com/pdfs/Litwin-1980-Linear_Hashing.pdf |
4ce8bebc | 28 | * |
c2969ff6 | 29 | * From the Wikipedia article "Linear hashing is used in the BDB Berkeley |
4ce8bebc MC |
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 | */ | |
d02b48c6 | 37 | |
0f113f3e MC |
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) */ | |
d02b48c6 | 42 | |
0a1d3a81 | 43 | static int expand(OPENSSL_LHASH *lh); |
739a1eb1 RS |
44 | static void contract(OPENSSL_LHASH *lh); |
45 | static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh, const void *data, unsigned long *rhash); | |
d02b48c6 | 46 | |
5c42ced0 NH |
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 | ||
739a1eb1 | 63 | OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c) |
0f113f3e | 64 | { |
739a1eb1 | 65 | OPENSSL_LHASH *ret; |
0f113f3e | 66 | |
e077455e | 67 | if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) |
be606c01 | 68 | return NULL; |
64b25758 | 69 | if ((ret->b = OPENSSL_zalloc(sizeof(*ret->b) * MIN_NODES)) == NULL) |
be606c01 | 70 | goto err; |
739a1eb1 RS |
71 | ret->comp = ((c == NULL) ? (OPENSSL_LH_COMPFUNC)strcmp : c); |
72 | ret->hash = ((h == NULL) ? (OPENSSL_LH_HASHFUNC)OPENSSL_LH_strhash : h); | |
0f113f3e MC |
73 | ret->num_nodes = MIN_NODES / 2; |
74 | ret->num_alloc_nodes = MIN_NODES; | |
0f113f3e MC |
75 | ret->pmax = MIN_NODES / 2; |
76 | ret->up_load = UP_LOAD; | |
77 | ret->down_load = DOWN_LOAD; | |
2e8b5d75 | 78 | return ret; |
64b25758 | 79 | |
be606c01 RS |
80 | err: |
81 | OPENSSL_free(ret->b); | |
0f113f3e | 82 | OPENSSL_free(ret); |
be606c01 | 83 | return NULL; |
0f113f3e | 84 | } |
d02b48c6 | 85 | |
739a1eb1 | 86 | void OPENSSL_LH_free(OPENSSL_LHASH *lh) |
1bdbdaff P |
87 | { |
88 | if (lh == NULL) | |
89 | return; | |
90 | ||
91 | OPENSSL_LH_flush(lh); | |
92 | OPENSSL_free(lh->b); | |
93 | OPENSSL_free(lh); | |
94 | } | |
95 | ||
96 | void OPENSSL_LH_flush(OPENSSL_LHASH *lh) | |
0f113f3e MC |
97 | { |
98 | unsigned int i; | |
739a1eb1 | 99 | OPENSSL_LH_NODE *n, *nn; |
0f113f3e MC |
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 | } | |
bcb5d421 | 111 | lh->b[i] = NULL; |
0f113f3e | 112 | } |
e5da6818 HL |
113 | |
114 | lh->num_items = 0; | |
0f113f3e | 115 | } |
d02b48c6 | 116 | |
739a1eb1 | 117 | void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data) |
0f113f3e MC |
118 | { |
119 | unsigned long hash; | |
739a1eb1 | 120 | OPENSSL_LH_NODE *nn, **rn; |
0f113f3e | 121 | void *ret; |
152d2646 | 122 | |
0f113f3e | 123 | lh->error = 0; |
152d2646 | 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 | ||
0f113f3e MC |
127 | rn = getrn(lh, data, &hash); |
128 | ||
129 | if (*rn == NULL) { | |
b4faea50 | 130 | if ((nn = OPENSSL_malloc(sizeof(*nn))) == NULL) { |
0f113f3e | 131 | lh->error++; |
2e8b5d75 | 132 | return NULL; |
0f113f3e MC |
133 | } |
134 | nn->data = data; | |
135 | nn->next = NULL; | |
0f113f3e | 136 | nn->hash = hash; |
0f113f3e MC |
137 | *rn = nn; |
138 | ret = NULL; | |
0f113f3e MC |
139 | lh->num_items++; |
140 | } else { /* replace same key */ | |
0f113f3e MC |
141 | ret = (*rn)->data; |
142 | (*rn)->data = data; | |
0f113f3e | 143 | } |
2e8b5d75 | 144 | return ret; |
0f113f3e | 145 | } |
d02b48c6 | 146 | |
739a1eb1 | 147 | void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data) |
0f113f3e MC |
148 | { |
149 | unsigned long hash; | |
739a1eb1 | 150 | OPENSSL_LH_NODE *nn, **rn; |
0f113f3e MC |
151 | void *ret; |
152 | ||
153 | lh->error = 0; | |
154 | rn = getrn(lh, data, &hash); | |
155 | ||
156 | if (*rn == NULL) { | |
2e8b5d75 | 157 | return NULL; |
0f113f3e MC |
158 | } else { |
159 | nn = *rn; | |
160 | *rn = nn->next; | |
161 | ret = nn->data; | |
162 | OPENSSL_free(nn); | |
0f113f3e MC |
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 | ||
2e8b5d75 | 170 | return ret; |
0f113f3e | 171 | } |
d02b48c6 | 172 | |
739a1eb1 | 173 | void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data) |
0f113f3e MC |
174 | { |
175 | unsigned long hash; | |
739a1eb1 | 176 | OPENSSL_LH_NODE **rn; |
0f113f3e | 177 | |
77d7b6ee HL |
178 | if (lh->error != 0) |
179 | lh->error = 0; | |
cab76c0f | 180 | |
0f113f3e MC |
181 | rn = getrn(lh, data, &hash); |
182 | ||
43f13277 | 183 | return *rn == NULL ? NULL : (*rn)->data; |
0f113f3e | 184 | } |
d02b48c6 | 185 | |
739a1eb1 | 186 | static void doall_util_fn(OPENSSL_LHASH *lh, int use_arg, |
5c42ced0 | 187 | OPENSSL_LH_DOALL_FUNC_THUNK wfunc, |
739a1eb1 | 188 | OPENSSL_LH_DOALL_FUNC func, |
5c42ced0 NH |
189 | OPENSSL_LH_DOALL_FUNCARG func_arg, |
190 | OPENSSL_LH_DOALL_FUNCARG_THUNK wfunc_arg, | |
191 | void *arg) | |
0f113f3e MC |
192 | { |
193 | int i; | |
739a1eb1 | 194 | OPENSSL_LH_NODE *a, *n; |
0f113f3e MC |
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) { | |
0f113f3e MC |
206 | n = a->next; |
207 | if (use_arg) | |
5c42ced0 | 208 | wfunc_arg(a->data, arg, func_arg); |
0f113f3e | 209 | else |
5c42ced0 | 210 | wfunc(a->data, func); |
0f113f3e MC |
211 | a = n; |
212 | } | |
213 | } | |
214 | } | |
d02b48c6 | 215 | |
739a1eb1 | 216 | void OPENSSL_LH_doall(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNC func) |
0f113f3e | 217 | { |
5c42ced0 NH |
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); | |
0f113f3e | 223 | } |
18602745 | 224 | |
5c42ced0 NH |
225 | void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh, |
226 | OPENSSL_LH_DOALL_FUNCARG func, void *arg) | |
0f113f3e | 227 | { |
5c42ced0 NH |
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 | ||
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); | |
0f113f3e | 241 | } |
18602745 | 242 | |
0a1d3a81 | 243 | static int expand(OPENSSL_LHASH *lh) |
0f113f3e | 244 | { |
739a1eb1 | 245 | OPENSSL_LH_NODE **n, **n1, **n2, *np; |
4ce8bebc MC |
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; | |
4ce8bebc MC |
263 | lh->p = 0; |
264 | } else { | |
265 | lh->p++; | |
266 | } | |
0f113f3e MC |
267 | |
268 | lh->num_nodes++; | |
0f113f3e | 269 | n1 = &(lh->b[p]); |
4ce8bebc | 270 | n2 = &(lh->b[p + pmax]); |
739a1eb1 | 271 | *n2 = NULL; |
0f113f3e MC |
272 | |
273 | for (np = *n1; np != NULL;) { | |
0f113f3e | 274 | hash = np->hash; |
0f113f3e MC |
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 | ||
152d2646 | 284 | return 1; |
0f113f3e | 285 | } |
d02b48c6 | 286 | |
739a1eb1 | 287 | static void contract(OPENSSL_LHASH *lh) |
0f113f3e | 288 | { |
739a1eb1 | 289 | OPENSSL_LH_NODE **n, *n1, *np; |
0f113f3e MC |
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) { | |
b196e7d9 | 294 | n = OPENSSL_realloc(lh->b, |
739a1eb1 | 295 | (unsigned int)(sizeof(OPENSSL_LH_NODE *) * lh->pmax)); |
0f113f3e | 296 | if (n == NULL) { |
1287dabd | 297 | /* fputs("realloc error in lhash", stderr); */ |
0f113f3e | 298 | lh->error++; |
5fbfd641 BE |
299 | } else { |
300 | lh->b = n; | |
0f113f3e | 301 | } |
0f113f3e MC |
302 | lh->num_alloc_nodes /= 2; |
303 | lh->pmax /= 2; | |
304 | lh->p = lh->pmax - 1; | |
0f113f3e MC |
305 | } else |
306 | lh->p--; | |
307 | ||
308 | lh->num_nodes--; | |
0f113f3e MC |
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 | } | |
d02b48c6 | 319 | |
739a1eb1 RS |
320 | static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh, |
321 | const void *data, unsigned long *rhash) | |
0f113f3e | 322 | { |
739a1eb1 | 323 | OPENSSL_LH_NODE **ret, *n1; |
0f113f3e | 324 | unsigned long hash, nn; |
0f113f3e | 325 | |
5c42ced0 NH |
326 | if (lh->hashw != NULL) |
327 | hash = lh->hashw(data, lh->hash); | |
328 | else | |
329 | hash = lh->hash(data); | |
330 | ||
0f113f3e MC |
331 | *rhash = hash; |
332 | ||
333 | nn = hash % lh->pmax; | |
334 | if (nn < lh->p) | |
335 | nn = hash % lh->num_alloc_nodes; | |
336 | ||
0f113f3e MC |
337 | ret = &(lh->b[(int)nn]); |
338 | for (n1 = *ret; n1 != NULL; n1 = n1->next) { | |
0f113f3e MC |
339 | if (n1->hash != hash) { |
340 | ret = &(n1->next); | |
341 | continue; | |
342 | } | |
5c42ced0 NH |
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 | } | |
0f113f3e MC |
351 | ret = &(n1->next); |
352 | } | |
2e8b5d75 | 353 | return ret; |
0f113f3e MC |
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. | |
d02b48c6 | 360 | */ |
739a1eb1 | 361 | unsigned long OPENSSL_LH_strhash(const char *c) |
0f113f3e MC |
362 | { |
363 | unsigned long ret = 0; | |
364 | long n; | |
365 | unsigned long v; | |
366 | int r; | |
367 | ||
368 | if ((c == NULL) || (*c == '\0')) | |
2e8b5d75 | 369 | return ret; |
d02b48c6 | 370 | |
0f113f3e MC |
371 | n = 0x100; |
372 | while (*c) { | |
373 | v = n | (*c); | |
374 | n += 0x100; | |
375 | r = (int)((v >> 2) ^ v) & 0x0f; | |
2ce0a3d1 TM |
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)); | |
0f113f3e MC |
378 | ret &= 0xFFFFFFFFL; |
379 | ret ^= v * v; | |
380 | c++; | |
381 | } | |
2e8b5d75 | 382 | return (ret >> 16) ^ ret; |
0f113f3e | 383 | } |
d02b48c6 | 384 | |
a4e21d18 P |
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 | */ | |
285aa80e | 399 | unsigned long ossl_lh_strcasehash(const char *c) |
fc196a5e P |
400 | { |
401 | unsigned long ret = 0; | |
402 | long n; | |
403 | unsigned long v; | |
404 | int r; | |
a4e21d18 P |
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 | |
fc196a5e P |
410 | |
411 | if (c == NULL || *c == '\0') | |
412 | return ret; | |
413 | ||
414 | for (n = 0x100; *c != '\0'; n += 0x100) { | |
a4e21d18 | 415 | v = n | (case_adjust & *c); |
fc196a5e | 416 | r = (int)((v >> 2) ^ v) & 0x0f; |
2ce0a3d1 TM |
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)); | |
fc196a5e P |
419 | ret &= 0xFFFFFFFFL; |
420 | ret ^= v * v; | |
421 | c++; | |
422 | } | |
423 | return (ret >> 16) ^ ret; | |
424 | } | |
425 | ||
739a1eb1 | 426 | unsigned long OPENSSL_LH_num_items(const OPENSSL_LHASH *lh) |
0f113f3e MC |
427 | { |
428 | return lh ? lh->num_items : 0; | |
429 | } | |
e6b5c341 | 430 | |
739a1eb1 | 431 | unsigned long OPENSSL_LH_get_down_load(const OPENSSL_LHASH *lh) |
e6b5c341 DSH |
432 | { |
433 | return lh->down_load; | |
434 | } | |
435 | ||
739a1eb1 | 436 | void OPENSSL_LH_set_down_load(OPENSSL_LHASH *lh, unsigned long down_load) |
e6b5c341 DSH |
437 | { |
438 | lh->down_load = down_load; | |
439 | } | |
440 | ||
739a1eb1 | 441 | int OPENSSL_LH_error(OPENSSL_LHASH *lh) |
e6b5c341 DSH |
442 | { |
443 | return lh->error; | |
444 | } |