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

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.