/* * xxHash - Fast Hash algorithm * 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 homepage: http://www.xxhash.com * - xxHash source repository : https://github.com/Cyan4973/xxHash */ /* ************************************* * Tuning parameters ***************************************/ /*!XXH_FORCE_MEMORY_ACCESS : * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable. * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal. * The below switch allow to select different access method for improved performance. * Method 0 (default) : use `memcpy()`. Safe and portable. * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable). * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`. * Method 2 : direct access. This method doesn't depend on compiler but violate C standard. * It can generate buggy code on targets which do not support unaligned memory accesses. * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6) * See http://stackoverflow.com/a/32095106/646947 for details. * Prefer these methods in priority order (0 > 1 > 2) */ #ifndef XXH_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */ # if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) \ || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) \ || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) ) #define XXH_FORCE_MEMORY_ACCESS … # elif (defined(__INTEL_COMPILER) && !defined(_WIN32)) || \ (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) \ || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) \ || defined(__ARM_ARCH_7S__) )) #define XXH_FORCE_MEMORY_ACCESS … # endif #endif /*!XXH_ACCEPT_NULL_INPUT_POINTER : * If input pointer is NULL, xxHash default behavior is to dereference it, triggering a segfault. * When this macro is enabled, xxHash actively checks input for null pointer. * It it is, result for null input pointers is the same as a null-length input. */ #ifndef XXH_ACCEPT_NULL_INPUT_POINTER /* can be defined externally */ #define XXH_ACCEPT_NULL_INPUT_POINTER … #endif /*!XXH_FORCE_NATIVE_FORMAT : * By default, xxHash library provides endian-independent Hash values, based on little-endian convention. * Results are therefore identical for little-endian and big-endian CPU. * This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format. * Should endian-independence be of no importance for your application, you may set the #define below to 1, * to improve speed for Big-endian CPU. * This option has no impact on Little_Endian CPU. */ #ifndef XXH_FORCE_NATIVE_FORMAT /* can be defined externally */ #define XXH_FORCE_NATIVE_FORMAT … #endif /*!XXH_FORCE_ALIGN_CHECK : * This is a minor performance trick, only useful with lots of very small keys. * It means : check for aligned/unaligned input. * The check costs one initial branch per hash; * set it to 0 when the input is guaranteed to be aligned, * or when alignment doesn't matter for performance. */ #ifndef XXH_FORCE_ALIGN_CHECK /* can be defined externally */ # if defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64) #define XXH_FORCE_ALIGN_CHECK … # else #define XXH_FORCE_ALIGN_CHECK … # endif #endif /* ************************************* * Includes & Memory related functions ***************************************/ /*! Modify the local functions below should you wish to use some other memory routines * for malloc(), free() */ #include <stdlib.h> static void* XXH_malloc(size_t s) { … } static void XXH_free (void* p) { … } /*! and for memcpy() */ #include <string.h> static void* XXH_memcpy(void* dest, const void* src, size_t size) { … } #include <assert.h> /* assert */ #define XXH_STATIC_LINKING_ONLY #include "xxhash.h" /* ************************************* * Compiler Specific Options ***************************************/ #ifdef _MSC_VER /* Visual Studio */ # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ #define FORCE_INLINE … #else # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ # ifdef __GNUC__ #define FORCE_INLINE … # else #define FORCE_INLINE … # endif # else #define FORCE_INLINE … # endif /* __STDC_VERSION__ */ #endif /* ************************************* * Basic Types ***************************************/ #ifndef MEM_MODULE # if !defined (__VMS) \ && (defined (__cplusplus) \ || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) # include <stdint.h> BYTE; U16; U32; # else typedef unsigned char BYTE; typedef unsigned short U16; typedef unsigned int U32; # endif #endif #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2)) /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */ static U32 XXH_read32(const void* memPtr) { return *(const U32*) memPtr; } #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1)) /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ /* currently only defined for gcc and icc */ typedef union { U32 u32; } __attribute__((packed)) unalign; static U32 XXH_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } #else /* portable and safe solution. Generally efficient. * see : http://stackoverflow.com/a/32095106/646947 */ static U32 XXH_read32(const void* memPtr) { … } #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */ /* **************************************** * Compiler-specific Functions and Macros ******************************************/ #define XXH_GCC_VERSION … /* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */ #if defined(_MSC_VER) #define XXH_rotl32 … #define XXH_rotl64 … #else #define XXH_rotl32(x,r) … #define XXH_rotl64(x,r) … #endif #if defined(_MSC_VER) /* Visual Studio */ #define XXH_swap32 … #elif XXH_GCC_VERSION >= 403 #define XXH_swap32 … #else static U32 XXH_swap32 (U32 x) { … } #endif /* ************************************* * Architecture Macros ***************************************/ XXH_endianess; /* XXH_CPU_LITTLE_ENDIAN can be defined externally, for example on the compiler command line */ #ifndef XXH_CPU_LITTLE_ENDIAN static int XXH_isLittleEndian(void) { … } #define XXH_CPU_LITTLE_ENDIAN … #endif /* *************************** * Memory reads *****************************/ XXH_alignment; FORCE_INLINE U32 XXH_readLE32_align(const void* ptr, XXH_endianess endian, XXH_alignment align) { … } FORCE_INLINE U32 XXH_readLE32(const void* ptr, XXH_endianess endian) { … } static U32 XXH_readBE32(const void* ptr) { … } /* ************************************* * Macros ***************************************/ #define XXH_STATIC_ASSERT(c) … XXH_PUBLIC_API unsigned XXH_versionNumber (void) { … } /* ******************************************************************* * 32-bit hash functions *********************************************************************/ static const U32 PRIME32_1 = …; /* 0b10011110001101110111100110110001 */ static const U32 PRIME32_2 = …; /* 0b10000101111010111100101001110111 */ static const U32 PRIME32_3 = …; /* 0b11000010101100101010111000111101 */ static const U32 PRIME32_4 = …; /* 0b00100111110101001110101100101111 */ static const U32 PRIME32_5 = …; /* 0b00010110010101100110011110110001 */ static U32 XXH32_round(U32 seed, U32 input) { … } /* mix all bits */ static U32 XXH32_avalanche(U32 h32) { … } #define XXH_get32bits(p) … static U32 XXH32_finalize(U32 h32, const void* ptr, size_t len, XXH_endianess endian, XXH_alignment align) { … } FORCE_INLINE U32 XXH32_endian_align(const void* input, size_t len, U32 seed, XXH_endianess endian, XXH_alignment align) { … } XXH_PUBLIC_API unsigned int XXH32 (const void* input, size_t len, unsigned int seed) { … } /*====== Hash streaming ======*/ XXH_PUBLIC_API XXH32_state_t* XXH32_createState(void) { … } XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr) { … } XXH_PUBLIC_API void XXH32_copyState(XXH32_state_t* dstState, const XXH32_state_t* srcState) { … } XXH_PUBLIC_API XXH_errorcode XXH32_reset(XXH32_state_t* statePtr, unsigned int seed) { … } FORCE_INLINE XXH_errorcode XXH32_update_endian(XXH32_state_t* state, const void* input, size_t len, XXH_endianess endian) { … } XXH_PUBLIC_API XXH_errorcode XXH32_update (XXH32_state_t* state_in, const void* input, size_t len) { … } FORCE_INLINE U32 XXH32_digest_endian (const XXH32_state_t* state, XXH_endianess endian) { … } XXH_PUBLIC_API unsigned int XXH32_digest (const XXH32_state_t* state_in) { … } /*====== Canonical representation ======*/ /*! Default XXH result types are basic unsigned 32 and 64 bits. * The canonical representation follows 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 or buffer, remaining comparable across different systems. */ XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash) { … } XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t* src) { … } #ifndef XXH_NO_LONG_LONG /* ******************************************************************* * 64-bit hash functions *********************************************************************/ /*====== Memory access ======*/ #ifndef MEM_MODULE #define MEM_MODULE # if !defined (__VMS) \ && (defined (__cplusplus) \ || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) # include <stdint.h> U64; # else /* if compiler doesn't support unsigned long long, replace by another 64-bit type */ typedef unsigned long long U64; # endif #endif #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2)) /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */ static U64 XXH_read64(const void* memPtr) { return *(const U64*) memPtr; } #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1)) /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ /* currently only defined for gcc and icc */ typedef union { U32 u32; U64 u64; } __attribute__((packed)) unalign64; static U64 XXH_read64(const void* ptr) { return ((const unalign64*)ptr)->u64; } #else /* portable and safe solution. Generally efficient. * see : http://stackoverflow.com/a/32095106/646947 */ static U64 XXH_read64(const void* memPtr) { … } #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */ #if defined(_MSC_VER) /* Visual Studio */ #define XXH_swap64 … #elif XXH_GCC_VERSION >= 403 #define XXH_swap64 … #else static U64 XXH_swap64 (U64 x) { … } #endif FORCE_INLINE U64 XXH_readLE64_align(const void* ptr, XXH_endianess endian, XXH_alignment align) { … } FORCE_INLINE U64 XXH_readLE64(const void* ptr, XXH_endianess endian) { … } static U64 XXH_readBE64(const void* ptr) { … } /*====== xxh64 ======*/ static const U64 PRIME64_1 = …; /* 0b1001111000110111011110011011000110000101111010111100101010000111 */ static const U64 PRIME64_2 = …; /* 0b1100001010110010101011100011110100100111110101001110101101001111 */ static const U64 PRIME64_3 = …; /* 0b0001011001010110011001111011000110011110001101110111100111111001 */ static const U64 PRIME64_4 = …; /* 0b1000010111101011110010100111011111000010101100101010111001100011 */ static const U64 PRIME64_5 = …; /* 0b0010011111010100111010110010111100010110010101100110011111000101 */ static U64 XXH64_round(U64 acc, U64 input) { … } static U64 XXH64_mergeRound(U64 acc, U64 val) { … } static U64 XXH64_avalanche(U64 h64) { … } #define XXH_get64bits(p) … static U64 XXH64_finalize(U64 h64, const void* ptr, size_t len, XXH_endianess endian, XXH_alignment align) { … } FORCE_INLINE U64 XXH64_endian_align(const void* input, size_t len, U64 seed, XXH_endianess endian, XXH_alignment align) { … } XXH_PUBLIC_API unsigned long long XXH64 (const void* input, size_t len, unsigned long long seed) { … } /*====== Hash Streaming ======*/ XXH_PUBLIC_API XXH64_state_t* XXH64_createState(void) { … } XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr) { … } XXH_PUBLIC_API void XXH64_copyState(XXH64_state_t* dstState, const XXH64_state_t* srcState) { … } XXH_PUBLIC_API XXH_errorcode XXH64_reset(XXH64_state_t* statePtr, unsigned long long seed) { … } FORCE_INLINE XXH_errorcode XXH64_update_endian (XXH64_state_t* state, const void* input, size_t len, XXH_endianess endian) { … } XXH_PUBLIC_API XXH_errorcode XXH64_update (XXH64_state_t* state_in, const void* input, size_t len) { … } FORCE_INLINE U64 XXH64_digest_endian (const XXH64_state_t* state, XXH_endianess endian) { … } XXH_PUBLIC_API unsigned long long XXH64_digest (const XXH64_state_t* state_in) { … } /*====== Canonical representation ======*/ XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash) { … } XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t* src) { … } #endif /* XXH_NO_LONG_LONG */
Codebase Browser
chromium