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

["Mattias Rönnblom" <hofors@lysator.liu.se>]

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
>