diff options
Diffstat (limited to 'absl')
| -rw-r--r-- | absl/base/log_severity_test.cc | 6 | ||||
| -rw-r--r-- | absl/container/internal/raw_hash_set.cc | 2 | ||||
| -rw-r--r-- | absl/container/internal/raw_hash_set.h | 6 | ||||
| -rw-r--r-- | absl/debugging/BUILD.bazel | 1 | ||||
| -rw-r--r-- | absl/debugging/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | absl/debugging/internal/stacktrace_config.h | 3 | ||||
| -rw-r--r-- | absl/debugging/internal/stacktrace_riscv-inl.inc | 234 | ||||
| -rw-r--r-- | absl/debugging/stacktrace.cc | 1 | ||||
| -rw-r--r-- | absl/flags/flag_test.cc | 37 | ||||
| -rw-r--r-- | absl/flags/internal/flag.cc | 91 | ||||
| -rw-r--r-- | absl/flags/internal/flag.h | 71 | ||||
| -rw-r--r-- | absl/hash/BUILD.bazel | 1 | ||||
| -rw-r--r-- | absl/hash/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | absl/hash/internal/low_level_hash.cc | 12 | ||||
| -rw-r--r-- | absl/hash/internal/low_level_hash_test.cc | 484 | ||||
| -rw-r--r-- | absl/numeric/int128.h | 128 | ||||
| -rw-r--r-- | absl/numeric/int128_have_intrinsic.inc | 44 | ||||
| -rw-r--r-- | absl/numeric/int128_no_intrinsic.inc | 133 |
18 files changed, 840 insertions, 416 deletions
diff --git a/absl/base/log_severity_test.cc b/absl/base/log_severity_test.cc index 2c6872b0..55b26d17 100644 --- a/absl/base/log_severity_test.cc +++ b/absl/base/log_severity_test.cc @@ -52,9 +52,9 @@ TEST(StreamTest, Works) { Eq("absl::LogSeverity(4)")); } -static_assert( - absl::flags_internal::FlagUseOneWordStorage<absl::LogSeverity>::value, - "Flags of type absl::LogSeverity ought to be lock-free."); +static_assert(absl::flags_internal::FlagUseValueAndInitBitStorage< + absl::LogSeverity>::value, + "Flags of type absl::LogSeverity ought to be lock-free."); using ParseFlagFromOutOfRangeIntegerTest = TestWithParam<int64_t>; INSTANTIATE_TEST_SUITE_P( diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 3c72c41a..687bcb8a 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc @@ -59,6 +59,8 @@ void ConvertDeletedToEmptyAndFullToDeleted(ctrl_t* ctrl, size_t capacity) { std::memcpy(ctrl + capacity + 1, ctrl, NumClonedBytes()); ctrl[capacity] = ctrl_t::kSentinel; } +// Extern template instantiotion for inline function. +template FindInfo find_first_non_full(const ctrl_t*, size_t, size_t); } // namespace container_internal ABSL_NAMESPACE_END diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index ade2f584..18b1f5a4 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -570,6 +570,7 @@ inline probe_seq<Group::kWidth> probe(const ctrl_t* ctrl, size_t hash, // - the input is already a set // - there are enough slots // - the element with the hash is not in the table +template <typename = void> inline FindInfo find_first_non_full(const ctrl_t* ctrl, size_t hash, size_t capacity) { auto seq = probe(ctrl, hash, capacity); @@ -593,6 +594,11 @@ inline FindInfo find_first_non_full(const ctrl_t* ctrl, size_t hash, } } +// Extern template for inline function keep possibility of inlining. +// When compiler decided to not inline, no symbols will be added to the +// corresponding translation unit. +extern template FindInfo find_first_non_full(const ctrl_t*, size_t, size_t); + // Reset all ctrl bytes back to ctrl_t::kEmpty, except the sentinel. inline void ResetCtrl(size_t capacity, ctrl_t* ctrl, const void* slot, size_t slot_size) { diff --git a/absl/debugging/BUILD.bazel b/absl/debugging/BUILD.bazel index a8c51a5c..b536a044 100644 --- a/absl/debugging/BUILD.bazel +++ b/absl/debugging/BUILD.bazel @@ -37,6 +37,7 @@ cc_library( "internal/stacktrace_emscripten-inl.inc", "internal/stacktrace_generic-inl.inc", "internal/stacktrace_powerpc-inl.inc", + "internal/stacktrace_riscv-inl.inc", "internal/stacktrace_unimplemented-inl.inc", "internal/stacktrace_win32-inl.inc", "internal/stacktrace_x86-inl.inc", diff --git a/absl/debugging/CMakeLists.txt b/absl/debugging/CMakeLists.txt index 760772f3..b16fa007 100644 --- a/absl/debugging/CMakeLists.txt +++ b/absl/debugging/CMakeLists.txt @@ -25,6 +25,7 @@ absl_cc_library( "internal/stacktrace_emscripten-inl.inc" "internal/stacktrace_generic-inl.inc" "internal/stacktrace_powerpc-inl.inc" + "internal/stacktrace_riscv-inl.inc" "internal/stacktrace_unimplemented-inl.inc" "internal/stacktrace_win32-inl.inc" "internal/stacktrace_x86-inl.inc" diff --git a/absl/debugging/internal/stacktrace_config.h b/absl/debugging/internal/stacktrace_config.h index 6cceef26..29b26bdd 100644 --- a/absl/debugging/internal/stacktrace_config.h +++ b/absl/debugging/internal/stacktrace_config.h @@ -65,6 +65,9 @@ #elif defined(__aarch64__) #define ABSL_STACKTRACE_INL_HEADER \ "absl/debugging/internal/stacktrace_aarch64-inl.inc" +#elif defined(__riscv) +#define ABSL_STACKTRACE_INL_HEADER \ + "absl/debugging/internal/stacktrace_riscv-inl.inc" #elif defined(__has_include) #if __has_include(<execinfo.h>) // Note: When using glibc this may require -funwind-tables to function properly. diff --git a/absl/debugging/internal/stacktrace_riscv-inl.inc b/absl/debugging/internal/stacktrace_riscv-inl.inc new file mode 100644 index 00000000..8cbc7854 --- /dev/null +++ b/absl/debugging/internal/stacktrace_riscv-inl.inc @@ -0,0 +1,234 @@ +// Copyright 2021 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. + +#ifndef ABSL_DEBUGGING_INTERNAL_STACKTRACE_RISCV_INL_H_ +#define ABSL_DEBUGGING_INTERNAL_STACKTRACE_RISCV_INL_H_ + +// Generate stack trace for riscv + +#include <sys/ucontext.h> + +#include "absl/base/config.h" +#if defined(__linux__) +#include <sys/mman.h> +#include <ucontext.h> +#include <unistd.h> +#endif + +#include <atomic> +#include <cassert> +#include <cstdint> +#include <iostream> + +#include "absl/base/attributes.h" +#include "absl/debugging/internal/address_is_readable.h" +#include "absl/debugging/internal/vdso_support.h" +#include "absl/debugging/stacktrace.h" + +static const uintptr_t kUnknownFrameSize = 0; + +#if defined(__linux__) +// Returns the address of the VDSO __kernel_rt_sigreturn function, if present. +static const unsigned char *GetKernelRtSigreturnAddress() { + constexpr uintptr_t kImpossibleAddress = 0; + ABSL_CONST_INIT static std::atomic<uintptr_t> memoized(kImpossibleAddress); + uintptr_t address = memoized.load(std::memory_order_relaxed); + if (address != kImpossibleAddress) { + return reinterpret_cast<const unsigned char *>(address); + } + + address = reinterpret_cast<uintptr_t>(nullptr); + +#if ABSL_HAVE_VDSO_SUPPORT + absl::debugging_internal::VDSOSupport vdso; + if (vdso.IsPresent()) { + absl::debugging_internal::VDSOSupport::SymbolInfo symbol_info; + // Symbol versioning pulled from arch/riscv/kernel/vdso/vdso.lds at v5.10. + auto lookup = [&](int type) { + return vdso.LookupSymbol("__kernel_rt_sigreturn", "LINUX_4.15", type, + &symbol_info); + }; + if ((!lookup(STT_FUNC) && !lookup(STT_NOTYPE)) || + symbol_info.address == nullptr) { + // Unexpected: VDSO is present, yet the expected symbol is missing or + // null. + assert(false && "VDSO is present, but doesn't have expected symbol"); + } else { + if (reinterpret_cast<uintptr_t>(symbol_info.address) != + kImpossibleAddress) { + address = reinterpret_cast<uintptr_t>(symbol_info.address); + } else { + assert(false && "VDSO returned invalid address"); + } + } + } +#endif + + memoized.store(address, std::memory_order_relaxed); + return reinterpret_cast<const unsigned char *>(address); +} +#endif // __linux__ + +// Compute the size of a stack frame in [low..high). We assume that low < high. +// Return size of kUnknownFrameSize. +template <typename T> +static inline uintptr_t ComputeStackFrameSize(const T *low, const T *high) { + const char *low_char_ptr = reinterpret_cast<const char *>(low); + const char *high_char_ptr = reinterpret_cast<const char *>(high); + return low < high ? high_char_ptr - low_char_ptr : kUnknownFrameSize; +} + +// Given a pointer to a stack frame, locate and return the calling stackframe, +// or return null if no stackframe can be found. Perform sanity checks (the +// strictness of which is controlled by the boolean parameter +// "STRICT_UNWINDING") to reduce the chance that a bad pointer is returned. +template <bool STRICT_UNWINDING, bool WITH_CONTEXT> +ABSL_ATTRIBUTE_NO_SANITIZE_ADDRESS // May read random elements from stack. +ABSL_ATTRIBUTE_NO_SANITIZE_MEMORY // May read random elements from stack. +static void ** NextStackFrame(void **old_frame_pointer, const void *uc) { + // . + // . + // . + // +-> +----------------+ + // | | return address | + // | | previous fp | + // | | ... | + // | +----------------+ <-+ + // | | return address | | + // +---|- previous fp | | + // | ... | | + // $fp ->|----------------+ | + // | return address | | + // | previous fp -|---+ + // $sp ->| ... | + // +----------------+ + void **new_frame_pointer = reinterpret_cast<void **>(old_frame_pointer[-2]); + bool check_frame_size = true; + +#if defined(__linux__) + if (WITH_CONTEXT && uc != nullptr) { + // Check to see if next frame's return address is __kernel_rt_sigreturn. + if (old_frame_pointer[-1] == GetKernelRtSigreturnAddress()) { + const ucontext_t *ucv = static_cast<const ucontext_t *>(uc); + // old_frame_pointer is not suitable for unwinding, look at ucontext to + // discover frame pointer before signal. + // + // RISCV ELF psABI has the frame pointer at x8/fp/s0. + // -- RISCV psABI Table 18.2 + void **const pre_signal_frame_pointer = + reinterpret_cast<void **>(ucv->uc_mcontext.__gregs[8]); + + // Check the alleged frame pointer is actually readable. This is to + // prevent "double fault" in case we hit the first fault due to stack + // corruption. + if (!absl::debugging_internal::AddressIsReadable( + pre_signal_frame_pointer)) + return nullptr; + + // Alleged frame pointer is readable, use it for further unwinding. + new_frame_pointer = pre_signal_frame_pointer; + + // Skip frame size check if we return from a signal. We may be using an + // alterate stack for signals. + check_frame_size = false; + } + } +#endif + + // The RISCV ELF psABI mandates that the stack pointer is always 16-byte + // aligned. + // FIXME(abdulras) this doesn't hold for ILP32E which only mandates a 4-byte + // alignment. + if ((reinterpret_cast<uintptr_t>(new_frame_pointer) & 15) != 0) + return nullptr; + + // Check frame size. In strict mode, we assume frames to be under 100,000 + // bytes. In non-strict mode, we relax the limit to 1MB. + if (check_frame_size) { + const uintptr_t max_size = STRICT_UNWINDING ? 100000 : 1000000; + const uintptr_t frame_size = + ComputeStackFrameSize(old_frame_pointer, new_frame_pointer); + if (frame_size == kUnknownFrameSize || frame_size > max_size) + return nullptr; + } + + return new_frame_pointer; +} + +template <bool IS_STACK_FRAMES, bool IS_WITH_CONTEXT> +ABSL_ATTRIBUTE_NO_SANITIZE_ADDRESS // May read random elements from stack. +ABSL_ATTRIBUTE_NO_SANITIZE_MEMORY // May read random elements from stack. +static int UnwindImpl(void **result, int *sizes, int max_depth, int skip_count, + const void *ucp, int *min_dropped_frames) { +#if defined(__GNUC__) + void **frame_pointer = reinterpret_cast<void **>(__builtin_frame_address(0)); +#else +#error reading stack pointer not yet supported on this platform +#endif + + skip_count++; // Skip the frame for this function. + int n = 0; + + // The `frame_pointer` that is computed here points to the top of the frame. + // The two words preceding the address are the return address and the previous + // frame pointer. To find a PC value associated with the current frame, we + // need to go down a level in the call chain. So we remember the return + // address of the last frame seen. This does not work for the first stack + // frame, which belongs to `UnwindImp()` but we skip the frame for + // `UnwindImp()` anyway. + void *prev_return_address = nullptr; + + while (frame_pointer && n < max_depth) { + // The absl::GetStackFrames routine si called when we are in some + // informational context (the failure signal handler for example). Use the + // non-strict unwinding rules to produce a stack trace that is as complete + // as possible (even if it contains a few bogus entries in some rare cases). + void **next_frame_pointer = + NextStackFrame<!IS_STACK_FRAMES, IS_WITH_CONTEXT>(frame_pointer, ucp); + + if (skip_count > 0) { + skip_count--; + } else { + result[n] = prev_return_address; + if (IS_STACK_FRAMES) { + sizes[n] = ComputeStackFrameSize(frame_pointer, next_frame_pointer); + } + n++; + } + prev_return_address = frame_pointer[-1]; + frame_pointer = next_frame_pointer; + } + if (min_dropped_frames != nullptr) { + // Implementation detail: we clamp the max of frames we are willing to + // count, so as not to spend too much time in the loop below. + const int kMaxUnwind = 200; + int j = 0; + for (; frame_pointer != nullptr && j < kMaxUnwind; j++) { + frame_pointer = + NextStackFrame<!IS_STACK_FRAMES, IS_WITH_CONTEXT>(frame_pointer, ucp); + } + *min_dropped_frames = j; + } + return n; +} + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace debugging_internal { +bool StackTraceWorksForTest() { return true; } +} // namespace debugging_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif diff --git a/absl/debugging/stacktrace.cc b/absl/debugging/stacktrace.cc index 5358b942..ff8069f8 100644 --- a/absl/debugging/stacktrace.cc +++ b/absl/debugging/stacktrace.cc @@ -52,6 +52,7 @@ # include "absl/debugging/internal/stacktrace_emscripten-inl.inc" # include "absl/debugging/internal/stacktrace_generic-inl.inc" # include "absl/debugging/internal/stacktrace_powerpc-inl.inc" +# include "absl/debugging/internal/stacktrace_riscv-inl.inc" # include "absl/debugging/internal/stacktrace_unimplemented-inl.inc" # include "absl/debugging/internal/stacktrace_win32-inl.inc" # include "absl/debugging/internal/stacktrace_x86-inl.inc" diff --git a/absl/flags/flag_test.cc b/absl/flags/flag_test.cc index ba81317b..6e974a5b 100644 --- a/absl/flags/flag_test.cc +++ b/absl/flags/flag_test.cc @@ -103,9 +103,9 @@ struct S2 { TEST_F(FlagTest, Traits) { EXPECT_EQ(flags::StorageKind<int>(), - flags::FlagValueStorageKind::kOneWordAtomic); + flags::FlagValueStorageKind::kValueAndInitBit); EXPECT_EQ(flags::StorageKind<bool>(), - flags::FlagValueStorageKind::kOneWordAtomic); + flags::FlagValueStorageKind::kValueAndInitBit); EXPECT_EQ(flags::StorageKind<double>(), flags::FlagValueStorageKind::kOneWordAtomic); EXPECT_EQ(flags::StorageKind<int64_t>(), @@ -724,6 +724,8 @@ ABSL_FLAG(CustomUDT, test_flag_custom_udt, CustomUDT(), "test flag custom UDT"); namespace { TEST_F(FlagTest, TestCustomUDT) { + EXPECT_EQ(flags::StorageKind<CustomUDT>(), + flags::FlagValueStorageKind::kOneWordAtomic); EXPECT_EQ(absl::GetFlag(FLAGS_test_flag_custom_udt), CustomUDT(1, 1)); absl::SetFlag(&FLAGS_test_flag_custom_udt, CustomUDT(2, 3)); EXPECT_EQ(absl::GetFlag(FLAGS_test_flag_custom_udt), CustomUDT(2, 3)); @@ -944,3 +946,34 @@ TEST_F(FlagTest, TestNonTriviallyCopyableUDT) { } } // namespace + +// -------------------------------------------------------------------- + +namespace { + +enum TestE { A = 1, B = 2, C = 3 }; + +struct EnumWrapper { + EnumWrapper() : e(A) {} + + TestE e; +}; + +bool AbslParseFlag(absl::string_view, EnumWrapper*, std::string*) { + return true; +} +std::string AbslUnparseFlag(const EnumWrapper&) { return ""; } + +} // namespace + +ABSL_FLAG(EnumWrapper, test_enum_wrapper_flag, {}, "help"); + +TEST_F(FlagTest, TesTypeWrappingEnum) { + EnumWrapper value = absl::GetFlag(FLAGS_test_enum_wrapper_flag); + EXPECT_EQ(value.e, A); + + value.e = B; + absl::SetFlag(&FLAGS_test_enum_wrapper_flag, value); + value = absl::GetFlag(FLAGS_test_enum_wrapper_flag); + EXPECT_EQ(value.e, B); +} diff --git a/absl/flags/internal/flag.cc b/absl/flags/internal/flag.cc index f83c1fe7..1515022d 100644 --- a/absl/flags/internal/flag.cc +++ b/absl/flags/internal/flag.cc @@ -145,12 +145,7 @@ void FlagImpl::Init() { auto def_kind = static_cast<FlagDefaultKind>(def_kind_); switch (ValueStorageKind()) { - case FlagValueStorageKind::kAlignedBuffer: - // For this storage kind the default_value_ always points to gen_func - // during initialization. - assert(def_kind == FlagDefaultKind::kGenFunc); - (*default_value_.gen_func)(AlignedBufferValue()); - break; + case FlagValueStorageKind::kValueAndInitBit: case FlagValueStorageKind::kOneWordAtomic: { alignas(int64_t) std::array<char, sizeof(int64_t)> buf{}; if (def_kind == FlagDefaultKind::kGenFunc) { @@ -159,6 +154,12 @@ void FlagImpl::Init() { assert(def_kind != FlagDefaultKind::kDynamicValue); std::memcpy(buf.data(), &default_value_, Sizeof(op_)); } + if (ValueStorageKind() == FlagValueStorageKind::kValueAndInitBit) { + // We presume here the memory layout of FlagValueAndInitBit struct. + uint8_t initialized = 1; + std::memcpy(buf.data() + Sizeof(op_), &initialized, + sizeof(initialized)); + } OneWordValue().store(absl::bit_cast<int64_t>(buf), std::memory_order_release); break; @@ -170,6 +171,12 @@ void FlagImpl::Init() { (*default_value_.gen_func)(AtomicBufferValue()); break; } + case FlagValueStorageKind::kAlignedBuffer: + // For this storage kind the default_value_ always points to gen_func + // during initialization. + assert(def_kind == FlagDefaultKind::kGenFunc); + (*default_value_.gen_func)(AlignedBufferValue()); + break; } seq_lock_.MarkInitialized(); } @@ -226,12 +233,10 @@ std::unique_ptr<void, DynValueDeleter> FlagImpl::MakeInitValue() const { void FlagImpl::StoreValue(const void* src) { switch (ValueStorageKind()) { - case FlagValueStorageKind::kAlignedBuffer: - Copy(op_, src, AlignedBufferValue()); - seq_lock_.IncrementModificationCount(); - break; + case FlagValueStorageKind::kValueAndInitBit: case FlagValueStorageKind::kOneWordAtomic: { - int64_t one_word_val = 0; + // Load the current value to avoid setting 'init' bit manualy. + int64_t one_word_val = OneWordValue().load(std::memory_order_acquire); std::memcpy(&one_word_val, src, Sizeof(op_)); OneWordValue().store(one_word_val, std::memory_order_release); seq_lock_.IncrementModificationCount(); @@ -241,6 +246,10 @@ void FlagImpl::StoreValue(const void* src) { seq_lock_.Write(AtomicBufferValue(), src, Sizeof(op_)); break; } + case FlagValueStorageKind::kAlignedBuffer: + Copy(op_, src, AlignedBufferValue()); + seq_lock_.IncrementModificationCount(); + break; } modified_ = true; InvokeCallback(); @@ -280,10 +289,7 @@ std::string FlagImpl::DefaultValue() const { std::string FlagImpl::CurrentValue() const { auto* guard = DataGuard(); // Make sure flag initialized switch (ValueStorageKind()) { - case FlagValueStorageKind::kAlignedBuffer: { - absl::MutexLock l(guard); - return flags_internal::Unparse(op_, AlignedBufferValue()); - } + case FlagValueStorageKind::kValueAndInitBit: case FlagValueStorageKind::kOneWordAtomic: { const auto one_word_val = absl::bit_cast<std::array<char, sizeof(int64_t)>>( @@ -296,6 +302,10 @@ std::string FlagImpl::CurrentValue() const { ReadSequenceLockedData(cloned.get()); return flags_internal::Unparse(op_, cloned.get()); } + case FlagValueStorageKind::kAlignedBuffer: { + absl::MutexLock l(guard); + return flags_internal::Unparse(op_, AlignedBufferValue()); + } } return ""; @@ -341,11 +351,7 @@ std::unique_ptr<FlagStateInterface> FlagImpl::SaveState() { bool modified = modified_; bool on_command_line = on_command_line_; switch (ValueStorageKind()) { - case FlagValueStorageKind::kAlignedBuffer: { - return absl::make_unique<FlagState>( - *this, flags_internal::Clone(op_, AlignedBufferValue()), modified, - on_command_line, ModificationCount()); - } + case FlagValueStorageKind::kValueAndInitBit: case FlagValueStorageKind::kOneWordAtomic: { return absl::make_unique<FlagState>( *this, OneWordValue().load(std::memory_order_acquire), modified, @@ -361,6 +367,11 @@ std::unique_ptr<FlagStateInterface> FlagImpl::SaveState() { return absl::make_unique<FlagState>(*this, cloned, modified, on_command_line, ModificationCount()); } + case FlagValueStorageKind::kAlignedBuffer: { + return absl::make_unique<FlagState>( + *this, flags_internal::Clone(op_, AlignedBufferValue()), modified, + on_command_line, ModificationCount()); + } } return nullptr; } @@ -372,13 +383,14 @@ bool FlagImpl::RestoreState(const FlagState& flag_state) { } switch (ValueStorageKind()) { - case FlagValueStorageKind::kAlignedBuffer: - case FlagValueStorageKind::kSequenceLocked: - StoreValue(flag_state.value_.heap_allocated); - break; + case FlagValueStorageKind::kValueAndInitBit: case FlagValueStorageKind::kOneWordAtomic: StoreValue(&flag_state.value_.one_word); break; + case FlagValueStorageKind::kSequenceLocked: + case FlagValueStorageKind::kAlignedBuffer: + StoreValue(flag_state.value_.heap_allocated); + break; } modified_ = flag_state.modified_; @@ -407,7 +419,8 @@ std::atomic<uint64_t>* FlagImpl::AtomicBufferValue() const { } std::atomic<int64_t>& FlagImpl::OneWordValue() const { - assert(ValueStorageKind() == FlagValueStorageKind::kOneWordAtomic); + assert(ValueStorageKind() == FlagValueStorageKind::kOneWordAtomic || + ValueStorageKind() == FlagValueStorageKind::kValueAndInitBit); return OffsetValue<FlagOneWordValue>()->value; } @@ -433,11 +446,7 @@ std::unique_ptr<void, DynValueDeleter> FlagImpl::TryParse( void FlagImpl::Read(void* dst) const { auto* guard = DataGuard(); // Make sure flag initialized switch (ValueStorageKind()) { - case FlagValueStorageKind::kAlignedBuffer: { - absl::MutexLock l(guard); - flags_internal::CopyConstruct(op_, AlignedBufferValue(), dst); - break; - } + case FlagValueStorageKind::kValueAndInitBit: case FlagValueStorageKind::kOneWordAtomic: { const int64_t one_word_val = OneWordValue().load(std::memory_order_acquire); @@ -448,9 +457,31 @@ void FlagImpl::Read(void* dst) const { ReadSequenceLockedData(dst); break; } + case FlagValueStorageKind::kAlignedBuffer: { + absl::MutexLock l(guard); + flags_internal::CopyConstruct(op_, AlignedBufferValue(), dst); + break; + } } } +int64_t FlagImpl::ReadOneWord() const { + assert(ValueStorageKind() == FlagValueStorageKind::kOneWordAtomic || + ValueStorageKind() == FlagValueStorageKind::kValueAndInitBit); + auto* guard = DataGuard(); // Make sure flag initialized + (void)guard; + return OneWordValue().load(std::memory_order_acquire); +} + +bool FlagImpl::ReadOneBool() const { + assert(ValueStorageKind() == FlagValueStorageKind::kValueAndInitBit); + auto* guard = DataGuard(); // Make sure flag initialized + (void)guard; + return absl::bit_cast<FlagValueAndInitBit<bool>>( + OneWordValue().load(std::memory_order_acquire)) + .value; +} + void FlagImpl::ReadSequenceLockedData(void* dst) const { int size = Sizeof(op_); // Attempt to read using the sequence lock. diff --git a/absl/flags/internal/flag.h b/absl/flags/internal/flag.h index e6bade0a..8636fadc 100644 --- a/absl/flags/internal/flag.h +++ b/absl/flags/internal/flag.h @@ -29,6 +29,7 @@ #include "absl/base/attributes.h" #include "absl/base/call_once.h" +#include "absl/base/casts.h" #include "absl/base/config.h" #include "absl/base/optimization.h" #include "absl/base/thread_annotations.h" @@ -305,48 +306,71 @@ constexpr FlagDefaultArg DefaultArg(char) { constexpr int64_t UninitializedFlagValue() { return 0xababababababababll; } template <typename T> +using FlagUseValueAndInitBitStorage = std::integral_constant< + bool, absl::type_traits_internal::is_trivially_copyable<T>::value && + std::is_default_constructible<T>::value && (sizeof(T) < 8)>; + +template <typename T> using FlagUseOneWordStorage = std::integral_constant< bool, absl::type_traits_internal::is_trivially_copyable<T>::value && (sizeof(T) <= 8)>; template <class T> -using FlagShouldUseSequenceLock = std::integral_constant< +using FlagUseSequenceLockStorage = std::integral_constant< bool, absl::type_traits_internal::is_trivially_copyable<T>::value && (sizeof(T) > 8)>; enum class FlagValueStorageKind : uint8_t { - kAlignedBuffer = 0, + kValueAndInitBit = 0, kOneWordAtomic = 1, kSequenceLocked = 2, + kAlignedBuffer = 3, }; template <typename T> static constexpr FlagValueStorageKind StorageKind() { - return FlagUseOneWordStorage<T>::value ? FlagValueStorageKind::kOneWordAtomic - : FlagShouldUseSequenceLock<T>::value + return FlagUseValueAndInitBitStorage<T>::value + ? FlagValueStorageKind::kValueAndInitBit + : FlagUseOneWordStorage<T>::value + ? FlagValueStorageKind::kOneWordAtomic + : FlagUseSequenceLockStorage<T>::value ? FlagValueStorageKind::kSequenceLocked : FlagValueStorageKind::kAlignedBuffer; } struct FlagOneWordValue { - constexpr FlagOneWordValue() : value(UninitializedFlagValue()) {} - + constexpr explicit FlagOneWordValue(int64_t v) : value(v) {} std::atomic<int64_t> value; }; +template <typename T> +struct alignas(8) FlagValueAndInitBit { + T value; + // Use an int instead of a bool to guarantee that a non-zero value has + // a bit set. + uint8_t init; +}; + template <typename T, FlagValueStorageKind Kind = flags_internal::StorageKind<T>()> struct FlagValue; template <typename T> -struct FlagValue<T, FlagValueStorageKind::kAlignedBuffer> { - bool Get(const SequenceLock&, T&) const { return false; } - - alignas(T) char value[sizeof(T)]; +struct FlagValue<T, FlagValueStorageKind::kValueAndInitBit> : FlagOneWordValue { + constexpr FlagValue() : FlagOneWordValue(0) {} + bool Get(const SequenceLock&, T& dst) const { + int64_t storage = value.load(std::memory_order_acquire); + if (ABSL_PREDICT_FALSE(storage == 0)) { + return false; + } + dst = absl::bit_cast<FlagValueAndInitBit<T>>(storage).value; + return true; + } }; template <typename T> struct FlagValue<T, FlagValueStorageKind::kOneWordAtomic> : FlagOneWordValue { + constexpr FlagValue() : FlagOneWordValue(UninitializedFlagValue()) {} bool Get(const SequenceLock&, T& dst) const { int64_t one_word_val = value.load(std::memory_order_acquire); if (ABSL_PREDICT_FALSE(one_word_val == UninitializedFlagValue())) { @@ -370,6 +394,13 @@ struct FlagValue<T, FlagValueStorageKind::kSequenceLocked> { std::atomic<uint64_t>) std::atomic<uint64_t> value_words[kNumWords]; }; +template <typename T> +struct FlagValue<T, FlagValueStorageKind::kAlignedBuffer> { + bool Get(const SequenceLock&, T&) const { return false; } + + alignas(T) char value[sizeof(T)]; +}; + /////////////////////////////////////////////////////////////////////////////// // Flag callback auxiliary structs. @@ -415,7 +446,27 @@ class FlagImpl final : public CommandLineFlag { data_guard_{} {} // Constant access methods + int64_t ReadOneWord() const ABSL_LOCKS_EXCLUDED(*DataGuard()); + bool ReadOneBool() const ABSL_LOCKS_EXCLUDED(*DataGuard()); void Read(void* dst) const override ABSL_LOCKS_EXCLUDED(*DataGuard()); + void Read(bool* value) const ABSL_LOCKS_EXCLUDED(*DataGuard()) { + *value = ReadOneBool(); + } + template <typename T, + absl::enable_if_t<flags_internal::StorageKind<T>() == + FlagValueStorageKind::kOneWordAtomic, + int> = 0> + void Read(T* value) const ABSL_LOCKS_EXCLUDED(*DataGuard()) { + int64_t v = ReadOneWord(); + std::memcpy(value, static_cast<const void*>(&v), sizeof(T)); + } + template <typename T, + typename std::enable_if<flags_internal::StorageKind<T>() == + FlagValueStorageKind::kValueAndInitBit, + int>::type = 0> + void Read(T* value) const ABSL_LOCKS_EXCLUDED(*DataGuard()) { + *value = absl::bit_cast<FlagValueAndInitBit<T>>(ReadOneWord()).value; + } // Mutating access methods void Write(const void* src) ABSL_LOCKS_EXCLUDED(*DataGuard()); diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel index 21915cc1..392b68f1 100644 --- a/absl/hash/BUILD.bazel +++ b/absl/hash/BUILD.bazel @@ -152,6 +152,7 @@ cc_library( deps = [ "//absl/base:config", "//absl/base:endian", + "//absl/numeric:bits", "//absl/numeric:int128", ], ) diff --git a/absl/hash/CMakeLists.txt b/absl/hash/CMakeLists.txt index 6c79c93a..5916ae3c 100644 --- a/absl/hash/CMakeLists.txt +++ b/absl/hash/CMakeLists.txt @@ -126,6 +126,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS + absl::bits absl::config absl::endian absl::int128 diff --git a/absl/hash/internal/low_level_hash.cc b/absl/hash/internal/low_level_hash.cc index 856bbd9b..6f9cb9c7 100644 --- a/absl/hash/internal/low_level_hash.cc +++ b/absl/hash/internal/low_level_hash.cc @@ -15,6 +15,7 @@ #include "absl/hash/internal/low_level_hash.h" #include "absl/base/internal/unaligned_access.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" namespace absl { @@ -22,9 +23,20 @@ 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); +#else + // The default bit-mixer above would perform poorly on some ARM microarchs, + // where calculating a 128-bit product requires a sequence of two + // instructions with a high combined latency and poor throughput. + // Instead, we mix bits using only 64-bit arithmetic, which is faster. + uint64_t p = v0 ^ absl::rotl(v1, 40); + p *= v1 ^ absl::rotl(v0, 39); + return p ^ (p >> 11); +#endif } uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed, diff --git a/absl/hash/internal/low_level_hash_test.cc b/absl/hash/internal/low_level_hash_test.cc index 0ef50236..cf22dc3c 100644 --- a/absl/hash/internal/low_level_hash_test.cc +++ b/absl/hash/internal/low_level_hash_test.cc @@ -14,473 +14,519 @@ #include "absl/hash/internal/low_level_hash.h" -#include "absl/strings/escaping.h" +#include <cinttypes> + #include "gmock/gmock.h" #include "gtest/gtest.h" +#include "absl/strings/escaping.h" + +#define UPDATE_GOLDEN 0 namespace { -static const uint64_t kCurrentSeed = 0; static const uint64_t kSalt[5] = {0xa0761d6478bd642f, 0xe7037ed1a0b428dbl, 0x8ebc6af09c88c6e3, 0x589965cc75374cc3l, 0x1d8e4e27c47d124f}; -// Note: We don't account for endianness, so the values here are only correct if -// you're also running on a little endian platform. - -TEST(LowLevelHashTest, EmptyString) { - const std::string s = ""; - EXPECT_EQ(absl::hash_internal::LowLevelHash(s.c_str(), s.length(), - kCurrentSeed, kSalt), - 4808886099364463827); -} - -TEST(LowLevelHashTest, Spaces) { - const std::string s = " "; - EXPECT_EQ(absl::hash_internal::LowLevelHash(s.c_str(), s.length(), - kCurrentSeed, kSalt), - 1686201463024549249); -} - -TEST(LowLevelHashTest, RepeatingString) { - const std::string s = "aaaa"; - EXPECT_EQ(absl::hash_internal::LowLevelHash(s.c_str(), s.length(), - kCurrentSeed, kSalt), - 6646112255271966632); -} - -TEST(LowLevelHashTest, HexString) { - const std::string small = "\x01\x02\x03"; - const std::string med = "\x01\x02\x03\x04"; - - EXPECT_EQ(absl::hash_internal::LowLevelHash(small.c_str(), small.length(), - kCurrentSeed, kSalt), - 11989428023081740911ULL); - EXPECT_EQ(absl::hash_internal::LowLevelHash(med.c_str(), med.length(), - kCurrentSeed, kSalt), - 9765997711188871556ULL); -} - -TEST(LowLevelHashTest, Words) { - const std::string s = "third_party|wyhash|64"; - EXPECT_EQ(absl::hash_internal::LowLevelHash(s.c_str(), s.length(), - kCurrentSeed, kSalt), - 3702018632387611330); -} - -TEST(LowLevelHashTest, LongString) { - const std::string s = - "AbCdEfGhIjKlMnOpQrStUvWxYz0123456789AbCdEfGhIjKlMnOpQrStUvWxYz" - "0123456789AbCdEfGhIjKlMnOpQrStUvWxYz0123456789AbCdEfGhIjKlMnOp" - "QrStUvWxYz0123456789AbCdEfGhIjKlMnOpQrStUvWxYz0123456789AbCdEf" - "GhIjKlMnOpQrStUvWxYz0123456789AbCdEfGhIjKlMnOpQrStUvWxYz012345" - "6789AbCdEfGhIjKlMnOpQrStUvWxYz0123456789"; - - EXPECT_EQ(absl::hash_internal::LowLevelHash(s.c_str(), s.length(), - kCurrentSeed, kSalt), - 9245411362605796064ULL); -} - -TEST(LowLevelHashTest, BigReference) { - struct ExpectedResult { +TEST(LowLevelHashTest, VerifyGolden) { + constexpr size_t kNumGoldenOutputs = 134; + static struct { absl::string_view base64_data; uint64_t seed; - uint64_t hash; - } expected_results[] = { - {"", uint64_t{0xec42b7ab404b8acb}, uint64_t{0xe5a40d39ab796423}}, - {"Zw==", uint64_t{0xeeee074043a3ee0f}, uint64_t{0xa6564b468248c683}}, - {"xmk=", uint64_t{0x857902089c393de}, uint64_t{0xef192f401b116e1c}}, - {"c1H/", uint64_t{0x993df040024ca3af}, uint64_t{0xbe8dc0c54617639d}}, - {"SuwpzQ==", uint64_t{0xc4e4c2acea740e96}, uint64_t{0x93d7f665b5521c8e}}, - {"uqvy++M=", uint64_t{0x6a214b3db872d0cf}, uint64_t{0x646d70bb42445f28}}, - {"RnzCVPgb", uint64_t{0x44343db6a89dba4d}, uint64_t{0x96a7b1e3cc9bd426}}, - {"6OeNdlouYw==", uint64_t{0x77b5d6d1ae1dd483}, - uint64_t{0x76020289ab0790c4}}, - {"M5/JmmYyDbc=", uint64_t{0x89ab8ecb44d221f1}, - uint64_t{0x39f842e4133b9b44}}, - {"MVijWiVdBRdY", uint64_t{0x60244b17577ca81b}, - uint64_t{0x2b8d7047be4bcaab}}, - {"6V7Uq7LNxpu0VA==", uint64_t{0x59a08dcee0717067}, - uint64_t{0x99628abef6716a97}}, - {"EQ6CdEEhPdyHcOk=", uint64_t{0xf5f20db3ade57396}, - uint64_t{0x4432e02ba42b2740}}, - {"PqFB4fxnPgF+l+rc", uint64_t{0xbf8dee0751ad3efb}, - uint64_t{0x74d810efcad7918a}}, - {"a5aPOFwq7LA7+zKvPA==", uint64_t{0x6b7a06b268d63e30}, - uint64_t{0x88c84e986002507f}}, - {"VOwY21wCGv5D+/qqOvs=", uint64_t{0xb8c37f0ae0f54c82}, - uint64_t{0x4f99acf193cf39b9}}, - {"KdHmBTx8lHXYvmGJ+Vy7", uint64_t{0x9fcbed0c38e50eef}, - uint64_t{0xd90e7a3655891e37}}, - {"qJkPlbHr8bMF7/cA6aE65Q==", uint64_t{0x2af4bade1d8e3a1d}, - uint64_t{0x3bb378b1d4df8fcf}}, - {"ygvL0EhHZL0fIx6oHHtkxRQ=", uint64_t{0x714e3aa912da2f2c}, - uint64_t{0xf78e94045c052d47}}, - {"c1rFXkt5YztwZCQRngncqtSs", uint64_t{0xf5ee75e3cbb82c1c}, - uint64_t{0x26da0b2130da6b40}}, - {"8hsQrzszzeNQSEcVXLtvIhm6mw==", uint64_t{0x620e7007321b93b9}, - uint64_t{0x30b4d426af8c6986}}, - {"ffUL4RocfyP4KfikGxO1yk7omDI=", uint64_t{0xc08528cac2e551fc}, - uint64_t{0x5413b4aaf3baaeae}}, - {"OOB5TT00vF9Od/rLbAWshiErqhpV", uint64_t{0x6a1debf9cc3ad39}, - uint64_t{0x756ab265370a1597}}, - {"or5wtXM7BFzTNpSzr+Lw5J5PMhVJ/Q==", uint64_t{0x7e0a3c88111fc226}, - uint64_t{0xdaf5f4b7d09814fb}}, - {"gk6pCHDUsoopVEiaCrzVDhioRKxb844=", uint64_t{0x1301fef15df39edb}, - uint64_t{0x8f874ae37742b75e}}, - {"TNctmwlC5QbEM6/No4R/La3UdkfeMhzs", uint64_t{0x64e181f3d5817ab}, - uint64_t{0x8fecd03956121ce8}}, - {"SsQw9iAjhWz7sgcE9OwLuSC6hsM+BfHs2Q==", uint64_t{0xafafc44961078ecb}, - uint64_t{0x229c292ea7a08285}}, - {"ZzO3mVCj4xTT2TT3XqDyEKj2BZQBvrS8RHg=", uint64_t{0x4f7bb45549250094}, - uint64_t{0xbb4bf0692d14bae}}, - {"+klp5iPQGtppan5MflEls0iEUzqU+zGZkDJX", uint64_t{0xa30061abaa2818c}, - uint64_t{0x207b24ca3bdac1db}}, - {"RO6bvOnlJc8I9eniXlNgqtKy0IX6VNg16NRmgg==", uint64_t{0xd902ee3e44a5705f}, - uint64_t{0x64f6cd6745d3825b}}, - {"ZJjZqId1ZXBaij9igClE3nyliU5XWdNRrayGlYA=", uint64_t{0x316d36da516f583}, - uint64_t{0xa2b2e1656b58df1e}}, - {"7BfkhfGMDGbxfMB8uyL85GbaYQtjr2K8g7RpLzr/", uint64_t{0x402d83f9f834f616}, - uint64_t{0xd01d30d9ee7a148}}, + } cases[] = { + {"", uint64_t{0xec42b7ab404b8acb}}, + {"ICAg", uint64_t{0}}, + {"YWFhYQ==", uint64_t{0}}, + {"AQID", uint64_t{0}}, + {"AQIDBA==", uint64_t{0}}, + {"dGhpcmRfcGFydHl8d3loYXNofDY0", uint64_t{0}}, + {"Zw==", uint64_t{0xeeee074043a3ee0f}}, + {"xmk=", uint64_t{0x857902089c393de}}, + {"c1H/", uint64_t{0x993df040024ca3af}}, + {"SuwpzQ==", uint64_t{0xc4e4c2acea740e96}}, + {"uqvy++M=", uint64_t{0x6a214b3db872d0cf}}, + {"RnzCVPgb", uint64_t{0x44343db6a89dba4d}}, + {"6OeNdlouYw==", uint64_t{0x77b5d6d1ae1dd483}}, + {"M5/JmmYyDbc=", uint64_t{0x89ab8ecb44d221f1}}, + {"MVijWiVdBRdY", uint64_t{0x60244b17577ca81b}}, + {"6V7Uq7LNxpu0VA==", uint64_t{0x59a08dcee0717067}}, + {"EQ6CdEEhPdyHcOk=", uint64_t{0xf5f20db3ade57396}}, + {"PqFB4fxnPgF+l+rc", uint64_t{0xbf8dee0751ad3efb}}, + {"a5aPOFwq7LA7+zKvPA==", uint64_t{0x6b7a06b268d63e30}}, + {"VOwY21wCGv5D+/qqOvs=", uint64_t{0xb8c37f0ae0f54c82}}, + {"KdHmBTx8lHXYvmGJ+Vy7", uint64_t{0x9fcbed0c38e50eef}}, + {"qJkPlbHr8bMF7/cA6aE65Q==", uint64_t{0x2af4bade1d8e3a1d}}, + {"ygvL0EhHZL0fIx6oHHtkxRQ=", uint64_t{0x714e3aa912da2f2c}}, + {"c1rFXkt5YztwZCQRngncqtSs", uint64_t{0xf5ee75e3cbb82c1c}}, + {"8hsQrzszzeNQSEcVXLtvIhm6mw==", uint64_t{0x620e7007321b93b9}}, + {"ffUL4RocfyP4KfikGxO1yk7omDI=", uint64_t{0xc08528cac2e551fc}}, + {"OOB5TT00vF9Od/rLbAWshiErqhpV", uint64_t{0x6a1debf9cc3ad39}}, + {"or5wtXM7BFzTNpSzr+Lw5J5PMhVJ/Q==", uint64_t{0x7e0a3c88111fc226}}, + {"gk6pCHDUsoopVEiaCrzVDhioRKxb844=", uint64_t{0x1301fef15df39edb}}, + {"TNctmwlC5QbEM6/No4R/La3UdkfeMhzs", uint64_t{0x64e181f3d5817ab}}, + {"SsQw9iAjhWz7sgcE9OwLuSC6hsM+BfHs2Q==", uint64_t{0xafafc44961078ecb}}, + {"ZzO3mVCj4xTT2TT3XqDyEKj2BZQBvrS8RHg=", uint64_t{0x4f7bb45549250094}}, + {"+klp5iPQGtppan5MflEls0iEUzqU+zGZkDJX", uint64_t{0xa30061abaa2818c}}, + {"RO6bvOnlJc8I9eniXlNgqtKy0IX6VNg16NRmgg==", + uint64_t{0xd902ee3e44a5705f}}, + {"ZJjZqId1ZXBaij9igClE3nyliU5XWdNRrayGlYA=", uint64_t{0x316d36da516f583}}, + {"7BfkhfGMDGbxfMB8uyL85GbaYQtjr2K8g7RpLzr/", + uint64_t{0x402d83f9f834f616}}, {"rycWk6wHH7htETQtje9PidS2YzXBx+Qkg2fY7ZYS7A==", - uint64_t{0x9c604164c016b72c}, uint64_t{0x1cb4cd00ab804e3b}}, + uint64_t{0x9c604164c016b72c}}, {"RTkC2OUK+J13CdGllsH0H5WqgspsSa6QzRZouqx6pvI=", - uint64_t{0x3f4507e01f9e73ba}, uint64_t{0x4697f2637fd90999}}, + uint64_t{0x3f4507e01f9e73ba}}, {"tKjKmbLCNyrLCM9hycOAXm4DKNpM12oZ7dLTmUx5iwAi", - uint64_t{0xc3fe0d5be8d2c7c7}, uint64_t{0x8383a756b5688c07}}, + uint64_t{0xc3fe0d5be8d2c7c7}}, {"VprUGNH+5NnNRaORxgH/ySrZFQFDL+4VAodhfBNinmn8cg==", - uint64_t{0x531858a40bfa7ea1}, uint64_t{0x695c29cb3696a975}}, + uint64_t{0x531858a40bfa7ea1}}, {"gc1xZaY+q0nPcUvOOnWnT3bqfmT/geth/f7Dm2e/DemMfk4=", - uint64_t{0x86689478a7a7e8fa}, uint64_t{0xda2e5a5a5e971521}}, + uint64_t{0x86689478a7a7e8fa}}, {"Mr35fIxqx1ukPAL0su1yFuzzAU3wABCLZ8+ZUFsXn47UmAph", - uint64_t{0x4ec948b8e7f27288}, uint64_t{0x7935d4befa056b2b}}, + uint64_t{0x4ec948b8e7f27288}}, {"A9G8pw2+m7+rDtWYAdbl8tb2fT7FFo4hLi2vAsa5Y8mKH3CX3g==", - uint64_t{0xce46c7213c10032}, uint64_t{0x38dd541ca95420fe}}, + uint64_t{0xce46c7213c10032}}, {"DFaJGishGwEHDdj9ixbCoaTjz9KS0phLNWHVVdFsM93CvPft3hM=", - uint64_t{0xf63e96ee6f32a8b6}, uint64_t{0xcc06c7a4963f967f}}, + uint64_t{0xf63e96ee6f32a8b6}}, {"7+Ugx+Kr3aRNgYgcUxru62YkTDt5Hqis+2po81hGBkcrJg4N0uuy", - uint64_t{0x1cfe85e65fc5225}, uint64_t{0xbf0f6f66e232fb20}}, + uint64_t{0x1cfe85e65fc5225}}, {"H2w6O8BUKqu6Tvj2xxaecxEI2wRgIgqnTTG1WwOgDSINR13Nm4d4Vg==", - uint64_t{0x45c474f1cee1d2e8}, uint64_t{0xf7efb32d373fe71a}}, + uint64_t{0x45c474f1cee1d2e8}}, {"1XBMnIbqD5jy65xTDaf6WtiwtdtQwv1dCVoqpeKj+7cTR1SaMWMyI04=", - uint64_t{0x6e024e14015f329c}, uint64_t{0xe2e64634b1c12660}}, + uint64_t{0x6e024e14015f329c}}, {"znZbdXG2TSFrKHEuJc83gPncYpzXGbAebUpP0XxzH0rpe8BaMQ17nDbt", - uint64_t{0x760c40502103ae1c}, uint64_t{0x285b8fd1638e306d}}, + uint64_t{0x760c40502103ae1c}}, {"ylu8Atu13j1StlcC1MRMJJXIl7USgDDS22HgVv0WQ8hx/8pNtaiKB17hCQ==", - uint64_t{0x17fd05c3c560c320}, uint64_t{0x658e8a4e3b714d6c}}, + uint64_t{0x17fd05c3c560c320}}, {"M6ZVVzsd7vAvbiACSYHioH/440dp4xG2mLlBnxgiqEvI/aIEGpD0Sf4VS0g=", - uint64_t{0x8b34200a6f8e90d9}, uint64_t{0xf391fb968e0eb398}}, + uint64_t{0x8b34200a6f8e90d9}}, {"li3oFSXLXI+ubUVGJ4blP6mNinGKLHWkvGruun85AhVn6iuMtocbZPVhqxzn", - uint64_t{0x6be89e50818bdf69}, uint64_t{0x744a9ea0cc144bf2}}, + uint64_t{0x6be89e50818bdf69}}, {"kFuQHuUCqBF3Tc3hO4dgdIp223ShaCoog48d5Do5zMqUXOh5XpGK1t5XtxnfGA==", - uint64_t{0xfb389773315b47d8}, uint64_t{0x12636f2be11012f1}}, + uint64_t{0xfb389773315b47d8}}, {"jWmOad0v0QhXVJd1OdGuBZtDYYS8wBVHlvOeTQx9ZZnm8wLEItPMeihj72E0nWY=", - uint64_t{0x4f2512a23f61efee}, uint64_t{0x29c57de825948f80}}, + uint64_t{0x4f2512a23f61efee}}, {"z+DHU52HaOQdW4JrZwDQAebEA6rm13Zg/9lPYA3txt3NjTBqFZlOMvTRnVzRbl23", - uint64_t{0x59ccd92fc16c6fda}, uint64_t{0x58c6f99ab0d1c021}}, + uint64_t{0x59ccd92fc16c6fda}}, {"MmBiGDfYeTayyJa/tVycg+rN7f9mPDFaDc+23j0TlW9094er0ADigsl4QX7V3gG/qw==", - uint64_t{0x25c5a7f5bd330919}, uint64_t{0x13e7b5a7b82fe3bb}}, + uint64_t{0x25c5a7f5bd330919}}, {"774RK+9rOL4iFvs1q2qpo/JVc/I39buvNjqEFDtDvyoB0FXxPI2vXqOrk08VPfIHkmU=", - uint64_t{0x51df4174d34c97d7}, uint64_t{0x10fbc87901e02b63}}, + uint64_t{0x51df4174d34c97d7}}, {"+slatXiQ7/2lK0BkVUI1qzNxOOLP3I1iK6OfHaoxgqT63FpzbElwEXSwdsryq3UlHK0I", - uint64_t{0x80ce6d76f89cb57}, uint64_t{0xa24c9184901b748b}}, + uint64_t{0x80ce6d76f89cb57}}, {"64mVTbQ47dHjHlOHGS/hjJwr/" "K2frCNpn87exOqMzNUVYiPKmhCbfS7vBUce5tO6Ec9osQ==", - uint64_t{0x20961c911965f684}, uint64_t{0xcac4fd4c5080e581}}, + uint64_t{0x20961c911965f684}}, {"fIsaG1r530SFrBqaDj1kqE0AJnvvK8MNEZbII2Yw1OK77v0V59xabIh0B5axaz/" "+a2V5WpA=", - uint64_t{0x4e5b926ec83868e7}, uint64_t{0xc38bdb7483ba68e1}}, + uint64_t{0x4e5b926ec83868e7}}, {"PGih0zDEOWCYGxuHGDFu9Ivbff/" "iE7BNUq65tycTR2R76TerrXALRosnzaNYO5fjFhTi+CiS", - uint64_t{0x3927b30b922eecef}, uint64_t{0xdb2a8069b2ceaffa}}, + uint64_t{0x3927b30b922eecef}}, {"RnpA/" "zJnEnnLjmICORByRVb9bCOgxF44p3VMiW10G7PvW7IhwsWajlP9kIwNA9FjAD2GoQHk2Q=" "=", - uint64_t{0xbd0291284a49b61c}, uint64_t{0xdf9fe91d0d1c7887}}, + uint64_t{0xbd0291284a49b61c}}, {"qFklMceaTHqJpy2qavJE+EVBiNFOi6OxjOA3LeIcBop1K7w8xQi3TrDk+" "BrWPRIbfprszSaPfrI=", - uint64_t{0x73a77c575bcc956}, uint64_t{0xe83f49e96e2e6a08}}, + uint64_t{0x73a77c575bcc956}}, {"cLbfUtLl3EcQmITWoTskUR8da/VafRDYF/ylPYwk7/" "zazk6ssyrzxMN3mmSyvrXR2yDGNZ3WDrTT", - uint64_t{0x766a0e2ade6d09a6}, uint64_t{0xc69e61b62ca2b62}}, + uint64_t{0x766a0e2ade6d09a6}}, {"s/" "Jf1+" "FbsbCpXWPTUSeWyMH6e4CvTFvPE5Fs6Z8hvFITGyr0dtukHzkI84oviVLxhM1xMxrMAy1db" "w==", - uint64_t{0x2599f4f905115869}, uint64_t{0xb4a4f3f85f8298fe}}, + uint64_t{0x2599f4f905115869}}, {"FvyQ00+j7nmYZVQ8hI1Edxd0AWplhTfWuFGiu34AK5X8u2hLX1bE97sZM0CmeLe+" "7LgoUT1fJ/axybE=", - uint64_t{0xd8256e5444d21e53}, uint64_t{0x167a1b39e1e95f41}}, + uint64_t{0xd8256e5444d21e53}}, {"L8ncxMaYLBH3g9buPu8hfpWZNlOF7nvWLNv9IozH07uQsIBWSKxoPy8+" "LW4tTuzC6CIWbRGRRD1sQV/4", - uint64_t{0xf664a91333fb8dfd}, uint64_t{0xf8a2a5649855ee41}}, + uint64_t{0xf664a91333fb8dfd}}, {"CDK0meI07yrgV2kQlZZ+" "wuVqhc2NmzqeLH7bmcA6kchsRWFPeVF5Wqjjaj556ABeUoUr3yBmfU3kWOakkg==", - uint64_t{0x9625b859be372cd1}, uint64_t{0x27992565b595c498}}, + uint64_t{0x9625b859be372cd1}}, {"d23/vc5ONh/" "HkMiq+gYk4gaCNYyuFKwUkvn46t+dfVcKfBTYykr4kdvAPNXGYLjM4u1YkAEFpJP+" "nX7eOvs=", - uint64_t{0x7b99940782e29898}, uint64_t{0x3e08cca5b71f9346}}, + uint64_t{0x7b99940782e29898}}, {"NUR3SRxBkxTSbtQORJpu/GdR6b/h6sSGfsMj/KFd99ahbh+9r7LSgSGmkGVB/" "mGoT0pnMTQst7Lv2q6QN6Vm", - uint64_t{0x4fe12fa5383b51a8}, uint64_t{0xad406b10c770a6d2}}, + uint64_t{0x4fe12fa5383b51a8}}, {"2BOFlcI3Z0RYDtS9T9Ie9yJoXlOdigpPeeT+CRujb/" "O39Ih5LPC9hP6RQk1kYESGyaLZZi3jtabHs7DiVx/VDg==", - uint64_t{0xe2ccb09ac0f5b4b6}, uint64_t{0xd1713ce6e552bcf2}}, + uint64_t{0xe2ccb09ac0f5b4b6}}, {"FF2HQE1FxEvWBpg6Z9zAMH+Zlqx8S1JD/" "wIlViL6ZDZY63alMDrxB0GJQahmAtjlm26RGLnjW7jmgQ4Ie3I+014=", - uint64_t{0x7d0a37adbd7b753b}, uint64_t{0x753b287194c73ad3}}, + uint64_t{0x7d0a37adbd7b753b}}, {"tHmO7mqVL/PX11nZrz50Hc+M17Poj5lpnqHkEN+4bpMx/" "YGbkrGOaYjoQjgmt1X2QyypK7xClFrjeWrCMdlVYtbW", - uint64_t{0xd3ae96ef9f7185f2}, uint64_t{0x5ae41a95f600af1c}}, + uint64_t{0xd3ae96ef9f7185f2}}, {"/WiHi9IQcxRImsudkA/KOTqGe8/" "gXkhKIHkjddv5S9hi02M049dIK3EUyAEjkjpdGLUs+BN0QzPtZqjIYPOgwsYE9g==", - uint64_t{0x4fb88ea63f79a0d8}, uint64_t{0x4a61163b86a8bb4c}}, + uint64_t{0x4fb88ea63f79a0d8}}, {"qds+1ExSnU11L4fTSDz/QE90g4Jh6ioqSh3KDOTOAo2pQGL1k/" "9CCC7J23YF27dUTzrWsCQA2m4epXoCc3yPHb3xElA=", - uint64_t{0xed564e259bb5ebe9}, uint64_t{0x42eeaa79e760c7e4}}, + uint64_t{0xed564e259bb5ebe9}}, {"8FVYHx40lSQPTHheh08Oq0/" "pGm2OlG8BEf8ezvAxHuGGdgCkqpXIueJBF2mQJhTfDy5NncO8ntS7vaKs7sCNdDaNGOEi", - uint64_t{0x3e3256b60c428000}, uint64_t{0x698df622ef465b0a}}, + uint64_t{0x3e3256b60c428000}}, {"4ZoEIrJtstiCkeew3oRzmyJHVt/pAs2pj0HgHFrBPztbQ10NsQ/" "lM6DM439QVxpznnBSiHMgMQJhER+70l72LqFTO1JiIQ==", - uint64_t{0xfb05bad59ec8705}, uint64_t{0x157583111e1a6026}}, + uint64_t{0xfb05bad59ec8705}}, {"hQPtaYI+wJyxXgwD5n8jGIKFKaFA/" "P83KqCKZfPthnjwdOFysqEOYwAaZuaaiv4cDyi9TyS8hk5cEbNP/jrI7q6pYGBLbsM=", - uint64_t{0xafdc251dbf97b5f8}, uint64_t{0xaa1388f078e793e0}}, + uint64_t{0xafdc251dbf97b5f8}}, {"S4gpMSKzMD7CWPsSfLeYyhSpfWOntyuVZdX1xSBjiGvsspwOZcxNKCRIOqAA0moUfOh3I5+" "juQV4rsqYElMD/gWfDGpsWZKQ", - uint64_t{0x10ec9c92ddb5dcbc}, uint64_t{0xf10d68d0f3309360}}, + uint64_t{0x10ec9c92ddb5dcbc}}, {"oswxop+" "bthuDLT4j0PcoSKby4LhF47ZKg8K17xxHf74UsGCzTBbOz0MM8hQEGlyqDT1iUiAYnaPaUp" "L2mRK0rcIUYA4qLt5uOw==", - uint64_t{0x9a767d5822c7dac4}, uint64_t{0x2af056184457a3de}}, + uint64_t{0x9a767d5822c7dac4}}, {"0II/" "697p+" "BtLSjxj5989OXI004TogEb94VUnDzOVSgMXie72cuYRvTFNIBgtXlKfkiUjeqVpd4a+" "n5bxNOD1TGrjQtzKU5r7obo=", - uint64_t{0xee46254080d6e2db}, uint64_t{0x6d0058e1590b2489}}, + uint64_t{0xee46254080d6e2db}}, {"E84YZW2qipAlMPmctrg7TKlwLZ68l4L+c0xRDUfyyFrA4MAti0q9sHq3TDFviH0Y+" "Kq3tEE5srWFA8LM9oomtmvm5PYxoaarWPLc", - uint64_t{0xbbb669588d8bf398}, uint64_t{0x638f287f68817f12}}, + uint64_t{0xbbb669588d8bf398}}, {"x3pa4HIElyZG0Nj7Vdy9IdJIR4izLmypXw5PCmZB5y68QQ4uRaVVi3UthsoJROvbjDJkP2D" "Q6L/eN8pFeLFzNPKBYzcmuMOb5Ull7w==", - uint64_t{0xdc2afaa529beef44}, uint64_t{0xc46b71fecefd5467}}, + uint64_t{0xdc2afaa529beef44}}, {"jVDKGYIuWOP/" "QKLdd2wi8B2VJA8Wh0c8PwrXJVM8FOGM3voPDVPyDJOU6QsBDPseoR8uuKd19OZ/" "zAvSCB+zlf6upAsBlheUKgCfKww=", - uint64_t{0xf1f67391d45013a8}, uint64_t{0x2c8e94679d964e0a}}, + uint64_t{0xf1f67391d45013a8}}, {"mkquunhmYe1aR2wmUz4vcvLEcKBoe6H+kjUok9VUn2+eTSkWs4oDDtJvNCWtY5efJwg/" "j4PgjRYWtqnrCkhaqJaEvkkOwVfgMIwF3e+d", - uint64_t{0x16fce2b8c65a3429}, uint64_t{0x8612b797ce22503a}}, + uint64_t{0x16fce2b8c65a3429}}, {"fRelvKYonTQ+s+rnnvQw+JzGfFoPixtna0vzcSjiDqX5s2Kg2//" "UGrK+AVCyMUhO98WoB1DDbrsOYSw2QzrcPe0+3ck9sePvb+Q/IRaHbw==", - uint64_t{0xf4b096699f49fe67}, uint64_t{0x59f929babfba7170}}, + uint64_t{0xf4b096699f49fe67}}, {"DUwXFJzagljo44QeJ7/" "6ZKw4QXV18lhkYT2jglMr8WB3CHUU4vdsytvw6AKv42ZcG6fRkZkq9fpnmXy6xG0aO3WPT1" "eHuyFirAlkW+zKtwg=", - uint64_t{0xca584c4bc8198682}, uint64_t{0x9527556923fb49a0}}, + uint64_t{0xca584c4bc8198682}}, {"cYmZCrOOBBongNTr7e4nYn52uQUy2mfe48s50JXx2AZ6cRAt/" "xRHJ5QbEoEJOeOHsJyM4nbzwFm++SlT6gFZZHJpkXJ92JkR86uS/eV1hJUR", - uint64_t{0xed269fc3818b6aad}, uint64_t{0x1039ab644f5e150b}}, + uint64_t{0xed269fc3818b6aad}}, {"EXeHBDfhwzAKFhsMcH9+2RHwV+mJaN01+9oacF6vgm8mCXRd6jeN9U2oAb0of5c5cO4i+" "Vb/LlHZSMI490SnHU0bejhSCC2gsC5d2K30ER3iNA==", - uint64_t{0x33f253cbb8fe66a8}, uint64_t{0x7816c83f3aa05e6d}}, + uint64_t{0x33f253cbb8fe66a8}}, {"FzkzRYoNjkxFhZDso94IHRZaJUP61nFYrh5MwDwv9FNoJ5jyNCY/" "eazPZk+tbmzDyJIGw2h3GxaWZ9bSlsol/vK98SbkMKCQ/wbfrXRLcDzdd/8=", - uint64_t{0xd0b76b2c1523d99c}, uint64_t{0xf51d2f564518c619}}, + uint64_t{0xd0b76b2c1523d99c}}, {"Re4aXISCMlYY/XsX7zkIFR04ta03u4zkL9dVbLXMa/q6hlY/CImVIIYRN3VKP4pnd0AUr/" "ugkyt36JcstAInb4h9rpAGQ7GMVOgBniiMBZ/MGU7H", - uint64_t{0xfd28f0811a2a237f}, uint64_t{0x67d494cff03ac004}}, + uint64_t{0xfd28f0811a2a237f}}, {"ueLyMcqJXX+MhO4UApylCN9WlTQ+" "ltJmItgG7vFUtqs2qNwBMjmAvr5u0sAKd8jpzV0dDPTwchbIeAW5zbtkA2NABJV6hFM48ib" "4/J3A5mseA3cS8w==", - uint64_t{0x6261fb136482e84}, uint64_t{0x2802d636ced1cfbb}}, + uint64_t{0x6261fb136482e84}}, {"6Si7Yi11L+jZMkwaN+GUuzXMrlvEqviEkGOilNq0h8TdQyYKuFXzkYc/" "q74gP3pVCyiwz9KpVGMM9vfnq36riMHRknkmhQutxLZs5fbmOgEO69HglCU=", - uint64_t{0x458efc750bca7c3a}, uint64_t{0xf64e20bad771cb12}}, + uint64_t{0x458efc750bca7c3a}}, {"Q6AbOofGuTJOegPh9Clm/" "9crtUMQqylKrTc1fhfJo1tqvpXxhU4k08kntL1RG7woRnFrVh2UoMrL1kjin+s9CanT+" "y4hHwLqRranl9FjvxfVKm3yvg68", - uint64_t{0xa7e69ff84e5e7c27}, uint64_t{0xb9a6cf84a83e15e}}, + uint64_t{0xa7e69ff84e5e7c27}}, {"ieQEbIPvqY2YfIjHnqfJiO1/MIVRk0RoaG/WWi3kFrfIGiNLCczYoklgaecHMm/" "1sZ96AjO+a5stQfZbJQwS7Sc1ODABEdJKcTsxeW2hbh9A6CFzpowP1A==", - uint64_t{0x3c59bfd0c29efe9e}, uint64_t{0x8da6630319609301}}, + uint64_t{0x3c59bfd0c29efe9e}}, {"zQUv8hFB3zh2GGl3KTvCmnfzE+" "SUgQPVaSVIELFX5H9cE3FuVFGmymkPQZJLAyzC90Cmi8GqYCvPqTuAAB//" "XTJxy4bCcVArgZG9zJXpjowpNBfr3ngWrSE=", - uint64_t{0x10befacc6afd298d}, uint64_t{0x40946a86e2a996f3}}, + uint64_t{0x10befacc6afd298d}}, {"US4hcC1+op5JKGC7eIs8CUgInjKWKlvKQkapulxW262E/" "B2ye79QxOexf188u2mFwwe3WTISJHRZzS61IwljqAWAWoBAqkUnW8SHmIDwHUP31J0p5sGd" "P47L", - uint64_t{0x41d5320b0a38efa7}, uint64_t{0xcab7f5997953fa76}}, + uint64_t{0x41d5320b0a38efa7}}, {"9bHUWFna2LNaGF6fQLlkx1Hkt24nrkLE2CmFdWgTQV3FFbUe747SSqYw6ebpTa07MWSpWRP" "sHesVo2B9tqHbe7eQmqYebPDFnNqrhSdZwFm9arLQVs+7a3Ic6A==", - uint64_t{0x58db1c7450fe17f3}, uint64_t{0x39129ca0e04fc465}}, + uint64_t{0x58db1c7450fe17f3}}, {"Kb3DpHRUPhtyqgs3RuXjzA08jGb59hjKTOeFt1qhoINfYyfTt2buKhD6YVffRCPsgK9SeqZ" "qRPJSyaqsa0ovyq1WnWW8jI/NhvAkZTVHUrX2pC+cD3OPYT05Dag=", - uint64_t{0x6098c055a335b7a6}, uint64_t{0x5238221fd685e1b8}}, + uint64_t{0x6098c055a335b7a6}}, {"gzxyMJIPlU+bJBwhFUCHSofZ/" "319LxqMoqnt3+L6h2U2+ZXJCSsYpE80xmR0Ta77Jq54o92SMH87HV8dGOaCTuAYF+" "lDL42SY1P316Cl0sZTS2ow3ZqwGbcPNs/1", - uint64_t{0x1bbacec67845a801}, uint64_t{0x175130c407dbcaab}}, + uint64_t{0x1bbacec67845a801}}, {"uR7V0TW+FGVMpsifnaBAQ3IGlr1wx5sKd7TChuqRe6OvUXTlD4hKWy8S+" "8yyOw8lQabism19vOQxfmocEOW/" "vzY0pEa87qHrAZy4s9fH2Bltu8vaOIe+agYohhYORQ==", - uint64_t{0xc419cfc7442190}, uint64_t{0x2f20e7536c0b0df}}, + uint64_t{0xc419cfc7442190}}, {"1UR5eoo2aCwhacjZHaCh9bkOsITp6QunUxHQ2SfeHv0imHetzt/" "Z70mhyWZBalv6eAx+YfWKCUib2SHDtz/" "A2dc3hqUWX5VfAV7FQsghPUAtu6IiRatq4YSLpDvKZBQ=", - uint64_t{0xc95e510d94ba270c}, uint64_t{0x2742cb488a04ad56}}, + uint64_t{0xc95e510d94ba270c}}, {"opubR7H63BH7OtY+Avd7QyQ25UZ8kLBdFDsBTwZlY6gA/" "u+x+" "czC9AaZMgmQrUy15DH7YMGsvdXnviTtI4eVI4aF1H9Rl3NXMKZgwFOsdTfdcZeeHVRzBBKX" "8jUfh1il", - uint64_t{0xff1ae05c98089c3f}, uint64_t{0xd6afb593879ff93b}}, + uint64_t{0xff1ae05c98089c3f}}, {"DC0kXcSXtfQ9FbSRwirIn5tgPri0sbzHSa78aDZVDUKCMaBGyFU6BmrulywYX8yzvwprdLs" "oOwTWN2wMjHlPDqrvVHNEjnmufRDblW+nSS+xtKNs3N5xsxXdv6JXDrAB/Q==", - uint64_t{0x90c02b8dceced493}, uint64_t{0xf50ad64caac0ca7f}}, + uint64_t{0x90c02b8dceced493}}, {"BXRBk+3wEP3Lpm1y75wjoz+PgB0AMzLe8tQ1AYU2/" "oqrQB2YMC6W+9QDbcOfkGbeH+b7IBkt/" "gwCMw2HaQsRFEsurXtcQ3YwRuPz5XNaw5NAvrNa67Fm7eRzdE1+hWLKtA8=", - uint64_t{0x9f8a76697ab1aa36}, uint64_t{0x2ade95c4261364ae}}, + uint64_t{0x9f8a76697ab1aa36}}, {"RRBSvEGYnzR9E45Aps/+WSnpCo/X7gJLO4DRnUqFrJCV/kzWlusLE/" "6ZU6RoUf2ROwcgEvUiXTGjLs7ts3t9SXnJHxC1KiOzxHdYLMhVvgNd3hVSAXODpKFSkVXND" "55G2L1W", - uint64_t{0x6ba1bf3d811a531d}, uint64_t{0x5c4f3299faacd07a}}, + uint64_t{0x6ba1bf3d811a531d}}, {"jeh6Qazxmdi57pa9S3XSnnZFIRrnc6s8QLrah5OX3SB/V2ErSPoEAumavzQPkdKF1/" "SfvmdL+qgF1C+Yawy562QaFqwVGq7+tW0yxP8FStb56ZRgNI4IOmI30s1Ei7iops9Uuw==", - uint64_t{0x6a418974109c67b4}, uint64_t{0xfffe3bff0ae5e9bc}}, + uint64_t{0x6a418974109c67b4}}, {"6QO5nnDrY2/" "wrUXpltlKy2dSBcmK15fOY092CR7KxAjNfaY+" "aAmtWbbzQk3MjBg03x39afSUN1fkrWACdyQKRaGxgwq6MGNxI6W+8DLWJBHzIXrntrE/" "ml6fnNXEpxplWJ1vEs4=", - uint64_t{0x8472f1c2b3d230a3}, uint64_t{0x1db785c0005166e4}}, + uint64_t{0x8472f1c2b3d230a3}}, {"0oPxeEHhqhcFuwonNfLd5jF3RNATGZS6NPoS0WklnzyokbTqcl4BeBkMn07+fDQv83j/" "BpGUwcWO05f3+DYzocfnizpFjLJemFGsls3gxcBYxcbqWYev51tG3lN9EvRE+X9+Pwww", - uint64_t{0x5e06068f884e73a7}, uint64_t{0xea000d962ad18418}}, + uint64_t{0x5e06068f884e73a7}}, {"naSBSjtOKgAOg8XVbR5cHAW3Y+QL4Pb/JO9/" "oy6L08wvVRZqo0BrssMwhzBP401Um7A4ppAupbQeJFdMrysY34AuSSNvtNUy5VxjNECwiNt" "gwYHw7yakDUv8WvonctmnoSPKENegQg==", - uint64_t{0x55290b1a8f170f59}, uint64_t{0xe42aef38359362d9}}, + uint64_t{0x55290b1a8f170f59}}, {"vPyl8DxVeRe1OpilKb9KNwpGkQRtA94UpAHetNh+" "95V7nIW38v7PpzhnTWIml5kw3So1Si0TXtIUPIbsu32BNhoH7QwFvLM+" "JACgSpc5e3RjsL6Qwxxi11npwxRmRUqATDeMUfRAjxg=", - uint64_t{0x5501cfd83dfe706a}, uint64_t{0xc8e95657348a3891}}, + uint64_t{0x5501cfd83dfe706a}}, {"QC9i2GjdTMuNC1xQJ74ngKfrlA4w3o58FhvNCltdIpuMhHP1YsDA78scQPLbZ3OCUgeQguY" "f/vw6zAaVKSgwtaykqg5ka/4vhz4hYqWU5ficdXqClHl+zkWEY26slCNYOM5nnDlly8Cj", - uint64_t{0xe43ed13d13a66990}, uint64_t{0xc162eca864f238c6}}, + uint64_t{0xe43ed13d13a66990}}, {"7CNIgQhAHX27nxI0HeB5oUTnTdgKpRDYDKwRcXfSFGP1XeT9nQF6WKCMjL1tBV6x7KuJ91G" "Zz11F4c+8s+MfqEAEpd4FHzamrMNjGcjCyrVtU6y+7HscMVzr7Q/" "ODLcPEFztFnwjvCjmHw==", - uint64_t{0xdf43bc375cf5283f}, uint64_t{0xbe1fb373e20579ad}}, + uint64_t{0xdf43bc375cf5283f}}, {"Qa/hC2RPXhANSospe+gUaPfjdK/yhQvfm4cCV6/pdvCYWPv8p1kMtKOX3h5/" "8oZ31fsmx4Axphu5qXJokuhZKkBUJueuMpxRyXpwSWz2wELx5glxF7CM0Fn+" "OevnkhUn5jsPlG2r5jYlVn8=", - uint64_t{0x8112b806d288d7b5}, uint64_t{0x628a1d4f40aa6ffd}}, + uint64_t{0x8112b806d288d7b5}}, {"kUw/0z4l3a89jTwN5jpG0SHY5km/" "IVhTjgM5xCiPRLncg40aqWrJ5vcF891AOq5hEpSq0bUCJUMFXgct7kvnys905HjerV7Vs1G" "y84tgVJ70/2+pAZTsB/PzNOE/G6sOj4+GbTzkQu819OLB", - uint64_t{0xd52a18abb001cb46}, uint64_t{0xa87bdb7456340f90}}, + uint64_t{0xd52a18abb001cb46}}, {"VDdfSDbO8Tdj3T5W0XM3EI7iHh5xpIutiM6dvcJ/fhe23V/srFEkDy5iZf/" "VnA9kfi2C79ENnFnbOReeuZW1b3MUXB9lgC6U4pOTuC+" "jHK3Qnpyiqzj7h3ISJSuo2pob7vY6VHZo6Fn7exEqHg==", - uint64_t{0xe12b76a2433a1236}, uint64_t{0x5960ef3ba982c801}}, + uint64_t{0xe12b76a2433a1236}}, {"Ldfvy3ORdquM/R2fIkhH/ONi69mcP1AEJ6n/" "oropwecAsLJzQSgezSY8bEiEs0VnFTBBsW+RtZY6tDj03fnb3amNUOq1b7jbqyQkL9hpl+" "2Z2J8IaVSeownWl+bQcsR5/xRktIMckC5AtF4YHfU=", - uint64_t{0x175bf7319cf1fa00}, uint64_t{0x5026586df9a431ec}}, + uint64_t{0x175bf7319cf1fa00}}, {"BrbNpb42+" "VzZAjJw6QLirXzhweCVRfwlczzZ0VX2xluskwBqyfnGovz5EuX79JJ31VNXa5hTkAyQat3l" "YKRADTdAdwE5PqM1N7YaMqqsqoAAAeuYVXuk5eWCykYmClNdSspegwgCuT+403JigBzi", - uint64_t{0xd63d57b3f67525ae}, uint64_t{0xfe4b8a20fdf0840b}}, + uint64_t{0xd63d57b3f67525ae}}, {"gB3NGHJJvVcuPyF0ZSvHwnWSIfmaI7La24VMPQVoIIWF7Z74NltPZZpx2f+cocESM+" "ILzQW9p+BC8x5IWz7N4Str2WLGKMdgmaBfNkEhSHQDU0IJEOnpUt0HmjhFaBlx0/" "LTmhua+rQ6Wup8ezLwfg==", - uint64_t{0x933faea858832b73}, uint64_t{0xdcb761867da7072f}}, + uint64_t{0x933faea858832b73}}, {"hTKHlRxx6Pl4gjG+6ksvvj0CWFicUg3WrPdSJypDpq91LUWRni2KF6+" "81ZoHBFhEBrCdogKqeK+hy9bLDnx7g6rAFUjtn1+cWzQ2YjiOpz4+" "ROBB7lnwjyTGWzJD1rXtlso1g2qVH8XJVigC5M9AIxM=", - uint64_t{0x53d061e5f8e7c04f}, uint64_t{0xc10d4653667275b7}}, + uint64_t{0x53d061e5f8e7c04f}}, {"IWQBelSQnhrr0F3BhUpXUIDauhX6f95Qp+A0diFXiUK7irwPG1oqBiqHyK/SH/" "9S+" "rln9DlFROAmeFdH0OCJi2tFm4afxYzJTFR4HnR4cG4x12JqHaZLQx6iiu6CE3rtWBVz99oA" "wCZUOEXIsLU24o2Y", - uint64_t{0xdb4124556dd515e0}, uint64_t{0x727720deec13110b}}, + uint64_t{0xdb4124556dd515e0}}, {"TKo+l+" "1dOXdLvIrFqeLaHdm0HZnbcdEgOoLVcGRiCbAMR0j5pIFw8D36tefckAS1RCFOH5IgP8yiF" "T0Gd0a2hI3+" "fTKA7iK96NekxWeoeqzJyctc6QsoiyBlkZerRxs5RplrxoeNg29kKDTM0K94mnhD9g==", - uint64_t{0x4fb31a0dd681ee71}, uint64_t{0x710b009662858dc9}}, + uint64_t{0x4fb31a0dd681ee71}}, {"YU4e7G6EfQYvxCFoCrrT0EFgVLHFfOWRTJQJ5gxM3G2b+" "1kJf9YPrpsxF6Xr6nYtS8reEEbDoZJYqnlk9lXSkVArm88Cqn6d25VCx3+" "49MqC0trIlXtb7SXUUhwpJK16T0hJUfPH7s5cMZXc6YmmbFuBNPE=", - uint64_t{0x27cc72eefa138e4c}, uint64_t{0xfbf8f7a3ecac1eb7}}, + uint64_t{0x27cc72eefa138e4c}}, {"/I/" "eImMwPo1U6wekNFD1Jxjk9XQVi1D+" "FPdqcHifYXQuP5aScNQfxMAmaPR2XhuOQhADV5tTVbBKwCDCX4E3jcDNHzCiPvViZF1W27t" "xaf2BbFQdwKrNCmrtzcluBFYu0XZfc7RU1RmxK/RtnF1qHsq/O4pp", - uint64_t{0x44bc2dfba4bd3ced}, uint64_t{0xb6fc4fcd0722e3df}}, + uint64_t{0x44bc2dfba4bd3ced}}, {"CJTT9WGcY2XykTdo8KodRIA29qsqY0iHzWZRjKHb9alwyJ7RZAE3V5Juv4MY3MeYEr1EPCC" "MxO7yFXqT8XA8YTjaMp3bafRt17Pw8JC4iKJ1zN+WWKOESrj+" "3aluGQqn8z1EzqY4PH7rLG575PYeWsP98BugdA==", - uint64_t{0x242da1e3a439bed8}, uint64_t{0x7cb86dcc55104aac}}, + uint64_t{0x242da1e3a439bed8}}, {"ZlhyQwLhXQyIUEnMH/" "AEW27vh9xrbNKJxpWGtrEmKhd+nFqAfbeNBQjW0SfG1YI0xQkQMHXjuTt4P/" "EpZRtA47ibZDVS8TtaxwyBjuIDwqcN09eCtpC+Ls+" "vWDTLmBeDM3u4hmzz4DQAYsLiZYSJcldg9Q3wszw=", - uint64_t{0xdc559c746e35c139}, uint64_t{0x19e71e9b45c3a51e}}, + uint64_t{0xdc559c746e35c139}}, {"v2KU8y0sCrBghmnm8lzGJlwo6D6ObccAxCf10heoDtYLosk4ztTpLlpSFEyu23MLA1tJkcg" "Rko04h19QMG0mOw/" "wc93EXAweriBqXfvdaP85sZABwiKO+6rtS9pacRVpYYhHJeVTQ5NzrvBvi1huxAr+" "xswhVMfL", - uint64_t{0xd0b0350275b9989}, uint64_t{0x51de38573c2bea48}}, + uint64_t{0xd0b0350275b9989}}, {"QhKlnIS6BuVCTQsnoE67E/" "yrgogE8EwO7xLaEGei26m0gEU4OksefJgppDh3X0x0Cs78Dr9IHK5b977CmZlrTRmwhlP8p" "M+UzXPNRNIZuN3ntOum/QhUWP8SGpirheXENWsXMQ/" "nxtxakyEtrNkKk471Oov9juP8oQ==", - uint64_t{0xb04489e41d17730c}, uint64_t{0xa73ab6996d6df158}}, + uint64_t{0xb04489e41d17730c}}, {"/ZRMgnoRt+Uo6fUPr9FqQvKX7syhgVqWu+" "WUSsiQ68UlN0efSP6Eced5gJZL6tg9gcYJIkhjuQNITU0Q3TjVAnAcobgbJikCn6qZ6pRxK" "BY4MTiAlfGD3T7R7hwJwx554MAy++Zb/YUFlnCaCJiwQMnowF7aQzwYFCo=", - uint64_t{0x2217285eb4572156}, uint64_t{0x55ef2b8c930817b2}}, + uint64_t{0x2217285eb4572156}}, {"NB7tU5fNE8nI+SXGfipc7sRkhnSkUF1krjeo6k+8FITaAtdyz+" "o7mONgXmGLulBPH9bEwyYhKNVY0L+njNQrZ9YC2aXsFD3PdZsxAFaBT3VXEzh+" "NGBTjDASNL3mXyS8Yv1iThGfHoY7T4aR0NYGJ+k+pR6f+KrPC96M", - uint64_t{0x12c2e8e68aede73b}, uint64_t{0xb2850bf5fae87157}}, + uint64_t{0x12c2e8e68aede73b}}, {"8T6wrqCtEO6/rwxF6lvMeyuigVOLwPipX/FULvwyu+1wa5sQGav/" "2FsLHUVn6cGSi0LlFwLewGHPFJDLR0u4t7ZUyM//" "x6da0sWgOa5hzDqjsVGmjxEHXiaXKW3i4iSZNuxoNbMQkIbVML+" "DkYu9ND0O2swg4itGeVSzXA==", - uint64_t{0x4d612125bdc4fd00}, uint64_t{0xecf3de1acd04651f}}, + uint64_t{0x4d612125bdc4fd00}}, {"Ntf1bMRdondtMv1CYr3G80iDJ4WSAlKy5H34XdGruQiCrnRGDBa+" "eUi7vKp4gp3BBcVGl8eYSasVQQjn7MLvb3BjtXx6c/" "bCL7JtpzQKaDnPr9GWRxpBXVxKREgMM7d8lm35EODv0w+" "hQLfVSh8OGs7fsBb68nNWPLeeSOo=", - uint64_t{0x81826b553954464e}, uint64_t{0xcc0a40552559ff32}}, + uint64_t{0x81826b553954464e}}, {"VsSAw72Ro6xks02kaiLuiTEIWBC5bgqr4WDnmP8vglXzAhixk7td926rm9jNimL+" "kroPSygZ9gl63aF5DCPOACXmsbmhDrAQuUzoh9ZKhWgElLQsrqo1KIjWoZT5b5QfVUXY9lS" "IBg3U75SqORoTPq7HalxxoIT5diWOcJQi", - uint64_t{0xc2e5d345dc0ddd2d}, uint64_t{0xc385c374f20315b1}}, + uint64_t{0xc2e5d345dc0ddd2d}}, {"j+loZ+C87+" "bJxNVebg94gU0mSLeDulcHs84tQT7BZM2rzDSLiCNxUedHr1ZWJ9ejTiBa0dqy2I2ABc++" "xzOLcv+//YfibtjKtYggC6/3rv0XCc7xu6d/" "O6xO+XOBhOWAQ+IHJVHf7wZnDxIXB8AUHsnjEISKj7823biqXjyP3g==", - uint64_t{0x3da6830a9e32631e}, uint64_t{0xb90208a4c7234183}}, + uint64_t{0x3da6830a9e32631e}}, {"f3LlpcPElMkspNtDq5xXyWU62erEaKn7RWKlo540gR6mZsNpK1czV/" "sOmqaq8XAQLEn68LKj6/" "cFkJukxRzCa4OF1a7cCAXYFp9+wZDu0bw4y63qbpjhdCl8GO6Z2lkcXy7KOzbPE01ukg7+" "gN+7uKpoohgAhIwpAKQXmX5xtd0=", - uint64_t{0xc9ae5c8759b4877a}, uint64_t{0x58aa1ca7a4c075d9}}, + uint64_t{0xc9ae5c8759b4877a}}, + }; + +#if defined(__aarch64__) + constexpr uint64_t kGolden[kNumGoldenOutputs] = { + 0x45c0aadee165dcbe, 0x25ed8587f6f20d06, 0x5f23ae668ce7926d, + 0xfef74d1da0846719, 0x54478408e68cb7d4, 0xee27ddaf88c6fe68, + 0xb7ac7031e81867ca, 0xf1168f818ec6c36d, 0x1dd0b734a83b019a, + 0xd6ae30d4142b54fe, 0xcd860c721ccb80fb, 0x068acf8493794756, + 0xd4ada0be58681307, 0x13ffe0f64ca540ed, 0xffc1d7a3401aec02, + 0xd81c4d865cf95fb9, 0x1dd0793acede62e0, 0xa6722abbca8fe4cf, + 0x5453d3e4111a7e40, 0xf29b3e3204c9dcd2, 0x23be2980e43117f7, + 0x74e2ccbc286f08eb, 0x19ef7c0f9496003a, 0xbfbf1c3e49b27987, + 0x6e6c179eb4a82c70, 0x07f4e184216bc4fc, 0xf17fbc4254927554, + 0xe57696b70a45b1b6, 0x6d3b144631b320e8, 0xccf8729792c75a2d, + 0xe832495b41fa980b, 0x5c96cfdc7b227d34, 0xc4dca234ef4e43f4, + 0x5fc801abf9abe307, 0xe41e3c5076d88f4d, 0x522346200ddec3c3, + 0x72bed1946fd7aaa4, 0x0ac1f84dcc335f96, 0x3af78db5e0a47670, + 0x6100ebf1481f1caf, 0xf5fd10037fc651a3, 0xa01227d8944665f3, + 0x7217681c4bbc9420, 0x4adee538e3eb10d1, 0x35e1761ad96de9a7, + 0x8b370aef9613bfba, 0x824506f749eeaf59, 0x85e805fa04423991, + 0xb61e9c33283c3de7, 0xc79721bbcb039ed6, 0x04e1c19a3a1e6639, + 0x6aaf6346b68dd638, 0x601a4b496be6d0c4, 0x3ece355f91c41787, + 0xd2fc8998448d7888, 0xd7529804f843efa9, 0xabdcc38a288536aa, + 0xdd323e48a9718648, 0x2090279c0030a52a, 0xe2f90faca88a3cd1, + 0x3e0c4e92fc50e4aa, 0xa26d308798e801dd, 0x432eefeedee8c02e, + 0xca4ce494614b77df, 0xbba82911e838066d, 0x4b00821016adee4b, + 0x4cf6e526dfb5a20f, 0x5b8466495142cba2, 0xe28ac1406e88a68c, + 0x8511e5f9d3100999, 0x05acbfe02798890b, 0x74c249c7ce4a8425, + 0xdbe7468d09bc34bc, 0x11079ab10e3b9b58, 0xb7788dec9032035a, + 0xb7e8daa786513f80, 0x34c3288831f46b45, 0x014cce5f0c21ecc6, + 0xc6a8f7b024551a28, 0x49784e902e207fd8, 0x4720d32af0b55158, + 0x8df3ec5de0c1da00, 0xf4db677b2c9e6853, 0xaa419abea78d312d, + 0x181e0f91bd757443, 0xa8c45136fada083b, 0x91303b93f5f0582c, + 0x883b95c6ddc62a08, 0x93186a8875fe952b, 0xd94f533928e957e2, + 0x6ba343003e10c172, 0xc8623b620c715d6a, 0x8ca0c512e180e244, + 0xdc9b74c2536b6216, 0x8eb5fdc61b295d96, 0x2ad83966b37c95ba, + 0xb90bf154ac5edec9, 0x902cf847b326cfb3, 0x7b02d0c0ca7808ca, + 0x492f310d003ea15f, 0x3eb6497a47c95990, 0x5d46b0ced31428b7, + 0x081afa67d1986157, 0x043482ec286b20eb, 0xc103c8f18c1a2a53, + 0xe8e9995a81481e83, 0x6bb3295822bc90b5, 0xeec75297a3fa5672, + 0x591c8440c4857412, 0x74947f455aaf24ad, 0xcf0e571586ec77a9, + 0x0c2553ea8c0400ad, 0x380219118066255f, 0x7595adb88b15ebe2, + 0xb33c00696c64ae23, 0xa143516ddd7c9857, 0x39179af229248d26, + 0x65d387a6f2ee2079, 0x89f8a9b21cd2f195, 0xbfef032d25df92e6, + 0x6b7e18a36c69da71, 0x4b3b15f6c28974e6, 0x032a75917f6c544c, + 0xe3b97ecca6d287cd, 0xa4a563110d3cda81, 0x35e09e8134f4e7f1, + 0xc9419dd03a9a390e, 0x7b86fae9000fd329, 0x1e044f8d54fe74c3, + 0x9c4991d7a47e9666, 0xfb485f3a1df4fdb6, 0xb11519969eeb94ff, + 0x3224ea1c44caeb8d, 0x86570bbd7cc6b80d, }; +#else + constexpr uint64_t kGolden[kNumGoldenOutputs] = { + 0xe5a40d39ab796423, 0x1766974bf7527d81, 0x5c3bbbe230db17a8, + 0xa6630143a7e6aa6f, 0x8787cb2d04b0c984, 0x33603654ff574ac2, + 0xa6564b468248c683, 0xef192f401b116e1c, 0xbe8dc0c54617639d, + 0x93d7f665b5521c8e, 0x646d70bb42445f28, 0x96a7b1e3cc9bd426, + 0x76020289ab0790c4, 0x39f842e4133b9b44, 0x2b8d7047be4bcaab, + 0x99628abef6716a97, 0x4432e02ba42b2740, 0x74d810efcad7918a, + 0x88c84e986002507f, 0x4f99acf193cf39b9, 0xd90e7a3655891e37, + 0x3bb378b1d4df8fcf, 0xf78e94045c052d47, 0x26da0b2130da6b40, + 0x30b4d426af8c6986, 0x5413b4aaf3baaeae, 0x756ab265370a1597, + 0xdaf5f4b7d09814fb, 0x8f874ae37742b75e, 0x8fecd03956121ce8, + 0x229c292ea7a08285, 0x0bb4bf0692d14bae, 0x207b24ca3bdac1db, + 0x64f6cd6745d3825b, 0xa2b2e1656b58df1e, 0x0d01d30d9ee7a148, + 0x1cb4cd00ab804e3b, 0x4697f2637fd90999, 0x8383a756b5688c07, + 0x695c29cb3696a975, 0xda2e5a5a5e971521, 0x7935d4befa056b2b, + 0x38dd541ca95420fe, 0xcc06c7a4963f967f, 0xbf0f6f66e232fb20, + 0xf7efb32d373fe71a, 0xe2e64634b1c12660, 0x285b8fd1638e306d, + 0x658e8a4e3b714d6c, 0xf391fb968e0eb398, 0x744a9ea0cc144bf2, + 0x12636f2be11012f1, 0x29c57de825948f80, 0x58c6f99ab0d1c021, + 0x13e7b5a7b82fe3bb, 0x10fbc87901e02b63, 0xa24c9184901b748b, + 0xcac4fd4c5080e581, 0xc38bdb7483ba68e1, 0xdb2a8069b2ceaffa, + 0xdf9fe91d0d1c7887, 0xe83f49e96e2e6a08, 0x0c69e61b62ca2b62, + 0xb4a4f3f85f8298fe, 0x167a1b39e1e95f41, 0xf8a2a5649855ee41, + 0x27992565b595c498, 0x3e08cca5b71f9346, 0xad406b10c770a6d2, + 0xd1713ce6e552bcf2, 0x753b287194c73ad3, 0x5ae41a95f600af1c, + 0x4a61163b86a8bb4c, 0x42eeaa79e760c7e4, 0x698df622ef465b0a, + 0x157583111e1a6026, 0xaa1388f078e793e0, 0xf10d68d0f3309360, + 0x2af056184457a3de, 0x6d0058e1590b2489, 0x638f287f68817f12, + 0xc46b71fecefd5467, 0x2c8e94679d964e0a, 0x8612b797ce22503a, + 0x59f929babfba7170, 0x9527556923fb49a0, 0x1039ab644f5e150b, + 0x7816c83f3aa05e6d, 0xf51d2f564518c619, 0x67d494cff03ac004, + 0x2802d636ced1cfbb, 0xf64e20bad771cb12, 0x0b9a6cf84a83e15e, + 0x8da6630319609301, 0x40946a86e2a996f3, 0xcab7f5997953fa76, + 0x39129ca0e04fc465, 0x5238221fd685e1b8, 0x175130c407dbcaab, + 0x02f20e7536c0b0df, 0x2742cb488a04ad56, 0xd6afb593879ff93b, + 0xf50ad64caac0ca7f, 0x2ade95c4261364ae, 0x5c4f3299faacd07a, + 0xfffe3bff0ae5e9bc, 0x1db785c0005166e4, 0xea000d962ad18418, + 0xe42aef38359362d9, 0xc8e95657348a3891, 0xc162eca864f238c6, + 0xbe1fb373e20579ad, 0x628a1d4f40aa6ffd, 0xa87bdb7456340f90, + 0x5960ef3ba982c801, 0x5026586df9a431ec, 0xfe4b8a20fdf0840b, + 0xdcb761867da7072f, 0xc10d4653667275b7, 0x727720deec13110b, + 0x710b009662858dc9, 0xfbf8f7a3ecac1eb7, 0xb6fc4fcd0722e3df, + 0x7cb86dcc55104aac, 0x19e71e9b45c3a51e, 0x51de38573c2bea48, + 0xa73ab6996d6df158, 0x55ef2b8c930817b2, 0xb2850bf5fae87157, + 0xecf3de1acd04651f, 0xcc0a40552559ff32, 0xc385c374f20315b1, + 0xb90208a4c7234183, 0x58aa1ca7a4c075d9, + }; +#endif - for (const auto& expected_result : expected_results) { +#if UPDATE_GOLDEN + (void)kGolden; // Silence warning. + for (size_t i = 0; i < kNumGoldenOutputs; ++i) { + std::string str; + ASSERT_TRUE(absl::Base64Unescape(cases[i].base64_data, &str)); + uint64_t h = absl::hash_internal::LowLevelHash(str.data(), str.size(), + cases[i].seed, kSalt); + printf("0x%016" PRIx64 ", ", h); + if (i % 3 == 2) { + printf("\n"); + } + } + printf("\n\n\n"); + EXPECT_FALSE(true); +#else + for (size_t i = 0; i < kNumGoldenOutputs; ++i) { + SCOPED_TRACE(::testing::Message() + << "i = " << i << "; input = " << cases[i].base64_data); std::string str; - ASSERT_TRUE(absl::Base64Unescape(expected_result.base64_data, &str)); + ASSERT_TRUE(absl::Base64Unescape(cases[i].base64_data, &str)); EXPECT_EQ(absl::hash_internal::LowLevelHash(str.data(), str.size(), - expected_result.seed, kSalt), - expected_result.hash); + cases[i].seed, kSalt), + kGolden[i]); } +#endif } } // namespace diff --git a/absl/numeric/int128.h b/absl/numeric/int128.h index a9cbe489..c7ad96be 100644 --- a/absl/numeric/int128.h +++ b/absl/numeric/int128.h @@ -586,10 +586,10 @@ inline uint128& uint128::operator=(int128 v) { // Arithmetic operators. -uint128 operator<<(uint128 lhs, int amount); -uint128 operator>>(uint128 lhs, int amount); -uint128 operator+(uint128 lhs, uint128 rhs); -uint128 operator-(uint128 lhs, uint128 rhs); +constexpr uint128 operator<<(uint128 lhs, int amount); +constexpr uint128 operator>>(uint128 lhs, int amount); +constexpr uint128 operator+(uint128 lhs, uint128 rhs); +constexpr uint128 operator-(uint128 lhs, uint128 rhs); uint128 operator*(uint128 lhs, uint128 rhs); uint128 operator/(uint128 lhs, uint128 rhs); uint128 operator%(uint128 lhs, uint128 rhs); @@ -786,7 +786,7 @@ inline uint128::operator long double() const { // Comparison operators. -inline bool operator==(uint128 lhs, uint128 rhs) { +constexpr bool operator==(uint128 lhs, uint128 rhs) { #if defined(ABSL_HAVE_INTRINSIC_INT128) return static_cast<unsigned __int128>(lhs) == static_cast<unsigned __int128>(rhs); @@ -796,11 +796,9 @@ inline bool operator==(uint128 lhs, uint128 rhs) { #endif } -inline bool operator!=(uint128 lhs, uint128 rhs) { - return !(lhs == rhs); -} +constexpr bool operator!=(uint128 lhs, uint128 rhs) { return !(lhs == rhs); } -inline bool operator<(uint128 lhs, uint128 rhs) { +constexpr bool operator<(uint128 lhs, uint128 rhs) { #ifdef ABSL_HAVE_INTRINSIC_INT128 return static_cast<unsigned __int128>(lhs) < static_cast<unsigned __int128>(rhs); @@ -811,11 +809,11 @@ inline bool operator<(uint128 lhs, uint128 rhs) { #endif } -inline bool operator>(uint128 lhs, uint128 rhs) { return rhs < lhs; } +constexpr bool operator>(uint128 lhs, uint128 rhs) { return rhs < lhs; } -inline bool operator<=(uint128 lhs, uint128 rhs) { return !(rhs < lhs); } +constexpr bool operator<=(uint128 lhs, uint128 rhs) { return !(rhs < lhs); } -inline bool operator>=(uint128 lhs, uint128 rhs) { return !(lhs < rhs); } +constexpr bool operator>=(uint128 lhs, uint128 rhs) { return !(lhs < rhs); } // Unary operators. @@ -827,14 +825,13 @@ constexpr inline int128 operator+(int128 val) { return val; } -inline uint128 operator-(uint128 val) { +constexpr uint128 operator-(uint128 val) { #if defined(ABSL_HAVE_INTRINSIC_INT128) return -static_cast<unsigned __int128>(val); #else - uint64_t hi = ~Uint128High64(val); - uint64_t lo = ~Uint128Low64(val) + 1; - if (lo == 0) ++hi; // carry - return MakeUint128(hi, lo); + return MakeUint128( + ~Uint128High64(val) + static_cast<unsigned long>(Uint128Low64(val) == 0), + ~Uint128Low64(val) + 1); #endif } @@ -903,67 +900,77 @@ inline uint128& uint128::operator^=(uint128 other) { // Arithmetic operators. -inline uint128 operator<<(uint128 lhs, int amount) { +constexpr uint128 operator<<(uint128 lhs, int amount) { #ifdef ABSL_HAVE_INTRINSIC_INT128 return static_cast<unsigned __int128>(lhs) << amount; #else // uint64_t shifts of >= 64 are undefined, so we will need some // special-casing. - if (amount < 64) { - if (amount != 0) { - return MakeUint128( - (Uint128High64(lhs) << amount) | (Uint128Low64(lhs) >> (64 - amount)), - Uint128Low64(lhs) << amount); - } - return lhs; - } - return MakeUint128(Uint128Low64(lhs) << (amount - 64), 0); + return amount >= 64 ? MakeUint128(Uint128Low64(lhs) << (amount - 64), 0) + : amount == 0 ? lhs + : MakeUint128((Uint128High64(lhs) << amount) | + (Uint128Low64(lhs) >> (64 - amount)), + Uint128Low64(lhs) << amount); #endif } -inline uint128 operator>>(uint128 lhs, int amount) { +constexpr uint128 operator>>(uint128 lhs, int amount) { #ifdef ABSL_HAVE_INTRINSIC_INT128 return static_cast<unsigned __int128>(lhs) >> amount; #else // uint64_t shifts of >= 64 are undefined, so we will need some // special-casing. - if (amount < 64) { - if (amount != 0) { - return MakeUint128(Uint128High64(lhs) >> amount, - (Uint128Low64(lhs) >> amount) | - (Uint128High64(lhs) << (64 - amount))); - } - return lhs; - } - return MakeUint128(0, Uint128High64(lhs) >> (amount - 64)); + return amount >= 64 ? MakeUint128(0, Uint128High64(lhs) >> (amount - 64)) + : amount == 0 ? lhs + : MakeUint128(Uint128High64(lhs) >> amount, + (Uint128Low64(lhs) >> amount) | + (Uint128High64(lhs) << (64 - amount))); #endif } -inline uint128 operator+(uint128 lhs, uint128 rhs) { +#if !defined(ABSL_HAVE_INTRINSIC_INT128) +namespace int128_internal { +constexpr uint128 AddResult(uint128 result, uint128 lhs) { + // check for carry + return (Uint128Low64(result) < Uint128Low64(lhs)) + ? MakeUint128(Uint128High64(result) + 1, Uint128Low64(result)) + : result; +} +} // namespace int128_internal +#endif + +constexpr uint128 operator+(uint128 lhs, uint128 rhs) { #if defined(ABSL_HAVE_INTRINSIC_INT128) return static_cast<unsigned __int128>(lhs) + static_cast<unsigned __int128>(rhs); #else - uint128 result = MakeUint128(Uint128High64(lhs) + Uint128High64(rhs), - Uint128Low64(lhs) + Uint128Low64(rhs)); - if (Uint128Low64(result) < Uint128Low64(lhs)) { // check for carry - return MakeUint128(Uint128High64(result) + 1, Uint128Low64(result)); - } - return result; + return int128_internal::AddResult( + MakeUint128(Uint128High64(lhs) + Uint128High64(rhs), + Uint128Low64(lhs) + Uint128Low64(rhs)), + lhs); #endif } -inline uint128 operator-(uint128 lhs, uint128 rhs) { +#if !defined(ABSL_HAVE_INTRINSIC_INT128) +namespace int128_internal { +constexpr uint128 SubstructResult(uint128 result, uint128 lhs, uint128 rhs) { + // check for carry + return (Uint128Low64(lhs) < Uint128Low64(rhs)) + ? MakeUint128(Uint128High64(result) - 1, Uint128Low64(result)) + : result; +} +} // namespace int128_internal +#endif + +constexpr uint128 operator-(uint128 lhs, uint128 rhs) { #if defined(ABSL_HAVE_INTRINSIC_INT128) return static_cast<unsigned __int128>(lhs) - static_cast<unsigned __int128>(rhs); #else - uint128 result = MakeUint128(Uint128High64(lhs) - Uint128High64(rhs), - Uint128Low64(lhs) - Uint128Low64(rhs)); - if (Uint128Low64(lhs) < Uint128Low64(rhs)) { // check for carry - return MakeUint128(Uint128High64(result) - 1, Uint128Low64(result)); - } - return result; + return int128_internal::SubstructResult( + MakeUint128(Uint128High64(lhs) - Uint128High64(rhs), + Uint128Low64(lhs) - Uint128Low64(rhs)), + lhs, rhs); #endif } @@ -1063,17 +1070,17 @@ inline int128& int128::operator=(unsigned long long v) { } // Arithmetic operators. - -int128 operator+(int128 lhs, int128 rhs); -int128 operator-(int128 lhs, int128 rhs); +constexpr int128 operator-(int128 v); +constexpr int128 operator+(int128 lhs, int128 rhs); +constexpr int128 operator-(int128 lhs, int128 rhs); int128 operator*(int128 lhs, int128 rhs); int128 operator/(int128 lhs, int128 rhs); int128 operator%(int128 lhs, int128 rhs); -int128 operator|(int128 lhs, int128 rhs); -int128 operator&(int128 lhs, int128 rhs); -int128 operator^(int128 lhs, int128 rhs); -int128 operator<<(int128 lhs, int amount); -int128 operator>>(int128 lhs, int amount); +constexpr int128 operator|(int128 lhs, int128 rhs); +constexpr int128 operator&(int128 lhs, int128 rhs); +constexpr int128 operator^(int128 lhs, int128 rhs); +constexpr int128 operator<<(int128 lhs, int amount); +constexpr int128 operator>>(int128 lhs, int amount); inline int128& int128::operator+=(int128 other) { *this = *this + other; @@ -1125,6 +1132,9 @@ inline int128& int128::operator>>=(int amount) { return *this; } +// Forward declaration for comparison operators. +constexpr bool operator!=(int128 lhs, int128 rhs); + namespace int128_internal { // Casts from unsigned to signed while preserving the underlying binary diff --git a/absl/numeric/int128_have_intrinsic.inc b/absl/numeric/int128_have_intrinsic.inc index d6c76dd3..3945fa29 100644 --- a/absl/numeric/int128_have_intrinsic.inc +++ b/absl/numeric/int128_have_intrinsic.inc @@ -155,7 +155,7 @@ constexpr int128::operator unsigned __int128() const { #if defined(__clang__) && !defined(__ppc64__) inline int128::operator float() const { return static_cast<float>(v_); } -inline int128::operator double () const { return static_cast<double>(v_); } +inline int128::operator double() const { return static_cast<double>(v_); } inline int128::operator long double() const { return static_cast<long double>(v_); @@ -163,8 +163,8 @@ inline int128::operator long double() const { #else // Clang on PowerPC // Forward declaration for conversion operators to floating point types. -int128 operator-(int128 v); -bool operator!=(int128 lhs, int128 rhs); +constexpr int128 operator-(int128 v); +constexpr bool operator!=(int128 lhs, int128 rhs); inline int128::operator float() const { // We must convert the absolute value and then negate as needed, because @@ -199,51 +199,45 @@ inline int128::operator long double() const { // Comparison operators. -inline bool operator==(int128 lhs, int128 rhs) { +constexpr bool operator==(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) == static_cast<__int128>(rhs); } -inline bool operator!=(int128 lhs, int128 rhs) { +constexpr bool operator!=(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) != static_cast<__int128>(rhs); } -inline bool operator<(int128 lhs, int128 rhs) { +constexpr bool operator<(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) < static_cast<__int128>(rhs); } -inline bool operator>(int128 lhs, int128 rhs) { +constexpr bool operator>(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) > static_cast<__int128>(rhs); } -inline bool operator<=(int128 lhs, int128 rhs) { +constexpr bool operator<=(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) <= static_cast<__int128>(rhs); } -inline bool operator>=(int128 lhs, int128 rhs) { +constexpr bool operator>=(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) >= static_cast<__int128>(rhs); } // Unary operators. -inline int128 operator-(int128 v) { - return -static_cast<__int128>(v); -} +constexpr int128 operator-(int128 v) { return -static_cast<__int128>(v); } -inline bool operator!(int128 v) { - return !static_cast<__int128>(v); -} +constexpr bool operator!(int128 v) { return !static_cast<__int128>(v); } -inline int128 operator~(int128 val) { - return ~static_cast<__int128>(val); -} +constexpr int128 operator~(int128 val) { return ~static_cast<__int128>(val); } // Arithmetic operators. -inline int128 operator+(int128 lhs, int128 rhs) { +constexpr int128 operator+(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) + static_cast<__int128>(rhs); } -inline int128 operator-(int128 lhs, int128 rhs) { +constexpr int128 operator-(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) - static_cast<__int128>(rhs); } @@ -281,22 +275,22 @@ inline int128& int128::operator--() { return *this; } -inline int128 operator|(int128 lhs, int128 rhs) { +constexpr int128 operator|(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) | static_cast<__int128>(rhs); } -inline int128 operator&(int128 lhs, int128 rhs) { +constexpr int128 operator&(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) & static_cast<__int128>(rhs); } -inline int128 operator^(int128 lhs, int128 rhs) { +constexpr int128 operator^(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) ^ static_cast<__int128>(rhs); } -inline int128 operator<<(int128 lhs, int amount) { +constexpr int128 operator<<(int128 lhs, int amount) { return static_cast<__int128>(lhs) << amount; } -inline int128 operator>>(int128 lhs, int amount) { +constexpr int128 operator>>(int128 lhs, int amount) { return static_cast<__int128>(lhs) >> amount; } diff --git a/absl/numeric/int128_no_intrinsic.inc b/absl/numeric/int128_no_intrinsic.inc index c753771a..66f6809f 100644 --- a/absl/numeric/int128_no_intrinsic.inc +++ b/absl/numeric/int128_no_intrinsic.inc @@ -134,10 +134,6 @@ constexpr int128::operator unsigned long long() const { // NOLINT(runtime/int) return static_cast<unsigned long long>(lo_); // NOLINT(runtime/int) } -// Forward declaration for conversion operators to floating point types. -int128 operator-(int128 v); -bool operator!=(int128 lhs, int128 rhs); - inline int128::operator float() const { // We must convert the absolute value and then negate as needed, because // floating point types are typically sign-magnitude. Otherwise, the @@ -169,76 +165,80 @@ inline int128::operator long double() const { // Comparison operators. -inline bool operator==(int128 lhs, int128 rhs) { +constexpr bool operator==(int128 lhs, int128 rhs) { return (Int128Low64(lhs) == Int128Low64(rhs) && Int128High64(lhs) == Int128High64(rhs)); } -inline bool operator!=(int128 lhs, int128 rhs) { - return !(lhs == rhs); -} +constexpr bool operator!=(int128 lhs, int128 rhs) { return !(lhs == rhs); } -inline bool operator<(int128 lhs, int128 rhs) { +constexpr bool operator<(int128 lhs, int128 rhs) { return (Int128High64(lhs) == Int128High64(rhs)) ? (Int128Low64(lhs) < Int128Low64(rhs)) : (Int128High64(lhs) < Int128High64(rhs)); } -inline bool operator>(int128 lhs, int128 rhs) { +constexpr bool operator>(int128 lhs, int128 rhs) { return (Int128High64(lhs) == Int128High64(rhs)) ? (Int128Low64(lhs) > Int128Low64(rhs)) : (Int128High64(lhs) > Int128High64(rhs)); } -inline bool operator<=(int128 lhs, int128 rhs) { - return !(lhs > rhs); -} +constexpr bool operator<=(int128 lhs, int128 rhs) { return !(lhs > rhs); } -inline bool operator>=(int128 lhs, int128 rhs) { - return !(lhs < rhs); -} +constexpr bool operator>=(int128 lhs, int128 rhs) { return !(lhs < rhs); } // Unary operators. -inline int128 operator-(int128 v) { - int64_t hi = ~Int128High64(v); - uint64_t lo = ~Int128Low64(v) + 1; - if (lo == 0) ++hi; // carry - return MakeInt128(hi, lo); +constexpr int128 operator-(int128 v) { + return MakeInt128(~Int128High64(v) + (Int128Low64(v) == 0), + ~Int128Low64(v) + 1); } -inline bool operator!(int128 v) { +constexpr bool operator!(int128 v) { return !Int128Low64(v) && !Int128High64(v); } -inline int128 operator~(int128 val) { +constexpr int128 operator~(int128 val) { return MakeInt128(~Int128High64(val), ~Int128Low64(val)); } // Arithmetic operators. -inline int128 operator+(int128 lhs, int128 rhs) { - int128 result = MakeInt128(Int128High64(lhs) + Int128High64(rhs), - Int128Low64(lhs) + Int128Low64(rhs)); - if (Int128Low64(result) < Int128Low64(lhs)) { // check for carry - return MakeInt128(Int128High64(result) + 1, Int128Low64(result)); - } - return result; +namespace int128_internal { +constexpr int128 SignedAddResult(int128 result, int128 lhs) { + // check for carry + return (Int128Low64(result) < Int128Low64(lhs)) + ? MakeInt128(Int128High64(result) + 1, Int128Low64(result)) + : result; +} +} // namespace int128_internal +constexpr int128 operator+(int128 lhs, int128 rhs) { + return int128_internal::SignedAddResult( + MakeInt128(Int128High64(lhs) + Int128High64(rhs), + Int128Low64(lhs) + Int128Low64(rhs)), + lhs); } -inline int128 operator-(int128 lhs, int128 rhs) { - int128 result = MakeInt128(Int128High64(lhs) - Int128High64(rhs), - Int128Low64(lhs) - Int128Low64(rhs)); - if (Int128Low64(lhs) < Int128Low64(rhs)) { // check for carry - return MakeInt128(Int128High64(result) - 1, Int128Low64(result)); - } - return result; +namespace int128_internal { +constexpr int128 SignedSubstructResult(int128 result, int128 lhs, int128 rhs) { + // check for carry + return (Int128Low64(lhs) < Int128Low64(rhs)) + ? MakeInt128(Int128High64(result) - 1, Int128Low64(result)) + : result; +} +} // namespace int128_internal +constexpr int128 operator-(int128 lhs, int128 rhs) { + return int128_internal::SignedSubstructResult( + MakeInt128(Int128High64(lhs) - Int128High64(rhs), + Int128Low64(lhs) - Int128Low64(rhs)), + lhs, rhs); } inline int128 operator*(int128 lhs, int128 rhs) { - uint128 result = uint128(lhs) * rhs; - return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(result)), - Uint128Low64(result)); + return MakeInt128( + int128_internal::BitCastToSigned(Uint128High64(uint128(lhs) * rhs)), + Uint128Low64(uint128(lhs) * rhs)); } inline int128 int128::operator++(int) { @@ -263,46 +263,43 @@ inline int128& int128::operator--() { return *this; } -inline int128 operator|(int128 lhs, int128 rhs) { +constexpr int128 operator|(int128 lhs, int128 rhs) { return MakeInt128(Int128High64(lhs) | Int128High64(rhs), Int128Low64(lhs) | Int128Low64(rhs)); } -inline int128 operator&(int128 lhs, int128 rhs) { +constexpr int128 operator&(int128 lhs, int128 rhs) { return MakeInt128(Int128High64(lhs) & Int128High64(rhs), Int128Low64(lhs) & Int128Low64(rhs)); } -inline int128 operator^(int128 lhs, int128 rhs) { +constexpr int128 operator^(int128 lhs, int128 rhs) { return MakeInt128(Int128High64(lhs) ^ Int128High64(rhs), Int128Low64(lhs) ^ Int128Low64(rhs)); } -inline int128 operator<<(int128 lhs, int amount) { +constexpr int128 operator<<(int128 lhs, int amount) { // uint64_t shifts of >= 64 are undefined, so we need some special-casing. - if (amount < 64) { - if (amount != 0) { - return MakeInt128( - (Int128High64(lhs) << amount) | - static_cast<int64_t>(Int128Low64(lhs) >> (64 - amount)), - Int128Low64(lhs) << amount); - } - return lhs; - } - return MakeInt128(static_cast<int64_t>(Int128Low64(lhs) << (amount - 64)), 0); -} - -inline int128 operator>>(int128 lhs, int amount) { + return amount >= 64 + ? MakeInt128( + static_cast<int64_t>(Int128Low64(lhs) << (amount - 64)), 0) + : amount == 0 + ? lhs + : MakeInt128( + (Int128High64(lhs) << amount) | + static_cast<int64_t>(Int128Low64(lhs) >> (64 - amount)), + Int128Low64(lhs) << amount); +} + +constexpr int128 operator>>(int128 lhs, int amount) { // uint64_t shifts of >= 64 are undefined, so we need some special-casing. - if (amount < 64) { - if (amount != 0) { - return MakeInt128( - Int128High64(lhs) >> amount, - (Int128Low64(lhs) >> amount) | - (static_cast<uint64_t>(Int128High64(lhs)) << (64 - amount))); - } - return lhs; - } - return MakeInt128(0, - static_cast<uint64_t>(Int128High64(lhs) >> (amount - 64))); + return amount >= 64 + ? MakeInt128( + 0, static_cast<uint64_t>(Int128High64(lhs) >> (amount - 64))) + : amount == 0 + ? lhs + : MakeInt128(Int128High64(lhs) >> amount, + (Int128Low64(lhs) >> amount) | + (static_cast<uint64_t>(Int128High64(lhs)) + << (64 - amount))); } |