From b045529c40c83601909dca7b76a53498e9a70f33 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 10 Apr 2024 21:05:44 +0200 Subject: Adding upstream version 3.3.4. Signed-off-by: Daniel Baumann --- src/contrib/toeplitz.h | 122 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 122 insertions(+) create mode 100644 src/contrib/toeplitz.h (limited to 'src/contrib/toeplitz.h') 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. + + 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 . + */ + +/*! + * \brief Microsoft Toeplitz-based hash implementation + */ + +#pragma once + +#include +#include + +#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; +} -- cgit v1.2.3