WSP-Hash-OAAT: The Fastest One-at-a-Time Hashing Algorithm With Good Quality
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;
};
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;
}
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() is the all-at-once hashing function that accepts the 2 following arguments.
input_count is the count of elements in the input array.
input is the const uint8_t array to hash.
The return value data type is uint32_t.
It returns the 32-bit unsigned integer hash digest result.
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 function 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 code 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.
All speed tests were performed locally on a Pixelbook Go M3 using Debian.
