city.cc | Explore in Territory

// Copyright 2018 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// 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 "absl/hash/internal/city.h"

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

#include "absl/base/config.h"
#include "absl/base/internal/endian.h"
#include "absl/base/internal/unaligned_access.h"
#include "absl/base/optimization.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace hash_internal {

#ifdef ABSL_IS_BIG_ENDIAN
#define uint32_in_expected_order …
#define uint64_in_expected_order …
#else
#define uint32_in_expected_order(x) …
#define uint64_in_expected_order(x) …
#endif

static uint64_t Fetch64(const char *p) { … }

static uint32_t Fetch32(const char *p) { … }

// Some primes between 2^63 and 2^64 for various uses.
static const uint64_t k0 = …;
static const uint64_t k1 = …;
static const uint64_t k2 = …;

// Magic numbers for 32-bit hashing.  Copied from Murmur3.
static const uint32_t c1 = …;
static const uint32_t c2 = …;

// A 32-bit to 32-bit integer hash copied from Murmur3.
static uint32_t fmix(uint32_t h) { … }

static uint32_t Rotate32(uint32_t val, int shift) { … }

#undef PERMUTE3
#define PERMUTE3(a, b, c) …

static uint32_t Mur(uint32_t a, uint32_t h) { … }

static uint32_t Hash32Len13to24(const char *s, size_t len) { … }

static uint32_t Hash32Len0to4(const char *s, size_t len) { … }

static uint32_t Hash32Len5to12(const char *s, size_t len) { … }

uint32_t 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_t Rotate(uint64_t val, int shift) { … }

static uint64_t ShiftMix(uint64_t val) { … }

static uint64_t HashLen16(uint64_t u, uint64_t v, uint64_t mul) { … }

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

static uint64_t 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_t 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_t, uint64_t> WeakHashLen32WithSeeds(
    uint64_t w, uint64_t x, uint64_t y, uint64_t z, uint64_t a, uint64_t b) { … }

// Return a 16-byte hash for s[0] ... s[31], a, and b.  Quick and dirty.
static std::pair<uint64_t, uint64_t> WeakHashLen32WithSeeds(const char *s,
                                                            uint64_t a,
                                                            uint64_t b) { … }

// Return an 8-byte hash for 33 to 64 bytes.
static uint64_t HashLen33to64(const char *s, size_t len) { … }

uint64_t CityHash64(const char *s, size_t len) { … }

uint64_t CityHash64WithSeed(const char *s, size_t len, uint64_t seed) { … }

uint64_t CityHash64WithSeeds(const char *s, size_t len, uint64_t seed0,
                             uint64_t seed1) { … }

}  // namespace hash_internal
ABSL_NAMESPACE_END
}  // namespace absl
chromium/third_party/abseil-cpp/absl/hash/internal/city.cc
