1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ssl/libcrypto/src/crypto/lhash/lhash.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,470 @@
1.4 +/* crypto/lhash/lhash.c */
1.5 +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
1.6 + * All rights reserved.
1.7 + *
1.8 + * This package is an SSL implementation written
1.9 + * by Eric Young (eay@cryptsoft.com).
1.10 + * The implementation was written so as to conform with Netscapes SSL.
1.11 + *
1.12 + * This library is free for commercial and non-commercial use as long as
1.13 + * the following conditions are aheared to. The following conditions
1.14 + * apply to all code found in this distribution, be it the RC4, RSA,
1.15 + * lhash, DES, etc., code; not just the SSL code. The SSL documentation
1.16 + * included with this distribution is covered by the same copyright terms
1.17 + * except that the holder is Tim Hudson (tjh@cryptsoft.com).
1.18 + *
1.19 + * Copyright remains Eric Young's, and as such any Copyright notices in
1.20 + * the code are not to be removed.
1.21 + * If this package is used in a product, Eric Young should be given attribution
1.22 + * as the author of the parts of the library used.
1.23 + * This can be in the form of a textual message at program startup or
1.24 + * in documentation (online or textual) provided with the package.
1.25 + *
1.26 + * Redistribution and use in source and binary forms, with or without
1.27 + * modification, are permitted provided that the following conditions
1.28 + * are met:
1.29 + * 1. Redistributions of source code must retain the copyright
1.30 + * notice, this list of conditions and the following disclaimer.
1.31 + * 2. Redistributions in binary form must reproduce the above copyright
1.32 + * notice, this list of conditions and the following disclaimer in the
1.33 + * documentation and/or other materials provided with the distribution.
1.34 + * 3. All advertising materials mentioning features or use of this software
1.35 + * must display the following acknowledgement:
1.36 + * "This product includes cryptographic software written by
1.37 + * Eric Young (eay@cryptsoft.com)"
1.38 + * The word 'cryptographic' can be left out if the rouines from the library
1.39 + * being used are not cryptographic related :-).
1.40 + * 4. If you include any Windows specific code (or a derivative thereof) from
1.41 + * the apps directory (application code) you must include an acknowledgement:
1.42 + * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
1.43 + *
1.44 + * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
1.45 + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.46 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.47 + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
1.48 + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1.49 + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
1.50 + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1.51 + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1.52 + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
1.53 + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
1.54 + * SUCH DAMAGE.
1.55 + *
1.56 + * The licence and distribution terms for any publically available version or
1.57 + * derivative of this code cannot be changed. i.e. this code cannot simply be
1.58 + * copied and put under another distribution licence
1.59 + * [including the GNU Public Licence.]
1.60 + */
1.61 +
1.62 +/* Code for dynamic hash table routines
1.63 + * Author - Eric Young v 2.0
1.64 + *
1.65 + * 2.2 eay - added #include "crypto.h" so the memory leak checking code is
1.66 + * present. eay 18-Jun-98
1.67 + *
1.68 + * 2.1 eay - Added an 'error in last operation' flag. eay 6-May-98
1.69 + *
1.70 + * 2.0 eay - Fixed a bug that occurred when using lh_delete
1.71 + * from inside lh_doall(). As entries were deleted,
1.72 + * the 'table' was 'contract()ed', making some entries
1.73 + * jump from the end of the table to the start, there by
1.74 + * skipping the lh_doall() processing. eay - 4/12/95
1.75 + *
1.76 + * 1.9 eay - Fixed a memory leak in lh_free, the LHASH_NODEs
1.77 + * were not being free()ed. 21/11/95
1.78 + *
1.79 + * 1.8 eay - Put the stats routines into a separate file, lh_stats.c
1.80 + * 19/09/95
1.81 + *
1.82 + * 1.7 eay - Removed the fputs() for realloc failures - the code
1.83 + * should silently tolerate them. I have also fixed things
1.84 + * lint complained about 04/05/95
1.85 + *
1.86 + * 1.6 eay - Fixed an invalid pointers in contract/expand 27/07/92
1.87 + *
1.88 + * 1.5 eay - Fixed a misuse of realloc in expand 02/03/1992
1.89 + *
1.90 + * 1.4 eay - Fixed lh_doall so the function can call lh_delete 28/05/91
1.91 + *
1.92 + * 1.3 eay - Fixed a few lint problems 19/3/1991
1.93 + *
1.94 + * 1.2 eay - Fixed lh_doall problem 13/3/1991
1.95 + *
1.96 + * 1.1 eay - Added lh_doall
1.97 + *
1.98 + * 1.0 eay - First version
1.99 + */
1.100 +#include <stdio.h>
1.101 +#include <string.h>
1.102 +#include <stdlib.h>
1.103 +#include <openssl/crypto.h>
1.104 +#include <openssl/lhash.h>
1.105 +
1.106 +const char lh_version[]="lhash" OPENSSL_VERSION_PTEXT;
1.107 +
1.108 +#undef MIN_NODES
1.109 +#define MIN_NODES 16
1.110 +#define UP_LOAD (2*LH_LOAD_MULT) /* load times 256 (default 2) */
1.111 +#define DOWN_LOAD (LH_LOAD_MULT) /* load times 256 (default 1) */
1.112 +
1.113 +static void expand(LHASH *lh);
1.114 +static void contract(LHASH *lh);
1.115 +static LHASH_NODE **getrn(LHASH *lh, const void *data, unsigned long *rhash);
1.116 +
1.117 +EXPORT_C LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c)
1.118 + {
1.119 + LHASH *ret;
1.120 + int i;
1.121 +
1.122 + if ((ret=(LHASH *)OPENSSL_malloc(sizeof(LHASH))) == NULL)
1.123 + goto err0;
1.124 + if ((ret->b=(LHASH_NODE **)OPENSSL_malloc(sizeof(LHASH_NODE *)*MIN_NODES)) == NULL)
1.125 + goto err1;
1.126 + for (i=0; i<MIN_NODES; i++)
1.127 + ret->b[i]=NULL;
1.128 + ret->comp=((c == NULL)?(LHASH_COMP_FN_TYPE)strcmp:c);
1.129 + ret->hash=((h == NULL)?(LHASH_HASH_FN_TYPE)lh_strhash:h);
1.130 + ret->num_nodes=MIN_NODES/2;
1.131 + ret->num_alloc_nodes=MIN_NODES;
1.132 + ret->p=0;
1.133 + ret->pmax=MIN_NODES/2;
1.134 + ret->up_load=UP_LOAD;
1.135 + ret->down_load=DOWN_LOAD;
1.136 + ret->num_items=0;
1.137 +
1.138 + ret->num_expands=0;
1.139 + ret->num_expand_reallocs=0;
1.140 + ret->num_contracts=0;
1.141 + ret->num_contract_reallocs=0;
1.142 + ret->num_hash_calls=0;
1.143 + ret->num_comp_calls=0;
1.144 + ret->num_insert=0;
1.145 + ret->num_replace=0;
1.146 + ret->num_delete=0;
1.147 + ret->num_no_delete=0;
1.148 + ret->num_retrieve=0;
1.149 + ret->num_retrieve_miss=0;
1.150 + ret->num_hash_comps=0;
1.151 +
1.152 + ret->error=0;
1.153 + return(ret);
1.154 +err1:
1.155 + OPENSSL_free(ret);
1.156 +err0:
1.157 + return(NULL);
1.158 + }
1.159 +
1.160 +EXPORT_C void lh_free(LHASH *lh)
1.161 + {
1.162 + unsigned int i;
1.163 + LHASH_NODE *n,*nn;
1.164 +
1.165 + if (lh == NULL)
1.166 + return;
1.167 +
1.168 + for (i=0; i<lh->num_nodes; i++)
1.169 + {
1.170 + n=lh->b[i];
1.171 + while (n != NULL)
1.172 + {
1.173 + nn=n->next;
1.174 + OPENSSL_free(n);
1.175 + n=nn;
1.176 + }
1.177 + }
1.178 + OPENSSL_free(lh->b);
1.179 + OPENSSL_free(lh);
1.180 + }
1.181 +
1.182 +EXPORT_C void *lh_insert(LHASH *lh, void *data)
1.183 + {
1.184 + unsigned long hash;
1.185 + LHASH_NODE *nn,**rn;
1.186 + void *ret;
1.187 +
1.188 + lh->error=0;
1.189 + if (lh->up_load <= (lh->num_items*LH_LOAD_MULT/lh->num_nodes))
1.190 + expand(lh);
1.191 +
1.192 + rn=getrn(lh,data,&hash);
1.193 +
1.194 + if (*rn == NULL)
1.195 + {
1.196 + if ((nn=(LHASH_NODE *)OPENSSL_malloc(sizeof(LHASH_NODE))) == NULL)
1.197 + {
1.198 + lh->error++;
1.199 + return(NULL);
1.200 + }
1.201 + nn->data=data;
1.202 + nn->next=NULL;
1.203 +#ifndef OPENSSL_NO_HASH_COMP
1.204 + nn->hash=hash;
1.205 +#endif
1.206 + *rn=nn;
1.207 + ret=NULL;
1.208 + lh->num_insert++;
1.209 + lh->num_items++;
1.210 + }
1.211 + else /* replace same key */
1.212 + {
1.213 + ret= (*rn)->data;
1.214 + (*rn)->data=data;
1.215 + lh->num_replace++;
1.216 + }
1.217 + return(ret);
1.218 + }
1.219 +
1.220 +EXPORT_C void *lh_delete(LHASH *lh, const void *data)
1.221 + {
1.222 + unsigned long hash;
1.223 + LHASH_NODE *nn,**rn;
1.224 + void *ret;
1.225 +
1.226 + lh->error=0;
1.227 + rn=getrn(lh,data,&hash);
1.228 +
1.229 + if (*rn == NULL)
1.230 + {
1.231 + lh->num_no_delete++;
1.232 + return(NULL);
1.233 + }
1.234 + else
1.235 + {
1.236 + nn= *rn;
1.237 + *rn=nn->next;
1.238 + ret=nn->data;
1.239 + OPENSSL_free(nn);
1.240 + lh->num_delete++;
1.241 + }
1.242 +
1.243 + lh->num_items--;
1.244 + if ((lh->num_nodes > MIN_NODES) &&
1.245 + (lh->down_load >= (lh->num_items*LH_LOAD_MULT/lh->num_nodes)))
1.246 + contract(lh);
1.247 +
1.248 + return(ret);
1.249 + }
1.250 +
1.251 +EXPORT_C void *lh_retrieve(LHASH *lh, const void *data)
1.252 + {
1.253 + unsigned long hash;
1.254 + LHASH_NODE **rn;
1.255 + void *ret;
1.256 +
1.257 + lh->error=0;
1.258 + rn=getrn(lh,data,&hash);
1.259 +
1.260 + if (*rn == NULL)
1.261 + {
1.262 + lh->num_retrieve_miss++;
1.263 + return(NULL);
1.264 + }
1.265 + else
1.266 + {
1.267 + ret= (*rn)->data;
1.268 + lh->num_retrieve++;
1.269 + }
1.270 + return(ret);
1.271 + }
1.272 +
1.273 +static void doall_util_fn(LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func,
1.274 + LHASH_DOALL_ARG_FN_TYPE func_arg, void *arg)
1.275 + {
1.276 + int i;
1.277 + LHASH_NODE *a,*n;
1.278 +
1.279 + /* reverse the order so we search from 'top to bottom'
1.280 + * We were having memory leaks otherwise */
1.281 + for (i=lh->num_nodes-1; i>=0; i--)
1.282 + {
1.283 + a=lh->b[i];
1.284 + while (a != NULL)
1.285 + {
1.286 + /* 28/05/91 - eay - n added so items can be deleted
1.287 + * via lh_doall */
1.288 + n=a->next;
1.289 + if(use_arg)
1.290 + func_arg(a->data,arg);
1.291 + else
1.292 + func(a->data);
1.293 + a=n;
1.294 + }
1.295 + }
1.296 + }
1.297 +
1.298 +EXPORT_C void lh_doall(LHASH *lh, LHASH_DOALL_FN_TYPE func)
1.299 + {
1.300 + doall_util_fn(lh, 0, func, (LHASH_DOALL_ARG_FN_TYPE)0, NULL);
1.301 + }
1.302 +
1.303 +EXPORT_C void lh_doall_arg(LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg)
1.304 + {
1.305 + doall_util_fn(lh, 1, (LHASH_DOALL_FN_TYPE)0, func, arg);
1.306 + }
1.307 +
1.308 +static void expand(LHASH *lh)
1.309 + {
1.310 + LHASH_NODE **n,**n1,**n2,*np;
1.311 + unsigned int p,i,j;
1.312 + unsigned long hash,nni;
1.313 +
1.314 + lh->num_nodes++;
1.315 + lh->num_expands++;
1.316 + p=(int)lh->p++;
1.317 + n1= &(lh->b[p]);
1.318 + n2= &(lh->b[p+(int)lh->pmax]);
1.319 + *n2=NULL; /* 27/07/92 - eay - undefined pointer bug */
1.320 + nni=lh->num_alloc_nodes;
1.321 +
1.322 + for (np= *n1; np != NULL; )
1.323 + {
1.324 +#ifndef OPENSSL_NO_HASH_COMP
1.325 + hash=np->hash;
1.326 +#else
1.327 + hash=lh->hash(np->data);
1.328 + lh->num_hash_calls++;
1.329 +#endif
1.330 + if ((hash%nni) != p)
1.331 + { /* move it */
1.332 + *n1= (*n1)->next;
1.333 + np->next= *n2;
1.334 + *n2=np;
1.335 + }
1.336 + else
1.337 + n1= &((*n1)->next);
1.338 + np= *n1;
1.339 + }
1.340 +
1.341 + if ((lh->p) >= lh->pmax)
1.342 + {
1.343 + j=(int)lh->num_alloc_nodes*2;
1.344 + n=(LHASH_NODE **)OPENSSL_realloc(lh->b,
1.345 + (int)(sizeof(LHASH_NODE *)*j));
1.346 + if (n == NULL)
1.347 + {
1.348 +/* fputs("realloc error in lhash",stderr); */
1.349 + lh->error++;
1.350 + lh->p=0;
1.351 + return;
1.352 + }
1.353 + /* else */
1.354 + for (i=(int)lh->num_alloc_nodes; i<j; i++)/* 26/02/92 eay */
1.355 + n[i]=NULL; /* 02/03/92 eay */
1.356 + lh->pmax=lh->num_alloc_nodes;
1.357 + lh->num_alloc_nodes=j;
1.358 + lh->num_expand_reallocs++;
1.359 + lh->p=0;
1.360 + lh->b=n;
1.361 + }
1.362 + }
1.363 +
1.364 +static void contract(LHASH *lh)
1.365 + {
1.366 + LHASH_NODE **n,*n1,*np;
1.367 +
1.368 + np=lh->b[lh->p+lh->pmax-1];
1.369 + lh->b[lh->p+lh->pmax-1]=NULL; /* 24/07-92 - eay - weird but :-( */
1.370 + if (lh->p == 0)
1.371 + {
1.372 + n=(LHASH_NODE **)OPENSSL_realloc(lh->b,
1.373 + (unsigned int)(sizeof(LHASH_NODE *)*lh->pmax));
1.374 + if (n == NULL)
1.375 + {
1.376 +/* fputs("realloc error in lhash",stderr); */
1.377 + lh->error++;
1.378 + return;
1.379 + }
1.380 + lh->num_contract_reallocs++;
1.381 + lh->num_alloc_nodes/=2;
1.382 + lh->pmax/=2;
1.383 + lh->p=lh->pmax-1;
1.384 + lh->b=n;
1.385 + }
1.386 + else
1.387 + lh->p--;
1.388 +
1.389 + lh->num_nodes--;
1.390 + lh->num_contracts++;
1.391 +
1.392 + n1=lh->b[(int)lh->p];
1.393 + if (n1 == NULL)
1.394 + lh->b[(int)lh->p]=np;
1.395 + else
1.396 + {
1.397 + while (n1->next != NULL)
1.398 + n1=n1->next;
1.399 + n1->next=np;
1.400 + }
1.401 + }
1.402 +
1.403 +static LHASH_NODE **getrn(LHASH *lh, const void *data, unsigned long *rhash)
1.404 + {
1.405 + LHASH_NODE **ret,*n1;
1.406 + unsigned long hash,nn;
1.407 + LHASH_COMP_FN_TYPE cf;
1.408 +
1.409 + hash=(*(lh->hash))(data);
1.410 + lh->num_hash_calls++;
1.411 + *rhash=hash;
1.412 +
1.413 + nn=hash%lh->pmax;
1.414 + if (nn < lh->p)
1.415 + nn=hash%lh->num_alloc_nodes;
1.416 +
1.417 + cf=lh->comp;
1.418 + ret= &(lh->b[(int)nn]);
1.419 + for (n1= *ret; n1 != NULL; n1=n1->next)
1.420 + {
1.421 +#ifndef OPENSSL_NO_HASH_COMP
1.422 + lh->num_hash_comps++;
1.423 + if (n1->hash != hash)
1.424 + {
1.425 + ret= &(n1->next);
1.426 + continue;
1.427 + }
1.428 +#endif
1.429 + lh->num_comp_calls++;
1.430 + if(cf(n1->data,data) == 0)
1.431 + break;
1.432 + ret= &(n1->next);
1.433 + }
1.434 + return(ret);
1.435 + }
1.436 +
1.437 +/* The following hash seems to work very well on normal text strings
1.438 + * no collisions on /usr/dict/words and it distributes on %2^n quite
1.439 + * well, not as good as MD5, but still good.
1.440 + */
1.441 +EXPORT_C unsigned long lh_strhash(const char *c)
1.442 + {
1.443 + unsigned long ret=0;
1.444 + long n;
1.445 + unsigned long v;
1.446 + int r;
1.447 +
1.448 + if ((c == NULL) || (*c == '\0'))
1.449 + return(ret);
1.450 +/*
1.451 + unsigned char b[16];
1.452 + MD5(c,strlen(c),b);
1.453 + return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
1.454 +*/
1.455 +
1.456 + n=0x100;
1.457 + while (*c)
1.458 + {
1.459 + v=n|(*c);
1.460 + n+=0x100;
1.461 + r= (int)((v>>2)^v)&0x0f;
1.462 + ret=(ret<<r)|(ret>>(32-r));
1.463 + ret&=0xFFFFFFFFL;
1.464 + ret^=v*v;
1.465 + c++;
1.466 + }
1.467 + return((ret>>16)^ret);
1.468 + }
1.469 +
1.470 +EXPORT_C unsigned long lh_num_items(const LHASH *lh)
1.471 + {
1.472 + return lh ? lh->num_items : 0;
1.473 + }