From mboxrd@z Thu Jan 1 00:00:00 1970 From: Pablo de Lara Subject: [PATCH v2 4/6] hash: add two new functions to jhash library Date: Fri, 24 Apr 2015 12:23:05 +0100 Message-ID: <1429874587-17939-5-git-send-email-pablo.de.lara.guarch@intel.com> References: <1429190819-27402-1-git-send-email-pablo.de.lara.guarch@intel.com> <1429874587-17939-1-git-send-email-pablo.de.lara.guarch@intel.com> To: dev-VfR2kkLFssw@public.gmane.org Return-path: In-Reply-To: <1429874587-17939-1-git-send-email-pablo.de.lara.guarch-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org> List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces-VfR2kkLFssw@public.gmane.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 | 194 +++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 194 insertions(+), 0 deletions(-) diff --git a/lib/librte_hash/rte_jhash.h b/lib/librte_hash/rte_jhash.h index 4ec1c39..1e69e40 100644 --- a/lib/librte_hash/rte_jhash.h +++ b/lib/librte_hash/rte_jhash.h @@ -292,6 +292,200 @@ 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; +} /** * A special ultra-optimized versions that knows it is hashing exactly -- 1.7.4.1