Replace CRC32 digest with more modern and appropriate algorithms

This makes the hassle of platform-specific code go away, and instead uses
portable implementations of relatively standard modern hash algorithms.  CRC32
is not great as a hash function anyway, though it is very fast when hardware
accelerated.

5 files changed, 324 insertions, 157 deletions

diff --git a/benchmark/dict_bench.c b/benchmark/dict_bench.c
index 3ba33f9..952aae3 100644
--- a/benchmark/dict_bench.c
+++ b/benchmark/dict_bench.c
@@ -52,7 +52,7 @@ lcg64(const uint64_t i)
 static uint32_t
 zix_chunk_hash(const ZixChunk* const chunk)
 {
-  return zix_digest_add(zix_digest_start(), chunk->buf, chunk->len);
+  return zix_digest32(0u, chunk->buf, chunk->len);
 }
 
 static bool
diff --git a/include/zix/digest.h b/include/zix/digest.h
index 41db20f..6df7002 100644
--- a/include/zix/digest.h
+++ b/include/zix/digest.h
@@ -1,5 +1,5 @@
 /*
-  Copyright 2012-2020 David Robillard <d@drobilla.net>
+  Copyright 2012-2021 David Robillard <d@drobilla.net>
 
   Permission to use, copy, modify, and/or distribute this software for any
   purpose with or without fee is hereby granted, provided that the above
@@ -26,37 +26,81 @@
 extern "C" {
 #endif
 
-/// Return an initial empty digest value
-ZIX_CONST_API
-uint32_t
-zix_digest_start(void);
+/**
+   @addtogroup zix
+   @{
+   @name Digest
+   Functions to generate a short "digest" of data with minimal collisions.
+
+   These are good general-purpose hash functions for indexing arbitrary data,
+   but are not necessarily stable across platforms and should never be used for
+   cryptographic purposes.
+   @{
+*/
 
 /**
-   Update `hash` to include `buf`, a buffer of `len` bytes.
+   Return a 32-bit hash of a buffer.
 
    This can be used for any size or alignment.
 */
 ZIX_PURE_API
 uint32_t
-zix_digest_add(uint32_t hash, const void* buf, size_t len);
+zix_digest32(uint32_t seed, const void* buf, size_t len);
 
 /**
-   Update `hash` to include `buf`, a 64-bit aligned buffer of `len` bytes.
+   Return a 32-bit hash of an aligned buffer.
 
-   Both `buf` and `len` must be evenly divisible by 8 (64 bits).
+   Both the buffer and size must be aligned to 32 bits.  For data that fits
+   these requirements, this is equivalent to, but faster than, zix_digest32().
 */
 ZIX_PURE_API
 uint32_t
-zix_digest_add_64(uint32_t hash, const void* buf, size_t len);
+zix_digest32_aligned(uint32_t seed, const void* buf, size_t len);
 
 /**
-   Update `hash` to include `ptr`.
+   Return a 64-bit hash of a buffer.
 
-   This hashes the value of the pointer itself, and does not dereference `ptr`.
+   This can be used for any size or alignment.
 */
-ZIX_CONST_API
-uint32_t
-zix_digest_add_ptr(uint32_t hash, const void* ptr);
+ZIX_PURE_API
+uint64_t
+zix_digest64(uint64_t seed, const void* buf, size_t len);
+
+/**
+   Return a 64-bit hash of an aligned buffer.
+
+   Both the buffer and size must be aligned to 64 bits.  For data that fits
+   these requirements, this is equivalent to, but faster than, zix_digest64().
+*/
+ZIX_PURE_API
+uint64_t
+zix_digest64_aligned(uint64_t seed, const void* buf, size_t len);
+
+/**
+   Return a pointer-sized hash of a buffer.
+
+   This can be used for any size or alignment.
+
+   Internally, this simply dispatches to zix_digest32() or zix_digest64() as
+   appropriate.
+*/
+ZIX_PURE_API
+size_t
+zix_digest(size_t seed, const void* buf, size_t len);
+
+/**
+   Return a pointer-sized hash of an aligned buffer.
+
+   Both the buffer and size must be aligned to the pointer size.  For data that
+   fits these requirements, this is equivalent to, but faster than,
+   zix_digest().
+
+   Internally, this simply dispatches to zix_digest32_aligned() or
+   zix_digest64_aligned() as appropriate.
+*/
+ZIX_PURE_API
+size_t
+zix_digest_aligned(size_t seed, const void* buf, size_t len);
 
 #ifdef __cplusplus
 } /* extern "C" */
diff --git a/src/digest.c b/src/digest.c
index c14a3f5..32cae63 100644
--- a/src/digest.c
+++ b/src/digest.c
@@ -1,5 +1,5 @@
 /*
-  Copyright 2012-2020 David Robillard <d@drobilla.net>
+  Copyright 2012-2021 David Robillard <d@drobilla.net>
 
   Permission to use, copy, modify, and/or distribute this software for any
   purpose with or without fee is hereby granted, provided that the above
@@ -16,150 +16,222 @@
 
 #include "zix/digest.h"
 
-#ifdef __SSE4_2__
-#  include <smmintrin.h>
-#endif
-
 #include <assert.h>
 #include <stdint.h>
+#include <string.h>
 
-#ifdef __SSE4_2__
-
-// SSE 4.2 CRC32
+#if defined(__clang__) && __clang_major__ >= 12
+#  define FALLTHROUGH() __attribute__((fallthrough))
+#elif defined(__GNUC__) && !defined(__clang__)
+#  define FALLTHROUGH() __attribute__((fallthrough))
+#else
+#  define FALLTHROUGH()
+#endif
 
-uint32_t
-zix_digest_start(void)
-{
-  return 1;
-}
+/*
+  64-bit hash: Essentially fasthash64, implemented here in an aligned/padded
+  and a general UB-free variant.
+*/
 
 static inline uint64_t
-load64(const void* const mem)
+mix64(uint64_t h)
 {
-  uint64_t r = 0u;
-  memcpy(&r, mem, sizeof(r));
-  return r;
+  h ^= h >> 23u;
+  h *= 0x2127599BF4325C37ull;
+  h ^= h >> 47u;
+  return h;
 }
 
-static inline uint32_t
-load32(const void* const mem)
+uint64_t
+zix_digest64(const uint64_t seed, const void* const key, const size_t len)
 {
-  uint32_t r = 0u;
-  memcpy(&r, mem, sizeof(r));
-  return r;
-}
+  static const uint64_t m = 0x880355F21E6D1965ull;
 
-static inline uint16_t
-load16(const void* const mem)
-{
-  uint16_t r = 0u;
-  memcpy(&r, mem, sizeof(r));
-  return r;
-}
+  const size_t         n_blocks   = len / sizeof(uint64_t);
+  const uint8_t* const data       = (const uint8_t*)key;
+  const uint8_t* const blocks_end = data + (n_blocks * sizeof(uint64_t));
 
-uint32_t
-zix_digest_add(uint32_t hash, const void* const buf, const size_t len)
-{
-  const uint8_t* str = (const uint8_t*)buf;
+  uint64_t h = seed ^ (len * m);
+  for (size_t i = 0u; i < n_blocks; ++i) {
+    uint64_t k = 0u;
+    memcpy(&k, data, sizeof(uint64_t));
 
-#  ifdef __x86_64__
-  for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) {
-    hash = (uint32_t)_mm_crc32_u64(hash, load64(str));
-    str += sizeof(uint64_t);
-  }
-  if (len & sizeof(uint32_t)) {
-    hash = _mm_crc32_u32(hash, load32(str));
-    str += sizeof(uint32_t);
-  }
-#  else
-  for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) {
-    hash = _mm_crc32_u32(hash, load32(str));
-    str += sizeof(uint32_t);
+    h ^= mix64(k);
+    h *= m;
   }
-#  endif
-  if (len & sizeof(uint16_t)) {
-    hash = _mm_crc32_u16(hash, load16(str));
-    str += sizeof(uint16_t);
-  }
-  if (len & sizeof(uint8_t)) {
-    hash = _mm_crc32_u8(hash, *str);
+
+  const uint8_t* const tail = blocks_end;
+  uint64_t             v    = 0u;
+
+  switch (len & 7u) {
+  case 7:
+    v |= (uint64_t)tail[6] << 48u;
+    FALLTHROUGH();
+  case 6:
+    v |= (uint64_t)tail[5] << 40u;
+    FALLTHROUGH();
+  case 5:
+    v |= (uint64_t)tail[4] << 32u;
+    FALLTHROUGH();
+  case 4:
+    v |= (uint64_t)tail[3] << 24u;
+    FALLTHROUGH();
+  case 3:
+    v |= (uint64_t)tail[2] << 16u;
+    FALLTHROUGH();
+  case 2:
+    v |= (uint64_t)tail[1] << 8u;
+    FALLTHROUGH();
+  case 1:
+    v |= (uint64_t)tail[0];
+
+    h ^= mix64(v);
+    h *= m;
   }
 
-  return hash;
+  return mix64(h);
 }
 
-uint32_t
-zix_digest_add_64(uint32_t hash, const void* const buf, const size_t len)
+uint64_t
+zix_digest64_aligned(const uint64_t seed, const void* const key, size_t len)
 {
-  assert((uintptr_t)buf % sizeof(uint64_t) == 0);
-  assert(len % sizeof(uint64_t) == 0);
+  static const uint64_t m = 0x880355F21E6D1965ull;
 
-#  ifdef __x86_64__
-  const uint64_t* ptr = (const uint64_t*)buf;
+  assert((uintptr_t)key % sizeof(uint64_t) == 0u);
+  assert(len % sizeof(uint64_t) == 0u);
 
-  for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) {
-    hash = (uint32_t)_mm_crc32_u64(hash, *ptr);
-    ++ptr;
-  }
-
-  return hash;
-#  else
-  const uint32_t* ptr = (const uint32_t*)buf;
+  const uint64_t* const blocks   = (const uint64_t*)key;
+  const size_t          n_blocks = len / sizeof(uint64_t);
+  uint64_t              h        = seed ^ (len * m);
 
-  for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) {
-    hash = _mm_crc32_u32(hash, *ptr);
-    ++ptr;
+  for (size_t i = 0u; i < n_blocks; ++i) {
+    h ^= mix64(blocks[i]);
+    h *= m;
   }
 
-  return hash;
-#  endif
+  return mix64(h);
 }
 
-uint32_t
-zix_digest_add_ptr(const uint32_t hash, const void* const ptr)
-{
-#  ifdef __x86_64__
-  return (uint32_t)_mm_crc32_u64(hash, (uintptr_t)ptr);
-#  else
-  return _mm_crc32_u32(hash, (uintptr_t)ptr);
-#  endif
-}
+/*
+  32-bit hash: Essentially murmur3, reimplemented here in an aligned/padded and
+  a general UB-free variant.
+*/
 
-#else
+/**
+   Rotate left by some count of bits.
 
-// Classic DJB hash
+   This is recognized by any halfway decent compiler and compiled to a single
+   instruction on architectures that have one.
+*/
+static inline uint32_t
+rotl32(const uint32_t val, const uint32_t bits)
+{
+  return ((val << bits) | (val >> (32 - bits)));
+}
 
-uint32_t
-zix_digest_start(void)
+static inline uint32_t
+mix32(uint32_t h)
 {
-  return 5381;
+  h ^= h >> 16u;
+  h *= 0x85EBCA6Bu;
+  h ^= h >> 13u;
+  h *= 0xC2B2AE35u;
+  h ^= h >> 16u;
+  return h;
 }
 
 uint32_t
-zix_digest_add(uint32_t hash, const void* const buf, const size_t len)
+zix_digest32(const uint32_t seed, const void* const key, const size_t len)
 {
-  const uint8_t* str = (const uint8_t*)buf;
+  static const uint32_t c1 = 0xCC9E2D51u;
+  static const uint32_t c2 = 0x1B873593u;
+
+  // Process as many 32-bit blocks as possible
+  const size_t         n_blocks   = len / sizeof(uint32_t);
+  const uint8_t*       data       = (const uint8_t*)key;
+  const uint8_t* const blocks_end = data + (n_blocks * sizeof(uint32_t));
+  uint32_t             h          = seed;
+  for (; data != blocks_end; data += sizeof(uint32_t)) {
+    uint32_t k = 0u;
+    memcpy(&k, data, sizeof(uint32_t));
+
+    k *= c1;
+    k = rotl32(k, 15);
+    k *= c2;
+
+    h ^= k;
+    h = rotl32(h, 13);
+    h = h * 5u + 0xE6546B64u;
+  }
 
-  for (size_t i = 0; i < len; ++i) {
-    hash = (hash << 5u) + hash + str[i];
+  // Process any trailing bytes
+  uint32_t k = 0u;
+  switch (len & 3u) {
+  case 3u:
+    k ^= (uint32_t)data[2u] << 16u;
+    FALLTHROUGH();
+  case 2u:
+    k ^= (uint32_t)data[1u] << 8u;
+    FALLTHROUGH();
+  case 1u:
+    k ^= (uint32_t)data[0u];
+
+    k *= c1;
+    k = rotl32(k, 15u);
+    k *= c2;
+    h ^= k;
   }
 
-  return hash;
+  return mix32(h ^ (uint32_t)len);
 }
 
 uint32_t
-zix_digest_add_64(uint32_t hash, const void* const buf, const size_t len)
+zix_digest32_aligned(const uint32_t    seed,
+                     const void* const key,
+                     const size_t      len)
 {
-  assert((uintptr_t)buf % sizeof(uint64_t) == 0);
-  assert(len % sizeof(uint64_t) == 0);
+  static const uint32_t c1 = 0xCC9E2D51u;
+  static const uint32_t c2 = 0x1B873593u;
 
-  return zix_digest_add(hash, buf, len);
+  assert((uintptr_t)key % sizeof(uint32_t) == 0u);
+  assert(len % sizeof(uint32_t) == 0u);
+
+  const uint32_t* const blocks   = (const uint32_t*)key;
+  const size_t          n_blocks = len / sizeof(uint32_t);
+  uint32_t              h        = seed;
+  for (size_t i = 0u; i < n_blocks; ++i) {
+    uint32_t k = blocks[i];
+
+    k *= c1;
+    k = rotl32(k, 15);
+    k *= c2;
+
+    h ^= k;
+    h = rotl32(h, 13);
+    h = h * 5u + 0xE6546B64u;
+  }
+
+  return mix32(h ^ (uint32_t)len);
 }
 
-uint32_t
-zix_digest_add_ptr(const uint32_t hash, const void* const ptr)
+// Native word size wrapper
+
+size_t
+zix_digest(const size_t seed, const void* const buf, const size_t len)
 {
-  return zix_digest_add(hash, &ptr, sizeof(ptr));
+#if UINTPTR_MAX >= UINT64_MAX
+  return zix_digest64(seed, buf, len);
+#else
+  return zix_digest32(seed, buf, len);
+#endif
 }
 
+size_t
+zix_digest_aligned(const size_t seed, const void* const buf, const size_t len)
+{
+#if UINTPTR_MAX >= UINT64_MAX
+  return zix_digest64_aligned(seed, buf, len);
+#else
+  return zix_digest32_aligned(seed, buf, len);
 #endif
+}
diff --git a/test/digest_test.c b/test/digest_test.c
index 3ed5aff..75dc8ff 100644
--- a/test/digest_test.c
+++ b/test/digest_test.c
@@ -1,5 +1,5 @@
 /*
-  Copyright 2020 David Robillard <d@drobilla.net>
+  Copyright 2020-2021 David Robillard <d@drobilla.net>
 
   Permission to use, copy, modify, and/or distribute this software for any
   purpose with or without fee is hereby granted, provided that the above
@@ -21,71 +21,122 @@
 #include <assert.h>
 #include <stddef.h>
 
+// Just basic smoke tests to ensure the hash functions are reacting to data
+
 static void
-test_bytes(void)
+test_digest(void)
 {
-  static const uint8_t data[] = {1, 2, 3, 4, 5, 6, 7, 8};
+  static const uint8_t data[] = {
+    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
 
-  for (size_t offset = 0; offset < 7; ++offset) {
-    const size_t len = 8 - offset;
+  size_t last = 0u;
 
-    uint32_t d = zix_digest_start();
+  for (size_t offset = 0; offset < 7; ++offset) {
+    const size_t len = 8u - offset;
     for (size_t i = offset; i < 8; ++i) {
-      const uint32_t new_d = zix_digest_add(d, &data[i], 1);
-      assert(new_d != d);
-      d = new_d;
+      const size_t h = zix_digest(0u, &data[i], len);
+      assert(h != last);
+      last = h;
     }
+  }
+}
+
+static void
+test_digest32(void)
+{
+  static const uint8_t data[] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  uint32_t last = 0u;
 
-    assert(zix_digest_add(zix_digest_start(), &data[offset], len) == d);
+  for (size_t offset = 0; offset < 3; ++offset) {
+    for (size_t i = offset; i < 4; ++i) {
+      const uint32_t h = zix_digest32(0u, &data[i], 4);
+      assert(h != last);
+      last = h;
+    }
   }
 }
 
 static void
-test_64(void)
+test_digest64(void)
 {
-  static const uint64_t data[] = {1, 2, 3, 4, 5, 6, 7, 8};
+  static const uint8_t data[] = {
+    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
+
+  uint64_t last = 0u;
 
-  uint32_t d = zix_digest_start();
-  for (size_t i = 0; i < 8; ++i) {
-    const uint32_t new_d = zix_digest_add_64(d, &data[i], sizeof(uint64_t));
-    assert(new_d != d);
-    d = new_d;
+  for (size_t offset = 0; offset < 7; ++offset) {
+    for (size_t i = offset; i < 8; ++i) {
+      const uint64_t h = zix_digest64(0u, &data[i], 8);
+      assert(h != last);
+      last = h;
+    }
   }
+}
 
-  assert(zix_digest_add(zix_digest_start(), data, 8 * sizeof(uint64_t)) == d);
+static void
+test_digest32_aligned(void)
+{
+  static const uint32_t data[] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  uint32_t last = 0u;
+
+  for (size_t offset = 0; offset < 3; ++offset) {
+    const size_t len = 4u - offset;
+    for (size_t i = offset; i < 4; ++i) {
+      const uint32_t h =
+        zix_digest32_aligned(0u, &data[i], len * sizeof(uint32_t));
+      assert(h != last);
+      last = h;
+    }
+  }
 }
 
 static void
-test_ptr(void)
+test_digest64_aligned(void)
 {
-  static const uint64_t pointees[] = {1, 2, 3, 4, 5, 6, 7, 8};
-
-  static const void* data[] = {&pointees[0],
-                               &pointees[1],
-                               &pointees[2],
-                               &pointees[3],
-                               &pointees[4],
-                               &pointees[5],
-                               &pointees[6],
-                               &pointees[7],
-                               &pointees[8]};
-
-  uint32_t d = zix_digest_start();
-  for (size_t i = 0; i < 8; ++i) {
-    const uint32_t new_d = zix_digest_add_ptr(d, data[i]);
-    assert(new_d != d);
-    d = new_d;
+  static const uint64_t data[] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  uint64_t last = 0u;
+
+  for (size_t offset = 0; offset < 3; ++offset) {
+    const size_t len = 4u - offset;
+    for (size_t i = offset; i < 4; ++i) {
+      const uint64_t h =
+        zix_digest64_aligned(0u, &data[i], len * sizeof(uint64_t));
+      assert(h != last);
+      last = h;
+    }
   }
+}
+
+static void
+test_digest_aligned(void)
+{
+  static const size_t data[] = {1, 2, 3, 4, 5, 6, 7, 8};
 
-  assert(zix_digest_add(zix_digest_start(), data, 8 * sizeof(void*)) == d);
+  size_t last = 0u;
+
+  for (size_t offset = 0; offset < 3; ++offset) {
+    const size_t len = 4u - offset;
+    for (size_t i = offset; i < 4; ++i) {
+      const size_t h = zix_digest_aligned(0u, &data[i], len * sizeof(size_t));
+      assert(h != last);
+      last = h;
+    }
+  }
 }
 
 ZIX_PURE_FUNC int
 main(void)
 {
-  test_bytes();
-  test_64();
-  test_ptr();
+  test_digest32();
+  test_digest64();
+  test_digest();
+
+  test_digest32_aligned();
+  test_digest64_aligned();
+  test_digest_aligned();
 
   return 0;
 }
diff --git a/test/hash_test.c b/test/hash_test.c
index 00f1bce..d82b76a 100644
--- a/test/hash_test.c
+++ b/test/hash_test.c
@@ -77,7 +77,7 @@ string_ptr_hash(const void* value)
 {
   const char* const str = *(const char* const*)value;
 
-  return zix_digest_add(zix_digest_start(), str, strlen(str));
+  return zix_digest32(0u, str, strlen(str));
 }
 
 static bool