// Copyright (c) 2011 Google, Inc. // // Permission is hereby granted, free of charge, to any person obtaining a copy // of this software and associated documentation files (the "Software"), to deal // in the Software without restriction, including without limitation the rights // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell // copies of the Software, and to permit persons to whom the Software is // furnished to do so, subject to the following conditions: // // The above copyright notice and this permission notice shall be included in // all copies or substantial portions of the Software. // // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN // THE SOFTWARE. // // CityHash, by Geoff Pike and Jyrki Alakuijala // // This file provides CityHash64() and related functions. // // It's probably possible to create even faster hash functions by // writing a program that systematically explores some of the space of // possible hash functions, by using SIMD instructions, or by // compromising on hash quality. #include "city.h" #include <string.h> // for memcpy and memset #include <algorithm> make_pair; pair; #if defined(__clang__) // Use builtins where possible. On Windows for instance, this may prevent a // function call instead of emitting a single instruction. #define bswap_32(x) … #define bswap_64(x) … #elif _MSC_VER #include <stdlib.h> #define bswap_32 … #define bswap_64 … #elif defined(__APPLE__) // Mac OS X / Darwin features #include <libkern/OSByteOrder.h> #define bswap_32 … #define bswap_64 … #elif defined(__sun) || defined(sun) #include <sys/byteorder.h> #define bswap_32 … #define bswap_64 … #elif defined(__FreeBSD__) #include <sys/endian.h> #define bswap_32 … #define bswap_64 … #elif defined(__OpenBSD__) #include <sys/types.h> #define bswap_32 … #define bswap_64 … #elif defined(__NetBSD__) #include <machine/bswap.h> #include <sys/types.h> #if defined(__BSWAP_RENAME) && !defined(__bswap_32) #define bswap_32 … #define bswap_64 … #endif #else // XXX(cavalcanti): building 'native_client' fails with this header. //#include <byteswap.h> // Falling back to compiler builtins instead. #define bswap_32 … #define bswap_64 … #endif namespace base { namespace internal { namespace cityhash_v111 { #ifdef WORDS_BIGENDIAN #define uint32_in_expected_order … #define uint64_in_expected_order … #else #define uint32_in_expected_order(x) … #define uint64_in_expected_order(x) … #endif #if !defined(LIKELY) #if HAVE_BUILTIN_EXPECT #define LIKELY … #else #define LIKELY(x) … #endif #endif static uint64 UNALIGNED_LOAD64(const char* p) { … } static uint32 UNALIGNED_LOAD32(const char* p) { … } static uint64 Fetch64(const char* p) { … } static uint32 Fetch32(const char* p) { … } // Some primes between 2^63 and 2^64 for various uses. static const uint64 k0 = …; static const uint64 k1 = …; static const uint64 k2 = …; // Magic numbers for 32-bit hashing. Copied from Murmur3. static const uint32 c1 = …; static const uint32 c2 = …; // A 32-bit to 32-bit integer hash copied from Murmur3. static uint32 fmix(uint32 h) { … } static uint32 Rotate32(uint32 val, int shift) { … } #undef PERMUTE3 #define PERMUTE3(a, b, c) … static uint32 Mur(uint32 a, uint32 h) { … } static uint32 Hash32Len13to24(const char* s, size_t len) { … } static uint32 Hash32Len0to4(const char* s, size_t len) { … } static uint32 Hash32Len5to12(const char* s, size_t len) { … } uint32 CityHash32(const char* s, size_t len) { … } // Bitwise right rotate. Normally this will compile to a single // instruction, especially if the shift is a manifest constant. static uint64 Rotate(uint64 val, int shift) { … } static uint64 ShiftMix(uint64 val) { … } static uint64 HashLen16(uint64 u, uint64 v) { … } static uint64 HashLen16(uint64 u, uint64 v, uint64 mul) { … } static uint64 HashLen0to16(const char* s, size_t len) { … } // This probably works well for 16-byte strings as well, but it may be overkill // in that case. static uint64 HashLen17to32(const char* s, size_t len) { … } // Return a 16-byte hash for 48 bytes. Quick and dirty. // Callers do best to use "random-looking" values for a and b. static pair<uint64, uint64> WeakHashLen32WithSeeds(uint64 w, uint64 x, uint64 y, uint64 z, uint64 a, uint64 b) { … } // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty. static pair<uint64, uint64> WeakHashLen32WithSeeds(const char* s, uint64 a, uint64 b) { … } // Return an 8-byte hash for 33 to 64 bytes. static uint64 HashLen33to64(const char* s, size_t len) { … } uint64 CityHash64(const char* s, size_t len) { … } uint64 CityHash64WithSeed(const char* s, size_t len, uint64 seed) { … } uint64 CityHash64WithSeeds(const char* s, size_t len, uint64 seed0, uint64 seed1) { … } // A subroutine for CityHash128(). Returns a decent 128-bit hash for strings // of any length representable in signed long. Based on City and Murmur. static uint128 CityMurmur(const char* s, size_t len, uint128 seed) { … } uint128 CityHash128WithSeed(const char* s, size_t len, uint128 seed) { … } uint128 CityHash128(const char* s, size_t len) { … } } // namespace cityhash_v111 } // namespace internal } // namespace base
Codebase Browser
chromium