Eightomic Hash 32 C: The Fastest 32-Bit, OAAT Hashing Algorithm Versus GoodOAAT and Jenkins' OAAT

Eightomic Hash 32 C is a 32-bit, OAAT hashing algorithm as a substantial improvement to GoodOAAT and Jenkins' OAAT.

Library

Source

#ifndef EIGHTOMIC_HASH_32_C_H
#define EIGHTOMIC_HASH_32_C_H

#include <stdint.h>

uint32_t eightomic_hash_32_c(const unsigned long input_count,
                             const uint8_t *input);

#endif

#include "eightomic_hash_32_c.h"

uint32_t eightomic_hash_32_c(const unsigned long input_count,
                             const uint8_t *input) {
  uint32_t mix = 1;
  uint32_t mix_offset = 1111111111;
  unsigned long i = 0;

  while (i < input_count) {
    mix += input[i];
    mix += mix << 3;
    mix_offset += mix + mix_offset;
    mix_offset = (mix_offset << 19) | (mix_offset >> 13);
    i++;
  }

  mix ^= mix_offset;
  mix += (mix_offset << 27) | (mix_offset >> 5);
  mix_offset ^= mix >> 4;
  mix += (mix_offset << 8) | (mix_offset >> 24);
  mix ^= mix_offset >> 3;
  mix_offset += (mix << 14) | (mix >> 18);
  mix_offset ^= ((mix << 9) | (mix >> 23)) + (mix_offset >> 7);
  return mix ^ mix_offset;
}

Reference

eightomic_hash_32_c() is the hashing function that accepts the 2 following arguments in left-to-right order.

1: input_count is the const unsigned long count of elements in the input array.

2: 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.

Example

#include <stdio.h>
#include "eightomic_hash_32_c.h"

int main(void) {
  uint8_t input[8] = {'m', 'e', 's', 's', 'a', 'g', 'e', 0};
  unsigned char i = 0;

  while (i < 10) {
    i++;
    printf("Result %u is 0x%08x.\n", i, eightomic_hash_32_c(8, input));
    input[7]++;
  }

  return 0;
}

Explanation

Eightomic Hash 32 C appears similar to GoodOAAT due to the limited options when designing the fastest one-at-a-time hashing function with good diffusion and collision avoidance, but the technical difference is vast.

The first expression is indentical. It adds an input byte to mix before combining with mix_offset.

The second expression is identical. 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 mix_offset after additive assignment instead of right-rotating bits in mix before additive assignment.

mix_offset combines with mix summed with an additional mix_offset as a cheap addition operand instead of a slow bitwise multiplication after the bit rotation.

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 Xorshift operations in the finalization sequence to create a greater avalanche effect with better differential distribution results on average.

Seed tests in SMHasher are omitted to both discourage using hashing algorithms as PRNGs and prevent collision vulnerabilities from 2³² different initialized states.

It passes all extended SMHasher tests that don't require a seed.

It's faster than GoodOAAT on average with input sizes segmented from 1 byte to 32 bytes, 1 byte to 64 bytes and greater than 64 bytes.

It's faster than Jenkins' OAAT with all input sizes.

When pseudo-cryptographic security isn't required against adversarial input, Eightomic Hash 32 B is a faster alternative with good collision avoidance relative to non-cryptographic hashing algorithms.