summaryrefslogtreecommitdiffstats
path: root/src/contrib/toeplitz.h
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 15:24:08 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 15:24:08 +0000
commitf449f278dd3c70e479a035f50a9bb817a9b433ba (patch)
tree8ca2bfb785dda9bb4d573acdf9b42aea9cd51383 /src/contrib/toeplitz.h
parentInitial commit. (diff)
downloadknot-upstream/3.2.6.tar.xz
knot-upstream/3.2.6.zip
Adding upstream version 3.2.6.upstream/3.2.6upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/contrib/toeplitz.h')
-rw-r--r--src/contrib/toeplitz.h122
1 files changed, 122 insertions, 0 deletions
diff --git a/src/contrib/toeplitz.h b/src/contrib/toeplitz.h
new file mode 100644
index 0000000..02974d2
--- /dev/null
+++ b/src/contrib/toeplitz.h
@@ -0,0 +1,122 @@
+/* Copyright (C) 2022 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <https://www.gnu.org/licenses/>.
+ */
+
+/*!
+ * \brief Microsoft Toeplitz-based hash implementation
+ */
+
+#pragma once
+
+#include <assert.h>
+#include <stdint.h>
+
+#include "libknot/endian.h"
+
+/*!
+ * \brief Computes a Toeplitz hash value for given key and data.
+ *
+ * \param key Key vector
+ * \param key_len Length of the key vector in bytes.
+ * \param data Input data to compute hash from.
+ * \param data_len Lenght of the input data in bytes.
+ *
+ * \return A Toeplitz hash value.
+ */
+inline static uint32_t toeplitz_hash(const uint8_t *key, const size_t key_len,
+ const uint8_t *data, const size_t data_len)
+{
+ assert(key_len >= 4 + 2 * (16 + 2));
+
+ uint32_t key32 = be32toh(*(const uint32_t *)key);
+ key += sizeof(uint32_t);
+
+ int ret = 0;
+
+ for (int i = 0; i < data_len; i++) {
+ for (int bit = 7; bit >= 0; bit--) {
+ if (data[i] & (1 << bit)) {
+ ret ^= key32;
+ }
+
+ key32 <<= 1;
+ key32 |= !!(key[0] & (1 << bit));
+ }
+ key++;
+ }
+
+ return ret;
+}
+
+/*!
+ * \brief Toeplitz hash context for divided processing.
+ */
+typedef struct {
+ const uint8_t *data;
+ const uint8_t *data_end;
+ const uint8_t *key;
+ uint32_t hash;
+ uint32_t key32;
+} toeplitz_ctx_t;
+
+inline static void toeplitz_init(toeplitz_ctx_t *ctx, uint8_t count,
+ const uint8_t *key, const uint8_t key_len,
+ const uint8_t *data, const uint8_t data_len)
+{
+ assert(key_len >= 40);
+
+ ctx->data = data;
+ ctx->data_end = data + data_len;
+ ctx->key = key + sizeof(uint32_t);
+ ctx->hash = 0;
+ ctx->key32 = be32toh(*(const uint32_t *)key);
+
+ const uint8_t *stop = ctx->data + count;
+ assert(stop <= ctx->data_end);
+
+ while (ctx->data < stop) {
+ for (int bit = 7; bit >= 0; bit--) {
+ if (*ctx->data & (1 << bit)) {
+ ctx->hash ^= ctx->key32;
+ }
+
+ ctx->key32 <<= 1;
+ ctx->key32 |= !!(*ctx->key & (1 << bit));
+ }
+ ctx->data++;
+ ctx->key++;
+ }
+}
+
+inline static uint32_t toeplitz_finish(toeplitz_ctx_t *ctx)
+{
+ uint32_t hash = ctx->hash;
+ uint32_t key32 = ctx->key32;
+ const uint8_t *key = ctx->key;
+
+ for (const uint8_t *in = ctx->data; in < ctx->data_end; in++) {
+ for (int bit = 7; bit >= 0; bit--) {
+ if (*in & (1 << bit)) {
+ hash ^= key32;
+ }
+
+ key32 <<= 1;
+ key32 |= !!(*key & (1 << bit));
+ }
+ key++;
+ }
+
+ return hash;
+}