diff options
Diffstat (limited to 'crypto/sparse_array.c')
| -rw-r--r-- | crypto/sparse_array.c | 216 |
1 files changed, 216 insertions, 0 deletions
diff --git a/crypto/sparse_array.c b/crypto/sparse_array.c new file mode 100644 index 000000000000..bbbc9cdb3696 --- /dev/null +++ b/crypto/sparse_array.c @@ -0,0 +1,216 @@ +/* + * Copyright 2019-2022 The OpenSSL Project Authors. All Rights Reserved. + * Copyright (c) 2019, Oracle and/or its affiliates. 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 <openssl/crypto.h> +#include <openssl/bn.h> +#include "crypto/sparse_array.h" + +/* + * How many bits are used to index each level in the tree structure? + * This setting determines the number of pointers stored in each node of the + * tree used to represent the sparse array. Having more pointers reduces the + * depth of the tree but potentially wastes more memory. That is, this is a + * direct space versus time tradeoff. + * + * The default is to use four bits which means that the are 16 + * pointers in each tree node. + * + * The library builder is also permitted to define other sizes in the closed + * interval [2, sizeof(ossl_uintmax_t) * 8]. Space use generally scales + * exponentially with the block size, although the implementation only + * creates enough blocks to support the largest used index. The depth is: + * ceil(log_2(largest index) / 2^{block size}) + * E.g. with a block size of 4, and a largest index of 1000, the depth + * will be three. + */ +#ifndef OPENSSL_SA_BLOCK_BITS +# define OPENSSL_SA_BLOCK_BITS 4 +#elif OPENSSL_SA_BLOCK_BITS < 2 || OPENSSL_SA_BLOCK_BITS > (BN_BITS2 - 1) +# error OPENSSL_SA_BLOCK_BITS is out of range +#endif + +/* + * From the number of bits, work out: + * the number of pointers in a tree node; + * a bit mask to quickly extract an index and + * the maximum depth of the tree structure. + */ +#define SA_BLOCK_MAX (1 << OPENSSL_SA_BLOCK_BITS) +#define SA_BLOCK_MASK (SA_BLOCK_MAX - 1) +#define SA_BLOCK_MAX_LEVELS (((int)sizeof(ossl_uintmax_t) * 8 \ + + OPENSSL_SA_BLOCK_BITS - 1) \ + / OPENSSL_SA_BLOCK_BITS) + +struct sparse_array_st { + int levels; + ossl_uintmax_t top; + size_t nelem; + void **nodes; +}; + +OPENSSL_SA *ossl_sa_new(void) +{ + OPENSSL_SA *res = OPENSSL_zalloc(sizeof(*res)); + + return res; +} + +static void sa_doall(const OPENSSL_SA *sa, void (*node)(void **), + void (*leaf)(ossl_uintmax_t, void *, void *), void *arg) +{ + int i[SA_BLOCK_MAX_LEVELS]; + void *nodes[SA_BLOCK_MAX_LEVELS]; + ossl_uintmax_t idx = 0; + int l = 0; + + i[0] = 0; + nodes[0] = sa->nodes; + while (l >= 0) { + const int n = i[l]; + void ** const p = nodes[l]; + + if (n >= SA_BLOCK_MAX) { + if (p != NULL && node != NULL) + (*node)(p); + l--; + idx >>= OPENSSL_SA_BLOCK_BITS; + } else { + i[l] = n + 1; + if (p != NULL && p[n] != NULL) { + idx = (idx & ~SA_BLOCK_MASK) | n; + if (l < sa->levels - 1) { + i[++l] = 0; + nodes[l] = p[n]; + idx <<= OPENSSL_SA_BLOCK_BITS; + } else if (leaf != NULL) { + (*leaf)(idx, p[n], arg); + } + } + } + } +} + +static void sa_free_node(void **p) +{ + OPENSSL_free(p); +} + +static void sa_free_leaf(ossl_uintmax_t n, void *p, void *arg) +{ + OPENSSL_free(p); +} + +void ossl_sa_free(OPENSSL_SA *sa) +{ + if (sa != NULL) { + sa_doall(sa, &sa_free_node, NULL, NULL); + OPENSSL_free(sa); + } +} + +void ossl_sa_free_leaves(OPENSSL_SA *sa) +{ + sa_doall(sa, &sa_free_node, &sa_free_leaf, NULL); + OPENSSL_free(sa); +} + +/* Wrap this in a structure to avoid compiler warnings */ +struct trampoline_st { + void (*func)(ossl_uintmax_t, void *); +}; + +static void trampoline(ossl_uintmax_t n, void *l, void *arg) +{ + ((const struct trampoline_st *)arg)->func(n, l); +} + +void ossl_sa_doall(const OPENSSL_SA *sa, void (*leaf)(ossl_uintmax_t, void *)) +{ + struct trampoline_st tramp; + + tramp.func = leaf; + if (sa != NULL) + sa_doall(sa, NULL, &trampoline, &tramp); +} + +void ossl_sa_doall_arg(const OPENSSL_SA *sa, + void (*leaf)(ossl_uintmax_t, void *, void *), + void *arg) +{ + if (sa != NULL) + sa_doall(sa, NULL, leaf, arg); +} + +size_t ossl_sa_num(const OPENSSL_SA *sa) +{ + return sa == NULL ? 0 : sa->nelem; +} + +void *ossl_sa_get(const OPENSSL_SA *sa, ossl_uintmax_t n) +{ + int level; + void **p, *r = NULL; + + if (sa == NULL || sa->nelem == 0) + return NULL; + + if (n <= sa->top) { + p = sa->nodes; + for (level = sa->levels - 1; p != NULL && level > 0; level--) + p = (void **)p[(n >> (OPENSSL_SA_BLOCK_BITS * level)) + & SA_BLOCK_MASK]; + r = p == NULL ? NULL : p[n & SA_BLOCK_MASK]; + } + return r; +} + +static ossl_inline void **alloc_node(void) +{ + return OPENSSL_zalloc(SA_BLOCK_MAX * sizeof(void *)); +} + +int ossl_sa_set(OPENSSL_SA *sa, ossl_uintmax_t posn, void *val) +{ + int i, level = 1; + ossl_uintmax_t n = posn; + void **p; + + if (sa == NULL) + return 0; + + for (level = 1; level < SA_BLOCK_MAX_LEVELS; level++) + if ((n >>= OPENSSL_SA_BLOCK_BITS) == 0) + break; + + for (;sa->levels < level; sa->levels++) { + p = alloc_node(); + if (p == NULL) + return 0; + p[0] = sa->nodes; + sa->nodes = p; + } + if (sa->top < posn) + sa->top = posn; + + p = sa->nodes; + for (level = sa->levels - 1; level > 0; level--) { + i = (posn >> (OPENSSL_SA_BLOCK_BITS * level)) & SA_BLOCK_MASK; + if (p[i] == NULL && (p[i] = alloc_node()) == NULL) + return 0; + p = p[i]; + } + p += posn & SA_BLOCK_MASK; + if (val == NULL && *p != NULL) + sa->nelem--; + else if (val != NULL && *p == NULL) + sa->nelem++; + *p = val; + return 1; +} |