diff options
author | prime <prime@yandex-team.ru> | 2022-02-10 16:46:00 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:46:00 +0300 |
commit | 3695a7cd42b74a4987d8d5a8f2e2443556998943 (patch) | |
tree | ee79ee9294a61ee00e647684b3700d0a87e102a3 /contrib/restricted/abseil-cpp/absl/hash/internal | |
parent | 4d8b546b89b5afc08cf3667e176271c7ba935f33 (diff) | |
download | ydb-3695a7cd42b74a4987d8d5a8f2e2443556998943.tar.gz |
Restoring authorship annotation for <prime@yandex-team.ru>. Commit 1 of 2.
Diffstat (limited to 'contrib/restricted/abseil-cpp/absl/hash/internal')
5 files changed, 210 insertions, 210 deletions
diff --git a/contrib/restricted/abseil-cpp/absl/hash/internal/city.cc b/contrib/restricted/abseil-cpp/absl/hash/internal/city.cc index 5460134e57..01bd850482 100644 --- a/contrib/restricted/abseil-cpp/absl/hash/internal/city.cc +++ b/contrib/restricted/abseil-cpp/absl/hash/internal/city.cc @@ -210,11 +210,11 @@ static uint64_t HashLen16(uint64_t u, uint64_t v, uint64_t mul) { return b; } -static uint64_t HashLen16(uint64_t u, uint64_t v) { - const uint64_t kMul = 0x9ddfea08eb382d69ULL; - return HashLen16(u, v, kMul); -} - +static uint64_t HashLen16(uint64_t u, uint64_t v) { + const uint64_t kMul = 0x9ddfea08eb382d69ULL; + return HashLen16(u, v, kMul); +} + static uint64_t HashLen0to16(const char *s, size_t len) { if (len >= 8) { uint64_t mul = k2 + len * 2; diff --git a/contrib/restricted/abseil-cpp/absl/hash/internal/hash.cc b/contrib/restricted/abseil-cpp/absl/hash/internal/hash.cc index 11451e575c..f8cb56df18 100644 --- a/contrib/restricted/abseil-cpp/absl/hash/internal/hash.cc +++ b/contrib/restricted/abseil-cpp/absl/hash/internal/hash.cc @@ -35,7 +35,7 @@ uint64_t MixingHashState::CombineLargeContiguousImpl32( uint64_t MixingHashState::CombineLargeContiguousImpl64( uint64_t state, const unsigned char* first, size_t len) { while (len >= PiecewiseChunkSize()) { - state = Mix(state, Hash64(first, PiecewiseChunkSize())); + state = Mix(state, Hash64(first, PiecewiseChunkSize())); len -= PiecewiseChunkSize(); first += PiecewiseChunkSize(); } @@ -49,21 +49,21 @@ ABSL_CONST_INIT const void* const MixingHashState::kSeed = &kSeed; // The salt array used by LowLevelHash. This array is NOT the mechanism used to // make absl::Hash non-deterministic between program invocations. See `Seed()` // for that mechanism. -// -// Any random values are fine. These values are just digits from the decimal -// part of pi. -// https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number +// +// Any random values are fine. These values are just digits from the decimal +// part of pi. +// https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number constexpr uint64_t kHashSalt[5] = { - uint64_t{0x243F6A8885A308D3}, uint64_t{0x13198A2E03707344}, - uint64_t{0xA4093822299F31D0}, uint64_t{0x082EFA98EC4E6C89}, - uint64_t{0x452821E638D01377}, -}; - + uint64_t{0x243F6A8885A308D3}, uint64_t{0x13198A2E03707344}, + uint64_t{0xA4093822299F31D0}, uint64_t{0x082EFA98EC4E6C89}, + uint64_t{0x452821E638D01377}, +}; + uint64_t MixingHashState::LowLevelHashImpl(const unsigned char* data, size_t len) { return LowLevelHash(data, len, Seed(), kHashSalt); -} - +} + } // namespace hash_internal ABSL_NAMESPACE_END } // namespace absl diff --git a/contrib/restricted/abseil-cpp/absl/hash/internal/hash.h b/contrib/restricted/abseil-cpp/absl/hash/internal/hash.h index b1e33caf4c..f6c4a148b8 100644 --- a/contrib/restricted/abseil-cpp/absl/hash/internal/hash.h +++ b/contrib/restricted/abseil-cpp/absl/hash/internal/hash.h @@ -39,8 +39,8 @@ #include <utility> #include <vector> -#include "absl/base/config.h" -#include "absl/base/internal/unaligned_access.h" +#include "absl/base/config.h" +#include "absl/base/internal/unaligned_access.h" #include "absl/base/port.h" #include "absl/container/fixed_array.h" #include "absl/hash/internal/city.h" @@ -834,7 +834,7 @@ class ABSL_DLL MixingHashState : public HashStateBase<MixingHashState> { static uint64_t CombineContiguousImpl(uint64_t state, const unsigned char* first, size_t len, std::integral_constant<int, 8> - /* sizeof_size_t */); + /* sizeof_size_t */); // Slow dispatch path for calls to CombineContiguousImpl with a size argument // larger than PiecewiseChunkSize(). Has the same effect as calling @@ -847,54 +847,54 @@ class ABSL_DLL MixingHashState : public HashStateBase<MixingHashState> { size_t len); // Reads 9 to 16 bytes from p. - // The least significant 8 bytes are in .first, the rest (zero padded) bytes - // are in .second. + // The least significant 8 bytes are in .first, the rest (zero padded) bytes + // are in .second. static std::pair<uint64_t, uint64_t> Read9To16(const unsigned char* p, size_t len) { - uint64_t low_mem = absl::base_internal::UnalignedLoad64(p); - uint64_t high_mem = absl::base_internal::UnalignedLoad64(p + len - 8); -#ifdef ABSL_IS_LITTLE_ENDIAN - uint64_t most_significant = high_mem; - uint64_t least_significant = low_mem; -#else - uint64_t most_significant = low_mem; - uint64_t least_significant = high_mem; -#endif - return {least_significant, most_significant >> (128 - len * 8)}; + uint64_t low_mem = absl::base_internal::UnalignedLoad64(p); + uint64_t high_mem = absl::base_internal::UnalignedLoad64(p + len - 8); +#ifdef ABSL_IS_LITTLE_ENDIAN + uint64_t most_significant = high_mem; + uint64_t least_significant = low_mem; +#else + uint64_t most_significant = low_mem; + uint64_t least_significant = high_mem; +#endif + return {least_significant, most_significant >> (128 - len * 8)}; } // Reads 4 to 8 bytes from p. Zero pads to fill uint64_t. static uint64_t Read4To8(const unsigned char* p, size_t len) { - uint32_t low_mem = absl::base_internal::UnalignedLoad32(p); - uint32_t high_mem = absl::base_internal::UnalignedLoad32(p + len - 4); -#ifdef ABSL_IS_LITTLE_ENDIAN - uint32_t most_significant = high_mem; - uint32_t least_significant = low_mem; -#else - uint32_t most_significant = low_mem; - uint32_t least_significant = high_mem; -#endif - return (static_cast<uint64_t>(most_significant) << (len - 4) * 8) | - least_significant; + uint32_t low_mem = absl::base_internal::UnalignedLoad32(p); + uint32_t high_mem = absl::base_internal::UnalignedLoad32(p + len - 4); +#ifdef ABSL_IS_LITTLE_ENDIAN + uint32_t most_significant = high_mem; + uint32_t least_significant = low_mem; +#else + uint32_t most_significant = low_mem; + uint32_t least_significant = high_mem; +#endif + return (static_cast<uint64_t>(most_significant) << (len - 4) * 8) | + least_significant; } // Reads 1 to 3 bytes from p. Zero pads to fill uint32_t. static uint32_t Read1To3(const unsigned char* p, size_t len) { - unsigned char mem0 = p[0]; - unsigned char mem1 = p[len / 2]; - unsigned char mem2 = p[len - 1]; -#ifdef ABSL_IS_LITTLE_ENDIAN - unsigned char significant2 = mem2; - unsigned char significant1 = mem1; - unsigned char significant0 = mem0; -#else - unsigned char significant2 = mem0; - unsigned char significant1 = mem1; - unsigned char significant0 = mem2; -#endif - return static_cast<uint32_t>(significant0 | // - (significant1 << (len / 2 * 8)) | // - (significant2 << ((len - 1) * 8))); + unsigned char mem0 = p[0]; + unsigned char mem1 = p[len / 2]; + unsigned char mem2 = p[len - 1]; +#ifdef ABSL_IS_LITTLE_ENDIAN + unsigned char significant2 = mem2; + unsigned char significant1 = mem1; + unsigned char significant0 = mem0; +#else + unsigned char significant2 = mem0; + unsigned char significant1 = mem1; + unsigned char significant0 = mem2; +#endif + return static_cast<uint32_t>(significant0 | // + (significant1 << (len / 2 * 8)) | // + (significant2 << ((len - 1) * 8))); } ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Mix(uint64_t state, uint64_t v) { @@ -919,16 +919,16 @@ class ABSL_DLL MixingHashState : public HashStateBase<MixingHashState> { // An extern to avoid bloat on a direct call to LowLevelHash() with fixed // values for both the seed and salt parameters. static uint64_t LowLevelHashImpl(const unsigned char* data, size_t len); - - ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Hash64(const unsigned char* data, - size_t len) { -#ifdef ABSL_HAVE_INTRINSIC_INT128 + + ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Hash64(const unsigned char* data, + size_t len) { +#ifdef ABSL_HAVE_INTRINSIC_INT128 return LowLevelHashImpl(data, len); -#else +#else return hash_internal::CityHash64(reinterpret_cast<const char*>(data), len); -#endif - } - +#endif + } + // Seed() // // A non-deterministic seed. @@ -946,14 +946,14 @@ class ABSL_DLL MixingHashState : public HashStateBase<MixingHashState> { // On other platforms this is still going to be non-deterministic but most // probably per-build and not per-process. ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Seed() { -#if (!defined(__clang__) || __clang_major__ > 11) && \ - !defined(__apple_build_version__) - return static_cast<uint64_t>(reinterpret_cast<uintptr_t>(&kSeed)); -#else - // Workaround the absence of - // https://github.com/llvm/llvm-project/commit/bc15bf66dcca76cc06fe71fca35b74dc4d521021. +#if (!defined(__clang__) || __clang_major__ > 11) && \ + !defined(__apple_build_version__) + return static_cast<uint64_t>(reinterpret_cast<uintptr_t>(&kSeed)); +#else + // Workaround the absence of + // https://github.com/llvm/llvm-project/commit/bc15bf66dcca76cc06fe71fca35b74dc4d521021. return static_cast<uint64_t>(reinterpret_cast<uintptr_t>(kSeed)); -#endif +#endif } static const void* const kSeed; @@ -994,7 +994,7 @@ inline uint64_t MixingHashState::CombineContiguousImpl( if (ABSL_PREDICT_FALSE(len > PiecewiseChunkSize())) { return CombineLargeContiguousImpl64(state, first, len); } - v = Hash64(first, len); + v = Hash64(first, len); } else if (len > 8) { auto p = Read9To16(first, len); state = Mix(state, p.first); diff --git a/contrib/restricted/abseil-cpp/absl/hash/internal/low_level_hash.cc b/contrib/restricted/abseil-cpp/absl/hash/internal/low_level_hash.cc index 6f9cb9c7bf..865f5901c8 100644 --- a/contrib/restricted/abseil-cpp/absl/hash/internal/low_level_hash.cc +++ b/contrib/restricted/abseil-cpp/absl/hash/internal/low_level_hash.cc @@ -1,33 +1,33 @@ -// Copyright 2020 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. - +// Copyright 2020 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. + #include "absl/hash/internal/low_level_hash.h" - -#include "absl/base/internal/unaligned_access.h" + +#include "absl/base/internal/unaligned_access.h" #include "absl/numeric/bits.h" -#include "absl/numeric/int128.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace hash_internal { - +#include "absl/numeric/int128.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace hash_internal { + static uint64_t Mix(uint64_t v0, uint64_t v1) { #if !defined(__aarch64__) // The default bit-mixer uses 64x64->128-bit multiplication. - absl::uint128 p = v0; - p *= v1; - return absl::Uint128Low64(p) ^ absl::Uint128High64(p); + absl::uint128 p = v0; + p *= v1; + return absl::Uint128Low64(p) ^ absl::Uint128High64(p); #else // The default bit-mixer above would perform poorly on some ARM microarchs, // where calculating a 128-bit product requires a sequence of two @@ -37,87 +37,87 @@ static uint64_t Mix(uint64_t v0, uint64_t v1) { p *= v1 ^ absl::rotl(v0, 39); return p ^ (p >> 11); #endif -} - +} + uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed, const uint64_t salt[]) { - const uint8_t* ptr = static_cast<const uint8_t*>(data); - uint64_t starting_length = static_cast<uint64_t>(len); - uint64_t current_state = seed ^ salt[0]; - - if (len > 64) { - // If we have more than 64 bytes, we're going to handle chunks of 64 - // bytes at a time. We're going to build up two separate hash states - // which we will then hash together. - uint64_t duplicated_state = current_state; - - do { - uint64_t a = absl::base_internal::UnalignedLoad64(ptr); - uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); - uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16); - uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24); - uint64_t e = absl::base_internal::UnalignedLoad64(ptr + 32); - uint64_t f = absl::base_internal::UnalignedLoad64(ptr + 40); - uint64_t g = absl::base_internal::UnalignedLoad64(ptr + 48); - uint64_t h = absl::base_internal::UnalignedLoad64(ptr + 56); - + const uint8_t* ptr = static_cast<const uint8_t*>(data); + uint64_t starting_length = static_cast<uint64_t>(len); + uint64_t current_state = seed ^ salt[0]; + + if (len > 64) { + // If we have more than 64 bytes, we're going to handle chunks of 64 + // bytes at a time. We're going to build up two separate hash states + // which we will then hash together. + uint64_t duplicated_state = current_state; + + do { + uint64_t a = absl::base_internal::UnalignedLoad64(ptr); + uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); + uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16); + uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24); + uint64_t e = absl::base_internal::UnalignedLoad64(ptr + 32); + uint64_t f = absl::base_internal::UnalignedLoad64(ptr + 40); + uint64_t g = absl::base_internal::UnalignedLoad64(ptr + 48); + uint64_t h = absl::base_internal::UnalignedLoad64(ptr + 56); + uint64_t cs0 = Mix(a ^ salt[1], b ^ current_state); uint64_t cs1 = Mix(c ^ salt[2], d ^ current_state); - current_state = (cs0 ^ cs1); - + current_state = (cs0 ^ cs1); + uint64_t ds0 = Mix(e ^ salt[3], f ^ duplicated_state); uint64_t ds1 = Mix(g ^ salt[4], h ^ duplicated_state); - duplicated_state = (ds0 ^ ds1); - - ptr += 64; - len -= 64; - } while (len > 64); - - current_state = current_state ^ duplicated_state; - } - - // We now have a data `ptr` with at most 64 bytes and the current state - // of the hashing state machine stored in current_state. - while (len > 16) { - uint64_t a = absl::base_internal::UnalignedLoad64(ptr); - uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); - + duplicated_state = (ds0 ^ ds1); + + ptr += 64; + len -= 64; + } while (len > 64); + + current_state = current_state ^ duplicated_state; + } + + // We now have a data `ptr` with at most 64 bytes and the current state + // of the hashing state machine stored in current_state. + while (len > 16) { + uint64_t a = absl::base_internal::UnalignedLoad64(ptr); + uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); + current_state = Mix(a ^ salt[1], b ^ current_state); - - ptr += 16; - len -= 16; - } - - // We now have a data `ptr` with at most 16 bytes. - uint64_t a = 0; - uint64_t b = 0; - if (len > 8) { - // When we have at least 9 and at most 16 bytes, set A to the first 64 - // bits of the input and B to the last 64 bits of the input. Yes, they will - // overlap in the middle if we are working with less than the full 16 - // bytes. - a = absl::base_internal::UnalignedLoad64(ptr); - b = absl::base_internal::UnalignedLoad64(ptr + len - 8); - } else if (len > 3) { - // If we have at least 4 and at most 8 bytes, set A to the first 32 - // bits and B to the last 32 bits. - a = absl::base_internal::UnalignedLoad32(ptr); - b = absl::base_internal::UnalignedLoad32(ptr + len - 4); - } else if (len > 0) { - // If we have at least 1 and at most 3 bytes, read all of the provided - // bits into A, with some adjustments. - a = ((ptr[0] << 16) | (ptr[len >> 1] << 8) | ptr[len - 1]); - b = 0; - } else { - a = 0; - b = 0; - } - + + ptr += 16; + len -= 16; + } + + // We now have a data `ptr` with at most 16 bytes. + uint64_t a = 0; + uint64_t b = 0; + if (len > 8) { + // When we have at least 9 and at most 16 bytes, set A to the first 64 + // bits of the input and B to the last 64 bits of the input. Yes, they will + // overlap in the middle if we are working with less than the full 16 + // bytes. + a = absl::base_internal::UnalignedLoad64(ptr); + b = absl::base_internal::UnalignedLoad64(ptr + len - 8); + } else if (len > 3) { + // If we have at least 4 and at most 8 bytes, set A to the first 32 + // bits and B to the last 32 bits. + a = absl::base_internal::UnalignedLoad32(ptr); + b = absl::base_internal::UnalignedLoad32(ptr + len - 4); + } else if (len > 0) { + // If we have at least 1 and at most 3 bytes, read all of the provided + // bits into A, with some adjustments. + a = ((ptr[0] << 16) | (ptr[len >> 1] << 8) | ptr[len - 1]); + b = 0; + } else { + a = 0; + b = 0; + } + uint64_t w = Mix(a ^ salt[1], b ^ current_state); - uint64_t z = salt[1] ^ starting_length; + uint64_t z = salt[1] ^ starting_length; return Mix(w, z); -} - -} // namespace hash_internal -ABSL_NAMESPACE_END -} // namespace absl +} + +} // namespace hash_internal +ABSL_NAMESPACE_END +} // namespace absl diff --git a/contrib/restricted/abseil-cpp/absl/hash/internal/low_level_hash.h b/contrib/restricted/abseil-cpp/absl/hash/internal/low_level_hash.h index 439968aa98..3409f41b61 100644 --- a/contrib/restricted/abseil-cpp/absl/hash/internal/low_level_hash.h +++ b/contrib/restricted/abseil-cpp/absl/hash/internal/low_level_hash.h @@ -1,19 +1,19 @@ -// Copyright 2020 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. -// +// Copyright 2020 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 the Google-internal implementation of LowLevelHash. -// +// // LowLevelHash is a fast hash function for hash tables, the fastest we've // currently (late 2020) found that passes the SMHasher tests. The algorithm // relies on intrinsic 128-bit multiplication for speed. This is not meant to be @@ -21,30 +21,30 @@ // // It is closely based on a version of wyhash, but does not maintain or // guarantee future compatibility with it. - + #ifndef ABSL_HASH_INTERNAL_LOW_LEVEL_HASH_H_ #define ABSL_HASH_INTERNAL_LOW_LEVEL_HASH_H_ - -#include <stdint.h> -#include <stdlib.h> - -#include "absl/base/config.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace hash_internal { - -// Hash function for a byte array. A 64-bit seed and a set of five 64-bit -// integers are hashed into the result. -// -// To allow all hashable types (including string_view and Span) to depend on + +#include <stdint.h> +#include <stdlib.h> + +#include "absl/base/config.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace hash_internal { + +// Hash function for a byte array. A 64-bit seed and a set of five 64-bit +// integers are hashed into the result. +// +// To allow all hashable types (including string_view and Span) to depend on // this algorithm, we keep the API low-level, with as few dependencies as -// possible. +// possible. uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed, const uint64_t salt[5]); - -} // namespace hash_internal -ABSL_NAMESPACE_END -} // namespace absl - + +} // namespace hash_internal +ABSL_NAMESPACE_END +} // namespace absl + #endif // ABSL_HASH_INTERNAL_LOW_LEVEL_HASH_H_ |