1/* 2 * xxHash - Extremely 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 * This program is free software; you can redistribute it and/or modify it under 31 * the terms of the GNU General Public License version 2 as published by the 32 * Free Software Foundation. This program is dual-licensed; you may select 33 * either version 2 of the GNU General Public License ("GPL") or BSD license 34 * ("BSD"). 35 * 36 * You can contact the author at: 37 * - xxHash homepage: http://cyan4973.github.io/xxHash/ 38 * - xxHash source repository: https://github.com/Cyan4973/xxHash 39 */ 40 41/* 42 * Notice extracted from xxHash homepage: 43 * 44 * xxHash is an extremely fast Hash algorithm, running at RAM speed limits. 45 * It also successfully passes all tests from the SMHasher suite. 46 * 47 * Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 48 * Duo @3GHz) 49 * 50 * Name Speed Q.Score Author 51 * xxHash 5.4 GB/s 10 52 * CrapWow 3.2 GB/s 2 Andrew 53 * MumurHash 3a 2.7 GB/s 10 Austin Appleby 54 * SpookyHash 2.0 GB/s 10 Bob Jenkins 55 * SBox 1.4 GB/s 9 Bret Mulvey 56 * Lookup3 1.2 GB/s 9 Bob Jenkins 57 * SuperFastHash 1.2 GB/s 1 Paul Hsieh 58 * CityHash64 1.05 GB/s 10 Pike & Alakuijala 59 * FNV 0.55 GB/s 5 Fowler, Noll, Vo 60 * CRC32 0.43 GB/s 9 61 * MD5-32 0.33 GB/s 10 Ronald L. Rivest 62 * SHA1-32 0.28 GB/s 10 63 * 64 * Q.Score is a measure of quality of the hash function. 65 * It depends on successfully passing SMHasher test set. 66 * 10 is a perfect score. 67 * 68 * A 64-bits version, named xxh64 offers much better speed, 69 * but for 64-bits applications only. 70 * Name Speed on 64 bits Speed on 32 bits 71 * xxh64 13.8 GB/s 1.9 GB/s 72 * xxh32 6.8 GB/s 6.0 GB/s 73 */ 74 75#ifndef XXHASH_H 76#define XXHASH_H 77 78#include <linux/types.h> 79 80/*-**************************** 81 * Simple Hash Functions 82 *****************************/ 83 84/** 85 * xxh32() - calculate the 32-bit hash of the input with a given seed. 86 * 87 * @input: The data to hash. 88 * @length: The length of the data to hash. 89 * @seed: The seed can be used to alter the result predictably. 90 * 91 * Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s 92 * 93 * Return: The 32-bit hash of the data. 94 */ 95uint32_t xxh32(const void *input, size_t length, uint32_t seed); 96 97/** 98 * xxh64() - calculate the 64-bit hash of the input with a given seed. 99 * 100 * @input: The data to hash. 101 * @length: The length of the data to hash. 102 * @seed: The seed can be used to alter the result predictably. 103 * 104 * This function runs 2x faster on 64-bit systems, but slower on 32-bit systems. 105 * 106 * Return: The 64-bit hash of the data. 107 */ 108uint64_t xxh64(const void *input, size_t length, uint64_t seed); 109 110/*-**************************** 111 * Streaming Hash Functions 112 *****************************/ 113 114/* 115 * These definitions are only meant to allow allocation of XXH state 116 * statically, on stack, or in a struct for example. 117 * Do not use members directly. 118 */ 119 120/** 121 * struct xxh32_state - private xxh32 state, do not use members directly 122 */ 123struct xxh32_state { 124 uint32_t total_len_32; 125 uint32_t large_len; 126 uint32_t v1; 127 uint32_t v2; 128 uint32_t v3; 129 uint32_t v4; 130 uint32_t mem32[4]; 131 uint32_t memsize; 132}; 133 134/** 135 * struct xxh32_state - private xxh64 state, do not use members directly 136 */ 137struct xxh64_state { 138 uint64_t total_len; 139 uint64_t v1; 140 uint64_t v2; 141 uint64_t v3; 142 uint64_t v4; 143 uint64_t mem64[4]; 144 uint32_t memsize; 145}; 146 147/** 148 * xxh32_reset() - reset the xxh32 state to start a new hashing operation 149 * 150 * @state: The xxh32 state to reset. 151 * @seed: Initialize the hash state with this seed. 152 * 153 * Call this function on any xxh32_state to prepare for a new hashing operation. 154 */ 155void xxh32_reset(struct xxh32_state *state, uint32_t seed); 156 157/** 158 * xxh32_update() - hash the data given and update the xxh32 state 159 * 160 * @state: The xxh32 state to update. 161 * @input: The data to hash. 162 * @length: The length of the data to hash. 163 * 164 * After calling xxh32_reset() call xxh32_update() as many times as necessary. 165 * 166 * Return: Zero on success, otherwise an error code. 167 */ 168int xxh32_update(struct xxh32_state *state, const void *input, size_t length); 169 170/** 171 * xxh32_digest() - produce the current xxh32 hash 172 * 173 * @state: Produce the current xxh32 hash of this state. 174 * 175 * A hash value can be produced at any time. It is still possible to continue 176 * inserting input into the hash state after a call to xxh32_digest(), and 177 * generate new hashes later on, by calling xxh32_digest() again. 178 * 179 * Return: The xxh32 hash stored in the state. 180 */ 181uint32_t xxh32_digest(const struct xxh32_state *state); 182 183/** 184 * xxh64_reset() - reset the xxh64 state to start a new hashing operation 185 * 186 * @state: The xxh64 state to reset. 187 * @seed: Initialize the hash state with this seed. 188 */ 189void xxh64_reset(struct xxh64_state *state, uint64_t seed); 190 191/** 192 * xxh64_update() - hash the data given and update the xxh64 state 193 * @state: The xxh64 state to update. 194 * @input: The data to hash. 195 * @length: The length of the data to hash. 196 * 197 * After calling xxh64_reset() call xxh64_update() as many times as necessary. 198 * 199 * Return: Zero on success, otherwise an error code. 200 */ 201int xxh64_update(struct xxh64_state *state, const void *input, size_t length); 202 203/** 204 * xxh64_digest() - produce the current xxh64 hash 205 * 206 * @state: Produce the current xxh64 hash of this state. 207 * 208 * A hash value can be produced at any time. It is still possible to continue 209 * inserting input into the hash state after a call to xxh64_digest(), and 210 * generate new hashes later on, by calling xxh64_digest() again. 211 * 212 * Return: The xxh64 hash stored in the state. 213 */ 214uint64_t xxh64_digest(const struct xxh64_state *state); 215 216/*-************************** 217 * Utils 218 ***************************/ 219 220/** 221 * xxh32_copy_state() - copy the source state into the destination state 222 * 223 * @src: The source xxh32 state. 224 * @dst: The destination xxh32 state. 225 */ 226void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src); 227 228/** 229 * xxh64_copy_state() - copy the source state into the destination state 230 * 231 * @src: The source xxh64 state. 232 * @dst: The destination xxh64 state. 233 */ 234void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src); 235 236#endif /* XXHASH_H */ 237