DPDK patches and discussions
 help / color / mirror / Atom feed
From: Didier Pallard <didier.pallard@6wind.com>
To: dev@dpdk.org, bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com
Subject: [dpdk-dev] [PATCH] hash: fix CRC32c computation
Date: Tue, 22 Dec 2015 10:34:58 +0100	[thread overview]
Message-ID: <1450776898-8951-1-git-send-email-didier.pallard@6wind.com> (raw)

As demonstrated by the following code, CRC32c computation is not valid
when buffer length is not a multiple of 4 bytes:
(Output obtained by code below)

CRC of 1 NULL bytes expected: 0x527d5351
    soft: 527d5351
    rte accelerated: 48674bc7
    rte soft: 48674bc7
CRC of 2 NULL bytes expected: 0xf16177d2
    soft: f16177d2
    rte accelerated: 48674bc7
    rte soft: 48674bc7
CRC of 2x1 NULL bytes expected: 0xf16177d2
    soft: f16177d2
    rte accelerated: 8c28b28a
    rte soft: 8c28b28a
CRC of 3 NULL bytes expected: 0x6064a37a
    soft: 6064a37a
    rte accelerated: 48674bc7
    rte soft: 48674bc7
CRC of 4 NULL bytes expected: 0x48674bc7
    soft: 48674bc7
    rte accelerated: 48674bc7
    rte soft: 48674bc7

Values returned by rte_hash_crc functions does not match the one
computed by a trivial crc32c implementation.

ARM code is a guess, it is not tested, neither compiled.

code showing the problem:

uint8_t null_test[32] = {0};

static uint32_t crc32c_trivial(uint8_t *buffer, uint32_t length, uint32_t crc)
{
    uint32_t i, j;
    for (i = 0; i < length; ++i)
    {
        crc = crc ^ buffer[i];
        for (j = 0; j < 8; j++)
            crc = (crc >> 1) ^ 0x80000000 ^ ((~crc & 1) * 0x82f63b78);
    }
    return crc;
}

void hash_test(void);
void hash_test(void)
{
	printf("CRC of 1 nul byte expected: 0x527d5351\n");
	printf("    soft: %08x\n", crc32c_trivial(null_test, 1, 0));
	rte_hash_crc_init_alg();
	printf("    rte accelerated: %08x\n", ~rte_hash_crc(null_test, 1, 0xFFFFFFFF));
	rte_hash_crc_set_alg(CRC32_SW);
	printf("    rte soft: %08x\n", ~rte_hash_crc(null_test, 1, 0xFFFFFFFF));

	printf("CRC of 2 nul bytes expected: 0xf16177d2\n");
	printf("    soft: %08x\n", crc32c_trivial(null_test, 2, 0));
	rte_hash_crc_init_alg();
	printf("    rte accelerated: %08x\n", ~rte_hash_crc(null_test, 2, 0xFFFFFFFF));
	rte_hash_crc_set_alg(CRC32_SW);
	printf("    rte soft: %08x\n", ~rte_hash_crc(null_test, 2, 0xFFFFFFFF));

	printf("CRC of 2x1 nul bytes expected: 0xf16177d2\n");
	printf("    soft: %08x\n", crc32c_trivial(null_test, 1, crc32c_trivial(null_test, 1, 0)));
	rte_hash_crc_init_alg();
	printf("    rte accelerated: %08x\n", ~rte_hash_crc(null_test, 1, rte_hash_crc(null_test, 1, 0xFFFFFFFF)));
	rte_hash_crc_set_alg(CRC32_SW);
	printf("    rte soft: %08x\n", ~rte_hash_crc(null_test, 1, rte_hash_crc(null_test, 1, 0xFFFFFFFF)));

	printf("CRC of 3 nul bytes expected: 0x6064a37a\n");
	printf("    soft: %08x\n", crc32c_trivial(null_test, 3, 0));
	rte_hash_crc_init_alg();
	printf("    rte accelerated: %08x\n", ~rte_hash_crc(null_test, 3, 0xFFFFFFFF));
	rte_hash_crc_set_alg(CRC32_SW);
	printf("    rte soft: %08x\n", ~rte_hash_crc(null_test, 3, 0xFFFFFFFF));

	printf("CRC of 4 nul bytes expected: 0x48674bc7\n");
	printf("    soft: %08x\n", crc32c_trivial(null_test, 4, 0));
	rte_hash_crc_init_alg();
	printf("    rte accelerated: %08x\n", ~rte_hash_crc(null_test, 4, 0xFFFFFFFF));
	rte_hash_crc_set_alg(CRC32_SW);
	printf("    rte soft: %08x\n", ~rte_hash_crc(null_test, 4, 0xFFFFFFFF));
}

Signed-off-by: Didier Pallard <didier.pallard@6wind.com>
Acked-by: David Marchand <david.marchand@6wind.com>
---
 lib/librte_hash/rte_crc_arm64.h |  64 ++++++++++++++++++++
 lib/librte_hash/rte_hash_crc.h  | 125 +++++++++++++++++++++++++++++++---------
 2 files changed, 162 insertions(+), 27 deletions(-)

diff --git a/lib/librte_hash/rte_crc_arm64.h b/lib/librte_hash/rte_crc_arm64.h
index 02e26bc..44ef460 100644
--- a/lib/librte_hash/rte_crc_arm64.h
+++ b/lib/librte_hash/rte_crc_arm64.h
@@ -50,6 +50,28 @@ extern "C" {
 #include <rte_common.h>
 
 static inline uint32_t
+crc32c_arm64_u8(uint8_t data, uint32_t init_val)
+{
+	asm(".arch armv8-a+crc");
+	__asm__ volatile(
+			"crc32cb %w[crc], %w[crc], %b[value]"
+			: [crc] "+r" (init_val)
+			: [value] "r" (data));
+	return init_val;
+}
+
+static inline uint32_t
+crc32c_arm64_u16(uint16_t data, uint32_t init_val)
+{
+	asm(".arch armv8-a+crc");
+	__asm__ volatile(
+			"crc32ch %w[crc], %w[crc], %h[value]"
+			: [crc] "+r" (init_val)
+			: [value] "r" (data));
+	return init_val;
+}
+
+static inline uint32_t
 crc32c_arm64_u32(uint32_t data, uint32_t init_val)
 {
 	asm(".arch armv8-a+crc");
@@ -103,6 +125,48 @@ rte_hash_crc_init_alg(void)
 }
 
 /**
+ * Use single crc32 instruction to perform a hash on a 1 byte value.
+ * Fall back to software crc32 implementation in case arm64 crc intrinsics is
+ * not supported
+ *
+ * @param data
+ *   Data to perform hash on.
+ * @param init_val
+ *   Value to initialise hash generator.
+ * @return
+ *   32bit calculated hash value.
+ */
+static inline uint32_t
+rte_hash_crc_1byte(uint8_t data, uint32_t init_val)
+{
+	if (likely(crc32_alg & CRC32_ARM64))
+		return crc32c_arm64_u8(data, init_val);
+
+	return crc32c_1byte(data, init_val);
+}
+
+/**
+ * Use single crc32 instruction to perform a hash on a 2 bytes value.
+ * Fall back to software crc32 implementation in case arm64 crc intrinsics is
+ * not supported
+ *
+ * @param data
+ *   Data to perform hash on.
+ * @param init_val
+ *   Value to initialise hash generator.
+ * @return
+ *   32bit calculated hash value.
+ */
+static inline uint32_t
+rte_hash_crc_2byte(uint16_t data, uint32_t init_val)
+{
+	if (likely(crc32_alg & CRC32_ARM64))
+		return crc32c_arm64_u16(data, init_val);
+
+	return crc32c_2bytes(data, init_val);
+}
+
+/**
  * Use single crc32 instruction to perform a hash on a 4 byte value.
  * Fall back to software crc32 implementation in case arm64 crc intrinsics is
  * not supported
diff --git a/lib/librte_hash/rte_hash_crc.h b/lib/librte_hash/rte_hash_crc.h
index 78a34b7..485f8a2 100644
--- a/lib/librte_hash/rte_hash_crc.h
+++ b/lib/librte_hash/rte_hash_crc.h
@@ -328,6 +328,28 @@ static const uint32_t crc32c_tables[8][256] = {{
 	 crc32c_tables[(n)-1][((crc) >> 8) & 0xFF])
 
 static inline uint32_t
+crc32c_1byte(uint8_t data, uint32_t init_val)
+{
+	uint32_t crc;
+	crc = init_val;
+	crc ^= data;
+
+	return crc32c_tables[0][crc & 0xff] ^ (crc >> 8);
+}
+
+static inline uint32_t
+crc32c_2bytes(uint16_t data, uint32_t init_val)
+{
+	uint32_t crc;
+	crc = init_val;
+	crc ^= data;
+
+	crc = CRC32_UPD(crc, 1) ^ (crc >> 16);
+
+	return crc;
+}
+
+static inline uint32_t
 crc32c_1word(uint32_t data, uint32_t init_val)
 {
 	uint32_t crc, term1, term2;
@@ -367,6 +389,26 @@ crc32c_2words(uint64_t data, uint32_t init_val)
 
 #if defined(RTE_ARCH_I686) || defined(RTE_ARCH_X86_64)
 static inline uint32_t
+crc32c_sse42_u8(uint8_t data, uint32_t init_val)
+{
+	__asm__ volatile(
+			"crc32b %[data], %[init_val];"
+			: [init_val] "+r" (init_val)
+			: [data] "rm" (data));
+	return init_val;
+}
+
+static inline uint32_t
+crc32c_sse42_u16(uint16_t data, uint32_t init_val)
+{
+	__asm__ volatile(
+			"crc32w %[data], %[init_val];"
+			: [init_val] "+r" (init_val)
+			: [data] "rm" (data));
+	return init_val;
+}
+
+static inline uint32_t
 crc32c_sse42_u32(uint32_t data, uint32_t init_val)
 {
 	__asm__ volatile(
@@ -453,6 +495,52 @@ rte_hash_crc_init_alg(void)
 }
 
 /**
+ * Use single crc32 instruction to perform a hash on a byte value.
+ * Fall back to software crc32 implementation in case SSE4.2 is
+ * not supported
+ *
+ * @param data
+ *   Data to perform hash on.
+ * @param init_val
+ *   Value to initialise hash generator.
+ * @return
+ *   32bit calculated hash value.
+ */
+static inline uint32_t
+rte_hash_crc_1byte(uint8_t data, uint32_t init_val)
+{
+#if defined RTE_ARCH_I686 || defined RTE_ARCH_X86_64
+	if (likely(crc32_alg & CRC32_SSE42))
+		return crc32c_sse42_u8(data, init_val);
+#endif
+
+	return crc32c_1byte(data, init_val);
+}
+
+/**
+ * Use single crc32 instruction to perform a hash on a byte value.
+ * Fall back to software crc32 implementation in case SSE4.2 is
+ * not supported
+ *
+ * @param data
+ *   Data to perform hash on.
+ * @param init_val
+ *   Value to initialise hash generator.
+ * @return
+ *   32bit calculated hash value.
+ */
+static inline uint32_t
+rte_hash_crc_2byte(uint16_t data, uint32_t init_val)
+{
+#if defined RTE_ARCH_I686 || defined RTE_ARCH_X86_64
+	if (likely(crc32_alg & CRC32_SSE42))
+		return crc32c_sse42_u16(data, init_val);
+#endif
+
+	return crc32c_2bytes(data, init_val);
+}
+
+/**
  * Use single crc32 instruction to perform a hash on a 4 byte value.
  * Fall back to software crc32 implementation in case SSE4.2 is
  * not supported
@@ -521,7 +609,6 @@ static inline uint32_t
 rte_hash_crc(const void *data, uint32_t data_len, uint32_t init_val)
 {
 	unsigned i;
-	uint64_t temp = 0;
 	uintptr_t pd = (uintptr_t) data;
 
 	for (i = 0; i < data_len / 8; i++) {
@@ -529,35 +616,19 @@ rte_hash_crc(const void *data, uint32_t data_len, uint32_t init_val)
 		pd += 8;
 	}
 
-	switch (7 - (data_len & 0x07)) {
-	case 0:
-		temp |= (uint64_t) *((const uint8_t *)pd + 6) << 48;
-		/* Fallthrough */
-	case 1:
-		temp |= (uint64_t) *((const uint8_t *)pd + 5) << 40;
-		/* Fallthrough */
-	case 2:
-		temp |= (uint64_t) *((const uint8_t *)pd + 4) << 32;
-		temp |= *(const uint32_t *)pd;
-		init_val = rte_hash_crc_8byte(temp, init_val);
-		break;
-	case 3:
+	if (data_len & 0x4) {
 		init_val = rte_hash_crc_4byte(*(const uint32_t *)pd, init_val);
-		break;
-	case 4:
-		temp |= *((const uint8_t *)pd + 2) << 16;
-		/* Fallthrough */
-	case 5:
-		temp |= *((const uint8_t *)pd + 1) << 8;
-		/* Fallthrough */
-	case 6:
-		temp |= *(const uint8_t *)pd;
-		init_val = rte_hash_crc_4byte(temp, init_val);
-		/* Fallthrough */
-	default:
-		break;
+		pd += 4;
+	}
+
+	if (data_len & 0x2) {
+		init_val = rte_hash_crc_2byte(*(const uint16_t *)pd, init_val);
+		pd += 2;
 	}
 
+	if (data_len & 0x1)
+		init_val = rte_hash_crc_1byte(*(const uint8_t *)pd, init_val);
+
 	return init_val;
 }
 
-- 
2.1.4

             reply	other threads:[~2015-12-22  9:35 UTC|newest]

Thread overview: 13+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-12-22  9:34 Didier Pallard [this message]
2015-12-23  9:12 ` Qiu, Michael
2015-12-23 11:37   ` Vincent JARDIN
     [not found]     ` <E115CCD9D858EF4F90C690B0DCB4D8973C8A16BD@IRSMSX108.ger.corp.intel.com>
2016-02-08 14:43       ` De Lara Guarch, Pablo
2016-02-09  9:34 ` [dpdk-dev] [PATCH v2] " Didier Pallard
2016-02-10 12:16   ` De Lara Guarch, Pablo
2016-02-19 11:00   ` [dpdk-dev] [PATCH v3 0/2] Fix " Didier Pallard
2016-02-19 11:00     ` [dpdk-dev] [PATCH v3 1/2] test: fix CRC hash function autotest Didier Pallard
2016-02-19 11:00     ` [dpdk-dev] [PATCH v3 2/2] hash: fix CRC32c computation Didier Pallard
2016-02-19 15:08     ` [dpdk-dev] [PATCH v3 0/2] Fix " De Lara Guarch, Pablo
2016-03-01 13:31       ` Thomas Monjalon
2016-02-10 14:35 ` [dpdk-dev] [PATCH] hash: fix " Pattan, Reshma
2016-02-11  8:21   ` Didier Pallard

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=1450776898-8951-1-git-send-email-didier.pallard@6wind.com \
    --to=didier.pallard@6wind.com \
    --cc=bruce.richardson@intel.com \
    --cc=dev@dpdk.org \
    --cc=pablo.de.lara.guarch@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).