From: Bili Dong <qobilidop@gmail.com>
To: Vladimir Medvedkin <medvedkinv@gmail.com>
Cc: vladimir.medvedkin@intel.com, dev@dpdk.org,
cristian.dumitrescu@intel.com,
Bruce Richardson <bruce.richardson@intel.com>,
yipeng1.wang@intel.com, sameh.gobriel@intel.com,
Thomas Monjalon <thomas@monjalon.net>
Subject: Re: [PATCH v6] hash: add XOR32 hash function
Date: Fri, 16 Jun 2023 10:15:25 -0700 [thread overview]
Message-ID: <CAFnY8dFBrL1-PsQ0FM_n73oE73pMatG9aZe_Bhw_mxhmkpUmzw@mail.gmail.com> (raw)
In-Reply-To: <CANDrEHmH3Gq11ngtQQ9mc2XGBsL+V_v4uOh-Cbv9M0qFyDNYHw@mail.gmail.com>
[-- 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 --]
next prev parent reply other threads:[~2023-06-16 17:16 UTC|newest]
Thread overview: 38+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-02-15 10:30 [PATCH] " Bili Dong
2023-02-15 10:54 ` [PATCH v2] " Bili Dong
2023-02-15 11:06 ` [PATCH v3] " Bili Dong
2023-02-15 11:39 ` Morten Brørup
2023-02-15 21:39 ` Bili Dong
2023-02-16 9:49 ` Morten Brørup
2023-02-20 13:49 ` Thomas Monjalon
2023-02-20 17:21 ` Bili Dong
2023-02-20 17:38 ` Thomas Monjalon
2023-02-20 17:51 ` Bruce Richardson
2023-02-20 17:54 ` Bili Dong
2023-02-20 18:19 ` Dumitrescu, Cristian
2023-02-20 18:50 ` Bili Dong
2023-02-20 20:10 ` Medvedkin, Vladimir
2023-02-20 20:17 ` Bili Dong
2023-02-20 20:19 ` Dumitrescu, Cristian
2023-02-20 20:44 ` Bili Dong
2023-02-20 23:04 ` Stephen Hemminger
2023-02-21 1:38 ` Bili Dong
2023-02-21 16:47 ` [PATCH v4] " Bili Dong
2023-02-21 17:55 ` [PATCH v5] " Bili Dong
2023-02-21 19:37 ` [PATCH v6] " Bili Dong
2023-02-21 21:35 ` Bili Dong
2023-06-12 14:56 ` Thomas Monjalon
2023-06-15 17:14 ` Vladimir Medvedkin
2023-06-16 17:15 ` Bili Dong [this message]
2023-06-17 20:34 ` Mattias Rönnblom
2023-06-20 19:12 ` [PATCH v7 1/1] " Bili Dong
2023-06-28 19:19 ` Medvedkin, Vladimir
2023-06-29 17:33 ` [PATCH v8] " Bili Dong
2023-07-06 20:08 ` Stephen Hemminger
2023-07-10 22:01 ` Bili Dong
2023-07-10 21:59 ` [PATCH v9] " Bili Dong
2023-09-29 15:38 ` David Marchand
2023-10-03 16:51 ` Medvedkin, Vladimir
2023-10-06 8:06 ` David Marchand
2023-06-17 20:59 ` [PATCH] " Stephen Hemminger
2023-06-20 19:27 ` Bili Dong
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAFnY8dFBrL1-PsQ0FM_n73oE73pMatG9aZe_Bhw_mxhmkpUmzw@mail.gmail.com \
--to=qobilidop@gmail.com \
--cc=bruce.richardson@intel.com \
--cc=cristian.dumitrescu@intel.com \
--cc=dev@dpdk.org \
--cc=medvedkinv@gmail.com \
--cc=sameh.gobriel@intel.com \
--cc=thomas@monjalon.net \
--cc=vladimir.medvedkin@intel.com \
--cc=yipeng1.wang@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).