Squashed 'third_party/abseil/' changes from ddf8e52a2..384af0e91
384af0e91 Export of internal Abseil changes
e7ca23aca Export of internal Abseil changes
4611a601a Export of internal Abseil changes
8a9ef3c5d Export of internal Abseil changes
9f8b87b71 Add missing word 'library' in the 'status' description (#868)
e2b1bab19 Export of internal Abseil changes
1bae23e32 Export of internal Abseil changes
6df644c56 Include the status library into the main README. (#863)
68f1ad932 Export of internal Abseil changes
52acfe6fc Export of internal Abseil changes
1918ad2ae Export of internal Abseil changes
938fd0f4e Export of internal Abseil changes
fbdff6f3a Export of internal Abseil changes
acf3390ca Export of internal Abseil changes
592924480 Export of internal Abseil changes
e80c0b353 Export of internal Abseil changes
5d8fc9192 Export of internal Abseil changes
e19260fd7 Export of internal Abseil changes
4fd9a1ec5 Export of internal Abseil changes
4ae673067 Export of internal Abseil changes
1b465af3b Export of internal Abseil changes
6b03bf543 fix build dll (#797)
0bbebc85c Export of internal Abseil changes
0453e1653 Export of internal Abseil changes
a4798817e Export of internal Abseil changes
e96d49687 Export of internal Abseil changes
731852f10 Fix stacktrace on aarch64 architecture. Fixes #805 (#827)
2e5f2bcfd moved deleted functions to public for better compiler errors. (#828)
e9e9b9fc7 Export of internal Abseil changes
b8e890f95 Export of internal Abseil changes
c9894d1dc Export of internal Abseil changes
e9b9e38f6 Export of internal Abseil changes
962b06754 Export of internal Abseil changes
5bf048b84 Export of internal Abseil changes
1e3d25b26 Export of internal Abseil changes
eb317a701 Export of internal Abseil changes
4b915e709 Export of internal Abseil changes
8f1c34a77 Export of internal Abseil changes
60d00a582 Export of internal Abseil changes
f3f785ab5 Export of internal Abseil changes
4b2fbb4ad Export of internal Abseil changes
e493d6acb fix compile fails with asan and -Wredundant-decls (#801)
e63a5a610 Export of internal Abseil changes
c678d6c6b Export of internal Abseil changes
4b4f9aae7 Export of internal Abseil changes
887d0eee6 Export of internal Abseil changes
b978fc02f Export of internal Abseil changes
093cc2760 Export of internal Abseil changes
40fdb59d3 btree: fix sign-compare warnings (#800)
1fd58b69c Export of internal Abseil changes
d1de75bf5 Export of internal Abseil changes
cad3f30b4 Export of internal Abseil changes
9927a0989 Export of internal Abseil changes
7680a5f8e Added missing asserts for seq.index() < capacity_ and unified their usage based on has_element(). (#781)
d3614de61 Export of internal Abseil changes
20feb1cdb Export of internal Abseil changes
c1ae0a497 Export of internal Abseil changes
6af91b351 Export of internal Abseil changes
f2c9c663d Export of internal Abseil changes
3c8b5d758 Export of internal Abseil changes
7ba8cdb56 Export of internal Abseil changes
930fbec75 Export of internal Abseil changes
0e9921b75 Export of internal Abseil changes
a4cbb5f69 Export of internal Abseil changes
4d2ff381a Export of internal Abseil changes
c03c18e7f Export of internal Abseil changes
b321ad86c Export of internal Abseil changes
fbf0fdab6 Export of internal Abseil changes
dc969f34a Export of internal Abseil changes
d0c433455 Export of internal Abseil changes
c6b3f2cf5 Export of internal Abseil changes
1beb3191c Export of internal Abseil changes
1b7e751e5 Export of internal Abseil changes
ce4bc9277 Export of internal Abseil changes
f72cc3516 Export of internal Abseil changes
f66bc7492 Export of internal Abseil changes
1995c6a3c Export of internal Abseil changes
184cf2524 Export of internal Abseil changes
82302f1e0 Export of internal Abseil changes
dea76486c Export of internal Abseil changes
d39fe6cd6 Export of internal Abseil changes
2c8a5b0d8 Export of internal Abseil changes
41a6263fd Export of internal Abseil changes
3c2bed2e7 Export of internal Abseil changes
ea8a689cf fix build on P9 (#739)
672d9e0ae Export of internal Abseil changes
f624790b7 Export of internal Abseil changes
55c04eb92 Export of internal Abseil changes
302b250e1 Disable pthread for standalone wasm build support (#721)
61d8bc057 Merge branch 'master' of https://github.com/abseil/abseil-cpp into master
4b5b25a28 cmake: remove unneeded enable_testing() cmd (#736)
63f2c695e cmake: flag conformance_testing as TESTONLY (#737)
d5269a8b6 Export of internal Abseil changes
23f1f9cf6 Typo in comment (#733)
259301a52 Fix CMake path for INSTALL_INCLUDEDIR (#723)
dc464c1dc Allow overriding Abseil IDE folder (#724)
bf655de09 Export of internal Abseil changes
38db52adb Export of internal Abseil changes
81f34df83 Export of internal Abseil changes
b86fff162 Export of internal Abseil changes
10cb35e45 Export of internal Abseil changes
4ccc0fce0 Export of internal Abseil changes
4a851046a Export of internal Abseil changes
ccdbb5941 Export of internal Abseil changes
01f5f81f9 Export of internal Abseil changes
2c92bdc7c Export of internal Abseil changes
e7ebf9803 Export of internal Abseil changes
2eba343b5 Export of internal Abseil changes
a8b03d90e Export of internal Abseil changes
1d31b5c36 Export of internal Abseil changes
da3a87690 Export of internal Abseil changes
8faf20461 Exclude empty directories (#697)
2069dc796 Export of internal Abseil changes
4832bf6bf Added a BUILD file in root to expose license. (#695)
af8f994af Export of internal Abseil changes
33caf1097 Export of internal Abseil changes
cf1a02e2d Export of internal Abseil changes
768eb2ca2 Export of internal Abseil changes
3f347c462 Fix build on riscv32 (#675)
62cf6a704 Export of internal Abseil changes
d118d4bb1 Export of internal Abseil changes
f2bc9d11e Fix public target name of the random library (#684)
0fecf0e63 Export of internal Abseil changes
cbfd0f0fe Export of internal Abseil changes
c45d1c09d Export of internal Abseil changes
a35ef8a62 Export of internal Abseil changes
bd317cae3 Export of internal Abseil changes
b11574465 fix MSVC warning 4245: conversion signed => unsigned during initialization (#678)
d85783fd0 Export of internal Abseil changes
a1d668990 Export of internal Abseil changes
ca9856cab Export of internal Abseil changes
6e18c7115 Export of internal Abseil changes
3f48ce1c4 init (#673)
cde2e2410 Export of internal Abseil changes
68494aae9 Fix CMake Threads dependency issue
902909a43 Export of internal Abseil changes
cb52b05ea Export of internal Abseil changes
1a02b7a20 Use "-lrt" instead of the resolved find_library result when linking librt (#665)
df60c82df Export of internal Abseil changes
b35973e3e Export of internal Abseil changes
db5773a72 Export of internal Abseil changes
71079e42c Export of internal Abseil changes
2946ac0de Use base_internal::AtomicHook instead of std::atomic (#661)
567bee2f7 Fix ABSL_RANDOM_RANDEN_COPTS setting on FreeBSD (#664)
bf6166a63 Export of internal Abseil changes
111260963 Export of internal Abseil changes
73ea9a957 Export of internal Abseil changes
c01b9916e Add option to use an externally provided GoogleTest target (for usage of abseil as add_subdirectory target) (#647)
d43b7997c Export of internal Abseil changes
62f05b1f5 Export of internal Abseil changes
fba8a316c Export of internal Abseil changes
79e0dc115 Export of internal Abseil changes
132d791b4 bazel: Add missing load statements for cc_binary (#645)
518f17501 Export of internal Abseil changes
092ed9793 Export of internal Abseil changes
2d2a8aea2 Export of internal Abseil changes
7853a7586 Export of internal Abseil changes
c6954897f Export of internal Abseil changes
b92f35f65 Fix CompressedTuple move constructor on MSVC (#637)
a877af1f2 Export of internal Abseil changes
d936052d3 Export of internal Abseil changes
238b9a59c Skip the .exe suffix in the helpshort filter on Windows (#629)
417ea99cb UWP doesn't allow reading regkeys (#594)
40a0e58eb Export of internal Abseil changes
cf3a1998e Export of internal Abseil changes
b19ba9676 Export of internal Abseil changes
06f0e767d BuildBreak: UWP apps can't call GetModuleHandle (#596)
bcefbdcdf Export of internal Abseil changes
0033c9ea9 Fix build on FreeBSD/powerpc (#616)
0d5ce2797 Export of internal Abseil changes
b69c7d880 Export of internal Abseil changes
2a5633fc0 Merge "Export of internal Abseil changes"
f9b3d6e49 Add RISCV support to GetProgramCounter() (#621)
914ff4451 Export of internal Abseil changes
0232c87f2 Add missing ABSL_HAVE_VDSO_SUPPORT conditional (#622)
3c8141051 Export of internal Abseil changes
c44657f55 Export of internal Abseil changes
98eb410c9 Export of internal Abseil changes
bf78e9773 Export of internal Abseil changes
d95d15671 Export of internal Abseil changes
24713a703 Export of internal Abseil changes
72382c21f Export of internal Abseil changes
08a7e7bf9 Export of internal Abseil changes
36bcd9599 Fix pointer format specifier in documentation (#614)
0f86336b6 Export of internal Abseil changes
c512f118d Export of internal Abseil changes
37dd2562e Export of internal Abseil changes
444277026 fix: Add support for more ARM processors detection (#608)
159bf2bf6 Export of internal Abseil changes
a2e6adecc Use https links. (#586)
564001ae5 Export of internal Abseil changes
b3aaac8a3 Export of internal Abseil changes
63ee2f887 Export of internal Abseil changes
a048203a8 Export of internal Abseil changes
1de016636 Export of internal Abseil changes
ad904b6cd Export of internal Abseil changes
7bd1935dc cmake: Fix x86_64 check on Windows for random copts (#518)
292351391 Export of internal Abseil changes
bf86cfe16 Export of internal Abseil changes
12bc53e03 Export of internal Abseil changes
1e39f8626 Export of internal Abseil changes
77f87009a Export of internal Abseil changes
d659fe54b Export of internal Abseil changes
a4b757b5d Export of internal Abseil changes
0514227d2 Export of internal Abseil changes
7f4fe64af Export of internal Abseil changes
16d9fd58a Export of internal Abseil changes
bcaae6009 Export of internal Abseil changes
8ba96a824 Export of internal Abseil changes
2103fd9ac Export of internal Abseil changes
3df7b52a6 Export of internal Abseil changes
fa8c75182 Export of internal Abseil changes
85092b4b6 Fix Conan builds (#400)
e96ae2203 Export of internal Abseil changes
20de2db74 Export of internal Abseil changes
846e5dbed Export of internal Abseil changes
83880e3d8 Merge branch 'master' of https://github.com/abseil/abseil-cpp
8207907f4 Export of internal Abseil changes
39d68a422 docs: fix typo (#397)
078b89b3c Export of internal Abseil changes
19b021cb3 Export of internal Abseil changes
ecc0033b5 Always enable proper symbolize implementation on Windows (#257)
2796d500a Export of internal Abseil changes
e4c8d0eb8 Export of internal Abseil changes
a15364ce4 Export of internal Abseil changes
ab3552a18 Export of internal Abseil changes
e9f9000c7 Fix ABSL_WAITER_MODE detection for mingw (#342)
abea769b5 Fix ABSL_HAVE_ALARM check on mingw (#341)
25597bdfc Export of internal Abseil changes
aad33fefa Export of internal Abseil changes
8fe7214fe Export of internal Abseil changes
debac94cf Export of internal Abseil changes
882b3501a Fix spelling errors (#384)
502efe6d7 Export of internal Abseil changes
ccdd1d57b Export of internal Abseil changes
Change-Id: I59864a0053f6e03d88cc9d5e2a92757039a05484
git-subtree-dir: third_party/abseil
git-subtree-split: 384af0e9141283172e2bff3210dae79fb7130d9c
diff --git a/absl/numeric/BUILD.bazel b/absl/numeric/BUILD.bazel
index e09e52d..5d7b185 100644
--- a/absl/numeric/BUILD.bazel
+++ b/absl/numeric/BUILD.bazel
@@ -22,7 +22,36 @@
package(default_visibility = ["//visibility:public"])
-licenses(["notice"]) # Apache 2.0
+licenses(["notice"])
+
+cc_library(
+ name = "bits",
+ hdrs = [
+ "bits.h",
+ "internal/bits.h",
+ ],
+ copts = ABSL_DEFAULT_COPTS,
+ linkopts = ABSL_DEFAULT_LINKOPTS,
+ deps = [
+ "//absl/base:config",
+ "//absl/base:core_headers",
+ ],
+)
+
+cc_test(
+ name = "bits_test",
+ size = "small",
+ srcs = [
+ "bits_test.cc",
+ ],
+ copts = ABSL_TEST_COPTS,
+ linkopts = ABSL_DEFAULT_LINKOPTS,
+ deps = [
+ ":bits",
+ "//absl/random",
+ "@com_google_googletest//:gtest_main",
+ ],
+)
cc_library(
name = "int128",
@@ -35,6 +64,7 @@
copts = ABSL_DEFAULT_COPTS,
linkopts = ABSL_DEFAULT_LINKOPTS,
deps = [
+ ":bits",
"//absl/base:config",
"//absl/base:core_headers",
],
diff --git a/absl/numeric/CMakeLists.txt b/absl/numeric/CMakeLists.txt
index 242889f..be94352 100644
--- a/absl/numeric/CMakeLists.txt
+++ b/absl/numeric/CMakeLists.txt
@@ -16,6 +16,33 @@
absl_cc_library(
NAME
+ bits
+ HDRS
+ "bits.h"
+ "internal/bits.h"
+ COPTS
+ ${ABSL_DEFAULT_COPTS}
+ DEPS
+ absl::core_headers
+ PUBLIC
+)
+
+absl_cc_test(
+ NAME
+ bits_test
+ SRCS
+ "bits_test.cc"
+ COPTS
+ ${ABSL_TEST_COPTS}
+ DEPS
+ absl::bits
+ absl::core_headers
+ absl::random_random
+ gmock_main
+)
+
+absl_cc_library(
+ NAME
int128
HDRS
"int128.h"
@@ -28,6 +55,7 @@
DEPS
absl::config
absl::core_headers
+ absl::bits
PUBLIC
)
diff --git a/absl/numeric/bits.h b/absl/numeric/bits.h
new file mode 100644
index 0000000..52013ad
--- /dev/null
+++ b/absl/numeric/bits.h
@@ -0,0 +1,177 @@
+// 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.
+//
+// -----------------------------------------------------------------------------
+// File: bits.h
+// -----------------------------------------------------------------------------
+//
+// This file contains implementations of C++20's bitwise math functions, as
+// defined by:
+//
+// P0553R4:
+// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html
+// P0556R3:
+// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0556r3.html
+// P1355R2:
+// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1355r2.html
+// P1956R1:
+// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p1956r1.pdf
+//
+// When using a standard library that implements these functions, we use the
+// standard library's implementation.
+
+#ifndef ABSL_NUMERIC_BITS_H_
+#define ABSL_NUMERIC_BITS_H_
+
+#include <cstdint>
+#include <limits>
+#include <type_traits>
+
+#if (defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L) || \
+ (defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L)
+#include <bit>
+#endif
+
+#include "absl/base/attributes.h"
+#include "absl/base/config.h"
+#include "absl/numeric/internal/bits.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+
+#if !(defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L)
+// rotating
+template <class T>
+ABSL_MUST_USE_RESULT constexpr
+ typename std::enable_if<std::is_unsigned<T>::value, T>::type
+ rotl(T x, int s) noexcept {
+ return numeric_internal::RotateLeft(x, s);
+}
+
+template <class T>
+ABSL_MUST_USE_RESULT constexpr
+ typename std::enable_if<std::is_unsigned<T>::value, T>::type
+ rotr(T x, int s) noexcept {
+ return numeric_internal::RotateRight(x, s);
+}
+
+// Counting functions
+//
+// While these functions are typically constexpr, on some platforms, they may
+// not be marked as constexpr due to constraints of the compiler/available
+// intrinsics.
+template <class T>
+ABSL_INTERNAL_CONSTEXPR_CLZ inline
+ typename std::enable_if<std::is_unsigned<T>::value, int>::type
+ countl_zero(T x) noexcept {
+ return numeric_internal::CountLeadingZeroes(x);
+}
+
+template <class T>
+ABSL_INTERNAL_CONSTEXPR_CLZ inline
+ typename std::enable_if<std::is_unsigned<T>::value, int>::type
+ countl_one(T x) noexcept {
+ // Avoid integer promotion to a wider type
+ return countl_zero(static_cast<T>(~x));
+}
+
+template <class T>
+ABSL_INTERNAL_CONSTEXPR_CTZ inline
+ typename std::enable_if<std::is_unsigned<T>::value, int>::type
+ countr_zero(T x) noexcept {
+ return numeric_internal::CountTrailingZeroes(x);
+}
+
+template <class T>
+ABSL_INTERNAL_CONSTEXPR_CTZ inline
+ typename std::enable_if<std::is_unsigned<T>::value, int>::type
+ countr_one(T x) noexcept {
+ // Avoid integer promotion to a wider type
+ return countr_zero(static_cast<T>(~x));
+}
+
+template <class T>
+ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline
+ typename std::enable_if<std::is_unsigned<T>::value, int>::type
+ popcount(T x) noexcept {
+ return numeric_internal::Popcount(x);
+}
+#else // defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
+
+using std::countl_one;
+using std::countl_zero;
+using std::countr_one;
+using std::countr_zero;
+using std::popcount;
+using std::rotl;
+using std::rotr;
+
+#endif
+
+#if !(defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L)
+// Returns: true if x is an integral power of two; false otherwise.
+template <class T>
+constexpr inline typename std::enable_if<std::is_unsigned<T>::value, bool>::type
+has_single_bit(T x) noexcept {
+ return x != 0 && (x & (x - 1)) == 0;
+}
+
+// Returns: If x == 0, 0; otherwise one plus the base-2 logarithm of x, with any
+// fractional part discarded.
+template <class T>
+ABSL_INTERNAL_CONSTEXPR_CLZ inline
+ typename std::enable_if<std::is_unsigned<T>::value, T>::type
+ bit_width(T x) noexcept {
+ return std::numeric_limits<T>::digits - countl_zero(x);
+}
+
+// Returns: If x == 0, 0; otherwise the maximal value y such that
+// has_single_bit(y) is true and y <= x.
+template <class T>
+ABSL_INTERNAL_CONSTEXPR_CLZ inline
+ typename std::enable_if<std::is_unsigned<T>::value, T>::type
+ bit_floor(T x) noexcept {
+ return x == 0 ? 0 : T{1} << (bit_width(x) - 1);
+}
+
+// Returns: N, where N is the smallest power of 2 greater than or equal to x.
+//
+// Preconditions: N is representable as a value of type T.
+template <class T>
+ABSL_INTERNAL_CONSTEXPR_CLZ inline
+ typename std::enable_if<std::is_unsigned<T>::value, T>::type
+ bit_ceil(T x) {
+ // If T is narrower than unsigned, T{1} << bit_width will be promoted. We
+ // want to force it to wraparound so that bit_ceil of an invalid value are not
+ // core constant expressions.
+ //
+ // BitCeilNonPowerOf2 triggers an overflow in constexpr contexts if we would
+ // undergo promotion to unsigned but not fit the result into T without
+ // truncation.
+ return has_single_bit(x) ? T{1} << (bit_width(x) - 1)
+ : numeric_internal::BitCeilNonPowerOf2(x);
+}
+#else // defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L
+
+using std::bit_ceil;
+using std::bit_floor;
+using std::bit_width;
+using std::has_single_bit;
+
+#endif
+
+ABSL_NAMESPACE_END
+} // namespace absl
+
+#endif // ABSL_NUMERIC_BITS_H_
diff --git a/absl/numeric/bits_test.cc b/absl/numeric/bits_test.cc
new file mode 100644
index 0000000..8bf7bc9
--- /dev/null
+++ b/absl/numeric/bits_test.cc
@@ -0,0 +1,565 @@
+// 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/numeric/bits.h"
+
+#include <limits>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/random/random.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace {
+
+TEST(Rotate, Left) {
+ static_assert(rotl(uint8_t{0x12}, 0) == uint8_t{0x12}, "");
+ static_assert(rotl(uint16_t{0x1234}, 0) == uint16_t{0x1234}, "");
+ static_assert(rotl(uint32_t{0x12345678UL}, 0) == uint32_t{0x12345678UL}, "");
+ static_assert(rotl(uint64_t{0x12345678ABCDEF01ULL}, 0) ==
+ uint64_t{0x12345678ABCDEF01ULL},
+ "");
+
+ EXPECT_EQ(rotl(uint8_t{0x12}, 0), uint8_t{0x12});
+ EXPECT_EQ(rotl(uint16_t{0x1234}, 0), uint16_t{0x1234});
+ EXPECT_EQ(rotl(uint32_t{0x12345678UL}, 0), uint32_t{0x12345678UL});
+ EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, 0),
+ uint64_t{0x12345678ABCDEF01ULL});
+
+ EXPECT_EQ(rotl(uint8_t{0x12}, 8), uint8_t{0x12});
+ EXPECT_EQ(rotl(uint16_t{0x1234}, 16), uint16_t{0x1234});
+ EXPECT_EQ(rotl(uint32_t{0x12345678UL}, 32), uint32_t{0x12345678UL});
+ EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, 64),
+ uint64_t{0x12345678ABCDEF01ULL});
+
+ EXPECT_EQ(rotl(uint8_t{0x12}, -8), uint8_t{0x12});
+ EXPECT_EQ(rotl(uint16_t{0x1234}, -16), uint16_t{0x1234});
+ EXPECT_EQ(rotl(uint32_t{0x12345678UL}, -32), uint32_t{0x12345678UL});
+ EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, -64),
+ uint64_t{0x12345678ABCDEF01ULL});
+
+ EXPECT_EQ(rotl(uint8_t{0x12}, 4), uint8_t{0x21});
+ EXPECT_EQ(rotl(uint16_t{0x1234}, 4), uint16_t{0x2341});
+ EXPECT_EQ(rotl(uint32_t{0x12345678UL}, 4), uint32_t{0x23456781UL});
+ EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, 4),
+ uint64_t{0x2345678ABCDEF011ULL});
+
+ EXPECT_EQ(rotl(uint8_t{0x12}, -4), uint8_t{0x21});
+ EXPECT_EQ(rotl(uint16_t{0x1234}, -4), uint16_t{0x4123});
+ EXPECT_EQ(rotl(uint32_t{0x12345678UL}, -4), uint32_t{0x81234567UL});
+ EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, -4),
+ uint64_t{0x112345678ABCDEF0ULL});
+}
+
+TEST(Rotate, Right) {
+ static_assert(rotr(uint8_t{0x12}, 0) == uint8_t{0x12}, "");
+ static_assert(rotr(uint16_t{0x1234}, 0) == uint16_t{0x1234}, "");
+ static_assert(rotr(uint32_t{0x12345678UL}, 0) == uint32_t{0x12345678UL}, "");
+ static_assert(rotr(uint64_t{0x12345678ABCDEF01ULL}, 0) ==
+ uint64_t{0x12345678ABCDEF01ULL},
+ "");
+
+ EXPECT_EQ(rotr(uint8_t{0x12}, 0), uint8_t{0x12});
+ EXPECT_EQ(rotr(uint16_t{0x1234}, 0), uint16_t{0x1234});
+ EXPECT_EQ(rotr(uint32_t{0x12345678UL}, 0), uint32_t{0x12345678UL});
+ EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, 0),
+ uint64_t{0x12345678ABCDEF01ULL});
+
+ EXPECT_EQ(rotr(uint8_t{0x12}, 8), uint8_t{0x12});
+ EXPECT_EQ(rotr(uint16_t{0x1234}, 16), uint16_t{0x1234});
+ EXPECT_EQ(rotr(uint32_t{0x12345678UL}, 32), uint32_t{0x12345678UL});
+ EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, 64),
+ uint64_t{0x12345678ABCDEF01ULL});
+
+ EXPECT_EQ(rotr(uint8_t{0x12}, -8), uint8_t{0x12});
+ EXPECT_EQ(rotr(uint16_t{0x1234}, -16), uint16_t{0x1234});
+ EXPECT_EQ(rotr(uint32_t{0x12345678UL}, -32), uint32_t{0x12345678UL});
+ EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, -64),
+ uint64_t{0x12345678ABCDEF01ULL});
+
+ EXPECT_EQ(rotr(uint8_t{0x12}, 4), uint8_t{0x21});
+ EXPECT_EQ(rotr(uint16_t{0x1234}, 4), uint16_t{0x4123});
+ EXPECT_EQ(rotr(uint32_t{0x12345678UL}, 4), uint32_t{0x81234567UL});
+ EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, 4),
+ uint64_t{0x112345678ABCDEF0ULL});
+
+ EXPECT_EQ(rotr(uint8_t{0x12}, -4), uint8_t{0x21});
+ EXPECT_EQ(rotr(uint16_t{0x1234}, -4), uint16_t{0x2341});
+ EXPECT_EQ(rotr(uint32_t{0x12345678UL}, -4), uint32_t{0x23456781UL});
+ EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, -4),
+ uint64_t{0x2345678ABCDEF011ULL});
+}
+
+TEST(Rotate, Symmetry) {
+ // rotr(x, s) is equivalent to rotl(x, -s)
+ absl::BitGen rng;
+ constexpr int kTrials = 100;
+
+ for (int i = 0; i < kTrials; ++i) {
+ uint8_t value = absl::Uniform(rng, std::numeric_limits<uint8_t>::min(),
+ std::numeric_limits<uint8_t>::max());
+ int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint8_t>::digits,
+ 2 * std::numeric_limits<uint8_t>::digits);
+
+ EXPECT_EQ(rotl(value, shift), rotr(value, -shift));
+ }
+
+ for (int i = 0; i < kTrials; ++i) {
+ uint16_t value = absl::Uniform(rng, std::numeric_limits<uint16_t>::min(),
+ std::numeric_limits<uint16_t>::max());
+ int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint16_t>::digits,
+ 2 * std::numeric_limits<uint16_t>::digits);
+
+ EXPECT_EQ(rotl(value, shift), rotr(value, -shift));
+ }
+
+ for (int i = 0; i < kTrials; ++i) {
+ uint32_t value = absl::Uniform(rng, std::numeric_limits<uint32_t>::min(),
+ std::numeric_limits<uint32_t>::max());
+ int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint32_t>::digits,
+ 2 * std::numeric_limits<uint32_t>::digits);
+
+ EXPECT_EQ(rotl(value, shift), rotr(value, -shift));
+ }
+
+ for (int i = 0; i < kTrials; ++i) {
+ uint64_t value = absl::Uniform(rng, std::numeric_limits<uint64_t>::min(),
+ std::numeric_limits<uint64_t>::max());
+ int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint64_t>::digits,
+ 2 * std::numeric_limits<uint64_t>::digits);
+
+ EXPECT_EQ(rotl(value, shift), rotr(value, -shift));
+ }
+}
+
+TEST(Counting, LeadingZeroes) {
+#if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ
+ static_assert(countl_zero(uint8_t{}) == 8, "");
+ static_assert(countl_zero(static_cast<uint8_t>(-1)) == 0, "");
+ static_assert(countl_zero(uint16_t{}) == 16, "");
+ static_assert(countl_zero(static_cast<uint16_t>(-1)) == 0, "");
+ static_assert(countl_zero(uint32_t{}) == 32, "");
+ static_assert(countl_zero(~uint32_t{}) == 0, "");
+ static_assert(countl_zero(uint64_t{}) == 64, "");
+ static_assert(countl_zero(~uint64_t{}) == 0, "");
+#endif
+
+ EXPECT_EQ(countl_zero(uint8_t{}), 8);
+ EXPECT_EQ(countl_zero(static_cast<uint8_t>(-1)), 0);
+ EXPECT_EQ(countl_zero(uint16_t{}), 16);
+ EXPECT_EQ(countl_zero(static_cast<uint16_t>(-1)), 0);
+ EXPECT_EQ(countl_zero(uint32_t{}), 32);
+ EXPECT_EQ(countl_zero(~uint32_t{}), 0);
+ EXPECT_EQ(countl_zero(uint64_t{}), 64);
+ EXPECT_EQ(countl_zero(~uint64_t{}), 0);
+
+ for (int i = 0; i < 8; i++) {
+ EXPECT_EQ(countl_zero(static_cast<uint8_t>(1u << i)), 7 - i);
+ }
+
+ for (int i = 0; i < 16; i++) {
+ EXPECT_EQ(countl_zero(static_cast<uint16_t>(1u << i)), 15 - i);
+ }
+
+ for (int i = 0; i < 32; i++) {
+ EXPECT_EQ(countl_zero(uint32_t{1} << i), 31 - i);
+ }
+
+ for (int i = 0; i < 64; i++) {
+ EXPECT_EQ(countl_zero(uint64_t{1} << i), 63 - i);
+ }
+}
+
+TEST(Counting, LeadingOnes) {
+#if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ
+ static_assert(countl_one(uint8_t{}) == 0, "");
+ static_assert(countl_one(static_cast<uint8_t>(-1)) == 8, "");
+ static_assert(countl_one(uint16_t{}) == 0, "");
+ static_assert(countl_one(static_cast<uint16_t>(-1)) == 16, "");
+ static_assert(countl_one(uint32_t{}) == 0, "");
+ static_assert(countl_one(~uint32_t{}) == 32, "");
+ static_assert(countl_one(uint64_t{}) == 0, "");
+ static_assert(countl_one(~uint64_t{}) == 64, "");
+#endif
+
+ EXPECT_EQ(countl_one(uint8_t{}), 0);
+ EXPECT_EQ(countl_one(static_cast<uint8_t>(-1)), 8);
+ EXPECT_EQ(countl_one(uint16_t{}), 0);
+ EXPECT_EQ(countl_one(static_cast<uint16_t>(-1)), 16);
+ EXPECT_EQ(countl_one(uint32_t{}), 0);
+ EXPECT_EQ(countl_one(~uint32_t{}), 32);
+ EXPECT_EQ(countl_one(uint64_t{}), 0);
+ EXPECT_EQ(countl_one(~uint64_t{}), 64);
+}
+
+TEST(Counting, TrailingZeroes) {
+#if ABSL_INTERNAL_HAS_CONSTEXPR_CTZ
+ static_assert(countr_zero(uint8_t{}) == 8, "");
+ static_assert(countr_zero(static_cast<uint8_t>(-1)) == 0, "");
+ static_assert(countr_zero(uint16_t{}) == 16, "");
+ static_assert(countr_zero(static_cast<uint16_t>(-1)) == 0, "");
+ static_assert(countr_zero(uint32_t{}) == 32, "");
+ static_assert(countr_zero(~uint32_t{}) == 0, "");
+ static_assert(countr_zero(uint64_t{}) == 64, "");
+ static_assert(countr_zero(~uint64_t{}) == 0, "");
+#endif
+
+ EXPECT_EQ(countr_zero(uint8_t{}), 8);
+ EXPECT_EQ(countr_zero(static_cast<uint8_t>(-1)), 0);
+ EXPECT_EQ(countr_zero(uint16_t{}), 16);
+ EXPECT_EQ(countr_zero(static_cast<uint16_t>(-1)), 0);
+ EXPECT_EQ(countr_zero(uint32_t{}), 32);
+ EXPECT_EQ(countr_zero(~uint32_t{}), 0);
+ EXPECT_EQ(countr_zero(uint64_t{}), 64);
+ EXPECT_EQ(countr_zero(~uint64_t{}), 0);
+}
+
+TEST(Counting, TrailingOnes) {
+#if ABSL_INTERNAL_HAS_CONSTEXPR_CTZ
+ static_assert(countr_one(uint8_t{}) == 0, "");
+ static_assert(countr_one(static_cast<uint8_t>(-1)) == 8, "");
+ static_assert(countr_one(uint16_t{}) == 0, "");
+ static_assert(countr_one(static_cast<uint16_t>(-1)) == 16, "");
+ static_assert(countr_one(uint32_t{}) == 0, "");
+ static_assert(countr_one(~uint32_t{}) == 32, "");
+ static_assert(countr_one(uint64_t{}) == 0, "");
+ static_assert(countr_one(~uint64_t{}) == 64, "");
+#endif
+
+ EXPECT_EQ(countr_one(uint8_t{}), 0);
+ EXPECT_EQ(countr_one(static_cast<uint8_t>(-1)), 8);
+ EXPECT_EQ(countr_one(uint16_t{}), 0);
+ EXPECT_EQ(countr_one(static_cast<uint16_t>(-1)), 16);
+ EXPECT_EQ(countr_one(uint32_t{}), 0);
+ EXPECT_EQ(countr_one(~uint32_t{}), 32);
+ EXPECT_EQ(countr_one(uint64_t{}), 0);
+ EXPECT_EQ(countr_one(~uint64_t{}), 64);
+}
+
+TEST(Counting, Popcount) {
+#if ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT
+ static_assert(popcount(uint8_t{}) == 0, "");
+ static_assert(popcount(uint8_t{1}) == 1, "");
+ static_assert(popcount(static_cast<uint8_t>(-1)) == 8, "");
+ static_assert(popcount(uint16_t{}) == 0, "");
+ static_assert(popcount(uint16_t{1}) == 1, "");
+ static_assert(popcount(static_cast<uint16_t>(-1)) == 16, "");
+ static_assert(popcount(uint32_t{}) == 0, "");
+ static_assert(popcount(uint32_t{1}) == 1, "");
+ static_assert(popcount(~uint32_t{}) == 32, "");
+ static_assert(popcount(uint64_t{}) == 0, "");
+ static_assert(popcount(uint64_t{1}) == 1, "");
+ static_assert(popcount(~uint64_t{}) == 64, "");
+#endif // ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT
+
+ EXPECT_EQ(popcount(uint8_t{}), 0);
+ EXPECT_EQ(popcount(uint8_t{1}), 1);
+ EXPECT_EQ(popcount(static_cast<uint8_t>(-1)), 8);
+ EXPECT_EQ(popcount(uint16_t{}), 0);
+ EXPECT_EQ(popcount(uint16_t{1}), 1);
+ EXPECT_EQ(popcount(static_cast<uint16_t>(-1)), 16);
+ EXPECT_EQ(popcount(uint32_t{}), 0);
+ EXPECT_EQ(popcount(uint32_t{1}), 1);
+ EXPECT_EQ(popcount(~uint32_t{}), 32);
+ EXPECT_EQ(popcount(uint64_t{}), 0);
+ EXPECT_EQ(popcount(uint64_t{1}), 1);
+ EXPECT_EQ(popcount(~uint64_t{}), 64);
+
+ for (int i = 0; i < 8; i++) {
+ EXPECT_EQ(popcount(static_cast<uint8_t>(uint8_t{1} << i)), 1);
+ EXPECT_EQ(popcount(static_cast<uint8_t>(static_cast<uint8_t>(-1) ^
+ (uint8_t{1} << i))),
+ 7);
+ }
+
+ for (int i = 0; i < 16; i++) {
+ EXPECT_EQ(popcount(static_cast<uint16_t>(uint16_t{1} << i)), 1);
+ EXPECT_EQ(popcount(static_cast<uint16_t>(static_cast<uint16_t>(-1) ^
+ (uint16_t{1} << i))),
+ 15);
+ }
+
+ for (int i = 0; i < 32; i++) {
+ EXPECT_EQ(popcount(uint32_t{1} << i), 1);
+ EXPECT_EQ(popcount(static_cast<uint32_t>(-1) ^ (uint32_t{1} << i)), 31);
+ }
+
+ for (int i = 0; i < 64; i++) {
+ EXPECT_EQ(popcount(uint64_t{1} << i), 1);
+ EXPECT_EQ(popcount(static_cast<uint64_t>(-1) ^ (uint64_t{1} << i)), 63);
+ }
+}
+
+template <typename T>
+struct PopcountInput {
+ T value = 0;
+ int expected = 0;
+};
+
+template <typename T>
+PopcountInput<T> GeneratePopcountInput(absl::BitGen& gen) {
+ PopcountInput<T> ret;
+ for (int i = 0; i < std::numeric_limits<T>::digits; i++) {
+ bool coin = absl::Bernoulli(gen, 0.2);
+ if (coin) {
+ ret.value |= T{1} << i;
+ ret.expected++;
+ }
+ }
+ return ret;
+}
+
+TEST(Counting, PopcountFuzz) {
+ absl::BitGen rng;
+ constexpr int kTrials = 100;
+
+ for (int i = 0; i < kTrials; ++i) {
+ auto input = GeneratePopcountInput<uint8_t>(rng);
+ EXPECT_EQ(popcount(input.value), input.expected);
+ }
+
+ for (int i = 0; i < kTrials; ++i) {
+ auto input = GeneratePopcountInput<uint16_t>(rng);
+ EXPECT_EQ(popcount(input.value), input.expected);
+ }
+
+ for (int i = 0; i < kTrials; ++i) {
+ auto input = GeneratePopcountInput<uint32_t>(rng);
+ EXPECT_EQ(popcount(input.value), input.expected);
+ }
+
+ for (int i = 0; i < kTrials; ++i) {
+ auto input = GeneratePopcountInput<uint64_t>(rng);
+ EXPECT_EQ(popcount(input.value), input.expected);
+ }
+}
+
+TEST(IntegralPowersOfTwo, SingleBit) {
+ EXPECT_FALSE(has_single_bit(uint8_t{}));
+ EXPECT_FALSE(has_single_bit(static_cast<uint8_t>(-1)));
+ EXPECT_FALSE(has_single_bit(uint16_t{}));
+ EXPECT_FALSE(has_single_bit(static_cast<uint16_t>(-1)));
+ EXPECT_FALSE(has_single_bit(uint32_t{}));
+ EXPECT_FALSE(has_single_bit(~uint32_t{}));
+ EXPECT_FALSE(has_single_bit(uint64_t{}));
+ EXPECT_FALSE(has_single_bit(~uint64_t{}));
+
+ static_assert(!has_single_bit(0u), "");
+ static_assert(has_single_bit(1u), "");
+ static_assert(has_single_bit(2u), "");
+ static_assert(!has_single_bit(3u), "");
+ static_assert(has_single_bit(4u), "");
+ static_assert(!has_single_bit(1337u), "");
+ static_assert(has_single_bit(65536u), "");
+ static_assert(has_single_bit(uint32_t{1} << 30), "");
+ static_assert(has_single_bit(uint64_t{1} << 42), "");
+
+ EXPECT_FALSE(has_single_bit(0u));
+ EXPECT_TRUE(has_single_bit(1u));
+ EXPECT_TRUE(has_single_bit(2u));
+ EXPECT_FALSE(has_single_bit(3u));
+ EXPECT_TRUE(has_single_bit(4u));
+ EXPECT_FALSE(has_single_bit(1337u));
+ EXPECT_TRUE(has_single_bit(65536u));
+ EXPECT_TRUE(has_single_bit(uint32_t{1} << 30));
+ EXPECT_TRUE(has_single_bit(uint64_t{1} << 42));
+
+ EXPECT_TRUE(has_single_bit(
+ static_cast<uint8_t>(std::numeric_limits<uint8_t>::max() / 2 + 1)));
+ EXPECT_TRUE(has_single_bit(
+ static_cast<uint16_t>(std::numeric_limits<uint16_t>::max() / 2 + 1)));
+ EXPECT_TRUE(has_single_bit(
+ static_cast<uint32_t>(std::numeric_limits<uint32_t>::max() / 2 + 1)));
+ EXPECT_TRUE(has_single_bit(
+ static_cast<uint64_t>(std::numeric_limits<uint64_t>::max() / 2 + 1)));
+}
+
+template <typename T, T arg, T = bit_ceil(arg)>
+bool IsBitCeilConstantExpression(int) {
+ return true;
+}
+template <typename T, T arg>
+bool IsBitCeilConstantExpression(char) {
+ return false;
+}
+
+TEST(IntegralPowersOfTwo, Ceiling) {
+#if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ
+ static_assert(bit_ceil(0u) == 1, "");
+ static_assert(bit_ceil(1u) == 1, "");
+ static_assert(bit_ceil(2u) == 2, "");
+ static_assert(bit_ceil(3u) == 4, "");
+ static_assert(bit_ceil(4u) == 4, "");
+ static_assert(bit_ceil(1337u) == 2048, "");
+ static_assert(bit_ceil(65536u) == 65536, "");
+ static_assert(bit_ceil(65536u - 1337u) == 65536, "");
+ static_assert(bit_ceil(uint32_t{0x80000000}) == uint32_t{0x80000000}, "");
+ static_assert(bit_ceil(uint64_t{0x40000000000}) == uint64_t{0x40000000000},
+ "");
+ static_assert(
+ bit_ceil(uint64_t{0x8000000000000000}) == uint64_t{0x8000000000000000},
+ "");
+
+ EXPECT_TRUE((IsBitCeilConstantExpression<uint8_t, uint8_t{0x0}>(0)));
+ EXPECT_TRUE((IsBitCeilConstantExpression<uint8_t, uint8_t{0x80}>(0)));
+ EXPECT_FALSE((IsBitCeilConstantExpression<uint8_t, uint8_t{0x81}>(0)));
+ EXPECT_FALSE((IsBitCeilConstantExpression<uint8_t, uint8_t{0xff}>(0)));
+
+ EXPECT_TRUE((IsBitCeilConstantExpression<uint16_t, uint16_t{0x0}>(0)));
+ EXPECT_TRUE((IsBitCeilConstantExpression<uint16_t, uint16_t{0x8000}>(0)));
+ EXPECT_FALSE((IsBitCeilConstantExpression<uint16_t, uint16_t{0x8001}>(0)));
+ EXPECT_FALSE((IsBitCeilConstantExpression<uint16_t, uint16_t{0xffff}>(0)));
+
+ EXPECT_TRUE((IsBitCeilConstantExpression<uint32_t, uint32_t{0x0}>(0)));
+ EXPECT_TRUE((IsBitCeilConstantExpression<uint32_t, uint32_t{0x80000000}>(0)));
+ EXPECT_FALSE(
+ (IsBitCeilConstantExpression<uint32_t, uint32_t{0x80000001}>(0)));
+ EXPECT_FALSE(
+ (IsBitCeilConstantExpression<uint32_t, uint32_t{0xffffffff}>(0)));
+
+ EXPECT_TRUE((IsBitCeilConstantExpression<uint64_t, uint64_t{0x0}>(0)));
+ EXPECT_TRUE(
+ (IsBitCeilConstantExpression<uint64_t, uint64_t{0x8000000000000000}>(0)));
+ EXPECT_FALSE(
+ (IsBitCeilConstantExpression<uint64_t, uint64_t{0x8000000000000001}>(0)));
+ EXPECT_FALSE(
+ (IsBitCeilConstantExpression<uint64_t, uint64_t{0xffffffffffffffff}>(0)));
+#endif
+
+ EXPECT_EQ(bit_ceil(0u), 1);
+ EXPECT_EQ(bit_ceil(1u), 1);
+ EXPECT_EQ(bit_ceil(2u), 2);
+ EXPECT_EQ(bit_ceil(3u), 4);
+ EXPECT_EQ(bit_ceil(4u), 4);
+ EXPECT_EQ(bit_ceil(1337u), 2048);
+ EXPECT_EQ(bit_ceil(65536u), 65536);
+ EXPECT_EQ(bit_ceil(65536u - 1337u), 65536);
+ EXPECT_EQ(bit_ceil(uint64_t{0x40000000000}), uint64_t{0x40000000000});
+}
+
+TEST(IntegralPowersOfTwo, Floor) {
+#if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ
+ static_assert(bit_floor(0u) == 0, "");
+ static_assert(bit_floor(1u) == 1, "");
+ static_assert(bit_floor(2u) == 2, "");
+ static_assert(bit_floor(3u) == 2, "");
+ static_assert(bit_floor(4u) == 4, "");
+ static_assert(bit_floor(1337u) == 1024, "");
+ static_assert(bit_floor(65536u) == 65536, "");
+ static_assert(bit_floor(65536u - 1337u) == 32768, "");
+ static_assert(bit_floor(uint64_t{0x40000000000}) == uint64_t{0x40000000000},
+ "");
+#endif
+
+ EXPECT_EQ(bit_floor(0u), 0);
+ EXPECT_EQ(bit_floor(1u), 1);
+ EXPECT_EQ(bit_floor(2u), 2);
+ EXPECT_EQ(bit_floor(3u), 2);
+ EXPECT_EQ(bit_floor(4u), 4);
+ EXPECT_EQ(bit_floor(1337u), 1024);
+ EXPECT_EQ(bit_floor(65536u), 65536);
+ EXPECT_EQ(bit_floor(65536u - 1337u), 32768);
+ EXPECT_EQ(bit_floor(uint64_t{0x40000000000}), uint64_t{0x40000000000});
+
+ for (int i = 0; i < 8; i++) {
+ uint8_t input = uint8_t{1} << i;
+ EXPECT_EQ(bit_floor(input), input);
+ if (i > 0) {
+ EXPECT_EQ(bit_floor(static_cast<uint8_t>(input + 1)), input);
+ }
+ }
+
+ for (int i = 0; i < 16; i++) {
+ uint16_t input = uint16_t{1} << i;
+ EXPECT_EQ(bit_floor(input), input);
+ if (i > 0) {
+ EXPECT_EQ(bit_floor(static_cast<uint16_t>(input + 1)), input);
+ }
+ }
+
+ for (int i = 0; i < 32; i++) {
+ uint32_t input = uint32_t{1} << i;
+ EXPECT_EQ(bit_floor(input), input);
+ if (i > 0) {
+ EXPECT_EQ(bit_floor(input + 1), input);
+ }
+ }
+
+ for (int i = 0; i < 64; i++) {
+ uint64_t input = uint64_t{1} << i;
+ EXPECT_EQ(bit_floor(input), input);
+ if (i > 0) {
+ EXPECT_EQ(bit_floor(input + 1), input);
+ }
+ }
+}
+
+TEST(IntegralPowersOfTwo, Width) {
+#if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ
+ static_assert(bit_width(uint8_t{}) == 0, "");
+ static_assert(bit_width(uint8_t{1}) == 1, "");
+ static_assert(bit_width(uint8_t{3}) == 2, "");
+ static_assert(bit_width(static_cast<uint8_t>(-1)) == 8, "");
+ static_assert(bit_width(uint16_t{}) == 0, "");
+ static_assert(bit_width(uint16_t{1}) == 1, "");
+ static_assert(bit_width(uint16_t{3}) == 2, "");
+ static_assert(bit_width(static_cast<uint16_t>(-1)) == 16, "");
+ static_assert(bit_width(uint32_t{}) == 0, "");
+ static_assert(bit_width(uint32_t{1}) == 1, "");
+ static_assert(bit_width(uint32_t{3}) == 2, "");
+ static_assert(bit_width(~uint32_t{}) == 32, "");
+ static_assert(bit_width(uint64_t{}) == 0, "");
+ static_assert(bit_width(uint64_t{1}) == 1, "");
+ static_assert(bit_width(uint64_t{3}) == 2, "");
+ static_assert(bit_width(~uint64_t{}) == 64, "");
+#endif
+
+ EXPECT_EQ(bit_width(uint8_t{}), 0);
+ EXPECT_EQ(bit_width(uint8_t{1}), 1);
+ EXPECT_EQ(bit_width(uint8_t{3}), 2);
+ EXPECT_EQ(bit_width(static_cast<uint8_t>(-1)), 8);
+ EXPECT_EQ(bit_width(uint16_t{}), 0);
+ EXPECT_EQ(bit_width(uint16_t{1}), 1);
+ EXPECT_EQ(bit_width(uint16_t{3}), 2);
+ EXPECT_EQ(bit_width(static_cast<uint16_t>(-1)), 16);
+ EXPECT_EQ(bit_width(uint32_t{}), 0);
+ EXPECT_EQ(bit_width(uint32_t{1}), 1);
+ EXPECT_EQ(bit_width(uint32_t{3}), 2);
+ EXPECT_EQ(bit_width(~uint32_t{}), 32);
+ EXPECT_EQ(bit_width(uint64_t{}), 0);
+ EXPECT_EQ(bit_width(uint64_t{1}), 1);
+ EXPECT_EQ(bit_width(uint64_t{3}), 2);
+ EXPECT_EQ(bit_width(~uint64_t{}), 64);
+
+ for (int i = 0; i < 8; i++) {
+ EXPECT_EQ(bit_width(static_cast<uint8_t>(uint8_t{1} << i)), i + 1);
+ }
+
+ for (int i = 0; i < 16; i++) {
+ EXPECT_EQ(bit_width(static_cast<uint16_t>(uint16_t{1} << i)), i + 1);
+ }
+
+ for (int i = 0; i < 32; i++) {
+ EXPECT_EQ(bit_width(uint32_t{1} << i), i + 1);
+ }
+
+ for (int i = 0; i < 64; i++) {
+ EXPECT_EQ(bit_width(uint64_t{1} << i), i + 1);
+ }
+}
+
+} // namespace
+ABSL_NAMESPACE_END
+} // namespace absl
diff --git a/absl/numeric/int128.cc b/absl/numeric/int128.cc
index 93b62c5..5160df7 100644
--- a/absl/numeric/int128.cc
+++ b/absl/numeric/int128.cc
@@ -15,6 +15,7 @@
#include "absl/numeric/int128.h"
#include <stddef.h>
+
#include <cassert>
#include <iomanip>
#include <ostream> // NOLINT(readability/streams)
@@ -22,52 +23,38 @@
#include <string>
#include <type_traits>
-namespace absl {
+#include "absl/base/optimization.h"
+#include "absl/numeric/bits.h"
-const uint128 kuint128max = MakeUint128(std::numeric_limits<uint64_t>::max(),
- std::numeric_limits<uint64_t>::max());
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+
+ABSL_DLL const uint128 kuint128max = MakeUint128(
+ std::numeric_limits<uint64_t>::max(), std::numeric_limits<uint64_t>::max());
namespace {
// Returns the 0-based position of the last set bit (i.e., most significant bit)
-// in the given uint64_t. The argument may not be 0.
+// in the given uint128. The argument is not 0.
//
// For example:
// Given: 5 (decimal) == 101 (binary)
// Returns: 2
-#define STEP(T, n, pos, sh) \
- do { \
- if ((n) >= (static_cast<T>(1) << (sh))) { \
- (n) = (n) >> (sh); \
- (pos) |= (sh); \
- } \
- } while (0)
-static inline int Fls64(uint64_t n) {
- assert(n != 0);
- int pos = 0;
- STEP(uint64_t, n, pos, 0x20);
- uint32_t n32 = static_cast<uint32_t>(n);
- STEP(uint32_t, n32, pos, 0x10);
- STEP(uint32_t, n32, pos, 0x08);
- STEP(uint32_t, n32, pos, 0x04);
- return pos + ((uint64_t{0x3333333322221100} >> (n32 << 2)) & 0x3);
-}
-#undef STEP
-
-// Like Fls64() above, but returns the 0-based position of the last set bit
-// (i.e., most significant bit) in the given uint128. The argument may not be 0.
-static inline int Fls128(uint128 n) {
+inline ABSL_ATTRIBUTE_ALWAYS_INLINE int Fls128(uint128 n) {
if (uint64_t hi = Uint128High64(n)) {
- return Fls64(hi) + 64;
+ ABSL_INTERNAL_ASSUME(hi != 0);
+ return 127 - countl_zero(hi);
}
- return Fls64(Uint128Low64(n));
+ const uint64_t low = Uint128Low64(n);
+ ABSL_INTERNAL_ASSUME(low != 0);
+ return 63 - countl_zero(low);
}
// Long division/modulo for uint128 implemented using the shift-subtract
// division algorithm adapted from:
// https://stackoverflow.com/questions/5386377/division-without-using
-void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret,
- uint128* remainder_ret) {
+inline void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret,
+ uint128* remainder_ret) {
assert(divisor != 0);
if (divisor > dividend) {
@@ -244,6 +231,112 @@
return os << rep;
}
+namespace {
+
+uint128 UnsignedAbsoluteValue(int128 v) {
+ // Cast to uint128 before possibly negating because -Int128Min() is undefined.
+ return Int128High64(v) < 0 ? -uint128(v) : uint128(v);
+}
+
+} // namespace
+
+#if !defined(ABSL_HAVE_INTRINSIC_INT128)
+namespace {
+
+template <typename T>
+int128 MakeInt128FromFloat(T v) {
+ // Conversion when v is NaN or cannot fit into int128 would be undefined
+ // behavior if using an intrinsic 128-bit integer.
+ assert(std::isfinite(v) && (std::numeric_limits<T>::max_exponent <= 127 ||
+ (v >= -std::ldexp(static_cast<T>(1), 127) &&
+ v < std::ldexp(static_cast<T>(1), 127))));
+
+ // We must convert the absolute value and then negate as needed, because
+ // floating point types are typically sign-magnitude. Otherwise, the
+ // difference between the high and low 64 bits when interpreted as two's
+ // complement overwhelms the precision of the mantissa.
+ uint128 result = v < 0 ? -MakeUint128FromFloat(-v) : MakeUint128FromFloat(v);
+ return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(result)),
+ Uint128Low64(result));
+}
+
+} // namespace
+
+int128::int128(float v) : int128(MakeInt128FromFloat(v)) {}
+int128::int128(double v) : int128(MakeInt128FromFloat(v)) {}
+int128::int128(long double v) : int128(MakeInt128FromFloat(v)) {}
+
+int128 operator/(int128 lhs, int128 rhs) {
+ assert(lhs != Int128Min() || rhs != -1); // UB on two's complement.
+
+ uint128 quotient = 0;
+ uint128 remainder = 0;
+ DivModImpl(UnsignedAbsoluteValue(lhs), UnsignedAbsoluteValue(rhs),
+ "ient, &remainder);
+ if ((Int128High64(lhs) < 0) != (Int128High64(rhs) < 0)) quotient = -quotient;
+ return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(quotient)),
+ Uint128Low64(quotient));
+}
+
+int128 operator%(int128 lhs, int128 rhs) {
+ assert(lhs != Int128Min() || rhs != -1); // UB on two's complement.
+
+ uint128 quotient = 0;
+ uint128 remainder = 0;
+ DivModImpl(UnsignedAbsoluteValue(lhs), UnsignedAbsoluteValue(rhs),
+ "ient, &remainder);
+ if (Int128High64(lhs) < 0) remainder = -remainder;
+ return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(remainder)),
+ Uint128Low64(remainder));
+}
+#endif // ABSL_HAVE_INTRINSIC_INT128
+
+std::ostream& operator<<(std::ostream& os, int128 v) {
+ std::ios_base::fmtflags flags = os.flags();
+ std::string rep;
+
+ // Add the sign if needed.
+ bool print_as_decimal =
+ (flags & std::ios::basefield) == std::ios::dec ||
+ (flags & std::ios::basefield) == std::ios_base::fmtflags();
+ if (print_as_decimal) {
+ if (Int128High64(v) < 0) {
+ rep = "-";
+ } else if (flags & std::ios::showpos) {
+ rep = "+";
+ }
+ }
+
+ rep.append(Uint128ToFormattedString(
+ print_as_decimal ? UnsignedAbsoluteValue(v) : uint128(v), os.flags()));
+
+ // Add the requisite padding.
+ std::streamsize width = os.width(0);
+ if (static_cast<size_t>(width) > rep.size()) {
+ switch (flags & std::ios::adjustfield) {
+ case std::ios::left:
+ rep.append(width - rep.size(), os.fill());
+ break;
+ case std::ios::internal:
+ if (print_as_decimal && (rep[0] == '+' || rep[0] == '-')) {
+ rep.insert(1, width - rep.size(), os.fill());
+ } else if ((flags & std::ios::basefield) == std::ios::hex &&
+ (flags & std::ios::showbase) && v != 0) {
+ rep.insert(2, width - rep.size(), os.fill());
+ } else {
+ rep.insert(0, width - rep.size(), os.fill());
+ }
+ break;
+ default: // std::ios::right
+ rep.insert(0, width - rep.size(), os.fill());
+ break;
+ }
+ }
+
+ return os << rep;
+}
+
+ABSL_NAMESPACE_END
} // namespace absl
namespace std {
@@ -270,4 +363,28 @@
constexpr int numeric_limits<absl::uint128>::max_exponent10;
constexpr bool numeric_limits<absl::uint128>::traps;
constexpr bool numeric_limits<absl::uint128>::tinyness_before;
+
+constexpr bool numeric_limits<absl::int128>::is_specialized;
+constexpr bool numeric_limits<absl::int128>::is_signed;
+constexpr bool numeric_limits<absl::int128>::is_integer;
+constexpr bool numeric_limits<absl::int128>::is_exact;
+constexpr bool numeric_limits<absl::int128>::has_infinity;
+constexpr bool numeric_limits<absl::int128>::has_quiet_NaN;
+constexpr bool numeric_limits<absl::int128>::has_signaling_NaN;
+constexpr float_denorm_style numeric_limits<absl::int128>::has_denorm;
+constexpr bool numeric_limits<absl::int128>::has_denorm_loss;
+constexpr float_round_style numeric_limits<absl::int128>::round_style;
+constexpr bool numeric_limits<absl::int128>::is_iec559;
+constexpr bool numeric_limits<absl::int128>::is_bounded;
+constexpr bool numeric_limits<absl::int128>::is_modulo;
+constexpr int numeric_limits<absl::int128>::digits;
+constexpr int numeric_limits<absl::int128>::digits10;
+constexpr int numeric_limits<absl::int128>::max_digits10;
+constexpr int numeric_limits<absl::int128>::radix;
+constexpr int numeric_limits<absl::int128>::min_exponent;
+constexpr int numeric_limits<absl::int128>::min_exponent10;
+constexpr int numeric_limits<absl::int128>::max_exponent;
+constexpr int numeric_limits<absl::int128>::max_exponent10;
+constexpr bool numeric_limits<absl::int128>::traps;
+constexpr bool numeric_limits<absl::int128>::tinyness_before;
} // namespace std
diff --git a/absl/numeric/int128.h b/absl/numeric/int128.h
index 10be8ec..0dd814a 100644
--- a/absl/numeric/int128.h
+++ b/absl/numeric/int128.h
@@ -17,10 +17,7 @@
// File: int128.h
// -----------------------------------------------------------------------------
//
-// This header file defines 128-bit integer types.
-//
-// Currently, this file defines `uint128`, an unsigned 128-bit integer;
-// a signed 128-bit integer is forthcoming.
+// This header file defines 128-bit integer types, `uint128` and `int128`.
#ifndef ABSL_NUMERIC_INT128_H_
#define ABSL_NUMERIC_INT128_H_
@@ -52,6 +49,9 @@
#endif // defined(_MSC_VER)
namespace absl {
+ABSL_NAMESPACE_BEGIN
+
+class int128;
// uint128
//
@@ -116,6 +116,7 @@
constexpr uint128(__int128 v); // NOLINT(runtime/explicit)
constexpr uint128(unsigned __int128 v); // NOLINT(runtime/explicit)
#endif // ABSL_HAVE_INTRINSIC_INT128
+ constexpr uint128(int128 v); // NOLINT(runtime/explicit)
explicit uint128(float v);
explicit uint128(double v);
explicit uint128(long double v);
@@ -131,6 +132,7 @@
uint128& operator=(__int128 v);
uint128& operator=(unsigned __int128 v);
#endif // ABSL_HAVE_INTRINSIC_INT128
+ uint128& operator=(int128 v);
// Conversion operators to other arithmetic types
constexpr explicit operator bool() const;
@@ -232,7 +234,7 @@
// Prefer to use the constexpr `Uint128Max()`.
//
// TODO(absl-team) deprecate kuint128max once migration tool is released.
-extern const uint128 kuint128max;
+ABSL_DLL extern const uint128 kuint128max;
// allow uint128 to be logged
std::ostream& operator<<(std::ostream& os, uint128 v);
@@ -244,6 +246,7 @@
(std::numeric_limits<uint64_t>::max)());
}
+ABSL_NAMESPACE_END
} // namespace absl
// Specialized numeric_limits for uint128.
@@ -291,12 +294,246 @@
};
} // namespace std
-// TODO(absl-team): Implement signed 128-bit type
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+
+// int128
+//
+// A signed 128-bit integer type. The API is meant to mimic an intrinsic
+// integral type as closely as is practical, including exhibiting undefined
+// behavior in analogous cases (e.g. division by zero).
+//
+// An `int128` supports the following:
+//
+// * Implicit construction from integral types
+// * Explicit conversion to integral types
+//
+// However, an `int128` differs from intrinsic integral types in the following
+// ways:
+//
+// * It is not implicitly convertible to other integral types.
+// * Requires explicit construction from and conversion to floating point
+// types.
+
+// Additionally, if your compiler supports `__int128`, `int128` is
+// interoperable with that type. (Abseil checks for this compatibility through
+// the `ABSL_HAVE_INTRINSIC_INT128` macro.)
+//
+// The design goal for `int128` is that it will be compatible with a future
+// `int128_t`, if that type becomes a part of the standard.
+//
+// Example:
+//
+// float y = absl::int128(17); // Error. int128 cannot be implicitly
+// // converted to float.
+//
+// absl::int128 v;
+// int64_t i = v; // Error
+// int64_t i = static_cast<int64_t>(v); // OK
+//
+class int128 {
+ public:
+ int128() = default;
+
+ // Constructors from arithmetic types
+ constexpr int128(int v); // NOLINT(runtime/explicit)
+ constexpr int128(unsigned int v); // NOLINT(runtime/explicit)
+ constexpr int128(long v); // NOLINT(runtime/int)
+ constexpr int128(unsigned long v); // NOLINT(runtime/int)
+ constexpr int128(long long v); // NOLINT(runtime/int)
+ constexpr int128(unsigned long long v); // NOLINT(runtime/int)
+#ifdef ABSL_HAVE_INTRINSIC_INT128
+ constexpr int128(__int128 v); // NOLINT(runtime/explicit)
+ constexpr explicit int128(unsigned __int128 v);
+#endif // ABSL_HAVE_INTRINSIC_INT128
+ constexpr explicit int128(uint128 v);
+ explicit int128(float v);
+ explicit int128(double v);
+ explicit int128(long double v);
+
+ // Assignment operators from arithmetic types
+ int128& operator=(int v);
+ int128& operator=(unsigned int v);
+ int128& operator=(long v); // NOLINT(runtime/int)
+ int128& operator=(unsigned long v); // NOLINT(runtime/int)
+ int128& operator=(long long v); // NOLINT(runtime/int)
+ int128& operator=(unsigned long long v); // NOLINT(runtime/int)
+#ifdef ABSL_HAVE_INTRINSIC_INT128
+ int128& operator=(__int128 v);
+#endif // ABSL_HAVE_INTRINSIC_INT128
+
+ // Conversion operators to other arithmetic types
+ constexpr explicit operator bool() const;
+ constexpr explicit operator char() const;
+ constexpr explicit operator signed char() const;
+ constexpr explicit operator unsigned char() const;
+ constexpr explicit operator char16_t() const;
+ constexpr explicit operator char32_t() const;
+ constexpr explicit operator ABSL_INTERNAL_WCHAR_T() const;
+ constexpr explicit operator short() const; // NOLINT(runtime/int)
+ // NOLINTNEXTLINE(runtime/int)
+ constexpr explicit operator unsigned short() const;
+ constexpr explicit operator int() const;
+ constexpr explicit operator unsigned int() const;
+ constexpr explicit operator long() const; // NOLINT(runtime/int)
+ // NOLINTNEXTLINE(runtime/int)
+ constexpr explicit operator unsigned long() const;
+ // NOLINTNEXTLINE(runtime/int)
+ constexpr explicit operator long long() const;
+ // NOLINTNEXTLINE(runtime/int)
+ constexpr explicit operator unsigned long long() const;
+#ifdef ABSL_HAVE_INTRINSIC_INT128
+ constexpr explicit operator __int128() const;
+ constexpr explicit operator unsigned __int128() const;
+#endif // ABSL_HAVE_INTRINSIC_INT128
+ explicit operator float() const;
+ explicit operator double() const;
+ explicit operator long double() const;
+
+ // Trivial copy constructor, assignment operator and destructor.
+
+ // Arithmetic operators
+ int128& operator+=(int128 other);
+ int128& operator-=(int128 other);
+ int128& operator*=(int128 other);
+ int128& operator/=(int128 other);
+ int128& operator%=(int128 other);
+ int128 operator++(int); // postfix increment: i++
+ int128 operator--(int); // postfix decrement: i--
+ int128& operator++(); // prefix increment: ++i
+ int128& operator--(); // prefix decrement: --i
+ int128& operator&=(int128 other);
+ int128& operator|=(int128 other);
+ int128& operator^=(int128 other);
+ int128& operator<<=(int amount);
+ int128& operator>>=(int amount);
+
+ // Int128Low64()
+ //
+ // Returns the lower 64-bit value of a `int128` value.
+ friend constexpr uint64_t Int128Low64(int128 v);
+
+ // Int128High64()
+ //
+ // Returns the higher 64-bit value of a `int128` value.
+ friend constexpr int64_t Int128High64(int128 v);
+
+ // MakeInt128()
+ //
+ // Constructs a `int128` numeric value from two 64-bit integers. Note that
+ // signedness is conveyed in the upper `high` value.
+ //
+ // (absl::int128(1) << 64) * high + low
+ //
+ // Note that this factory function is the only way to construct a `int128`
+ // from integer values greater than 2^64 or less than -2^64.
+ //
+ // Example:
+ //
+ // absl::int128 big = absl::MakeInt128(1, 0);
+ // absl::int128 big_n = absl::MakeInt128(-1, 0);
+ friend constexpr int128 MakeInt128(int64_t high, uint64_t low);
+
+ // Int128Max()
+ //
+ // Returns the maximum value for a 128-bit signed integer.
+ friend constexpr int128 Int128Max();
+
+ // Int128Min()
+ //
+ // Returns the minimum value for a 128-bit signed integer.
+ friend constexpr int128 Int128Min();
+
+ // Support for absl::Hash.
+ template <typename H>
+ friend H AbslHashValue(H h, int128 v) {
+ return H::combine(std::move(h), Int128High64(v), Int128Low64(v));
+ }
+
+ private:
+ constexpr int128(int64_t high, uint64_t low);
+
+#if defined(ABSL_HAVE_INTRINSIC_INT128)
+ __int128 v_;
+#else // ABSL_HAVE_INTRINSIC_INT128
+#if defined(ABSL_IS_LITTLE_ENDIAN)
+ uint64_t lo_;
+ int64_t hi_;
+#elif defined(ABSL_IS_BIG_ENDIAN)
+ int64_t hi_;
+ uint64_t lo_;
+#else // byte order
+#error "Unsupported byte order: must be little-endian or big-endian."
+#endif // byte order
+#endif // ABSL_HAVE_INTRINSIC_INT128
+};
+
+std::ostream& operator<<(std::ostream& os, int128 v);
+
+// TODO(absl-team) add operator>>(std::istream&, int128)
+
+constexpr int128 Int128Max() {
+ return int128((std::numeric_limits<int64_t>::max)(),
+ (std::numeric_limits<uint64_t>::max)());
+}
+
+constexpr int128 Int128Min() {
+ return int128((std::numeric_limits<int64_t>::min)(), 0);
+}
+
+ABSL_NAMESPACE_END
+} // namespace absl
+
+// Specialized numeric_limits for int128.
+namespace std {
+template <>
+class numeric_limits<absl::int128> {
+ public:
+ static constexpr bool is_specialized = true;
+ static constexpr bool is_signed = true;
+ static constexpr bool is_integer = true;
+ static constexpr bool is_exact = true;
+ static constexpr bool has_infinity = false;
+ static constexpr bool has_quiet_NaN = false;
+ static constexpr bool has_signaling_NaN = false;
+ static constexpr float_denorm_style has_denorm = denorm_absent;
+ static constexpr bool has_denorm_loss = false;
+ static constexpr float_round_style round_style = round_toward_zero;
+ static constexpr bool is_iec559 = false;
+ static constexpr bool is_bounded = true;
+ static constexpr bool is_modulo = false;
+ static constexpr int digits = 127;
+ static constexpr int digits10 = 38;
+ static constexpr int max_digits10 = 0;
+ static constexpr int radix = 2;
+ static constexpr int min_exponent = 0;
+ static constexpr int min_exponent10 = 0;
+ static constexpr int max_exponent = 0;
+ static constexpr int max_exponent10 = 0;
+#ifdef ABSL_HAVE_INTRINSIC_INT128
+ static constexpr bool traps = numeric_limits<__int128>::traps;
+#else // ABSL_HAVE_INTRINSIC_INT128
+ static constexpr bool traps = numeric_limits<uint64_t>::traps;
+#endif // ABSL_HAVE_INTRINSIC_INT128
+ static constexpr bool tinyness_before = false;
+
+ static constexpr absl::int128 (min)() { return absl::Int128Min(); }
+ static constexpr absl::int128 lowest() { return absl::Int128Min(); }
+ static constexpr absl::int128 (max)() { return absl::Int128Max(); }
+ static constexpr absl::int128 epsilon() { return 0; }
+ static constexpr absl::int128 round_error() { return 0; }
+ static constexpr absl::int128 infinity() { return 0; }
+ static constexpr absl::int128 quiet_NaN() { return 0; }
+ static constexpr absl::int128 signaling_NaN() { return 0; }
+ static constexpr absl::int128 denorm_min() { return 0; }
+};
+} // namespace std
// --------------------------------------------------------------------------
// Implementation details follow
// --------------------------------------------------------------------------
namespace absl {
+ABSL_NAMESPACE_BEGIN
constexpr uint128 MakeUint128(uint64_t high, uint64_t low) {
return uint128(high, low);
@@ -339,6 +576,10 @@
}
#endif // ABSL_HAVE_INTRINSIC_INT128
+inline uint128& uint128::operator=(int128 v) {
+ return *this = uint128(v);
+}
+
// Arithmetic operators.
uint128 operator<<(uint128 lhs, int amount);
@@ -420,6 +661,9 @@
hi_{static_cast<uint64_t>(v >> 64)} {}
#endif // ABSL_HAVE_INTRINSIC_INT128
+constexpr uint128::uint128(int128 v)
+ : lo_{Int128Low64(v)}, hi_{static_cast<uint64_t>(Int128High64(v))} {}
+
#elif defined(ABSL_IS_BIG_ENDIAN)
constexpr uint128::uint128(uint64_t high, uint64_t low)
@@ -450,6 +694,9 @@
lo_{static_cast<uint64_t>(v & ~uint64_t{0})} {}
#endif // ABSL_HAVE_INTRINSIC_INT128
+constexpr uint128::uint128(int128 v)
+ : hi_{static_cast<uint64_t>(Int128High64(v))}, lo_{Int128Low64(v)} {}
+
#else // byte order
#error "Unsupported byte order: must be little-endian or big-endian."
#endif // byte order
@@ -545,28 +792,21 @@
}
inline bool operator<(uint128 lhs, uint128 rhs) {
+#ifdef ABSL_HAVE_INTRINSIC_INT128
+ return static_cast<unsigned __int128>(lhs) <
+ static_cast<unsigned __int128>(rhs);
+#else
return (Uint128High64(lhs) == Uint128High64(rhs))
? (Uint128Low64(lhs) < Uint128Low64(rhs))
: (Uint128High64(lhs) < Uint128High64(rhs));
+#endif
}
-inline bool operator>(uint128 lhs, uint128 rhs) {
- return (Uint128High64(lhs) == Uint128High64(rhs))
- ? (Uint128Low64(lhs) > Uint128Low64(rhs))
- : (Uint128High64(lhs) > Uint128High64(rhs));
-}
+inline bool operator>(uint128 lhs, uint128 rhs) { return rhs < lhs; }
-inline bool operator<=(uint128 lhs, uint128 rhs) {
- return (Uint128High64(lhs) == Uint128High64(rhs))
- ? (Uint128Low64(lhs) <= Uint128Low64(rhs))
- : (Uint128High64(lhs) <= Uint128High64(rhs));
-}
+inline bool operator<=(uint128 lhs, uint128 rhs) { return !(rhs < lhs); }
-inline bool operator>=(uint128 lhs, uint128 rhs) {
- return (Uint128High64(lhs) == Uint128High64(rhs))
- ? (Uint128Low64(lhs) >= Uint128Low64(rhs))
- : (Uint128High64(lhs) >= Uint128High64(rhs));
-}
+inline bool operator>=(uint128 lhs, uint128 rhs) { return !(lhs < rhs); }
// Unary operators.
@@ -623,6 +863,9 @@
// Arithmetic operators.
inline 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) {
@@ -634,9 +877,13 @@
return lhs;
}
return MakeUint128(Uint128Low64(lhs) << (amount - 64), 0);
+#endif
}
inline 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) {
@@ -648,6 +895,7 @@
return lhs;
}
return MakeUint128(0, Uint128High64(lhs) >> (amount - 64));
+#endif
}
inline uint128 operator+(uint128 lhs, uint128 rhs) {
@@ -719,12 +967,124 @@
return *this;
}
+constexpr int128 MakeInt128(int64_t high, uint64_t low) {
+ return int128(high, low);
+}
+
+// Assignment from integer types.
+inline int128& int128::operator=(int v) {
+ return *this = int128(v);
+}
+
+inline int128& int128::operator=(unsigned int v) {
+ return *this = int128(v);
+}
+
+inline int128& int128::operator=(long v) { // NOLINT(runtime/int)
+ return *this = int128(v);
+}
+
+// NOLINTNEXTLINE(runtime/int)
+inline int128& int128::operator=(unsigned long v) {
+ return *this = int128(v);
+}
+
+// NOLINTNEXTLINE(runtime/int)
+inline int128& int128::operator=(long long v) {
+ return *this = int128(v);
+}
+
+// NOLINTNEXTLINE(runtime/int)
+inline int128& int128::operator=(unsigned long long v) {
+ return *this = int128(v);
+}
+
+// Arithmetic operators.
+
+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, int128 rhs);
+int128 operator<<(int128 lhs, int amount);
+int128 operator>>(int128 lhs, int amount);
+
+inline int128& int128::operator+=(int128 other) {
+ *this = *this + other;
+ return *this;
+}
+
+inline int128& int128::operator-=(int128 other) {
+ *this = *this - other;
+ return *this;
+}
+
+inline int128& int128::operator*=(int128 other) {
+ *this = *this * other;
+ return *this;
+}
+
+inline int128& int128::operator/=(int128 other) {
+ *this = *this / other;
+ return *this;
+}
+
+inline int128& int128::operator%=(int128 other) {
+ *this = *this % other;
+ return *this;
+}
+
+inline int128& int128::operator|=(int128 other) {
+ *this = *this | other;
+ return *this;
+}
+
+inline int128& int128::operator&=(int128 other) {
+ *this = *this & other;
+ return *this;
+}
+
+inline int128& int128::operator^=(int128 other) {
+ *this = *this ^ other;
+ return *this;
+}
+
+inline int128& int128::operator<<=(int amount) {
+ *this = *this << amount;
+ return *this;
+}
+
+inline int128& int128::operator>>=(int amount) {
+ *this = *this >> amount;
+ return *this;
+}
+
+namespace int128_internal {
+
+// Casts from unsigned to signed while preserving the underlying binary
+// representation.
+constexpr int64_t BitCastToSigned(uint64_t v) {
+ // Casting an unsigned integer to a signed integer of the same
+ // width is implementation defined behavior if the source value would not fit
+ // in the destination type. We step around it with a roundtrip bitwise not
+ // operation to make sure this function remains constexpr. Clang, GCC, and
+ // MSVC optimize this to a no-op on x86-64.
+ return v & (uint64_t{1} << 63) ? ~static_cast<int64_t>(~v)
+ : static_cast<int64_t>(v);
+}
+
+} // namespace int128_internal
+
#if defined(ABSL_HAVE_INTRINSIC_INT128)
-#include "absl/numeric/int128_have_intrinsic.inc"
+#include "absl/numeric/int128_have_intrinsic.inc" // IWYU pragma: export
#else // ABSL_HAVE_INTRINSIC_INT128
-#include "absl/numeric/int128_no_intrinsic.inc"
+#include "absl/numeric/int128_no_intrinsic.inc" // IWYU pragma: export
#endif // ABSL_HAVE_INTRINSIC_INT128
+ABSL_NAMESPACE_END
} // namespace absl
#undef ABSL_INTERNAL_WCHAR_T
diff --git a/absl/numeric/int128_benchmark.cc b/absl/numeric/int128_benchmark.cc
index a5502d9..eab1515 100644
--- a/absl/numeric/int128_benchmark.cc
+++ b/absl/numeric/int128_benchmark.cc
@@ -12,15 +12,15 @@
// See the License for the specific language governing permissions and
// limitations under the License.
-#include "absl/numeric/int128.h"
-
#include <algorithm>
#include <cstdint>
+#include <limits>
#include <random>
#include <vector>
#include "benchmark/benchmark.h"
#include "absl/base/config.h"
+#include "absl/numeric/int128.h"
namespace {
@@ -32,57 +32,85 @@
return std::mt19937(seed);
}
-std::vector<std::pair<absl::uint128, absl::uint128>>
-GetRandomClass128SampleUniformDivisor() {
- std::vector<std::pair<absl::uint128, absl::uint128>> values;
+template <typename T,
+ typename H = typename std::conditional<
+ std::numeric_limits<T>::is_signed, int64_t, uint64_t>::type>
+std::vector<std::pair<T, T>> GetRandomClass128SampleUniformDivisor() {
+ std::vector<std::pair<T, T>> values;
std::mt19937 random = MakeRandomEngine();
- std::uniform_int_distribution<uint64_t> uniform_uint64;
+ std::uniform_int_distribution<H> uniform_h;
values.reserve(kSampleSize);
for (size_t i = 0; i < kSampleSize; ++i) {
- absl::uint128 a =
- absl::MakeUint128(uniform_uint64(random), uniform_uint64(random));
- absl::uint128 b =
- absl::MakeUint128(uniform_uint64(random), uniform_uint64(random));
- values.emplace_back(std::max(a, b),
- std::max(absl::uint128(2), std::min(a, b)));
+ T a{absl::MakeUint128(uniform_h(random), uniform_h(random))};
+ T b{absl::MakeUint128(uniform_h(random), uniform_h(random))};
+ values.emplace_back(std::max(a, b), std::max(T(2), std::min(a, b)));
}
return values;
}
+template <typename T>
void BM_DivideClass128UniformDivisor(benchmark::State& state) {
- auto values = GetRandomClass128SampleUniformDivisor();
+ auto values = GetRandomClass128SampleUniformDivisor<T>();
while (state.KeepRunningBatch(values.size())) {
for (const auto& pair : values) {
benchmark::DoNotOptimize(pair.first / pair.second);
}
}
}
-BENCHMARK(BM_DivideClass128UniformDivisor);
+BENCHMARK_TEMPLATE(BM_DivideClass128UniformDivisor, absl::uint128);
+BENCHMARK_TEMPLATE(BM_DivideClass128UniformDivisor, absl::int128);
-std::vector<std::pair<absl::uint128, uint64_t>>
-GetRandomClass128SampleSmallDivisor() {
- std::vector<std::pair<absl::uint128, uint64_t>> values;
+template <typename T>
+void BM_RemainderClass128UniformDivisor(benchmark::State& state) {
+ auto values = GetRandomClass128SampleUniformDivisor<T>();
+ while (state.KeepRunningBatch(values.size())) {
+ for (const auto& pair : values) {
+ benchmark::DoNotOptimize(pair.first % pair.second);
+ }
+ }
+}
+BENCHMARK_TEMPLATE(BM_RemainderClass128UniformDivisor, absl::uint128);
+BENCHMARK_TEMPLATE(BM_RemainderClass128UniformDivisor, absl::int128);
+
+template <typename T,
+ typename H = typename std::conditional<
+ std::numeric_limits<T>::is_signed, int64_t, uint64_t>::type>
+std::vector<std::pair<T, H>> GetRandomClass128SampleSmallDivisor() {
+ std::vector<std::pair<T, H>> values;
std::mt19937 random = MakeRandomEngine();
- std::uniform_int_distribution<uint64_t> uniform_uint64;
+ std::uniform_int_distribution<H> uniform_h;
values.reserve(kSampleSize);
for (size_t i = 0; i < kSampleSize; ++i) {
- absl::uint128 a =
- absl::MakeUint128(uniform_uint64(random), uniform_uint64(random));
- uint64_t b = std::max(uint64_t{2}, uniform_uint64(random));
- values.emplace_back(std::max(a, absl::uint128(b)), b);
+ T a{absl::MakeUint128(uniform_h(random), uniform_h(random))};
+ H b{std::max(H{2}, uniform_h(random))};
+ values.emplace_back(std::max(a, T(b)), b);
}
return values;
}
+template <typename T>
void BM_DivideClass128SmallDivisor(benchmark::State& state) {
- auto values = GetRandomClass128SampleSmallDivisor();
+ auto values = GetRandomClass128SampleSmallDivisor<T>();
while (state.KeepRunningBatch(values.size())) {
for (const auto& pair : values) {
benchmark::DoNotOptimize(pair.first / pair.second);
}
}
}
-BENCHMARK(BM_DivideClass128SmallDivisor);
+BENCHMARK_TEMPLATE(BM_DivideClass128SmallDivisor, absl::uint128);
+BENCHMARK_TEMPLATE(BM_DivideClass128SmallDivisor, absl::int128);
+
+template <typename T>
+void BM_RemainderClass128SmallDivisor(benchmark::State& state) {
+ auto values = GetRandomClass128SampleSmallDivisor<T>();
+ while (state.KeepRunningBatch(values.size())) {
+ for (const auto& pair : values) {
+ benchmark::DoNotOptimize(pair.first % pair.second);
+ }
+ }
+}
+BENCHMARK_TEMPLATE(BM_RemainderClass128SmallDivisor, absl::uint128);
+BENCHMARK_TEMPLATE(BM_RemainderClass128SmallDivisor, absl::int128);
std::vector<std::pair<absl::uint128, absl::uint128>> GetRandomClass128Sample() {
std::vector<std::pair<absl::uint128, absl::uint128>> values;
@@ -121,74 +149,107 @@
// Some implementations of <random> do not support __int128 when it is
// available, so we make our own uniform_int_distribution-like type.
+template <typename T,
+ typename H = typename std::conditional<
+ std::is_same<T, __int128>::value, int64_t, uint64_t>::type>
class UniformIntDistribution128 {
public:
// NOLINTNEXTLINE: mimicking std::uniform_int_distribution API
- unsigned __int128 operator()(std::mt19937& generator) {
- return (static_cast<unsigned __int128>(dist64_(generator)) << 64) |
- dist64_(generator);
+ T operator()(std::mt19937& generator) {
+ return (static_cast<T>(dist64_(generator)) << 64) | dist64_(generator);
}
private:
- std::uniform_int_distribution<uint64_t> dist64_;
+ std::uniform_int_distribution<H> dist64_;
};
-std::vector<std::pair<unsigned __int128, unsigned __int128>>
-GetRandomIntrinsic128SampleUniformDivisor() {
- std::vector<std::pair<unsigned __int128, unsigned __int128>> values;
+template <typename T,
+ typename H = typename std::conditional<
+ std::is_same<T, __int128>::value, int64_t, uint64_t>::type>
+std::vector<std::pair<T, T>> GetRandomIntrinsic128SampleUniformDivisor() {
+ std::vector<std::pair<T, T>> values;
std::mt19937 random = MakeRandomEngine();
- UniformIntDistribution128 uniform_uint128;
+ UniformIntDistribution128<T> uniform_128;
values.reserve(kSampleSize);
for (size_t i = 0; i < kSampleSize; ++i) {
- unsigned __int128 a = uniform_uint128(random);
- unsigned __int128 b = uniform_uint128(random);
- values.emplace_back(
- std::max(a, b),
- std::max(static_cast<unsigned __int128>(2), std::min(a, b)));
+ T a = uniform_128(random);
+ T b = uniform_128(random);
+ values.emplace_back(std::max(a, b),
+ std::max(static_cast<T>(2), std::min(a, b)));
}
return values;
}
+template <typename T>
void BM_DivideIntrinsic128UniformDivisor(benchmark::State& state) {
- auto values = GetRandomIntrinsic128SampleUniformDivisor();
+ auto values = GetRandomIntrinsic128SampleUniformDivisor<T>();
while (state.KeepRunningBatch(values.size())) {
for (const auto& pair : values) {
benchmark::DoNotOptimize(pair.first / pair.second);
}
}
}
-BENCHMARK(BM_DivideIntrinsic128UniformDivisor);
+BENCHMARK_TEMPLATE(BM_DivideIntrinsic128UniformDivisor, unsigned __int128);
+BENCHMARK_TEMPLATE(BM_DivideIntrinsic128UniformDivisor, __int128);
-std::vector<std::pair<unsigned __int128, uint64_t>>
-GetRandomIntrinsic128SampleSmallDivisor() {
- std::vector<std::pair<unsigned __int128, uint64_t>> values;
+template <typename T>
+void BM_RemainderIntrinsic128UniformDivisor(benchmark::State& state) {
+ auto values = GetRandomIntrinsic128SampleUniformDivisor<T>();
+ while (state.KeepRunningBatch(values.size())) {
+ for (const auto& pair : values) {
+ benchmark::DoNotOptimize(pair.first % pair.second);
+ }
+ }
+}
+BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128UniformDivisor, unsigned __int128);
+BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128UniformDivisor, __int128);
+
+template <typename T,
+ typename H = typename std::conditional<
+ std::is_same<T, __int128>::value, int64_t, uint64_t>::type>
+std::vector<std::pair<T, H>> GetRandomIntrinsic128SampleSmallDivisor() {
+ std::vector<std::pair<T, H>> values;
std::mt19937 random = MakeRandomEngine();
- UniformIntDistribution128 uniform_uint128;
- std::uniform_int_distribution<uint64_t> uniform_uint64;
+ UniformIntDistribution128<T> uniform_int128;
+ std::uniform_int_distribution<H> uniform_int64;
values.reserve(kSampleSize);
for (size_t i = 0; i < kSampleSize; ++i) {
- unsigned __int128 a = uniform_uint128(random);
- uint64_t b = std::max(uint64_t{2}, uniform_uint64(random));
- values.emplace_back(std::max(a, static_cast<unsigned __int128>(b)), b);
+ T a = uniform_int128(random);
+ H b = std::max(H{2}, uniform_int64(random));
+ values.emplace_back(std::max(a, static_cast<T>(b)), b);
}
return values;
}
+template <typename T>
void BM_DivideIntrinsic128SmallDivisor(benchmark::State& state) {
- auto values = GetRandomIntrinsic128SampleSmallDivisor();
+ auto values = GetRandomIntrinsic128SampleSmallDivisor<T>();
while (state.KeepRunningBatch(values.size())) {
for (const auto& pair : values) {
benchmark::DoNotOptimize(pair.first / pair.second);
}
}
}
-BENCHMARK(BM_DivideIntrinsic128SmallDivisor);
+BENCHMARK_TEMPLATE(BM_DivideIntrinsic128SmallDivisor, unsigned __int128);
+BENCHMARK_TEMPLATE(BM_DivideIntrinsic128SmallDivisor, __int128);
+
+template <typename T>
+void BM_RemainderIntrinsic128SmallDivisor(benchmark::State& state) {
+ auto values = GetRandomIntrinsic128SampleSmallDivisor<T>();
+ while (state.KeepRunningBatch(values.size())) {
+ for (const auto& pair : values) {
+ benchmark::DoNotOptimize(pair.first % pair.second);
+ }
+ }
+}
+BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128SmallDivisor, unsigned __int128);
+BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128SmallDivisor, __int128);
std::vector<std::pair<unsigned __int128, unsigned __int128>>
GetRandomIntrinsic128Sample() {
std::vector<std::pair<unsigned __int128, unsigned __int128>> values;
std::mt19937 random = MakeRandomEngine();
- UniformIntDistribution128 uniform_uint128;
+ UniformIntDistribution128<unsigned __int128> uniform_uint128;
values.reserve(kSampleSize);
for (size_t i = 0; i < kSampleSize; ++i) {
values.emplace_back(uniform_uint128(random), uniform_uint128(random));
diff --git a/absl/numeric/int128_have_intrinsic.inc b/absl/numeric/int128_have_intrinsic.inc
index c7ea683..d6c76dd 100644
--- a/absl/numeric/int128_have_intrinsic.inc
+++ b/absl/numeric/int128_have_intrinsic.inc
@@ -16,3 +16,287 @@
// This file contains :int128 implementation details that depend on internal
// representation when ABSL_HAVE_INTRINSIC_INT128 is defined. This file is
// included by int128.h and relies on ABSL_INTERNAL_WCHAR_T being defined.
+
+namespace int128_internal {
+
+// Casts from unsigned to signed while preserving the underlying binary
+// representation.
+constexpr __int128 BitCastToSigned(unsigned __int128 v) {
+ // Casting an unsigned integer to a signed integer of the same
+ // width is implementation defined behavior if the source value would not fit
+ // in the destination type. We step around it with a roundtrip bitwise not
+ // operation to make sure this function remains constexpr. Clang and GCC
+ // optimize this to a no-op on x86-64.
+ return v & (static_cast<unsigned __int128>(1) << 127)
+ ? ~static_cast<__int128>(~v)
+ : static_cast<__int128>(v);
+}
+
+} // namespace int128_internal
+
+inline int128& int128::operator=(__int128 v) {
+ v_ = v;
+ return *this;
+}
+
+constexpr uint64_t Int128Low64(int128 v) {
+ return static_cast<uint64_t>(v.v_ & ~uint64_t{0});
+}
+
+constexpr int64_t Int128High64(int128 v) {
+ // Initially cast to unsigned to prevent a right shift on a negative value.
+ return int128_internal::BitCastToSigned(
+ static_cast<uint64_t>(static_cast<unsigned __int128>(v.v_) >> 64));
+}
+
+constexpr int128::int128(int64_t high, uint64_t low)
+ // Initially cast to unsigned to prevent a left shift that overflows.
+ : v_(int128_internal::BitCastToSigned(static_cast<unsigned __int128>(high)
+ << 64) |
+ low) {}
+
+
+constexpr int128::int128(int v) : v_{v} {}
+
+constexpr int128::int128(long v) : v_{v} {} // NOLINT(runtime/int)
+
+constexpr int128::int128(long long v) : v_{v} {} // NOLINT(runtime/int)
+
+constexpr int128::int128(__int128 v) : v_{v} {}
+
+constexpr int128::int128(unsigned int v) : v_{v} {}
+
+constexpr int128::int128(unsigned long v) : v_{v} {} // NOLINT(runtime/int)
+
+// NOLINTNEXTLINE(runtime/int)
+constexpr int128::int128(unsigned long long v) : v_{v} {}
+
+constexpr int128::int128(unsigned __int128 v) : v_{static_cast<__int128>(v)} {}
+
+inline int128::int128(float v) {
+ v_ = static_cast<__int128>(v);
+}
+
+inline int128::int128(double v) {
+ v_ = static_cast<__int128>(v);
+}
+
+inline int128::int128(long double v) {
+ v_ = static_cast<__int128>(v);
+}
+
+constexpr int128::int128(uint128 v) : v_{static_cast<__int128>(v)} {}
+
+constexpr int128::operator bool() const { return static_cast<bool>(v_); }
+
+constexpr int128::operator char() const { return static_cast<char>(v_); }
+
+constexpr int128::operator signed char() const {
+ return static_cast<signed char>(v_);
+}
+
+constexpr int128::operator unsigned char() const {
+ return static_cast<unsigned char>(v_);
+}
+
+constexpr int128::operator char16_t() const {
+ return static_cast<char16_t>(v_);
+}
+
+constexpr int128::operator char32_t() const {
+ return static_cast<char32_t>(v_);
+}
+
+constexpr int128::operator ABSL_INTERNAL_WCHAR_T() const {
+ return static_cast<ABSL_INTERNAL_WCHAR_T>(v_);
+}
+
+constexpr int128::operator short() const { // NOLINT(runtime/int)
+ return static_cast<short>(v_); // NOLINT(runtime/int)
+}
+
+constexpr int128::operator unsigned short() const { // NOLINT(runtime/int)
+ return static_cast<unsigned short>(v_); // NOLINT(runtime/int)
+}
+
+constexpr int128::operator int() const {
+ return static_cast<int>(v_);
+}
+
+constexpr int128::operator unsigned int() const {
+ return static_cast<unsigned int>(v_);
+}
+
+constexpr int128::operator long() const { // NOLINT(runtime/int)
+ return static_cast<long>(v_); // NOLINT(runtime/int)
+}
+
+constexpr int128::operator unsigned long() const { // NOLINT(runtime/int)
+ return static_cast<unsigned long>(v_); // NOLINT(runtime/int)
+}
+
+constexpr int128::operator long long() const { // NOLINT(runtime/int)
+ return static_cast<long long>(v_); // NOLINT(runtime/int)
+}
+
+constexpr int128::operator unsigned long long() const { // NOLINT(runtime/int)
+ return static_cast<unsigned long long>(v_); // NOLINT(runtime/int)
+}
+
+constexpr int128::operator __int128() const { return v_; }
+
+constexpr int128::operator unsigned __int128() const {
+ return static_cast<unsigned __int128>(v_);
+}
+
+// Clang on PowerPC sometimes produces incorrect __int128 to floating point
+// conversions. In that case, we do the conversion with a similar implementation
+// to the conversion operators in int128_no_intrinsic.inc.
+#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 long double() const {
+ return static_cast<long double>(v_);
+}
+
+#else // Clang on PowerPC
+// 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
+ // difference between the high and low 64 bits when interpreted as two's
+ // complement overwhelms the precision of the mantissa.
+ //
+ // Also check to make sure we don't negate Int128Min()
+ return v_ < 0 && *this != Int128Min()
+ ? -static_cast<float>(-*this)
+ : static_cast<float>(Int128Low64(*this)) +
+ std::ldexp(static_cast<float>(Int128High64(*this)), 64);
+}
+
+inline int128::operator double() const {
+ // See comment in int128::operator float() above.
+ return v_ < 0 && *this != Int128Min()
+ ? -static_cast<double>(-*this)
+ : static_cast<double>(Int128Low64(*this)) +
+ std::ldexp(static_cast<double>(Int128High64(*this)), 64);
+}
+
+inline int128::operator long double() const {
+ // See comment in int128::operator float() above.
+ return v_ < 0 && *this != Int128Min()
+ ? -static_cast<long double>(-*this)
+ : static_cast<long double>(Int128Low64(*this)) +
+ std::ldexp(static_cast<long double>(Int128High64(*this)),
+ 64);
+}
+#endif // Clang on PowerPC
+
+// Comparison operators.
+
+inline bool operator==(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) == static_cast<__int128>(rhs);
+}
+
+inline bool operator!=(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) != static_cast<__int128>(rhs);
+}
+
+inline bool operator<(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) < static_cast<__int128>(rhs);
+}
+
+inline bool operator>(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) > static_cast<__int128>(rhs);
+}
+
+inline bool operator<=(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) <= static_cast<__int128>(rhs);
+}
+
+inline 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);
+}
+
+inline bool operator!(int128 v) {
+ return !static_cast<__int128>(v);
+}
+
+inline int128 operator~(int128 val) {
+ return ~static_cast<__int128>(val);
+}
+
+// Arithmetic operators.
+
+inline int128 operator+(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) + static_cast<__int128>(rhs);
+}
+
+inline int128 operator-(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) - static_cast<__int128>(rhs);
+}
+
+inline int128 operator*(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) * static_cast<__int128>(rhs);
+}
+
+inline int128 operator/(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) / static_cast<__int128>(rhs);
+}
+
+inline int128 operator%(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) % static_cast<__int128>(rhs);
+}
+
+inline int128 int128::operator++(int) {
+ int128 tmp(*this);
+ ++v_;
+ return tmp;
+}
+
+inline int128 int128::operator--(int) {
+ int128 tmp(*this);
+ --v_;
+ return tmp;
+}
+
+inline int128& int128::operator++() {
+ ++v_;
+ return *this;
+}
+
+inline int128& int128::operator--() {
+ --v_;
+ return *this;
+}
+
+inline int128 operator|(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) | static_cast<__int128>(rhs);
+}
+
+inline int128 operator&(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) & static_cast<__int128>(rhs);
+}
+
+inline int128 operator^(int128 lhs, int128 rhs) {
+ return static_cast<__int128>(lhs) ^ static_cast<__int128>(rhs);
+}
+
+inline int128 operator<<(int128 lhs, int amount) {
+ return static_cast<__int128>(lhs) << amount;
+}
+
+inline 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 046cb9b..c753771 100644
--- a/absl/numeric/int128_no_intrinsic.inc
+++ b/absl/numeric/int128_no_intrinsic.inc
@@ -16,3 +16,293 @@
// This file contains :int128 implementation details that depend on internal
// representation when ABSL_HAVE_INTRINSIC_INT128 is *not* defined. This file
// is included by int128.h and relies on ABSL_INTERNAL_WCHAR_T being defined.
+
+constexpr uint64_t Int128Low64(int128 v) { return v.lo_; }
+
+constexpr int64_t Int128High64(int128 v) { return v.hi_; }
+
+#if defined(ABSL_IS_LITTLE_ENDIAN)
+
+constexpr int128::int128(int64_t high, uint64_t low) :
+ lo_(low), hi_(high) {}
+
+constexpr int128::int128(int v)
+ : lo_{static_cast<uint64_t>(v)}, hi_{v < 0 ? ~int64_t{0} : 0} {}
+constexpr int128::int128(long v) // NOLINT(runtime/int)
+ : lo_{static_cast<uint64_t>(v)}, hi_{v < 0 ? ~int64_t{0} : 0} {}
+constexpr int128::int128(long long v) // NOLINT(runtime/int)
+ : lo_{static_cast<uint64_t>(v)}, hi_{v < 0 ? ~int64_t{0} : 0} {}
+
+constexpr int128::int128(unsigned int v) : lo_{v}, hi_{0} {}
+// NOLINTNEXTLINE(runtime/int)
+constexpr int128::int128(unsigned long v) : lo_{v}, hi_{0} {}
+// NOLINTNEXTLINE(runtime/int)
+constexpr int128::int128(unsigned long long v) : lo_{v}, hi_{0} {}
+
+constexpr int128::int128(uint128 v)
+ : lo_{Uint128Low64(v)}, hi_{static_cast<int64_t>(Uint128High64(v))} {}
+
+#elif defined(ABSL_IS_BIG_ENDIAN)
+
+constexpr int128::int128(int64_t high, uint64_t low) :
+ hi_{high}, lo_{low} {}
+
+constexpr int128::int128(int v)
+ : hi_{v < 0 ? ~int64_t{0} : 0}, lo_{static_cast<uint64_t>(v)} {}
+constexpr int128::int128(long v) // NOLINT(runtime/int)
+ : hi_{v < 0 ? ~int64_t{0} : 0}, lo_{static_cast<uint64_t>(v)} {}
+constexpr int128::int128(long long v) // NOLINT(runtime/int)
+ : hi_{v < 0 ? ~int64_t{0} : 0}, lo_{static_cast<uint64_t>(v)} {}
+
+constexpr int128::int128(unsigned int v) : hi_{0}, lo_{v} {}
+// NOLINTNEXTLINE(runtime/int)
+constexpr int128::int128(unsigned long v) : hi_{0}, lo_{v} {}
+// NOLINTNEXTLINE(runtime/int)
+constexpr int128::int128(unsigned long long v) : hi_{0}, lo_{v} {}
+
+constexpr int128::int128(uint128 v)
+ : hi_{static_cast<int64_t>(Uint128High64(v))}, lo_{Uint128Low64(v)} {}
+
+#else // byte order
+#error "Unsupported byte order: must be little-endian or big-endian."
+#endif // byte order
+
+constexpr int128::operator bool() const { return lo_ || hi_; }
+
+constexpr int128::operator char() const {
+ // NOLINTNEXTLINE(runtime/int)
+ return static_cast<char>(static_cast<long long>(*this));
+}
+
+constexpr int128::operator signed char() const {
+ // NOLINTNEXTLINE(runtime/int)
+ return static_cast<signed char>(static_cast<long long>(*this));
+}
+
+constexpr int128::operator unsigned char() const {
+ return static_cast<unsigned char>(lo_);
+}
+
+constexpr int128::operator char16_t() const {
+ return static_cast<char16_t>(lo_);
+}
+
+constexpr int128::operator char32_t() const {
+ return static_cast<char32_t>(lo_);
+}
+
+constexpr int128::operator ABSL_INTERNAL_WCHAR_T() const {
+ // NOLINTNEXTLINE(runtime/int)
+ return static_cast<ABSL_INTERNAL_WCHAR_T>(static_cast<long long>(*this));
+}
+
+constexpr int128::operator short() const { // NOLINT(runtime/int)
+ // NOLINTNEXTLINE(runtime/int)
+ return static_cast<short>(static_cast<long long>(*this));
+}
+
+constexpr int128::operator unsigned short() const { // NOLINT(runtime/int)
+ return static_cast<unsigned short>(lo_); // NOLINT(runtime/int)
+}
+
+constexpr int128::operator int() const {
+ // NOLINTNEXTLINE(runtime/int)
+ return static_cast<int>(static_cast<long long>(*this));
+}
+
+constexpr int128::operator unsigned int() const {
+ return static_cast<unsigned int>(lo_);
+}
+
+constexpr int128::operator long() const { // NOLINT(runtime/int)
+ // NOLINTNEXTLINE(runtime/int)
+ return static_cast<long>(static_cast<long long>(*this));
+}
+
+constexpr int128::operator unsigned long() const { // NOLINT(runtime/int)
+ return static_cast<unsigned long>(lo_); // NOLINT(runtime/int)
+}
+
+constexpr int128::operator long long() const { // NOLINT(runtime/int)
+ // We don't bother checking the value of hi_. If *this < 0, lo_'s high bit
+ // must be set in order for the value to fit into a long long. Conversely, if
+ // lo_'s high bit is set, *this must be < 0 for the value to fit.
+ return int128_internal::BitCastToSigned(lo_);
+}
+
+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
+ // difference between the high and low 64 bits when interpreted as two's
+ // complement overwhelms the precision of the mantissa.
+ //
+ // Also check to make sure we don't negate Int128Min()
+ return hi_ < 0 && *this != Int128Min()
+ ? -static_cast<float>(-*this)
+ : static_cast<float>(lo_) +
+ std::ldexp(static_cast<float>(hi_), 64);
+}
+
+inline int128::operator double() const {
+ // See comment in int128::operator float() above.
+ return hi_ < 0 && *this != Int128Min()
+ ? -static_cast<double>(-*this)
+ : static_cast<double>(lo_) +
+ std::ldexp(static_cast<double>(hi_), 64);
+}
+
+inline int128::operator long double() const {
+ // See comment in int128::operator float() above.
+ return hi_ < 0 && *this != Int128Min()
+ ? -static_cast<long double>(-*this)
+ : static_cast<long double>(lo_) +
+ std::ldexp(static_cast<long double>(hi_), 64);
+}
+
+// Comparison operators.
+
+inline 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);
+}
+
+inline 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 (Int128High64(lhs) == Int128High64(rhs))
+ ? (Int128Low64(lhs) > Int128Low64(rhs))
+ : (Int128High64(lhs) > Int128High64(rhs));
+}
+
+inline bool operator<=(int128 lhs, int128 rhs) {
+ return !(lhs > rhs);
+}
+
+inline 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);
+}
+
+inline bool operator!(int128 v) {
+ return !Int128Low64(v) && !Int128High64(v);
+}
+
+inline 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;
+}
+
+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;
+}
+
+inline int128 operator*(int128 lhs, int128 rhs) {
+ uint128 result = uint128(lhs) * rhs;
+ return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(result)),
+ Uint128Low64(result));
+}
+
+inline int128 int128::operator++(int) {
+ int128 tmp(*this);
+ *this += 1;
+ return tmp;
+}
+
+inline int128 int128::operator--(int) {
+ int128 tmp(*this);
+ *this -= 1;
+ return tmp;
+}
+
+inline int128& int128::operator++() {
+ *this += 1;
+ return *this;
+}
+
+inline int128& int128::operator--() {
+ *this -= 1;
+ return *this;
+}
+
+inline int128 operator|(int128 lhs, int128 rhs) {
+ return MakeInt128(Int128High64(lhs) | Int128High64(rhs),
+ Int128Low64(lhs) | Int128Low64(rhs));
+}
+
+inline int128 operator&(int128 lhs, int128 rhs) {
+ return MakeInt128(Int128High64(lhs) & Int128High64(rhs),
+ Int128Low64(lhs) & Int128Low64(rhs));
+}
+
+inline int128 operator^(int128 lhs, int128 rhs) {
+ return MakeInt128(Int128High64(lhs) ^ Int128High64(rhs),
+ Int128Low64(lhs) ^ Int128Low64(rhs));
+}
+
+inline 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) {
+ // 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)));
+}
diff --git a/absl/numeric/int128_stream_test.cc b/absl/numeric/int128_stream_test.cc
index 3cfa9dc..479ad66 100644
--- a/absl/numeric/int128_stream_test.cc
+++ b/absl/numeric/int128_stream_test.cc
@@ -147,6 +147,735 @@
}
}
+struct Int128TestCase {
+ absl::int128 value;
+ std::ios_base::fmtflags flags;
+ std::streamsize width;
+ const char* expected;
+};
+
+void CheckInt128Case(const Int128TestCase& test_case) {
+ std::ostringstream os;
+ os.flags(test_case.flags);
+ os.width(test_case.width);
+ os.fill(kFill);
+ os << test_case.value;
+ SCOPED_TRACE(StreamFormatToString(test_case.flags, test_case.width));
+ EXPECT_EQ(test_case.expected, os.str());
+}
+
+TEST(Int128, OStreamValueTest) {
+ CheckInt128Case({1, kDec, /*width = */ 0, "1"});
+ CheckInt128Case({1, kOct, /*width = */ 0, "1"});
+ CheckInt128Case({1, kHex, /*width = */ 0, "1"});
+ CheckInt128Case({9, kDec, /*width = */ 0, "9"});
+ CheckInt128Case({9, kOct, /*width = */ 0, "11"});
+ CheckInt128Case({9, kHex, /*width = */ 0, "9"});
+ CheckInt128Case({12345, kDec, /*width = */ 0, "12345"});
+ CheckInt128Case({12345, kOct, /*width = */ 0, "30071"});
+ CheckInt128Case({12345, kHex, /*width = */ 0, "3039"});
+ CheckInt128Case(
+ {0x8000000000000000, kDec, /*width = */ 0, "9223372036854775808"});
+ CheckInt128Case(
+ {0x8000000000000000, kOct, /*width = */ 0, "1000000000000000000000"});
+ CheckInt128Case(
+ {0x8000000000000000, kHex, /*width = */ 0, "8000000000000000"});
+ CheckInt128Case({std::numeric_limits<uint64_t>::max(), kDec,
+ /*width = */ 0, "18446744073709551615"});
+ CheckInt128Case({std::numeric_limits<uint64_t>::max(), kOct,
+ /*width = */ 0, "1777777777777777777777"});
+ CheckInt128Case({std::numeric_limits<uint64_t>::max(), kHex,
+ /*width = */ 0, "ffffffffffffffff"});
+ CheckInt128Case(
+ {absl::MakeInt128(1, 0), kDec, /*width = */ 0, "18446744073709551616"});
+ CheckInt128Case(
+ {absl::MakeInt128(1, 0), kOct, /*width = */ 0, "2000000000000000000000"});
+ CheckInt128Case(
+ {absl::MakeInt128(1, 0), kHex, /*width = */ 0, "10000000000000000"});
+ CheckInt128Case({absl::MakeInt128(std::numeric_limits<int64_t>::max(),
+ std::numeric_limits<uint64_t>::max()),
+ std::ios::dec, /*width = */ 0,
+ "170141183460469231731687303715884105727"});
+ CheckInt128Case({absl::MakeInt128(std::numeric_limits<int64_t>::max(),
+ std::numeric_limits<uint64_t>::max()),
+ std::ios::oct, /*width = */ 0,
+ "1777777777777777777777777777777777777777777"});
+ CheckInt128Case({absl::MakeInt128(std::numeric_limits<int64_t>::max(),
+ std::numeric_limits<uint64_t>::max()),
+ std::ios::hex, /*width = */ 0,
+ "7fffffffffffffffffffffffffffffff"});
+ CheckInt128Case({absl::MakeInt128(std::numeric_limits<int64_t>::min(), 0),
+ std::ios::dec, /*width = */ 0,
+ "-170141183460469231731687303715884105728"});
+ CheckInt128Case({absl::MakeInt128(std::numeric_limits<int64_t>::min(), 0),
+ std::ios::oct, /*width = */ 0,
+ "2000000000000000000000000000000000000000000"});
+ CheckInt128Case({absl::MakeInt128(std::numeric_limits<int64_t>::min(), 0),
+ std::ios::hex, /*width = */ 0,
+ "80000000000000000000000000000000"});
+ CheckInt128Case({-1, std::ios::dec, /*width = */ 0, "-1"});
+ CheckInt128Case({-1, std::ios::oct, /*width = */ 0,
+ "3777777777777777777777777777777777777777777"});
+ CheckInt128Case(
+ {-1, std::ios::hex, /*width = */ 0, "ffffffffffffffffffffffffffffffff"});
+ CheckInt128Case({-12345, std::ios::dec, /*width = */ 0, "-12345"});
+ CheckInt128Case({-12345, std::ios::oct, /*width = */ 0,
+ "3777777777777777777777777777777777777747707"});
+ CheckInt128Case({-12345, std::ios::hex, /*width = */ 0,
+ "ffffffffffffffffffffffffffffcfc7"});
+}
+
+std::vector<Int128TestCase> GetInt128FormatCases();
+TEST(Int128, OStreamFormatTest) {
+ for (const Int128TestCase& test_case : GetInt128FormatCases()) {
+ CheckInt128Case(test_case);
+ }
+}
+
+std::vector<Int128TestCase> GetInt128FormatCases() {
+ return {
+ {0, std::ios_base::fmtflags(), /*width = */ 0, "0"},
+ {0, std::ios_base::fmtflags(), /*width = */ 6, "_____0"},
+ {0, kPos, /*width = */ 0, "+0"},
+ {0, kPos, /*width = */ 6, "____+0"},
+ {0, kBase, /*width = */ 0, "0"},
+ {0, kBase, /*width = */ 6, "_____0"},
+ {0, kBase | kPos, /*width = */ 0, "+0"},
+ {0, kBase | kPos, /*width = */ 6, "____+0"},
+ {0, kUpper, /*width = */ 0, "0"},
+ {0, kUpper, /*width = */ 6, "_____0"},
+ {0, kUpper | kPos, /*width = */ 0, "+0"},
+ {0, kUpper | kPos, /*width = */ 6, "____+0"},
+ {0, kUpper | kBase, /*width = */ 0, "0"},
+ {0, kUpper | kBase, /*width = */ 6, "_____0"},
+ {0, kUpper | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kUpper | kBase | kPos, /*width = */ 6, "____+0"},
+ {0, kLeft, /*width = */ 0, "0"},
+ {0, kLeft, /*width = */ 6, "0_____"},
+ {0, kLeft | kPos, /*width = */ 0, "+0"},
+ {0, kLeft | kPos, /*width = */ 6, "+0____"},
+ {0, kLeft | kBase, /*width = */ 0, "0"},
+ {0, kLeft | kBase, /*width = */ 6, "0_____"},
+ {0, kLeft | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kLeft | kBase | kPos, /*width = */ 6, "+0____"},
+ {0, kLeft | kUpper, /*width = */ 0, "0"},
+ {0, kLeft | kUpper, /*width = */ 6, "0_____"},
+ {0, kLeft | kUpper | kPos, /*width = */ 0, "+0"},
+ {0, kLeft | kUpper | kPos, /*width = */ 6, "+0____"},
+ {0, kLeft | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kLeft | kUpper | kBase, /*width = */ 6, "0_____"},
+ {0, kLeft | kUpper | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kLeft | kUpper | kBase | kPos, /*width = */ 6, "+0____"},
+ {0, kInt, /*width = */ 0, "0"},
+ {0, kInt, /*width = */ 6, "_____0"},
+ {0, kInt | kPos, /*width = */ 0, "+0"},
+ {0, kInt | kPos, /*width = */ 6, "+____0"},
+ {0, kInt | kBase, /*width = */ 0, "0"},
+ {0, kInt | kBase, /*width = */ 6, "_____0"},
+ {0, kInt | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kInt | kBase | kPos, /*width = */ 6, "+____0"},
+ {0, kInt | kUpper, /*width = */ 0, "0"},
+ {0, kInt | kUpper, /*width = */ 6, "_____0"},
+ {0, kInt | kUpper | kPos, /*width = */ 0, "+0"},
+ {0, kInt | kUpper | kPos, /*width = */ 6, "+____0"},
+ {0, kInt | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kInt | kUpper | kBase, /*width = */ 6, "_____0"},
+ {0, kInt | kUpper | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kInt | kUpper | kBase | kPos, /*width = */ 6, "+____0"},
+ {0, kRight, /*width = */ 0, "0"},
+ {0, kRight, /*width = */ 6, "_____0"},
+ {0, kRight | kPos, /*width = */ 0, "+0"},
+ {0, kRight | kPos, /*width = */ 6, "____+0"},
+ {0, kRight | kBase, /*width = */ 0, "0"},
+ {0, kRight | kBase, /*width = */ 6, "_____0"},
+ {0, kRight | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kRight | kBase | kPos, /*width = */ 6, "____+0"},
+ {0, kRight | kUpper, /*width = */ 0, "0"},
+ {0, kRight | kUpper, /*width = */ 6, "_____0"},
+ {0, kRight | kUpper | kPos, /*width = */ 0, "+0"},
+ {0, kRight | kUpper | kPos, /*width = */ 6, "____+0"},
+ {0, kRight | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kRight | kUpper | kBase, /*width = */ 6, "_____0"},
+ {0, kRight | kUpper | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kRight | kUpper | kBase | kPos, /*width = */ 6, "____+0"},
+ {0, kDec, /*width = */ 0, "0"},
+ {0, kDec, /*width = */ 6, "_____0"},
+ {0, kDec | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kPos, /*width = */ 6, "____+0"},
+ {0, kDec | kBase, /*width = */ 0, "0"},
+ {0, kDec | kBase, /*width = */ 6, "_____0"},
+ {0, kDec | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kBase | kPos, /*width = */ 6, "____+0"},
+ {0, kDec | kUpper, /*width = */ 0, "0"},
+ {0, kDec | kUpper, /*width = */ 6, "_____0"},
+ {0, kDec | kUpper | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kUpper | kPos, /*width = */ 6, "____+0"},
+ {0, kDec | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kDec | kUpper | kBase, /*width = */ 6, "_____0"},
+ {0, kDec | kUpper | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kUpper | kBase | kPos, /*width = */ 6, "____+0"},
+ {0, kDec | kLeft, /*width = */ 0, "0"},
+ {0, kDec | kLeft, /*width = */ 6, "0_____"},
+ {0, kDec | kLeft | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kLeft | kPos, /*width = */ 6, "+0____"},
+ {0, kDec | kLeft | kBase, /*width = */ 0, "0"},
+ {0, kDec | kLeft | kBase, /*width = */ 6, "0_____"},
+ {0, kDec | kLeft | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kLeft | kBase | kPos, /*width = */ 6, "+0____"},
+ {0, kDec | kLeft | kUpper, /*width = */ 0, "0"},
+ {0, kDec | kLeft | kUpper, /*width = */ 6, "0_____"},
+ {0, kDec | kLeft | kUpper | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kLeft | kUpper | kPos, /*width = */ 6, "+0____"},
+ {0, kDec | kLeft | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kDec | kLeft | kUpper | kBase, /*width = */ 6, "0_____"},
+ {0, kDec | kLeft | kUpper | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kLeft | kUpper | kBase | kPos, /*width = */ 6, "+0____"},
+ {0, kDec | kInt, /*width = */ 0, "0"},
+ {0, kDec | kInt, /*width = */ 6, "_____0"},
+ {0, kDec | kInt | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kInt | kPos, /*width = */ 6, "+____0"},
+ {0, kDec | kInt | kBase, /*width = */ 0, "0"},
+ {0, kDec | kInt | kBase, /*width = */ 6, "_____0"},
+ {0, kDec | kInt | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kInt | kBase | kPos, /*width = */ 6, "+____0"},
+ {0, kDec | kInt | kUpper, /*width = */ 0, "0"},
+ {0, kDec | kInt | kUpper, /*width = */ 6, "_____0"},
+ {0, kDec | kInt | kUpper | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kInt | kUpper | kPos, /*width = */ 6, "+____0"},
+ {0, kDec | kInt | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kDec | kInt | kUpper | kBase, /*width = */ 6, "_____0"},
+ {0, kDec | kInt | kUpper | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kInt | kUpper | kBase | kPos, /*width = */ 6, "+____0"},
+ {0, kDec | kRight, /*width = */ 0, "0"},
+ {0, kDec | kRight, /*width = */ 6, "_____0"},
+ {0, kDec | kRight | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kRight | kPos, /*width = */ 6, "____+0"},
+ {0, kDec | kRight | kBase, /*width = */ 0, "0"},
+ {0, kDec | kRight | kBase, /*width = */ 6, "_____0"},
+ {0, kDec | kRight | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kRight | kBase | kPos, /*width = */ 6, "____+0"},
+ {0, kDec | kRight | kUpper, /*width = */ 0, "0"},
+ {0, kDec | kRight | kUpper, /*width = */ 6, "_____0"},
+ {0, kDec | kRight | kUpper | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kRight | kUpper | kPos, /*width = */ 6, "____+0"},
+ {0, kDec | kRight | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kDec | kRight | kUpper | kBase, /*width = */ 6, "_____0"},
+ {0, kDec | kRight | kUpper | kBase | kPos, /*width = */ 0, "+0"},
+ {0, kDec | kRight | kUpper | kBase | kPos, /*width = */ 6, "____+0"},
+ {0, kOct, /*width = */ 0, "0"},
+ {0, kOct, /*width = */ 6, "_____0"},
+ {0, kOct | kPos, /*width = */ 0, "0"},
+ {0, kOct | kPos, /*width = */ 6, "_____0"},
+ {0, kOct | kBase, /*width = */ 0, "0"},
+ {0, kOct | kBase, /*width = */ 6, "_____0"},
+ {0, kOct | kBase | kPos, /*width = */ 0, "0"},
+ {0, kOct | kBase | kPos, /*width = */ 6, "_____0"},
+ {0, kOct | kUpper, /*width = */ 0, "0"},
+ {0, kOct | kUpper, /*width = */ 6, "_____0"},
+ {0, kOct | kUpper | kPos, /*width = */ 0, "0"},
+ {0, kOct | kUpper | kPos, /*width = */ 6, "_____0"},
+ {0, kOct | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kOct | kUpper | kBase, /*width = */ 6, "_____0"},
+ {0, kOct | kUpper | kBase | kPos, /*width = */ 0, "0"},
+ {0, kOct | kUpper | kBase | kPos, /*width = */ 6, "_____0"},
+ {0, kOct | kLeft, /*width = */ 0, "0"},
+ {0, kOct | kLeft, /*width = */ 6, "0_____"},
+ {0, kOct | kLeft | kPos, /*width = */ 0, "0"},
+ {0, kOct | kLeft | kPos, /*width = */ 6, "0_____"},
+ {0, kOct | kLeft | kBase, /*width = */ 0, "0"},
+ {0, kOct | kLeft | kBase, /*width = */ 6, "0_____"},
+ {0, kOct | kLeft | kBase | kPos, /*width = */ 0, "0"},
+ {0, kOct | kLeft | kBase | kPos, /*width = */ 6, "0_____"},
+ {0, kOct | kLeft | kUpper, /*width = */ 0, "0"},
+ {0, kOct | kLeft | kUpper, /*width = */ 6, "0_____"},
+ {0, kOct | kLeft | kUpper | kPos, /*width = */ 0, "0"},
+ {0, kOct | kLeft | kUpper | kPos, /*width = */ 6, "0_____"},
+ {0, kOct | kLeft | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kOct | kLeft | kUpper | kBase, /*width = */ 6, "0_____"},
+ {0, kOct | kLeft | kUpper | kBase | kPos, /*width = */ 0, "0"},
+ {0, kOct | kLeft | kUpper | kBase | kPos, /*width = */ 6, "0_____"},
+ {0, kOct | kInt, /*width = */ 0, "0"},
+ {0, kOct | kInt, /*width = */ 6, "_____0"},
+ {0, kOct | kInt | kPos, /*width = */ 0, "0"},
+ {0, kOct | kInt | kPos, /*width = */ 6, "_____0"},
+ {0, kOct | kInt | kBase, /*width = */ 0, "0"},
+ {0, kOct | kInt | kBase, /*width = */ 6, "_____0"},
+ {0, kOct | kInt | kBase | kPos, /*width = */ 0, "0"},
+ {0, kOct | kInt | kBase | kPos, /*width = */ 6, "_____0"},
+ {0, kOct | kInt | kUpper, /*width = */ 0, "0"},
+ {0, kOct | kInt | kUpper, /*width = */ 6, "_____0"},
+ {0, kOct | kInt | kUpper | kPos, /*width = */ 0, "0"},
+ {0, kOct | kInt | kUpper | kPos, /*width = */ 6, "_____0"},
+ {0, kOct | kInt | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kOct | kInt | kUpper | kBase, /*width = */ 6, "_____0"},
+ {0, kOct | kInt | kUpper | kBase | kPos, /*width = */ 0, "0"},
+ {0, kOct | kInt | kUpper | kBase | kPos, /*width = */ 6, "_____0"},
+ {0, kOct | kRight, /*width = */ 0, "0"},
+ {0, kOct | kRight, /*width = */ 6, "_____0"},
+ {0, kOct | kRight | kPos, /*width = */ 0, "0"},
+ {0, kOct | kRight | kPos, /*width = */ 6, "_____0"},
+ {0, kOct | kRight | kBase, /*width = */ 0, "0"},
+ {0, kOct | kRight | kBase, /*width = */ 6, "_____0"},
+ {0, kOct | kRight | kBase | kPos, /*width = */ 0, "0"},
+ {0, kOct | kRight | kBase | kPos, /*width = */ 6, "_____0"},
+ {0, kOct | kRight | kUpper, /*width = */ 0, "0"},
+ {0, kOct | kRight | kUpper, /*width = */ 6, "_____0"},
+ {0, kOct | kRight | kUpper | kPos, /*width = */ 0, "0"},
+ {0, kOct | kRight | kUpper | kPos, /*width = */ 6, "_____0"},
+ {0, kOct | kRight | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kOct | kRight | kUpper | kBase, /*width = */ 6, "_____0"},
+ {0, kOct | kRight | kUpper | kBase | kPos, /*width = */ 0, "0"},
+ {0, kOct | kRight | kUpper | kBase | kPos, /*width = */ 6, "_____0"},
+ {0, kHex, /*width = */ 0, "0"},
+ {0, kHex, /*width = */ 6, "_____0"},
+ {0, kHex | kPos, /*width = */ 0, "0"},
+ {0, kHex | kPos, /*width = */ 6, "_____0"},
+ {0, kHex | kBase, /*width = */ 0, "0"},
+ {0, kHex | kBase, /*width = */ 6, "_____0"},
+ {0, kHex | kBase | kPos, /*width = */ 0, "0"},
+ {0, kHex | kBase | kPos, /*width = */ 6, "_____0"},
+ {0, kHex | kUpper, /*width = */ 0, "0"},
+ {0, kHex | kUpper, /*width = */ 6, "_____0"},
+ {0, kHex | kUpper | kPos, /*width = */ 0, "0"},
+ {0, kHex | kUpper | kPos, /*width = */ 6, "_____0"},
+ {0, kHex | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kHex | kUpper | kBase, /*width = */ 6, "_____0"},
+ {0, kHex | kUpper | kBase | kPos, /*width = */ 0, "0"},
+ {0, kHex | kUpper | kBase | kPos, /*width = */ 6, "_____0"},
+ {0, kHex | kLeft, /*width = */ 0, "0"},
+ {0, kHex | kLeft, /*width = */ 6, "0_____"},
+ {0, kHex | kLeft | kPos, /*width = */ 0, "0"},
+ {0, kHex | kLeft | kPos, /*width = */ 6, "0_____"},
+ {0, kHex | kLeft | kBase, /*width = */ 0, "0"},
+ {0, kHex | kLeft | kBase, /*width = */ 6, "0_____"},
+ {0, kHex | kLeft | kBase | kPos, /*width = */ 0, "0"},
+ {0, kHex | kLeft | kBase | kPos, /*width = */ 6, "0_____"},
+ {0, kHex | kLeft | kUpper, /*width = */ 0, "0"},
+ {0, kHex | kLeft | kUpper, /*width = */ 6, "0_____"},
+ {0, kHex | kLeft | kUpper | kPos, /*width = */ 0, "0"},
+ {0, kHex | kLeft | kUpper | kPos, /*width = */ 6, "0_____"},
+ {0, kHex | kLeft | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kHex | kLeft | kUpper | kBase, /*width = */ 6, "0_____"},
+ {0, kHex | kLeft | kUpper | kBase | kPos, /*width = */ 0, "0"},
+ {0, kHex | kLeft | kUpper | kBase | kPos, /*width = */ 6, "0_____"},
+ {0, kHex | kInt, /*width = */ 0, "0"},
+ {0, kHex | kInt, /*width = */ 6, "_____0"},
+ {0, kHex | kInt | kPos, /*width = */ 0, "0"},
+ {0, kHex | kInt | kPos, /*width = */ 6, "_____0"},
+ {0, kHex | kInt | kBase, /*width = */ 0, "0"},
+ {0, kHex | kInt | kBase, /*width = */ 6, "_____0"},
+ {0, kHex | kInt | kBase | kPos, /*width = */ 0, "0"},
+ {0, kHex | kInt | kBase | kPos, /*width = */ 6, "_____0"},
+ {0, kHex | kInt | kUpper, /*width = */ 0, "0"},
+ {0, kHex | kInt | kUpper, /*width = */ 6, "_____0"},
+ {0, kHex | kInt | kUpper | kPos, /*width = */ 0, "0"},
+ {0, kHex | kInt | kUpper | kPos, /*width = */ 6, "_____0"},
+ {0, kHex | kInt | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kHex | kInt | kUpper | kBase, /*width = */ 6, "_____0"},
+ {0, kHex | kInt | kUpper | kBase | kPos, /*width = */ 0, "0"},
+ {0, kHex | kInt | kUpper | kBase | kPos, /*width = */ 6, "_____0"},
+ {0, kHex | kRight, /*width = */ 0, "0"},
+ {0, kHex | kRight, /*width = */ 6, "_____0"},
+ {0, kHex | kRight | kPos, /*width = */ 0, "0"},
+ {0, kHex | kRight | kPos, /*width = */ 6, "_____0"},
+ {0, kHex | kRight | kBase, /*width = */ 0, "0"},
+ {0, kHex | kRight | kBase, /*width = */ 6, "_____0"},
+ {0, kHex | kRight | kBase | kPos, /*width = */ 0, "0"},
+ {0, kHex | kRight | kBase | kPos, /*width = */ 6, "_____0"},
+ {0, kHex | kRight | kUpper, /*width = */ 0, "0"},
+ {0, kHex | kRight | kUpper, /*width = */ 6, "_____0"},
+ {0, kHex | kRight | kUpper | kPos, /*width = */ 0, "0"},
+ {0, kHex | kRight | kUpper | kPos, /*width = */ 6, "_____0"},
+ {0, kHex | kRight | kUpper | kBase, /*width = */ 0, "0"},
+ {0, kHex | kRight | kUpper | kBase, /*width = */ 6, "_____0"},
+ {0, kHex | kRight | kUpper | kBase | kPos, /*width = */ 0, "0"},
+ {0, kHex | kRight | kUpper | kBase | kPos, /*width = */ 6, "_____0"},
+ {42, std::ios_base::fmtflags(), /*width = */ 0, "42"},
+ {42, std::ios_base::fmtflags(), /*width = */ 6, "____42"},
+ {42, kPos, /*width = */ 0, "+42"},
+ {42, kPos, /*width = */ 6, "___+42"},
+ {42, kBase, /*width = */ 0, "42"},
+ {42, kBase, /*width = */ 6, "____42"},
+ {42, kBase | kPos, /*width = */ 0, "+42"},
+ {42, kBase | kPos, /*width = */ 6, "___+42"},
+ {42, kUpper, /*width = */ 0, "42"},
+ {42, kUpper, /*width = */ 6, "____42"},
+ {42, kUpper | kPos, /*width = */ 0, "+42"},
+ {42, kUpper | kPos, /*width = */ 6, "___+42"},
+ {42, kUpper | kBase, /*width = */ 0, "42"},
+ {42, kUpper | kBase, /*width = */ 6, "____42"},
+ {42, kUpper | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kUpper | kBase | kPos, /*width = */ 6, "___+42"},
+ {42, kLeft, /*width = */ 0, "42"},
+ {42, kLeft, /*width = */ 6, "42____"},
+ {42, kLeft | kPos, /*width = */ 0, "+42"},
+ {42, kLeft | kPos, /*width = */ 6, "+42___"},
+ {42, kLeft | kBase, /*width = */ 0, "42"},
+ {42, kLeft | kBase, /*width = */ 6, "42____"},
+ {42, kLeft | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kLeft | kBase | kPos, /*width = */ 6, "+42___"},
+ {42, kLeft | kUpper, /*width = */ 0, "42"},
+ {42, kLeft | kUpper, /*width = */ 6, "42____"},
+ {42, kLeft | kUpper | kPos, /*width = */ 0, "+42"},
+ {42, kLeft | kUpper | kPos, /*width = */ 6, "+42___"},
+ {42, kLeft | kUpper | kBase, /*width = */ 0, "42"},
+ {42, kLeft | kUpper | kBase, /*width = */ 6, "42____"},
+ {42, kLeft | kUpper | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kLeft | kUpper | kBase | kPos, /*width = */ 6, "+42___"},
+ {42, kInt, /*width = */ 0, "42"},
+ {42, kInt, /*width = */ 6, "____42"},
+ {42, kInt | kPos, /*width = */ 0, "+42"},
+ {42, kInt | kPos, /*width = */ 6, "+___42"},
+ {42, kInt | kBase, /*width = */ 0, "42"},
+ {42, kInt | kBase, /*width = */ 6, "____42"},
+ {42, kInt | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kInt | kBase | kPos, /*width = */ 6, "+___42"},
+ {42, kInt | kUpper, /*width = */ 0, "42"},
+ {42, kInt | kUpper, /*width = */ 6, "____42"},
+ {42, kInt | kUpper | kPos, /*width = */ 0, "+42"},
+ {42, kInt | kUpper | kPos, /*width = */ 6, "+___42"},
+ {42, kInt | kUpper | kBase, /*width = */ 0, "42"},
+ {42, kInt | kUpper | kBase, /*width = */ 6, "____42"},
+ {42, kInt | kUpper | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kInt | kUpper | kBase | kPos, /*width = */ 6, "+___42"},
+ {42, kRight, /*width = */ 0, "42"},
+ {42, kRight, /*width = */ 6, "____42"},
+ {42, kRight | kPos, /*width = */ 0, "+42"},
+ {42, kRight | kPos, /*width = */ 6, "___+42"},
+ {42, kRight | kBase, /*width = */ 0, "42"},
+ {42, kRight | kBase, /*width = */ 6, "____42"},
+ {42, kRight | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kRight | kBase | kPos, /*width = */ 6, "___+42"},
+ {42, kRight | kUpper, /*width = */ 0, "42"},
+ {42, kRight | kUpper, /*width = */ 6, "____42"},
+ {42, kRight | kUpper | kPos, /*width = */ 0, "+42"},
+ {42, kRight | kUpper | kPos, /*width = */ 6, "___+42"},
+ {42, kRight | kUpper | kBase, /*width = */ 0, "42"},
+ {42, kRight | kUpper | kBase, /*width = */ 6, "____42"},
+ {42, kRight | kUpper | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kRight | kUpper | kBase | kPos, /*width = */ 6, "___+42"},
+ {42, kDec, /*width = */ 0, "42"},
+ {42, kDec, /*width = */ 6, "____42"},
+ {42, kDec | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kPos, /*width = */ 6, "___+42"},
+ {42, kDec | kBase, /*width = */ 0, "42"},
+ {42, kDec | kBase, /*width = */ 6, "____42"},
+ {42, kDec | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kBase | kPos, /*width = */ 6, "___+42"},
+ {42, kDec | kUpper, /*width = */ 0, "42"},
+ {42, kDec | kUpper, /*width = */ 6, "____42"},
+ {42, kDec | kUpper | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kUpper | kPos, /*width = */ 6, "___+42"},
+ {42, kDec | kUpper | kBase, /*width = */ 0, "42"},
+ {42, kDec | kUpper | kBase, /*width = */ 6, "____42"},
+ {42, kDec | kUpper | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kUpper | kBase | kPos, /*width = */ 6, "___+42"},
+ {42, kDec | kLeft, /*width = */ 0, "42"},
+ {42, kDec | kLeft, /*width = */ 6, "42____"},
+ {42, kDec | kLeft | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kLeft | kPos, /*width = */ 6, "+42___"},
+ {42, kDec | kLeft | kBase, /*width = */ 0, "42"},
+ {42, kDec | kLeft | kBase, /*width = */ 6, "42____"},
+ {42, kDec | kLeft | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kLeft | kBase | kPos, /*width = */ 6, "+42___"},
+ {42, kDec | kLeft | kUpper, /*width = */ 0, "42"},
+ {42, kDec | kLeft | kUpper, /*width = */ 6, "42____"},
+ {42, kDec | kLeft | kUpper | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kLeft | kUpper | kPos, /*width = */ 6, "+42___"},
+ {42, kDec | kLeft | kUpper | kBase, /*width = */ 0, "42"},
+ {42, kDec | kLeft | kUpper | kBase, /*width = */ 6, "42____"},
+ {42, kDec | kLeft | kUpper | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kLeft | kUpper | kBase | kPos, /*width = */ 6, "+42___"},
+ {42, kDec | kInt, /*width = */ 0, "42"},
+ {42, kDec | kInt, /*width = */ 6, "____42"},
+ {42, kDec | kInt | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kInt | kPos, /*width = */ 6, "+___42"},
+ {42, kDec | kInt | kBase, /*width = */ 0, "42"},
+ {42, kDec | kInt | kBase, /*width = */ 6, "____42"},
+ {42, kDec | kInt | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kInt | kBase | kPos, /*width = */ 6, "+___42"},
+ {42, kDec | kInt | kUpper, /*width = */ 0, "42"},
+ {42, kDec | kInt | kUpper, /*width = */ 6, "____42"},
+ {42, kDec | kInt | kUpper | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kInt | kUpper | kPos, /*width = */ 6, "+___42"},
+ {42, kDec | kInt | kUpper | kBase, /*width = */ 0, "42"},
+ {42, kDec | kInt | kUpper | kBase, /*width = */ 6, "____42"},
+ {42, kDec | kInt | kUpper | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kInt | kUpper | kBase | kPos, /*width = */ 6, "+___42"},
+ {42, kDec | kRight, /*width = */ 0, "42"},
+ {42, kDec | kRight, /*width = */ 6, "____42"},
+ {42, kDec | kRight | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kRight | kPos, /*width = */ 6, "___+42"},
+ {42, kDec | kRight | kBase, /*width = */ 0, "42"},
+ {42, kDec | kRight | kBase, /*width = */ 6, "____42"},
+ {42, kDec | kRight | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kRight | kBase | kPos, /*width = */ 6, "___+42"},
+ {42, kDec | kRight | kUpper, /*width = */ 0, "42"},
+ {42, kDec | kRight | kUpper, /*width = */ 6, "____42"},
+ {42, kDec | kRight | kUpper | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kRight | kUpper | kPos, /*width = */ 6, "___+42"},
+ {42, kDec | kRight | kUpper | kBase, /*width = */ 0, "42"},
+ {42, kDec | kRight | kUpper | kBase, /*width = */ 6, "____42"},
+ {42, kDec | kRight | kUpper | kBase | kPos, /*width = */ 0, "+42"},
+ {42, kDec | kRight | kUpper | kBase | kPos, /*width = */ 6, "___+42"},
+ {42, kOct, /*width = */ 0, "52"},
+ {42, kOct, /*width = */ 6, "____52"},
+ {42, kOct | kPos, /*width = */ 0, "52"},
+ {42, kOct | kPos, /*width = */ 6, "____52"},
+ {42, kOct | kBase, /*width = */ 0, "052"},
+ {42, kOct | kBase, /*width = */ 6, "___052"},
+ {42, kOct | kBase | kPos, /*width = */ 0, "052"},
+ {42, kOct | kBase | kPos, /*width = */ 6, "___052"},
+ {42, kOct | kUpper, /*width = */ 0, "52"},
+ {42, kOct | kUpper, /*width = */ 6, "____52"},
+ {42, kOct | kUpper | kPos, /*width = */ 0, "52"},
+ {42, kOct | kUpper | kPos, /*width = */ 6, "____52"},
+ {42, kOct | kUpper | kBase, /*width = */ 0, "052"},
+ {42, kOct | kUpper | kBase, /*width = */ 6, "___052"},
+ {42, kOct | kUpper | kBase | kPos, /*width = */ 0, "052"},
+ {42, kOct | kUpper | kBase | kPos, /*width = */ 6, "___052"},
+ {42, kOct | kLeft, /*width = */ 0, "52"},
+ {42, kOct | kLeft, /*width = */ 6, "52____"},
+ {42, kOct | kLeft | kPos, /*width = */ 0, "52"},
+ {42, kOct | kLeft | kPos, /*width = */ 6, "52____"},
+ {42, kOct | kLeft | kBase, /*width = */ 0, "052"},
+ {42, kOct | kLeft | kBase, /*width = */ 6, "052___"},
+ {42, kOct | kLeft | kBase | kPos, /*width = */ 0, "052"},
+ {42, kOct | kLeft | kBase | kPos, /*width = */ 6, "052___"},
+ {42, kOct | kLeft | kUpper, /*width = */ 0, "52"},
+ {42, kOct | kLeft | kUpper, /*width = */ 6, "52____"},
+ {42, kOct | kLeft | kUpper | kPos, /*width = */ 0, "52"},
+ {42, kOct | kLeft | kUpper | kPos, /*width = */ 6, "52____"},
+ {42, kOct | kLeft | kUpper | kBase, /*width = */ 0, "052"},
+ {42, kOct | kLeft | kUpper | kBase, /*width = */ 6, "052___"},
+ {42, kOct | kLeft | kUpper | kBase | kPos, /*width = */ 0, "052"},
+ {42, kOct | kLeft | kUpper | kBase | kPos, /*width = */ 6, "052___"},
+ {42, kOct | kInt, /*width = */ 0, "52"},
+ {42, kOct | kInt, /*width = */ 6, "____52"},
+ {42, kOct | kInt | kPos, /*width = */ 0, "52"},
+ {42, kOct | kInt | kPos, /*width = */ 6, "____52"},
+ {42, kOct | kInt | kBase, /*width = */ 0, "052"},
+ {42, kOct | kInt | kBase, /*width = */ 6, "___052"},
+ {42, kOct | kInt | kBase | kPos, /*width = */ 0, "052"},
+ {42, kOct | kInt | kBase | kPos, /*width = */ 6, "___052"},
+ {42, kOct | kInt | kUpper, /*width = */ 0, "52"},
+ {42, kOct | kInt | kUpper, /*width = */ 6, "____52"},
+ {42, kOct | kInt | kUpper | kPos, /*width = */ 0, "52"},
+ {42, kOct | kInt | kUpper | kPos, /*width = */ 6, "____52"},
+ {42, kOct | kInt | kUpper | kBase, /*width = */ 0, "052"},
+ {42, kOct | kInt | kUpper | kBase, /*width = */ 6, "___052"},
+ {42, kOct | kInt | kUpper | kBase | kPos, /*width = */ 0, "052"},
+ {42, kOct | kInt | kUpper | kBase | kPos, /*width = */ 6, "___052"},
+ {42, kOct | kRight, /*width = */ 0, "52"},
+ {42, kOct | kRight, /*width = */ 6, "____52"},
+ {42, kOct | kRight | kPos, /*width = */ 0, "52"},
+ {42, kOct | kRight | kPos, /*width = */ 6, "____52"},
+ {42, kOct | kRight | kBase, /*width = */ 0, "052"},
+ {42, kOct | kRight | kBase, /*width = */ 6, "___052"},
+ {42, kOct | kRight | kBase | kPos, /*width = */ 0, "052"},
+ {42, kOct | kRight | kBase | kPos, /*width = */ 6, "___052"},
+ {42, kOct | kRight | kUpper, /*width = */ 0, "52"},
+ {42, kOct | kRight | kUpper, /*width = */ 6, "____52"},
+ {42, kOct | kRight | kUpper | kPos, /*width = */ 0, "52"},
+ {42, kOct | kRight | kUpper | kPos, /*width = */ 6, "____52"},
+ {42, kOct | kRight | kUpper | kBase, /*width = */ 0, "052"},
+ {42, kOct | kRight | kUpper | kBase, /*width = */ 6, "___052"},
+ {42, kOct | kRight | kUpper | kBase | kPos, /*width = */ 0, "052"},
+ {42, kOct | kRight | kUpper | kBase | kPos, /*width = */ 6, "___052"},
+ {42, kHex, /*width = */ 0, "2a"},
+ {42, kHex, /*width = */ 6, "____2a"},
+ {42, kHex | kPos, /*width = */ 0, "2a"},
+ {42, kHex | kPos, /*width = */ 6, "____2a"},
+ {42, kHex | kBase, /*width = */ 0, "0x2a"},
+ {42, kHex | kBase, /*width = */ 6, "__0x2a"},
+ {42, kHex | kBase | kPos, /*width = */ 0, "0x2a"},
+ {42, kHex | kBase | kPos, /*width = */ 6, "__0x2a"},
+ {42, kHex | kUpper, /*width = */ 0, "2A"},
+ {42, kHex | kUpper, /*width = */ 6, "____2A"},
+ {42, kHex | kUpper | kPos, /*width = */ 0, "2A"},
+ {42, kHex | kUpper | kPos, /*width = */ 6, "____2A"},
+ {42, kHex | kUpper | kBase, /*width = */ 0, "0X2A"},
+ {42, kHex | kUpper | kBase, /*width = */ 6, "__0X2A"},
+ {42, kHex | kUpper | kBase | kPos, /*width = */ 0, "0X2A"},
+ {42, kHex | kUpper | kBase | kPos, /*width = */ 6, "__0X2A"},
+ {42, kHex | kLeft, /*width = */ 0, "2a"},
+ {42, kHex | kLeft, /*width = */ 6, "2a____"},
+ {42, kHex | kLeft | kPos, /*width = */ 0, "2a"},
+ {42, kHex | kLeft | kPos, /*width = */ 6, "2a____"},
+ {42, kHex | kLeft | kBase, /*width = */ 0, "0x2a"},
+ {42, kHex | kLeft | kBase, /*width = */ 6, "0x2a__"},
+ {42, kHex | kLeft | kBase | kPos, /*width = */ 0, "0x2a"},
+ {42, kHex | kLeft | kBase | kPos, /*width = */ 6, "0x2a__"},
+ {42, kHex | kLeft | kUpper, /*width = */ 0, "2A"},
+ {42, kHex | kLeft | kUpper, /*width = */ 6, "2A____"},
+ {42, kHex | kLeft | kUpper | kPos, /*width = */ 0, "2A"},
+ {42, kHex | kLeft | kUpper | kPos, /*width = */ 6, "2A____"},
+ {42, kHex | kLeft | kUpper | kBase, /*width = */ 0, "0X2A"},
+ {42, kHex | kLeft | kUpper | kBase, /*width = */ 6, "0X2A__"},
+ {42, kHex | kLeft | kUpper | kBase | kPos, /*width = */ 0, "0X2A"},
+ {42, kHex | kLeft | kUpper | kBase | kPos, /*width = */ 6, "0X2A__"},
+ {42, kHex | kInt, /*width = */ 0, "2a"},
+ {42, kHex | kInt, /*width = */ 6, "____2a"},
+ {42, kHex | kInt | kPos, /*width = */ 0, "2a"},
+ {42, kHex | kInt | kPos, /*width = */ 6, "____2a"},
+ {42, kHex | kInt | kBase, /*width = */ 0, "0x2a"},
+ {42, kHex | kInt | kBase, /*width = */ 6, "0x__2a"},
+ {42, kHex | kInt | kBase | kPos, /*width = */ 0, "0x2a"},
+ {42, kHex | kInt | kBase | kPos, /*width = */ 6, "0x__2a"},
+ {42, kHex | kInt | kUpper, /*width = */ 0, "2A"},
+ {42, kHex | kInt | kUpper, /*width = */ 6, "____2A"},
+ {42, kHex | kInt | kUpper | kPos, /*width = */ 0, "2A"},
+ {42, kHex | kInt | kUpper | kPos, /*width = */ 6, "____2A"},
+ {42, kHex | kInt | kUpper | kBase, /*width = */ 0, "0X2A"},
+ {42, kHex | kInt | kUpper | kBase, /*width = */ 6, "0X__2A"},
+ {42, kHex | kInt | kUpper | kBase | kPos, /*width = */ 0, "0X2A"},
+ {42, kHex | kInt | kUpper | kBase | kPos, /*width = */ 6, "0X__2A"},
+ {42, kHex | kRight, /*width = */ 0, "2a"},
+ {42, kHex | kRight, /*width = */ 6, "____2a"},
+ {42, kHex | kRight | kPos, /*width = */ 0, "2a"},
+ {42, kHex | kRight | kPos, /*width = */ 6, "____2a"},
+ {42, kHex | kRight | kBase, /*width = */ 0, "0x2a"},
+ {42, kHex | kRight | kBase, /*width = */ 6, "__0x2a"},
+ {42, kHex | kRight | kBase | kPos, /*width = */ 0, "0x2a"},
+ {42, kHex | kRight | kBase | kPos, /*width = */ 6, "__0x2a"},
+ {42, kHex | kRight | kUpper, /*width = */ 0, "2A"},
+ {42, kHex | kRight | kUpper, /*width = */ 6, "____2A"},
+ {42, kHex | kRight | kUpper | kPos, /*width = */ 0, "2A"},
+ {42, kHex | kRight | kUpper | kPos, /*width = */ 6, "____2A"},
+ {42, kHex | kRight | kUpper | kBase, /*width = */ 0, "0X2A"},
+ {42, kHex | kRight | kUpper | kBase, /*width = */ 6, "__0X2A"},
+ {42, kHex | kRight | kUpper | kBase | kPos, /*width = */ 0, "0X2A"},
+ {42, kHex | kRight | kUpper | kBase | kPos, /*width = */ 6, "__0X2A"},
+ {-321, std::ios_base::fmtflags(), /*width = */ 0, "-321"},
+ {-321, std::ios_base::fmtflags(), /*width = */ 6, "__-321"},
+ {-321, kPos, /*width = */ 0, "-321"},
+ {-321, kPos, /*width = */ 6, "__-321"},
+ {-321, kBase, /*width = */ 0, "-321"},
+ {-321, kBase, /*width = */ 6, "__-321"},
+ {-321, kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kBase | kPos, /*width = */ 6, "__-321"},
+ {-321, kUpper, /*width = */ 0, "-321"},
+ {-321, kUpper, /*width = */ 6, "__-321"},
+ {-321, kUpper | kPos, /*width = */ 0, "-321"},
+ {-321, kUpper | kPos, /*width = */ 6, "__-321"},
+ {-321, kUpper | kBase, /*width = */ 0, "-321"},
+ {-321, kUpper | kBase, /*width = */ 6, "__-321"},
+ {-321, kUpper | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kUpper | kBase | kPos, /*width = */ 6, "__-321"},
+ {-321, kLeft, /*width = */ 0, "-321"},
+ {-321, kLeft, /*width = */ 6, "-321__"},
+ {-321, kLeft | kPos, /*width = */ 0, "-321"},
+ {-321, kLeft | kPos, /*width = */ 6, "-321__"},
+ {-321, kLeft | kBase, /*width = */ 0, "-321"},
+ {-321, kLeft | kBase, /*width = */ 6, "-321__"},
+ {-321, kLeft | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kLeft | kBase | kPos, /*width = */ 6, "-321__"},
+ {-321, kLeft | kUpper, /*width = */ 0, "-321"},
+ {-321, kLeft | kUpper, /*width = */ 6, "-321__"},
+ {-321, kLeft | kUpper | kPos, /*width = */ 0, "-321"},
+ {-321, kLeft | kUpper | kPos, /*width = */ 6, "-321__"},
+ {-321, kLeft | kUpper | kBase, /*width = */ 0, "-321"},
+ {-321, kLeft | kUpper | kBase, /*width = */ 6, "-321__"},
+ {-321, kLeft | kUpper | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kLeft | kUpper | kBase | kPos, /*width = */ 6, "-321__"},
+ {-321, kInt, /*width = */ 0, "-321"},
+ {-321, kInt, /*width = */ 6, "-__321"},
+ {-321, kInt | kPos, /*width = */ 0, "-321"},
+ {-321, kInt | kPos, /*width = */ 6, "-__321"},
+ {-321, kInt | kBase, /*width = */ 0, "-321"},
+ {-321, kInt | kBase, /*width = */ 6, "-__321"},
+ {-321, kInt | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kInt | kBase | kPos, /*width = */ 6, "-__321"},
+ {-321, kInt | kUpper, /*width = */ 0, "-321"},
+ {-321, kInt | kUpper, /*width = */ 6, "-__321"},
+ {-321, kInt | kUpper | kPos, /*width = */ 0, "-321"},
+ {-321, kInt | kUpper | kPos, /*width = */ 6, "-__321"},
+ {-321, kInt | kUpper | kBase, /*width = */ 0, "-321"},
+ {-321, kInt | kUpper | kBase, /*width = */ 6, "-__321"},
+ {-321, kInt | kUpper | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kInt | kUpper | kBase | kPos, /*width = */ 6, "-__321"},
+ {-321, kRight, /*width = */ 0, "-321"},
+ {-321, kRight, /*width = */ 6, "__-321"},
+ {-321, kRight | kPos, /*width = */ 0, "-321"},
+ {-321, kRight | kPos, /*width = */ 6, "__-321"},
+ {-321, kRight | kBase, /*width = */ 0, "-321"},
+ {-321, kRight | kBase, /*width = */ 6, "__-321"},
+ {-321, kRight | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kRight | kBase | kPos, /*width = */ 6, "__-321"},
+ {-321, kRight | kUpper, /*width = */ 0, "-321"},
+ {-321, kRight | kUpper, /*width = */ 6, "__-321"},
+ {-321, kRight | kUpper | kPos, /*width = */ 0, "-321"},
+ {-321, kRight | kUpper | kPos, /*width = */ 6, "__-321"},
+ {-321, kRight | kUpper | kBase, /*width = */ 0, "-321"},
+ {-321, kRight | kUpper | kBase, /*width = */ 6, "__-321"},
+ {-321, kRight | kUpper | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kRight | kUpper | kBase | kPos, /*width = */ 6, "__-321"},
+ {-321, kDec, /*width = */ 0, "-321"},
+ {-321, kDec, /*width = */ 6, "__-321"},
+ {-321, kDec | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kPos, /*width = */ 6, "__-321"},
+ {-321, kDec | kBase, /*width = */ 0, "-321"},
+ {-321, kDec | kBase, /*width = */ 6, "__-321"},
+ {-321, kDec | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kBase | kPos, /*width = */ 6, "__-321"},
+ {-321, kDec | kUpper, /*width = */ 0, "-321"},
+ {-321, kDec | kUpper, /*width = */ 6, "__-321"},
+ {-321, kDec | kUpper | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kUpper | kPos, /*width = */ 6, "__-321"},
+ {-321, kDec | kUpper | kBase, /*width = */ 0, "-321"},
+ {-321, kDec | kUpper | kBase, /*width = */ 6, "__-321"},
+ {-321, kDec | kUpper | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kUpper | kBase | kPos, /*width = */ 6, "__-321"},
+ {-321, kDec | kLeft, /*width = */ 0, "-321"},
+ {-321, kDec | kLeft, /*width = */ 6, "-321__"},
+ {-321, kDec | kLeft | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kLeft | kPos, /*width = */ 6, "-321__"},
+ {-321, kDec | kLeft | kBase, /*width = */ 0, "-321"},
+ {-321, kDec | kLeft | kBase, /*width = */ 6, "-321__"},
+ {-321, kDec | kLeft | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kLeft | kBase | kPos, /*width = */ 6, "-321__"},
+ {-321, kDec | kLeft | kUpper, /*width = */ 0, "-321"},
+ {-321, kDec | kLeft | kUpper, /*width = */ 6, "-321__"},
+ {-321, kDec | kLeft | kUpper | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kLeft | kUpper | kPos, /*width = */ 6, "-321__"},
+ {-321, kDec | kLeft | kUpper | kBase, /*width = */ 0, "-321"},
+ {-321, kDec | kLeft | kUpper | kBase, /*width = */ 6, "-321__"},
+ {-321, kDec | kLeft | kUpper | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kLeft | kUpper | kBase | kPos, /*width = */ 6, "-321__"},
+ {-321, kDec | kInt, /*width = */ 0, "-321"},
+ {-321, kDec | kInt, /*width = */ 6, "-__321"},
+ {-321, kDec | kInt | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kInt | kPos, /*width = */ 6, "-__321"},
+ {-321, kDec | kInt | kBase, /*width = */ 0, "-321"},
+ {-321, kDec | kInt | kBase, /*width = */ 6, "-__321"},
+ {-321, kDec | kInt | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kInt | kBase | kPos, /*width = */ 6, "-__321"},
+ {-321, kDec | kInt | kUpper, /*width = */ 0, "-321"},
+ {-321, kDec | kInt | kUpper, /*width = */ 6, "-__321"},
+ {-321, kDec | kInt | kUpper | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kInt | kUpper | kPos, /*width = */ 6, "-__321"},
+ {-321, kDec | kInt | kUpper | kBase, /*width = */ 0, "-321"},
+ {-321, kDec | kInt | kUpper | kBase, /*width = */ 6, "-__321"},
+ {-321, kDec | kInt | kUpper | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kInt | kUpper | kBase | kPos, /*width = */ 6, "-__321"},
+ {-321, kDec | kRight, /*width = */ 0, "-321"},
+ {-321, kDec | kRight, /*width = */ 6, "__-321"},
+ {-321, kDec | kRight | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kRight | kPos, /*width = */ 6, "__-321"},
+ {-321, kDec | kRight | kBase, /*width = */ 0, "-321"},
+ {-321, kDec | kRight | kBase, /*width = */ 6, "__-321"},
+ {-321, kDec | kRight | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kRight | kBase | kPos, /*width = */ 6, "__-321"},
+ {-321, kDec | kRight | kUpper, /*width = */ 0, "-321"},
+ {-321, kDec | kRight | kUpper, /*width = */ 6, "__-321"},
+ {-321, kDec | kRight | kUpper | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kRight | kUpper | kPos, /*width = */ 6, "__-321"},
+ {-321, kDec | kRight | kUpper | kBase, /*width = */ 0, "-321"},
+ {-321, kDec | kRight | kUpper | kBase, /*width = */ 6, "__-321"},
+ {-321, kDec | kRight | kUpper | kBase | kPos, /*width = */ 0, "-321"},
+ {-321, kDec | kRight | kUpper | kBase | kPos, /*width = */ 6, "__-321"}};
+}
+
std::vector<Uint128TestCase> GetUint128FormatCases() {
return {
{0, std::ios_base::fmtflags(), /*width = */ 0, "0"},
diff --git a/absl/numeric/int128_test.cc b/absl/numeric/int128_test.cc
index 5e1b5ec..bc86c71 100644
--- a/absl/numeric/int128_test.cc
+++ b/absl/numeric/int128_test.cc
@@ -479,4 +479,747 @@
}));
}
+
+TEST(Int128Uint128, ConversionTest) {
+ absl::int128 nonnegative_signed_values[] = {
+ 0,
+ 1,
+ 0xffeeddccbbaa9988,
+ absl::MakeInt128(0x7766554433221100, 0),
+ absl::MakeInt128(0x1234567890abcdef, 0xfedcba0987654321),
+ absl::Int128Max()};
+ for (absl::int128 value : nonnegative_signed_values) {
+ EXPECT_EQ(value, absl::int128(absl::uint128(value)));
+
+ absl::uint128 assigned_value;
+ assigned_value = value;
+ EXPECT_EQ(value, absl::int128(assigned_value));
+ }
+
+ absl::int128 negative_values[] = {
+ -1, -0x1234567890abcdef,
+ absl::MakeInt128(-0x5544332211ffeedd, 0),
+ -absl::MakeInt128(0x76543210fedcba98, 0xabcdef0123456789)};
+ for (absl::int128 value : negative_values) {
+ EXPECT_EQ(absl::uint128(-value), -absl::uint128(value));
+
+ absl::uint128 assigned_value;
+ assigned_value = value;
+ EXPECT_EQ(absl::uint128(-value), -assigned_value);
+ }
+}
+
+template <typename T>
+class Int128IntegerTraitsTest : public ::testing::Test {};
+
+TYPED_TEST_SUITE(Int128IntegerTraitsTest, IntegerTypes);
+
+TYPED_TEST(Int128IntegerTraitsTest, ConstructAssignTest) {
+ static_assert(std::is_constructible<absl::int128, TypeParam>::value,
+ "absl::int128 must be constructible from TypeParam");
+ static_assert(std::is_assignable<absl::int128&, TypeParam>::value,
+ "absl::int128 must be assignable from TypeParam");
+ static_assert(!std::is_assignable<TypeParam&, absl::int128>::value,
+ "TypeParam must not be assignable from absl::int128");
+}
+
+template <typename T>
+class Int128FloatTraitsTest : public ::testing::Test {};
+
+TYPED_TEST_SUITE(Int128FloatTraitsTest, FloatingPointTypes);
+
+TYPED_TEST(Int128FloatTraitsTest, ConstructAssignTest) {
+ static_assert(std::is_constructible<absl::int128, TypeParam>::value,
+ "absl::int128 must be constructible from TypeParam");
+ static_assert(!std::is_assignable<absl::int128&, TypeParam>::value,
+ "absl::int128 must not be assignable from TypeParam");
+ static_assert(!std::is_assignable<TypeParam&, absl::int128>::value,
+ "TypeParam must not be assignable from absl::int128");
+}
+
+#ifdef ABSL_HAVE_INTRINSIC_INT128
+// These type traits done separately as TYPED_TEST requires typeinfo, and not
+// all platforms have this for __int128 even though they define the type.
+TEST(Int128, IntrinsicTypeTraitsTest) {
+ static_assert(std::is_constructible<absl::int128, __int128>::value,
+ "absl::int128 must be constructible from __int128");
+ static_assert(std::is_assignable<absl::int128&, __int128>::value,
+ "absl::int128 must be assignable from __int128");
+ static_assert(!std::is_assignable<__int128&, absl::int128>::value,
+ "__int128 must not be assignable from absl::int128");
+
+ static_assert(std::is_constructible<absl::int128, unsigned __int128>::value,
+ "absl::int128 must be constructible from unsigned __int128");
+ static_assert(!std::is_assignable<absl::int128&, unsigned __int128>::value,
+ "absl::int128 must be assignable from unsigned __int128");
+ static_assert(!std::is_assignable<unsigned __int128&, absl::int128>::value,
+ "unsigned __int128 must not be assignable from absl::int128");
+}
+#endif // ABSL_HAVE_INTRINSIC_INT128
+
+TEST(Int128, TrivialTraitsTest) {
+ static_assert(absl::is_trivially_default_constructible<absl::int128>::value,
+ "");
+ static_assert(absl::is_trivially_copy_constructible<absl::int128>::value, "");
+ static_assert(absl::is_trivially_copy_assignable<absl::int128>::value, "");
+ static_assert(std::is_trivially_destructible<absl::int128>::value, "");
+}
+
+TEST(Int128, BoolConversionTest) {
+ EXPECT_FALSE(absl::int128(0));
+ for (int i = 0; i < 64; ++i) {
+ EXPECT_TRUE(absl::MakeInt128(0, uint64_t{1} << i));
+ }
+ for (int i = 0; i < 63; ++i) {
+ EXPECT_TRUE(absl::MakeInt128(int64_t{1} << i, 0));
+ }
+ EXPECT_TRUE(absl::Int128Min());
+
+ EXPECT_EQ(absl::int128(1), absl::int128(true));
+ EXPECT_EQ(absl::int128(0), absl::int128(false));
+}
+
+template <typename T>
+class Int128IntegerConversionTest : public ::testing::Test {};
+
+TYPED_TEST_SUITE(Int128IntegerConversionTest, IntegerTypes);
+
+TYPED_TEST(Int128IntegerConversionTest, RoundTripTest) {
+ EXPECT_EQ(TypeParam{0}, static_cast<TypeParam>(absl::int128(0)));
+ EXPECT_EQ(std::numeric_limits<TypeParam>::min(),
+ static_cast<TypeParam>(
+ absl::int128(std::numeric_limits<TypeParam>::min())));
+ EXPECT_EQ(std::numeric_limits<TypeParam>::max(),
+ static_cast<TypeParam>(
+ absl::int128(std::numeric_limits<TypeParam>::max())));
+}
+
+template <typename T>
+class Int128FloatConversionTest : public ::testing::Test {};
+
+TYPED_TEST_SUITE(Int128FloatConversionTest, FloatingPointTypes);
+
+TYPED_TEST(Int128FloatConversionTest, ConstructAndCastTest) {
+ // Conversions where the floating point values should be exactly the same.
+ // 0x9f5b is a randomly chosen small value.
+ for (int i = 0; i < 110; ++i) { // 110 = 126 - #bits in 0x9f5b
+ SCOPED_TRACE(::testing::Message() << "i = " << i);
+
+ TypeParam float_value = std::ldexp(static_cast<TypeParam>(0x9f5b), i);
+ absl::int128 int_value = absl::int128(0x9f5b) << i;
+
+ EXPECT_EQ(float_value, static_cast<TypeParam>(int_value));
+ EXPECT_EQ(-float_value, static_cast<TypeParam>(-int_value));
+ EXPECT_EQ(int_value, absl::int128(float_value));
+ EXPECT_EQ(-int_value, absl::int128(-float_value));
+ }
+
+ // Round trip conversions with a small sample of randomly generated uint64_t
+ // values (less than int64_t max so that value * 2^64 fits into int128).
+ uint64_t values[] = {0x6d4492c24fb86199, 0x26ead65e4cb359b5,
+ 0x2c43407433ba3fd1, 0x3b574ec668df6b55,
+ 0x1c750e55a29f4f0f};
+ for (uint64_t value : values) {
+ for (int i = 0; i <= 64; ++i) {
+ SCOPED_TRACE(::testing::Message()
+ << "value = " << value << "; i = " << i);
+
+ TypeParam fvalue = std::ldexp(static_cast<TypeParam>(value), i);
+ EXPECT_DOUBLE_EQ(fvalue, static_cast<TypeParam>(absl::int128(fvalue)));
+ EXPECT_DOUBLE_EQ(-fvalue, static_cast<TypeParam>(-absl::int128(fvalue)));
+ EXPECT_DOUBLE_EQ(-fvalue, static_cast<TypeParam>(absl::int128(-fvalue)));
+ EXPECT_DOUBLE_EQ(fvalue, static_cast<TypeParam>(-absl::int128(-fvalue)));
+ }
+ }
+
+ // Round trip conversions with a small sample of random large positive values.
+ absl::int128 large_values[] = {
+ absl::MakeInt128(0x5b0640d96c7b3d9f, 0xb7a7189e51d18622),
+ absl::MakeInt128(0x34bed042c6f65270, 0x73b236570669a089),
+ absl::MakeInt128(0x43deba9e6da12724, 0xf7f0f83da686797d),
+ absl::MakeInt128(0x71e8d383be4e5589, 0x75c3f96fb00752b6)};
+ for (absl::int128 value : large_values) {
+ // Make value have as many significant bits as can be represented by
+ // the mantissa, also making sure the highest and lowest bit in the range
+ // are set.
+ value >>= (127 - std::numeric_limits<TypeParam>::digits);
+ value |= absl::int128(1) << (std::numeric_limits<TypeParam>::digits - 1);
+ value |= 1;
+ for (int i = 0; i < 127 - std::numeric_limits<TypeParam>::digits; ++i) {
+ absl::int128 int_value = value << i;
+ EXPECT_EQ(int_value,
+ static_cast<absl::int128>(static_cast<TypeParam>(int_value)));
+ EXPECT_EQ(-int_value,
+ static_cast<absl::int128>(static_cast<TypeParam>(-int_value)));
+ }
+ }
+
+ // Small sample of checks that rounding is toward zero
+ EXPECT_EQ(0, absl::int128(TypeParam(0.1)));
+ EXPECT_EQ(17, absl::int128(TypeParam(17.8)));
+ EXPECT_EQ(0, absl::int128(TypeParam(-0.8)));
+ EXPECT_EQ(-53, absl::int128(TypeParam(-53.1)));
+ EXPECT_EQ(0, absl::int128(TypeParam(0.5)));
+ EXPECT_EQ(0, absl::int128(TypeParam(-0.5)));
+ TypeParam just_lt_one = std::nexttoward(TypeParam(1), TypeParam(0));
+ EXPECT_EQ(0, absl::int128(just_lt_one));
+ TypeParam just_gt_minus_one = std::nexttoward(TypeParam(-1), TypeParam(0));
+ EXPECT_EQ(0, absl::int128(just_gt_minus_one));
+
+ // Check limits
+ EXPECT_DOUBLE_EQ(std::ldexp(static_cast<TypeParam>(1), 127),
+ static_cast<TypeParam>(absl::Int128Max()));
+ EXPECT_DOUBLE_EQ(-std::ldexp(static_cast<TypeParam>(1), 127),
+ static_cast<TypeParam>(absl::Int128Min()));
+}
+
+TEST(Int128, FactoryTest) {
+ EXPECT_EQ(absl::int128(-1), absl::MakeInt128(-1, -1));
+ EXPECT_EQ(absl::int128(-31), absl::MakeInt128(-1, -31));
+ EXPECT_EQ(absl::int128(std::numeric_limits<int64_t>::min()),
+ absl::MakeInt128(-1, std::numeric_limits<int64_t>::min()));
+ EXPECT_EQ(absl::int128(0), absl::MakeInt128(0, 0));
+ EXPECT_EQ(absl::int128(1), absl::MakeInt128(0, 1));
+ EXPECT_EQ(absl::int128(std::numeric_limits<int64_t>::max()),
+ absl::MakeInt128(0, std::numeric_limits<int64_t>::max()));
+}
+
+TEST(Int128, HighLowTest) {
+ struct HighLowPair {
+ int64_t high;
+ uint64_t low;
+ };
+ HighLowPair values[]{{0, 0}, {0, 1}, {1, 0}, {123, 456}, {-654, 321}};
+ for (const HighLowPair& pair : values) {
+ absl::int128 value = absl::MakeInt128(pair.high, pair.low);
+ EXPECT_EQ(pair.low, absl::Int128Low64(value));
+ EXPECT_EQ(pair.high, absl::Int128High64(value));
+ }
+}
+
+TEST(Int128, LimitsTest) {
+ EXPECT_EQ(absl::MakeInt128(0x7fffffffffffffff, 0xffffffffffffffff),
+ absl::Int128Max());
+ EXPECT_EQ(absl::Int128Max(), ~absl::Int128Min());
+}
+
+#if defined(ABSL_HAVE_INTRINSIC_INT128)
+TEST(Int128, IntrinsicConversionTest) {
+ __int128 intrinsic =
+ (static_cast<__int128>(0x3a5b76c209de76f6) << 64) + 0x1f25e1d63a2b46c5;
+ absl::int128 custom =
+ absl::MakeInt128(0x3a5b76c209de76f6, 0x1f25e1d63a2b46c5);
+
+ EXPECT_EQ(custom, absl::int128(intrinsic));
+ EXPECT_EQ(intrinsic, static_cast<__int128>(custom));
+}
+#endif // ABSL_HAVE_INTRINSIC_INT128
+
+TEST(Int128, ConstexprTest) {
+ constexpr absl::int128 zero = absl::int128();
+ constexpr absl::int128 one = 1;
+ constexpr absl::int128 minus_two = -2;
+ constexpr absl::int128 min = absl::Int128Min();
+ constexpr absl::int128 max = absl::Int128Max();
+ EXPECT_EQ(zero, absl::int128(0));
+ EXPECT_EQ(one, absl::int128(1));
+ EXPECT_EQ(minus_two, absl::MakeInt128(-1, -2));
+ EXPECT_GT(max, one);
+ EXPECT_LT(min, minus_two);
+}
+
+TEST(Int128, ComparisonTest) {
+ struct TestCase {
+ absl::int128 smaller;
+ absl::int128 larger;
+ };
+ TestCase cases[] = {
+ {absl::int128(0), absl::int128(123)},
+ {absl::MakeInt128(-12, 34), absl::MakeInt128(12, 34)},
+ {absl::MakeInt128(1, 1000), absl::MakeInt128(1000, 1)},
+ {absl::MakeInt128(-1000, 1000), absl::MakeInt128(-1, 1)},
+ };
+ for (const TestCase& pair : cases) {
+ SCOPED_TRACE(::testing::Message() << "pair.smaller = " << pair.smaller
+ << "; pair.larger = " << pair.larger);
+
+ EXPECT_TRUE(pair.smaller == pair.smaller); // NOLINT(readability/check)
+ EXPECT_TRUE(pair.larger == pair.larger); // NOLINT(readability/check)
+ EXPECT_FALSE(pair.smaller == pair.larger); // NOLINT(readability/check)
+
+ EXPECT_TRUE(pair.smaller != pair.larger); // NOLINT(readability/check)
+ EXPECT_FALSE(pair.smaller != pair.smaller); // NOLINT(readability/check)
+ EXPECT_FALSE(pair.larger != pair.larger); // NOLINT(readability/check)
+
+ EXPECT_TRUE(pair.smaller < pair.larger); // NOLINT(readability/check)
+ EXPECT_FALSE(pair.larger < pair.smaller); // NOLINT(readability/check)
+
+ EXPECT_TRUE(pair.larger > pair.smaller); // NOLINT(readability/check)
+ EXPECT_FALSE(pair.smaller > pair.larger); // NOLINT(readability/check)
+
+ EXPECT_TRUE(pair.smaller <= pair.larger); // NOLINT(readability/check)
+ EXPECT_FALSE(pair.larger <= pair.smaller); // NOLINT(readability/check)
+ EXPECT_TRUE(pair.smaller <= pair.smaller); // NOLINT(readability/check)
+ EXPECT_TRUE(pair.larger <= pair.larger); // NOLINT(readability/check)
+
+ EXPECT_TRUE(pair.larger >= pair.smaller); // NOLINT(readability/check)
+ EXPECT_FALSE(pair.smaller >= pair.larger); // NOLINT(readability/check)
+ EXPECT_TRUE(pair.smaller >= pair.smaller); // NOLINT(readability/check)
+ EXPECT_TRUE(pair.larger >= pair.larger); // NOLINT(readability/check)
+ }
+}
+
+TEST(Int128, UnaryNegationTest) {
+ int64_t values64[] = {0, 1, 12345, 0x4000000000000000,
+ std::numeric_limits<int64_t>::max()};
+ for (int64_t value : values64) {
+ SCOPED_TRACE(::testing::Message() << "value = " << value);
+
+ EXPECT_EQ(absl::int128(-value), -absl::int128(value));
+ EXPECT_EQ(absl::int128(value), -absl::int128(-value));
+ EXPECT_EQ(absl::MakeInt128(-value, 0), -absl::MakeInt128(value, 0));
+ EXPECT_EQ(absl::MakeInt128(value, 0), -absl::MakeInt128(-value, 0));
+ }
+}
+
+TEST(Int128, LogicalNotTest) {
+ EXPECT_TRUE(!absl::int128(0));
+ for (int i = 0; i < 64; ++i) {
+ EXPECT_FALSE(!absl::MakeInt128(0, uint64_t{1} << i));
+ }
+ for (int i = 0; i < 63; ++i) {
+ EXPECT_FALSE(!absl::MakeInt128(int64_t{1} << i, 0));
+ }
+}
+
+TEST(Int128, AdditionSubtractionTest) {
+ // 64 bit pairs that will not cause overflow / underflow. These test negative
+ // carry; positive carry must be checked separately.
+ std::pair<int64_t, int64_t> cases[]{
+ {0, 0}, // 0, 0
+ {0, 2945781290834}, // 0, +
+ {1908357619234, 0}, // +, 0
+ {0, -1204895918245}, // 0, -
+ {-2957928523560, 0}, // -, 0
+ {89023982312461, 98346012567134}, // +, +
+ {-63454234568239, -23456235230773}, // -, -
+ {98263457263502, -21428561935925}, // +, -
+ {-88235237438467, 15923659234573}, // -, +
+ };
+ for (const auto& pair : cases) {
+ SCOPED_TRACE(::testing::Message()
+ << "pair = {" << pair.first << ", " << pair.second << '}');
+
+ EXPECT_EQ(absl::int128(pair.first + pair.second),
+ absl::int128(pair.first) + absl::int128(pair.second));
+ EXPECT_EQ(absl::int128(pair.second + pair.first),
+ absl::int128(pair.second) += absl::int128(pair.first));
+
+ EXPECT_EQ(absl::int128(pair.first - pair.second),
+ absl::int128(pair.first) - absl::int128(pair.second));
+ EXPECT_EQ(absl::int128(pair.second - pair.first),
+ absl::int128(pair.second) -= absl::int128(pair.first));
+
+ EXPECT_EQ(
+ absl::MakeInt128(pair.second + pair.first, 0),
+ absl::MakeInt128(pair.second, 0) + absl::MakeInt128(pair.first, 0));
+ EXPECT_EQ(
+ absl::MakeInt128(pair.first + pair.second, 0),
+ absl::MakeInt128(pair.first, 0) += absl::MakeInt128(pair.second, 0));
+
+ EXPECT_EQ(
+ absl::MakeInt128(pair.second - pair.first, 0),
+ absl::MakeInt128(pair.second, 0) - absl::MakeInt128(pair.first, 0));
+ EXPECT_EQ(
+ absl::MakeInt128(pair.first - pair.second, 0),
+ absl::MakeInt128(pair.first, 0) -= absl::MakeInt128(pair.second, 0));
+ }
+
+ // check positive carry
+ EXPECT_EQ(absl::MakeInt128(31, 0),
+ absl::MakeInt128(20, 1) +
+ absl::MakeInt128(10, std::numeric_limits<uint64_t>::max()));
+}
+
+TEST(Int128, IncrementDecrementTest) {
+ absl::int128 value = 0;
+ EXPECT_EQ(0, value++);
+ EXPECT_EQ(1, value);
+ EXPECT_EQ(1, value--);
+ EXPECT_EQ(0, value);
+ EXPECT_EQ(-1, --value);
+ EXPECT_EQ(-1, value);
+ EXPECT_EQ(0, ++value);
+ EXPECT_EQ(0, value);
+}
+
+TEST(Int128, MultiplicationTest) {
+ // 1 bit x 1 bit, and negative combinations
+ for (int i = 0; i < 64; ++i) {
+ for (int j = 0; j < 127 - i; ++j) {
+ SCOPED_TRACE(::testing::Message() << "i = " << i << "; j = " << j);
+ absl::int128 a = absl::int128(1) << i;
+ absl::int128 b = absl::int128(1) << j;
+ absl::int128 c = absl::int128(1) << (i + j);
+
+ EXPECT_EQ(c, a * b);
+ EXPECT_EQ(-c, -a * b);
+ EXPECT_EQ(-c, a * -b);
+ EXPECT_EQ(c, -a * -b);
+
+ EXPECT_EQ(c, absl::int128(a) *= b);
+ EXPECT_EQ(-c, absl::int128(-a) *= b);
+ EXPECT_EQ(-c, absl::int128(a) *= -b);
+ EXPECT_EQ(c, absl::int128(-a) *= -b);
+ }
+ }
+
+ // Pairs of random values that will not overflow signed 64-bit multiplication
+ std::pair<int64_t, int64_t> small_values[] = {
+ {0x5e61, 0xf29f79ca14b4}, // +, +
+ {0x3e033b, -0x612c0ee549}, // +, -
+ {-0x052ce7e8, 0x7c728f0f}, // -, +
+ {-0x3af7054626, -0xfb1e1d}, // -, -
+ };
+ for (const std::pair<int64_t, int64_t>& pair : small_values) {
+ SCOPED_TRACE(::testing::Message()
+ << "pair = {" << pair.first << ", " << pair.second << '}');
+
+ EXPECT_EQ(absl::int128(pair.first * pair.second),
+ absl::int128(pair.first) * absl::int128(pair.second));
+ EXPECT_EQ(absl::int128(pair.first * pair.second),
+ absl::int128(pair.first) *= absl::int128(pair.second));
+
+ EXPECT_EQ(absl::MakeInt128(pair.first * pair.second, 0),
+ absl::MakeInt128(pair.first, 0) * absl::int128(pair.second));
+ EXPECT_EQ(absl::MakeInt128(pair.first * pair.second, 0),
+ absl::MakeInt128(pair.first, 0) *= absl::int128(pair.second));
+ }
+
+ // Pairs of positive random values that will not overflow 64-bit
+ // multiplication and can be left shifted by 32 without overflow
+ std::pair<int64_t, int64_t> small_values2[] = {
+ {0x1bb0a110, 0x31487671},
+ {0x4792784e, 0x28add7d7},
+ {0x7b66553a, 0x11dff8ef},
+ };
+ for (const std::pair<int64_t, int64_t>& pair : small_values2) {
+ SCOPED_TRACE(::testing::Message()
+ << "pair = {" << pair.first << ", " << pair.second << '}');
+
+ absl::int128 a = absl::int128(pair.first << 32);
+ absl::int128 b = absl::int128(pair.second << 32);
+ absl::int128 c = absl::MakeInt128(pair.first * pair.second, 0);
+
+ EXPECT_EQ(c, a * b);
+ EXPECT_EQ(-c, -a * b);
+ EXPECT_EQ(-c, a * -b);
+ EXPECT_EQ(c, -a * -b);
+
+ EXPECT_EQ(c, absl::int128(a) *= b);
+ EXPECT_EQ(-c, absl::int128(-a) *= b);
+ EXPECT_EQ(-c, absl::int128(a) *= -b);
+ EXPECT_EQ(c, absl::int128(-a) *= -b);
+ }
+
+ // check 0, 1, and -1 behavior with large values
+ absl::int128 large_values[] = {
+ {absl::MakeInt128(0xd66f061af02d0408, 0x727d2846cb475b53)},
+ {absl::MakeInt128(0x27b8d5ed6104452d, 0x03f8a33b0ee1df4f)},
+ {-absl::MakeInt128(0x621b6626b9e8d042, 0x27311ac99df00938)},
+ {-absl::MakeInt128(0x34e0656f1e95fb60, 0x4281cfd731257a47)},
+ };
+ for (absl::int128 value : large_values) {
+ EXPECT_EQ(0, 0 * value);
+ EXPECT_EQ(0, value * 0);
+ EXPECT_EQ(0, absl::int128(0) *= value);
+ EXPECT_EQ(0, value *= 0);
+
+ EXPECT_EQ(value, 1 * value);
+ EXPECT_EQ(value, value * 1);
+ EXPECT_EQ(value, absl::int128(1) *= value);
+ EXPECT_EQ(value, value *= 1);
+
+ EXPECT_EQ(-value, -1 * value);
+ EXPECT_EQ(-value, value * -1);
+ EXPECT_EQ(-value, absl::int128(-1) *= value);
+ EXPECT_EQ(-value, value *= -1);
+ }
+
+ // Manually calculated random large value cases
+ EXPECT_EQ(absl::MakeInt128(0xcd0efd3442219bb, 0xde47c05bcd9df6e1),
+ absl::MakeInt128(0x7c6448, 0x3bc4285c47a9d253) * 0x1a6037537b);
+ EXPECT_EQ(-absl::MakeInt128(0x1f8f149850b1e5e6, 0x1e50d6b52d272c3e),
+ -absl::MakeInt128(0x23, 0x2e68a513ca1b8859) * 0xe5a434cd14866e);
+ EXPECT_EQ(-absl::MakeInt128(0x55cae732029d1fce, 0xca6474b6423263e4),
+ 0xa9b98a8ddf66bc * -absl::MakeInt128(0x81, 0x672e58231e2469d7));
+ EXPECT_EQ(absl::MakeInt128(0x19c8b7620b507dc4, 0xfec042b71a5f29a4),
+ -0x3e39341147 * -absl::MakeInt128(0x6a14b2, 0x5ed34cca42327b3c));
+
+ EXPECT_EQ(absl::MakeInt128(0xcd0efd3442219bb, 0xde47c05bcd9df6e1),
+ absl::MakeInt128(0x7c6448, 0x3bc4285c47a9d253) *= 0x1a6037537b);
+ EXPECT_EQ(-absl::MakeInt128(0x1f8f149850b1e5e6, 0x1e50d6b52d272c3e),
+ -absl::MakeInt128(0x23, 0x2e68a513ca1b8859) *= 0xe5a434cd14866e);
+ EXPECT_EQ(-absl::MakeInt128(0x55cae732029d1fce, 0xca6474b6423263e4),
+ absl::int128(0xa9b98a8ddf66bc) *=
+ -absl::MakeInt128(0x81, 0x672e58231e2469d7));
+ EXPECT_EQ(absl::MakeInt128(0x19c8b7620b507dc4, 0xfec042b71a5f29a4),
+ absl::int128(-0x3e39341147) *=
+ -absl::MakeInt128(0x6a14b2, 0x5ed34cca42327b3c));
+}
+
+TEST(Int128, DivisionAndModuloTest) {
+ // Check against 64 bit division and modulo operators with a sample of
+ // randomly generated pairs.
+ std::pair<int64_t, int64_t> small_pairs[] = {
+ {0x15f2a64138, 0x67da05}, {0x5e56d194af43045f, 0xcf1543fb99},
+ {0x15e61ed052036a, -0xc8e6}, {0x88125a341e85, -0xd23fb77683},
+ {-0xc06e20, 0x5a}, {-0x4f100219aea3e85d, 0xdcc56cb4efe993},
+ {-0x168d629105, -0xa7}, {-0x7b44e92f03ab2375, -0x6516},
+ };
+ for (const std::pair<int64_t, int64_t>& pair : small_pairs) {
+ SCOPED_TRACE(::testing::Message()
+ << "pair = {" << pair.first << ", " << pair.second << '}');
+
+ absl::int128 dividend = pair.first;
+ absl::int128 divisor = pair.second;
+ int64_t quotient = pair.first / pair.second;
+ int64_t remainder = pair.first % pair.second;
+
+ EXPECT_EQ(quotient, dividend / divisor);
+ EXPECT_EQ(quotient, absl::int128(dividend) /= divisor);
+ EXPECT_EQ(remainder, dividend % divisor);
+ EXPECT_EQ(remainder, absl::int128(dividend) %= divisor);
+ }
+
+ // Test behavior with 0, 1, and -1 with a sample of randomly generated large
+ // values.
+ absl::int128 values[] = {
+ absl::MakeInt128(0x63d26ee688a962b2, 0x9e1411abda5c1d70),
+ absl::MakeInt128(0x152f385159d6f986, 0xbf8d48ef63da395d),
+ -absl::MakeInt128(0x3098d7567030038c, 0x14e7a8a098dc2164),
+ -absl::MakeInt128(0x49a037aca35c809f, 0xa6a87525480ef330),
+ };
+ for (absl::int128 value : values) {
+ SCOPED_TRACE(::testing::Message() << "value = " << value);
+
+ EXPECT_EQ(0, 0 / value);
+ EXPECT_EQ(0, absl::int128(0) /= value);
+ EXPECT_EQ(0, 0 % value);
+ EXPECT_EQ(0, absl::int128(0) %= value);
+
+ EXPECT_EQ(value, value / 1);
+ EXPECT_EQ(value, absl::int128(value) /= 1);
+ EXPECT_EQ(0, value % 1);
+ EXPECT_EQ(0, absl::int128(value) %= 1);
+
+ EXPECT_EQ(-value, value / -1);
+ EXPECT_EQ(-value, absl::int128(value) /= -1);
+ EXPECT_EQ(0, value % -1);
+ EXPECT_EQ(0, absl::int128(value) %= -1);
+ }
+
+ // Min and max values
+ EXPECT_EQ(0, absl::Int128Max() / absl::Int128Min());
+ EXPECT_EQ(absl::Int128Max(), absl::Int128Max() % absl::Int128Min());
+ EXPECT_EQ(-1, absl::Int128Min() / absl::Int128Max());
+ EXPECT_EQ(-1, absl::Int128Min() % absl::Int128Max());
+
+ // Power of two division and modulo of random large dividends
+ absl::int128 positive_values[] = {
+ absl::MakeInt128(0x21e1a1cc69574620, 0xe7ac447fab2fc869),
+ absl::MakeInt128(0x32c2ff3ab89e66e8, 0x03379a613fd1ce74),
+ absl::MakeInt128(0x6f32ca786184dcaf, 0x046f9c9ecb3a9ce1),
+ absl::MakeInt128(0x1aeb469dd990e0ee, 0xda2740f243cd37eb),
+ };
+ for (absl::int128 value : positive_values) {
+ for (int i = 0; i < 127; ++i) {
+ SCOPED_TRACE(::testing::Message()
+ << "value = " << value << "; i = " << i);
+ absl::int128 power_of_two = absl::int128(1) << i;
+
+ EXPECT_EQ(value >> i, value / power_of_two);
+ EXPECT_EQ(value >> i, absl::int128(value) /= power_of_two);
+ EXPECT_EQ(value & (power_of_two - 1), value % power_of_two);
+ EXPECT_EQ(value & (power_of_two - 1),
+ absl::int128(value) %= power_of_two);
+ }
+ }
+
+ // Manually calculated cases with random large dividends
+ struct DivisionModCase {
+ absl::int128 dividend;
+ absl::int128 divisor;
+ absl::int128 quotient;
+ absl::int128 remainder;
+ };
+ DivisionModCase manual_cases[] = {
+ {absl::MakeInt128(0x6ada48d489007966, 0x3c9c5c98150d5d69),
+ absl::MakeInt128(0x8bc308fb, 0x8cb9cc9a3b803344), 0xc3b87e08,
+ absl::MakeInt128(0x1b7db5e1, 0xd9eca34b7af04b49)},
+ {absl::MakeInt128(0xd6946511b5b, 0x4886c5c96546bf5f),
+ -absl::MakeInt128(0x263b, 0xfd516279efcfe2dc), -0x59cbabf0,
+ absl::MakeInt128(0x622, 0xf462909155651d1f)},
+ {-absl::MakeInt128(0x33db734f9e8d1399, 0x8447ac92482bca4d), 0x37495078240,
+ -absl::MakeInt128(0xf01f1, 0xbc0368bf9a77eae8), -0x21a508f404d},
+ {-absl::MakeInt128(0x13f837b409a07e7d, 0x7fc8e248a7d73560), -0x1b9f,
+ absl::MakeInt128(0xb9157556d724, 0xb14f635714d7563e), -0x1ade},
+ };
+ for (const DivisionModCase test_case : manual_cases) {
+ EXPECT_EQ(test_case.quotient, test_case.dividend / test_case.divisor);
+ EXPECT_EQ(test_case.quotient,
+ absl::int128(test_case.dividend) /= test_case.divisor);
+ EXPECT_EQ(test_case.remainder, test_case.dividend % test_case.divisor);
+ EXPECT_EQ(test_case.remainder,
+ absl::int128(test_case.dividend) %= test_case.divisor);
+ }
+}
+
+TEST(Int128, BitwiseLogicTest) {
+ EXPECT_EQ(absl::int128(-1), ~absl::int128(0));
+
+ absl::int128 values[]{
+ 0, -1, 0xde400bee05c3ff6b, absl::MakeInt128(0x7f32178dd81d634a, 0),
+ absl::MakeInt128(0xaf539057055613a9, 0x7d104d7d946c2e4d)};
+ for (absl::int128 value : values) {
+ EXPECT_EQ(value, ~~value);
+
+ EXPECT_EQ(value, value | value);
+ EXPECT_EQ(value, value & value);
+ EXPECT_EQ(0, value ^ value);
+
+ EXPECT_EQ(value, absl::int128(value) |= value);
+ EXPECT_EQ(value, absl::int128(value) &= value);
+ EXPECT_EQ(0, absl::int128(value) ^= value);
+
+ EXPECT_EQ(value, value | 0);
+ EXPECT_EQ(0, value & 0);
+ EXPECT_EQ(value, value ^ 0);
+
+ EXPECT_EQ(absl::int128(-1), value | absl::int128(-1));
+ EXPECT_EQ(value, value & absl::int128(-1));
+ EXPECT_EQ(~value, value ^ absl::int128(-1));
+ }
+
+ // small sample of randomly generated int64_t's
+ std::pair<int64_t, int64_t> pairs64[]{
+ {0x7f86797f5e991af4, 0x1ee30494fb007c97},
+ {0x0b278282bacf01af, 0x58780e0a57a49e86},
+ {0x059f266ccb93a666, 0x3d5b731bae9286f5},
+ {0x63c0c4820f12108c, 0x58166713c12e1c3a},
+ {0x381488bb2ed2a66e, 0x2220a3eb76a3698c},
+ {0x2a0a0dfb81e06f21, 0x4b60585927f5523c},
+ {0x555b1c3a03698537, 0x25478cd19d8e53cb},
+ {0x4750f6f27d779225, 0x16397553c6ff05fc},
+ };
+ for (const std::pair<int64_t, int64_t>& pair : pairs64) {
+ SCOPED_TRACE(::testing::Message()
+ << "pair = {" << pair.first << ", " << pair.second << '}');
+
+ EXPECT_EQ(absl::MakeInt128(~pair.first, ~pair.second),
+ ~absl::MakeInt128(pair.first, pair.second));
+
+ EXPECT_EQ(absl::int128(pair.first & pair.second),
+ absl::int128(pair.first) & absl::int128(pair.second));
+ EXPECT_EQ(absl::int128(pair.first | pair.second),
+ absl::int128(pair.first) | absl::int128(pair.second));
+ EXPECT_EQ(absl::int128(pair.first ^ pair.second),
+ absl::int128(pair.first) ^ absl::int128(pair.second));
+
+ EXPECT_EQ(absl::int128(pair.first & pair.second),
+ absl::int128(pair.first) &= absl::int128(pair.second));
+ EXPECT_EQ(absl::int128(pair.first | pair.second),
+ absl::int128(pair.first) |= absl::int128(pair.second));
+ EXPECT_EQ(absl::int128(pair.first ^ pair.second),
+ absl::int128(pair.first) ^= absl::int128(pair.second));
+
+ EXPECT_EQ(
+ absl::MakeInt128(pair.first & pair.second, 0),
+ absl::MakeInt128(pair.first, 0) & absl::MakeInt128(pair.second, 0));
+ EXPECT_EQ(
+ absl::MakeInt128(pair.first | pair.second, 0),
+ absl::MakeInt128(pair.first, 0) | absl::MakeInt128(pair.second, 0));
+ EXPECT_EQ(
+ absl::MakeInt128(pair.first ^ pair.second, 0),
+ absl::MakeInt128(pair.first, 0) ^ absl::MakeInt128(pair.second, 0));
+
+ EXPECT_EQ(
+ absl::MakeInt128(pair.first & pair.second, 0),
+ absl::MakeInt128(pair.first, 0) &= absl::MakeInt128(pair.second, 0));
+ EXPECT_EQ(
+ absl::MakeInt128(pair.first | pair.second, 0),
+ absl::MakeInt128(pair.first, 0) |= absl::MakeInt128(pair.second, 0));
+ EXPECT_EQ(
+ absl::MakeInt128(pair.first ^ pair.second, 0),
+ absl::MakeInt128(pair.first, 0) ^= absl::MakeInt128(pair.second, 0));
+ }
+}
+
+TEST(Int128, BitwiseShiftTest) {
+ for (int i = 0; i < 64; ++i) {
+ for (int j = 0; j <= i; ++j) {
+ // Left shift from j-th bit to i-th bit.
+ SCOPED_TRACE(::testing::Message() << "i = " << i << "; j = " << j);
+ EXPECT_EQ(uint64_t{1} << i, absl::int128(uint64_t{1} << j) << (i - j));
+ EXPECT_EQ(uint64_t{1} << i, absl::int128(uint64_t{1} << j) <<= (i - j));
+ }
+ }
+ for (int i = 0; i < 63; ++i) {
+ for (int j = 0; j < 64; ++j) {
+ // Left shift from j-th bit to (i + 64)-th bit.
+ SCOPED_TRACE(::testing::Message() << "i = " << i << "; j = " << j);
+ EXPECT_EQ(absl::MakeInt128(uint64_t{1} << i, 0),
+ absl::int128(uint64_t{1} << j) << (i + 64 - j));
+ EXPECT_EQ(absl::MakeInt128(uint64_t{1} << i, 0),
+ absl::int128(uint64_t{1} << j) <<= (i + 64 - j));
+ }
+ for (int j = 0; j <= i; ++j) {
+ // Left shift from (j + 64)-th bit to (i + 64)-th bit.
+ SCOPED_TRACE(::testing::Message() << "i = " << i << "; j = " << j);
+ EXPECT_EQ(absl::MakeInt128(uint64_t{1} << i, 0),
+ absl::MakeInt128(uint64_t{1} << j, 0) << (i - j));
+ EXPECT_EQ(absl::MakeInt128(uint64_t{1} << i, 0),
+ absl::MakeInt128(uint64_t{1} << j, 0) <<= (i - j));
+ }
+ }
+
+ for (int i = 0; i < 64; ++i) {
+ for (int j = i; j < 64; ++j) {
+ // Right shift from j-th bit to i-th bit.
+ SCOPED_TRACE(::testing::Message() << "i = " << i << "; j = " << j);
+ EXPECT_EQ(uint64_t{1} << i, absl::int128(uint64_t{1} << j) >> (j - i));
+ EXPECT_EQ(uint64_t{1} << i, absl::int128(uint64_t{1} << j) >>= (j - i));
+ }
+ for (int j = 0; j < 63; ++j) {
+ // Right shift from (j + 64)-th bit to i-th bit.
+ SCOPED_TRACE(::testing::Message() << "i = " << i << "; j = " << j);
+ EXPECT_EQ(uint64_t{1} << i,
+ absl::MakeInt128(uint64_t{1} << j, 0) >> (j + 64 - i));
+ EXPECT_EQ(uint64_t{1} << i,
+ absl::MakeInt128(uint64_t{1} << j, 0) >>= (j + 64 - i));
+ }
+ }
+ for (int i = 0; i < 63; ++i) {
+ for (int j = i; j < 63; ++j) {
+ // Right shift from (j + 64)-th bit to (i + 64)-th bit.
+ SCOPED_TRACE(::testing::Message() << "i = " << i << "; j = " << j);
+ EXPECT_EQ(absl::MakeInt128(uint64_t{1} << i, 0),
+ absl::MakeInt128(uint64_t{1} << j, 0) >> (j - i));
+ EXPECT_EQ(absl::MakeInt128(uint64_t{1} << i, 0),
+ absl::MakeInt128(uint64_t{1} << j, 0) >>= (j - i));
+ }
+ }
+}
+
+TEST(Int128, NumericLimitsTest) {
+ static_assert(std::numeric_limits<absl::int128>::is_specialized, "");
+ static_assert(std::numeric_limits<absl::int128>::is_signed, "");
+ static_assert(std::numeric_limits<absl::int128>::is_integer, "");
+ EXPECT_EQ(static_cast<int>(127 * std::log10(2)),
+ std::numeric_limits<absl::int128>::digits10);
+ EXPECT_EQ(absl::Int128Min(), std::numeric_limits<absl::int128>::min());
+ EXPECT_EQ(absl::Int128Min(), std::numeric_limits<absl::int128>::lowest());
+ EXPECT_EQ(absl::Int128Max(), std::numeric_limits<absl::int128>::max());
+}
+
} // namespace
diff --git a/absl/numeric/internal/bits.h b/absl/numeric/internal/bits.h
new file mode 100644
index 0000000..af45700
--- /dev/null
+++ b/absl/numeric/internal/bits.h
@@ -0,0 +1,349 @@
+// 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.
+
+#ifndef ABSL_NUMERIC_INTERNAL_BITS_H_
+#define ABSL_NUMERIC_INTERNAL_BITS_H_
+
+#include <cstdint>
+#include <limits>
+#include <type_traits>
+
+// Clang on Windows has __builtin_clzll; otherwise we need to use the
+// windows intrinsic functions.
+#if defined(_MSC_VER) && !defined(__clang__)
+#include <intrin.h>
+#endif
+
+#include "absl/base/attributes.h"
+#include "absl/base/config.h"
+
+#if ABSL_HAVE_BUILTIN(__builtin_popcountl) && \
+ ABSL_HAVE_BUILTIN(__builtin_popcountll)
+#define ABSL_INTERNAL_CONSTEXPR_POPCOUNT constexpr
+#define ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT 1
+#else
+#define ABSL_INTERNAL_CONSTEXPR_POPCOUNT
+#define ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT 0
+#endif
+
+#if ABSL_HAVE_BUILTIN(__builtin_clz) && ABSL_HAVE_BUILTIN(__builtin_clzll)
+#define ABSL_INTERNAL_CONSTEXPR_CLZ constexpr
+#define ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 1
+#else
+#define ABSL_INTERNAL_CONSTEXPR_CLZ
+#define ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 0
+#endif
+
+#if ABSL_HAVE_BUILTIN(__builtin_ctz) && ABSL_HAVE_BUILTIN(__builtin_ctzll)
+#define ABSL_INTERNAL_CONSTEXPR_CTZ constexpr
+#define ABSL_INTERNAL_HAS_CONSTEXPR_CTZ 1
+#else
+#define ABSL_INTERNAL_CONSTEXPR_CTZ
+#define ABSL_INTERNAL_HAS_CONSTEXPR_CTZ 0
+#endif
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace numeric_internal {
+
+constexpr bool IsPowerOf2(unsigned int x) noexcept {
+ return x != 0 && (x & (x - 1)) == 0;
+}
+
+template <class T>
+ABSL_MUST_USE_RESULT ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateRight(
+ T x, int s) noexcept {
+ static_assert(std::is_unsigned<T>::value, "T must be unsigned");
+ static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
+ "T must have a power-of-2 size");
+
+ return static_cast<T>(x >> (s & (std::numeric_limits<T>::digits - 1))) |
+ static_cast<T>(x << ((-s) & (std::numeric_limits<T>::digits - 1)));
+}
+
+template <class T>
+ABSL_MUST_USE_RESULT ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateLeft(
+ T x, int s) noexcept {
+ static_assert(std::is_unsigned<T>::value, "T must be unsigned");
+ static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
+ "T must have a power-of-2 size");
+
+ return static_cast<T>(x << (s & (std::numeric_limits<T>::digits - 1))) |
+ static_cast<T>(x >> ((-s) & (std::numeric_limits<T>::digits - 1)));
+}
+
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int
+Popcount32(uint32_t x) noexcept {
+#if ABSL_HAVE_BUILTIN(__builtin_popcount)
+ static_assert(sizeof(unsigned int) == sizeof(x),
+ "__builtin_popcount does not take 32-bit arg");
+ return __builtin_popcount(x);
+#else
+ x -= ((x >> 1) & 0x55555555);
+ x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
+ return static_cast<int>((((x + (x >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24);
+#endif
+}
+
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int
+Popcount64(uint64_t x) noexcept {
+#if ABSL_HAVE_BUILTIN(__builtin_popcountll)
+ static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int)
+ "__builtin_popcount does not take 64-bit arg");
+ return __builtin_popcountll(x);
+#else
+ x -= (x >> 1) & 0x5555555555555555ULL;
+ x = ((x >> 2) & 0x3333333333333333ULL) + (x & 0x3333333333333333ULL);
+ return static_cast<int>(
+ (((x + (x >> 4)) & 0xF0F0F0F0F0F0F0FULL) * 0x101010101010101ULL) >> 56);
+#endif
+}
+
+template <class T>
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int
+Popcount(T x) noexcept {
+ static_assert(std::is_unsigned<T>::value, "T must be unsigned");
+ static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
+ "T must have a power-of-2 size");
+ static_assert(sizeof(x) <= sizeof(uint64_t), "T is too large");
+ return sizeof(x) <= sizeof(uint32_t) ? Popcount32(x) : Popcount64(x);
+}
+
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int
+CountLeadingZeroes32(uint32_t x) {
+#if ABSL_HAVE_BUILTIN(__builtin_clz)
+ // Use __builtin_clz, which uses the following instructions:
+ // x86: bsr, lzcnt
+ // ARM64: clz
+ // PPC: cntlzd
+
+ static_assert(sizeof(unsigned int) == sizeof(x),
+ "__builtin_clz does not take 32-bit arg");
+ // Handle 0 as a special case because __builtin_clz(0) is undefined.
+ return x == 0 ? 32 : __builtin_clz(x);
+#elif defined(_MSC_VER) && !defined(__clang__)
+ unsigned long result = 0; // NOLINT(runtime/int)
+ if (_BitScanReverse(&result, x)) {
+ return 31 - result;
+ }
+ return 32;
+#else
+ int zeroes = 28;
+ if (x >> 16) {
+ zeroes -= 16;
+ x >>= 16;
+ }
+ if (x >> 8) {
+ zeroes -= 8;
+ x >>= 8;
+ }
+ if (x >> 4) {
+ zeroes -= 4;
+ x >>= 4;
+ }
+ return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes;
+#endif
+}
+
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int
+CountLeadingZeroes16(uint16_t x) {
+#if ABSL_HAVE_BUILTIN(__builtin_clzs)
+ static_assert(sizeof(unsigned short) == sizeof(x), // NOLINT(runtime/int)
+ "__builtin_clzs does not take 16-bit arg");
+ return x == 0 ? 16 : __builtin_clzs(x);
+#else
+ return CountLeadingZeroes32(x) - 16;
+#endif
+}
+
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int
+CountLeadingZeroes64(uint64_t x) {
+#if ABSL_HAVE_BUILTIN(__builtin_clzll)
+ // Use __builtin_clzll, which uses the following instructions:
+ // x86: bsr, lzcnt
+ // ARM64: clz
+ // PPC: cntlzd
+ static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int)
+ "__builtin_clzll does not take 64-bit arg");
+
+ // Handle 0 as a special case because __builtin_clzll(0) is undefined.
+ return x == 0 ? 64 : __builtin_clzll(x);
+#elif defined(_MSC_VER) && !defined(__clang__) && \
+ (defined(_M_X64) || defined(_M_ARM64))
+ // MSVC does not have __buitin_clzll. Use _BitScanReverse64.
+ unsigned long result = 0; // NOLINT(runtime/int)
+ if (_BitScanReverse64(&result, x)) {
+ return 63 - result;
+ }
+ return 64;
+#elif defined(_MSC_VER) && !defined(__clang__)
+ // MSVC does not have __buitin_clzll. Compose two calls to _BitScanReverse
+ unsigned long result = 0; // NOLINT(runtime/int)
+ if ((x >> 32) &&
+ _BitScanReverse(&result, static_cast<unsigned long>(x >> 32))) {
+ return 31 - result;
+ }
+ if (_BitScanReverse(&result, static_cast<unsigned long>(x))) {
+ return 63 - result;
+ }
+ return 64;
+#else
+ int zeroes = 60;
+ if (x >> 32) {
+ zeroes -= 32;
+ x >>= 32;
+ }
+ if (x >> 16) {
+ zeroes -= 16;
+ x >>= 16;
+ }
+ if (x >> 8) {
+ zeroes -= 8;
+ x >>= 8;
+ }
+ if (x >> 4) {
+ zeroes -= 4;
+ x >>= 4;
+ }
+ return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes;
+#endif
+}
+
+template <typename T>
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int
+CountLeadingZeroes(T x) {
+ static_assert(std::is_unsigned<T>::value, "T must be unsigned");
+ static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
+ "T must have a power-of-2 size");
+ static_assert(sizeof(T) <= sizeof(uint64_t), "T too large");
+ return sizeof(T) <= sizeof(uint16_t)
+ ? CountLeadingZeroes16(static_cast<uint16_t>(x)) -
+ (std::numeric_limits<uint16_t>::digits -
+ std::numeric_limits<T>::digits)
+ : (sizeof(T) <= sizeof(uint32_t)
+ ? CountLeadingZeroes32(static_cast<uint32_t>(x)) -
+ (std::numeric_limits<uint32_t>::digits -
+ std::numeric_limits<T>::digits)
+ : CountLeadingZeroes64(x));
+}
+
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
+CountTrailingZeroesNonzero32(uint32_t x) {
+#if ABSL_HAVE_BUILTIN(__builtin_ctz)
+ static_assert(sizeof(unsigned int) == sizeof(x),
+ "__builtin_ctz does not take 32-bit arg");
+ return __builtin_ctz(x);
+#elif defined(_MSC_VER) && !defined(__clang__)
+ unsigned long result = 0; // NOLINT(runtime/int)
+ _BitScanForward(&result, x);
+ return result;
+#else
+ int c = 31;
+ x &= ~x + 1;
+ if (x & 0x0000FFFF) c -= 16;
+ if (x & 0x00FF00FF) c -= 8;
+ if (x & 0x0F0F0F0F) c -= 4;
+ if (x & 0x33333333) c -= 2;
+ if (x & 0x55555555) c -= 1;
+ return c;
+#endif
+}
+
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
+CountTrailingZeroesNonzero64(uint64_t x) {
+#if ABSL_HAVE_BUILTIN(__builtin_ctzll)
+ static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int)
+ "__builtin_ctzll does not take 64-bit arg");
+ return __builtin_ctzll(x);
+#elif defined(_MSC_VER) && !defined(__clang__) && \
+ (defined(_M_X64) || defined(_M_ARM64))
+ unsigned long result = 0; // NOLINT(runtime/int)
+ _BitScanForward64(&result, x);
+ return result;
+#elif defined(_MSC_VER) && !defined(__clang__)
+ unsigned long result = 0; // NOLINT(runtime/int)
+ if (static_cast<uint32_t>(x) == 0) {
+ _BitScanForward(&result, static_cast<unsigned long>(x >> 32));
+ return result + 32;
+ }
+ _BitScanForward(&result, static_cast<unsigned long>(x));
+ return result;
+#else
+ int c = 63;
+ x &= ~x + 1;
+ if (x & 0x00000000FFFFFFFF) c -= 32;
+ if (x & 0x0000FFFF0000FFFF) c -= 16;
+ if (x & 0x00FF00FF00FF00FF) c -= 8;
+ if (x & 0x0F0F0F0F0F0F0F0F) c -= 4;
+ if (x & 0x3333333333333333) c -= 2;
+ if (x & 0x5555555555555555) c -= 1;
+ return c;
+#endif
+}
+
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
+CountTrailingZeroesNonzero16(uint16_t x) {
+#if ABSL_HAVE_BUILTIN(__builtin_ctzs)
+ static_assert(sizeof(unsigned short) == sizeof(x), // NOLINT(runtime/int)
+ "__builtin_ctzs does not take 16-bit arg");
+ return __builtin_ctzs(x);
+#else
+ return CountTrailingZeroesNonzero32(x);
+#endif
+}
+
+template <class T>
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
+CountTrailingZeroes(T x) noexcept {
+ static_assert(std::is_unsigned<T>::value, "T must be unsigned");
+ static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
+ "T must have a power-of-2 size");
+ static_assert(sizeof(T) <= sizeof(uint64_t), "T too large");
+ return x == 0 ? std::numeric_limits<T>::digits
+ : (sizeof(T) <= sizeof(uint16_t)
+ ? CountTrailingZeroesNonzero16(static_cast<uint16_t>(x))
+ : (sizeof(T) <= sizeof(uint32_t)
+ ? CountTrailingZeroesNonzero32(
+ static_cast<uint32_t>(x))
+ : CountTrailingZeroesNonzero64(x)));
+}
+
+// If T is narrower than unsigned, T{1} << bit_width will be promoted. We
+// want to force it to wraparound so that bit_ceil of an invalid value are not
+// core constant expressions.
+template <class T>
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline
+ typename std::enable_if<std::is_unsigned<T>::value, T>::type
+ BitCeilPromotionHelper(T x, T promotion) {
+ return (T{1} << (x + promotion)) >> promotion;
+}
+
+template <class T>
+ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline
+ typename std::enable_if<std::is_unsigned<T>::value, T>::type
+ BitCeilNonPowerOf2(T x) {
+ // If T is narrower than unsigned, it undergoes promotion to unsigned when we
+ // shift. We calcualte the number of bits added by the wider type.
+ return BitCeilPromotionHelper(
+ static_cast<T>(std::numeric_limits<T>::digits - CountLeadingZeroes(x)),
+ T{sizeof(T) >= sizeof(unsigned) ? 0
+ : std::numeric_limits<unsigned>::digits -
+ std::numeric_limits<T>::digits});
+}
+
+} // namespace numeric_internal
+ABSL_NAMESPACE_END
+} // namespace absl
+
+#endif // ABSL_NUMERIC_INTERNAL_BITS_H_