14055cfc46a5beb13d0daeace53ac3fe56a1f4ad1Akira Hatanaka/* 24055cfc46a5beb13d0daeace53ac3fe56a1f4ad1Akira Hatanaka xxHash - Fast Hash algorithm 3dda91e0c4b794b1054a6672a6267942ec72d387fAkira Hatanaka Header File 4f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka Copyright (C) 2012-2014, Yann Collet. 5f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 6f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka 7f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka Redistribution and use in source and binary forms, with or without 8f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka modification, are permitted provided that the following conditions are 9f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka met: 10a33fd393d5255716e904fed021f87260095ed00aAkira Hatanaka 11f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka * Redistributions of source code must retain the above copyright 12176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines notice, this list of conditions and the following disclaimer. 13176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines * Redistributions in binary form must reproduce the above 14176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines copyright notice, this list of conditions and the following disclaimer 15f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka in the documentation and/or other materials provided with the 16f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka distribution. 17f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka 18f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21f0cc2087b18c48b17c2f647c88a3e7eef19285fdAkira Hatanaka A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22a33fd393d5255716e904fed021f87260095ed00aAkira Hatanaka OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23a33fd393d5255716e904fed021f87260095ed00aAkira Hatanaka SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27a33fd393d5255716e904fed021f87260095ed00aAkira Hatanaka (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28a33fd393d5255716e904fed021f87260095ed00aAkira Hatanaka OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29a33fd393d5255716e904fed021f87260095ed00aAkira Hatanaka 30a33fd393d5255716e904fed021f87260095ed00aAkira Hatanaka You can contact the author at : 31a33fd393d5255716e904fed021f87260095ed00aAkira Hatanaka - xxHash source repository : http://code.google.com/p/xxhash/ 32a33fd393d5255716e904fed021f87260095ed00aAkira Hatanaka*/ 33a33fd393d5255716e904fed021f87260095ed00aAkira Hatanaka 34cc66254946ec86a2ec94ff9c8db96b05a364a94fAkira Hatanaka/* Notice extracted from xxHash homepage : 35cc66254946ec86a2ec94ff9c8db96b05a364a94fAkira Hatanaka 3693ab6bf534fb6c26563c00f28a8fc5581bb71dfdStephen LinxxHash is an extremely fast Hash algorithm, running at RAM speed limits. 37176edba5311f6eff0cad2631449885ddf4fbc9eaStephen HinesIt also successfully passes all tests from the SMHasher suite. 38176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 39cc66254946ec86a2ec94ff9c8db96b05a364a94fAkira HatanakaComparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 Duo @3GHz) 40cc66254946ec86a2ec94ff9c8db96b05a364a94fAkira Hatanaka 41cc66254946ec86a2ec94ff9c8db96b05a364a94fAkira HatanakaName Speed Q.Score Author 42cc66254946ec86a2ec94ff9c8db96b05a364a94fAkira HatanakaxxHash 5.4 GB/s 10 43e9c876044b7fe9560128a41d511426c014bf5d3fAkira HatanakaCrapWow 3.2 GB/s 2 Andrew 44cc66254946ec86a2ec94ff9c8db96b05a364a94fAkira HatanakaMumurHash 3a 2.7 GB/s 10 Austin Appleby 45cc66254946ec86a2ec94ff9c8db96b05a364a94fAkira HatanakaSpookyHash 2.0 GB/s 10 Bob Jenkins 464055cfc46a5beb13d0daeace53ac3fe56a1f4ad1Akira HatanakaSBox 1.4 GB/s 9 Bret Mulvey 474055cfc46a5beb13d0daeace53ac3fe56a1f4ad1Akira HatanakaLookup3 1.2 GB/s 9 Bob Jenkins 4893ab6bf534fb6c26563c00f28a8fc5581bb71dfdStephen LinSuperFastHash 1.2 GB/s 1 Paul Hsieh 494055cfc46a5beb13d0daeace53ac3fe56a1f4ad1Akira HatanakaCityHash64 1.05 GB/s 10 Pike & Alakuijala 504055cfc46a5beb13d0daeace53ac3fe56a1f4ad1Akira HatanakaFNV 0.55 GB/s 5 Fowler, Noll, Vo 514055cfc46a5beb13d0daeace53ac3fe56a1f4ad1Akira HatanakaCRC32 0.43 GB/s 9 524055cfc46a5beb13d0daeace53ac3fe56a1f4ad1Akira HatanakaMD5-32 0.33 GB/s 10 Ronald L. Rivest 534055cfc46a5beb13d0daeace53ac3fe56a1f4ad1Akira HatanakaSHA1-32 0.28 GB/s 10 544055cfc46a5beb13d0daeace53ac3fe56a1f4ad1Akira Hatanaka 554055cfc46a5beb13d0daeace53ac3fe56a1f4ad1Akira HatanakaQ.Score is a measure of quality of the hash function. 564055cfc46a5beb13d0daeace53ac3fe56a1f4ad1Akira HatanakaIt depends on successfully passing SMHasher test set. 57550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanaka10 is a perfect score. 58176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines*/ 59550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanaka 60550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanaka#pragma once 61550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanaka 62550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanaka#if defined (__cplusplus) 63550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanakaextern "C" { 64550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanaka#endif 65550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanaka 66550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanaka#include <inttypes.h> 67550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanaka 68550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanakastruct XXH_state32_t 69550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanaka{ 70550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanaka uint64_t total_len; 71550ed2077e11ac183380478769c8ddc932ce3168Akira Hatanaka uint32_t seed; 72 uint32_t v1; 73 uint32_t v2; 74 uint32_t v3; 75 uint32_t v4; 76 int memsize; 77 char memory[16]; 78}; 79 80//**************************** 81// Type 82//**************************** 83typedef enum { XXH_OK=0, XXH_ERROR } XXH_errorcode; 84 85 86 87//**************************** 88// Simple Hash Functions 89//**************************** 90 91uint32_t XXH32 (const void* input, uint32_t len, uint32_t seed); 92 93/* 94XXH32() : 95 Calculate the 32-bits hash of sequence of length "len" stored at memory address "input". 96 The memory between input & input+len must be valid (allocated and read-accessible). 97 "seed" can be used to alter the result predictably. 98 This function successfully passes all SMHasher tests. 99 Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s 100 Note that "len" is type "int", which means it is limited to 2^31-1. 101 If your data is larger, use the advanced functions below. 102*/ 103 104 105 106//**************************** 107// Advanced Hash Functions 108//**************************** 109 110void* XXH32_init (unsigned int seed); 111XXH_errorcode XXH32_update (void* state, const void* input, int len); 112unsigned int XXH32_digest (void* state); 113 114/* 115These functions calculate the xxhash of an input provided in several small packets, 116as opposed to an input provided as a single block. 117 118It must be started with : 119void* XXH32_init() 120The function returns a pointer which holds the state of calculation. 121 122This pointer must be provided as "void* state" parameter for XXH32_update(). 123XXH32_update() can be called as many times as necessary. 124The user must provide a valid (allocated) input. 125The function returns an error code, with 0 meaning OK, and any other value meaning there is an error. 126Note that "len" is type "int", which means it is limited to 2^31-1. 127If your data is larger, it is recommended to chunk your data into blocks 128of size for example 2^30 (1GB) to avoid any "int" overflow issue. 129 130Finally, you can end the calculation anytime, by using XXH32_digest(). 131This function returns the final 32-bits hash. 132You must provide the same "void* state" parameter created by XXH32_init(). 133Memory will be freed by XXH32_digest(). 134*/ 135 136 137int XXH32_sizeofState(void); 138XXH_errorcode XXH32_resetState(void* state, unsigned int seed); 139 140#define XXH32_SIZEOFSTATE 48 141typedef struct { long long ll[(XXH32_SIZEOFSTATE+(sizeof(long long)-1))/sizeof(long long)]; } XXH32_stateSpace_t; 142/* 143These functions allow user application to make its own allocation for state. 144 145XXH32_sizeofState() is used to know how much space must be allocated for the xxHash 32-bits state. 146Note that the state must be aligned to access 'long long' fields. Memory must be allocated and referenced by a pointer. 147This pointer must then be provided as 'state' into XXH32_resetState(), which initializes the state. 148 149For static allocation purposes (such as allocation on stack, or freestanding systems without malloc()), 150use the structure XXH32_stateSpace_t, which will ensure that memory space is large enough and correctly aligned to access 'long long' fields. 151*/ 152 153 154unsigned int XXH32_intermediateDigest (void* state); 155/* 156This function does the same as XXH32_digest(), generating a 32-bit hash, 157but preserve memory context. 158This way, it becomes possible to generate intermediate hashes, and then continue feeding data with XXH32_update(). 159To free memory context, use XXH32_digest(), or free(). 160*/ 161 162 163 164//**************************** 165// Deprecated function names 166//**************************** 167// The following translations are provided to ease code transition 168// You are encouraged to no longer this function names 169#define XXH32_feed XXH32_update 170#define XXH32_result XXH32_digest 171#define XXH32_getIntermediateResult XXH32_intermediateDigest 172 173 174 175#if defined (__cplusplus) 176} 177#endif 178