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

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.