WSP-Hash-OAAT: A Fast, Lightweight, Non-Multiplicative, One-at-a-Time 32-Bit Hashing Algorithm That Passes Rigorous Collision Tests

William Stafford Parsons developed a tiny 32-bit OAAT hashing algorithm as a substantial improvement to 32-bit FNV-1a and MicroOAAT.

Library

Source

#include <stdint.h> struct wsp_hash_oaat_s { uint32_t _state; uint32_t state; }; void wsp_hash_oaat_initialize(struct wsp_hash_oaat_s *s) { s->_state = 1; s->state = 1111111111; } void wsp_hash_oaat_transform(unsigned long i, unsigned long input_count, const uint8_t *input, struct wsp_hash_oaat_s *s) { while (i != input_count) { s->state ^= input[i]; s->state += s->state << 3; s->_state += s->state; s->_state = (s->_state << 27) | (s->_state >> 5); i++; } } void wsp_hash_oaat_finalize(struct wsp_hash_oaat_s *s) { s->state ^= s->_state; s->state = (s->_state ^ s->state) + ((s->state << 10) | (s->state >> 22)); s->state += (s->_state << 27) | (s->_state >> 5); }

Reference

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

s is a struct wsp_hash_oaat_s pointer.

wsp_hash_oaat_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 const uint8_t array to hash.

s is a struct wsp_hash_oaat_s pointer.

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

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

The return value data type is void.

Requirements

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

CPU with single-threaded, instruction-level parallelism support.

Explanation

This 32-bit one-at-a-time hashing algorithm is designed to hash keys in data structures in place of existing 32-bit FNV-1a and MicroOAAT implementations.

It's a lossless performance and statistical quality improvement for all input sizes larger than 3 bytes.

Input sizes less than or equal to 3 bytes are slower by a small margin with higher statistical quality.

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.

Seed tests are omitted to discourage using one-at-a-time hashing algorithms as PRNGs and to prevent collision vulnerabilities from 2³² different initialized states.

The core hashing loop structure appears similar to MicroOAAT due to the limited options when designing the fastest non-multiplicative, one-at-a-time hashing function with good collision avoidance, but the technical difference is vast.

It uses a XOR assignment operation for each input byte instead of an addition assignment, similar to FNV-1a. The remaining operations emulate multiplication before finalizing with enhanced bit distribution.

Any bitwise multiplication with a left shift operand greater than << 3 is too slow in the core hashing loop and anything less doesn't result in enough distribution to omit a second bitwise multiplication.

It left-rotates bits in _state instead of right-rotating bits in state.

_state combines with state using addition instead of subtraction to keep bits rolling in the same direction.

Furthermore, the bit rotation is non-blocking with instruction-level parallelism for each next byte iteration.

The speed gains from these design differences allow for a minimal finalization sequence with finely-tuned shift values and additive bit rotations in both directions.

The result deprecates the usage of 32-bit FNV-1a and MicroOAAT by comparison in most practical instances.

There are significant improvements across all SMHasher tests with no critical collision vulnerabilities relative to the compared hashing algorithms.

Compared to 32-bit FNV-1a, it's 53% faster on average for small inputs and up to 70% faster on average for large inputs.

Compared to MicroOAAT, it's 13% faster on average for small inputs and up to 45% faster on average for large inputs.

It's a practical alternative to Jenkin's OAAT and Murmur OAAT as well with significant collision and speed improvements similar to the aforementioned comparisons.

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 wsp_hash_oaat(unsigned long input_count, const uint8_t *input) { uint32_t _state = 1; uint32_t state = 1111111111; unsigned long i = 0; while (i != input_count) { state ^= input[i]; state += state << 3; _state += state; _state = (_state << 27) | (_state >> 5); i++; } state ^= _state; state = (_state ^ state) + ((state << 10) | (state >> 22)); return ((_state << 27) | (_state >> 5)) + state; }

All speed tests were performed locally on a Pixelbook Go M3 using Debian.

Games

ContrivityContrivity Icon

Contrivity

Spawn into the hostile quantum laboratory and destroy wave after wave of oscillations.

v1.0.21