Eightomic Hash 32 B: The Fastest 32-Bit, OAAT Hashing Algorithm Versus 32-Bit FNV-1a and MicroOAAT

Eightomic Hash 32 B is a 32-bit, OAAT hashing algorithm as a substantial improvement to FNV-1a, MicroOAAT and MurmurOAAT.

Library

Source

#ifndef EIGHTOMIC_HASH_32_B_H
#define EIGHTOMIC_HASH_32_B_H

#include <stdint.h>

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

#endif

#include "eightomic_hash_32_b.h"

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

  if (input_count > 3) {
    while (i < input_count) {
      mix -= input[i];
      mix += mix << 3;
      mix_offset -= mix;
      mix_offset = (mix_offset << 27) | (mix_offset >> 5);
      i++;
    }

    mix ^= mix_offset;
    mix = (mix ^ mix_offset) + ((mix << 10) | (mix >> 22));
    return mix + ((mix_offset << 27) | (mix_offset >> 5));
  }

  while (i < input_count) {
    mix += input[i];
    mix += (mix << 23) | (mix >> 9);
    mix += mix << 3;
    i++;
  }

  return mix;
}

Reference

eightomic_hash_32_b() 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_b.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_b(8, input));
    input[7]++;
  }

  return 0;
}

Explanation

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

It uses a subtraction assignment for each input byte instead of XOR or addition assignments. The remaining operations emulate multiplication with combinatorial bit rotations.

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 instead of right-rotating bits in mix.

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.

Input sizes less than 4 bytes fall through to a minimal hashing algorithm that matches the speed of FNV-1a.

There are substantial improvements across all SMHasher tests in the context of critical collision vulnerabilities among the compared hashing algorithms.

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

It's faster than 32-bit FNV-1a with all input sizes.

It's faster than MicroOAAT with all input sizes.

It's faster than MurmurOAAT with all input sizes.

When lower collision counts aren't required for higher security against adversarial input, Eightomic Hash 32 A is a faster alternative that uses 4 less bytes per hash with a tradeoff of higher collision counts and poor diffusion.

When a better avalanche effect and lower collision counts are required for pseudo-cryptographic security against adversarial input, Eightomic Hash 32 C is a better alternative with a tradeoff of marginally-slower speed.