lsquic_xxhash.h revision a74702c6
1a74702c6SGeorge Wang/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc.  See LICENSE. */
250aadb33SDmitri Tikhonov/*
350aadb33SDmitri Tikhonov   xxHash - Extremely Fast Hash algorithm
450aadb33SDmitri Tikhonov   Header File
550aadb33SDmitri Tikhonov   Copyright (C) 2012-2014, Yann Collet.
650aadb33SDmitri Tikhonov   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
750aadb33SDmitri Tikhonov
850aadb33SDmitri Tikhonov   Redistribution and use in source and binary forms, with or without
950aadb33SDmitri Tikhonov   modification, are permitted provided that the following conditions are
1050aadb33SDmitri Tikhonov   met:
1150aadb33SDmitri Tikhonov
1250aadb33SDmitri Tikhonov       * Redistributions of source code must retain the above copyright
1350aadb33SDmitri Tikhonov   notice, this list of conditions and the following disclaimer.
1450aadb33SDmitri Tikhonov       * Redistributions in binary form must reproduce the above
1550aadb33SDmitri Tikhonov   copyright notice, this list of conditions and the following disclaimer
1650aadb33SDmitri Tikhonov   in the documentation and/or other materials provided with the
1750aadb33SDmitri Tikhonov   distribution.
1850aadb33SDmitri Tikhonov
1950aadb33SDmitri Tikhonov   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2050aadb33SDmitri Tikhonov   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2150aadb33SDmitri Tikhonov   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2250aadb33SDmitri Tikhonov   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2350aadb33SDmitri Tikhonov   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2450aadb33SDmitri Tikhonov   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2550aadb33SDmitri Tikhonov   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2650aadb33SDmitri Tikhonov   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2750aadb33SDmitri Tikhonov   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2850aadb33SDmitri Tikhonov   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2950aadb33SDmitri Tikhonov   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3050aadb33SDmitri Tikhonov
3150aadb33SDmitri Tikhonov   You can contact the author at :
3250aadb33SDmitri Tikhonov   - xxHash source repository : http://code.google.com/p/xxhash/
3350aadb33SDmitri Tikhonov*/
3450aadb33SDmitri Tikhonov
3550aadb33SDmitri Tikhonov/* Notice extracted from xxHash homepage :
3650aadb33SDmitri Tikhonov
3750aadb33SDmitri TikhonovxxHash is an extremely fast Hash algorithm, running at RAM speed limits.
3850aadb33SDmitri TikhonovIt also successfully passes all tests from the SMHasher suite.
3950aadb33SDmitri Tikhonov
4050aadb33SDmitri TikhonovComparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 Duo @3GHz)
4150aadb33SDmitri Tikhonov
4250aadb33SDmitri TikhonovName            Speed       Q.Score   Author
4350aadb33SDmitri TikhonovxxHash          5.4 GB/s     10
4450aadb33SDmitri TikhonovCrapWow         3.2 GB/s      2       Andrew
4550aadb33SDmitri TikhonovMumurHash 3a    2.7 GB/s     10       Austin Appleby
4650aadb33SDmitri TikhonovSpookyHash      2.0 GB/s     10       Bob Jenkins
4750aadb33SDmitri TikhonovSBox            1.4 GB/s      9       Bret Mulvey
4850aadb33SDmitri TikhonovLookup3         1.2 GB/s      9       Bob Jenkins
4950aadb33SDmitri TikhonovSuperFastHash   1.2 GB/s      1       Paul Hsieh
5050aadb33SDmitri TikhonovCityHash64      1.05 GB/s    10       Pike & Alakuijala
5150aadb33SDmitri TikhonovFNV             0.55 GB/s     5       Fowler, Noll, Vo
5250aadb33SDmitri TikhonovCRC32           0.43 GB/s     9
5350aadb33SDmitri TikhonovMD5-32          0.33 GB/s    10       Ronald L. Rivest
5450aadb33SDmitri TikhonovSHA1-32         0.28 GB/s    10
5550aadb33SDmitri Tikhonov
5650aadb33SDmitri TikhonovQ.Score is a measure of quality of the hash function.
5750aadb33SDmitri TikhonovIt depends on successfully passing SMHasher test set.
5850aadb33SDmitri Tikhonov10 is a perfect score.
5950aadb33SDmitri Tikhonov*/
6050aadb33SDmitri Tikhonov
6150aadb33SDmitri Tikhonov#pragma once
6250aadb33SDmitri Tikhonov
6350aadb33SDmitri Tikhonov#if defined (__cplusplus)
6450aadb33SDmitri Tikhonovextern "C" {
6550aadb33SDmitri Tikhonov#endif
6650aadb33SDmitri Tikhonov
6750aadb33SDmitri Tikhonov
6850aadb33SDmitri Tikhonov/*****************************
6950aadb33SDmitri Tikhonov   Includes
7050aadb33SDmitri Tikhonov*****************************/
7150aadb33SDmitri Tikhonov#include <stddef.h>   /* size_t */
7250aadb33SDmitri Tikhonov
7350aadb33SDmitri Tikhonov
7450aadb33SDmitri Tikhonov/*****************************
7550aadb33SDmitri Tikhonov   Type
7650aadb33SDmitri Tikhonov*****************************/
7750aadb33SDmitri Tikhonovtypedef enum { XXH_OK = 0, XXH_ERROR } XXH_errorcode;
7850aadb33SDmitri Tikhonov
7950aadb33SDmitri Tikhonov
8050aadb33SDmitri Tikhonov
8150aadb33SDmitri Tikhonov/*****************************
8250aadb33SDmitri Tikhonov   Simple Hash Functions
8350aadb33SDmitri Tikhonov*****************************/
8450aadb33SDmitri Tikhonov
8550aadb33SDmitri Tikhonovunsigned int       XXH32(const void *input, size_t length, unsigned seed);
8650aadb33SDmitri Tikhonovunsigned long long XXH64(const void *input, size_t length,
8750aadb33SDmitri Tikhonov                         unsigned long long seed);
8850aadb33SDmitri Tikhonov
8950aadb33SDmitri Tikhonov/*
9050aadb33SDmitri TikhonovXXH32() :
9150aadb33SDmitri Tikhonov    Calculate the 32-bits hash of sequence "length" bytes stored at memory address "input".
9250aadb33SDmitri Tikhonov    The memory between input & input+length must be valid (allocated and read-accessible).
9350aadb33SDmitri Tikhonov    "seed" can be used to alter the result predictably.
9450aadb33SDmitri Tikhonov    This function successfully passes all SMHasher tests.
9550aadb33SDmitri Tikhonov    Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s
9650aadb33SDmitri TikhonovXXH64() :
9750aadb33SDmitri Tikhonov    Calculate the 64-bits hash of sequence of length "len" stored at memory address "input".
9850aadb33SDmitri Tikhonov*/
9950aadb33SDmitri Tikhonov
10050aadb33SDmitri Tikhonov
10150aadb33SDmitri Tikhonov
10250aadb33SDmitri Tikhonov/*****************************
10350aadb33SDmitri Tikhonov   Advanced Hash Functions
10450aadb33SDmitri Tikhonov*****************************/
10550aadb33SDmitri Tikhonovtypedef struct { long long ll[ 6]; } XXH32_state_t;
10650aadb33SDmitri Tikhonovtypedef struct { long long ll[11]; } XXH64_state_t;
10750aadb33SDmitri Tikhonov
10850aadb33SDmitri Tikhonov/*
10950aadb33SDmitri TikhonovThese structures allow static allocation of XXH states.
11050aadb33SDmitri TikhonovStates must then be initialized using XXHnn_reset() before first use.
11150aadb33SDmitri Tikhonov
11250aadb33SDmitri TikhonovIf you prefer dynamic allocation, please refer to functions below.
11350aadb33SDmitri Tikhonov*/
11450aadb33SDmitri Tikhonov
11550aadb33SDmitri TikhonovXXH32_state_t *XXH32_createState(void);
11650aadb33SDmitri TikhonovXXH_errorcode  XXH32_freeState(XXH32_state_t *statePtr);
11750aadb33SDmitri Tikhonov
11850aadb33SDmitri TikhonovXXH64_state_t *XXH64_createState(void);
11950aadb33SDmitri TikhonovXXH_errorcode  XXH64_freeState(XXH64_state_t *statePtr);
12050aadb33SDmitri Tikhonov
12150aadb33SDmitri Tikhonov/*
12250aadb33SDmitri TikhonovThese functions create and release memory for XXH state.
12350aadb33SDmitri TikhonovStates must then be initialized using XXHnn_reset() before first use.
12450aadb33SDmitri Tikhonov*/
12550aadb33SDmitri Tikhonov
12650aadb33SDmitri Tikhonov
12750aadb33SDmitri TikhonovXXH_errorcode XXH32_reset(XXH32_state_t *statePtr, unsigned seed);
12850aadb33SDmitri TikhonovXXH_errorcode XXH32_update(XXH32_state_t *statePtr, const void *input,
12950aadb33SDmitri Tikhonov                           size_t length);
13050aadb33SDmitri Tikhonovunsigned int  XXH32_digest(const XXH32_state_t *statePtr);
13150aadb33SDmitri Tikhonov
13250aadb33SDmitri TikhonovXXH_errorcode      XXH64_reset(XXH64_state_t *statePtr,
13350aadb33SDmitri Tikhonov                               unsigned long long seed);
13450aadb33SDmitri TikhonovXXH_errorcode      XXH64_update(XXH64_state_t *statePtr, const void *input,
13550aadb33SDmitri Tikhonov                                size_t length);
13650aadb33SDmitri Tikhonovunsigned long long XXH64_digest(const XXH64_state_t *statePtr);
13750aadb33SDmitri Tikhonov
13850aadb33SDmitri Tikhonov/*
13950aadb33SDmitri TikhonovThese functions calculate the xxHash of an input provided in multiple smaller packets,
14050aadb33SDmitri Tikhonovas opposed to an input provided as a single block.
14150aadb33SDmitri Tikhonov
14250aadb33SDmitri TikhonovXXH state space must first be allocated, using either static or dynamic method provided above.
14350aadb33SDmitri Tikhonov
14450aadb33SDmitri TikhonovStart a new hash by initializing state with a seed, using XXHnn_reset().
14550aadb33SDmitri Tikhonov
14650aadb33SDmitri TikhonovThen, feed the hash state by calling XXHnn_update() as many times as necessary.
14750aadb33SDmitri TikhonovObviously, input must be valid, meaning allocated and read accessible.
14850aadb33SDmitri TikhonovThe function returns an error code, with 0 meaning OK, and any other value meaning there is an error.
14950aadb33SDmitri Tikhonov
15050aadb33SDmitri TikhonovFinally, you can produce a hash anytime, by using XXHnn_digest().
15150aadb33SDmitri TikhonovThis function returns the final nn-bits hash.
15250aadb33SDmitri TikhonovYou can nonetheless continue feeding the hash state with more input,
15350aadb33SDmitri Tikhonovand therefore get some new hashes, by calling again XXHnn_digest().
15450aadb33SDmitri Tikhonov
15550aadb33SDmitri TikhonovWhen you are done, don't forget to free XXH state space, using typically XXHnn_freeState().
15650aadb33SDmitri Tikhonov*/
15750aadb33SDmitri Tikhonov
15850aadb33SDmitri Tikhonov
15950aadb33SDmitri Tikhonov#if defined (__cplusplus)
16050aadb33SDmitri Tikhonov}
16150aadb33SDmitri Tikhonov#endif
162