[331] | 1 | /*
|
---|
| 2 | * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
|
---|
| 3 | *
|
---|
| 4 | * Licensed under the OpenSSL license (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 "lhash_lcl.h"
|
---|
| 16 |
|
---|
| 17 |
|
---|
| 18 | #undef MIN_NODES
|
---|
| 19 | #define MIN_NODES 16
|
---|
| 20 | #define UP_LOAD (2*LH_LOAD_MULT) /* load times 256 (default 2) */
|
---|
| 21 | #define DOWN_LOAD (LH_LOAD_MULT) /* load times 256 (default 1) */
|
---|
| 22 |
|
---|
| 23 | static int expand(OPENSSL_LHASH *lh);
|
---|
| 24 | static void contract(OPENSSL_LHASH *lh);
|
---|
| 25 | static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh, const void *data, unsigned long *rhash);
|
---|
| 26 |
|
---|
| 27 | OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c)
|
---|
| 28 | {
|
---|
| 29 | OPENSSL_LHASH *ret;
|
---|
| 30 |
|
---|
| 31 | if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
|
---|
| 32 | goto err0;
|
---|
| 33 | if ((ret->b = OPENSSL_zalloc(sizeof(*ret->b) * MIN_NODES)) == NULL)
|
---|
| 34 | goto err1;
|
---|
| 35 | ret->comp = ((c == NULL) ? (OPENSSL_LH_COMPFUNC)strcmp : c);
|
---|
| 36 | ret->hash = ((h == NULL) ? (OPENSSL_LH_HASHFUNC)OPENSSL_LH_strhash : h);
|
---|
| 37 | ret->num_nodes = MIN_NODES / 2;
|
---|
| 38 | ret->num_alloc_nodes = MIN_NODES;
|
---|
| 39 | ret->pmax = MIN_NODES / 2;
|
---|
| 40 | ret->up_load = UP_LOAD;
|
---|
| 41 | ret->down_load = DOWN_LOAD;
|
---|
| 42 | return (ret);
|
---|
| 43 |
|
---|
| 44 | err1:
|
---|
| 45 | OPENSSL_free(ret);
|
---|
| 46 | err0:
|
---|
| 47 | return (NULL);
|
---|
| 48 | }
|
---|
| 49 |
|
---|
| 50 | void OPENSSL_LH_free(OPENSSL_LHASH *lh)
|
---|
| 51 | {
|
---|
| 52 | unsigned int i;
|
---|
| 53 | OPENSSL_LH_NODE *n, *nn;
|
---|
| 54 |
|
---|
| 55 | if (lh == NULL)
|
---|
| 56 | return;
|
---|
| 57 |
|
---|
| 58 | for (i = 0; i < lh->num_nodes; i++) {
|
---|
| 59 | n = lh->b[i];
|
---|
| 60 | while (n != NULL) {
|
---|
| 61 | nn = n->next;
|
---|
| 62 | OPENSSL_free(n);
|
---|
| 63 | n = nn;
|
---|
| 64 | }
|
---|
| 65 | }
|
---|
| 66 | OPENSSL_free(lh->b);
|
---|
| 67 | OPENSSL_free(lh);
|
---|
| 68 | }
|
---|
| 69 |
|
---|
| 70 | void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data)
|
---|
| 71 | {
|
---|
| 72 | unsigned long hash;
|
---|
| 73 | OPENSSL_LH_NODE *nn, **rn;
|
---|
| 74 | void *ret;
|
---|
| 75 |
|
---|
| 76 | lh->error = 0;
|
---|
| 77 | if ((lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)) && !expand(lh))
|
---|
| 78 | return NULL; /* 'lh->error++' already done in 'expand' */
|
---|
| 79 |
|
---|
| 80 | rn = getrn(lh, data, &hash);
|
---|
| 81 |
|
---|
| 82 | if (*rn == NULL) {
|
---|
| 83 | if ((nn = OPENSSL_malloc(sizeof(*nn))) == NULL) {
|
---|
| 84 | lh->error++;
|
---|
| 85 | return (NULL);
|
---|
| 86 | }
|
---|
| 87 | nn->data = data;
|
---|
| 88 | nn->next = NULL;
|
---|
| 89 | nn->hash = hash;
|
---|
| 90 | *rn = nn;
|
---|
| 91 | ret = NULL;
|
---|
| 92 | lh->num_insert++;
|
---|
| 93 | lh->num_items++;
|
---|
| 94 | } else { /* replace same key */
|
---|
| 95 |
|
---|
| 96 | ret = (*rn)->data;
|
---|
| 97 | (*rn)->data = data;
|
---|
| 98 | lh->num_replace++;
|
---|
| 99 | }
|
---|
| 100 | return (ret);
|
---|
| 101 | }
|
---|
| 102 |
|
---|
| 103 | void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data)
|
---|
| 104 | {
|
---|
| 105 | unsigned long hash;
|
---|
| 106 | OPENSSL_LH_NODE *nn, **rn;
|
---|
| 107 | void *ret;
|
---|
| 108 |
|
---|
| 109 | lh->error = 0;
|
---|
| 110 | rn = getrn(lh, data, &hash);
|
---|
| 111 |
|
---|
| 112 | if (*rn == NULL) {
|
---|
| 113 | lh->num_no_delete++;
|
---|
| 114 | return (NULL);
|
---|
| 115 | } else {
|
---|
| 116 | nn = *rn;
|
---|
| 117 | *rn = nn->next;
|
---|
| 118 | ret = nn->data;
|
---|
| 119 | OPENSSL_free(nn);
|
---|
| 120 | lh->num_delete++;
|
---|
| 121 | }
|
---|
| 122 |
|
---|
| 123 | lh->num_items--;
|
---|
| 124 | if ((lh->num_nodes > MIN_NODES) &&
|
---|
| 125 | (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)))
|
---|
| 126 | contract(lh);
|
---|
| 127 |
|
---|
| 128 | return (ret);
|
---|
| 129 | }
|
---|
| 130 |
|
---|
| 131 | void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data)
|
---|
| 132 | {
|
---|
| 133 | unsigned long hash;
|
---|
| 134 | OPENSSL_LH_NODE **rn;
|
---|
| 135 | void *ret;
|
---|
| 136 |
|
---|
| 137 | lh->error = 0;
|
---|
| 138 | rn = getrn(lh, data, &hash);
|
---|
| 139 |
|
---|
| 140 | if (*rn == NULL) {
|
---|
| 141 | lh->num_retrieve_miss++;
|
---|
| 142 | return (NULL);
|
---|
| 143 | } else {
|
---|
| 144 | ret = (*rn)->data;
|
---|
| 145 | lh->num_retrieve++;
|
---|
| 146 | }
|
---|
| 147 | return (ret);
|
---|
| 148 | }
|
---|
| 149 |
|
---|
| 150 | static void doall_util_fn(OPENSSL_LHASH *lh, int use_arg,
|
---|
| 151 | OPENSSL_LH_DOALL_FUNC func,
|
---|
| 152 | OPENSSL_LH_DOALL_FUNCARG func_arg, void *arg)
|
---|
| 153 | {
|
---|
| 154 | int i;
|
---|
| 155 | OPENSSL_LH_NODE *a, *n;
|
---|
| 156 |
|
---|
| 157 | if (lh == NULL)
|
---|
| 158 | return;
|
---|
| 159 |
|
---|
| 160 | /*
|
---|
| 161 | * reverse the order so we search from 'top to bottom' We were having
|
---|
| 162 | * memory leaks otherwise
|
---|
| 163 | */
|
---|
| 164 | for (i = lh->num_nodes - 1; i >= 0; i--) {
|
---|
| 165 | a = lh->b[i];
|
---|
| 166 | while (a != NULL) {
|
---|
| 167 | n = a->next;
|
---|
| 168 | if (use_arg)
|
---|
| 169 | func_arg(a->data, arg);
|
---|
| 170 | else
|
---|
| 171 | func(a->data);
|
---|
| 172 | a = n;
|
---|
| 173 | }
|
---|
| 174 | }
|
---|
| 175 | }
|
---|
| 176 |
|
---|
| 177 | void OPENSSL_LH_doall(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNC func)
|
---|
| 178 | {
|
---|
| 179 | doall_util_fn(lh, 0, func, (OPENSSL_LH_DOALL_FUNCARG)0, NULL);
|
---|
| 180 | }
|
---|
| 181 |
|
---|
| 182 | void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNCARG func, void *arg)
|
---|
| 183 | {
|
---|
| 184 | doall_util_fn(lh, 1, (OPENSSL_LH_DOALL_FUNC)0, func, arg);
|
---|
| 185 | }
|
---|
| 186 |
|
---|
| 187 | static int expand(OPENSSL_LHASH *lh)
|
---|
| 188 | {
|
---|
| 189 | OPENSSL_LH_NODE **n, **n1, **n2, *np;
|
---|
| 190 | unsigned int p, i, j;
|
---|
| 191 | unsigned long hash, nni;
|
---|
| 192 |
|
---|
| 193 | lh->num_nodes++;
|
---|
| 194 | lh->num_expands++;
|
---|
| 195 | p = (int)lh->p++;
|
---|
| 196 | n1 = &(lh->b[p]);
|
---|
| 197 | n2 = &(lh->b[p + (int)lh->pmax]);
|
---|
| 198 | *n2 = NULL;
|
---|
| 199 | nni = lh->num_alloc_nodes;
|
---|
| 200 |
|
---|
| 201 | for (np = *n1; np != NULL;) {
|
---|
| 202 | hash = np->hash;
|
---|
| 203 | if ((hash % nni) != p) { /* move it */
|
---|
| 204 | *n1 = (*n1)->next;
|
---|
| 205 | np->next = *n2;
|
---|
| 206 | *n2 = np;
|
---|
| 207 | } else
|
---|
| 208 | n1 = &((*n1)->next);
|
---|
| 209 | np = *n1;
|
---|
| 210 | }
|
---|
| 211 |
|
---|
| 212 | if ((lh->p) >= lh->pmax) {
|
---|
| 213 | j = (int)lh->num_alloc_nodes * 2;
|
---|
| 214 | n = OPENSSL_realloc(lh->b, (int)(sizeof(OPENSSL_LH_NODE *) * j));
|
---|
| 215 | if (n == NULL) {
|
---|
| 216 | lh->error++;
|
---|
| 217 | lh->num_nodes--;
|
---|
| 218 | lh->p = 0;
|
---|
| 219 | return 0;
|
---|
| 220 | }
|
---|
| 221 | for (i = (int)lh->num_alloc_nodes; i < j; i++) /* 26/02/92 eay */
|
---|
| 222 | n[i] = NULL; /* 02/03/92 eay */
|
---|
| 223 | lh->pmax = lh->num_alloc_nodes;
|
---|
| 224 | lh->num_alloc_nodes = j;
|
---|
| 225 | lh->num_expand_reallocs++;
|
---|
| 226 | lh->p = 0;
|
---|
| 227 | lh->b = n;
|
---|
| 228 | }
|
---|
| 229 | return 1;
|
---|
| 230 | }
|
---|
| 231 |
|
---|
| 232 | static void contract(OPENSSL_LHASH *lh)
|
---|
| 233 | {
|
---|
| 234 | OPENSSL_LH_NODE **n, *n1, *np;
|
---|
| 235 |
|
---|
| 236 | np = lh->b[lh->p + lh->pmax - 1];
|
---|
| 237 | lh->b[lh->p + lh->pmax - 1] = NULL; /* 24/07-92 - eay - weird but :-( */
|
---|
| 238 | if (lh->p == 0) {
|
---|
| 239 | n = OPENSSL_realloc(lh->b,
|
---|
| 240 | (unsigned int)(sizeof(OPENSSL_LH_NODE *) * lh->pmax));
|
---|
| 241 | if (n == NULL) {
|
---|
| 242 | /* fputs("realloc error in lhash",stderr); */
|
---|
| 243 | lh->error++;
|
---|
| 244 | return;
|
---|
| 245 | }
|
---|
| 246 | lh->num_contract_reallocs++;
|
---|
| 247 | lh->num_alloc_nodes /= 2;
|
---|
| 248 | lh->pmax /= 2;
|
---|
| 249 | lh->p = lh->pmax - 1;
|
---|
| 250 | lh->b = n;
|
---|
| 251 | } else
|
---|
| 252 | lh->p--;
|
---|
| 253 |
|
---|
| 254 | lh->num_nodes--;
|
---|
| 255 | lh->num_contracts++;
|
---|
| 256 |
|
---|
| 257 | n1 = lh->b[(int)lh->p];
|
---|
| 258 | if (n1 == NULL)
|
---|
| 259 | lh->b[(int)lh->p] = np;
|
---|
| 260 | else {
|
---|
| 261 | while (n1->next != NULL)
|
---|
| 262 | n1 = n1->next;
|
---|
| 263 | n1->next = np;
|
---|
| 264 | }
|
---|
| 265 | }
|
---|
| 266 |
|
---|
| 267 | static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh,
|
---|
| 268 | const void *data, unsigned long *rhash)
|
---|
| 269 | {
|
---|
| 270 | OPENSSL_LH_NODE **ret, *n1;
|
---|
| 271 | unsigned long hash, nn;
|
---|
| 272 | OPENSSL_LH_COMPFUNC cf;
|
---|
| 273 |
|
---|
| 274 | hash = (*(lh->hash)) (data);
|
---|
| 275 | lh->num_hash_calls++;
|
---|
| 276 | *rhash = hash;
|
---|
| 277 |
|
---|
| 278 | nn = hash % lh->pmax;
|
---|
| 279 | if (nn < lh->p)
|
---|
| 280 | nn = hash % lh->num_alloc_nodes;
|
---|
| 281 |
|
---|
| 282 | cf = lh->comp;
|
---|
| 283 | ret = &(lh->b[(int)nn]);
|
---|
| 284 | for (n1 = *ret; n1 != NULL; n1 = n1->next) {
|
---|
| 285 | lh->num_hash_comps++;
|
---|
| 286 | if (n1->hash != hash) {
|
---|
| 287 | ret = &(n1->next);
|
---|
| 288 | continue;
|
---|
| 289 | }
|
---|
| 290 | lh->num_comp_calls++;
|
---|
| 291 | if (cf(n1->data, data) == 0)
|
---|
| 292 | break;
|
---|
| 293 | ret = &(n1->next);
|
---|
| 294 | }
|
---|
| 295 | return (ret);
|
---|
| 296 | }
|
---|
| 297 |
|
---|
| 298 | /*
|
---|
| 299 | * The following hash seems to work very well on normal text strings no
|
---|
| 300 | * collisions on /usr/dict/words and it distributes on %2^n quite well, not
|
---|
| 301 | * as good as MD5, but still good.
|
---|
| 302 | */
|
---|
| 303 | unsigned long OPENSSL_LH_strhash(const char *c)
|
---|
| 304 | {
|
---|
| 305 | unsigned long ret = 0;
|
---|
| 306 | long n;
|
---|
| 307 | unsigned long v;
|
---|
| 308 | int r;
|
---|
| 309 |
|
---|
| 310 | if ((c == NULL) || (*c == '\0'))
|
---|
| 311 | return (ret);
|
---|
| 312 | /*-
|
---|
| 313 | unsigned char b[16];
|
---|
| 314 | MD5(c,strlen(c),b);
|
---|
| 315 | return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
|
---|
| 316 | */
|
---|
| 317 |
|
---|
| 318 | n = 0x100;
|
---|
| 319 | while (*c) {
|
---|
| 320 | v = n | (*c);
|
---|
| 321 | n += 0x100;
|
---|
| 322 | r = (int)((v >> 2) ^ v) & 0x0f;
|
---|
| 323 | ret = (ret << r) | (ret >> (32 - r));
|
---|
| 324 | ret &= 0xFFFFFFFFL;
|
---|
| 325 | ret ^= v * v;
|
---|
| 326 | c++;
|
---|
| 327 | }
|
---|
| 328 | return ((ret >> 16) ^ ret);
|
---|
| 329 | }
|
---|
| 330 |
|
---|
| 331 | unsigned long OPENSSL_LH_num_items(const OPENSSL_LHASH *lh)
|
---|
| 332 | {
|
---|
| 333 | return lh ? lh->num_items : 0;
|
---|
| 334 | }
|
---|
| 335 |
|
---|
| 336 | unsigned long OPENSSL_LH_get_down_load(const OPENSSL_LHASH *lh)
|
---|
| 337 | {
|
---|
| 338 | return lh->down_load;
|
---|
| 339 | }
|
---|
| 340 |
|
---|
| 341 | void OPENSSL_LH_set_down_load(OPENSSL_LHASH *lh, unsigned long down_load)
|
---|
| 342 | {
|
---|
| 343 | lh->down_load = down_load;
|
---|
| 344 | }
|
---|
| 345 |
|
---|
| 346 | int OPENSSL_LH_error(OPENSSL_LHASH *lh)
|
---|
| 347 | {
|
---|
| 348 | return lh->error;
|
---|
| 349 | }
|
---|