diff options
-rw-r--r-- | crypto/bsearch.c | 44 | ||||
-rw-r--r-- | crypto/build.info | 4 | ||||
-rw-r--r-- | crypto/objects/obj_dat.c | 38 | ||||
-rw-r--r-- | crypto/stack/stack.c | 9 | ||||
-rw-r--r-- | include/internal/cryptlib.h | 11 |
5 files changed, 70 insertions, 36 deletions
diff --git a/crypto/bsearch.c b/crypto/bsearch.c new file mode 100644 index 0000000000..f812c4f8ef --- /dev/null +++ b/crypto/bsearch.c @@ -0,0 +1,44 @@ +/* + * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved. + * + * Licensed under the Apache License 2.0 (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 + */ + +#include <stddef.h> +#include "internal/cryptlib.h" + +const void *ossl_bsearch(const void *key, const void *base, int num, + int size, int (*cmp) (const void *, const void *), + int flags) +{ + const char *base_ = base; + int l, h, i = 0, c = 0; + const char *p = NULL; + + if (num == 0) + return NULL; + l = 0; + h = num; + while (l < h) { + i = (l + h) / 2; + p = &(base_[i * size]); + c = (*cmp) (key, p); + if (c < 0) + h = i; + else if (c > 0) + l = i + 1; + else + break; + } + if (c != 0 && !(flags & OSSL_BSEARCH_VALUE_ON_NOMATCH)) + p = NULL; + else if (c == 0 && (flags & OSSL_BSEARCH_FIRST_VALUE_ON_MATCH)) { + while (i > 0 && (*cmp) (key, &(base_[(i - 1) * size])) == 0) + i--; + p = &(base_[i * size]); + } + return p; +} diff --git a/crypto/build.info b/crypto/build.info index 30dcf8c91e..fa99d61bd6 100644 --- a/crypto/build.info +++ b/crypto/build.info @@ -18,12 +18,12 @@ SOURCE[../libcrypto]=\ ebcdic.c uid.c o_time.c o_str.c o_dir.c o_fopen.c ctype.c \ threads_pthread.c threads_win.c threads_none.c getenv.c \ o_init.c o_fips.c mem_sec.c init.c context.c sparse_array.c \ - trace.c provider.c params.c \ + trace.c provider.c params.c bsearch.c \ {- $target{cpuid_asm_src} -} {- $target{uplink_aux_src} -} # FIPS module SOURCE[../providers/fips]=\ - cryptlib.c mem.c mem_clr.c params.c + cryptlib.c mem.c mem_clr.c params.c bsearch.c DEPEND[cversion.o]=buildinf.h diff --git a/crypto/objects/obj_dat.c b/crypto/objects/obj_dat.c index f374d19fc7..ec9e131337 100644 --- a/crypto/objects/obj_dat.c +++ b/crypto/objects/obj_dat.c @@ -585,52 +585,32 @@ const void *OBJ_bsearch_(const void *key, const void *base, int num, int size, return OBJ_bsearch_ex_(key, base, num, size, cmp, 0); } -const void *OBJ_bsearch_ex_(const void *key, const void *base_, int num, +const void *OBJ_bsearch_ex_(const void *key, const void *base, int num, int size, int (*cmp) (const void *, const void *), int flags) { - const char *base = base_; - int l, h, i = 0, c = 0; - const char *p = NULL; + const char *p = ossl_bsearch(key, base, num, size, cmp, flags); - if (num == 0) - return NULL; - l = 0; - h = num; - while (l < h) { - i = (l + h) / 2; - p = &(base[i * size]); - c = (*cmp) (key, p); - if (c < 0) - h = i; - else if (c > 0) - l = i + 1; - else - break; - } #ifdef CHARSET_EBCDIC /* * THIS IS A KLUDGE - Because the *_obj is sorted in ASCII order, and I * don't have perl (yet), we revert to a *LINEAR* search when the object * wasn't found in the binary search. */ - if (c != 0) { + if (p == NULL) { + const char *base_ = base; + int l, h, i = 0, c = 0; + for (i = 0; i < num; ++i) { - p = &(base[i * size]); + p = &(base_[i * size]); c = (*cmp) (key, p); - if (c == 0 || (c < 0 && (flags & OBJ_BSEARCH_VALUE_ON_NOMATCH))) + if (c == 0 + || (c < 0 && (flags & OBJ_BSEARCH_VALUE_ON_NOMATCH))) return p; } } #endif - if (c != 0 && !(flags & OBJ_BSEARCH_VALUE_ON_NOMATCH)) - p = NULL; - else if (c == 0 && (flags & OBJ_BSEARCH_FIRST_VALUE_ON_MATCH)) { - while (i > 0 && (*cmp) (key, &(base[(i - 1) * size])) == 0) - i--; - p = &(base[i * size]); - } return p; } diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c index 2f0ed64232..450a4e1a0e 100644 --- a/crypto/stack/stack.c +++ b/crypto/stack/stack.c @@ -11,7 +11,6 @@ #include "internal/cryptlib.h" #include "internal/numbers.h" #include <openssl/stack.h> -#include <openssl/objects.h> #include <errno.h> #include <openssl/e_os2.h> /* For ossl_inline */ @@ -307,20 +306,20 @@ static int internal_find(OPENSSL_STACK *st, const void *data, } if (data == NULL) return -1; - r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp, - ret_val_options); + r = ossl_bsearch(&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); + return internal_find(st, data, OSSL_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); + return internal_find(st, data, OSSL_BSEARCH_VALUE_ON_NOMATCH); } int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data) diff --git a/include/internal/cryptlib.h b/include/internal/cryptlib.h index df23f578e3..46b5d344a4 100644 --- a/include/internal/cryptlib.h +++ b/include/internal/cryptlib.h @@ -174,4 +174,15 @@ int crypto_get_ex_new_index_ex(OPENSSL_CTX *ctx, int class_index, CRYPTO_EX_dup *dup_func, CRYPTO_EX_free *free_func); int crypto_free_ex_index_ex(OPENSSL_CTX *ctx, int class_index, int idx); + +/* Function for simple binary search */ + +/* Flags */ +# define OSSL_BSEARCH_VALUE_ON_NOMATCH 0x01 +# define OSSL_BSEARCH_FIRST_VALUE_ON_MATCH 0x02 + +const void *ossl_bsearch(const void *key, const void *base, int num, + int size, int (*cmp) (const void *, const void *), + int flags); + #endif |