From b00d4cd3cc0e70e90f50a8fed294754a4c6e9475 Mon Sep 17 00:00:00 2001 From: Vsevolod Stakhov Date: Thu, 12 May 2016 12:45:17 +0100 Subject: [PATCH] [Feature] Use metrohash as well --- contrib/metrohash/metro.h | 141 +++++++++++++++++++++++++++++++++++ src/libcryptobox/cryptobox.c | 36 ++++++--- src/libcryptobox/cryptobox.h | 4 +- 3 files changed, 170 insertions(+), 11 deletions(-) create mode 100644 contrib/metrohash/metro.h diff --git a/contrib/metrohash/metro.h b/contrib/metrohash/metro.h new file mode 100644 index 000000000..36c44d65c --- /dev/null +++ b/contrib/metrohash/metro.h @@ -0,0 +1,141 @@ +/*- +The MIT License (MIT) + +Copyright (c) 2015 J. Andrew Rogers + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. + */ +#ifndef CONTRIB_METROHASH_METRO_H_ +#define CONTRIB_METROHASH_METRO_H_ + +#include +#include +#include +#include +#ifdef _MSC_VER +typedef unsigned __int32 uint32_t; +typedef unsigned __int64 uint64_t; +#else +#include +#endif + +/* rotate right idiom recognized by compiler*/ +inline static uint64_t rotate_right(uint64_t v, unsigned k) +{ + return (v >> k) | (v << (64 - k)); +} + +inline static uint64_t read_u64(const void * const ptr) +{ + return * (uint64_t *) ptr; +} + +inline static uint64_t read_u32(const void * const ptr) +{ + return * (uint32_t *) ptr; +} + +inline static uint64_t read_u16(const void * const ptr) +{ + return * (uint16_t *) ptr; +} + +inline static uint64_t read_u8 (const void * const ptr) +{ + return * (uint8_t *) ptr; +} + +static inline uint64_t metrohash64_1(const uint8_t * key, uint64_t len, uint64_t seed) +{ + static const uint64_t k0 = 0xC83A91E1; + static const uint64_t k1 = 0x8648DBDB; + static const uint64_t k2 = 0x7BDEC03B; + static const uint64_t k3 = 0x2F5870A5; + + const uint8_t * ptr = key; + const uint8_t * const end = ptr + len; + + uint64_t hash = ((((uint64_t) seed) + k2) * k0) + len; + + if (len >= 32) + { + uint64_t v[4]; + v[0] = hash; + v[1] = hash; + v[2] = hash; + v[3] = hash; + + do + { + v[0] += read_u64(ptr) * k0; ptr += 8; v[0] = rotate_right(v[0],29) + v[2]; + v[1] += read_u64(ptr) * k1; ptr += 8; v[1] = rotate_right(v[1],29) + v[3]; + v[2] += read_u64(ptr) * k2; ptr += 8; v[2] = rotate_right(v[2],29) + v[0]; + v[3] += read_u64(ptr) * k3; ptr += 8; v[3] = rotate_right(v[3],29) + v[1]; + } + while (ptr <= (end - 32)); + + v[2] ^= rotate_right(((v[0] + v[3]) * k0) + v[1], 33) * k1; + v[3] ^= rotate_right(((v[1] + v[2]) * k1) + v[0], 33) * k0; + v[0] ^= rotate_right(((v[0] + v[2]) * k0) + v[3], 33) * k1; + v[1] ^= rotate_right(((v[1] + v[3]) * k1) + v[2], 33) * k0; + hash += v[0] ^ v[1]; + } + + if ((end - ptr) >= 16) + { + uint64_t v0 = hash + (read_u64(ptr) * k0); ptr += 8; v0 = rotate_right(v0,33) * k1; + uint64_t v1 = hash + (read_u64(ptr) * k1); ptr += 8; v1 = rotate_right(v1,33) * k2; + v0 ^= rotate_right(v0 * k0, 35) + v1; + v1 ^= rotate_right(v1 * k3, 35) + v0; + hash += v1; + } + + if ((end - ptr) >= 8) + { + hash += read_u64(ptr) * k3; ptr += 8; + hash ^= rotate_right(hash, 33) * k1; + + } + + if ((end - ptr) >= 4) + { + hash += read_u32(ptr) * k3; ptr += 4; + hash ^= rotate_right(hash, 15) * k1; + } + + if ((end - ptr) >= 2) + { + hash += read_u16(ptr) * k3; ptr += 2; + hash ^= rotate_right(hash, 13) * k1; + } + + if ((end - ptr) >= 1) + { + hash += read_u8 (ptr) * k3; + hash ^= rotate_right(hash, 25) * k1; + } + + hash ^= rotate_right(hash, 33); + hash *= k0; + hash ^= rotate_right(hash, 33); + + return hash; +} + +#endif /* CONTRIB_METROHASH_METRO_H_ */ diff --git a/src/libcryptobox/cryptobox.c b/src/libcryptobox/cryptobox.c index c6eb3310a..71180da12 100644 --- a/src/libcryptobox/cryptobox.c +++ b/src/libcryptobox/cryptobox.c @@ -34,7 +34,7 @@ #include "xxhash.h" #define MUM_TARGET_INDEPENDENT_HASH 1 /* For 32/64 bit equal hashes */ #include "../../contrib/mumhash/mum.h" - +#include "../../contrib/metrohash/metro.h" #ifdef HAVE_CPUID_H #include #endif @@ -1455,25 +1455,39 @@ rspamd_cryptobox_fast_hash_final (rspamd_cryptobox_fast_hash_state_t *st) /** * One in all function */ -guint64 -rspamd_cryptobox_fast_hash (const void *data, +static inline guint64 +rspamd_cryptobox_fast_hash_machdep (const void *data, gsize len, guint64 seed) { if (len >= 8 && len % 8 == 0) { - return rspamd_cryptobox_fast_hash_specific (RSPAMD_CRYPTOBOX_MUMHASH, - data, len, seed); + return mum_hash (data, len, seed); } else { #if defined(__LP64__) || defined(_LP64) - return rspamd_cryptobox_fast_hash_specific (RSPAMD_CRYPTOBOX_XXHASH64, - data, len, seed); + return metrohash64_1 (data, len, seed); #endif } - return rspamd_cryptobox_fast_hash_specific (RSPAMD_CRYPTOBOX_XXHASH32, - data, len, seed); + return XXH32 (data, len, seed); } +static inline guint64 +rspamd_cryptobox_fast_hash_indep (const void *data, + gsize len, guint64 seed) +{ + if (len >= 8 && len % 8 == 0) { + return mum_hash (data, len, seed); + } + + return metrohash64_1 (data, len, seed); +} + +guint64 +rspamd_cryptobox_fast_hash (const void *data, + gsize len, guint64 seed) +{ + return rspamd_cryptobox_fast_hash_machdep (data, len, seed); +} guint64 rspamd_cryptobox_fast_hash_specific ( @@ -1488,8 +1502,10 @@ rspamd_cryptobox_fast_hash_specific ( return XXH64 (data, len, seed); case RSPAMD_CRYPTOBOX_MUMHASH: return mum_hash (data, len, seed); + case RSPAMD_CRYPTOBOX_HASHFAST_INDEPENDENT: + return rspamd_cryptobox_fast_hash_indep (data, len, seed); case RSPAMD_CRYPTOBOX_HASHFAST: default: - return rspamd_cryptobox_fast_hash (data, len, seed); + return rspamd_cryptobox_fast_hash_machdep (data, len, seed); } } diff --git a/src/libcryptobox/cryptobox.h b/src/libcryptobox/cryptobox.h index c44044f48..6facf0a0e 100644 --- a/src/libcryptobox/cryptobox.h +++ b/src/libcryptobox/cryptobox.h @@ -358,7 +358,9 @@ enum rspamd_cryptobox_fast_hash_type { RSPAMD_CRYPTOBOX_XXHASH64 = 0, RSPAMD_CRYPTOBOX_XXHASH32, RSPAMD_CRYPTOBOX_MUMHASH, - RSPAMD_CRYPTOBOX_HASHFAST + RSPAMD_CRYPTOBOX_METROHASH, + RSPAMD_CRYPTOBOX_HASHFAST, + RSPAMD_CRYPTOBOX_HASHFAST_INDEPENDENT }; /** * Platform independent version -- 2.39.5