1868e25b9SDmitri Tikhonov/* 2868e25b9SDmitri Tikhonov xxHash - Extremely Fast Hash algorithm 3868e25b9SDmitri Tikhonov Header File 4868e25b9SDmitri Tikhonov Copyright (C) 2012-2014, Yann Collet. 5868e25b9SDmitri Tikhonov BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 6868e25b9SDmitri Tikhonov 7868e25b9SDmitri Tikhonov Redistribution and use in source and binary forms, with or without 8868e25b9SDmitri Tikhonov modification, are permitted provided that the following conditions are 9868e25b9SDmitri Tikhonov met: 10868e25b9SDmitri Tikhonov 11868e25b9SDmitri Tikhonov * Redistributions of source code must retain the above copyright 12868e25b9SDmitri Tikhonov notice, this list of conditions and the following disclaimer. 13868e25b9SDmitri Tikhonov * Redistributions in binary form must reproduce the above 14868e25b9SDmitri Tikhonov copyright notice, this list of conditions and the following disclaimer 15868e25b9SDmitri Tikhonov in the documentation and/or other materials provided with the 16868e25b9SDmitri Tikhonov distribution. 17868e25b9SDmitri Tikhonov 18868e25b9SDmitri Tikhonov THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19868e25b9SDmitri Tikhonov "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20868e25b9SDmitri Tikhonov LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21868e25b9SDmitri Tikhonov A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22868e25b9SDmitri Tikhonov OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23868e25b9SDmitri Tikhonov SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24868e25b9SDmitri Tikhonov LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25868e25b9SDmitri Tikhonov DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26868e25b9SDmitri Tikhonov THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27868e25b9SDmitri Tikhonov (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28868e25b9SDmitri Tikhonov OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29868e25b9SDmitri Tikhonov 30868e25b9SDmitri Tikhonov You can contact the author at : 31868e25b9SDmitri Tikhonov - xxHash source repository : http://code.google.com/p/xxhash/ 32868e25b9SDmitri Tikhonov*/ 33868e25b9SDmitri Tikhonov 34868e25b9SDmitri Tikhonov/* Notice extracted from xxHash homepage : 35868e25b9SDmitri Tikhonov 36868e25b9SDmitri TikhonovxxHash is an extremely fast Hash algorithm, running at RAM speed limits. 37868e25b9SDmitri TikhonovIt also successfully passes all tests from the SMHasher suite. 38868e25b9SDmitri Tikhonov 39868e25b9SDmitri TikhonovComparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 Duo @3GHz) 40868e25b9SDmitri Tikhonov 41868e25b9SDmitri TikhonovName Speed Q.Score Author 42868e25b9SDmitri TikhonovxxHash 5.4 GB/s 10 43868e25b9SDmitri TikhonovCrapWow 3.2 GB/s 2 Andrew 44868e25b9SDmitri TikhonovMumurHash 3a 2.7 GB/s 10 Austin Appleby 45868e25b9SDmitri TikhonovSpookyHash 2.0 GB/s 10 Bob Jenkins 46868e25b9SDmitri TikhonovSBox 1.4 GB/s 9 Bret Mulvey 47868e25b9SDmitri TikhonovLookup3 1.2 GB/s 9 Bob Jenkins 48868e25b9SDmitri TikhonovSuperFastHash 1.2 GB/s 1 Paul Hsieh 49868e25b9SDmitri TikhonovCityHash64 1.05 GB/s 10 Pike & Alakuijala 50868e25b9SDmitri TikhonovFNV 0.55 GB/s 5 Fowler, Noll, Vo 51868e25b9SDmitri TikhonovCRC32 0.43 GB/s 9 52868e25b9SDmitri TikhonovMD5-32 0.33 GB/s 10 Ronald L. Rivest 53868e25b9SDmitri TikhonovSHA1-32 0.28 GB/s 10 54868e25b9SDmitri Tikhonov 55868e25b9SDmitri TikhonovQ.Score is a measure of quality of the hash function. 56868e25b9SDmitri TikhonovIt depends on successfully passing SMHasher test set. 57868e25b9SDmitri Tikhonov10 is a perfect score. 58868e25b9SDmitri Tikhonov*/ 59868e25b9SDmitri Tikhonov 60868e25b9SDmitri Tikhonov#pragma once 61868e25b9SDmitri Tikhonov 62868e25b9SDmitri Tikhonov#if defined (__cplusplus) 63868e25b9SDmitri Tikhonovextern "C" { 64868e25b9SDmitri Tikhonov#endif 65868e25b9SDmitri Tikhonov 66868e25b9SDmitri Tikhonov 67868e25b9SDmitri Tikhonov/***************************** 68868e25b9SDmitri Tikhonov Includes 69868e25b9SDmitri Tikhonov*****************************/ 70868e25b9SDmitri Tikhonov#include <stddef.h> /* size_t */ 71868e25b9SDmitri Tikhonov 72868e25b9SDmitri Tikhonov 73868e25b9SDmitri Tikhonov/***************************** 74868e25b9SDmitri Tikhonov Type 75868e25b9SDmitri Tikhonov*****************************/ 76868e25b9SDmitri Tikhonovtypedef enum { XXH_OK = 0, XXH_ERROR } XXH_errorcode; 77868e25b9SDmitri Tikhonov 78868e25b9SDmitri Tikhonov 79868e25b9SDmitri Tikhonov 80868e25b9SDmitri Tikhonov/***************************** 81868e25b9SDmitri Tikhonov Simple Hash Functions 82868e25b9SDmitri Tikhonov*****************************/ 83868e25b9SDmitri Tikhonov 84868e25b9SDmitri Tikhonovunsigned int XXH32(const void *input, size_t length, unsigned seed); 85868e25b9SDmitri Tikhonovunsigned long long XXH64(const void *input, size_t length, 86868e25b9SDmitri Tikhonov unsigned long long seed); 87868e25b9SDmitri Tikhonov 88868e25b9SDmitri Tikhonov/* 89868e25b9SDmitri TikhonovXXH32() : 90868e25b9SDmitri Tikhonov Calculate the 32-bits hash of sequence "length" bytes stored at memory address "input". 91868e25b9SDmitri Tikhonov The memory between input & input+length must be valid (allocated and read-accessible). 92868e25b9SDmitri Tikhonov "seed" can be used to alter the result predictably. 93868e25b9SDmitri Tikhonov This function successfully passes all SMHasher tests. 94868e25b9SDmitri Tikhonov Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s 95868e25b9SDmitri TikhonovXXH64() : 96868e25b9SDmitri Tikhonov Calculate the 64-bits hash of sequence of length "len" stored at memory address "input". 97868e25b9SDmitri Tikhonov*/ 98868e25b9SDmitri Tikhonov 99868e25b9SDmitri Tikhonov 100868e25b9SDmitri Tikhonov 101868e25b9SDmitri Tikhonov/***************************** 102868e25b9SDmitri Tikhonov Advanced Hash Functions 103868e25b9SDmitri Tikhonov*****************************/ 104868e25b9SDmitri Tikhonovtypedef struct { long long ll[ 6]; } XXH32_state_t; 105868e25b9SDmitri Tikhonovtypedef struct { long long ll[11]; } XXH64_state_t; 106868e25b9SDmitri Tikhonov 107868e25b9SDmitri Tikhonov/* 108868e25b9SDmitri TikhonovThese structures allow static allocation of XXH states. 109868e25b9SDmitri TikhonovStates must then be initialized using XXHnn_reset() before first use. 110868e25b9SDmitri Tikhonov 111868e25b9SDmitri TikhonovIf you prefer dynamic allocation, please refer to functions below. 112868e25b9SDmitri Tikhonov*/ 113868e25b9SDmitri Tikhonov 114868e25b9SDmitri TikhonovXXH32_state_t *XXH32_createState(void); 115868e25b9SDmitri TikhonovXXH_errorcode XXH32_freeState(XXH32_state_t *statePtr); 116868e25b9SDmitri Tikhonov 117868e25b9SDmitri TikhonovXXH64_state_t *XXH64_createState(void); 118868e25b9SDmitri TikhonovXXH_errorcode XXH64_freeState(XXH64_state_t *statePtr); 119868e25b9SDmitri Tikhonov 120868e25b9SDmitri Tikhonov/* 121868e25b9SDmitri TikhonovThese functions create and release memory for XXH state. 122868e25b9SDmitri TikhonovStates must then be initialized using XXHnn_reset() before first use. 123868e25b9SDmitri Tikhonov*/ 124868e25b9SDmitri Tikhonov 125868e25b9SDmitri Tikhonov 126868e25b9SDmitri TikhonovXXH_errorcode XXH32_reset(XXH32_state_t *statePtr, unsigned seed); 127868e25b9SDmitri TikhonovXXH_errorcode XXH32_update(XXH32_state_t *statePtr, const void *input, 128868e25b9SDmitri Tikhonov size_t length); 129868e25b9SDmitri Tikhonovunsigned int XXH32_digest(const XXH32_state_t *statePtr); 130868e25b9SDmitri Tikhonov 131868e25b9SDmitri TikhonovXXH_errorcode XXH64_reset(XXH64_state_t *statePtr, 132868e25b9SDmitri Tikhonov unsigned long long seed); 133868e25b9SDmitri TikhonovXXH_errorcode XXH64_update(XXH64_state_t *statePtr, const void *input, 134868e25b9SDmitri Tikhonov size_t length); 135868e25b9SDmitri Tikhonovunsigned long long XXH64_digest(const XXH64_state_t *statePtr); 136868e25b9SDmitri Tikhonov 137868e25b9SDmitri Tikhonov/* 138868e25b9SDmitri TikhonovThese functions calculate the xxHash of an input provided in multiple smaller packets, 139868e25b9SDmitri Tikhonovas opposed to an input provided as a single block. 140868e25b9SDmitri Tikhonov 141868e25b9SDmitri TikhonovXXH state space must first be allocated, using either static or dynamic method provided above. 142868e25b9SDmitri Tikhonov 143868e25b9SDmitri TikhonovStart a new hash by initializing state with a seed, using XXHnn_reset(). 144868e25b9SDmitri Tikhonov 145868e25b9SDmitri TikhonovThen, feed the hash state by calling XXHnn_update() as many times as necessary. 146868e25b9SDmitri TikhonovObviously, input must be valid, meaning allocated and read accessible. 147868e25b9SDmitri TikhonovThe function returns an error code, with 0 meaning OK, and any other value meaning there is an error. 148868e25b9SDmitri Tikhonov 149868e25b9SDmitri TikhonovFinally, you can produce a hash anytime, by using XXHnn_digest(). 150868e25b9SDmitri TikhonovThis function returns the final nn-bits hash. 151868e25b9SDmitri TikhonovYou can nonetheless continue feeding the hash state with more input, 152868e25b9SDmitri Tikhonovand therefore get some new hashes, by calling again XXHnn_digest(). 153868e25b9SDmitri Tikhonov 154868e25b9SDmitri TikhonovWhen you are done, don't forget to free XXH state space, using typically XXHnn_freeState(). 155868e25b9SDmitri Tikhonov*/ 156868e25b9SDmitri Tikhonov 157868e25b9SDmitri Tikhonov 158868e25b9SDmitri Tikhonov#if defined (__cplusplus) 159868e25b9SDmitri Tikhonov} 160868e25b9SDmitri Tikhonov#endif 161