Tiny One-at-a-Time Hash: A Fast, Lightweight, Non-Multiplicative Hashing Algorithm That Passes Rigorous Statistical Quality Tests

Eightomic developed a tiny 32-bit OAAT hashing algorithm with a library in C99 as a substantial improvement to FNV-1a, Good OAAT, Jenkins OAAT, Micro OAAT and Murmur OAAT.

Library

Source

#include <stdint.h> struct eightomic_s { uint32_t _state; uint32_t state; }; void eightomic_initialize(struct eightomic_s *s) { s->_state = 1111; s->state = 1111111111; } void eightomic_transform(unsigned long i, unsigned long input_count, uint8_t *input, struct eightomic_s *s) { while (i != input_count) { s->state += input[i]; s->state += s->state << 3; s->state = (s->state << 19) | (s->state >> 13); s->_state += s->state + 1; i++; } } void eightomic_finalize(struct eightomic_s *s) { s->state ^= s->_state >> 1; s->state += (s->_state << 27) | (s->_state >> 5); s->_state ^= s->state >> 4; s->state += (s->_state << 8) | (s->_state >> 24); s->state ^= s->_state >> 3; s->_state += (s->state << 14) | (s->state >> 18); s->_state += (s->_state >> 7) ^ ((s->state << 9) | (s->state >> 23)); s->state ^= s->_state; }

Reference

eightomic_initialize() is the initialization function that accepts the following argument.

s is a struct eightomic_s pointer.

eightomic_transform() is the core hashing loop that accepts the 4 following arguments.

i is the starting index position of elements in the input array.

input_count is the count of elements in the input array.

input is the int8_t array to hash.

s is a struct eightomic_s pointer.

eightomic_finalize() is the finalization function that accepts the following argument.

s is a struct eightomic_s pointer. s.state contains the finalized hash digest result.

Requirements

C compiler with C99 (ISO/IEC 9899:1999) standard compatibility.

Explanation

This 32-bit one-at-a-time hashing algorithm is designed to hash keys in data structures as a performance and security upgrade to replace existing implementations of FNV-1a, Good OAAT, Jenkin's OAAT, Micro OAAT and Murmur OAAT.

It's portable for both 32-bit and 64-bit systems.

It meets strict compliance, portability and security requirements.

It doesn't use modulus, multiplication or division arithmetic operations.

Low-cost addition and bitwise instructions work well on a wide range of CPU queue loads and devices.

The additive constant 1, summed with the internal s->state, eliminates any possible vulnerability to input elements with a 0 value.

Seed tests are omitted to discourage using one-at-a-time hashing algorithms as PRNGs.

Furthermore, not allowing a seed secures the possibility of 2^32 deterministic attacks.

OAAT hashing algorithms are chosen over multi-byte hashing algorithms when hashing is infrequent or when there are implementation constraints, such as compiler security precautions, small input buffer sizes or strict compliance rules.

Compared to FNV-1a, Jenkin's OAAT, Micro OAAT and Murmur OAAT, the speed's faster on average.

Compared to Good OAAT, the speed is similar across different input sizes and compilers while achieving superior statistical quality in SMHasher. It passes all extended SMHasher tests with better results across a majority of tests, including avalanche distribution.

FNV-1a, Jenkin's OAAT, Micro OAAT, and Murmur OAAT all fail most SMHasher tests with 1000x to 4000x the expected number of collisions in some tests, which could lead to slow hash table performance and program failure when too much memory is allocated to compensate.

As with the other OAAT algorithms, it shouldn't be used for any cryptographic purposes due to the easily-reversible finalization sequence.

As with the other hashing functions in SMHasher, it was tested with the following all-at-once hashing function instead of the slower segmented functions from the aforementioned library code.

#include <stdint.h> uint32_t eightomic_oaat(unsigned long input_count, uint8_t *input) { uint32_t _state = 1111; uint32_t state = 1111111111; unsigned long i = 0; while (i != input_count) { state += input[i]; state += state << 3; state = (state << 19) | (state >> 13); _state += state + 1; i++; } state ^= _state >> 1; state += (_state << 27) | (_state >> 5); _state ^= state >> 4; state += (_state << 8) | (_state >> 24); state ^= _state >> 3; _state += (state << 14) | (state >> 18); _state += (_state >> 7) ^ ((state << 9) | (state >> 23)); return _state ^ state; }