city_v103.cc | Explore in Territory

// 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 "base/third_party/cityhash_v103/src/city_v103.h"

#include <string.h>  // for memcpy and memset
#include <algorithm>

#include "build/build_config.h"

namespace base {
namespace internal {
namespace cityhash_v103 {

static uint64 UNALIGNED_LOAD64(const char* p) { … }

static uint32 UNALIGNED_LOAD32(const char* p) { … }

#if defined(ARCH_CPU_LITTLE_ENDIAN)

#define uint32_in_expected_order(x) …
#define uint64_in_expected_order(x) …

#else

#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 …
#define bswap_64 …

#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 …

#else
#include <byteswap.h>
#endif

#define uint32_in_expected_order …
#define uint64_in_expected_order …

#endif  // defined(ARCH_CPU_LITTLE_ENDIAN)

#if !defined(LIKELY)
#if HAVE_BUILTIN_EXPECT
#define LIKELY …
#else
#define LIKELY(x) …
#endif
#endif

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 = …;
static const uint64 k3 = …;

// 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) { … }

// Equivalent to Rotate(), but requires the second arg to be non-zero.
// On x86-64, and probably others, it's possible for this to compile
// to a single instruction if both args are already in registers.
static uint64 RotateByAtLeast1(uint64 val, size_t shift) { … }

static uint64 ShiftMix(uint64 val) { … }

static uint64 HashLen16(uint64 u, uint64 v) { … }

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 std::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 std::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_v103
}  // namespace internal
}  // namespace base
chromium/base/third_party/cityhash_v103/src/city_v103.cc
