X-Git-Url: https://git.openssl.org/gitweb/?a=blobdiff_plain;f=crypto%2Fstack%2Fstack.c;h=fc755e36b672ec52e97e5cc071318a85d08b7ccc;hb=3ceab379fbaaf11b2adee0fb2a93c517272ee6c3;hp=31ea16a00c5a897300f3148d6857f8ce246d99dc;hpb=5f32680329648886701f5b5832239eecf0b38390;p=openssl.git diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c index 31ea16a00c..fc755e36b6 100644 --- a/crypto/stack/stack.c +++ b/crypto/stack/stack.c @@ -1,307 +1,408 @@ -/* crypto/stack/stack.c */ -/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) - * All rights reserved. +/* + * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved. * - * This package is an SSL implementation written - * by Eric Young (eay@cryptsoft.com). - * The implementation was written so as to conform with Netscapes SSL. - * - * This library is free for commercial and non-commercial use as long as - * the following conditions are aheared to. The following conditions - * apply to all code found in this distribution, be it the RC4, RSA, - * lhash, DES, etc., code; not just the SSL code. The SSL documentation - * included with this distribution is covered by the same copyright terms - * except that the holder is Tim Hudson (tjh@cryptsoft.com). - * - * Copyright remains Eric Young's, and as such any Copyright notices in - * the code are not to be removed. - * If this package is used in a product, Eric Young should be given attribution - * as the author of the parts of the library used. - * This can be in the form of a textual message at program startup or - * in documentation (online or textual) provided with the package. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * "This product includes cryptographic software written by - * Eric Young (eay@cryptsoft.com)" - * The word 'cryptographic' can be left out if the rouines from the library - * being used are not cryptographic related :-). - * 4. If you include any Windows specific code (or a derivative thereof) from - * the apps directory (application code) you must include an acknowledgement: - * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" - * - * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * The licence and distribution terms for any publically available version or - * derivative of this code cannot be changed. i.e. this code cannot simply be - * copied and put under another distribution licence - * [including the GNU Public Licence.] + * Licensed under the OpenSSL license (the "License"). You may not use + * this file except in compliance with the License. You can obtain a copy + * in the file LICENSE in the source distribution or at + * https://www.openssl.org/source/license.html */ -/* Code for stacks - * Author - Eric Young v 1.0 - * 1.2 eay 12-Mar-97 - Modified sk_find so that it _DOES_ return the - * lowest index for the seached item. +#include +#include "internal/cryptlib.h" +#include "internal/numbers.h" +#include +#include +#include +#include /* For ossl_inline */ + +/* + * The initial number of nodes in the array. + */ +static const int min_nodes = 4; +static const int max_nodes = SIZE_MAX / sizeof(void *) < INT_MAX + ? (int)(SIZE_MAX / sizeof(void *)) + : INT_MAX; + +struct stack_st { + int num; + const void **data; + int sorted; + int num_alloc; + OPENSSL_sk_compfunc comp; +}; + +OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc c) +{ + OPENSSL_sk_compfunc old = sk->comp; + + if (sk->comp != c) + sk->sorted = 0; + sk->comp = c; + + return old; +} + +OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk) +{ + OPENSSL_STACK *ret; + + if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) + return NULL; + + /* direct structure assignment */ + *ret = *sk; + + if (sk->num == 0) { + /* postpone |ret->data| allocation */ + ret->data = NULL; + ret->num_alloc = 0; + return ret; + } + /* duplicate |sk->data| content */ + if ((ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc)) == NULL) + goto err; + memcpy(ret->data, sk->data, sizeof(void *) * sk->num); + return ret; + err: + OPENSSL_sk_free(ret); + return NULL; +} + +OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk, + OPENSSL_sk_copyfunc copy_func, + OPENSSL_sk_freefunc free_func) +{ + OPENSSL_STACK *ret; + int i; + + if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) + return NULL; + + /* direct structure assignment */ + *ret = *sk; + + if (sk->num == 0) { + /* postpone |ret| data allocation */ + ret->data = NULL; + ret->num_alloc = 0; + return ret; + } + + ret->num_alloc = sk->num > min_nodes ? sk->num : min_nodes; + ret->data = OPENSSL_zalloc(sizeof(*ret->data) * ret->num_alloc); + if (ret->data == NULL) { + OPENSSL_free(ret); + return NULL; + } + + for (i = 0; i < ret->num; ++i) { + if (sk->data[i] == NULL) + continue; + if ((ret->data[i] = copy_func(sk->data[i])) == NULL) { + while (--i >= 0) + if (ret->data[i] != NULL) + free_func((void *)ret->data[i]); + OPENSSL_sk_free(ret); + return NULL; + } + } + return ret; +} + +OPENSSL_STACK *OPENSSL_sk_new_null(void) +{ + return OPENSSL_sk_new_reserve(NULL, 0); +} + +OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c) +{ + return OPENSSL_sk_new_reserve(c, 0); +} + +/* + * Calculate the array growth based on the target size. * - * 1.1 eay - Take from netdb and added to SSLeay + * The growth fraction is a rational number and is defined by a numerator + * and a denominator. According to Andrew Koenig in his paper "Why Are + * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less + * than the golden ratio (1.618...). * - * 1.0 eay - First version 29/07/92 + * We use 3/2 = 1.5 for simplicity of calculation and overflow checking. + * Another option 8/5 = 1.6 allows for slightly faster growth, although safe + * computation is more difficult. + * + * The limit to avoid overflow is spot on. The modulo three correction term + * ensures that the limit is the largest number than can be expanded by the + * growth factor without exceeding the hard limit. + * + * Do not call it with |current| lower than 2, or it will infinitely loop. */ -#include -#include "cryptlib.h" -#include "stack.h" +static ossl_inline int compute_growth(int target, int current) +{ + const int limit = (max_nodes / 3) * 2 + (max_nodes % 3 ? 1 : 0); -#undef MIN_NODES -#define MIN_NODES 4 + while (current < target) { + /* Check to see if we're at the hard limit */ + if (current >= max_nodes) + return 0; -char *STACK_version="Stack part of SSLeay/OpenSSL 0.9.1c 23-Dec-1998"; + /* Expand the size by a factor of 3/2 if it is within range */ + current = current < limit ? current + current / 2 : max_nodes; + } + return current; +} -#ifndef NOPROTO -#define FP_ICC (int (*)(const void *,const void *)) -#else -#define FP_ICC -#endif +/* internal STACK storage allocation */ +static int sk_reserve(OPENSSL_STACK *st, int n, int exact) +{ + const void **tmpdata; + int num_alloc; -#include + /* Check to see the reservation isn't exceeding the hard limit */ + if (n > max_nodes - st->num) + return 0; + + /* Figure out the new size */ + num_alloc = st->num + n; + if (num_alloc < min_nodes) + num_alloc = min_nodes; + + /* If |st->data| allocation was postponed */ + if (st->data == NULL) { + /* + * At this point, |st->num_alloc| and |st->num| are 0; + * so |num_alloc| value is |n| or |min_nodes| if greater than |n|. + */ + st->data = OPENSSL_zalloc(sizeof(void *) * num_alloc); + if (st->data == NULL) + return 0; + st->num_alloc = num_alloc; + return 1; + } + + if (!exact) { + if (num_alloc <= st->num_alloc) + return 1; + num_alloc = compute_growth(num_alloc, st->num_alloc); + if (num_alloc == 0) + return 0; + } else if (num_alloc == st->num_alloc) { + return 1; + } + + tmpdata = OPENSSL_realloc((void *)st->data, sizeof(void *) * num_alloc); + if (tmpdata == NULL) + return 0; + + st->data = tmpdata; + st->num_alloc = num_alloc; + return 1; +} + +OPENSSL_STACK *OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c, int n) +{ + OPENSSL_STACK *st = OPENSSL_zalloc(sizeof(OPENSSL_STACK)); + + if (st == NULL) + return NULL; + + st->comp = c; + + if (n <= 0) + return st; + + if (!sk_reserve(st, n, 1)) { + OPENSSL_sk_free(st); + return NULL; + } + + return st; +} + +int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n) +{ + if (st == NULL) + return 0; + + if (n < 0) + return 1; + return sk_reserve(st, n, 1); +} + +int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc) +{ + if (st == NULL || st->num == max_nodes) + return 0; + + if (!sk_reserve(st, 1, 0)) + return 0; + + if ((loc >= st->num) || (loc < 0)) { + st->data[st->num] = data; + } else { + memmove(&st->data[loc + 1], &st->data[loc], + sizeof(st->data[0]) * (st->num - loc)); + st->data[loc] = data; + } + st->num++; + st->sorted = 0; + return st->num; +} + +static ossl_inline void *internal_delete(OPENSSL_STACK *st, int loc) +{ + const void *ret = st->data[loc]; + + if (loc != st->num - 1) + memmove(&st->data[loc], &st->data[loc + 1], + sizeof(st->data[0]) * (st->num - loc - 1)); + st->num--; + + return (void *)ret; +} + +void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p) +{ + int i; + + for (i = 0; i < st->num; i++) + if (st->data[i] == p) + return internal_delete(st, i); + return NULL; +} + +void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc) +{ + if (st == NULL || loc < 0 || loc >= st->num) + return NULL; + + return internal_delete(st, loc); +} + +static int internal_find(OPENSSL_STACK *st, const void *data, + int ret_val_options) +{ + const void *r; + int i; + + if (st == NULL || st->num == 0) + return -1; + + if (st->comp == NULL) { + for (i = 0; i < st->num; i++) + if (st->data[i] == data) + return i; + return -1; + } + + if (!st->sorted) { + if (st->num > 1) + qsort(st->data, st->num, sizeof(void *), st->comp); + st->sorted = 1; /* empty or single-element stack is considered sorted */ + } + if (data == NULL) + return -1; + r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp, + ret_val_options); + + return r == NULL ? -1 : (int)((const void **)r - st->data); +} + +int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data) +{ + return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH); +} + +int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data) +{ + return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH); +} + +int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data) +{ + if (st == NULL) + return -1; + return OPENSSL_sk_insert(st, data, st->num); +} + +int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data) +{ + return OPENSSL_sk_insert(st, data, 0); +} + +void *OPENSSL_sk_shift(OPENSSL_STACK *st) +{ + if (st == NULL || st->num == 0) + return NULL; + return internal_delete(st, 0); +} + +void *OPENSSL_sk_pop(OPENSSL_STACK *st) +{ + if (st == NULL || st->num == 0) + return NULL; + return internal_delete(st, st->num - 1); +} + +void OPENSSL_sk_zero(OPENSSL_STACK *st) +{ + if (st == NULL || st->num == 0) + return; + memset(st->data, 0, sizeof(*st->data) * st->num); + st->num = 0; +} + +void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func) +{ + int i; + + if (st == NULL) + return; + for (i = 0; i < st->num; i++) + if (st->data[i] != NULL) + func((char *)st->data[i]); + OPENSSL_sk_free(st); +} + +void OPENSSL_sk_free(OPENSSL_STACK *st) +{ + if (st == NULL) + return; + OPENSSL_free(st->data); + OPENSSL_free(st); +} + +int OPENSSL_sk_num(const OPENSSL_STACK *st) +{ + return st == NULL ? -1 : st->num; +} + +void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i) +{ + if (st == NULL || i < 0 || i >= st->num) + return NULL; + return (void *)st->data[i]; +} + +void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data) +{ + if (st == NULL || i < 0 || i >= st->num) + return NULL; + st->data[i] = data; + st->sorted = 0; + return (void *)st->data[i]; +} -void sk_set_cmp_func(sk,c) -STACK *sk; -int (*c)(); - { - if (sk->comp != c) - sk->sorted=0; - sk->comp=c; - } - -STACK *sk_dup(sk) -STACK *sk; - { - STACK *ret; - char **s; - - if ((ret=sk_new(sk->comp)) == NULL) goto err; - s=(char **)Realloc((char *)ret->data, - (unsigned int)sizeof(char *)*sk->num_alloc); - if (s == NULL) goto err; - ret->data=s; - - ret->num=sk->num; - memcpy(ret->data,sk->data,sizeof(char *)*sk->num); - ret->sorted=sk->sorted; - ret->num_alloc=sk->num_alloc; - ret->comp=sk->comp; - return(ret); -err: - return(NULL); - } - -STACK *sk_new(c) -int (*c)(); - { - STACK *ret; - int i; - - if ((ret=(STACK *)Malloc(sizeof(STACK))) == NULL) - goto err0; - if ((ret->data=(char **)Malloc(sizeof(char *)*MIN_NODES)) == NULL) - goto err1; - for (i=0; idata[i]=NULL; - ret->comp=c; - ret->num_alloc=MIN_NODES; - ret->num=0; - ret->sorted=0; - return(ret); -err1: - Free((char *)ret); -err0: - return(NULL); - } - -int sk_insert(st,data,loc) -STACK *st; -char *data; -int loc; - { - char **s; - - if (st->num_alloc <= st->num+1) - { - s=(char **)Realloc((char *)st->data, - (unsigned int)sizeof(char *)*st->num_alloc*2); - if (s == NULL) - return(0); - st->data=s; - st->num_alloc*=2; - } - if ((loc >= (int)st->num) || (loc < 0)) - st->data[st->num]=data; - else - { - int i; - char **f,**t; - - f=(char **)st->data; - t=(char **)&(st->data[1]); - for (i=st->num; i>loc; i--) - t[i]=f[i]; - -#ifdef undef /* no memmove on sunos :-( */ - memmove( (char *)&(st->data[loc+1]), - (char *)&(st->data[loc]), - sizeof(char *)*(st->num-loc)); -#endif - st->data[loc]=data; - } - st->num++; - st->sorted=0; - return(st->num); - } - -char *sk_delete_ptr(st,p) -STACK *st; -char *p; - { - int i; - - for (i=0; inum; i++) - if (st->data[i] == p) - return(sk_delete(st,i)); - return(NULL); - } - -char *sk_delete(st,loc) -STACK *st; -int loc; - { - char *ret; - int i,j; - - if ((st->num == 0) || (loc < 0) || (loc >= st->num)) return(NULL); - - ret=st->data[loc]; - if (loc != st->num-1) - { - j=st->num-1; - for (i=loc; idata[i]=st->data[i+1]; - /* In theory memcpy is not safe for this - * memcpy( &(st->data[loc]), - * &(st->data[loc+1]), - * sizeof(char *)*(st->num-loc-1)); - */ - } - st->num--; - return(ret); - } - -int sk_find(st,data) -STACK *st; -char *data; - { - char **r; - int i; - int (*comp_func)(); - - if (st->comp == NULL) - { - for (i=0; inum; i++) - if (st->data[i] == data) - return(i); - return(-1); - } - comp_func=(int (*)())st->comp; - if (!st->sorted) - { - qsort((char *)st->data,st->num,sizeof(char *),FP_ICC comp_func); - st->sorted=1; - } - if (data == NULL) return(-1); - r=(char **)bsearch(&data,(char *)st->data, - st->num,sizeof(char *),FP_ICC comp_func); - if (r == NULL) return(-1); - i=(int)(r-st->data); - for ( ; i>0; i--) - if ((*st->comp)(&(st->data[i-1]),&data) < 0) - break; - return(i); - } - -int sk_push(st,data) -STACK *st; -char *data; - { - return(sk_insert(st,data,st->num)); - } - -int sk_unshift(st,data) -STACK *st; -char *data; - { - return(sk_insert(st,data,0)); - } - -char *sk_shift(st) -STACK *st; - { - if (st == NULL) return(NULL); - if (st->num <= 0) return(NULL); - return(sk_delete(st,0)); - } - -char *sk_pop(st) -STACK *st; - { - if (st == NULL) return(NULL); - if (st->num <= 0) return(NULL); - return(sk_delete(st,st->num-1)); - } - -void sk_zero(st) -STACK *st; - { - if (st == NULL) return; - if (st->num <= 0) return; - memset((char *)st->data,0,sizeof(st->data)*st->num); - st->num=0; - } - -void sk_pop_free(st,func) -STACK *st; -void (*func)(); - { - int i; - - if (st == NULL) return; - for (i=0; inum; i++) - if (st->data[i] != NULL) - func(st->data[i]); - sk_free(st); - } - -void sk_free(st) -STACK *st; - { - if (st == NULL) return; - if (st->data != NULL) Free((char *)st->data); - Free((char *)st); - } +void OPENSSL_sk_sort(OPENSSL_STACK *st) +{ + if (st != NULL && !st->sorted && st->comp != NULL) { + if (st->num > 1) + qsort(st->data, st->num, sizeof(void *), st->comp); + st->sorted = 1; /* empty or single-element stack is considered sorted */ + } +} +int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st) +{ + return st == NULL ? 1 : st->sorted; +}