THIS IS A TEST INSTANCE ONLY! REPOSITORIES CAN BE DELETED AT ANY TIME!

You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Dr. Matthias St. Pierre 387bbce45b Configure: add missing dependency to fix parallel builds on Windows 1 day ago
..
aes Unify all assembler file generators 5 days ago
aria Remove tab characters from C source files. 2 months ago
asn1 util/mkerr.pl: make it not depend on the function code 1 week ago
async util/mkerr.pl: make it not depend on the function code 1 week ago
bf Unify all assembler file generators 5 days ago
bio Use the correct maximum indent 22 hours ago
blake2 Move BLAKE2 MACs to the providers 1 month ago
bn crypto/bn/build.info: Correct use of SSE2 definition 4 days ago
buffer util/mkerr.pl: make it not depend on the function code 1 week ago
camellia Unify all assembler file generators 5 days ago
cast Unify all assembler file generators 5 days ago
chacha Unify all assembler file generators 5 days ago
cmac Coverty fixes for MACs 3 weeks ago
cmp util/mkerr.pl: make it not depend on the function code 1 week ago
cms util/mkerr.pl: make it not depend on the function code 1 week ago
comp util/mkerr.pl: make it not depend on the function code 1 week ago
conf Add fips module integrity check 6 days ago
crmf fix CRMF symmetric key handling 1 week ago
ct util/mkerr.pl: make it not depend on the function code 1 week ago
des Unify all assembler file generators 5 days ago
dh util/mkerr.pl: make it not depend on the function code 1 week ago
dsa util/mkerr.pl: make it not depend on the function code 1 week ago
dso util/mkerr.pl: make it not depend on the function code 1 week ago
ec Unify all assembler file generators 5 days ago
engine util/mkerr.pl: make it not depend on the function code 1 week ago
err Add aes_xts cipher to providers 1 week ago
ess util/mkerr.pl: make it not depend on the function code 1 week ago
evp Add aes_wrap cipher to providers 2 days ago
hmac Move HMAC to providers 1 month ago
idea Following the license change, modify the boilerplates in crypto/idea/ 9 months ago
include/internal In provider implemented methods, save the name number, not the name string 2 days ago
lhash Fix Typos 2 months ago
md2 Following the license change, modify the boilerplates in crypto/mdN/ 9 months ago
md4 Following the license change, modify the boilerplates in crypto/mdN/ 9 months ago
md5 Unify all assembler file generators 5 days ago
mdc2 Following the license change, modify the boilerplates in crypto/mdc2/ 9 months ago
modes Add aes_wrap cipher to providers 2 days ago
objects util/mkerr.pl: make it not depend on the function code 1 week ago
ocsp util/mkerr.pl: make it not depend on the function code 1 week ago
pem util/mkerr.pl: make it not depend on the function code 1 week ago
perlasm s390x assembly pack: update perlasm module 4 months ago
pkcs7 util/mkerr.pl: make it not depend on the function code 1 week ago
pkcs12 util/mkerr.pl: make it not depend on the function code 1 week ago
poly1305 Unify all assembler file generators 5 days ago
property util/mkerr.pl: make it not depend on the function code 1 week ago
rand Avoid ?: construct in XXXerr calls 2 days ago
rc2 Following the license change, modify the boilerplates in crypto/rcN/ 9 months ago
rc4 Unify all assembler file generators 5 days ago
rc5 Unify all assembler file generators 5 days ago
ripemd Unify all assembler file generators 5 days ago
rsa util/mkerr.pl: make it not depend on the function code 1 week ago
seed Following the license change, modify the boilerplates in crypto/seed/ 9 months ago
sha Unify all assembler file generators 5 days ago
siphash Move SipHash to providers 1 month ago
sm2 util/mkerr.pl: make it not depend on the function code 1 week ago
sm3 Move digests to providers 3 months ago
sm4 Following the license change, modify the boilerplates in crypto/smN/ 9 months ago
srp Remove unnecessary trailing whitespace 7 months ago
stack Make core code available within the FIPS module 4 months ago
store util/mkerr.pl: make it not depend on the function code 1 week ago
ts util/mkerr.pl: make it not depend on the function code 1 week ago
txt_db Following the license change, modify the boilerplates in crypto/ 9 months ago
ui util/mkerr.pl: make it not depend on the function code 1 week ago
whrlpool Unify all assembler file generators 5 days ago
x509 Fix potential memory leaks with BN_to_ASN1_INTEGER 1 week ago
LPdir_nyi.c Following the license change, modify the boilerplates in crypto/ 9 months ago
LPdir_unix.c Following the license change, modify the boilerplates in crypto/ 9 months ago
LPdir_vms.c Following the license change, modify the boilerplates in crypto/ 9 months ago
LPdir_win.c Following the license change, modify the boilerplates in crypto/ 9 months ago
LPdir_win32.c Following the license change, modify the boilerplates in crypto/ 9 months ago
LPdir_wince.c Following the license change, modify the boilerplates in crypto/ 9 months ago
README.sparse_array Fix Typos 2 months ago
alphacpuid.pl Unify all assembler file generators 5 days ago
arm64cpuid.pl Unify all assembler file generators 5 days ago
arm_arch.h Following the license change, modify the boilerplates in crypto/ 9 months ago
armcap.c crypto/armcap.c, crypto/ppccap.c: stricter use of getauxval() 8 months ago
armv4cpuid.pl Unify all assembler file generators 5 days ago
asn1_dsa.c remove end of line whitespace 2 months ago
bsearch.c ossl_bsearch(): New generic internal binary search utility function 4 months ago
build.info Configure: add missing dependency to fix parallel builds on Windows 22 hours ago
c64xpluscpuid.pl Following the license change, modify the boilerplates in crypto/ 9 months ago
context.c Make sure we pre-initialise properties 3 weeks ago
core_algorithm.c Add internal function ossl_algorithm_do_all() 2 months ago
core_fetch.c In provider implemented methods, save the name number, not the name string 2 days ago
core_namemap.c In provider implemented methods, save the name number, not the name string 2 days ago
cpt_err.c util/mkerr.pl: make it not depend on the function code 1 week ago
cryptlib.c Remove extern declarations of OPENSSL_ia32cap_P 2 weeks ago
ctype.c Add missing EBCDIC strings 1 month ago
cversion.c Undeprecate OpenSSL_version_num and OPENSSL_VERSION_NUMBER 2 weeks ago
dllmain.c Following the license change, modify the boilerplates in crypto/ 9 months ago
ebcdic.c Following the license change, modify the boilerplates in crypto/ 9 months ago
ex_data.c Access data after obtaining the lock not before. 1 month ago
getenv.c Following the license change, modify the boilerplates in crypto/ 9 months ago
ia64cpuid.S Following the license change, modify the boilerplates in crypto/ 9 months ago
info.c Add CPU info to the speed command summary 2 weeks ago
init.c drbg: ensure fork-safety without using a pthread_atfork handler 1 week ago
initthread.c Fix init_get_thread_local() 2 months ago
mem.c Create a FIPS provider and put SHA256 in it 5 months ago
mem_clr.c Following the license change, modify the boilerplates in crypto/ 9 months ago
mem_dbg.c Fix deprecation inconsisteny w.r.t. CRYPTO_mem_debug_{push,pop}() 1 month ago
mem_sec.c Use vxRandLib for VxWorks7 4 months ago
mips_arch.h Fix compiling error for mips32r6 and mips64r6 6 months ago
o_dir.c Following the license change, modify the boilerplates in crypto/ 9 months ago
o_fips.c Following the license change, modify the boilerplates in crypto/ 9 months ago
o_fopen.c Following the license change, modify the boilerplates in crypto/ 9 months ago
o_init.c Following the license change, modify the boilerplates in crypto/ 9 months ago
o_str.c Add OPENSSL_hexstr2buf_ex() and OPENSSL_buf2hexstr_ex() 1 month ago
o_time.c Following the license change, modify the boilerplates in crypto/ 9 months ago
packet.c Give WPACKET the ability to have a NULL buffer underneath it 2 months ago
param_build.c Fix ossl_param_bld_push_{utf8,octet}_string() / param_bld_convert() 1 month ago
params.c OSSL_PARAM_construct_utf8_string computes the string length. 2 weeks ago
params_from_text.c Params from text to allow zero length value fields 2 weeks ago
pariscid.pl Unify all assembler file generators 5 days ago
ppc_arch.h PPC: Try out if mftb works before using it 8 months ago
ppccap.c Make the EC code available from inside the FIPS provider 1 month ago
ppccpuid.pl Unify all assembler file generators 5 days ago
provider.c Rename provider and core get_param_types functions 1 month ago
provider_conf.c Load the config file by default 1 month ago
provider_core.c Add fips module integrity check 6 days ago
provider_local.h Replumbing: Add a mechanism to pre-populate the provider store 6 months ago
provider_predefined.c Make core code available within the FIPS module 4 months ago
s390x_arch.h Remove tab characters from C source files. 2 months ago
s390xcap.c s390x assembly pack: use getauxval to detect hw capabilities 1 month ago
s390xcpuid.pl Unify all assembler file generators 5 days ago
sparc_arch.h Following the license change, modify the boilerplates in crypto/ 9 months ago
sparccpuid.S Following the license change, modify the boilerplates in crypto/ 9 months ago
sparcv9cap.c Fix missing bn_mul_mont symbol in solaris fips module 2 days ago
sparse_array.c Fix Typos 2 months ago
threads_none.c drbg: ensure fork-safety without using a pthread_atfork handler 1 week ago
threads_pthread.c drbg: ensure fork-safety without using a pthread_atfork handler 1 week ago
threads_win.c crypto/threads_win.c: fix preprocessor indentation 1 week ago
trace.c prevent endless recursion when trace API is used within OPENSSL_init_crypto() 1 month ago
uid.c Remove NextStep support 2 months ago
vms_rms.h Following the license change, modify the boilerplates in crypto/ 9 months ago
x86_64cpuid.pl Unify all assembler file generators 5 days ago
x86cpuid.pl Unify all assembler file generators 5 days ago

README.sparse_array

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.