[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v5 08/18] exec: add tb_hash_func5, derived from
From: |
Sergey Fedorov |
Subject: |
Re: [Qemu-devel] [PATCH v5 08/18] exec: add tb_hash_func5, derived from xxhash |
Date: |
Tue, 17 May 2016 20:22:52 +0300 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.7.2 |
On 14/05/16 06:34, Emilio G. Cota wrote:
> This will be used by upcoming changes for hashing the tb hash.
>
> Add this into a separate file to include the copyright notice from
> xxhash.
>
> Reviewed-by: Richard Henderson <address@hidden>
> Signed-off-by: Emilio G. Cota <address@hidden>
> ---
> include/exec/tb-hash-xx.h | 94
> +++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 94 insertions(+)
> create mode 100644 include/exec/tb-hash-xx.h
>
> diff --git a/include/exec/tb-hash-xx.h b/include/exec/tb-hash-xx.h
> new file mode 100644
> index 0000000..67f4e6f
> --- /dev/null
> +++ b/include/exec/tb-hash-xx.h
> @@ -0,0 +1,94 @@
> +/*
> + * 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
> +#define EXEC_TB_HASH_XX
> +
> +#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 TB_HASH_XX_SEED 1
> +
> +/*
> + * xxhash32, customized for input variables that are not guaranteed to be
> + * contiguous in memory.
> + */
> +static inline
> +uint32_t tb_hash_func5(uint64_t a0, uint64_t b0, uint32_t e)
> +{
> + 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 >> 31 >> 1;
I'm wondering if there's something special forcing us to make ">> 31
>>1" instead of just ">> 32" on uint64_t?
Kind regards,
Sergey
> + uint32_t b = a0;
> + uint32_t c = b0 >> 31 >> 1;
> + uint32_t d = b0;
> + 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 += 20;
> +
> + h32 += e * 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;
> +}
> +
> +#endif /* EXEC_TB_HASH_XX */
- [Qemu-devel] [PATCH v5 18/18] translate-all: add tb hash bucket info to 'info jit' dump, (continued)
- [Qemu-devel] [PATCH v5 18/18] translate-all: add tb hash bucket info to 'info jit' dump, Emilio G. Cota, 2016/05/13
- [Qemu-devel] [PATCH v5 04/18] include/processor.h: define cpu_relax(), Emilio G. Cota, 2016/05/13
- [Qemu-devel] [PATCH v5 06/18] atomics: add atomic_read_acquire and atomic_set_release, Emilio G. Cota, 2016/05/13
- [Qemu-devel] [PATCH v5 13/18] qht: support parallel writes, Emilio G. Cota, 2016/05/13
- [Qemu-devel] [PATCH v5 10/18] qdist: add module to represent frequency distributions of data, Emilio G. Cota, 2016/05/13
- [Qemu-devel] [PATCH v5 08/18] exec: add tb_hash_func5, derived from xxhash, Emilio G. Cota, 2016/05/13
- Re: [Qemu-devel] [PATCH v5 08/18] exec: add tb_hash_func5, derived from xxhash,
Sergey Fedorov <=
- [Qemu-devel] [PATCH v5 16/18] qht: add test-qht-par to invoke qht-bench from 'check' target, Emilio G. Cota, 2016/05/13
- [Qemu-devel] [PATCH v5 17/18] tb hash: track translated blocks with qht, Emilio G. Cota, 2016/05/13
- [Qemu-devel] [PATCH v5 15/18] qht: add qht-bench, a performance benchmark, Emilio G. Cota, 2016/05/13
- [Qemu-devel] [PATCH v5 14/18] qht: add test program, Emilio G. Cota, 2016/05/13
- [Qemu-devel] [PATCH v5 09/18] tb hash: hash phys_pc, pc, and flags with xxhash, Emilio G. Cota, 2016/05/13
- [Qemu-devel] [PATCH v5 11/18] qdist: add test program, Emilio G. Cota, 2016/05/13
- [Qemu-devel] [PATCH v5 12/18] qht: QEMU's fast, resizable and scalable Hash Table, Emilio G. Cota, 2016/05/13