1 /* 2 * xxHash - Fast Hash algorithm 3 * Copyright (C) 2012-2016, Yann Collet 4 * 5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions are 9 * met: 10 * 11 * + Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * + Redistributions in binary form must reproduce the above 14 * copyright notice, this list of conditions and the following disclaimer 15 * in the documentation and/or other materials provided with the 16 * distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 * 30 * You can contact the author at : 31 * - xxHash source repository : https://github.com/Cyan4973/xxHash 32 */ 33 34 #ifndef QEMU_XXHASH_H 35 #define QEMU_XXHASH_H 36 37 #include "qemu/bitops.h" 38 39 #define PRIME32_1 2654435761U 40 #define PRIME32_2 2246822519U 41 #define PRIME32_3 3266489917U 42 #define PRIME32_4 668265263U 43 #define PRIME32_5 374761393U 44 45 #define QEMU_XXHASH_SEED 1 46 47 /* 48 * xxhash32, customized for input variables that are not guaranteed to be 49 * contiguous in memory. 50 */ 51 static inline uint32_t 52 qemu_xxhash7(uint64_t ab, uint64_t cd, uint32_t e, uint32_t f, uint32_t g) 53 { 54 uint32_t v1 = QEMU_XXHASH_SEED + PRIME32_1 + PRIME32_2; 55 uint32_t v2 = QEMU_XXHASH_SEED + PRIME32_2; 56 uint32_t v3 = QEMU_XXHASH_SEED + 0; 57 uint32_t v4 = QEMU_XXHASH_SEED - PRIME32_1; 58 uint32_t a = ab; 59 uint32_t b = ab >> 32; 60 uint32_t c = cd; 61 uint32_t d = cd >> 32; 62 uint32_t h32; 63 64 v1 += a * PRIME32_2; 65 v1 = rol32(v1, 13); 66 v1 *= PRIME32_1; 67 68 v2 += b * PRIME32_2; 69 v2 = rol32(v2, 13); 70 v2 *= PRIME32_1; 71 72 v3 += c * PRIME32_2; 73 v3 = rol32(v3, 13); 74 v3 *= PRIME32_1; 75 76 v4 += d * PRIME32_2; 77 v4 = rol32(v4, 13); 78 v4 *= PRIME32_1; 79 80 h32 = rol32(v1, 1) + rol32(v2, 7) + rol32(v3, 12) + rol32(v4, 18); 81 h32 += 28; 82 83 h32 += e * PRIME32_3; 84 h32 = rol32(h32, 17) * PRIME32_4; 85 86 h32 += f * PRIME32_3; 87 h32 = rol32(h32, 17) * PRIME32_4; 88 89 h32 += g * PRIME32_3; 90 h32 = rol32(h32, 17) * PRIME32_4; 91 92 h32 ^= h32 >> 15; 93 h32 *= PRIME32_2; 94 h32 ^= h32 >> 13; 95 h32 *= PRIME32_3; 96 h32 ^= h32 >> 16; 97 98 return h32; 99 } 100 101 static inline uint32_t qemu_xxhash2(uint64_t ab) 102 { 103 return qemu_xxhash7(ab, 0, 0, 0, 0); 104 } 105 106 static inline uint32_t qemu_xxhash4(uint64_t ab, uint64_t cd) 107 { 108 return qemu_xxhash7(ab, cd, 0, 0, 0); 109 } 110 111 static inline uint32_t qemu_xxhash5(uint64_t ab, uint64_t cd, uint32_t e) 112 { 113 return qemu_xxhash7(ab, cd, e, 0, 0); 114 } 115 116 static inline uint32_t qemu_xxhash6(uint64_t ab, uint64_t cd, uint32_t e, 117 uint32_t f) 118 { 119 return qemu_xxhash7(ab, cd, e, f, 0); 120 } 121 122 #endif /* QEMU_XXHASH_H */ 123