Dr. David von Oheimb 7c310e872e libcrypto refactoring: introduce and use ossl_asn1_string_set_bits_left() 1 rok temu
..
aes 65523758e5 Fix reported performance degradation on aarch64 1 rok temu
aria 36c269c302 Change loops conditions to make zero loop risk more obvious. 2 lat temu
asn1 7c310e872e libcrypto refactoring: introduce and use ossl_asn1_string_set_bits_left() 1 rok temu
async fecb3aae22 Update copyright year 2 lat temu
bf 9968c77539 Rename x86-32 assembly files from .s to .S. 2 lat temu
bio 358103b4a6 Coverity 1506566: unchecked return value 1 rok temu
bn 7fe7cc57af Fix bn_gcd code to check return value when calling BN_one() 1 rok temu
buffer 38fc02a708 Update copyright year 3 lat temu
camellia 9968c77539 Rename x86-32 assembly files from .s to .S. 2 lat temu
cast 9968c77539 Rename x86-32 assembly files from .s to .S. 2 lat temu
chacha ca6286c382 Add ROTATE inline RISC-V zbb/zbkb asm for chacha 1 rok temu
cmac 8d9fec1781 Fix the incorrect checks of EVP_CIPHER_CTX_set_key_length 2 lat temu
cmp 7c310e872e libcrypto refactoring: introduce and use ossl_asn1_string_set_bits_left() 1 rok temu
cms 7c310e872e libcrypto refactoring: introduce and use ossl_asn1_string_set_bits_left() 1 rok temu
comp 73a815defe Fix coverity 1493364 & 1493375: unchecked return value 2 lat temu
conf d840f07bcd Avoid crashing if CONF_modules_unload() is called after OPENSSL_cleanup() 1 rok temu
crmf de56f726e1 crmf_lib.c: Make sure Ed signature for POPO is called without digest 2 lat temu
ct 163bf682fd CTLOG_new_ex: Fix copy&paste error when setting propq 2 lat temu
des 9968c77539 Rename x86-32 assembly files from .s to .S. 2 lat temu
dh ddb13b283b Use as small dh key size as possible to support the security 1 rok temu
dsa 3ee2611677 Coverity: fix 1506297: negative returns 1 rok temu
dso fecb3aae22 Update copyright year 2 lat temu
ec 7c310e872e libcrypto refactoring: introduce and use ossl_asn1_string_set_bits_left() 1 rok temu
encode_decode 4fa5ed5ce5 Check return value of ossl_parse_property() 2 lat temu
engine 5317b6ee1f Add deprecation macro for 3.1 and deprecate OPENSSL_LH_stats 2 lat temu
err d2399d8cd2 RSA keygen update: Raise an error if no prime candidate q is found. 2 lat temu
ess b93f6c2db9 err: rename err_load_xxx_strings_int functions 3 lat temu
evp ee8db8c5fb evp: make all _is_a functions accept and handle a NULL argument 1 rok temu
ffc 5f311b10ab ossl_ffc_params_copy: Copy the keylength too 1 rok temu
hmac 21dfdbef49 Adapt other parts of the source to the changed EVP_Q_digest() and EVP_Q_mac() 3 lat temu
http 8c65e1f719 http_client.c: 2nd fix for calculation of Content-Length in set1_content() 1 rok temu
idea 3c2bdd7df9 Update copyright year 3 lat temu
kdf 905b097fd5 Deprecate ERR_load_KDF_strings() 4 lat temu
lhash 5317b6ee1f Add deprecation macro for 3.1 and deprecate OPENSSL_LH_stats 2 lat temu
md2 33388b44b6 Update copyright year 4 lat temu
md4 33388b44b6 Update copyright year 4 lat temu
md5 9968c77539 Rename x86-32 assembly files from .s to .S. 2 lat temu
mdc2 33388b44b6 Update copyright year 4 lat temu
modes 36c269c302 Change loops conditions to make zero loop risk more obvious. 2 lat temu
objects a0ff8e413e add a check for the return of OBJ_new_nid() 1 rok temu
ocsp fecb3aae22 Update copyright year 2 lat temu
pem fecb3aae22 Update copyright year 2 lat temu
perlasm 272138795f x86asm: Generate endbr32 based on __CET__. 2 lat temu
pkcs12 af801ec892 Fix memleak in PKCS12_pbe_crypt_ex() 1 rok temu
pkcs7 30adf6d209 Revert unnecessary PKCS7_verify() performance optimization 2 lat temu
poly1305 db24ed5430 Generate the preprocessed .s files for chacha and poly 1305 on ia64 2 lat temu
property 5ad3e76c23 put_str: Use memcpy instead of strncpy 2 lat temu
rand 9574842e90 Pre-declare all core dispatch table functions, and fix the internal ones 1 rok temu
rc2 aff636a489 Update copyright year 3 lat temu
rc4 9968c77539 Rename x86-32 assembly files from .s to .S. 2 lat temu
rc5 9968c77539 Rename x86-32 assembly files from .s to .S. 2 lat temu
ripemd 9968c77539 Rename x86-32 assembly files from .s to .S. 2 lat temu
rsa 28adea9597 Fix memory leak in ossl_rsa_fromdata. 1 rok temu
seed 38fc02a708 Update copyright year 3 lat temu
sha a8b238f0e4 Fix SHA, SHAKE, and KECCAK ASM flag passing 1 rok temu
siphash fecb3aae22 Update copyright year 2 lat temu
sm2 e257d3e76f Remove duplicated #include headers 2 lat temu
sm3 eea820f3e2 Add ROTATE inline asm support for SM3 2 lat temu
sm4 fecb3aae22 Update copyright year 2 lat temu
srp 1287dabd0b fix some code with obvious wrong coding style 2 lat temu
stack 7cc5738a56 Fix Coverity 1493746: constant expression result 2 lat temu
store 4cfcc7e121 store_result: Add fallback for fetching the keymgmt from the provider of the store 1 rok temu
ts fecb3aae22 Update copyright year 2 lat temu
txt_db 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 lat temu
ui 1aef2c10f1 Fix the check of UI_method_set_ex_data 2 lat temu
whrlpool 9968c77539 Rename x86-32 assembly files from .s to .S. 2 lat temu
x509 7c310e872e libcrypto refactoring: introduce and use ossl_asn1_string_set_bits_left() 1 rok temu
LPdir_nyi.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 lat temu
LPdir_unix.c fecb3aae22 Update copyright year 2 lat temu
LPdir_vms.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 lat temu
LPdir_win.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 lat temu
LPdir_win32.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 lat temu
LPdir_wince.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 lat temu
README-sparse_array.md 1dc1ea182b Fix many MarkDown issues in {NOTES*,README*,HACKING,LICENSE}.md files 4 lat temu
alphacpuid.pl 33388b44b6 Update copyright year 4 lat temu
arm64cpuid.pl fecb3aae22 Update copyright year 2 lat temu
arm_arch.h 9224a407f9 Apply the AES-GCM unroll8 optimization patch to Neoverse N2 2 lat temu
armcap.c 9224a407f9 Apply the AES-GCM unroll8 optimization patch to Neoverse N2 2 lat temu
armv4cpuid.pl 33388b44b6 Update copyright year 4 lat temu
asn1_dsa.c 3c2bdd7df9 Update copyright year 3 lat temu
bsearch.c 5c3f1e34b5 ossl_bsearch(): New generic internal binary search utility function 5 lat temu
build.info 5067c18910 Add sparse array to libssl 1 rok temu
c64xpluscpuid.pl 33388b44b6 Update copyright year 4 lat temu
context.c fecb3aae22 Update copyright year 2 lat temu
core_algorithm.c 10937d5867 Refactor method construction pre- and post-condition 2 lat temu
core_fetch.c 4b1b629725 Always try to construct methods as new provider might be added 2 lat temu
core_namemap.c 5317b6ee1f Add deprecation macro for 3.1 and deprecate OPENSSL_LH_stats 2 lat temu
cpt_err.c 826da1451b err: add additional errors 2 lat temu
cpuid.c fecb3aae22 Update copyright year 2 lat temu
cryptlib.c fecb3aae22 Update copyright year 2 lat temu
ctype.c 286053fc8f tolower: refine the tolower code to avoid a memory access 2 lat temu
cversion.c 26b7cc0d20 Cleanup include/openssl/opensslv.h.in 4 lat temu
der_writer.c 59196250cb der_writer: Use uint32_t instead of long. 2 lat temu
dllmain.c fecb3aae22 Update copyright year 2 lat temu
ebcdic.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 lat temu
ex_data.c a16d21744d Add the ability for ex_data to have a priority 3 lat temu
getenv.c fecb3aae22 Update copyright year 2 lat temu
ia64cpuid.S 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 lat temu
info.c fecb3aae22 Update copyright year 2 lat temu
init.c e9a806b2c2 Avoid reusing the init_lock for a different purpose 2 lat temu
initthread.c fecb3aae22 Update copyright year 2 lat temu
mem.c fecb3aae22 Update copyright year 2 lat temu
mem_clr.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 lat temu
mem_sec.c fecb3aae22 Update copyright year 2 lat temu
mips_arch.h ae4186b004 Fix header file include guard names 4 lat temu
o_dir.c fecb3aae22 Update copyright year 2 lat temu
o_fopen.c fecb3aae22 Update copyright year 2 lat temu
o_init.c fecb3aae22 Update copyright year 2 lat temu
o_str.c fb4cdca053 strcasecmp: implement strcasecmp and strncasecmp 2 lat temu
o_time.c 8020d79b40 Update copyright year 3 lat temu
packet.c 416d0a638c QUIC wire format support 2 lat temu
param_build.c fecb3aae22 Update copyright year 2 lat temu
param_build_set.c fecb3aae22 Update copyright year 2 lat temu
params.c fecb3aae22 Update copyright year 2 lat temu
params_dup.c fecb3aae22 Update copyright year 2 lat temu
params_from_text.c 946bc0e3ec Allow sign extension in OSSL_PARAM_allocate_from_text() 2 lat temu
pariscid.pl 33388b44b6 Update copyright year 4 lat temu
passphrase.c fecb3aae22 Update copyright year 2 lat temu
ppccap.c fecb3aae22 Update copyright year 2 lat temu
ppccpuid.pl fecb3aae22 Update copyright year 2 lat temu
provider.c 1e8ed3e596 Correctly activate the provider in OSSL_PROVIDER_try_load 2 lat temu
provider_child.c 4da7663b02 For child libctx / provider, don't count self-references in parent 2 lat temu
provider_conf.c fecb3aae22 Update copyright year 2 lat temu
provider_core.c f80910390c Coverity 1503321 & 1503327: dereference after null check 1 rok temu
provider_local.h b7248964a4 make struct provider_info_st a full type 3 lat temu
provider_predefined.c b7248964a4 make struct provider_info_st a full type 3 lat temu
punycode.c af16097feb Move more general parts of internal/cryptlib.h to new internal/common.h 2 lat temu
quic_vlint.c 416d0a638c QUIC wire format support 2 lat temu
riscv64cpuid.pl 360f6dcc5a Add basic RISC-V cpuid and OPENSSL_riscvcap 2 lat temu
riscvcap.c 360f6dcc5a Add basic RISC-V cpuid and OPENSSL_riscvcap 2 lat temu
s390x_arch.h fecb3aae22 Update copyright year 2 lat temu
s390xcap.c 42f111ad41 s390: Add new machine generation 2 lat temu
s390xcpuid.pl 33388b44b6 Update copyright year 4 lat temu
self_test_core.c fecb3aae22 Update copyright year 2 lat temu
sparccpuid.S 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 lat temu
sparcv9cap.c 52f7e44ec8 Split bignum code out of the sparcv9cap.c 2 lat temu
sparse_array.c fecb3aae22 Update copyright year 2 lat temu
threads_lib.c c739222b5a Fix no-threads 3 lat temu
threads_none.c 3c2bdd7df9 Update copyright year 3 lat temu
threads_pthread.c fecb3aae22 Update copyright year 2 lat temu
threads_win.c eeb612021e Explicitly #include <synchapi.h> is unnecessary 2 lat temu
trace.c e8fdb06035 http_client.c: Dump response on error when tracing is enabled 2 lat temu
uid.c 3a1fa0116a Openssl fails to compile on Debian with kfreebsd kernels 2 lat temu
vms_rms.h 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 5 lat temu
x86_64cpuid.pl 3c2bdd7df9 Update copyright year 3 lat temu
x86cpuid.pl 33388b44b6 Update copyright year 4 lat temu

README-sparse_array.md

Sparse Arrays

The sparse_array.c file contains an implementation of a sparse array that attempts to be both space and time efficient.

The sparse array is represented using a tree structure. Each node in the tree contains a block of pointers to either the user supplied leaf values or to another node.

There are a number of parameters used to define the block size:

OPENSSL_SA_BLOCK_BITS   Specifies the number of bits covered by each block
SA_BLOCK_MAX            Specifies the number of pointers in each block
SA_BLOCK_MASK           Specifies a bit mask to perform modulo block size
SA_BLOCK_MAX_LEVELS     Indicates the maximum possible height of the tree

These constants are inter-related:

SA_BLOCK_MAX        = 2 ^ OPENSSL_SA_BLOCK_BITS
SA_BLOCK_MASK       = SA_BLOCK_MAX - 1
SA_BLOCK_MAX_LEVELS = number of bits in size_t divided by
                      OPENSSL_SA_BLOCK_BITS rounded up to the next multiple
                      of OPENSSL_SA_BLOCK_BITS

OPENSSL_SA_BLOCK_BITS can be defined at compile time and this overrides the built in setting.

As a space and performance optimisation, the height of the tree is usually less than the maximum possible height. Only sufficient height is allocated to accommodate the largest index added to the data structure.

The largest index used to add a value to the array determines the tree height:

    +----------------------+---------------------+
    | Largest Added Index  |   Height of Tree    |
    +----------------------+---------------------+
    | SA_BLOCK_MAX     - 1 |          1          |
    | SA_BLOCK_MAX ^ 2 - 1 |          2          |
    | SA_BLOCK_MAX ^ 3 - 1 |          3          |
    | ...                  |          ...        |
    | size_t max           | SA_BLOCK_MAX_LEVELS |
    +----------------------+---------------------+

The tree height is dynamically increased as needed based on additions.

An empty tree is represented by a NULL root pointer. Inserting a value at index 0 results in the allocation of a top level node full of null pointers except for the single pointer to the user's data (N = SA_BLOCK_MAX for brevity):

    +----+
    |Root|
    |Node|
    +-+--+
      |
      |
      |
      v
    +-+-+---+---+---+---+
    | 0 | 1 | 2 |...|N-1|
    |   |nil|nil|...|nil|
    +-+-+---+---+---+---+
      |
      |
      |
      v
    +-+--+
    |User|
    |Data|
    +----+
Index 0

Inserting at element 2N+1 creates a new root node and pushes down the old root node. It then creates a second second level node to hold the pointer to the user's new data:

    +----+
    |Root|
    |Node|
    +-+--+
      |
      |
      |
      v
    +-+-+---+---+---+---+
    | 0 | 1 | 2 |...|N-1|
    |   |nil|   |...|nil|
    +-+-+---+-+-+---+---+
      |       |
      |       +------------------+
      |                          |
      v                          v
    +-+-+---+---+---+---+      +-+-+---+---+---+---+
    | 0 | 1 | 2 |...|N-1|      | 0 | 1 | 2 |...|N-1|
    |nil|   |nil|...|nil|      |nil|   |nil|...|nil|
    +-+-+---+---+---+---+      +---+-+-+---+---+---+
      |                              |
      |                              |
      |                              |
      v                              v
    +-+--+                         +-+--+
    |User|                         |User|
    |Data|                         |Data|
    +----+                         +----+
Index 0                       Index 2N+1

The nodes themselves are allocated in a sparse manner. Only nodes which exist along a path from the root of the tree to an added leaf will be allocated. The complexity is hidden and nodes are allocated on an as needed basis. Because the data is expected to be sparse this doesn't result in a large waste of space.

Values can be removed from the sparse array by setting their index position to NULL. The data structure does not attempt to reclaim nodes or reduce the height of the tree on removal. For example, now setting index 0 to NULL would result in:

    +----+
    |Root|
    |Node|
    +-+--+
      |
      |
      |
      v
    +-+-+---+---+---+---+
    | 0 | 1 | 2 |...|N-1|
    |   |nil|   |...|nil|
    +-+-+---+-+-+---+---+
      |       |
      |       +------------------+
      |                          |
      v                          v
    +-+-+---+---+---+---+      +-+-+---+---+---+---+
    | 0 | 1 | 2 |...|N-1|      | 0 | 1 | 2 |...|N-1|
    |nil|nil|nil|...|nil|      |nil|   |nil|...|nil|
    +---+---+---+---+---+      +---+-+-+---+---+---+
                                     |
                                     |
                                     |
                                     v
                                   +-+--+
                                   |User|
                                   |Data|
                                   +----+
                              Index 2N+1

Accesses to elements in the sparse array take O(log n) time where n is the largest element. The base of the logarithm is SA_BLOCK_MAX, so for moderately small indices (e.g. NIDs), single level (constant time) access is achievable. Space usage is O(minimum(m, n log(n)) where m is the number of elements in the array.

Note: sparse arrays only include pointers to types. Thus, SPARSE_ARRAY_OF(char) can be used to store a string.