diff options
author | Kotresh HR <khiremat@redhat.com> | 2017-06-28 05:09:12 -0400 |
---|---|---|
committer | Niels de Vos <ndevos@redhat.com> | 2017-06-30 08:16:57 +0000 |
commit | 292b4e42fdc023e307fde35e189285040d4b9cdd (patch) | |
tree | 1c91585e4a9c4bd3871666622f8fe5f158c67ec0 /contrib/xxhash/xxhash.h | |
parent | d95535bae2d200c2210feac7568b1fdbf6f545a9 (diff) |
contrib/xxhash: Add xxhash library
xxhash is a faster non-cryptographic hash.
https://github.com/Cyan4973/xxHash
Release Taken: "xxHash v0.6.2"
--------------
Files added:
contrib/xxhash/xxhash.c
contrib/xxhash/xxhash.h
contrib/xxhash/xxhsum.c
Modifications to source:
------------------------
Following functions and data types got 'GF_' prefix
as below to avoid any form of name collisions in future.
---- Functions ----
GF_XXH_versionNumber
GF_XXH32
GF_XXH32_createState
GF_XXH32_freeState
GF_XXH32_copyState
GF_XXH32_reset
GF_XXH32_update
GF_XXH32_digest
GF_XXH32_canonicalFromHash
GF_XXH32_hashFromCanonical
GF_XXH64
GF_XXH64_createState
GF_XXH64_freeState
GF_XXH64_copyState
GF_XXH64_reset
GF_XXH64_update
GF_XXH64_digest
GF_XXH64_canonicalFromHash
GF_XXH64_hashFromCanonical
---- Data Types ----
GF_XXH_errorcode
GF_XXH32_state_t*
GF_XXH32_canonical_t*
GF_XXH32_hash_t
GF_XXH64_state_t*
GF_XXH64_canonical_t*
GF_XXH64_hash_t
It is linked with libglusterfs.so. A wrapper
funtion is also added for the easy usage in
common-utils.c.
xxhash can be used for the all the usecases where
a faster non-cryptographic hash is required.
gfid to path infra would be using this for now.
NOTE:
----
The gluster coding guidelines check is ignored
as maintaining it further would be difficult.
Updates: #253
Change-Id: Ib143f90d91d4ee99864a10246d5983e92900173b
Signed-off-by: Kotresh HR <khiremat@redhat.com>
Reviewed-on: https://review.gluster.org/17641
Smoke: Gluster Build System <jenkins@build.gluster.org>
Reviewed-by: Amar Tumballi <amarts@redhat.com>
CentOS-regression: Gluster Build System <jenkins@build.gluster.org>
NetBSD-regression: NetBSD Build System <jenkins@build.gluster.org>
Reviewed-by: Niels de Vos <ndevos@redhat.com>
Diffstat (limited to 'contrib/xxhash/xxhash.h')
-rw-r--r-- | contrib/xxhash/xxhash.h | 301 |
1 files changed, 301 insertions, 0 deletions
diff --git a/contrib/xxhash/xxhash.h b/contrib/xxhash/xxhash.h new file mode 100644 index 00000000000..98352b9018e --- /dev/null +++ b/contrib/xxhash/xxhash.h @@ -0,0 +1,301 @@ +/* + xxHash - Extremely Fast Hash algorithm + Header File + Copyright (C) 2012-2016, Yann Collet. + + BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are + met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + copyright notice, this list of conditions and the following disclaimer + in the documentation and/or other materials provided with the + distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + + You can contact the author at : + - xxHash source repository : https://github.com/Cyan4973/xxHash +*/ + +/* Notice extracted from xxHash homepage : + +xxHash is an extremely fast Hash algorithm, running at RAM speed limits. +It also successfully passes all tests from the SMHasher suite. + +Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 Duo @3GHz) + +Name Speed Q.Score Author +xxHash 5.4 GB/s 10 +CrapWow 3.2 GB/s 2 Andrew +MumurHash 3a 2.7 GB/s 10 Austin Appleby +SpookyHash 2.0 GB/s 10 Bob Jenkins +SBox 1.4 GB/s 9 Bret Mulvey +Lookup3 1.2 GB/s 9 Bob Jenkins +SuperFastHash 1.2 GB/s 1 Paul Hsieh +CityHash64 1.05 GB/s 10 Pike & Alakuijala +FNV 0.55 GB/s 5 Fowler, Noll, Vo +CRC32 0.43 GB/s 9 +MD5-32 0.33 GB/s 10 Ronald L. Rivest +SHA1-32 0.28 GB/s 10 + +Q.Score is a measure of quality of the hash function. +It depends on successfully passing SMHasher test set. +10 is a perfect score. + +A 64-bits version, named XXH64, is available since r35. +It offers much better speed, but for 64-bits applications only. +Name Speed on 64 bits Speed on 32 bits +XXH64 13.8 GB/s 1.9 GB/s +XXH32 6.8 GB/s 6.0 GB/s +*/ + +#ifndef XXHASH_H_5627135585666179 +#define XXHASH_H_5627135585666179 1 + +#if defined (__cplusplus) +extern "C" { +#endif + + +/* **************************** +* Compiler specifics +******************************/ +#if !(defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) /* ! C99 */ +# define restrict /* disable restrict */ +#endif + + +/* **************************** +* Definitions +******************************/ +#include <stddef.h> /* size_t */ +typedef enum { XXH_OK=0, XXH_ERROR } GF_XXH_errorcode; + + +/* **************************** +* API modifier +******************************/ +/** XXH_PRIVATE_API +* This is useful to include xxhash functions in `static` mode +* in order to inline them, and remove their symbol from the public list. +* Methodology : +* #define XXH_PRIVATE_API +* #include "xxhash.h" +* `xxhash.c` is automatically included. +* It's not useful to compile and link it as a separate module. +*/ +#ifdef XXH_PRIVATE_API +# ifndef XXH_STATIC_LINKING_ONLY +# define XXH_STATIC_LINKING_ONLY +# endif +# if defined(__GNUC__) +# define XXH_PUBLIC_API static __inline __attribute__((unused)) +# elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) +# define XXH_PUBLIC_API static inline +# elif defined(_MSC_VER) +# define XXH_PUBLIC_API static __inline +# else +# define XXH_PUBLIC_API static /* this version may generate warnings for unused static functions; disable the relevant warning */ +# endif +#else +# define XXH_PUBLIC_API /* do nothing */ +#endif /* XXH_PRIVATE_API */ + +/*!XXH_NAMESPACE, aka Namespace Emulation : + +If you want to include _and expose_ xxHash functions from within your own library, +but also want to avoid symbol collisions with other libraries which may also include xxHash, + +you can use XXH_NAMESPACE, to automatically prefix any public symbol from xxhash library +with the value of XXH_NAMESPACE (therefore, avoid NULL and numeric values). + +Note that no change is required within the calling program as long as it includes `xxhash.h` : +regular symbol name will be automatically translated by this header. +*/ +#ifdef XXH_NAMESPACE +# define XXH_CAT(A,B) A##B +# define XXH_NAME2(A,B) XXH_CAT(A,B) +# define GF_XXH_versionNumber XXH_NAME2(XXH_NAMESPACE, GF_XXH_versionNumber) +# define GF_XXH32 XXH_NAME2(XXH_NAMESPACE, GF_XXH32) +# define GF_XXH32_createState XXH_NAME2(XXH_NAMESPACE, GF_XXH32_createState) +# define GF_XXH32_freeState XXH_NAME2(XXH_NAMESPACE, GF_XXH32_freeState) +# define GF_XXH32_reset XXH_NAME2(XXH_NAMESPACE, GF_XXH32_reset) +# define GF_XXH32_update XXH_NAME2(XXH_NAMESPACE, GF_XXH32_update) +# define GF_XXH32_digest XXH_NAME2(XXH_NAMESPACE, GF_XXH32_digest) +# define GF_XXH32_copyState XXH_NAME2(XXH_NAMESPACE, GF_XXH32_copyState) +# define GF_XXH32_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, GF_XXH32_canonicalFromHash) +# define GF_XXH32_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, GF_XXH32_hashFromCanonical) +# define GF_XXH64 XXH_NAME2(XXH_NAMESPACE, GF_XXH64) +# define GF_XXH64_createState XXH_NAME2(XXH_NAMESPACE, GF_XXH64_createState) +# define GF_XXH64_freeState XXH_NAME2(XXH_NAMESPACE, GF_XXH64_freeState) +# define GF_XXH64_reset XXH_NAME2(XXH_NAMESPACE, GF_XXH64_reset) +# define GF_XXH64_update XXH_NAME2(XXH_NAMESPACE, GF_XXH64_update) +# define GF_XXH64_digest XXH_NAME2(XXH_NAMESPACE, GF_XXH64_digest) +# define GF_XXH64_copyState XXH_NAME2(XXH_NAMESPACE, GF_XXH64_copyState) +# define GF_XXH64_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, GF_XXH64_canonicalFromHash) +# define GF_XXH64_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, GF_XXH64_hashFromCanonical) +#endif + + +/* ************************************* +* Version +***************************************/ +#define XXH_VERSION_MAJOR 0 +#define XXH_VERSION_MINOR 6 +#define XXH_VERSION_RELEASE 2 +#define XXH_VERSION_NUMBER (XXH_VERSION_MAJOR *100*100 + XXH_VERSION_MINOR *100 + XXH_VERSION_RELEASE) +XXH_PUBLIC_API unsigned GF_XXH_versionNumber (void); + + +/*-********************************************************************** +* 32-bits hash +************************************************************************/ +typedef unsigned int GF_XXH32_hash_t; + +/*! XXH32() : + Calculate the 32-bits hash of sequence "length" bytes stored at memory address "input". + The memory between input & input+length must be valid (allocated and read-accessible). + "seed" can be used to alter the result predictably. + Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s */ +XXH_PUBLIC_API GF_XXH32_hash_t GF_XXH32 (const void* input, size_t length, unsigned int seed); + +/*====== Streaming ======*/ +typedef struct XXH32_state_s GF_XXH32_state_t; /* incomplete type */ +XXH_PUBLIC_API GF_XXH32_state_t* GF_XXH32_createState(void); +XXH_PUBLIC_API GF_XXH_errorcode GF_XXH32_freeState(GF_XXH32_state_t* statePtr); +XXH_PUBLIC_API void GF_XXH32_copyState(GF_XXH32_state_t* restrict dst_state, const GF_XXH32_state_t* restrict src_state); + +XXH_PUBLIC_API GF_XXH_errorcode GF_XXH32_reset (GF_XXH32_state_t* statePtr, unsigned int seed); +XXH_PUBLIC_API GF_XXH_errorcode GF_XXH32_update (GF_XXH32_state_t* statePtr, const void* input, size_t length); +XXH_PUBLIC_API GF_XXH32_hash_t GF_XXH32_digest (const GF_XXH32_state_t* statePtr); + +/* +These functions generate the xxHash of an input provided in multiple segments. +Note that, for small input, they are slower than single-call functions, due to state management. +For small input, prefer `XXH32()` and `XXH64()` . + +XXH state must first be allocated, using XXH*_createState() . + +Start a new hash by initializing state with a seed, using XXH*_reset(). + +Then, feed the hash state by calling XXH*_update() as many times as necessary. +Obviously, input must be allocated and read accessible. +The function returns an error code, with 0 meaning OK, and any other value meaning there is an error. + +Finally, a hash value can be produced anytime, by using XXH*_digest(). +This function returns the nn-bits hash as an int or long long. + +It's still possible to continue inserting input into the hash state after a digest, +and generate some new hashes later on, by calling again XXH*_digest(). + +When done, free XXH state space if it was allocated dynamically. +*/ + +/*====== Canonical representation ======*/ + +typedef struct { unsigned char digest[4]; } GF_XXH32_canonical_t; +XXH_PUBLIC_API void GF_XXH32_canonicalFromHash(GF_XXH32_canonical_t* dst, GF_XXH32_hash_t hash); +XXH_PUBLIC_API GF_XXH32_hash_t GF_XXH32_hashFromCanonical(const GF_XXH32_canonical_t* src); + +/* Default result type for XXH functions are primitive unsigned 32 and 64 bits. +* The canonical representation uses human-readable write convention, aka big-endian (large digits first). +* These functions allow transformation of hash result into and from its canonical format. +* This way, hash values can be written into a file / memory, and remain comparable on different systems and programs. +*/ + + +#ifndef XXH_NO_LONG_LONG +/*-********************************************************************** +* 64-bits hash +************************************************************************/ +typedef unsigned long long GF_XXH64_hash_t; + +/*! XXH64() : + Calculate the 64-bits hash of sequence of length "len" stored at memory address "input". + "seed" can be used to alter the result predictably. + This function runs faster on 64-bits systems, but slower on 32-bits systems (see benchmark). +*/ +XXH_PUBLIC_API GF_XXH64_hash_t GF_XXH64 (const void* input, size_t length, unsigned long long seed); + +/*====== Streaming ======*/ +typedef struct XXH64_state_s GF_XXH64_state_t; /* incomplete type */ +XXH_PUBLIC_API GF_XXH64_state_t* GF_XXH64_createState(void); +XXH_PUBLIC_API GF_XXH_errorcode GF_XXH64_freeState(GF_XXH64_state_t* statePtr); +XXH_PUBLIC_API void GF_XXH64_copyState(GF_XXH64_state_t* restrict dst_state, const GF_XXH64_state_t* restrict src_state); + +XXH_PUBLIC_API GF_XXH_errorcode GF_XXH64_reset (GF_XXH64_state_t* statePtr, unsigned long long seed); +XXH_PUBLIC_API GF_XXH_errorcode GF_XXH64_update (GF_XXH64_state_t* statePtr, const void* input, size_t length); +XXH_PUBLIC_API GF_XXH64_hash_t GF_XXH64_digest (const GF_XXH64_state_t* statePtr); + +/*====== Canonical representation ======*/ +typedef struct { unsigned char digest[8]; } GF_XXH64_canonical_t; +XXH_PUBLIC_API void GF_XXH64_canonicalFromHash(GF_XXH64_canonical_t* dst, GF_XXH64_hash_t hash); +XXH_PUBLIC_API GF_XXH64_hash_t GF_XXH64_hashFromCanonical(const GF_XXH64_canonical_t* src); +#endif /* XXH_NO_LONG_LONG */ + + +#ifdef XXH_STATIC_LINKING_ONLY + +/* ================================================================================================ + This section contains definitions which are not guaranteed to remain stable. + They may change in future versions, becoming incompatible with a different version of the library. + They shall only be used with static linking. + Never use these definitions in association with dynamic linking ! +=================================================================================================== */ + +/* These definitions are only meant to allow allocation of XXH state + statically, on stack, or in a struct for example. + Do not use members directly. */ + + struct XXH32_state_s { + unsigned total_len_32; + unsigned large_len; + unsigned v1; + unsigned v2; + unsigned v3; + unsigned v4; + unsigned mem32[4]; /* buffer defined as U32 for alignment */ + unsigned memsize; + unsigned reserved; /* never read nor write, will be removed in a future version */ + }; /* typedef'd to XXH32_state_t */ + +#ifndef XXH_NO_LONG_LONG + struct XXH64_state_s { + unsigned long long total_len; + unsigned long long v1; + unsigned long long v2; + unsigned long long v3; + unsigned long long v4; + unsigned long long mem64[4]; /* buffer defined as U64 for alignment */ + unsigned memsize; + unsigned reserved[2]; /* never read nor write, will be removed in a future version */ + }; /* typedef'd to XXH64_state_t */ +#endif + +# ifdef XXH_PRIVATE_API +# include "xxhash.c" /* include xxhash function bodies as `static`, for inlining */ +# endif + +#endif /* XXH_STATIC_LINKING_ONLY */ + + +#if defined (__cplusplus) +} +#endif + +#endif /* XXHASH_H_5627135585666179 */ |