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

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.