From patchwork Tue May 5 14:43:52 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "De Lara Guarch, Pablo" X-Patchwork-Id: 4630 Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [IPv6:::1]) by dpdk.org (Postfix) with ESMTP id D9AC13195; Tue, 5 May 2015 16:44:19 +0200 (CEST) Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by dpdk.org (Postfix) with ESMTP id 645831396 for ; Tue, 5 May 2015 16:44:17 +0200 (CEST) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by orsmga101.jf.intel.com with ESMTP; 05 May 2015 07:43:56 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.13,373,1427785200"; d="scan'208";a="489619703" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by FMSMGA003.fm.intel.com with ESMTP; 05 May 2015 07:43:56 -0700 Received: from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com [10.237.217.46]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id t45Ehsvx022796 for ; Tue, 5 May 2015 15:43:55 +0100 Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t45Ehs1u021104 for ; Tue, 5 May 2015 15:43:54 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t45EhsEG021100 for dev@dpdk.org; Tue, 5 May 2015 15:43:54 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Tue, 5 May 2015 15:43:52 +0100 Message-Id: <1430837034-21031-5-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1430837034-21031-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1429874587-17939-1-git-send-email-pablo.de.lara.guarch@intel.com> <1430837034-21031-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH v3 4/6] hash: add two new functions to jhash library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" With the jhash update, two new functions were introduced: - rte_jhash_2hashes: Same as rte_jhash, but takes two seeds and return two hashes (uint32_ts) - rte_jhash2_2hashes: Same as rte_jhash2, but takes two seeds and return two hashes (uint32_ts) Signed-off-by: Pablo de Lara --- lib/librte_hash/rte_jhash.h | 195 +++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 195 insertions(+), 0 deletions(-) diff --git a/lib/librte_hash/rte_jhash.h b/lib/librte_hash/rte_jhash.h index 0e96b7c..9e82d06 100644 --- a/lib/librte_hash/rte_jhash.h +++ b/lib/librte_hash/rte_jhash.h @@ -292,6 +292,201 @@ rte_jhash2(const uint32_t *k, uint32_t length, uint32_t initval) return c; } +/** + * Same as rte_jhash, but takes two seeds and return two uint32_ts. + * pc and pb must be non-null, and *pc and *pb must both be initialized + * with seeds. If you pass in (*pb)=0, the output (*pc) will be + * the same as the return value from rte_jhash. + * + * @param k + * Key to calculate hash of. + * @param length + * Length of key in bytes. + * @param pc + * IN: seed OUT: primary hash value. + * @param pc + * IN: second seed OUT: secondary hash value. + */ +static inline void +rte_jhash_2hashes(const void *key, uint32_t length, uint32_t *pc, uint32_t *pb) +{ + uint32_t a, b, c; + union { + const void *ptr; + size_t i; + } u; + + /* Set up the internal state */ + a = b = c = RTE_JHASH_GOLDEN_RATIO + ((uint32_t)length) + *pc; + c += *pb; + + u.ptr = key; + + /* Check key alignment. For x86 architecture, first case is always optimal */ + if (!strcmp(RTE_ARCH,"x86_64") || !strcmp(RTE_ARCH,"i686") || (u.i & 0x3) == 0) { + const uint32_t *k = (const uint32_t *)key; + + while (length > 12) { + a += k[0]; + b += k[1]; + c += k[2]; + + __rte_jhash_mix(a, b, c); + + k += 3; + length -= 12; + } + + switch (length) { + case 12: + c += k[2]; b += k[1]; a += k[0]; break; + case 11: + c += k[2] & LOWER24b_MASK; b += k[1]; a += k[0]; break; + case 10: + c += k[2] & LOWER16b_MASK; b += k[1]; a += k[0]; break; + case 9: + c += k[2] & LOWER8b_MASK; b += k[1]; a += k[0]; break; + case 8: + b += k[1]; a += k[0]; break; + case 7: + b += k[1] & LOWER24b_MASK; a += k[0]; break; + case 6: + b += k[1] & LOWER16b_MASK; a += k[0]; break; + case 5: + b += k[1] & LOWER8b_MASK; a += k[0]; break; + case 4: + a += k[0]; break; + case 3: + a += k[0] & LOWER24b_MASK; break; + case 2: + a += k[0] & LOWER16b_MASK; break; + case 1: + a += k[0] & LOWER8b_MASK; break; + /* zero length strings require no mixing */ + case 0: + *pc = c; + *pb = b; + return; + }; + } else { + const uint8_t *k = (const uint8_t *)key; + + /* all but the last block: affect some 32 bits of (a, b, c) */ + while (length > 12) { + a += ((uint32_t)k[0]) << RTE_JHASH_BYTE0_SHIFT; + a += ((uint32_t)k[1]) << RTE_JHASH_BYTE1_SHIFT; + a += ((uint32_t)k[2]) << RTE_JHASH_BYTE2_SHIFT; + a += ((uint32_t)k[3]) << RTE_JHASH_BYTE3_SHIFT; + b += ((uint32_t)k[4]) << RTE_JHASH_BYTE0_SHIFT; + b += ((uint32_t)k[5]) << RTE_JHASH_BYTE1_SHIFT; + b += ((uint32_t)k[6]) << RTE_JHASH_BYTE2_SHIFT; + b += ((uint32_t)k[7]) << RTE_JHASH_BYTE3_SHIFT; + c += ((uint32_t)k[8]) << RTE_JHASH_BYTE0_SHIFT; + c += ((uint32_t)k[9]) << RTE_JHASH_BYTE1_SHIFT; + c += ((uint32_t)k[10]) << RTE_JHASH_BYTE2_SHIFT; + c += ((uint32_t)k[11]) << RTE_JHASH_BYTE3_SHIFT; + + __rte_jhash_mix(a, b, c); + + k += 12; + length -= 12; + } + + /* last block: affect all 32 bits of (c) */ + /* all the case statements fall through */ + switch (length) { + case 12: + c += ((uint32_t)k[11]) << RTE_JHASH_BYTE3_SHIFT; + case 11: + c += ((uint32_t)k[10]) << RTE_JHASH_BYTE2_SHIFT; + case 10: + c += ((uint32_t)k[9]) << RTE_JHASH_BYTE1_SHIFT; + case 9: + c += ((uint32_t)k[8]) << RTE_JHASH_BYTE0_SHIFT; + case 8: + b += ((uint32_t)k[7]) << RTE_JHASH_BYTE3_SHIFT; + case 7: + b += ((uint32_t)k[6]) << RTE_JHASH_BYTE2_SHIFT; + case 6: + b += ((uint32_t)k[5]) << RTE_JHASH_BYTE1_SHIFT; + case 5: + b += ((uint32_t)k[4]) << RTE_JHASH_BYTE0_SHIFT; + case 4: + a += ((uint32_t)k[3]) << RTE_JHASH_BYTE3_SHIFT; + case 3: + a += ((uint32_t)k[2]) << RTE_JHASH_BYTE2_SHIFT; + case 2: + a += ((uint32_t)k[1]) << RTE_JHASH_BYTE1_SHIFT; + case 1: + a += ((uint32_t)k[0]) << RTE_JHASH_BYTE0_SHIFT; + break; + case 0: + *pc = c; + *pb = b; + return; + } + } + + __rte_jhash_final(a, b, c); + + *pc = c; + *pb = b; +} + +/** + * Same as rte_jhash2, but takes two seeds and return two uint32_ts. + * pc and pb must be non-null, and *pc and *pb must both be initialized + * with seeds. If you pass in (*pb)=0, the output (*pc) will be + * the same as the return value from rte_jhash2. + * + * @param k + * Key to calculate hash of. + * @param length + * Length of key in units of 4 bytes. + * @param pc + * IN: seed OUT: primary hash value. + * @param pc + * IN: second seed OUT: secondary hash value. + */ +static inline void +rte_jhash2_2hashes(const uint32_t *k, uint32_t length, uint32_t *pc, uint32_t *pb) +{ + uint32_t a, b, c; + + /* Set up the internal state */ + a = b = c = RTE_JHASH_GOLDEN_RATIO + (((uint32_t)length) << 2) + *pc; + c += *pb; + + /* Handle most of the key */ + while (length > 3) { + a += k[0]; + b += k[1]; + c += k[2]; + + __rte_jhash_mix(a, b, c); + + k += 3; + length -= 3; + } + + /* Handle the last 3 uint32_t's */ + switch (length) { + case 3: + c += k[2]; + case 2: + b += k[1]; + case 1: + a += k[0]; + __rte_jhash_final(a, b, c); + /* case 0: nothing left to add */ + case 0: + break; + }; + + *pc = c; + *pb = b; +} + static inline uint32_t __rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval) {