Hash 32 F

It's the fastest 32-bit hashing algorithm versus CityHash32 and XXHash32.

Algorithm

Source

The control flow is being modified to increase speed without changing the core hashing algorithm output.

#include <stdint.h>

uint32_t eightomic_align_32(const uint8_t *input, unsigned long i) {
  uint32_t input_aligned = input[i];

  input_aligned |= input[i + 1] << 8;
  input_aligned |= input[i + 2] << 16;
  input_aligned |= input[i + 3] << 24;
  return input_aligned;
}

uint32_t eightomic_hash_32_f(unsigned long input_count, const uint8_t *input,
                             const uint32_t seed) {
  unsigned long input_count_capture = input_count;
  uint32_t a = seed ^ 1;
  uint32_t b = 11;
  uint32_t c = 111;
  uint32_t d = 1111;
  uint32_t e = 11111;
  uint32_t f = 111111;
  uint32_t g = 1111111;
  uint32_t h = 11111111;
  uint32_t mix = 111111111;
  uint32_t mix_offset = seed ^ 1111111111;
  unsigned long i = 0;

  if (input_count >= 32) {
    i = 31;

    while (i < input_count) {
      mix += a + b + c + d + e + f + g + h;
      a += eightomic_align_32(input, i - 3) + ((a << 8) | (a >> 24)) + mix;
      b += eightomic_align_32(input, i - 7) + ((b << 23) | (b >> 9));
      c += eightomic_align_32(input, i - 11) + ((c << 10) | (c >> 22));
      d += eightomic_align_32(input, i - 15) + ((d << 21) | (d >> 11));
      e += eightomic_align_32(input, i - 19) + ((e << 12) | (e >> 20));
      f += eightomic_align_32(input, i - 23) + ((f << 19) | (f >> 13));
      g += eightomic_align_32(input, i - 27) + ((g << 14) | (g >> 18));
      h += eightomic_align_32(input, i - 31) + ((h << 17) | (h >> 15));
      i += 32;
    }

    if (i >= input_count) {
      i -= 32;
    }

    mix_offset += a + b + c + d + e + f + g + h;
    i++;
  }

  if ((input_count - i) >= 16) {
    i += 16;
    a += eightomic_align_32(input, i - 16) + ((a << 8) | (a >> 24));
    b += eightomic_align_32(input, i - 12) + ((b << 23) | (b >> 9));
    c += eightomic_align_32(input, i - 8) + ((c << 10) | (c >> 22));
    d += eightomic_align_32(input, i - 4) + ((d << 21) | (d >> 11));
    mix += a + b + c + d;
  }

  if ((input_count - i) >= 8) {
    i += 8;
    a += eightomic_align_32(input, i - 8) + ((a << 8) | (a >> 24));
    b += eightomic_align_32(input, i - 4) + ((b << 23) | (b >> 9));
    mix += a + b;
  }

  if (i != input_count) {
    mix += (a << 8) | (a >> 24);
    input_count -= i;

    if (input_count >= 4) {
      a += eightomic_align_32(input, i);

      if (input_count != 4) {
        mix_offset += a + mix;

        switch (input_count) {
          case 7:
            b += input[i + 6] << 16;
          case 6:
            b += input[i + 5] << 8;
          case 5:
            b += input[i + 4];
        }
      }
    }

    switch (input_count) {
      case 3:
        a += input[i + 2] << 16;
      case 2:
        a += input[i + 1] << 8;
      case 1:
        a += input[i];
    }
  }

  a += b + mix_offset;
  mix += (a << 8) | (a >> 24);

  if (input_count_capture >= 8) {
    mix += c + ((d << 11) | (d >> 21));

    if (input_count_capture >= 32) {
      mix_offset += ((e << 20) | (e >> 12)) + g;
      mix += (h << 15) | (h >> 17);
    }
  }

  mix_offset += mix + input_count_capture;
  mix += ((a << 13) | (a >> 19)) + h;
  b += mix_offset;
  mix_offset += a + ((b << 18) | (b >> 14));

  if (input_count_capture >= 8) {
    c += mix;
    mix += b + ((c << 15) | (c >> 17));
    e += mix_offset;
    mix_offset += d + ((e << 18) | (e >> 14));

    if (input_count_capture >= 32) {
      f += ((e << 18) | (e >> 14)) + mix;
      mix_offset += e + ((f << 19) | (f >> 13));
      mix += f + g;
    }
  }

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

License

It's free and open source.

Reference

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

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

2: input is the const uint8_t array to hash.

3: seed is the const uint32_t auxiliary seed.

The return value data type is uint32_t.

It returns the 32-bit unsigned integer hash digest result.

Explanation

It's the fastest 32-bit hashing algorithm for 32-bit processors with good security properties and statistical quality relevant to non-cryptographic hashing.

It's faster than CityHash32 and XXHash32 at all input sizes.

Speed tests were performed with endian-safe, slower memory reads instead of using memcpy(), but eightomic_align_32() is adjustable whenever implementations allow endian-unsafe memcpy() reads or unaligned reads for faster speed.

It uses incrementally-decreasing block sizes based on the largest possible block size within input_count. It starts by hashing blocks of 256 bits, then decreases to 128 bits, 64 bits, 32 bits and the remainder instead of branching into one of several hash functions based on input_count.

The hash function uses addition arithmetic and bit rotations without XORs, making it a near-perfect hash function for duplicate hash inputs with varying seeds.

The finalization process decreases collisions by mixing between 16 and 256 bits of state into mix and mix_offset based on the input_count to increase speed for inputs smaller than 32 bytes.

The remaining finalization process is similar to the pseudo-cryptographic finalization from Eightomic Hash 32 C to increase diffusion for a good avalanche effect in a combination of 2 32-bit blocks.

The final expression in the finalization process uses a single XOR for a greater avalanche effect without either corrupting the collision avoidance properties or requiring additional bit mixing operations.

It passes all extended, non-cryptographic SMHasher and SMHasher2 collision tests while XXHash32 fails the Keyset "Text" collision tests.

Furthermore, it passes all extended seed-based collision tests in SMHasher2 without broken seeds, therefore indicating good security properties for resilience against HashDoS attacks in data structures that process user input.

There aren't any bit distribution bias calculation percentages exceeding 14% in the aforementioned tests where 100% is the worst result and less than 1% is desired for cryptographic security against cryptanalysis, therefore indicating the absence of critical bit distribution vulnerabilities relevant to non-cryptographic hashing.

Avalanche tests in SMHasher are omitted as strict avalanche criterion is only relevant to the analysis of cryptographic hash function output predictability.

To measure non-cryptographic bit distribution, especially for data structure keys, the following code tests collision counts for truncated digests against each of the 8 bits flipped within a single input byte ranging from 1 to 255 at all positions for all input_count values ranging from 1 to 256.

#include <stdint.h>
#include <stdio.h>
#include "eightomic_hash_32_f.h"

int main(void) {
  uint8_t input[256];
  uint32_t result = 0;
  uint32_t result_flipped = 1;
  unsigned long bit_collisions_counts[32];
  unsigned short sparse_byte = 0;
  unsigned short i = 0;
  unsigned short j = 0;
  unsigned short k = 0;
  unsigned short l = 0;
  unsigned short m = 0;

  while (i != 32) {
    bit_collisions_counts[i] = 0;
    i++;
  }

  i = 1;

  while (sparse_byte != 16) {
    while (i < 256) {
      j = 1;

      while (j < 256) {
        k = 0;

        while (k < j) {
          while (l < j) {
            input[l] = sparse_byte;
            l++;
          }

          if (sparse_byte == i) {
            k = j;
            l = 0;
            continue;
          }

          input[k] = i;
          result = eightomic_hash_32_f(j, (const uint8_t *) input, 0);
          l = 0;

          while (l < 8) {
            input[k] = input[k] ^ (1 << l);
            result_flipped = eightomic_hash_32_f(j, (const uint8_t *) input, 0);
            input[k] = input[k] ^ (1 << l);
            m = 1;

            while (m < 32) {
              if (
                (result & ((2 << m) - 1)) == (result_flipped & ((2 << m) - 1))
              ) {
                bit_collisions_counts[m - 1]++;
              }

              m++;
            }

            l++;
            m = 0;
          }

          k++;
          l = 0;
        }

        j++;
        k = 0;
      }

      i++;
    }

    sparse_byte++;
    i = 1;
  }

  i = 2;
  j = 0;

  while (i < 33) {
    printf("%2u-Bit Segmented Collisions: %9lu\n",
           i,
           bit_collisions_counts[i - 2]);
    i++;
    j++;
  }

  return 0;
}

The following collision results demonstrate a sufficient collision-based avalanche effect in a worst instance with non-cryptographic relevance.

 2-Bit Segmented Collisions: 270726087
 3-Bit Segmented Collisions: 136911129
 4-Bit Segmented Collisions:  69050184
 5-Bit Segmented Collisions:  34992037
 6-Bit Segmented Collisions:  17457406
 7-Bit Segmented Collisions:   8774708
 8-Bit Segmented Collisions:   4301852
 9-Bit Segmented Collisions:   2189270
10-Bit Segmented Collisions:   1107805
11-Bit Segmented Collisions:    574855
12-Bit Segmented Collisions:    311234
13-Bit Segmented Collisions:    177874
14-Bit Segmented Collisions:    109534
15-Bit Segmented Collisions:     34836
16-Bit Segmented Collisions:     16730
17-Bit Segmented Collisions:      7965
18-Bit Segmented Collisions:      3821
19-Bit Segmented Collisions:      2004
20-Bit Segmented Collisions:       975
21-Bit Segmented Collisions:       493
22-Bit Segmented Collisions:       249
23-Bit Segmented Collisions:       124
24-Bit Segmented Collisions:        60
25-Bit Segmented Collisions:        32
26-Bit Segmented Collisions:        12
27-Bit Segmented Collisions:         4
28-Bit Segmented Collisions:         2
29-Bit Segmented Collisions:         0
30-Bit Segmented Collisions:         0
31-Bit Segmented Collisions:         0
32-Bit Segmented Collisions:         0

The semi-linear collision increments after each truncation are within an acceptable range based on the probability of collisions at each bit size. For example, 200-300 million collisions in the lower 2 bits are expected out of 1 billion total keys, but 0 are expected in the full 32 bits.

As the truncated size of each set of digests increases, the amount of collisions should decrease by a minimum of 20% and a maximum of 75% until there are 0 collisions.

Eightomic is developing the aforementioned non-cryptographic avalanche test further with clearer explanations and a "pass or fail" test that uses a wider range of inputs and digest truncations.

API

Quantum

Spawn non-deterministic, quantum-aligned randomness with an optimal, unique QRNG API.