[PATCH v6] hash: add XOR32 hash function
Mattias Rönnblom
hofors at lysator.liu.se
Sat Jun 17 22:34:39 CEST 2023
On 2023-06-16 19:15, Bili Dong wrote:
> Thanks Vladimir for your suggestion! Indeed your version looks cleaner.
>
> I will make the changes (including the new test case you mentioned) and
> prepare a new version this weekend.
>
> Regards,
> Bili
>
> On Thu, Jun 15, 2023 at 10:15 AM Vladimir Medvedkin
> <medvedkinv at gmail.com <mailto:medvedkinv at gmail.com>> wrote:
>
> Hi Bili,
>
> The rte_hash_xor32() implementation looks a bit messy with respect
> to byte ordering, i.e. in case when data_len >= 8 init_val is byte
> swapped, but in other cases the data is byte swapped.
> Maybe it could be implemented like:
>
> static inline uint32_t
> rte_hash_xor32(const void *data, uint32_t data_len, uint32_t init_val)
> {
> const uint8_t *data8 = data;
> uint64_t hash64 = 0;
> uint32_t hash32;
> unsigned int i;
>
> for (i = 0; i < data_len / 8; i++) {
> hash64 ^= *(const uint64_t *)data8;
This statement assumes the data is 8-byte aligned.
If you change it to something like:
uint64_t v;
memcpy(&v, data8, sizeof(v));
hash64 ^= v;
the compiler will generate code which works without any particular input
buffer alignment requirements.
The same for 32- and 16-bit accesses.
You could also skip the "data8" pointer, and use the DPDK macros for
pointer arithmetic (e.g., RTE_PTR_ADD()) to manipulate the original
"data" pointer instead.
> data8 += 8;
> }
>
> if (data_len & 0x4) {
> hash64 ^= *(const uint32_t *)data8;
> data8 += 4;
> }
>
> int bit_offset = 0;
>
> if (data_len & 0x2) {
> hash64 ^= *(const uint16_t *)data8;
> bit_offset = 16;
> data8 += 2;
> }
>
> if (data_len & 0x1)
> hash64 ^= *(const uint8_t *)data8 << bit_offset;
>
> hash32 = (hash64 >> 32) ^ (uint32_t)hash64;
>
> return rte_be_to_cpu_32(hash32) ^ init_val;
> }
>
> What do you think?
>
> Also, consider to check in hash_functions_autotest keys with length
> equal to 3 (or eq 3 mod 4, for example 7 or 11)
>
> вт, 21 февр. 2023 г. в 19:37, Bili Dong <qobilidop at gmail.com
> <mailto:qobilidop at gmail.com>>:
>
> An XOR32 hash is needed in the Software Switch (SWX) Pipeline
> for its
> use case in P4. We implement it in this patch so it could be easily
> registered in the pipeline later.
>
> Signed-off-by: Bili Dong <qobilidop at gmail.com
> <mailto:qobilidop at gmail.com>>
> ---
> .mailmap | 1 +
> app/test/test_hash_functions.c | 33 +++++++++++--
> lib/hash/rte_hash_xor.h | 87
> ++++++++++++++++++++++++++++++++++
> 3 files changed, 118 insertions(+), 3 deletions(-)
> create mode 100644 lib/hash/rte_hash_xor.h
>
> diff --git a/.mailmap b/.mailmap
> index a9f4f28fba..3e9bec29d5 100644
> --- a/.mailmap
> +++ b/.mailmap
> @@ -159,6 +159,7 @@ Bernard Iremonger
> <bernard.iremonger at intel.com <mailto:bernard.iremonger at intel.com>>
> Bert van Leeuwen <bert.vanleeuwen at netronome.com
> <mailto:bert.vanleeuwen at netronome.com>>
> Bhagyada Modali <bhagyada.modali at amd.com
> <mailto:bhagyada.modali at amd.com>>
> Bharat Mota <bmota at vmware.com <mailto:bmota at vmware.com>>
> +Bili Dong <qobilidop at gmail.com <mailto:qobilidop at gmail.com>>
> Bill Hong <bhong at brocade.com <mailto:bhong at brocade.com>>
> Billy McFall <bmcfall at redhat.com <mailto:bmcfall at redhat.com>>
> Billy O'Mahony <billy.o.mahony at intel.com
> <mailto:billy.o.mahony at intel.com>>
> diff --git a/app/test/test_hash_functions.c
> b/app/test/test_hash_functions.c
> index 76d51b6e71..53e296fec4 100644
> --- a/app/test/test_hash_functions.c
> +++ b/app/test/test_hash_functions.c
> @@ -15,6 +15,7 @@
> #include <rte_hash.h>
> #include <rte_jhash.h>
> #include <rte_hash_crc.h>
> +#include <rte_hash_xor.h>
>
> #include "test.h"
>
> @@ -22,8 +23,8 @@
> * Hash values calculated for key sizes from array
> "hashtest_key_lens"
> * and for initial values from array "hashtest_initvals.
> * Each key will be formed by increasing each byte by 1:
> - * e.g.: key size = 4, key = 0x03020100
> - * key size = 8, key = 0x0706050403020100
> + * e.g.: key size = 4, key = 0x00010203
> + * key size = 8, key = 0x0001020304050607
> */
> static uint32_t hash_values_jhash[2][12] = {{
> 0x8ba9414b, 0xdf0d39c9,
> @@ -51,6 +52,19 @@ static uint32_t hash_values_crc[2][12] = {{
> 0x789c104f, 0x53028d3e
> }
> };
> +static uint32_t hash_values_xor32[2][12] = {{
> + 0x00000000, 0x00010000,
> + 0x00010203, 0x04040404, 0x00000000, 0x00000000,
> + 0x00000000, 0x00000000, 0x0c040404, 0x000d0e0f,
> + 0x04212223, 0x04040404
> +},
> +{
> + 0xdeadbeef, 0xdeacbeef,
> + 0xdeacbcec, 0xdaa9baeb, 0xdeadbeef, 0xdeadbeef,
> + 0xdeadbeef, 0xdeadbeef, 0xd2a9baeb, 0xdea0b0e0,
> + 0xda8c9ccc, 0xdaa9baeb
> +}
> +};
>
> /*******************************************************************************
> * Hash function performance test configuration section. Each
> performance test
> @@ -61,7 +75,7 @@ static uint32_t hash_values_crc[2][12] = {{
> */
> #define HASHTEST_ITERATIONS 1000000
> #define MAX_KEYSIZE 64
> -static rte_hash_function hashtest_funcs[] = {rte_jhash,
> rte_hash_crc};
> +static rte_hash_function hashtest_funcs[] = {rte_jhash,
> rte_hash_crc, rte_hash_xor32};
> static uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
> static uint32_t hashtest_key_lens[] = {
> 1, 2, /* Unusual key sizes */
> @@ -85,6 +99,9 @@ get_hash_name(rte_hash_function f)
> if (f == rte_hash_crc)
> return "rte_hash_crc";
>
> + if (f == rte_hash_xor32)
> + return "rte_hash_xor32";
> +
> return "UnknownHash";
> }
>
> @@ -173,6 +190,16 @@ verify_precalculated_hash_func_tests(void)
> hash_values_crc[j][i],
> hash);
> return -1;
> }
> +
> + hash = rte_hash_xor32(key,
> hashtest_key_lens[i],
> + hashtest_initvals[j]);
> + if (hash != hash_values_xor32[j][i]) {
> + printf("XOR32 for %u bytes with
> initial value 0x%x."
> + " Expected 0x%x, but got
> 0x%x\n",
> + hashtest_key_lens[i],
> hashtest_initvals[j],
> + hash_values_xor32[j][i],
> hash);
> + return -1;
> + }
> }
> }
>
> diff --git a/lib/hash/rte_hash_xor.h b/lib/hash/rte_hash_xor.h
> new file mode 100644
> index 0000000000..366adbe64c
> --- /dev/null
> +++ b/lib/hash/rte_hash_xor.h
> @@ -0,0 +1,87 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2023 Intel Corporation
> + */
> +
> +#ifndef _RTE_HASH_XOR_H_
> +#define _RTE_HASH_XOR_H_
> +
> +/**
> + * @file
> + *
> + * RTE XOR Hash
> + */
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +#include <stdint.h>
> +
> +#include <rte_byteorder.h>
> +
> +/**
> + * Calculate XOR32 hash on user-supplied byte array.
> + *
> + * @param data
> + * Data to perform hash on.
> + * @param data_len
> + * How many bytes to use to calculate hash value.
> + * @param init_val
> + * Value to initialise hash generator.
> + * @return
> + * 32bit calculated hash value.
> + */
> +static inline uint32_t
> +rte_hash_xor32(const void *data, uint32_t data_len, uint32_t
> init_val)
> +{
> + uint32_t hash32;
> + const uint8_t *data8 = data;
> +
> + /* Minimize byte order conversions depending on data
> length. */
> + if (data_len >= 8) {
> + /* For longer arrays, operate in big endian. */
> + uint64_t hash64 = rte_cpu_to_be_32(init_val);
> +
> + uint32_t i;
> + for (i = 0; i < data_len / 8; i++) {
> + hash64 ^= *(const uint64_t *)data8;
> + data8 += 8;
> + }
> +
> + if (data_len & 0x4) {
> + hash64 ^= *(const uint32_t *)data8;
> + data8 += 4;
> + }
> +
> + hash32 = rte_be_to_cpu_32(hash64 ^ (hash64 >> 32));
> + } else {
> + /* For shorter arrays, operate in host endian. */
> + hash32 = init_val;
> +
> + if (data_len & 0x4) {
> + hash32 ^= rte_be_to_cpu_32(*(const
> uint32_t *)data8);
> + data8 += 4;
> + }
> + }
> +
> + /* Deal with remaining (< 4) bytes. */
> +
> + uint8_t bit_offset = 0;
> +
> + if (data_len & 0x2) {
> + hash32 ^= (uint32_t)rte_be_to_cpu_16(*(const
> uint16_t *)data8) << 16;
> + data8 += 2;
> + bit_offset += 16;
> + }
> +
> + if (data_len & 0x1)
> + hash32 ^= (uint32_t)(*(const uint8_t *)data8) <<
> (24 - bit_offset);
> +
> + return hash32;
> +}
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* _RTE_HASH_XOR_H_ */
> --
> 2.34.1
>
>
>
> --
> Regards,
> Vladimir
>
More information about the dev
mailing list