lsquic_xxhash.h revision 50aadb33
1/* Copyright (c) 2017 LiteSpeed Technologies Inc. See LICENSE. */ 2/* 3 xxHash - Extremely Fast Hash algorithm 4 Header File 5 Copyright (C) 2012-2014, Yann Collet. 6 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 7 8 Redistribution and use in source and binary forms, with or without 9 modification, are permitted provided that the following conditions are 10 met: 11 12 * Redistributions of source code must retain the above copyright 13 notice, this list of conditions and the following disclaimer. 14 * Redistributions in binary form must reproduce the above 15 copyright notice, this list of conditions and the following disclaimer 16 in the documentation and/or other materials provided with the 17 distribution. 18 19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31 You can contact the author at : 32 - xxHash source repository : http://code.google.com/p/xxhash/ 33*/ 34 35/* Notice extracted from xxHash homepage : 36 37xxHash is an extremely fast Hash algorithm, running at RAM speed limits. 38It also successfully passes all tests from the SMHasher suite. 39 40Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 Duo @3GHz) 41 42Name Speed Q.Score Author 43xxHash 5.4 GB/s 10 44CrapWow 3.2 GB/s 2 Andrew 45MumurHash 3a 2.7 GB/s 10 Austin Appleby 46SpookyHash 2.0 GB/s 10 Bob Jenkins 47SBox 1.4 GB/s 9 Bret Mulvey 48Lookup3 1.2 GB/s 9 Bob Jenkins 49SuperFastHash 1.2 GB/s 1 Paul Hsieh 50CityHash64 1.05 GB/s 10 Pike & Alakuijala 51FNV 0.55 GB/s 5 Fowler, Noll, Vo 52CRC32 0.43 GB/s 9 53MD5-32 0.33 GB/s 10 Ronald L. Rivest 54SHA1-32 0.28 GB/s 10 55 56Q.Score is a measure of quality of the hash function. 57It depends on successfully passing SMHasher test set. 5810 is a perfect score. 59*/ 60 61#pragma once 62 63#if defined (__cplusplus) 64extern "C" { 65#endif 66 67 68/***************************** 69 Includes 70*****************************/ 71#include <stddef.h> /* size_t */ 72 73 74/***************************** 75 Type 76*****************************/ 77typedef enum { XXH_OK = 0, XXH_ERROR } XXH_errorcode; 78 79 80 81/***************************** 82 Simple Hash Functions 83*****************************/ 84 85unsigned int XXH32(const void *input, size_t length, unsigned seed); 86unsigned long long XXH64(const void *input, size_t length, 87 unsigned long long seed); 88 89/* 90XXH32() : 91 Calculate the 32-bits hash of sequence "length" bytes stored at memory address "input". 92 The memory between input & input+length must be valid (allocated and read-accessible). 93 "seed" can be used to alter the result predictably. 94 This function successfully passes all SMHasher tests. 95 Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s 96XXH64() : 97 Calculate the 64-bits hash of sequence of length "len" stored at memory address "input". 98*/ 99 100 101 102/***************************** 103 Advanced Hash Functions 104*****************************/ 105typedef struct { long long ll[ 6]; } XXH32_state_t; 106typedef struct { long long ll[11]; } XXH64_state_t; 107 108/* 109These structures allow static allocation of XXH states. 110States must then be initialized using XXHnn_reset() before first use. 111 112If you prefer dynamic allocation, please refer to functions below. 113*/ 114 115XXH32_state_t *XXH32_createState(void); 116XXH_errorcode XXH32_freeState(XXH32_state_t *statePtr); 117 118XXH64_state_t *XXH64_createState(void); 119XXH_errorcode XXH64_freeState(XXH64_state_t *statePtr); 120 121/* 122These functions create and release memory for XXH state. 123States must then be initialized using XXHnn_reset() before first use. 124*/ 125 126 127XXH_errorcode XXH32_reset(XXH32_state_t *statePtr, unsigned seed); 128XXH_errorcode XXH32_update(XXH32_state_t *statePtr, const void *input, 129 size_t length); 130unsigned int XXH32_digest(const XXH32_state_t *statePtr); 131 132XXH_errorcode XXH64_reset(XXH64_state_t *statePtr, 133 unsigned long long seed); 134XXH_errorcode XXH64_update(XXH64_state_t *statePtr, const void *input, 135 size_t length); 136unsigned long long XXH64_digest(const XXH64_state_t *statePtr); 137 138/* 139These functions calculate the xxHash of an input provided in multiple smaller packets, 140as opposed to an input provided as a single block. 141 142XXH state space must first be allocated, using either static or dynamic method provided above. 143 144Start a new hash by initializing state with a seed, using XXHnn_reset(). 145 146Then, feed the hash state by calling XXHnn_update() as many times as necessary. 147Obviously, input must be valid, meaning allocated and read accessible. 148The function returns an error code, with 0 meaning OK, and any other value meaning there is an error. 149 150Finally, you can produce a hash anytime, by using XXHnn_digest(). 151This function returns the final nn-bits hash. 152You can nonetheless continue feeding the hash state with more input, 153and therefore get some new hashes, by calling again XXHnn_digest(). 154 155When you are done, don't forget to free XXH state space, using typically XXHnn_freeState(). 156*/ 157 158 159#if defined (__cplusplus) 160} 161#endif 162