[PATCH] hash: add XOR32 hash function

[PATCH] hash: add XOR32 hash function

[Bili Dong]

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@gmail.com>
---
 .mailmap                       |  1 +
 app/test/test_hash_functions.c | 33 +++++++++++++++--
 lib/hash/rte_hash_xor.h        | 65 ++++++++++++++++++++++++++++++++++
 3 files changed, 96 insertions(+), 3 deletions(-)
 create mode 100644 lib/hash/rte_hash_xor.h

diff --git a/.mailmap b/.mailmap
index 5015494210..176dd93b66 100644
--- a/.mailmap
+++ b/.mailmap
@@ -159,6 +159,7 @@ Bernard Iremonger <bernard.iremonger@intel.com>
 Bert van Leeuwen <bert.vanleeuwen@netronome.com>
 Bhagyada Modali <bhagyada.modali@amd.com>
 Bharat Mota <bmota@vmware.com>
+Bili Dong <qobilidop@gmail.com>
 Bill Hong <bhong@brocade.com>
 Billy McFall <bmcfall@redhat.com>
 Billy O'Mahony <billy.o.mahony@intel.com>
diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
index 76d51b6e71..14d69d90c4 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_xor[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_xor};
 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_xor)
+		return "rte_hash_xor";
+
 	return "UnknownHash";
 }
 
@@ -173,6 +190,16 @@ verify_precalculated_hash_func_tests(void)
 				       hash_values_crc[j][i], hash);
 				return -1;
 			}
+
+			hash = rte_hash_xor(key, hashtest_key_lens[i],
+					hashtest_initvals[j]);
+			if (hash != hash_values_xor[j][i]) {
+				printf("XOR 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_xor[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..61ca8bee73
--- /dev/null
+++ b/lib/hash/rte_hash_xor.h
@@ -0,0 +1,65 @@
+/* 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>
+
+#define LEFT8b_MASK rte_cpu_to_be_32(0xff000000)
+#define LEFT16b_MASK rte_cpu_to_be_32(0xffff0000)
+
+/**
+ * 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_xor(const void *data, uint32_t data_len, uint32_t init_val)
+{
+	unsigned i;
+	uintptr_t pd = (uintptr_t) data;
+	init_val = rte_cpu_to_be_32(init_val);
+
+	for (i = 0; i < data_len / 4; i++) {
+		init_val ^= *(const uint32_t *)pd;
+		pd += 4;
+	}
+
+	if (data_len & 0x2) {
+		init_val ^= *(const uint32_t *)pd & LEFT16b_MASK;
+		pd += 2;
+	}
+
+	if (data_len & 0x1)
+		init_val ^= *(const uint32_t *)pd & LEFT8b_MASK;
+
+	init_val = rte_be_to_cpu_32(init_val);
+	return init_val;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_HASH_XOR_H_ */
-- 
2.34.1

[PATCH v2] hash: add XOR32 hash function

[Bili Dong]

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@gmail.com>
---
 .mailmap                       |  1 +
 app/test/test_hash_functions.c | 33 ++++++++++++++++--
 lib/hash/rte_hash_xor.h        | 64 ++++++++++++++++++++++++++++++++++
 3 files changed, 95 insertions(+), 3 deletions(-)
 create mode 100644 lib/hash/rte_hash_xor.h

diff --git a/.mailmap b/.mailmap
index 5015494210..176dd93b66 100644
--- a/.mailmap
+++ b/.mailmap
@@ -159,6 +159,7 @@ Bernard Iremonger <bernard.iremonger@intel.com>
 Bert van Leeuwen <bert.vanleeuwen@netronome.com>
 Bhagyada Modali <bhagyada.modali@amd.com>
 Bharat Mota <bmota@vmware.com>
+Bili Dong <qobilidop@gmail.com>
 Bill Hong <bhong@brocade.com>
 Billy McFall <bmcfall@redhat.com>
 Billy O'Mahony <billy.o.mahony@intel.com>
diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
index 76d51b6e71..14d69d90c4 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_xor[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_xor};
 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_xor)
+		return "rte_hash_xor";
+
 	return "UnknownHash";
 }
 
@@ -173,6 +190,16 @@ verify_precalculated_hash_func_tests(void)
 				       hash_values_crc[j][i], hash);
 				return -1;
 			}
+
+			hash = rte_hash_xor(key, hashtest_key_lens[i],
+					hashtest_initvals[j]);
+			if (hash != hash_values_xor[j][i]) {
+				printf("XOR 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_xor[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..8420fe997b
--- /dev/null
+++ b/lib/hash/rte_hash_xor.h
@@ -0,0 +1,64 @@
+/* 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>
+
+#define LEFT8b_MASK rte_cpu_to_be_32(0xff000000)
+#define LEFT16b_MASK rte_cpu_to_be_32(0xffff0000)
+
+/**
+ * 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_xor(const void *data, uint32_t data_len, uint32_t init_val)
+{
+	uintptr_t pd = (uintptr_t) data;
+	init_val = rte_cpu_to_be_32(init_val);
+
+	for (uint32_t i = 0; i < data_len / 4; i++) {
+		init_val ^= *(const uint32_t *)pd;
+		pd += 4;
+	}
+
+	if (data_len & 0x2) {
+		init_val ^= *(const uint32_t *)pd & LEFT16b_MASK;
+		pd += 2;
+	}
+
+	if (data_len & 0x1)
+		init_val ^= *(const uint32_t *)pd & LEFT8b_MASK;
+
+	init_val = rte_be_to_cpu_32(init_val);
+	return init_val;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_HASH_XOR_H_ */
-- 
2.34.1

[PATCH v3] hash: add XOR32 hash function

[Bili Dong]

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@gmail.com>
---
 .mailmap                       |  1 +
 app/test/test_hash_functions.c | 33 +++++++++++++++--
 lib/hash/rte_hash_xor.h        | 65 ++++++++++++++++++++++++++++++++++
 3 files changed, 96 insertions(+), 3 deletions(-)
 create mode 100644 lib/hash/rte_hash_xor.h

diff --git a/.mailmap b/.mailmap
index 5015494210..176dd93b66 100644
--- a/.mailmap
+++ b/.mailmap
@@ -159,6 +159,7 @@ Bernard Iremonger <bernard.iremonger@intel.com>
 Bert van Leeuwen <bert.vanleeuwen@netronome.com>
 Bhagyada Modali <bhagyada.modali@amd.com>
 Bharat Mota <bmota@vmware.com>
+Bili Dong <qobilidop@gmail.com>
 Bill Hong <bhong@brocade.com>
 Billy McFall <bmcfall@redhat.com>
 Billy O'Mahony <billy.o.mahony@intel.com>
diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
index 76d51b6e71..14d69d90c4 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_xor[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_xor};
 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_xor)
+		return "rte_hash_xor";
+
 	return "UnknownHash";
 }
 
@@ -173,6 +190,16 @@ verify_precalculated_hash_func_tests(void)
 				       hash_values_crc[j][i], hash);
 				return -1;
 			}
+
+			hash = rte_hash_xor(key, hashtest_key_lens[i],
+					hashtest_initvals[j]);
+			if (hash != hash_values_xor[j][i]) {
+				printf("XOR 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_xor[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..7004f83ec2
--- /dev/null
+++ b/lib/hash/rte_hash_xor.h
@@ -0,0 +1,65 @@
+/* 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>
+
+#define LEFT8b_MASK rte_cpu_to_be_32(0xff000000)
+#define LEFT16b_MASK rte_cpu_to_be_32(0xffff0000)
+
+/**
+ * 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_xor(const void *data, uint32_t data_len, uint32_t init_val)
+{
+	uint32_t i;
+	uintptr_t pd = (uintptr_t) data;
+	init_val = rte_cpu_to_be_32(init_val);
+
+	for (i = 0; i < data_len / 4; i++) {
+		init_val ^= *(const uint32_t *)pd;
+		pd += 4;
+	}
+
+	if (data_len & 0x2) {
+		init_val ^= *(const uint32_t *)pd & LEFT16b_MASK;
+		pd += 2;
+	}
+
+	if (data_len & 0x1)
+		init_val ^= *(const uint32_t *)pd & LEFT8b_MASK;
+
+	init_val = rte_be_to_cpu_32(init_val);
+	return init_val;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_HASH_XOR_H_ */
-- 
2.34.1

RE: [PATCH v3] hash: add XOR32 hash function

[Morten Brørup]

> From: Bili Dong [mailto:qobilidop@gmail.com]
> Sent: Wednesday, 15 February 2023 12.07
> 
> 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@gmail.com>
> ---

[...]

> +#define LEFT8b_MASK rte_cpu_to_be_32(0xff000000)
> +#define LEFT16b_MASK rte_cpu_to_be_32(0xffff0000)
> +
> +/**
> + * 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_xor(const void *data, uint32_t data_len, uint32_t init_val)
> +{
> +	uint32_t i;
> +	uintptr_t pd = (uintptr_t) data;
> +	init_val = rte_cpu_to_be_32(init_val);
> +
> +	for (i = 0; i < data_len / 4; i++) {
> +		init_val ^= *(const uint32_t *)pd;
> +		pd += 4;
> +	}
> +
> +	if (data_len & 0x2) {
> +		init_val ^= *(const uint32_t *)pd & LEFT16b_MASK;
> +		pd += 2;
> +	}
> +
> +	if (data_len & 0x1)
> +		init_val ^= *(const uint32_t *)pd & LEFT8b_MASK;
> +
> +	init_val = rte_be_to_cpu_32(init_val);
> +	return init_val;
> +}

I think that this function has swapped big endian and CPU endian everywhere. The result is the same, but the code would be much less confusing if using rte_cpu_32_to_be() when converting from CPU endian to big endian, and rte_be_to_cpu_32() when converting the other way.

I also suppose that the return type and the init_val parameter were meant to be rte_be32_t.

Also, please document that the byte array must be 32 bit aligned. Alternatively, implement support for unaligned data. You can find inspiration for handling of unaligned data in the __rte_raw_cksum() function:
https://elixir.bootlin.com/dpdk/v22.11.1/source/lib/net/rte_ip.h#L162

Re: [PATCH v3] hash: add XOR32 hash function

[Bili Dong]

[-- Attachment #1: Type: text/plain, Size: 3342 bytes --]

Hi Morten,

Thanks for your comments!

For endianness conversion, I double-checked my usages. I did use both
rte_cpu_to_be_32() and rte_be_to_cpu_32(). I might have missed something
but I think I used them (4 occurrences) in a semantically meaningful way.
Could you point me to the lines that are confusing?

The hash function signature has to conform to
https://elixir.bootlin.com/dpdk/v22.11.1/source/lib/table/rte_swx_hash_func.h#L31,
so I don't have the freedom to change the parameter type to rte_be32_t,
although personally I agree with you and would prefer to make everything
consistently big-endian here.

I'm not sure about the byte alignment assumptions used in hash functions.
My implementation basically follows the existing CRC32 hash:
https://elixir.bootlin.com/dpdk/v22.11.1/source/lib/hash/rte_hash_crc.h#L168,
and I don't see byte alignment handled there. Maybe someone more familiar
with lib/hash/ could provide some context on this?

Thanks,
Bili

On Wed, Feb 15, 2023 at 3:39 AM Morten Brørup <mb@smartsharesystems.com>
wrote:

> > From: Bili Dong [mailto:qobilidop@gmail.com]
> > Sent: Wednesday, 15 February 2023 12.07
> >
> > 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@gmail.com>
> > ---
>
> [...]
>
> > +#define LEFT8b_MASK rte_cpu_to_be_32(0xff000000)
> > +#define LEFT16b_MASK rte_cpu_to_be_32(0xffff0000)
> > +
> > +/**
> > + * 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_xor(const void *data, uint32_t data_len, uint32_t init_val)
> > +{
> > +     uint32_t i;
> > +     uintptr_t pd = (uintptr_t) data;
> > +     init_val = rte_cpu_to_be_32(init_val);
> > +
> > +     for (i = 0; i < data_len / 4; i++) {
> > +             init_val ^= *(const uint32_t *)pd;
> > +             pd += 4;
> > +     }
> > +
> > +     if (data_len & 0x2) {
> > +             init_val ^= *(const uint32_t *)pd & LEFT16b_MASK;
> > +             pd += 2;
> > +     }
> > +
> > +     if (data_len & 0x1)
> > +             init_val ^= *(const uint32_t *)pd & LEFT8b_MASK;
> > +
> > +     init_val = rte_be_to_cpu_32(init_val);
> > +     return init_val;
> > +}
>
> I think that this function has swapped big endian and CPU endian
> everywhere. The result is the same, but the code would be much less
> confusing if using rte_cpu_32_to_be() when converting from CPU endian to
> big endian, and rte_be_to_cpu_32() when converting the other way.
>
> I also suppose that the return type and the init_val parameter were meant
> to be rte_be32_t.
>
> Also, please document that the byte array must be 32 bit aligned.
> Alternatively, implement support for unaligned data. You can find
> inspiration for handling of unaligned data in the __rte_raw_cksum()
> function:
> https://elixir.bootlin.com/dpdk/v22.11.1/source/lib/net/rte_ip.h#L162
>
>
>

[-- Attachment #2: Type: text/html, Size: 4504 bytes --]

RE: [PATCH v3] hash: add XOR32 hash function

[Morten Brørup]

[-- Attachment #1: Type: text/plain, Size: 3995 bytes --]

Hi Bili,

 

OK. I’m not familiar with this library, but the other function assumes 8 byte aligned data, so this should be OK too.

 

And with the required function signature, I now understand why you use endian conversions this way.

 

Acked-by: Morten Brørup <mb@smartsharesystems.com>

 

 

Med venlig hilsen / Kind regards,

-Morten Brørup

 

From: Bili Dong [mailto:qobilidop@gmail.com] 
Sent: Wednesday, 15 February 2023 22.40
To: Morten Brørup
Cc: yipeng1.wang@intel.com; sameh.gobriel@intel.com; bruce.richardson@intel.com; vladimir.medvedkin@intel.com; cristian.dumitrescu@intel.com; dev@dpdk.org
Subject: Re: [PATCH v3] hash: add XOR32 hash function

 

Hi Morten,

 

Thanks for your comments!

 

For endianness conversion, I double-checked my usages. I did use both rte_cpu_to_be_32() and rte_be_to_cpu_32(). I might have missed something but I think I used them (4 occurrences) in a semantically meaningful way. Could you point me to the lines that are confusing?

 

The hash function signature has to conform to https://elixir.bootlin.com/dpdk/v22.11.1/source/lib/table/rte_swx_hash_func.h#L31, so I don't have the freedom to change the parameter type to rte_be32_t, although personally I agree with you and would prefer to make everything consistently big-endian here.

 

I'm not sure about the byte alignment assumptions used in hash functions. My implementation basically follows the existing CRC32 hash: https://elixir.bootlin.com/dpdk/v22.11.1/source/lib/hash/rte_hash_crc.h#L168, and I don't see byte alignment handled there. Maybe someone more familiar with lib/hash/ could provide some context on this?

 

Thanks,

Bili

 

On Wed, Feb 15, 2023 at 3:39 AM Morten Brørup <mb@smartsharesystems.com> wrote:

	> From: Bili Dong [mailto:qobilidop@gmail.com]
	> Sent: Wednesday, 15 February 2023 12.07
	> 
	> 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@gmail.com>
	> ---
	
	[...]
	
	> +#define LEFT8b_MASK rte_cpu_to_be_32(0xff000000)
	> +#define LEFT16b_MASK rte_cpu_to_be_32(0xffff0000)
	> +
	> +/**
	> + * 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_xor(const void *data, uint32_t data_len, uint32_t init_val)
	> +{
	> +     uint32_t i;
	> +     uintptr_t pd = (uintptr_t) data;
	> +     init_val = rte_cpu_to_be_32(init_val);
	> +
	> +     for (i = 0; i < data_len / 4; i++) {
	> +             init_val ^= *(const uint32_t *)pd;
	> +             pd += 4;
	> +     }
	> +
	> +     if (data_len & 0x2) {
	> +             init_val ^= *(const uint32_t *)pd & LEFT16b_MASK;
	> +             pd += 2;
	> +     }
	> +
	> +     if (data_len & 0x1)
	> +             init_val ^= *(const uint32_t *)pd & LEFT8b_MASK;
	> +
	> +     init_val = rte_be_to_cpu_32(init_val);
	> +     return init_val;
	> +}
	
	I think that this function has swapped big endian and CPU endian everywhere. The result is the same, but the code would be much less confusing if using rte_cpu_32_to_be() when converting from CPU endian to big endian, and rte_be_to_cpu_32() when converting the other way.
	
	I also suppose that the return type and the init_val parameter were meant to be rte_be32_t.
	
	Also, please document that the byte array must be 32 bit aligned. Alternatively, implement support for unaligned data. You can find inspiration for handling of unaligned data in the __rte_raw_cksum() function:
	https://elixir.bootlin.com/dpdk/v22.11.1/source/lib/net/rte_ip.h#L162
	
	


[-- Attachment #2: Type: text/html, Size: 9394 bytes --]

Re: [PATCH v3] hash: add XOR32 hash function

[Thomas Monjalon]

15/02/2023 12:06, Bili Dong:
> 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@gmail.com>
> ---
> +/**
> + * 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_xor(const void *data, uint32_t data_len, uint32_t init_val)

Should we add "32" in the function name?

Re: [PATCH v3] hash: add XOR32 hash function

[Bili Dong]

[-- Attachment #1: Type: text/plain, Size: 1190 bytes --]

The naming is following the existing CRC32 hash:
https://elixir.bootlin.com/dpdk/v22.11.1/source/lib/hash/rte_hash_crc.h#L168.
I believe all existing hash functions in DPDK are 32 bits, so "32" didn't
appear in other hash function names. If we add "32" here, we probably
should also rename rte_hash_crc(). I'm fine with either option.

On Mon, Feb 20, 2023 at 5:49 AM Thomas Monjalon <thomas@monjalon.net> wrote:

> 15/02/2023 12:06, Bili Dong:
> > 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@gmail.com>
> > ---
> > +/**
> > + * 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_xor(const void *data, uint32_t data_len, uint32_t init_val)
>
> Should we add "32" in the function name?
>
>
>

[-- Attachment #2: Type: text/html, Size: 1808 bytes --]

Re: [PATCH v3] hash: add XOR32 hash function

[Thomas Monjalon]

20/02/2023 18:21, Bili Dong:
> The naming is following the existing CRC32 hash:
> https://elixir.bootlin.com/dpdk/v22.11.1/source/lib/hash/rte_hash_crc.h#L168.
> I believe all existing hash functions in DPDK are 32 bits, so "32" didn't
> appear in other hash function names. If we add "32" here, we probably
> should also rename rte_hash_crc(). I'm fine with either option.

Why all functions would be 32-bit?
I don't think we need to rename all.
We can just make the right thing when adding a new function.

What maintainers of rte_hash think?

Re: [PATCH v3] hash: add XOR32 hash function

[Bruce Richardson]

On Mon, Feb 20, 2023 at 06:38:23PM +0100, Thomas Monjalon wrote:
> 20/02/2023 18:21, Bili Dong:
> > The naming is following the existing CRC32 hash:
> > https://elixir.bootlin.com/dpdk/v22.11.1/source/lib/hash/rte_hash_crc.h#L168.
> > I believe all existing hash functions in DPDK are 32 bits, so "32" didn't
> > appear in other hash function names. If we add "32" here, we probably
> > should also rename rte_hash_crc(). I'm fine with either option.
> 
> Why all functions would be 32-bit?
> I don't think we need to rename all.
> We can just make the right thing when adding a new function.
> 
> What maintainers of rte_hash think?
> 
+1 to adding the 32 for clarity.

If we want consistency, it's easy enough to create some aliases for the
existing functions with the "32" extension on them. No need to remove the
old names so there would be no compatibility issues.

Re: [PATCH v3] hash: add XOR32 hash function

[Bili Dong]

[-- Attachment #1: Type: text/plain, Size: 1061 bytes --]

Got it. I’ll update the patch.

On Mon, Feb 20, 2023 at 9:52 AM Bruce Richardson <bruce.richardson@intel.com>
wrote:

> On Mon, Feb 20, 2023 at 06:38:23PM +0100, Thomas Monjalon wrote:
> > 20/02/2023 18:21, Bili Dong:
> > > The naming is following the existing CRC32 hash:
> > >
> https://elixir.bootlin.com/dpdk/v22.11.1/source/lib/hash/rte_hash_crc.h#L168
> .
> > > I believe all existing hash functions in DPDK are 32 bits, so "32"
> didn't
> > > appear in other hash function names. If we add "32" here, we probably
> > > should also rename rte_hash_crc(). I'm fine with either option.
> >
> > Why all functions would be 32-bit?
> > I don't think we need to rename all.
> > We can just make the right thing when adding a new function.
> >
> > What maintainers of rte_hash think?
> >
> +1 to adding the 32 for clarity.
>
> If we want consistency, it's easy enough to create some aliases for the
> existing functions with the "32" extension on them. No need to remove the
> old names so there would be no compatibility issues.
>

[-- Attachment #2: Type: text/html, Size: 1649 bytes --]

RE: [PATCH v3] hash: add XOR32 hash function

[Dumitrescu, Cristian]

[-- Attachment #1: Type: text/plain, Size: 192 bytes --]

Hi Bili,

Would it be possible to also remove the endianness conversion from this hash function? What would be the impact if the rte_cpu_to_be() functions are removed?

Thanks,
Cristian

[-- Attachment #2: Type: text/html, Size: 2117 bytes --]

Re: [PATCH v3] hash: add XOR32 hash function

[Bili Dong]

[-- Attachment #1: Type: text/plain, Size: 817 bytes --]

I think the endianness conversions are necessary, otherwise, the hash
function return value will be host endianness dependent.

For example, what should rte_hash_xor32(/*data*/ &{0x00, 0x01, 0x02, 0x03},
/*data_len*/ 4, /*init_val*/ 0x0) return? With the current implementation,
it returns 0x00010203 consistently. If we remove the endianness
conversions, it will return 0x00010203 on big-endian hosts and 0x03020100
on little-endian hosts. Please correct me but I don't think that's the
expected behavior.

On Mon, Feb 20, 2023 at 10:19 AM Dumitrescu, Cristian <
cristian.dumitrescu@intel.com> wrote:

> Hi Bili,
>
>
>
> Would it be possible to also remove the endianness conversion from this
> hash function? What would be the impact if the rte_cpu_to_be() functions
> are removed?
>
>
>
> Thanks,
>
> Cristian
>
>

[-- Attachment #2: Type: text/html, Size: 1883 bytes --]

Re: [PATCH v3] hash: add XOR32 hash function

[Medvedkin, Vladimir]

Hi Bill,

On 15/02/2023 11:06, Bili Dong wrote:
> 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@gmail.com>
> ---
> +static inline uint32_t
> +rte_hash_xor(const void *data, uint32_t data_len, uint32_t init_val)
> +{
> +	uint32_t i;
> +	uintptr_t pd = (uintptr_t) data;
> +	init_val = rte_cpu_to_be_32(init_val);
> +
> +	for (i = 0; i < data_len / 4; i++) {
> +		init_val ^= *(const uint32_t *)pd;
> +		pd += 4;
> +	}
> +
> +	if (data_len & 0x2) {
> +		init_val ^= *(const uint32_t *)pd & LEFT16b_MASK;

Here you are reading 2 bytes after the data buffer, which can sometimes 
lead to segfault. I think it would be better just to:

init_val ^= *(const uint16_t *)pd << 16;

The same with the section bellow

> +		pd += 2;
> +	}
> +
> +	if (data_len & 0x1)
> +		init_val ^= *(const uint32_t *)pd & LEFT8b_MASK;
> +
> +	init_val = rte_be_to_cpu_32(init_val);
> +	return init_val;
> +}
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* _RTE_HASH_XOR_H_ */

-- 
Regards,
Vladimir

Re: [PATCH v3] hash: add XOR32 hash function

[Bili Dong]

[-- Attachment #1: Type: text/plain, Size: 1464 bytes --]

Got it. Will fix. Thanks!

On Mon, Feb 20, 2023 at 12:10 PM Medvedkin, Vladimir <
vladimir.medvedkin@intel.com> wrote:

> Hi Bill,
>
> On 15/02/2023 11:06, Bili Dong wrote:
> > 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@gmail.com>
> > ---
> > +static inline uint32_t
> > +rte_hash_xor(const void *data, uint32_t data_len, uint32_t init_val)
> > +{
> > +     uint32_t i;
> > +     uintptr_t pd = (uintptr_t) data;
> > +     init_val = rte_cpu_to_be_32(init_val);
> > +
> > +     for (i = 0; i < data_len / 4; i++) {
> > +             init_val ^= *(const uint32_t *)pd;
> > +             pd += 4;
> > +     }
> > +
> > +     if (data_len & 0x2) {
> > +             init_val ^= *(const uint32_t *)pd & LEFT16b_MASK;
>
> Here you are reading 2 bytes after the data buffer, which can sometimes
> lead to segfault. I think it would be better just to:
>
> init_val ^= *(const uint16_t *)pd << 16;
>
> The same with the section bellow
>
> > +             pd += 2;
> > +     }
> > +
> > +     if (data_len & 0x1)
> > +             init_val ^= *(const uint32_t *)pd & LEFT8b_MASK;
> > +
> > +     init_val = rte_be_to_cpu_32(init_val);
> > +     return init_val;
> > +}
> > +
> > +#ifdef __cplusplus
> > +}
> > +#endif
> > +
> > +#endif /* _RTE_HASH_XOR_H_ */
>
> --
> Regards,
> Vladimir
>
>

[-- Attachment #2: Type: text/html, Size: 2169 bytes --]

RE: [PATCH v3] hash: add XOR32 hash function

[Dumitrescu, Cristian]

HI Bili,

Comments inline below:

<snip>

> diff --git a/lib/hash/rte_hash_xor.h b/lib/hash/rte_hash_xor.h
> new file mode 100644
> index 0000000000..7004f83ec2
> --- /dev/null
> +++ b/lib/hash/rte_hash_xor.h
> @@ -0,0 +1,65 @@
> +/* 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>
> +
> +#define LEFT8b_MASK rte_cpu_to_be_32(0xff000000)

I know that cpu_to_be() and be_to_cpu() are doing the same thing, but to me the correct function to use here is be_to_cpu(), as the for loop in the function below works with values in the CPU endianness. Would you agree?

> +#define LEFT16b_MASK rte_cpu_to_be_32(0xffff0000)

I know that cpu_to_be() and be_to_cpu() are doing the same thing, but to me the correct function to use here is be_to_cpu(), as the for loop in the function below works with values in the CPU endianness. Would you agree?

> +
> +/**
> + * 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_xor(const void *data, uint32_t data_len, uint32_t init_val)
> +{
> +	uint32_t i;
> +	uintptr_t pd = (uintptr_t) data;
> +	init_val = rte_cpu_to_be_32(init_val);
I don't think this is correct, I the correct version here is to remove the above assignment, as I think the intention of this function (for performance reasons) is to do the endianness conversion only when needed, which is once at the end of the function (and also when handling the 2-byte and 1-byte left-overs).

> +
> +	for (i = 0; i < data_len / 4; i++) {
> +		init_val ^= *(const uint32_t *)pd;
> +		pd += 4;
> +	}
> +
> +	if (data_len & 0x2) {
> +		init_val ^= *(const uint32_t *)pd & LEFT16b_MASK;
> +		pd += 2;
> +	}
> +
> +	if (data_len & 0x1)
> +		init_val ^= *(const uint32_t *)pd & LEFT8b_MASK;
> +
> +	init_val = rte_be_to_cpu_32(init_val);
> +	return init_val;
> +}
> +

Due to the XOR properties (endianness-insensitivity, no carry bits, etc) and for performance reasons, I would also recommend implementing a 64-bit version of this function (while keeping the 32-bit result), similar to this:

uint64_t *data64 = (uint64_t *)data;
uint64_t result = init_data;

/* Read & accumulate input data in 8-byte increments. */
for (i = 0; i < data_len / 8; i++)
	result ^= *data64++;

data_len &= 0x7;

/* Handle any remaining bytes in the input data (up to 7 bytes). */
if (data_len >= 4) {
	uint32_t *data32 = (uint32_t *)data64;

	/* Read and accumulate  the next 4 bytes from the input data. */
	result ^= *data32++;
	data_len -= 4;

	if (data_len >= 2) {
		uint16_t *data16 = (uint16_t *)data32;

		/* Read and accumulate the next 2 bytes from the input data. */
		result ^= *data16++
		data_len -= 2;

		if (data_len) {
			uint8_t *data8 = (uint8_t *)data8;

			/* Read and accumulate the next byte from the input data. */
			result ^= *data8;
		}
	}
}

/* Accumulate the upper 32 bits on top of the lower 32 bits. */
result ^= result >> 32;

/* Single endianness swap at the very end. */
return rte_cpu_to_be32((uint32_t)result);

What do you think?

Regards,
Cristian

Re: [PATCH v3] hash: add XOR32 hash function

[Bili Dong]

[-- Attachment #1: Type: text/plain, Size: 5384 bytes --]

Hi Cristian,

I agree the 64-bit version could enable better performance, and I will do
it in the next version.

For endianness, see my comments below (inline):

On Mon, Feb 20, 2023 at 12:19 PM Dumitrescu, Cristian <
cristian.dumitrescu@intel.com> wrote:

> HI Bili,
>
> Comments inline below:
>
> <snip>
>
> > diff --git a/lib/hash/rte_hash_xor.h b/lib/hash/rte_hash_xor.h
> > new file mode 100644
> > index 0000000000..7004f83ec2
> > --- /dev/null
> > +++ b/lib/hash/rte_hash_xor.h
> > @@ -0,0 +1,65 @@
> > +/* 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>
> > +
> > +#define LEFT8b_MASK rte_cpu_to_be_32(0xff000000)
>
> I know that cpu_to_be() and be_to_cpu() are doing the same thing, but to
> me the correct function to use here is be_to_cpu(), as the for loop in the
> function below works with values in the CPU endianness. Would you agree?
>
What I have in mind is the 0xff000000 literal is in CPU endianness, and I'm
converting it to big-endian. For performance reasons, I think it's better
to work in big-endian in the loop.
Also as Vladimir suggested above, I'll remove these masks and switch to
using shifts directly. So I guess this won't matter anymore.

>
> > +#define LEFT16b_MASK rte_cpu_to_be_32(0xffff0000)
>
> I know that cpu_to_be() and be_to_cpu() are doing the same thing, but to
> me the correct function to use here is be_to_cpu(), as the for loop in the
> function below works with values in the CPU endianness. Would you agree?
>
> > +
> > +/**
> > + * 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_xor(const void *data, uint32_t data_len, uint32_t init_val)
> > +{
> > +     uint32_t i;
> > +     uintptr_t pd = (uintptr_t) data;
> > +     init_val = rte_cpu_to_be_32(init_val);
> I don't think this is correct, I the correct version here is to remove the
> above assignment, as I think the intention of this function (for
> performance reasons) is to do the endianness conversion only when needed,
> which is once at the end of the function (and also when handling the 2-byte
> and 1-byte left-overs).
>
What I have in mind is to convert init_val to big-endian once here, instead
of having to convert every byte array chunks from big-endian to host endian
in the loop (more conversions, worse performance, see comment below).

>
> > +
> > +     for (i = 0; i < data_len / 4; i++) {
> > +             init_val ^= *(const uint32_t *)pd;
>
Look at this line, if init_val is still in host endianness, we need to do
init_val ^= rte_be_to_cpu_32(*(const uint32_t *)pd) instead.
I think the essential tradeoff here is that, if we convert init_val from
host to be and back, we pay the constant cost of 2 conversions. The
alternative is to convert byte array chunks from be to host. The number of
conversions depends on data_len. Now I think of it more, maybe the best
option is to condition on the value of data_len, and choose the method with
fewer conversions.

> > +             pd += 4;
> > +     }
> > +
> > +     if (data_len & 0x2) {
> > +             init_val ^= *(const uint32_t *)pd & LEFT16b_MASK;
> > +             pd += 2;
> > +     }
> > +
> > +     if (data_len & 0x1)
> > +             init_val ^= *(const uint32_t *)pd & LEFT8b_MASK;
> > +
> > +     init_val = rte_be_to_cpu_32(init_val);
> > +     return init_val;
> > +}
> > +
>
> Due to the XOR properties (endianness-insensitivity, no carry bits, etc)
> and for performance reasons, I would also recommend implementing a 64-bit
> version of this function (while keeping the 32-bit result), similar to this:
>
> uint64_t *data64 = (uint64_t *)data;
> uint64_t result = init_data;
>
> /* Read & accumulate input data in 8-byte increments. */
> for (i = 0; i < data_len / 8; i++)
>         result ^= *data64++;
>
> data_len &= 0x7;
>
> /* Handle any remaining bytes in the input data (up to 7 bytes). */
> if (data_len >= 4) {
>         uint32_t *data32 = (uint32_t *)data64;
>
>         /* Read and accumulate  the next 4 bytes from the input data. */
>         result ^= *data32++;
>         data_len -= 4;
>
>         if (data_len >= 2) {
>                 uint16_t *data16 = (uint16_t *)data32;
>
>                 /* Read and accumulate the next 2 bytes from the input
> data. */
>                 result ^= *data16++
>                 data_len -= 2;
>
>                 if (data_len) {
>                         uint8_t *data8 = (uint8_t *)data8;
>
>                         /* Read and accumulate the next byte from the
> input data. */
>                         result ^= *data8;
>                 }
>         }
> }
>
> /* Accumulate the upper 32 bits on top of the lower 32 bits. */
> result ^= result >> 32;
>
> /* Single endianness swap at the very end. */
> return rte_cpu_to_be32((uint32_t)result);
>
> What do you think?
>
> Regards,
> Cristian
>
>

[-- Attachment #2: Type: text/html, Size: 7040 bytes --]

Re: [PATCH v3] hash: add XOR32 hash function

[Stephen Hemminger]

On Mon, 20 Feb 2023 12:44:06 -0800
Bili Dong <qobilidop@gmail.com> wrote:

> Hi Cristian,
> 
> I agree the 64-bit version could enable better performance, and I will do
> it in the next version.
> 

Same optimizations as ipv4 checksum probably apply.
Aligning data, and duffs device, etc.

You might even be able to use vector instructions

Re: [PATCH v3] hash: add XOR32 hash function

[Bili Dong]

[-- Attachment #1: Type: text/plain, Size: 481 bytes --]

Thanks, I'll check it out.

On Mon, Feb 20, 2023 at 3:04 PM Stephen Hemminger <
stephen@networkplumber.org> wrote:

> On Mon, 20 Feb 2023 12:44:06 -0800
> Bili Dong <qobilidop@gmail.com> wrote:
>
> > Hi Cristian,
> >
> > I agree the 64-bit version could enable better performance, and I will do
> > it in the next version.
> >
>
> Same optimizations as ipv4 checksum probably apply.
> Aligning data, and duffs device, etc.
>
> You might even be able to use vector instructions
>
>

[-- Attachment #2: Type: text/html, Size: 937 bytes --]

[PATCH v4] hash: add XOR32 hash function

[Bili Dong]

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@gmail.com>
---
 .mailmap                       |  1 +
 app/test/test_hash_functions.c | 33 +++++++++++++--
 lib/hash/rte_hash_xor.h        | 76 ++++++++++++++++++++++++++++++++++
 3 files changed, 107 insertions(+), 3 deletions(-)
 create mode 100644 lib/hash/rte_hash_xor.h

diff --git a/.mailmap b/.mailmap
index 5015494210..176dd93b66 100644
--- a/.mailmap
+++ b/.mailmap
@@ -159,6 +159,7 @@ Bernard Iremonger <bernard.iremonger@intel.com>
 Bert van Leeuwen <bert.vanleeuwen@netronome.com>
 Bhagyada Modali <bhagyada.modali@amd.com>
 Bharat Mota <bmota@vmware.com>
+Bili Dong <qobilidop@gmail.com>
 Bill Hong <bhong@brocade.com>
 Billy McFall <bmcfall@redhat.com>
 Billy O'Mahony <billy.o.mahony@intel.com>
diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
index 76d51b6e71..df8c14d7c5 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_xor[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_xor[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_xor[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..0b5a7bef09
--- /dev/null
+++ b/lib/hash/rte_hash_xor.h
@@ -0,0 +1,76 @@
+/* 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)
+{
+	/* Operate in big endian from here on. */
+	/* So we don't need to convert byte orders in the loop. */
+
+	uint64_t hash64 = rte_cpu_to_be_32(init_val);
+	const uint8_t *data8 = data;
+
+	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;
+	}
+
+	/* Operate in host endian from here on. */
+	/* Because bit shifts only make sense in host endian. */
+
+	uint32_t hash32 = rte_be_to_cpu_32(hash64 ^ (hash64 >> 32));
+	uint8_t offset = 0;
+
+	if (data_len & 0x2) {
+		hash32 ^= (uint32_t)rte_be_to_cpu_16(*(const uint16_t *)data8) << 16;
+		data8 += 2;
+		offset += 2;
+	}
+
+	if (data_len & 0x1)
+		hash32 ^= (uint32_t)(*(const uint8_t *)data8) << (8 * (3 - offset));
+
+	return hash32;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_HASH_XOR_H_ */
-- 
2.34.1

[PATCH v5] hash: add XOR32 hash function

[Bili Dong]

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@gmail.com>
---
 .mailmap                       |  1 +
 app/test/test_hash_functions.c | 33 +++++++++++++--
 lib/hash/rte_hash_xor.h        | 76 ++++++++++++++++++++++++++++++++++
 3 files changed, 107 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@intel.com>
 Bert van Leeuwen <bert.vanleeuwen@netronome.com>
 Bhagyada Modali <bhagyada.modali@amd.com>
 Bharat Mota <bmota@vmware.com>
+Bili Dong <qobilidop@gmail.com>
 Bill Hong <bhong@brocade.com>
 Billy McFall <bmcfall@redhat.com>
 Billy O'Mahony <billy.o.mahony@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..0b5a7bef09
--- /dev/null
+++ b/lib/hash/rte_hash_xor.h
@@ -0,0 +1,76 @@
+/* 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)
+{
+	/* Operate in big endian from here on. */
+	/* So we don't need to convert byte orders in the loop. */
+
+	uint64_t hash64 = rte_cpu_to_be_32(init_val);
+	const uint8_t *data8 = data;
+
+	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;
+	}
+
+	/* Operate in host endian from here on. */
+	/* Because bit shifts only make sense in host endian. */
+
+	uint32_t hash32 = rte_be_to_cpu_32(hash64 ^ (hash64 >> 32));
+	uint8_t offset = 0;
+
+	if (data_len & 0x2) {
+		hash32 ^= (uint32_t)rte_be_to_cpu_16(*(const uint16_t *)data8) << 16;
+		data8 += 2;
+		offset += 2;
+	}
+
+	if (data_len & 0x1)
+		hash32 ^= (uint32_t)(*(const uint8_t *)data8) << (8 * (3 - offset));
+
+	return hash32;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_HASH_XOR_H_ */
-- 
2.34.1

[PATCH v6] hash: add XOR32 hash function

[Bili Dong]

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@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@intel.com>
 Bert van Leeuwen <bert.vanleeuwen@netronome.com>
 Bhagyada Modali <bhagyada.modali@amd.com>
 Bharat Mota <bmota@vmware.com>
+Bili Dong <qobilidop@gmail.com>
 Bill Hong <bhong@brocade.com>
 Billy McFall <bmcfall@redhat.com>
 Billy O'Mahony <billy.o.mahony@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

Re: [PATCH v6] hash: add XOR32 hash function

[Bili Dong]

[-- Attachment #1: Type: text/plain, Size: 6893 bytes --]

The reported performance issue
<http://mails.dpdk.org/archives/test-report/2023-February/357697.html> is a
mystery to me. Does anyone have an idea what's going on?

Thanks,
Bili

On Tue, Feb 21, 2023 at 11:37 AM Bili Dong <qobilidop@gmail.com> wrote:

> 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@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@intel.com>
>  Bert van Leeuwen <bert.vanleeuwen@netronome.com>
>  Bhagyada Modali <bhagyada.modali@amd.com>
>  Bharat Mota <bmota@vmware.com>
> +Bili Dong <qobilidop@gmail.com>
>  Bill Hong <bhong@brocade.com>
>  Billy McFall <bmcfall@redhat.com>
>  Billy O'Mahony <billy.o.mahony@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
>
>

[-- Attachment #2: Type: text/html, Size: 9162 bytes --]

Re: [PATCH v6] hash: add XOR32 hash function

[Thomas Monjalon]

Any review please?
This patch is dying...


21/02/2023 20:37, Bili Dong:
> 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@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@intel.com>
>  Bert van Leeuwen <bert.vanleeuwen@netronome.com>
>  Bhagyada Modali <bhagyada.modali@amd.com>
>  Bharat Mota <bmota@vmware.com>
> +Bili Dong <qobilidop@gmail.com>
>  Bill Hong <bhong@brocade.com>
>  Billy McFall <bmcfall@redhat.com>
>  Billy O'Mahony <billy.o.mahony@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_ */
> 

Re: [PATCH v6] hash: add XOR32 hash function

[Vladimir Medvedkin]

[-- Attachment #1: Type: text/plain, Size: 8225 bytes --]

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;
                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@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@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@intel.com>
>  Bert van Leeuwen <bert.vanleeuwen@netronome.com>
>  Bhagyada Modali <bhagyada.modali@amd.com>
>  Bharat Mota <bmota@vmware.com>
> +Bili Dong <qobilidop@gmail.com>
>  Bill Hong <bhong@brocade.com>
>  Billy McFall <bmcfall@redhat.com>
>  Billy O'Mahony <billy.o.mahony@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

[-- Attachment #2: Type: text/html, Size: 10711 bytes --]

Re: [PATCH v6] hash: add XOR32 hash function

[Bili Dong]

[-- Attachment #1: Type: text/plain, Size: 8819 bytes --]

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@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;
>                 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@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@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@intel.com>
>>  Bert van Leeuwen <bert.vanleeuwen@netronome.com>
>>  Bhagyada Modali <bhagyada.modali@amd.com>
>>  Bharat Mota <bmota@vmware.com>
>> +Bili Dong <qobilidop@gmail.com>
>>  Bill Hong <bhong@brocade.com>
>>  Billy McFall <bmcfall@redhat.com>
>>  Billy O'Mahony <billy.o.mahony@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
>

[-- Attachment #2: Type: text/html, Size: 11347 bytes --]

Re: [PATCH v6] hash: add XOR32 hash function

[Mattias Rönnblom]

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@gmail.com <mailto:medvedkinv@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@gmail.com
>     <mailto:qobilidop@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@gmail.com
>         <mailto:qobilidop@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@intel.com <mailto:bernard.iremonger@intel.com>>
>           Bert van Leeuwen <bert.vanleeuwen@netronome.com
>         <mailto:bert.vanleeuwen@netronome.com>>
>           Bhagyada Modali <bhagyada.modali@amd.com
>         <mailto:bhagyada.modali@amd.com>>
>           Bharat Mota <bmota@vmware.com <mailto:bmota@vmware.com>>
>         +Bili Dong <qobilidop@gmail.com <mailto:qobilidop@gmail.com>>
>           Bill Hong <bhong@brocade.com <mailto:bhong@brocade.com>>
>           Billy McFall <bmcfall@redhat.com <mailto:bmcfall@redhat.com>>
>           Billy O'Mahony <billy.o.mahony@intel.com
>         <mailto:billy.o.mahony@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
> 

Re: [PATCH] hash: add XOR32 hash function

[Stephen Hemminger]

[-- Attachment #1: Type: text/plain, Size: 5920 bytes --]

Does it generate same hash as NIC than do it in HW?

On Wed, Feb 15, 2023, 3:31 AM Bili Dong <qobilidop@gmail.com> wrote:

> 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@gmail.com>
> ---
>  .mailmap                       |  1 +
>  app/test/test_hash_functions.c | 33 +++++++++++++++--
>  lib/hash/rte_hash_xor.h        | 65 ++++++++++++++++++++++++++++++++++
>  3 files changed, 96 insertions(+), 3 deletions(-)
>  create mode 100644 lib/hash/rte_hash_xor.h
>
> diff --git a/.mailmap b/.mailmap
> index 5015494210..176dd93b66 100644
> --- a/.mailmap
> +++ b/.mailmap
> @@ -159,6 +159,7 @@ Bernard Iremonger <bernard.iremonger@intel.com>
>  Bert van Leeuwen <bert.vanleeuwen@netronome.com>
>  Bhagyada Modali <bhagyada.modali@amd.com>
>  Bharat Mota <bmota@vmware.com>
> +Bili Dong <qobilidop@gmail.com>
>  Bill Hong <bhong@brocade.com>
>  Billy McFall <bmcfall@redhat.com>
>  Billy O'Mahony <billy.o.mahony@intel.com>
> diff --git a/app/test/test_hash_functions.c
> b/app/test/test_hash_functions.c
> index 76d51b6e71..14d69d90c4 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_xor[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_xor};
>  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_xor)
> +               return "rte_hash_xor";
> +
>         return "UnknownHash";
>  }
>
> @@ -173,6 +190,16 @@ verify_precalculated_hash_func_tests(void)
>                                        hash_values_crc[j][i], hash);
>                                 return -1;
>                         }
> +
> +                       hash = rte_hash_xor(key, hashtest_key_lens[i],
> +                                       hashtest_initvals[j]);
> +                       if (hash != hash_values_xor[j][i]) {
> +                               printf("XOR 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_xor[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..61ca8bee73
> --- /dev/null
> +++ b/lib/hash/rte_hash_xor.h
> @@ -0,0 +1,65 @@
> +/* 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>
> +
> +#define LEFT8b_MASK rte_cpu_to_be_32(0xff000000)
> +#define LEFT16b_MASK rte_cpu_to_be_32(0xffff0000)
> +
> +/**
> + * 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_xor(const void *data, uint32_t data_len, uint32_t init_val)
> +{
> +       unsigned i;
> +       uintptr_t pd = (uintptr_t) data;
> +       init_val = rte_cpu_to_be_32(init_val);
> +
> +       for (i = 0; i < data_len / 4; i++) {
> +               init_val ^= *(const uint32_t *)pd;
> +               pd += 4;
> +       }
> +
> +       if (data_len & 0x2) {
> +               init_val ^= *(const uint32_t *)pd & LEFT16b_MASK;
> +               pd += 2;
> +       }
> +
> +       if (data_len & 0x1)
> +               init_val ^= *(const uint32_t *)pd & LEFT8b_MASK;
> +
> +       init_val = rte_be_to_cpu_32(init_val);
> +       return init_val;
> +}
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* _RTE_HASH_XOR_H_ */
> --
> 2.34.1
>
>

[-- Attachment #2: Type: text/html, Size: 8022 bytes --]

[PATCH v7 1/1] hash: add XOR32 hash function

[Bili Dong]

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@gmail.com>
---
v7:
* Simplified byte ordering conversion logic. (re Vladimir Medvedkin <medvedkinv@gmail.com>)
* Added test cases with hash key length = 3 (mod 4). (re Vladimir Medvedkin <medvedkinv@gmail.com>)
* Adopted a better way to access bytes. (re Mattias Rönnblom <hofors@lysator.liu.se>)
* Adopted RTE_PTR_ADD for pointer arithmetic. (re Mattias Rönnblom <hofors@lysator.liu.se>)

 .mailmap                       |   1 +
 app/test/test_hash_functions.c |  47 +++++++++++---
 lib/hash/rte_hash_xor.h        | 109 +++++++++++++++++++++++++++++++++
 3 files changed, 147 insertions(+), 10 deletions(-)
 create mode 100644 lib/hash/rte_hash_xor.h

diff --git a/.mailmap b/.mailmap
index 8e3940a253..997d89388f 100644
--- a/.mailmap
+++ b/.mailmap
@@ -164,6 +164,7 @@ Bernard Iremonger <bernard.iremonger@intel.com>
 Bert van Leeuwen <bert.vanleeuwen@netronome.com>
 Bhagyada Modali <bhagyada.modali@amd.com>
 Bharat Mota <bmota@vmware.com>
+Bili Dong <qobilidop@gmail.com>
 Bill Hong <bhong@brocade.com>
 Billy McFall <bmcfall@redhat.com>
 Billy O'Mahony <billy.o.mahony@intel.com>
diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
index 76d51b6e71..61f1341cbc 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,35 +23,48 @@
  * 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,
+static uint32_t hash_values_jhash[2][14] = {{
+	0x8ba9414b, 0xdf0d39c9, 0x6b12f277, 0x589511d8,
 	0xe4cf1d42, 0xd4ccb93c, 0x5e84eafc, 0x21362cfe,
 	0x2f4775ab, 0x9ff036cc, 0xeca51474, 0xbc9d6816,
 	0x12926a31, 0x1c9fa888
 },
 {
-	0x5c62c303, 0x1b8cf784,
+	0x5c62c303, 0x1b8cf784, 0x455e19f7, 0x785de928,
 	0x8270ac65, 0x05fa6668, 0x762df861, 0xda088f2f,
 	0x59614cd4, 0x7a94f690, 0xdc1e4993, 0x30825494,
 	0x91d0e462, 0x768087fc
 }
 };
-static uint32_t hash_values_crc[2][12] = {{
-	0x00000000, 0xf26b8303,
+static uint32_t hash_values_crc[2][14] = {{
+	0x00000000, 0xf26b8303, 0xf299e880, 0x18678721,
 	0x91545164, 0x06040eb1, 0x9bb99201, 0xcc4c4fe4,
 	0x14a90993, 0xf8a5dd8c, 0xcaa1ad0b, 0x7ac1e03e,
 	0x43f44466, 0x4a11475e
 },
 {
-	0xbdfd3980, 0x70204542,
+	0xbdfd3980, 0x70204542, 0x410b3df9, 0xe3f8b2f1,
 	0x98cd4c70, 0xd52c702f, 0x41fc0e1c, 0x3905f65c,
 	0x94bff47f, 0x1bab102d, 0xf4a2c645, 0xbf441539,
 	0x789c104f, 0x53028d3e
 }
 };
+static uint32_t hash_values_xor32[2][14] = {{
+	0x00000000, 0x00010000, 0x00010200, 0x4040403,
+	0x00010203, 0x04040404, 0x00000000, 0x00000000,
+	0x00000000, 0x00000000, 0x0c040404, 0x000d0e0f,
+	0x04212223, 0x04040404
+},
+{
+	0xdeadbeef, 0xdeacbeef, 0xdeacbcef, 0xdaa9baec,
+	0xdeacbcec, 0xdaa9baeb, 0xdeadbeef, 0xdeadbeef,
+	0xdeadbeef, 0xdeadbeef, 0xd2a9baeb, 0xdea0b0e0,
+	0xda8c9ccc, 0xdaa9baeb
+}
+};

 /*******************************************************************************
  * Hash function performance test configuration section. Each performance test
@@ -61,10 +75,10 @@ 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 */
+	1, 2, 3, 7,           /* Unusual key sizes */
 	4, 8, 16, 32, 48, 64, /* standard key sizes */
 	9,                    /* IPv4 SRC + DST + protocol, unpadded */
 	13,                   /* IPv4 5-tuple, unpadded */
@@ -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..7bc0953716
--- /dev/null
+++ b/lib/hash/rte_hash_xor.h
@@ -0,0 +1,109 @@
+/* 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>
+#include <rte_common.h>
+
+/**
+ * The following bytes access helper functions are expected to work
+ * without any particular input buffer alignment requirements.
+ */
+
+static inline uint64_t
+rte_hash_access64(const void *data)
+{
+	uint64_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+static inline uint32_t
+rte_hash_access32(const void *data)
+{
+	uint32_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+static inline uint16_t
+rte_hash_access16(const void *data)
+{
+	uint16_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+static inline uint8_t
+rte_hash_access8(const void *data)
+{
+	uint8_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+/**
+ * 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 = init_val;
+	uint64_t hash64 = 0;
+
+	/* Batch process in 8 bytes for better performance. */
+	uint32_t i;
+	for (i = 0; i < data_len / 8; i++) {
+		hash64 ^= rte_hash_access64(data);
+		data = RTE_PTR_ADD(data, 8);
+	}
+
+	if (data_len & 0x4) {
+		hash64 ^= rte_hash_access32(data);
+		data = RTE_PTR_ADD(data, 4);
+	}
+
+	/* Deal with remaining (< 4) bytes. */
+	uint8_t bit_offset = 0;
+	if (data_len & 0x2) {
+		hash64 ^= rte_hash_access16(data);
+		data = RTE_PTR_ADD(data, 2);
+		bit_offset += 16;
+
+	}
+	if (data_len & 0x1)
+		hash64 ^= rte_hash_access8(data) << bit_offset;
+
+	hash32 ^= rte_be_to_cpu_32((uint32_t)hash64 ^ (hash64 >> 32));
+	return hash32;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_HASH_XOR_H_ */
--
2.41.0.162.gfafddb0af9-goog

Re: [PATCH] hash: add XOR32 hash function

[Bili Dong]

[-- Attachment #1: Type: text/plain, Size: 6626 bytes --]

For the HW I have access to, I think so.

That is actually one of the major final goals of this patch, so we can
model this HW in P4, including all the hash functions it supports, through
the DPDK SWX pipeline.

Thanks,
Bili

On Sat, Jun 17, 2023 at 1:59 PM Stephen Hemminger <
stephen@networkplumber.org> wrote:

> Does it generate same hash as NIC than do it in HW?
>
> On Wed, Feb 15, 2023, 3:31 AM Bili Dong <qobilidop@gmail.com> wrote:
>
>> 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@gmail.com>
>> ---
>>  .mailmap                       |  1 +
>>  app/test/test_hash_functions.c | 33 +++++++++++++++--
>>  lib/hash/rte_hash_xor.h        | 65 ++++++++++++++++++++++++++++++++++
>>  3 files changed, 96 insertions(+), 3 deletions(-)
>>  create mode 100644 lib/hash/rte_hash_xor.h
>>
>> diff --git a/.mailmap b/.mailmap
>> index 5015494210..176dd93b66 100644
>> --- a/.mailmap
>> +++ b/.mailmap
>> @@ -159,6 +159,7 @@ Bernard Iremonger <bernard.iremonger@intel.com>
>>  Bert van Leeuwen <bert.vanleeuwen@netronome.com>
>>  Bhagyada Modali <bhagyada.modali@amd.com>
>>  Bharat Mota <bmota@vmware.com>
>> +Bili Dong <qobilidop@gmail.com>
>>  Bill Hong <bhong@brocade.com>
>>  Billy McFall <bmcfall@redhat.com>
>>  Billy O'Mahony <billy.o.mahony@intel.com>
>> diff --git a/app/test/test_hash_functions.c
>> b/app/test/test_hash_functions.c
>> index 76d51b6e71..14d69d90c4 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_xor[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_xor};
>>  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_xor)
>> +               return "rte_hash_xor";
>> +
>>         return "UnknownHash";
>>  }
>>
>> @@ -173,6 +190,16 @@ verify_precalculated_hash_func_tests(void)
>>                                        hash_values_crc[j][i], hash);
>>                                 return -1;
>>                         }
>> +
>> +                       hash = rte_hash_xor(key, hashtest_key_lens[i],
>> +                                       hashtest_initvals[j]);
>> +                       if (hash != hash_values_xor[j][i]) {
>> +                               printf("XOR 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_xor[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..61ca8bee73
>> --- /dev/null
>> +++ b/lib/hash/rte_hash_xor.h
>> @@ -0,0 +1,65 @@
>> +/* 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>
>> +
>> +#define LEFT8b_MASK rte_cpu_to_be_32(0xff000000)
>> +#define LEFT16b_MASK rte_cpu_to_be_32(0xffff0000)
>> +
>> +/**
>> + * 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_xor(const void *data, uint32_t data_len, uint32_t init_val)
>> +{
>> +       unsigned i;
>> +       uintptr_t pd = (uintptr_t) data;
>> +       init_val = rte_cpu_to_be_32(init_val);
>> +
>> +       for (i = 0; i < data_len / 4; i++) {
>> +               init_val ^= *(const uint32_t *)pd;
>> +               pd += 4;
>> +       }
>> +
>> +       if (data_len & 0x2) {
>> +               init_val ^= *(const uint32_t *)pd & LEFT16b_MASK;
>> +               pd += 2;
>> +       }
>> +
>> +       if (data_len & 0x1)
>> +               init_val ^= *(const uint32_t *)pd & LEFT8b_MASK;
>> +
>> +       init_val = rte_be_to_cpu_32(init_val);
>> +       return init_val;
>> +}
>> +
>> +#ifdef __cplusplus
>> +}
>> +#endif
>> +
>> +#endif /* _RTE_HASH_XOR_H_ */
>> --
>> 2.34.1
>>
>>

[-- Attachment #2: Type: text/html, Size: 8717 bytes --]

Re: [PATCH v7 1/1] hash: add XOR32 hash function

[Medvedkin, Vladimir]

Hi Bili,

Please find just one nit below inlined

Apart from it LGTM

Acked-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>

On 20/06/2023 20:12, Bili Dong wrote:
> 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@gmail.com>
> ---
> v7:
> * Simplified byte ordering conversion logic. (re Vladimir Medvedkin <medvedkinv@gmail.com>)
> * Added test cases with hash key length = 3 (mod 4). (re Vladimir Medvedkin <medvedkinv@gmail.com>)
> * Adopted a better way to access bytes. (re Mattias Rönnblom <hofors@lysator.liu.se>)
> * Adopted RTE_PTR_ADD for pointer arithmetic. (re Mattias Rönnblom <hofors@lysator.liu.se>)
>
>   .mailmap                       |   1 +
>   app/test/test_hash_functions.c |  47 +++++++++++---
>   lib/hash/rte_hash_xor.h        | 109 +++++++++++++++++++++++++++++++++
>   3 files changed, 147 insertions(+), 10 deletions(-)
>   create mode 100644 lib/hash/rte_hash_xor.h
>
> diff --git a/.mailmap b/.mailmap
> index 8e3940a253..997d89388f 100644
> --- a/.mailmap
> +++ b/.mailmap
> @@ -164,6 +164,7 @@ Bernard Iremonger <bernard.iremonger@intel.com>
>   Bert van Leeuwen <bert.vanleeuwen@netronome.com>
>   Bhagyada Modali <bhagyada.modali@amd.com>
>   Bharat Mota <bmota@vmware.com>
> +Bili Dong <qobilidop@gmail.com>
>   Bill Hong <bhong@brocade.com>
>   Billy McFall <bmcfall@redhat.com>
>   Billy O'Mahony <billy.o.mahony@intel.com>
> diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
> index 76d51b6e71..61f1341cbc 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,35 +23,48 @@
>    * 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,
> +static uint32_t hash_values_jhash[2][14] = {{
> +	0x8ba9414b, 0xdf0d39c9, 0x6b12f277, 0x589511d8,
>   	0xe4cf1d42, 0xd4ccb93c, 0x5e84eafc, 0x21362cfe,
>   	0x2f4775ab, 0x9ff036cc, 0xeca51474, 0xbc9d6816,
>   	0x12926a31, 0x1c9fa888
>   },
>   {
> -	0x5c62c303, 0x1b8cf784,
> +	0x5c62c303, 0x1b8cf784, 0x455e19f7, 0x785de928,
>   	0x8270ac65, 0x05fa6668, 0x762df861, 0xda088f2f,
>   	0x59614cd4, 0x7a94f690, 0xdc1e4993, 0x30825494,
>   	0x91d0e462, 0x768087fc
>   }
>   };
> -static uint32_t hash_values_crc[2][12] = {{
> -	0x00000000, 0xf26b8303,
> +static uint32_t hash_values_crc[2][14] = {{
> +	0x00000000, 0xf26b8303, 0xf299e880, 0x18678721,
>   	0x91545164, 0x06040eb1, 0x9bb99201, 0xcc4c4fe4,
>   	0x14a90993, 0xf8a5dd8c, 0xcaa1ad0b, 0x7ac1e03e,
>   	0x43f44466, 0x4a11475e
>   },
>   {
> -	0xbdfd3980, 0x70204542,
> +	0xbdfd3980, 0x70204542, 0x410b3df9, 0xe3f8b2f1,
>   	0x98cd4c70, 0xd52c702f, 0x41fc0e1c, 0x3905f65c,
>   	0x94bff47f, 0x1bab102d, 0xf4a2c645, 0xbf441539,
>   	0x789c104f, 0x53028d3e
>   }
>   };
> +static uint32_t hash_values_xor32[2][14] = {{
> +	0x00000000, 0x00010000, 0x00010200, 0x4040403,
> +	0x00010203, 0x04040404, 0x00000000, 0x00000000,
> +	0x00000000, 0x00000000, 0x0c040404, 0x000d0e0f,
> +	0x04212223, 0x04040404
> +},
> +{
> +	0xdeadbeef, 0xdeacbeef, 0xdeacbcef, 0xdaa9baec,
> +	0xdeacbcec, 0xdaa9baeb, 0xdeadbeef, 0xdeadbeef,
> +	0xdeadbeef, 0xdeadbeef, 0xd2a9baeb, 0xdea0b0e0,
> +	0xda8c9ccc, 0xdaa9baeb
> +}
> +};
>
>   /*******************************************************************************
>    * Hash function performance test configuration section. Each performance test
> @@ -61,10 +75,10 @@ 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 */
> +	1, 2, 3, 7,           /* Unusual key sizes */
>   	4, 8, 16, 32, 48, 64, /* standard key sizes */
>   	9,                    /* IPv4 SRC + DST + protocol, unpadded */
>   	13,                   /* IPv4 5-tuple, unpadded */
> @@ -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..7bc0953716
> --- /dev/null
> +++ b/lib/hash/rte_hash_xor.h
> @@ -0,0 +1,109 @@
> +/* 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>
> +#include <rte_common.h>
> +
> +/**
> + * The following bytes access helper functions are expected to work
> + * without any particular input buffer alignment requirements.
> + */
> +
> +static inline uint64_t
> +rte_hash_access64(const void *data)
> +{
> +	uint64_t v;
> +	memcpy(&v, data, sizeof(v));
> +	return v;
> +}
> +
> +static inline uint32_t
> +rte_hash_access32(const void *data)
> +{
> +	uint32_t v;
> +	memcpy(&v, data, sizeof(v));
> +	return v;
> +}
> +
> +static inline uint16_t
> +rte_hash_access16(const void *data)
> +{
> +	uint16_t v;
> +	memcpy(&v, data, sizeof(v));
> +	return v;
> +}
> +
> +static inline uint8_t
> +rte_hash_access8(const void *data)
> +{
> +	uint8_t v;
> +	memcpy(&v, data, sizeof(v));
> +	return v;
> +}

I don't think this function is necessary.


> +
> +/**
> + * 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 = init_val;
> +	uint64_t hash64 = 0;
> +
> +	/* Batch process in 8 bytes for better performance. */
> +	uint32_t i;
> +	for (i = 0; i < data_len / 8; i++) {
> +		hash64 ^= rte_hash_access64(data);
> +		data = RTE_PTR_ADD(data, 8);
> +	}
> +
> +	if (data_len & 0x4) {
> +		hash64 ^= rte_hash_access32(data);
> +		data = RTE_PTR_ADD(data, 4);
> +	}
> +
> +	/* Deal with remaining (< 4) bytes. */
> +	uint8_t bit_offset = 0;
> +	if (data_len & 0x2) {
> +		hash64 ^= rte_hash_access16(data);
> +		data = RTE_PTR_ADD(data, 2);
> +		bit_offset += 16;
> +
> +	}
> +	if (data_len & 0x1)
> +		hash64 ^= rte_hash_access8(data) << bit_offset;
> +
> +	hash32 ^= rte_be_to_cpu_32((uint32_t)hash64 ^ (hash64 >> 32));
> +	return hash32;
> +}
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* _RTE_HASH_XOR_H_ */
> --
> 2.41.0.162.gfafddb0af9-goog
>
-- 
Regards,
Vladimir

[PATCH v8] hash: add XOR32 hash function

[Bili Dong]

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@gmail.com>
---
v8:
* Removed unnecessary helper function. (re Vladimir Medvedkin <vladimir.medvedkin@intel.com>)

v7:
* Simplified byte ordering conversion logic. (re Vladimir Medvedkin <medvedkinv@gmail.com>)
* Added test cases with hash key length = 3 (mod 4). (re Vladimir Medvedkin <medvedkinv@gmail.com>)
* Adopted a better way to access bytes. (re Mattias Rönnblom <hofors@lysator.liu.se>)
* Adopted RTE_PTR_ADD for pointer arithmetic. (re Mattias Rönnblom <hofors@lysator.liu.se>)

 .mailmap                       |   1 +
 app/test/test_hash_functions.c |  47 +++++++++++----
 lib/hash/rte_hash_xor.h        | 101 +++++++++++++++++++++++++++++++++
 3 files changed, 139 insertions(+), 10 deletions(-)
 create mode 100644 lib/hash/rte_hash_xor.h

diff --git a/.mailmap b/.mailmap
index 8e3940a253..997d89388f 100644
--- a/.mailmap
+++ b/.mailmap
@@ -164,6 +164,7 @@ Bernard Iremonger <bernard.iremonger@intel.com>
 Bert van Leeuwen <bert.vanleeuwen@netronome.com>
 Bhagyada Modali <bhagyada.modali@amd.com>
 Bharat Mota <bmota@vmware.com>
+Bili Dong <qobilidop@gmail.com>
 Bill Hong <bhong@brocade.com>
 Billy McFall <bmcfall@redhat.com>
 Billy O'Mahony <billy.o.mahony@intel.com>
diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
index 76d51b6e71..61f1341cbc 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,35 +23,48 @@
  * 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,
+static uint32_t hash_values_jhash[2][14] = {{
+	0x8ba9414b, 0xdf0d39c9, 0x6b12f277, 0x589511d8,
 	0xe4cf1d42, 0xd4ccb93c, 0x5e84eafc, 0x21362cfe,
 	0x2f4775ab, 0x9ff036cc, 0xeca51474, 0xbc9d6816,
 	0x12926a31, 0x1c9fa888
 },
 {
-	0x5c62c303, 0x1b8cf784,
+	0x5c62c303, 0x1b8cf784, 0x455e19f7, 0x785de928,
 	0x8270ac65, 0x05fa6668, 0x762df861, 0xda088f2f,
 	0x59614cd4, 0x7a94f690, 0xdc1e4993, 0x30825494,
 	0x91d0e462, 0x768087fc
 }
 };
-static uint32_t hash_values_crc[2][12] = {{
-	0x00000000, 0xf26b8303,
+static uint32_t hash_values_crc[2][14] = {{
+	0x00000000, 0xf26b8303, 0xf299e880, 0x18678721,
 	0x91545164, 0x06040eb1, 0x9bb99201, 0xcc4c4fe4,
 	0x14a90993, 0xf8a5dd8c, 0xcaa1ad0b, 0x7ac1e03e,
 	0x43f44466, 0x4a11475e
 },
 {
-	0xbdfd3980, 0x70204542,
+	0xbdfd3980, 0x70204542, 0x410b3df9, 0xe3f8b2f1,
 	0x98cd4c70, 0xd52c702f, 0x41fc0e1c, 0x3905f65c,
 	0x94bff47f, 0x1bab102d, 0xf4a2c645, 0xbf441539,
 	0x789c104f, 0x53028d3e
 }
 };
+static uint32_t hash_values_xor32[2][14] = {{
+	0x00000000, 0x00010000, 0x00010200, 0x4040403,
+	0x00010203, 0x04040404, 0x00000000, 0x00000000,
+	0x00000000, 0x00000000, 0x0c040404, 0x000d0e0f,
+	0x04212223, 0x04040404
+},
+{
+	0xdeadbeef, 0xdeacbeef, 0xdeacbcef, 0xdaa9baec,
+	0xdeacbcec, 0xdaa9baeb, 0xdeadbeef, 0xdeadbeef,
+	0xdeadbeef, 0xdeadbeef, 0xd2a9baeb, 0xdea0b0e0,
+	0xda8c9ccc, 0xdaa9baeb
+}
+};

 /*******************************************************************************
  * Hash function performance test configuration section. Each performance test
@@ -61,10 +75,10 @@ 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 */
+	1, 2, 3, 7,           /* Unusual key sizes */
 	4, 8, 16, 32, 48, 64, /* standard key sizes */
 	9,                    /* IPv4 SRC + DST + protocol, unpadded */
 	13,                   /* IPv4 5-tuple, unpadded */
@@ -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..223154b45c
--- /dev/null
+++ b/lib/hash/rte_hash_xor.h
@@ -0,0 +1,101 @@
+/* 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>
+#include <rte_common.h>
+
+/**
+ * The following bytes access helper functions are expected to work
+ * without any particular input buffer alignment requirements.
+ */
+
+static inline uint64_t
+rte_hash_access64(const void *data)
+{
+	uint64_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+static inline uint32_t
+rte_hash_access32(const void *data)
+{
+	uint32_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+static inline uint16_t
+rte_hash_access16(const void *data)
+{
+	uint16_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+/**
+ * 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 = init_val;
+	uint64_t hash64 = 0;
+
+	/* Batch process in 8 bytes for better performance. */
+	uint32_t i;
+	for (i = 0; i < data_len / 8; i++) {
+		hash64 ^= rte_hash_access64(data);
+		data = RTE_PTR_ADD(data, 8);
+	}
+
+	if (data_len & 0x4) {
+		hash64 ^= rte_hash_access32(data);
+		data = RTE_PTR_ADD(data, 4);
+	}
+
+	/* Deal with remaining (< 4) bytes. */
+	uint8_t bit_offset = 0;
+	if (data_len & 0x2) {
+		hash64 ^= rte_hash_access16(data);
+		data = RTE_PTR_ADD(data, 2);
+		bit_offset += 16;
+
+	}
+	if (data_len & 0x1)
+		hash64 ^= (*(const uint8_t *)data) << bit_offset;
+
+	hash32 ^= rte_be_to_cpu_32((uint32_t)hash64 ^ (hash64 >> 32));
+	return hash32;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_HASH_XOR_H_ */
--
2.34.1

Re: [PATCH v8] hash: add XOR32 hash function

[Stephen Hemminger]

On Thu, 29 Jun 2023 17:33:00 +0000
Bili Dong <qobilidop@gmail.com> wrote:

> +
> +/**
> + * The following bytes access helper functions are expected to work
> + * without any particular input buffer alignment requirements.
> + */
> +

Probably need to avoid users getting tempted to use these helpers
ad exported API's? Mark them with @internal tag?

[PATCH v9] hash: add XOR32 hash function

[Bili Dong]

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@gmail.com>
---
v9:
* Marked internl helper functions as @internal. (re Stephen Hemminger <stephen@networkplumber.org>)

v8:
* Removed unnecessary helper function. (re Vladimir Medvedkin <vladimir.medvedkin@intel.com>)

v7:
* Simplified byte ordering conversion logic. (re Vladimir Medvedkin <medvedkinv@gmail.com>)
* Added test cases with hash key length = 3 (mod 4). (re Vladimir Medvedkin <medvedkinv@gmail.com>)
* Adopted a better way to access bytes. (re Mattias Rönnblom <hofors@lysator.liu.se>)
* Adopted RTE_PTR_ADD for pointer arithmetic. (re Mattias Rönnblom <hofors@lysator.liu.se>)

 .mailmap                       |   1 +
 app/test/test_hash_functions.c |  47 +++++++++++---
 lib/hash/rte_hash_xor.h        | 113 +++++++++++++++++++++++++++++++++
 3 files changed, 151 insertions(+), 10 deletions(-)
 create mode 100644 lib/hash/rte_hash_xor.h

diff --git a/.mailmap b/.mailmap
index 8e3940a253..997d89388f 100644
--- a/.mailmap
+++ b/.mailmap
@@ -164,6 +164,7 @@ Bernard Iremonger <bernard.iremonger@intel.com>
 Bert van Leeuwen <bert.vanleeuwen@netronome.com>
 Bhagyada Modali <bhagyada.modali@amd.com>
 Bharat Mota <bmota@vmware.com>
+Bili Dong <qobilidop@gmail.com>
 Bill Hong <bhong@brocade.com>
 Billy McFall <bmcfall@redhat.com>
 Billy O'Mahony <billy.o.mahony@intel.com>
diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
index 76d51b6e71..61f1341cbc 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,35 +23,48 @@
  * 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,
+static uint32_t hash_values_jhash[2][14] = {{
+	0x8ba9414b, 0xdf0d39c9, 0x6b12f277, 0x589511d8,
 	0xe4cf1d42, 0xd4ccb93c, 0x5e84eafc, 0x21362cfe,
 	0x2f4775ab, 0x9ff036cc, 0xeca51474, 0xbc9d6816,
 	0x12926a31, 0x1c9fa888
 },
 {
-	0x5c62c303, 0x1b8cf784,
+	0x5c62c303, 0x1b8cf784, 0x455e19f7, 0x785de928,
 	0x8270ac65, 0x05fa6668, 0x762df861, 0xda088f2f,
 	0x59614cd4, 0x7a94f690, 0xdc1e4993, 0x30825494,
 	0x91d0e462, 0x768087fc
 }
 };
-static uint32_t hash_values_crc[2][12] = {{
-	0x00000000, 0xf26b8303,
+static uint32_t hash_values_crc[2][14] = {{
+	0x00000000, 0xf26b8303, 0xf299e880, 0x18678721,
 	0x91545164, 0x06040eb1, 0x9bb99201, 0xcc4c4fe4,
 	0x14a90993, 0xf8a5dd8c, 0xcaa1ad0b, 0x7ac1e03e,
 	0x43f44466, 0x4a11475e
 },
 {
-	0xbdfd3980, 0x70204542,
+	0xbdfd3980, 0x70204542, 0x410b3df9, 0xe3f8b2f1,
 	0x98cd4c70, 0xd52c702f, 0x41fc0e1c, 0x3905f65c,
 	0x94bff47f, 0x1bab102d, 0xf4a2c645, 0xbf441539,
 	0x789c104f, 0x53028d3e
 }
 };
+static uint32_t hash_values_xor32[2][14] = {{
+	0x00000000, 0x00010000, 0x00010200, 0x4040403,
+	0x00010203, 0x04040404, 0x00000000, 0x00000000,
+	0x00000000, 0x00000000, 0x0c040404, 0x000d0e0f,
+	0x04212223, 0x04040404
+},
+{
+	0xdeadbeef, 0xdeacbeef, 0xdeacbcef, 0xdaa9baec,
+	0xdeacbcec, 0xdaa9baeb, 0xdeadbeef, 0xdeadbeef,
+	0xdeadbeef, 0xdeadbeef, 0xd2a9baeb, 0xdea0b0e0,
+	0xda8c9ccc, 0xdaa9baeb
+}
+};

 /*******************************************************************************
  * Hash function performance test configuration section. Each performance test
@@ -61,10 +75,10 @@ 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 */
+	1, 2, 3, 7,           /* Unusual key sizes */
 	4, 8, 16, 32, 48, 64, /* standard key sizes */
 	9,                    /* IPv4 SRC + DST + protocol, unpadded */
 	13,                   /* IPv4 5-tuple, unpadded */
@@ -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..7175841507
--- /dev/null
+++ b/lib/hash/rte_hash_xor.h
@@ -0,0 +1,113 @@
+/* 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>
+#include <rte_common.h>
+
+/**
+ * The following bytes access helper functions are expected to work
+ * without any particular input buffer alignment requirements.
+ */
+
+/**
+ * @internal
+ * Access the next 8 bytes.
+ */
+static inline uint64_t
+rte_hash_access64(const void *data)
+{
+	uint64_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+/**
+ * @internal
+ * Access the next 4 bytes.
+ */
+static inline uint32_t
+rte_hash_access32(const void *data)
+{
+	uint32_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+/**
+ * @internal
+ * Access the next 2 bytes.
+ */
+static inline uint16_t
+rte_hash_access16(const void *data)
+{
+	uint16_t v;
+	memcpy(&v, data, sizeof(v));
+	return v;
+}
+
+/**
+ * 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 = init_val;
+	uint64_t hash64 = 0;
+
+	/* Batch process in 8 bytes for better performance. */
+	uint32_t i;
+	for (i = 0; i < data_len / 8; i++) {
+		hash64 ^= rte_hash_access64(data);
+		data = RTE_PTR_ADD(data, 8);
+	}
+
+	if (data_len & 0x4) {
+		hash64 ^= rte_hash_access32(data);
+		data = RTE_PTR_ADD(data, 4);
+	}
+
+	/* Deal with remaining (< 4) bytes. */
+	uint8_t bit_offset = 0;
+	if (data_len & 0x2) {
+		hash64 ^= rte_hash_access16(data);
+		data = RTE_PTR_ADD(data, 2);
+		bit_offset += 16;
+
+	}
+	if (data_len & 0x1)
+		hash64 ^= (*(const uint8_t *)data) << bit_offset;
+
+	hash32 ^= rte_be_to_cpu_32((uint32_t)hash64 ^ (hash64 >> 32));
+	return hash32;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_HASH_XOR_H_ */
--
2.41.0.390.g38632f3daf-goog

Re: [PATCH v8] hash: add XOR32 hash function

[Bili Dong]

[-- Attachment #1: Type: text/plain, Size: 542 bytes --]

Thanks for the suggestion! It's fixed in the latest version.

On Thu, Jul 6, 2023 at 1:08 PM Stephen Hemminger <stephen@networkplumber.org>
wrote:

> On Thu, 29 Jun 2023 17:33:00 +0000
> Bili Dong <qobilidop@gmail.com> wrote:
>
> > +
> > +/**
> > + * The following bytes access helper functions are expected to work
> > + * without any particular input buffer alignment requirements.
> > + */
> > +
>
> Probably need to avoid users getting tempted to use these helpers
> ad exported API's? Mark them with @internal tag?
>

[-- Attachment #2: Type: text/html, Size: 935 bytes --]

Re: [PATCH v9] hash: add XOR32 hash function

[David Marchand]

On Tue, Jul 11, 2023 at 12:00 AM Bili Dong <qobilidop@gmail.com> wrote:
>
> 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@gmail.com>

Review, please.


-- 
David Marchand

Re: [PATCH v9] hash: add XOR32 hash function

[Medvedkin, Vladimir]

Acked-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>

On 10/07/2023 22:59, Bili Dong wrote:
> 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@gmail.com>
>
>
>
-- 
Regards,
Vladimir

Re: [PATCH v9] hash: add XOR32 hash function

[David Marchand]

Hello,

On Tue, Jul 11, 2023 at 12:00 AM Bili Dong <qobilidop@gmail.com> wrote:
>
> 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@gmail.com>
>  .mailmap                       |   1 +
>  app/test/test_hash_functions.c |  47 +++++++++++---
>  lib/hash/rte_hash_xor.h        | 113 +++++++++++++++++++++++++++++++++
>  3 files changed, 151 insertions(+), 10 deletions(-)
>  create mode 100644 lib/hash/rte_hash_xor.h
>

I was about to merge this patch but there are some issues that should
have been caught by the library maintainer...

It seems the intention is to have a public API (meaning external DPDK
apps) consumption.
Then the header must be exported via 'headers' in lib/hash/meson.build.
Besides, such API addition must be announced in the release notes.
And this API should be documented either in some doc/guides/ or at
least with doxygen (meaning that rte_hash_xor.h must be referenced in
doc/api/doxy-api-index.md).


Thanks.

-- 
David Marchand