crypto/lhash/lhash.c

   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
  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
  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
  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
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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  */
 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  */
 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
 426 unsigned long OPENSSL_LH_num_items(const OPENSSL_LHASH *lh)
 427 {
 428     return lh ? lh->num_items : 0;
 429 }
 430
 431 unsigned long OPENSSL_LH_get_down_load(const OPENSSL_LHASH *lh)
 432 {
 433     return lh->down_load;
 434 }
 435
 436 void OPENSSL_LH_set_down_load(OPENSSL_LHASH *lh, unsigned long down_load)
 437 {
 438     lh->down_load = down_load;
 439 }
 440
 441 int OPENSSL_LH_error(OPENSSL_LHASH *lh)
 442 {
 443     return lh->error;
 444 }