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;
+}