Coverage Report

Created: 2026-11-16 07:12

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/openssl/crypto/lhash/lhash.c
Line
Count
Source
1
/*
2
 * Copyright 1995-2025 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
288
#define MIN_NODES 16
40
96
#define UP_LOAD (2 * LH_LOAD_MULT) /* load times 256 (default 2) */
41
96
#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
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
96
{
53
54
96
    if (lh == NULL)
55
0
        return NULL;
56
96
    lh->compw = cw;
57
96
    lh->hashw = hw;
58
96
    lh->daw = daw;
59
96
    lh->daaw = daaw;
60
96
    return lh;
61
96
}
62
63
OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c)
64
96
{
65
96
    OPENSSL_LHASH *ret;
66
67
96
    if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
68
0
        return NULL;
69
96
    if ((ret->b = OPENSSL_calloc(MIN_NODES, sizeof(*ret->b))) == NULL)
70
0
        goto err;
71
96
    ret->comp = ((c == NULL) ? (OPENSSL_LH_COMPFUNC)strcmp : c);
72
96
    ret->hash = ((h == NULL) ? (OPENSSL_LH_HASHFUNC)OPENSSL_LH_strhash : h);
73
96
    ret->num_nodes = MIN_NODES / 2;
74
96
    ret->num_alloc_nodes = MIN_NODES;
75
96
    ret->pmax = MIN_NODES / 2;
76
96
    ret->up_load = UP_LOAD;
77
96
    ret->down_load = DOWN_LOAD;
78
96
    return ret;
79
80
0
err:
81
0
    OPENSSL_free(ret->b);
82
0
    OPENSSL_free(ret);
83
0
    return NULL;
84
96
}
85
86
void OPENSSL_LH_free(OPENSSL_LHASH *lh)
87
0
{
88
0
    if (lh == NULL)
89
0
        return;
90
91
0
    OPENSSL_LH_flush(lh);
92
0
    OPENSSL_free(lh->b);
93
0
    OPENSSL_free(lh);
94
0
}
95
96
void OPENSSL_LH_flush(OPENSSL_LHASH *lh)
97
0
{
98
0
    unsigned int i;
99
0
    OPENSSL_LH_NODE *n, *nn;
100
101
0
    if (lh == NULL)
102
0
        return;
103
104
0
    for (i = 0; i < lh->num_nodes; i++) {
105
0
        n = lh->b[i];
106
0
        while (n != NULL) {
107
0
            nn = n->next;
108
0
            OPENSSL_free(n);
109
0
            n = nn;
110
0
        }
111
0
        lh->b[i] = NULL;
112
0
    }
113
114
0
    lh->num_items = 0;
115
0
}
116
117
void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data)
118
83.1k
{
119
83.1k
    unsigned long hash;
120
83.1k
    OPENSSL_LH_NODE *nn, **rn;
121
83.1k
    void *ret;
122
123
83.1k
    lh->error = 0;
124
83.1k
    if ((lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)) && !expand(lh))
125
0
        return NULL; /* 'lh->error++' already done in 'expand' */
126
127
83.1k
    rn = getrn(lh, data, &hash);
128
129
83.1k
    if (*rn == NULL) {
130
34.2k
        if ((nn = OPENSSL_malloc(sizeof(*nn))) == NULL) {
131
0
            lh->error++;
132
0
            return NULL;
133
0
        }
134
34.2k
        nn->data = data;
135
34.2k
        nn->next = NULL;
136
34.2k
        nn->hash = hash;
137
34.2k
        *rn = nn;
138
34.2k
        ret = NULL;
139
34.2k
        lh->num_items++;
140
48.8k
    } else { /* replace same key */
141
48.8k
        ret = (*rn)->data;
142
48.8k
        (*rn)->data = data;
143
48.8k
    }
144
83.1k
    return ret;
145
83.1k
}
146
147
void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data)
148
0
{
149
0
    unsigned long hash;
150
0
    OPENSSL_LH_NODE *nn, **rn;
151
0
    void *ret;
152
153
0
    lh->error = 0;
154
0
    rn = getrn(lh, data, &hash);
155
156
0
    if (*rn == NULL) {
157
0
        return NULL;
158
0
    } else {
159
0
        nn = *rn;
160
0
        *rn = nn->next;
161
0
        ret = nn->data;
162
0
        OPENSSL_free(nn);
163
0
    }
164
165
0
    lh->num_items--;
166
0
    if ((lh->num_nodes > MIN_NODES) && (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)))
167
0
        contract(lh);
168
169
0
    return ret;
170
0
}
171
172
void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data)
173
122k
{
174
122k
    unsigned long hash;
175
122k
    OPENSSL_LH_NODE **rn;
176
177
122k
    if (lh->error != 0)
178
0
        lh->error = 0;
179
180
122k
    rn = getrn(lh, data, &hash);
181
182
122k
    return *rn == NULL ? NULL : (*rn)->data;
183
122k
}
184
185
static void doall_util_fn(OPENSSL_LHASH *lh, int use_arg,
186
    OPENSSL_LH_DOALL_FUNC_THUNK wfunc,
187
    OPENSSL_LH_DOALL_FUNC func,
188
    OPENSSL_LH_DOALL_FUNCARG func_arg,
189
    OPENSSL_LH_DOALL_FUNCARG_THUNK wfunc_arg,
190
    void *arg)
191
32
{
192
32
    int i;
193
32
    OPENSSL_LH_NODE *a, *n;
194
195
32
    if (lh == NULL)
196
0
        return;
197
198
    /*
199
     * reverse the order so we search from 'top to bottom' We were having
200
     * memory leaks otherwise
201
     */
202
3.93k
    for (i = lh->num_nodes - 1; i >= 0; i--) {
203
3.90k
        a = lh->b[i];
204
11.6k
        while (a != NULL) {
205
7.74k
            n = a->next;
206
            /*
207
             * Tables created with OPENSSL_LH_new() have no thunks, so fall
208
             * back to calling the caller supplied function directly, as
209
             * getrn() does for the hash and compare functions.
210
             */
211
7.74k
            if (use_arg) {
212
7.74k
                if (wfunc_arg != NULL)
213
7.74k
                    wfunc_arg(a->data, arg, func_arg);
214
0
                else
215
0
                    func_arg(a->data, arg);
216
7.74k
            } else {
217
0
                if (wfunc != NULL)
218
0
                    wfunc(a->data, func);
219
0
                else
220
0
                    func(a->data);
221
0
            }
222
7.74k
            a = n;
223
7.74k
        }
224
3.90k
    }
225
32
}
226
227
void OPENSSL_LH_doall(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNC func)
228
0
{
229
0
    if (lh == NULL)
230
0
        return;
231
232
0
    doall_util_fn(lh, 0, lh->daw, func, (OPENSSL_LH_DOALL_FUNCARG)NULL,
233
0
        (OPENSSL_LH_DOALL_FUNCARG_THUNK)NULL, NULL);
234
0
}
235
236
void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh,
237
    OPENSSL_LH_DOALL_FUNCARG func, void *arg)
238
0
{
239
0
    if (lh == NULL)
240
0
        return;
241
242
0
    doall_util_fn(lh, 1, (OPENSSL_LH_DOALL_FUNC_THUNK)NULL,
243
0
        (OPENSSL_LH_DOALL_FUNC)NULL, func, lh->daaw, arg);
244
0
}
245
246
void OPENSSL_LH_doall_arg_thunk(OPENSSL_LHASH *lh,
247
    OPENSSL_LH_DOALL_FUNCARG_THUNK daaw,
248
    OPENSSL_LH_DOALL_FUNCARG fn, void *arg)
249
32
{
250
32
    doall_util_fn(lh, 1, (OPENSSL_LH_DOALL_FUNC_THUNK)NULL,
251
32
        (OPENSSL_LH_DOALL_FUNC)NULL, fn, daaw, arg);
252
32
}
253
254
static int expand(OPENSSL_LHASH *lh)
255
16.8k
{
256
16.8k
    OPENSSL_LH_NODE **n, **n1, **n2, *np;
257
16.8k
    unsigned int p, pmax, nni, j;
258
16.8k
    unsigned long hash;
259
260
16.8k
    nni = lh->num_alloc_nodes;
261
16.8k
    p = lh->p;
262
16.8k
    pmax = lh->pmax;
263
16.8k
    if (p + 1 >= pmax) {
264
144
        j = nni * 2;
265
144
        n = OPENSSL_realloc_array(lh->b, j, sizeof(OPENSSL_LH_NODE *));
266
144
        if (n == NULL) {
267
0
            lh->error++;
268
0
            return 0;
269
0
        }
270
144
        lh->b = n;
271
144
        memset(n + nni, 0, sizeof(*n) * (j - nni));
272
144
        lh->pmax = nni;
273
144
        lh->num_alloc_nodes = j;
274
144
        lh->p = 0;
275
16.6k
    } else {
276
16.6k
        lh->p++;
277
16.6k
    }
278
279
16.8k
    lh->num_nodes++;
280
16.8k
    n1 = &(lh->b[p]);
281
16.8k
    n2 = &(lh->b[p + pmax]);
282
16.8k
    *n2 = NULL;
283
284
68.0k
    for (np = *n1; np != NULL;) {
285
51.1k
        hash = np->hash;
286
51.1k
        if ((hash % nni) != p) { /* move it */
287
8.84k
            *n1 = (*n1)->next;
288
8.84k
            np->next = *n2;
289
8.84k
            *n2 = np;
290
8.84k
        } else
291
42.3k
            n1 = &((*n1)->next);
292
51.1k
        np = *n1;
293
51.1k
    }
294
295
16.8k
    return 1;
296
16.8k
}
297
298
static void contract(OPENSSL_LHASH *lh)
299
0
{
300
0
    OPENSSL_LH_NODE **n, *n1, *np;
301
302
0
    np = lh->b[lh->p + lh->pmax - 1];
303
0
    lh->b[lh->p + lh->pmax - 1] = NULL; /* 24/07-92 - eay - weird but :-( */
304
0
    if (lh->p == 0) {
305
0
        n = OPENSSL_realloc_array(lh->b, lh->pmax, sizeof(OPENSSL_LH_NODE *));
306
0
        if (n == NULL) {
307
            /* fputs("realloc error in lhash", stderr); */
308
0
            lh->error++;
309
0
        } else {
310
0
            lh->b = n;
311
0
        }
312
0
        lh->num_alloc_nodes /= 2;
313
0
        lh->pmax /= 2;
314
0
        lh->p = lh->pmax - 1;
315
0
    } else
316
0
        lh->p--;
317
318
0
    lh->num_nodes--;
319
320
0
    n1 = lh->b[(int)lh->p];
321
0
    if (n1 == NULL)
322
0
        lh->b[(int)lh->p] = np;
323
0
    else {
324
0
        while (n1->next != NULL)
325
0
            n1 = n1->next;
326
0
        n1->next = np;
327
0
    }
328
0
}
329
330
static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh,
331
    const void *data, unsigned long *rhash)
332
205k
{
333
205k
    OPENSSL_LH_NODE **ret, *n1;
334
205k
    unsigned long hash, nn;
335
336
205k
    if (lh->hashw != NULL)
337
205k
        hash = lh->hashw(data, lh->hash);
338
0
    else
339
0
        hash = lh->hash(data);
340
341
205k
    *rhash = hash;
342
343
205k
    nn = hash % lh->pmax;
344
205k
    if (nn < lh->p)
345
141k
        nn = hash % lh->num_alloc_nodes;
346
347
205k
    ret = &(lh->b[(int)nn]);
348
433k
    for (n1 = *ret; n1 != NULL; n1 = n1->next) {
349
379k
        if (n1->hash != hash) {
350
222k
            ret = &(n1->next);
351
222k
            continue;
352
222k
        }
353
354
156k
        if (lh->compw != NULL) {
355
156k
            if (lh->compw(n1->data, data, lh->comp) == 0)
356
150k
                break;
357
156k
        } else {
358
0
            if (lh->comp(n1->data, data) == 0)
359
0
                break;
360
0
        }
361
6.12k
        ret = &(n1->next);
362
6.12k
    }
363
205k
    return ret;
364
205k
}
365
366
/*
367
 * The following hash seems to work very well on normal text strings no
368
 * collisions on /usr/dict/words and it distributes on %2^n quite well, not
369
 * as good as MD5, but still good.
370
 */
371
unsigned long OPENSSL_LH_strhash(const char *c)
372
3.26k
{
373
3.26k
    unsigned long ret = 0;
374
3.26k
    long n;
375
3.26k
    unsigned long v;
376
3.26k
    int r;
377
378
3.26k
    if ((c == NULL) || (*c == '\0'))
379
0
        return ret;
380
381
3.26k
    n = 0x100;
382
50.3k
    while (*c) {
383
47.0k
        v = n | (*c);
384
47.0k
        n += 0x100;
385
47.0k
        r = (int)((v >> 2) ^ v) & 0x0f;
386
        /* cast to uint64_t to avoid 32 bit shift of 32 bit value */
387
47.0k
        ret = (ret << r) | (unsigned long)((uint64_t)ret >> (32 - r));
388
47.0k
        ret &= 0xFFFFFFFFL;
389
47.0k
        ret ^= v * v;
390
47.0k
        c++;
391
47.0k
    }
392
3.26k
    return (ret >> 16) ^ ret;
393
3.26k
}
394
395
/*
396
 * Case insensitive string hashing.
397
 *
398
 * The lower/upper case bit is masked out (forcing all letters to be capitals).
399
 * The major side effect on non-alpha characters is mapping the symbols and
400
 * digits into the control character range (which should be harmless).
401
 * The duplication (with respect to the hash value) of printable characters
402
 * are that '`', '{', '|', '}' and '~' map to '@', '[', '\', ']' and '^'
403
 * respectively (which seems tolerable).
404
 *
405
 * For EBCDIC, the alpha mapping is to lower case, most symbols go to control
406
 * characters.  The only duplication is '0' mapping to '^', which is better
407
 * than for ASCII.
408
 */
409
unsigned long ossl_lh_strcasehash(const char *c)
410
17.4k
{
411
17.4k
    unsigned long ret = 0;
412
17.4k
    long n;
413
17.4k
    unsigned long v;
414
17.4k
    int r;
415
#if defined(CHARSET_EBCDIC) && !defined(CHARSET_EBCDIC_TEST)
416
    const long int case_adjust = ~0x40;
417
#else
418
17.4k
    const long int case_adjust = ~0x20;
419
17.4k
#endif
420
421
17.4k
    if (c == NULL || *c == '\0')
422
0
        return ret;
423
424
226k
    for (n = 0x100; *c != '\0'; n += 0x100) {
425
209k
        v = n | (case_adjust & *c);
426
209k
        r = (int)((v >> 2) ^ v) & 0x0f;
427
        /* cast to uint64_t to avoid 32 bit shift of 32 bit value */
428
209k
        ret = (ret << r) | (unsigned long)((uint64_t)ret >> (32 - r));
429
209k
        ret &= 0xFFFFFFFFL;
430
209k
        ret ^= v * v;
431
209k
        c++;
432
209k
    }
433
17.4k
    return (ret >> 16) ^ ret;
434
17.4k
}
435
436
unsigned long OPENSSL_LH_num_items(const OPENSSL_LHASH *lh)
437
0
{
438
0
    return lh ? lh->num_items : 0;
439
0
}
440
441
unsigned long OPENSSL_LH_get_down_load(const OPENSSL_LHASH *lh)
442
0
{
443
0
    return lh->down_load;
444
0
}
445
446
void OPENSSL_LH_set_down_load(OPENSSL_LHASH *lh, unsigned long down_load)
447
0
{
448
0
    lh->down_load = down_load;
449
0
}
450
451
int OPENSSL_LH_error(OPENSSL_LHASH *lh)
452
4.03k
{
453
4.03k
    return lh->error;
454
4.03k
}