From c971d8fa73ff92996d751fa87d90f220cf3c8194 Mon Sep 17 00:00:00 2001 From: Emilio G. Cota Date: Sat, 20 Oct 2018 18:46:28 -0400 Subject: exec: introduce qemu_xxhash{2,4,5,6,7} Before moving them all to include/qemu/xxhash.h. Reviewed-by: Alex Bennée Signed-off-by: Emilio G. Cota Signed-off-by: Richard Henderson --- include/exec/tb-hash-xx.h | 41 +++++++++++++++++++++++++++++++---------- include/exec/tb-hash.h | 2 +- 2 files changed, 32 insertions(+), 11 deletions(-) (limited to 'include/exec') diff --git a/include/exec/tb-hash-xx.h b/include/exec/tb-hash-xx.h index 747a9a612c..98ce4b628a 100644 --- a/include/exec/tb-hash-xx.h +++ b/include/exec/tb-hash-xx.h @@ -42,23 +42,23 @@ #define PRIME32_4 668265263U #define PRIME32_5 374761393U -#define TB_HASH_XX_SEED 1 +#define QEMU_XXHASH_SEED 1 /* * xxhash32, customized for input variables that are not guaranteed to be * contiguous in memory. */ static inline uint32_t -tb_hash_func7(uint64_t a0, uint64_t b0, uint32_t e, uint32_t f, uint32_t g) +qemu_xxhash7(uint64_t ab, uint64_t cd, uint32_t e, uint32_t f, uint32_t g) { - uint32_t v1 = TB_HASH_XX_SEED + PRIME32_1 + PRIME32_2; - uint32_t v2 = TB_HASH_XX_SEED + PRIME32_2; - uint32_t v3 = TB_HASH_XX_SEED + 0; - uint32_t v4 = TB_HASH_XX_SEED - PRIME32_1; - uint32_t a = a0 >> 32; - uint32_t b = a0; - uint32_t c = b0 >> 32; - uint32_t d = b0; + uint32_t v1 = QEMU_XXHASH_SEED + PRIME32_1 + PRIME32_2; + uint32_t v2 = QEMU_XXHASH_SEED + PRIME32_2; + uint32_t v3 = QEMU_XXHASH_SEED + 0; + uint32_t v4 = QEMU_XXHASH_SEED - PRIME32_1; + uint32_t a = ab >> 32; + uint32_t b = ab; + uint32_t c = cd >> 32; + uint32_t d = cd; uint32_t h32; v1 += a * PRIME32_2; @@ -98,4 +98,25 @@ tb_hash_func7(uint64_t a0, uint64_t b0, uint32_t e, uint32_t f, uint32_t g) return h32; } +static inline uint32_t qemu_xxhash2(uint64_t ab) +{ + return qemu_xxhash7(ab, 0, 0, 0, 0); +} + +static inline uint32_t qemu_xxhash4(uint64_t ab, uint64_t cd) +{ + return qemu_xxhash7(ab, cd, 0, 0, 0); +} + +static inline uint32_t qemu_xxhash5(uint64_t ab, uint64_t cd, uint32_t e) +{ + return qemu_xxhash7(ab, cd, e, 0, 0); +} + +static inline uint32_t qemu_xxhash6(uint64_t ab, uint64_t cd, uint32_t e, + uint32_t f) +{ + return qemu_xxhash7(ab, cd, e, f, 0); +} + #endif /* EXEC_TB_HASH_XX_H */ diff --git a/include/exec/tb-hash.h b/include/exec/tb-hash.h index 0526c4f678..731ba4c272 100644 --- a/include/exec/tb-hash.h +++ b/include/exec/tb-hash.h @@ -61,7 +61,7 @@ static inline uint32_t tb_hash_func(tb_page_addr_t phys_pc, target_ulong pc, uint32_t flags, uint32_t cf_mask, uint32_t trace_vcpu_dstate) { - return tb_hash_func7(phys_pc, pc, flags, cf_mask, trace_vcpu_dstate); + return qemu_xxhash7(phys_pc, pc, flags, cf_mask, trace_vcpu_dstate); } #endif -- cgit v1.2.3-55-g7522 From fe656e3185fa10973d43492c867643e80fa433cd Mon Sep 17 00:00:00 2001 From: Emilio G. Cota Date: Sat, 20 Oct 2018 18:49:53 -0400 Subject: include: move exec/tb-hash-xx.h to qemu/xxhash.h Reviewed-by: Alex Bennée Signed-off-by: Emilio G. Cota Signed-off-by: Richard Henderson --- include/exec/tb-hash-xx.h | 122 ---------------------------------------------- include/exec/tb-hash.h | 2 +- include/qemu/xxhash.h | 122 ++++++++++++++++++++++++++++++++++++++++++++++ tests/qht-bench.c | 2 +- util/qsp.c | 2 +- 5 files changed, 125 insertions(+), 125 deletions(-) delete mode 100644 include/exec/tb-hash-xx.h create mode 100644 include/qemu/xxhash.h (limited to 'include/exec') diff --git a/include/exec/tb-hash-xx.h b/include/exec/tb-hash-xx.h deleted file mode 100644 index 98ce4b628a..0000000000 --- a/include/exec/tb-hash-xx.h +++ /dev/null @@ -1,122 +0,0 @@ -/* - * xxHash - Fast Hash algorithm - * Copyright (C) 2012-2016, Yann Collet - * - * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: - * - * + Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * + Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following disclaimer - * in the documentation and/or other materials provided with the - * distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * You can contact the author at : - * - xxHash source repository : https://github.com/Cyan4973/xxHash - */ - -#ifndef EXEC_TB_HASH_XX_H -#define EXEC_TB_HASH_XX_H - -#include "qemu/bitops.h" - -#define PRIME32_1 2654435761U -#define PRIME32_2 2246822519U -#define PRIME32_3 3266489917U -#define PRIME32_4 668265263U -#define PRIME32_5 374761393U - -#define QEMU_XXHASH_SEED 1 - -/* - * xxhash32, customized for input variables that are not guaranteed to be - * contiguous in memory. - */ -static inline uint32_t -qemu_xxhash7(uint64_t ab, uint64_t cd, uint32_t e, uint32_t f, uint32_t g) -{ - uint32_t v1 = QEMU_XXHASH_SEED + PRIME32_1 + PRIME32_2; - uint32_t v2 = QEMU_XXHASH_SEED + PRIME32_2; - uint32_t v3 = QEMU_XXHASH_SEED + 0; - uint32_t v4 = QEMU_XXHASH_SEED - PRIME32_1; - uint32_t a = ab >> 32; - uint32_t b = ab; - uint32_t c = cd >> 32; - uint32_t d = cd; - uint32_t h32; - - v1 += a * PRIME32_2; - v1 = rol32(v1, 13); - v1 *= PRIME32_1; - - v2 += b * PRIME32_2; - v2 = rol32(v2, 13); - v2 *= PRIME32_1; - - v3 += c * PRIME32_2; - v3 = rol32(v3, 13); - v3 *= PRIME32_1; - - v4 += d * PRIME32_2; - v4 = rol32(v4, 13); - v4 *= PRIME32_1; - - h32 = rol32(v1, 1) + rol32(v2, 7) + rol32(v3, 12) + rol32(v4, 18); - h32 += 28; - - h32 += e * PRIME32_3; - h32 = rol32(h32, 17) * PRIME32_4; - - h32 += f * PRIME32_3; - h32 = rol32(h32, 17) * PRIME32_4; - - h32 += g * PRIME32_3; - h32 = rol32(h32, 17) * PRIME32_4; - - h32 ^= h32 >> 15; - h32 *= PRIME32_2; - h32 ^= h32 >> 13; - h32 *= PRIME32_3; - h32 ^= h32 >> 16; - - return h32; -} - -static inline uint32_t qemu_xxhash2(uint64_t ab) -{ - return qemu_xxhash7(ab, 0, 0, 0, 0); -} - -static inline uint32_t qemu_xxhash4(uint64_t ab, uint64_t cd) -{ - return qemu_xxhash7(ab, cd, 0, 0, 0); -} - -static inline uint32_t qemu_xxhash5(uint64_t ab, uint64_t cd, uint32_t e) -{ - return qemu_xxhash7(ab, cd, e, 0, 0); -} - -static inline uint32_t qemu_xxhash6(uint64_t ab, uint64_t cd, uint32_t e, - uint32_t f) -{ - return qemu_xxhash7(ab, cd, e, f, 0); -} - -#endif /* EXEC_TB_HASH_XX_H */ diff --git a/include/exec/tb-hash.h b/include/exec/tb-hash.h index 731ba4c272..4f3a37d927 100644 --- a/include/exec/tb-hash.h +++ b/include/exec/tb-hash.h @@ -20,7 +20,7 @@ #ifndef EXEC_TB_HASH_H #define EXEC_TB_HASH_H -#include "exec/tb-hash-xx.h" +#include "qemu/xxhash.h" #ifdef CONFIG_SOFTMMU diff --git a/include/qemu/xxhash.h b/include/qemu/xxhash.h new file mode 100644 index 0000000000..fe35dde328 --- /dev/null +++ b/include/qemu/xxhash.h @@ -0,0 +1,122 @@ +/* + * xxHash - Fast Hash algorithm + * Copyright (C) 2012-2016, Yann Collet + * + * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * + Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * You can contact the author at : + * - xxHash source repository : https://github.com/Cyan4973/xxHash + */ + +#ifndef QEMU_XXHASH_H +#define QEMU_XXHASH_H + +#include "qemu/bitops.h" + +#define PRIME32_1 2654435761U +#define PRIME32_2 2246822519U +#define PRIME32_3 3266489917U +#define PRIME32_4 668265263U +#define PRIME32_5 374761393U + +#define QEMU_XXHASH_SEED 1 + +/* + * xxhash32, customized for input variables that are not guaranteed to be + * contiguous in memory. + */ +static inline uint32_t +qemu_xxhash7(uint64_t ab, uint64_t cd, uint32_t e, uint32_t f, uint32_t g) +{ + uint32_t v1 = QEMU_XXHASH_SEED + PRIME32_1 + PRIME32_2; + uint32_t v2 = QEMU_XXHASH_SEED + PRIME32_2; + uint32_t v3 = QEMU_XXHASH_SEED + 0; + uint32_t v4 = QEMU_XXHASH_SEED - PRIME32_1; + uint32_t a = ab >> 32; + uint32_t b = ab; + uint32_t c = cd >> 32; + uint32_t d = cd; + uint32_t h32; + + v1 += a * PRIME32_2; + v1 = rol32(v1, 13); + v1 *= PRIME32_1; + + v2 += b * PRIME32_2; + v2 = rol32(v2, 13); + v2 *= PRIME32_1; + + v3 += c * PRIME32_2; + v3 = rol32(v3, 13); + v3 *= PRIME32_1; + + v4 += d * PRIME32_2; + v4 = rol32(v4, 13); + v4 *= PRIME32_1; + + h32 = rol32(v1, 1) + rol32(v2, 7) + rol32(v3, 12) + rol32(v4, 18); + h32 += 28; + + h32 += e * PRIME32_3; + h32 = rol32(h32, 17) * PRIME32_4; + + h32 += f * PRIME32_3; + h32 = rol32(h32, 17) * PRIME32_4; + + h32 += g * PRIME32_3; + h32 = rol32(h32, 17) * PRIME32_4; + + h32 ^= h32 >> 15; + h32 *= PRIME32_2; + h32 ^= h32 >> 13; + h32 *= PRIME32_3; + h32 ^= h32 >> 16; + + return h32; +} + +static inline uint32_t qemu_xxhash2(uint64_t ab) +{ + return qemu_xxhash7(ab, 0, 0, 0, 0); +} + +static inline uint32_t qemu_xxhash4(uint64_t ab, uint64_t cd) +{ + return qemu_xxhash7(ab, cd, 0, 0, 0); +} + +static inline uint32_t qemu_xxhash5(uint64_t ab, uint64_t cd, uint32_t e) +{ + return qemu_xxhash7(ab, cd, e, 0, 0); +} + +static inline uint32_t qemu_xxhash6(uint64_t ab, uint64_t cd, uint32_t e, + uint32_t f) +{ + return qemu_xxhash7(ab, cd, e, f, 0); +} + +#endif /* QEMU_XXHASH_H */ diff --git a/tests/qht-bench.c b/tests/qht-bench.c index 0278f4da04..ab4e708180 100644 --- a/tests/qht-bench.c +++ b/tests/qht-bench.c @@ -9,7 +9,7 @@ #include "qemu/atomic.h" #include "qemu/qht.h" #include "qemu/rcu.h" -#include "exec/tb-hash-xx.h" +#include "qemu/xxhash.h" struct thread_stats { size_t rd; diff --git a/util/qsp.c b/util/qsp.c index dc29c41fde..410f1ba004 100644 --- a/util/qsp.c +++ b/util/qsp.c @@ -61,7 +61,7 @@ #include "qemu/timer.h" #include "qemu/qht.h" #include "qemu/rcu.h" -#include "exec/tb-hash-xx.h" +#include "qemu/xxhash.h" enum QSPType { QSP_MUTEX, -- cgit v1.2.3-55-g7522