64-Bit Non-Cryptographic Hash: A Fast, Non-Multiplicative, Security-Centric Hashing Algorithm With Good High and Low Bits

Eightomic developed a 64-bit hashing algorithm with a library in C99 as a substantial improvement to CityHash64, MurmurHash3, SipHash and SpookyHashV2.

Library

Source

#include <stdint.h>
#include <stdio.h>
#include <string.h>

uint32_t align_32(const uint8_t *input, unsigned long i) {
  uint32_t _input = 0xFEFF;
  uint8_t byte_order;

  memcpy(&byte_order, &_input, sizeof(byte_order));
  memcpy(&_input, &input[i], sizeof(_input));

  if (byte_order != 0xFF) {
    _input = (_input << 24) | ((_input & 0xFF00) << 8)
      | ((_input & 0xFF0000) >> 8) | (_input >> 24);
  }

  return _input;
}

uint64_t align_64(const uint8_t *input, unsigned long i) {
  uint64_t _input = 0xFEFF;
  uint8_t byte_order;

  memcpy(&byte_order, &_input, sizeof(byte_order));
  memcpy(&_input, &input[i], sizeof(_input));

  if (byte_order != 0xFF) {
    _input = (_input << 56)
      | ((_input & 0xFF00) << 40)
      | ((_input & 0xFF0000) << 24)
      | ((_input & 0xFF000000) << 8)
      | ((_input & 0xFF00000000) >> 8)
      | ((_input & 0xFF0000000000) >> 24)
      | ((_input & 0xFF000000000000) >> 40)
      | (_input >> 56);
  }

  return _input;
}

struct eightomic_s {
  uint64_t a;
  uint64_t b;
  uint64_t c;
  uint64_t d;
  uint64_t _state;
  uint64_t state;
};

void eightomic_initialize(struct eightomic_s *s) {
  s->a = 1;
  s->b = 11;
  s->c = 111;
  s->d = 1111;
  s->_state = 1111111111;
  s->state = 11111111111;
}

void eightomic_transform(unsigned long i, unsigned long input_count,
                         const uint8_t *input, struct eightomic_s *s) {
  uint64_t _a;
  uint64_t _b;
  uint64_t _c;
  uint64_t _d;

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

    while (i < input_count) {
      _a = align_64(input, i - 7);
      _b = align_64(input, i - 15);
      _c = align_64(input, i - 23);
      _d = align_64(input, i - 31);
      s->state += _a + _b + _c + _d;
      s->a += ((s->a << 30) | (s->a >> 34)) + s->state + _a + 1;
      s->b += ((s->b << 29) | (s->b >> 35)) + s->state + _b + 11;
      s->c += ((s->c << 28) | (s->c >> 36)) + _c + 111;
      s->d += ((s->d << 27) | (s->d >> 37)) + _d + 1111;
      i += 32;
    }

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

    s->state += s->a + s->b + s->c + s->d;
    i++;
    input_count -= i;
  }

  if (input_count >= 16) {
    input_count -= 16;
    i += 16;
    _a = align_64(input, i - 16);
    _b = align_64(input, i - 8);
    s->state += _a + _b;
    s->a += ((s->a << 30) | (s->a >> 34)) + s->state + _a + 1;
    s->b += ((s->b << 29) | (s->b >> 35)) + s->state + _b + 11;
  }

  if (input_count >= 8) {
    input_count -= 8;
    i += 8;
    _a = align_64(input, i - 8);
    s->state += _a;
    s->a += ((s->a << 30) | (s->a >> 34)) + s->state + _a + 1;
  }

  if (input_count != 0) {
    s->state += ((s->a << 16) | (s->a >> 48)) + s->_state;

    if (input_count >= 4) {
      s->a += align_32(input, i) + s->state + 1111111111;

      if (input_count != 4) {
        s->_state += s->a + s->b;
        s->state += ((s->b << 20) | (s->b >> 44)) + s->_state;

        if (input_count == 7) {
          s->b += (input[i + 4] | (input[i + 5] << 8)
            | (input[i + 6] << 16)) + s->state + 111111111;
        } else {
          if (input_count == 6) {
            s->b += (input[i + 4] | (input[i + 5] << 8)) + s->state + 11111111;
          } else {
            s->b += input[i + 4] + s->state + 1111111;
          }
        }
      }
    } else {
      if (input_count == 3) {
        s->a += (input[i] | (input[i + 1] << 8)
          | (input[i + 2] << 16)) + s->state + 111111;
      } else {
        if (input_count == 2) {
          s->a += (input[i] | (input[i + 1] << 8)) + s->state + 1111;
        } else {
          s->a += input[i] + s->state + 11;
        }
      }
    }
  }
}

void eightomic_finalize(struct eightomic_s *s) {
  s->a += s->_state;
  s->state += (s->a << 36) | (s->a >> 28);
  s->b += s->_state ^ s->state;
  s->state += (s->b << 38) | (s->b >> 26);
  s->c += s->_state + s->state;
  s->state += (s->c << 40) | (s->c >> 24);
  s->d += (s->a + s->b + s->c) ^ s->state;
  s->state += (s->d << 42) | (s->d >> 22);
  s->_state += s->state;
  s->b += s->a + s->state;
  s->state += (s->b << 28) | (s->b >> 36);
  s->c += s->b + (s->_state ^ s->state);
  s->state += (s->c << 30) | (s->c >> 34);
  s->d += s->c ^ (s->_state + s->state);
  s->state += (s->d << 34) | (s->d >> 30);
  s->a += s->_state;
  s->state += (s->a << 36) | (s->a >> 28);
  s->b += s->_state + s->state;
  s->state += (s->b << 38) | (s->b >> 26);
  s->c += s->_state ^ s->state;
  s->state += (s->c << 40) | (s->c >> 24);
  s->d += (s->a + s->b) ^ s->state;
  s->state += (s->d << 42) | (s->d >> 22);
  s->state = (s->c + s->d) ^ (s->_state + s->state);
}

Reference

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

s is a struct eightomic_s pointer.

eightomic_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. When hashing in split segments, the value must be a multiple of 32, with the exception of the end segment.

input is the const uint8_t array to hash.

s is a struct eightomic_s pointer.

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

s is a struct eightomic_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 64-bit non-cryptographic hashing algorithm is designed to hash keys of all sizes in data structures without hidden security issues such as excess collisions, hashDoS vulnerability, poor distribution and slow speeds.

It has speed properties similar to CityHash64 and SpookyHashV2 with security properties similar to SipHash.

It's portable for 64-bit systems. There's an alternative 32-bit hashing algorithm for 32-bit systems, although the 32-bit version is outperformed by the lower or upper 32-bits of the aformentioned 64-bit hashing algorithm.

It meets strict compliance, portability and security requirements.

Endian-agnostic memory reading is aligned safely using memcpy() with resistance to runtime byte order changes.

It doesn't use modulus, multiplication or division arithmetic operations.

It supports unlimited input length by splitting input bytes into descending segments of 256, 128, 64 and the remaining 8–63 bits. All-at-once hashing isn't required and the digest results are consistent when hashing in partial segments.

Single-threaded, instruction-level parallelism with low-cost addition and bitwise instructions work well on a wide range of CPU queue loads and devices.

The staggered additive constants, summed with s->a through s->d, eliminate any possible vulnerability to input elements with a 0 value.

Not allowing a seed secures the possibility of 2^32 deterministic attacks, so all seed-based tests were omitted.

It passes all extended SMHasher excessive torture tests that don't require a seed and it's likely to pass new tests as they're released.

Most of the tests passed beyond the default extended limit. For example, avalanche tests passed with 2000-bit, 3000-bit and 3501-bit inputs.

The high and low 32-bit segments pass extended tests as well.

It's compared with the fastest hashing algorithms that aren't dependent on compiler-specific or platform-specific optimizations with heavy macro usage.

Compared to CityHash64, the speed's approximately 6% faster on average for varying input lengths.

Furthermore, the low and high 32-bit segments in CityHash64 are lower in quality by a small margin, it relies on multiplication operations, bytes are processed more than once during alignment and there are derivatives from other hashing algorithms such as CRC and MurmurHash.

Compared to the lower 64 bits of the 128-bit MurmurHash3 variant, the speed's approximately 80% faster on average for varying input lengths without endian dependence, inline functions or undefined behavior from unaligned reads.

Compared to SipHash, the speed's at least 1000% faster on average with the similar absence of cryptanalytic vulnerabilities using 320 auxiliary bits of preimage attack security.

Compared to SpookyHashV2, the speed's 9% faster on average for varying input lengths without endian dependence, inline functions or unaligned memory reads.

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>
#include <stdio.h>
#include <string.h>

uint32_t align_32(const uint8_t *input, unsigned long i) {
  uint32_t _input = 0xFEFF;
  uint8_t byte_order;

  memcpy(&byte_order, &_input, sizeof(byte_order));
  memcpy(&_input, &input[i], sizeof(_input));

  if (byte_order != 0xFF) {
    _input = (_input << 24) | ((_input & 0xFF00) << 8)
      | ((_input & 0xFF0000) >> 8) | (_input >> 24);
  }

  return _input;
}

uint64_t align_64(const uint8_t *input, unsigned long i) {
  uint64_t _input = 0xFEFF;
  uint8_t byte_order;

  memcpy(&byte_order, &_input, sizeof(byte_order));
  memcpy(&_input, &input[i], sizeof(_input));

  if (byte_order != 0xFF) {
    _input = (_input << 56)
      | ((_input & 0xFF00) << 40)
      | ((_input & 0xFF0000) << 24)
      | ((_input & 0xFF000000) << 8)
      | ((_input & 0xFF00000000) >> 8)
      | ((_input & 0xFF0000000000) >> 24)
      | ((_input & 0xFF000000000000) >> 40)
      | (_input >> 56);
  }

  return _input;
}

uint64_t eightomic(unsigned long input_count, const uint8_t *input) {
  uint64_t _a;
  uint64_t _b;
  uint64_t _c;
  uint64_t _d;
  uint64_t a = 1;
  uint64_t b = 11;
  uint64_t c = 111;
  uint64_t d = 1111;
  uint64_t _state = 1111111111;
  uint64_t state = 11111111111;
  unsigned long i = 0;

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

    while (i < input_count) {
      _a = align_64(input, i - 7);
      _b = align_64(input, i - 15);
      _c = align_64(input, i - 23);
      _d = align_64(input, i - 31);
      state += _a + _b + _c + _d;
      a += _a + ((a << 30) | (a >> 34)) + state + 1;
      b += _b + ((b << 29) | (b >> 35)) + state + 11;
      c += _c + ((c << 28) | (c >> 36)) + 111;
      d += _d + ((d << 27) | (d >> 37)) + 1111;
      i += 32;
    }

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

    state += a + b + c + d;
    i++;
    input_count -= i;
  }

  if (input_count >= 16) {
    input_count -= 16;
    i += 16;
    _a = align_64(input, i - 16);
    _b = align_64(input, i - 8);
    state += _a + _b;
    a += _a + ((a << 30) | (a >> 34)) + state + 1;
    b += _b + ((b << 29) | (b >> 35)) + state + 11;
  }

  if (input_count >= 8) {
    input_count -= 8;
    i += 8;
    _a = align_64(input, i - 8);
    state += _a;
    a += _a + ((a << 30) | (a >> 34)) + state + 1;
  }

  if (input_count != 0) {
    state += ((a << 16) | (a >> 48)) + _state;

    if (input_count >= 4) {
      a += align_32(input, i) + state + 1111111111;

      if (input_count != 4) {
        _state += a + b;
        state += ((b << 20) | (b >> 44)) + _state;

        if (input_count == 7) {
          b += (input[i + 4] | (input[i + 5] << 8)
            | (input[i + 6] << 16)) + state + 111111111;
        } else {
          if (input_count == 6) {
            b += (input[i + 4] | (input[i + 5] << 8)) + state + 11111111;
          } else {
            b += input[i + 4] + state + 1111111;
          }
        }
      }
    } else {
      if (input_count == 3) {
        a += (input[i] | (input[i + 1] << 8)
          | (input[i + 2] << 16)) + state + 111111;
      } else {
        if (input_count == 2) {
          a += (input[i] | (input[i + 1] << 8)) + state + 1111;
        } else {
          a += input[i] + state + 11;
        }
      }
    }
  }

  a += _state;
  state += (a << 36) | (a >> 28);
  b += _state ^ state;
  state += (b << 38) | (b >> 26);
  c += _state + state;
  state += (c << 40) | (c >> 24);
  d += (a + b + c) ^ state;
  state += (d << 42) | (d >> 22);
  _state += state;
  b += a + state;
  state += (b << 28) | (b >> 36);
  c += b + (_state ^ state);
  state += (c << 30) | (c >> 34);
  d += c ^ (_state + state);
  state += (d << 34) | (d >> 30);
  a += _state;
  state += (a << 36) | (a >> 28);
  b += _state + state;
  state += (b << 38) | (b >> 26);
  c += _state ^ state;
  state += (c << 40) | (c >> 24);
  d += (a + b) ^ state;
  state += (d << 42) | (d >> 22);
  return (c + d) ^ (_state + state);
}

Games

Contrivity

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

v1.0.14