Tomas Mraz 3a857b9532 Implement BIO_s_dgram_mem() reusing the BIO_s_dgram_pair() code 2 weeks ago
..
aes ef917549f5 Add vpaes-loongarch64.pl module. 3 months ago
aria 36c269c302 Change loops conditions to make zero loop risk more obvious. 8 months ago
asn1 fe2a7341b5 PKCS12 - Add additional libctx and propq support. 1 week ago
async e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
bf 1567a821a4 crypto: Fix various typos, repeated words, align some spelling to LDP. 3 months ago
bio 3a857b9532 Implement BIO_s_dgram_mem() reusing the BIO_s_dgram_pair() code 1 day ago
bn c9466f38e0 bn2bin(): Don't accept len < 0 1 week ago
buffer e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
camellia 9968c77539 Rename x86-32 assembly files from .s to .S. 8 months ago
cast 2fb5fa4686 remove unused macro in cast_local.h and des_local.h 1 week ago
chacha cd7a8e96bb Fix big-endian issue in chacha20 SVE implementation on aarch64 1 week ago
cmac e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
cmp 01a17b24f6 Fix Coverity 1520485: logically dead code 2 days ago
cms bf3f8f2c0e Ensure ossl_cms_EncryptedContent_init_bio() reports an error on no OID 1 month ago
comp 3840271e98 Add zlib oneshot compression 2 months ago
conf a8086e6bfc stack: Do not add error if pop/shift/value accesses outside of the stack 3 months ago
crmf 084d3afd26 Compensate for CMP-related TODOs removed by PR #15539 1 month ago
ct e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
des 2fb5fa4686 remove unused macro in cast_local.h and des_local.h 1 week ago
dh 7c639f0b8e DH_check[_params]() use libctx of the dh for prime checks 2 months ago
dsa f3090fc710 Implement deterministic ECDSA sign (RFC6979) 1 month ago
dso 89d7231132 crypto/dso/dso_vms.c: Better definition of DSO_MALLOC() 3 months ago
ec 836080a89a Support all five EdDSA instances from RFC 8032 2 weeks ago
encode_decode 9ab57f29c7 Coverity 1515953: negative loop bound 3 months ago
engine 1567a821a4 crypto: Fix various typos, repeated words, align some spelling to LDP. 3 months ago
err a2a09af086 Write SSL_R alerts to error state to keep updated strings 3 weeks ago
ess e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
evp 114d99b46b Fix incomplete checks for EVP_CIPHER_asn1_to_param 3 days ago
ffc a2b01ae1c8 Fix incorrect check on RAND_bytes_ex() in generate_q_fips186_4() 5 days ago
hmac 21dfdbef49 Adapt other parts of the source to the changed EVP_Q_digest() and EVP_Q_mac() 1 year ago
hpke cae72eefc3 prevent HPKE sender setting seq unwisely 1 month ago
http 35b76bc818 OSSL_HTTP_REQ_CTX_nbio(): use OSSL_TRACE_STRING() for msg body where it makes sense 2 days ago
idea c734058309 crypto/*: Fix various typos, repeated words, align some spelling to LDP. 3 months ago
kdf 905b097fd5 Deprecate ERR_load_KDF_strings() 3 years ago
lhash 45ada6b92b Change all references to OpenSSL 3.1 to OpenSSL 3.2 in the master branch 3 months ago
md2 33388b44b6 Update copyright year 2 years ago
md4 33388b44b6 Update copyright year 2 years ago
md5 9968c77539 Rename x86-32 assembly files from .s to .S. 8 months ago
mdc2 33388b44b6 Update copyright year 2 years ago
modes 50d9b2b5f1 Do not build P10-specific AES-GCM assembler on AIX 1 month ago
objects b79da97cf8 Allow OBJ_create() to create an OBJ and NID with a NULL OID 1 month ago
ocsp e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
pem adb408dc79 When using PEM_read_bio_PrivateKey_ex() the public key is optional 2 months ago
perlasm b863e1e4c6 Add two new build targets to enable the possibility of using clang-cl as 2 months ago
pkcs12 fe2a7341b5 PKCS12 - Add additional libctx and propq support. 1 week ago
pkcs7 114d99b46b Fix incomplete checks for EVP_CIPHER_asn1_to_param 3 days ago
poly1305 db24ed5430 Generate the preprocessed .s files for chacha and poly 1305 on ia64 8 months ago
property 9866200bbe Correct property EBNF for unquoted strings 1 week ago
rand a88e97fcac Release the drbg in the global default context before engines 2 months ago
rc2 bb4a32ba24 remove unused macro in rc2_local.h and rc5_local.h 2 weeks ago
rc4 9968c77539 Rename x86-32 assembly files from .s to .S. 8 months ago
rc5 bb4a32ba24 remove unused macro in rc2_local.h and rc5_local.h 2 weeks ago
ripemd 155a82d1fe Avoid putting ripemd_prov.c in libcommon otherwise it is regarded as fips source 3 months ago
rsa 7efc653c43 Make RSA_generate_multi_prime_key() not segfault if e is NULL. 2 weeks ago
seed 38fc02a708 Update copyright year 1 year ago
sha 119b7b5f2a crypto/sha/asm/sha512-ia64.pl: When checking assembler file names, ignore case 2 months ago
siphash c734058309 crypto/*: Fix various typos, repeated words, align some spelling to LDP. 3 months ago
sm2 e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
sm3 eea820f3e2 Add ROTATE inline asm support for SM3 7 months ago
sm4 accd3bdd11 Fix SM4 test failures on big-endian ARM processors 3 weeks ago
srp f44d32fdfb add a check for the return of sk_SRP_gN_new_null() so that capture the potential memory error in time 3 months ago
stack 3a09dfb4f9 Errors raised from OPENSSL_sk_set should have ERR_LIB_CRYPTO 3 months ago
store c734058309 crypto/*: Fix various typos, repeated words, align some spelling to LDP. 3 months ago
thread 14c593e003 Don't set cancel state/type 1 month ago
ts c734058309 crypto/*: Fix various typos, repeated words, align some spelling to LDP. 3 months ago
txt_db f9e8e2c0ab txt_db: fix -Wunused-but-set-variable 3 months ago
ui e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
whrlpool 9968c77539 Rename x86-32 assembly files from .s to .S. 8 months ago
x509 342e3652c7 APPS: generated certs bear X.509 V3, unless -x509v1 option of req app is given 4 days ago
LPdir_nyi.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 4 years ago
LPdir_unix.c fecb3aae22 Update copyright year 9 months ago
LPdir_vms.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 4 years ago
LPdir_win.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 4 years ago
LPdir_win32.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 4 years ago
LPdir_wince.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 4 years ago
README-sparse_array.md 1dc1ea182b Fix many MarkDown issues in {NOTES*,README*,HACKING,LICENSE}.md files 2 years ago
alphacpuid.pl 33388b44b6 Update copyright year 2 years ago
arm64cpuid.pl fecb3aae22 Update copyright year 9 months ago
arm_arch.h 88c53cf17d Apply SM4 optimization patch to Kunpeng-920 2 months ago
armcap.c f97ddfc305 Fix the code used to detect aarch64 capabilities when we don't have getauxval() 1 month ago
armv4cpuid.pl 33388b44b6 Update copyright year 2 years ago
asn1_dsa.c 3c2bdd7df9 Update copyright year 1 year ago
bsearch.c 5c3f1e34b5 ossl_bsearch(): New generic internal binary search utility function 3 years ago
build.info f3090fc710 Implement deterministic ECDSA sign (RFC6979) 1 month ago
c64xpluscpuid.pl 33388b44b6 Update copyright year 2 years ago
context.c f5a3669c8b Add functions supporting thread pool only when it is enabled 2 months ago
core_algorithm.c e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
core_fetch.c e1eafe8c87 "Reserve" the method store when constructing methods 6 months ago
core_namemap.c 5317b6ee1f Add deprecation macro for 3.1 and deprecate OPENSSL_LH_stats 7 months ago
cpt_err.c 826da1451b err: add additional errors 1 year ago
cpuid.c fecb3aae22 Update copyright year 9 months ago
cryptlib.c fecb3aae22 Update copyright year 9 months ago
ctype.c a53d4f83fc Fixed typos in documentation and comments 3 weeks ago
cversion.c 26b7cc0d20 Cleanup include/openssl/opensslv.h.in 3 years ago
der_writer.c 59196250cb der_writer: Use uint32_t instead of long. 7 months ago
deterministic_nonce.c 5e42118de2 Address coverity issue CID 1517105 1 month ago
dllmain.c fecb3aae22 Update copyright year 9 months ago
ebcdic.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 4 years ago
ex_data.c e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
getenv.c fecb3aae22 Update copyright year 9 months ago
ia64cpuid.S 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 4 years ago
info.c 9c3de01512 info.c: Fix typos in seed macro name and description string 2 weeks ago
init.c caf9317d7d Add ZSTD compression support (RFC8478bis) 3 months ago
initthread.c fecb3aae22 Update copyright year 9 months ago
loongarch64cpuid.pl 7f2d6188c7 Add LoongArch64 cpuid and OPENSSL_loongarchcap_P 3 months ago
loongarch_arch.h 7f2d6188c7 Add LoongArch64 cpuid and OPENSSL_loongarchcap_P 3 months ago
loongarchcap.c 7f2d6188c7 Add LoongArch64 cpuid and OPENSSL_loongarchcap_P 3 months ago
mem.c 5639ee79bd ERR: Make CRYPTO_malloc() and friends report ERR_R_MALLOC_FAILURE 5 months ago
mem_clr.c 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 4 years ago
mem_sec.c a509b97d2c Do not check definition of a macro and use it in a single condition 2 weeks ago
mips_arch.h ae4186b004 Fix header file include guard names 3 years ago
o_dir.c fecb3aae22 Update copyright year 9 months ago
o_fopen.c 1567a821a4 crypto: Fix various typos, repeated words, align some spelling to LDP. 3 months ago
o_init.c fecb3aae22 Update copyright year 9 months ago
o_str.c e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
o_time.c 8020d79b40 Update copyright year 1 year ago
packet.c 6292519cd8 QUIC: Enable building with QUIC support disabled 2 weeks ago
param_build.c c455f87aeb OSSL_PARAM_BLD and BIGNUM; ensure at least one byte is allocated 2 weeks ago
param_build_set.c fecb3aae22 Update copyright year 9 months ago
params.c c2ae891483 In OSSL_PARAM_set_BN(), make sure that the data_size field is at least 1 2 weeks ago
params_dup.c e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
params_from_text.c e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
pariscid.pl 33388b44b6 Update copyright year 2 years ago
passphrase.c e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
ppccap.c fecb3aae22 Update copyright year 9 months ago
ppccpuid.pl fecb3aae22 Update copyright year 9 months ago
provider.c e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
provider_child.c 4da7663b02 For child libctx / provider, don't count self-references in parent 8 months ago
provider_conf.c e077455e9e Stop raising ERR_R_MALLOC_FAILURE in most places 3 months ago
provider_core.c d3db25f568 Implement OSSL_PROVIDER_get0_default_search_path, add docs and tests. 1 month ago
provider_local.h b7248964a4 make struct provider_info_st a full type 1 year ago
provider_predefined.c b7248964a4 make struct provider_info_st a full type 1 year ago
punycode.c 905ba92439 punycode: update to use WPACKET instead of using custom range checking 2 months ago
quic_vlint.c 6292519cd8 QUIC: Enable building with QUIC support disabled 2 weeks ago
riscv32cpuid.pl 61170642b1 Add RISC-V 32 cpuid support 4 months ago
riscv64cpuid.pl 360f6dcc5a Add basic RISC-V cpuid and OPENSSL_riscvcap 8 months ago
riscvcap.c 360f6dcc5a Add basic RISC-V cpuid and OPENSSL_riscvcap 8 months ago
s390x_arch.h fecb3aae22 Update copyright year 9 months ago
s390xcap.c 42f111ad41 s390: Add new machine generation 9 months ago
s390xcpuid.pl 33388b44b6 Update copyright year 2 years ago
self_test_core.c fecb3aae22 Update copyright year 9 months ago
sleep.c 82d28c6b3c Rename ossl_sleep() to OSSL_sleep() and make it public 3 months ago
sparccpuid.S 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 4 years ago
sparcv9cap.c 52f7e44ec8 Split bignum code out of the sparcv9cap.c 1 year ago
sparse_array.c 93429fc0ce Coverity 1507376: Dereference after null check 6 months ago
threads_lib.c 523e54c15c Define threads_lib.c functions only for OPENSSL_SYS_UNIX 2 months ago
threads_none.c 894f2166ef CRYPTO_THREAD_lock_new(): Avoid infinite recursion on allocation error 3 months ago
threads_pthread.c 894f2166ef CRYPTO_THREAD_lock_new(): Avoid infinite recursion on allocation error 3 months ago
threads_win.c 894f2166ef CRYPTO_THREAD_lock_new(): Avoid infinite recursion on allocation error 3 months ago
time.c 02d0f87a8b time: move OSSL_TIME to libcrypto 4 months ago
trace.c 0243e82147 add OSSL_TRACE_STRING(), OSSL_TRACE_STRING_MAX, and OSSL_trace_string() 2 days ago
uid.c 3a1fa0116a Openssl fails to compile on Debian with kfreebsd kernels 1 year ago
vms_rms.h 0e9725bcb9 Following the license change, modify the boilerplates in crypto/ 4 years ago
x86_64cpuid.pl 3c2bdd7df9 Update copyright year 1 year ago
x86cpuid.pl 33388b44b6 Update copyright year 2 years ago

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.