Improve digest

4 files changed, 195 insertions, 13 deletions

diff --git a/test/digest_test.c b/test/digest_test.c
new file mode 100644
index 0000000..a4b2dc9
--- /dev/null
+++ b/test/digest_test.c
@@ -0,0 +1,91 @@
+/*
+  Copyright 2020 David Robillard <http://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
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#undef NDEBUG
+
+#include "zix/digest.h"
+
+#include <assert.h>
+#include <stddef.h>
+
+static void
+test_bytes(void)
+{
+	static const uint8_t data[] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+	for (size_t offset = 0; offset < 7; ++offset) {
+		const size_t len = 8 - offset;
+
+		uint32_t d = zix_digest_start();
+		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;
+		}
+
+		assert(zix_digest_add(zix_digest_start(), &data[offset], len) == d);
+	}
+}
+
+static void
+test_64(void)
+{
+	static const uint64_t data[] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+	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;
+	}
+
+	assert(zix_digest_add(zix_digest_start(), data, 8 * sizeof(uint64_t)) == d);
+}
+
+static void
+test_ptr(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;
+	}
+
+	assert(zix_digest_add(zix_digest_start(), data, 8 * sizeof(void*)) == d);
+}
+
+int
+main(void)
+{
+	test_bytes();
+	test_64();
+	test_ptr();
+
+	return 0;
+}
diff --git a/wscript b/wscript
index 858bd51..f7854ae 100644
--- a/wscript
+++ b/wscript
@@ -123,6 +123,7 @@ sources = [
 ]
 
 tests = [
+    'digest_test',
     'hash_test',
     'inline_test',
     'patree_test',
diff --git a/zix/digest.c b/zix/digest.c
index d6ceb0e..4fc7608 100644
--- a/zix/digest.c
+++ b/zix/digest.c
@@ -1,5 +1,5 @@
 /*
-  Copyright 2012-2014 David Robillard <http://drobilla.net>
+  Copyright 2012-2020 David Robillard <http://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
@@ -20,23 +20,29 @@
 #    include <smmintrin.h>
 #endif
 
+#include <assert.h>
+#include <stdint.h>
+
+#ifdef __SSE4_2__
+
+// SSE 4.2 CRC32
+
 ZIX_API uint32_t
 zix_digest_start(void)
 {
-#ifdef __SSE4_2__
-	return 1;  // CRC32 initial value
-#else
-	return 5381;  // DJB hash initial value
-#endif
+	return 1;
 }
 
 ZIX_API uint32_t
 zix_digest_add(uint32_t hash, const void* const buf, const size_t len)
 {
 	const uint8_t* str = (const uint8_t*)buf;
-#ifdef __SSE4_2__
-	// SSE 4.2 CRC32
-	for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) {
+
+	for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) {
+		hash = (uint32_t)_mm_crc32_u64(hash, *(const uint64_t*)str);
+		str += sizeof(uint64_t);
+	}
+	if (len & sizeof(uint32_t)) {
 		hash = _mm_crc32_u32(hash, *(const uint32_t*)str);
 		str += sizeof(uint32_t);
 	}
@@ -47,11 +53,71 @@ zix_digest_add(uint32_t hash, const void* const buf, const size_t len)
 	if (len & sizeof(uint8_t)) {
 		hash = _mm_crc32_u8(hash, *(const uint8_t*)str);
 	}
+
+	return hash;
+}
+
+ZIX_API uint32_t
+zix_digest_add_64(uint32_t hash, const void* const buf, const size_t len)
+{
+	assert((uintptr_t)buf % sizeof(uint64_t) == 0);
+	assert(len % sizeof(uint64_t) == 0);
+
+	const uint64_t* ptr = (const uint64_t*)buf;
+
+	for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) {
+		hash = (uint32_t)_mm_crc32_u64(hash, *ptr);
+		++ptr;
+	}
+
+	return hash;
+}
+
+ZIX_API uint32_t
+zix_digest_add_ptr(const uint32_t hash, const void* const ptr)
+{
+#if UINTPTR_MAX == UINT64_MAX
+	return (uint32_t)_mm_crc32_u64(hash, (uintptr_t)ptr);
+#else
+	return _mm_crc32_u32(hash, (uintptr_t)ptr);
+#endif
+}
+
 #else
-	// Classic DJB hash
+
+// Classic DJB hash
+
+ZIX_API uint32_t
+zix_digest_start(void)
+{
+	return 5381;
+}
+
+ZIX_API uint32_t
+zix_digest_add(uint32_t hash, const void* const buf, const size_t len)
+{
+	const uint8_t* str = (const uint8_t*)buf;
+
 	for (size_t i = 0; i < len; ++i) {
-		hash = (hash << 5u) + hash + str[i];
+		hash = (hash << 5) + hash + str[i];
 	}
-#endif
+
 	return hash;
 }
+
+ZIX_API uint32_t
+zix_digest_add_64(uint32_t hash, const void* const buf, const size_t len)
+{
+	assert((uintptr_t)buf % sizeof(uint64_t) == 0);
+	assert(len % sizeof(uint64_t) == 0);
+
+	return zix_digest_add(hash, buf, len);
+}
+
+ZIX_API uint32_t
+zix_digest_add_ptr(const uint32_t hash, const void* const ptr)
+{
+	return zix_digest_add(hash, &ptr, sizeof(ptr));
+}
+
+#endif
diff --git a/zix/digest.h b/zix/digest.h
index 264c918..16ba9b9 100644
--- a/zix/digest.h
+++ b/zix/digest.h
@@ -1,5 +1,5 @@
 /*
-  Copyright 2012 David Robillard <http://drobilla.net>
+  Copyright 2012-2020 David Robillard <http://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,12 +26,36 @@
 extern "C" {
 #endif
 
+/**
+   Return an initial empty digest value.
+*/
 ZIX_API uint32_t
 zix_digest_start(void);
 
+/**
+   Update `hash` to include `buf`, a buffer of `len` bytes.
+
+   This can be used for any size or alignment.
+*/
 ZIX_API uint32_t
 zix_digest_add(uint32_t hash, const void* buf, size_t len);
 
+/**
+   Update `hash` to include `buf`, a 64-bit aligned buffer of `len` bytes.
+
+   Both `buf` and `len` must be evenly divisible by 8 (64 bits).
+*/
+ZIX_API uint32_t
+zix_digest_add_64(uint32_t hash, const void* buf, size_t len);
+
+/**
+   Update `hash` to include `ptr`.
+
+   This hashes the value of the pointer itself, and does not dereference `ptr`.
+*/
+ZIX_API uint32_t
+zix_digest_add_ptr(uint32_t hash, const void* ptr);
+
 #ifdef __cplusplus
 }  /* extern "C" */
 #endif