summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--test/digest_test.c91
-rw-r--r--wscript1
-rw-r--r--zix/digest.c90
-rw-r--r--zix/digest.h26
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
generated by cgit v1.2.1 (git 2.18.0) at 2025-02-09 13:21:49 +0000