Pauli 987d7da327 Include a local static buffer for the SHA helper functions		3 tahun lalu
..
aes	0051746e03 Add AES consttime code for no-asm configurations	3 tahun lalu
aria	3c2bdd7df9 Update copyright year	3 tahun lalu
asn1	515480be79 ASN1_parse_dump(): allow NULL BIO input, to simplify applications not needing output	3 tahun lalu
async	b93f6c2db9 err: rename err_load_xxx_strings_int functions	3 tahun lalu
bf	33388b44b6 Update copyright year	4 tahun lalu
bio	bb19b9d456 BIO_write_ex(): Make handing of BIO b == NULL and dlen == 0 less redundant	3 tahun lalu
bn	26b3e44a66 bn: remove TODOs	3 tahun lalu
buffer	b93f6c2db9 err: rename err_load_xxx_strings_int functions	3 tahun lalu
camellia	33388b44b6 Update copyright year	4 tahun lalu
cast	670ff08e77 Fix logic error for building x86 CAST assembly	4 tahun lalu
chacha	6d3f798cba Properly restore XMM registers in ChaCha20's AVX-512(VL) assembly	3 tahun lalu
cmac	ed576acdf5 Rename all getters to use get/get0 in name	3 tahun lalu
cmp	7be04a3ac4 Give ASN.1 objects the ability to report their libctx/propq	3 tahun lalu
cms	60d13c8ff8 remove end of line whitespace	3 tahun lalu
comp	1486b1fbd3 comp: remove TODOs	3 tahun lalu
conf	b3c2ed7043 Add NCONF_get_section_names()	3 tahun lalu
crmf	e0a7ef0b51 crmf: remove TODOs	3 tahun lalu
ct	7834d50fa9 Fix CTLOG_new_from_base64_ex()	3 tahun lalu
des	4333b89f50 Update copyright year	3 tahun lalu
dh	1c49be8673 Fix DH/DHX named groups to not overwrite the private key length.	3 tahun lalu
dsa	ed576acdf5 Rename all getters to use get/get0 in name	3 tahun lalu
dso	d475a9efcf dl_name_converter: Avoid unnecessary overallocation	3 tahun lalu
ec	8c7c1c84cb Add a generic SubjectPublicKeyInfo decoder	3 tahun lalu
encode_decode	27fb7a0a27 DECODER & ENCODER: Add better tracing	3 tahun lalu
engine	ed576acdf5 Rename all getters to use get/get0 in name	3 tahun lalu
err	5a9dbfc58a err: clear flags better when clearing errors.	3 tahun lalu
ess	b93f6c2db9 err: rename err_load_xxx_strings_int functions	3 tahun lalu
evp	cd77073879 Adapt all public EVP_XXX_do_all_provided() for the changed evp_generic_do_all()	3 tahun lalu
ffc	ed576acdf5 Rename all getters to use get/get0 in name	3 tahun lalu
hmac	ed576acdf5 Rename all getters to use get/get0 in name	3 tahun lalu
http	8ccbf00d17 Rename OSSL_HTTP_set_request() to OSSL_HTTP_set1_request() for clarity	3 tahun lalu
idea	3c2bdd7df9 Update copyright year	3 tahun lalu
kdf	905b097fd5 Deprecate ERR_load_KDF_strings()	5 tahun lalu
lhash	3c2bdd7df9 Update copyright year	3 tahun lalu
md2	33388b44b6 Update copyright year	4 tahun lalu
md4	33388b44b6 Update copyright year	4 tahun lalu
md5	839261592c Remove unused code from the fips module	3 tahun lalu
mdc2	33388b44b6 Update copyright year	4 tahun lalu
modes	ed576acdf5 Rename all getters to use get/get0 in name	3 tahun lalu
objects	b93f6c2db9 err: rename err_load_xxx_strings_int functions	3 tahun lalu
ocsp	126e37716f ocsp: remove TODOs	3 tahun lalu
pem	6a2b8ff392 Decoding PKCS#8: separate decoding of encrypted and unencrypted PKCS#8	3 tahun lalu
perlasm	178fa72ed5 Add aix64-gcc-as architecture and p2align callback	3 tahun lalu
pkcs12	9428977994 pkcs12: fix Coverity 1485667 logically dead code	3 tahun lalu
pkcs7	dea2878fac Teach more of the ASN.1 code about libctx/propq	3 tahun lalu
poly1305	848af5e8fe Drop libimplementations.a	3 tahun lalu
property	f0191d0b13 Add the internal function ossl_method_store_do_all()	3 tahun lalu
rand	dce7272d08 Elimination of some sources not needed in the FIPS_MODULE	3 tahun lalu
rc2	aff636a489 Update copyright year	3 tahun lalu
rc4	572e6df7db rename md5_block_asm_data_order to ossl_md5_block_asm_data_order	4 tahun lalu
rc5	33388b44b6 Update copyright year	4 tahun lalu
ripemd	848af5e8fe Drop libimplementations.a	3 tahun lalu
rsa	085e3cecbd Move libssl related defines used by fips provider to prov_ssl.h	3 tahun lalu
seed	6229815ab8 Use <> for #include openssl/xxx	3 tahun lalu
sha	987d7da327 Include a local static buffer for the SHA helper functions	3 tahun lalu
siphash	5db682733d Fix a TODO(3.0) in the siphash code	3 tahun lalu
sm2	ed576acdf5 Rename all getters to use get/get0 in name	3 tahun lalu
sm3	f6c95e46c0 Add "origin" field to EVP_CIPHER, EVP_MD	3 tahun lalu
sm4	3c2bdd7df9 Update copyright year	3 tahun lalu
srp	5cbd2ea3f9 add zero strenght arguments to BN and RAND RNG calls	3 tahun lalu
stack	5fd7eb5c8a Improve the implementation of X509_STORE_CTX_get1_issuer()	3 tahun lalu
store	29b3fdad2b Refactor OSSL_STORE_LOADER_do_all_provided() to behave like OSSL_STORE_LOADER_fetch()	3 tahun lalu
ts	effb0dcf86 Check the return value of ASN1_STRING_length	3 tahun lalu
txt_db	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
ui	b93f6c2db9 err: rename err_load_xxx_strings_int functions	3 tahun lalu
whrlpool	202cbdd2fc A few cleanups of the provider build.infos	3 tahun lalu
x509	8c7c1c84cb Add a generic SubjectPublicKeyInfo decoder	3 tahun lalu
LPdir_nyi.c	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
LPdir_unix.c	db5cf86535 Fix a -Warray-bounds gcc warning in OPENSSL_DIR_read	5 tahun lalu
LPdir_vms.c	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
LPdir_win.c	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
LPdir_win32.c	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
LPdir_wince.c	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
README-sparse_array.md	1dc1ea182b Fix many MarkDown issues in {NOTES,README,HACKING,LICENSE}.md files	4 tahun lalu
alphacpuid.pl	33388b44b6 Update copyright year	4 tahun lalu
arm64cpuid.pl	5ea64b456b Read MIDR_EL1 system register on aarch64	3 tahun lalu
arm_arch.h	0789c7d834 Update copyright year	3 tahun lalu
armcap.c	a5d250e57e Use getauxval on Android with API level > 18	3 tahun lalu
armv4cpuid.pl	33388b44b6 Update copyright year	4 tahun lalu
asn1_dsa.c	3c2bdd7df9 Update copyright year	3 tahun lalu
bsearch.c	5c3f1e34b5 ossl_bsearch(): New generic internal binary search utility function	5 tahun lalu
build.info	50360c1a4b FIPS: don't include crypto/passphrase.c in libfips.a	3 tahun lalu
c64xpluscpuid.pl	33388b44b6 Update copyright year	4 tahun lalu
context.c	f12a5690de Add the concept of a child OSSL_LIB_CTX	3 tahun lalu
core_algorithm.c	d7970dd963 Fix pointer passed to provider_unquery_operation	3 tahun lalu
core_fetch.c	9067cf6ccd CORE: Move away the allocation of the temporary no_cache method store	3 tahun lalu
core_namemap.c	ed576acdf5 Rename all getters to use get/get0 in name	3 tahun lalu
cpt_err.c	b93f6c2db9 err: rename err_load_xxx_strings_int functions	3 tahun lalu
cpuid.c	ef83daf4da Refactor CPUID code	3 tahun lalu
cryptlib.c	71653965b3 crypto: remove TODOs	3 tahun lalu
ctype.c	6229815ab8 Use <> for #include openssl/xxx	3 tahun lalu
cversion.c	26b7cc0d20 Cleanup include/openssl/opensslv.h.in	5 tahun lalu
der_writer.c	a55b00bdbc der: _ossl prefix DER functions	4 tahun lalu
dllmain.c	25f2138b0a Reorganize private crypto header files	5 tahun lalu
ebcdic.c	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
ex_data.c	a16d21744d Add the ability for ex_data to have a priority	3 tahun lalu
getenv.c	eec0ad10b9 Update copyright year	4 tahun lalu
ia64cpuid.S	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
info.c	b55a0b0ff2 Print CPUINFO also for s390 processors	4 tahun lalu
init.c	7d69c07ddf OPENSSL_init_crypto must return 0 when cleanup was done	3 tahun lalu
initthread.c	c9732f0953 Fix a memleak in the FIPS provider	3 tahun lalu
mem.c	f844f9eb44 Rename FIPS_MODE to FIPS_MODULE	4 tahun lalu
mem_clr.c	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
mem_sec.c	3c2bdd7df9 Update copyright year	3 tahun lalu
mips_arch.h	ae4186b004 Fix header file include guard names	5 tahun lalu
o_dir.c	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
o_fopen.c	605856d72c Update copyright year	4 tahun lalu
o_init.c	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
o_str.c	3c2bdd7df9 Update copyright year	3 tahun lalu
o_time.c	8020d79b40 Update copyright year	3 tahun lalu
packet.c	085e3cecbd Move libssl related defines used by fips provider to prov_ssl.h	3 tahun lalu
param_build.c	3f883c7c83 Replace OSSL_PARAM_BLD_free_params() with OSSL_PARAM_free().	3 tahun lalu
param_build_set.c	8020d79b40 Update copyright year	3 tahun lalu
params.c	1fac270501 Fix potential NULL dereference in OSSL_PARAM_get_utf8_string()	3 tahun lalu
params_dup.c	4ecb19d109 params_dup: fix off by one error that allows array overreach.	3 tahun lalu
params_from_text.c	27f37279df params: fix coverity 1473069: unchecked return values	3 tahun lalu
pariscid.pl	33388b44b6 Update copyright year	4 tahun lalu
passphrase.c	67b6401356 CORE: Fix small bug in passphrase caching	4 tahun lalu
ppc_arch.h	ae4186b004 Fix header file include guard names	5 tahun lalu
ppccap.c	a7981653ea ppc: fix ambiguous if if else statement	3 tahun lalu
ppccpuid.pl	33388b44b6 Update copyright year	4 tahun lalu
provider.c	c4e9167437 Rename also the OSSL_PROVIDER_name() function	3 tahun lalu
provider_child.c	b1c053acda Ensure mirroring of properties works for subsequent updates	3 tahun lalu
provider_conf.c	6b750b89ee Add NCONF_get0_libctx()	3 tahun lalu
provider_core.c	97abae6a9d Add various OBJ functions as callbacks	3 tahun lalu
provider_local.h	3c2bdd7df9 Update copyright year	3 tahun lalu
provider_predefined.c	3c2bdd7df9 Update copyright year	3 tahun lalu
punycode.c	eec0ad10b9 Update copyright year	4 tahun lalu
s390x_arch.h	33388b44b6 Update copyright year	4 tahun lalu
s390xcap.c	5768804d5a crypto/s390xcap.c: Add guards around the GETAUXVAL checks	5 tahun lalu
s390xcpuid.pl	33388b44b6 Update copyright year	4 tahun lalu
self_test_core.c	0789c7d834 Update copyright year	3 tahun lalu
sparc_arch.h	ae4186b004 Fix header file include guard names	5 tahun lalu
sparccpuid.S	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
sparcv9cap.c	64fac96de8 sparc: fix cross compile build	3 tahun lalu
sparse_array.c	3c2bdd7df9 Update copyright year	3 tahun lalu
threads_lib.c	c739222b5a Fix no-threads	3 tahun lalu
threads_none.c	3c2bdd7df9 Update copyright year	3 tahun lalu
threads_pthread.c	cd3f8c1b11 Always check CRYPTO_LOCK_{read,write}_lock	3 tahun lalu
threads_win.c	cd3f8c1b11 Always check CRYPTO_LOCK_{read,write}_lock	3 tahun lalu
trace.c	a935791d54 Rework and make DEBUG macros consistent.	3 tahun lalu
uid.c	6b10d29c1a Remove NextStep support	5 tahun lalu
vms_rms.h	0e9725bcb9 Following the license change, modify the boilerplates in crypto/	6 tahun lalu
x86_64cpuid.pl	3c2bdd7df9 Update copyright year	3 tahun lalu
x86cpuid.pl	33388b44b6 Update copyright year	4 tahun lalu

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.

README-sparse_array.md

Sparse Arrays