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

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.