diff options
| -rw-r--r-- | absl/base/BUILD.bazel | 20 | ||||
| -rw-r--r-- | absl/base/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | absl/base/internal/bits.h | 193 | ||||
| -rw-r--r-- | absl/base/internal/bits_test.cc | 97 | ||||
| -rw-r--r-- | absl/strings/BUILD.bazel | 2 | ||||
| -rw-r--r-- | absl/strings/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | absl/strings/charconv.cc | 8 | ||||
| -rw-r--r-- | absl/strings/escaping.cc | 2 | ||||
| -rw-r--r-- | absl/strings/internal/bits.h | 53 | ||||
| -rw-r--r-- | absl/strings/numbers.cc | 6 | ||||
| -rw-r--r-- | absl/time/time.h | 31 |
11 files changed, 345 insertions, 69 deletions
diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel index 7063f96a4589..83d48f6b20a0 100644 --- a/absl/base/BUILD.bazel +++ b/absl/base/BUILD.bazel @@ -427,3 +427,23 @@ cc_test( "@com_github_google_benchmark//:benchmark_main", ], ) + +cc_library( + name = "bits", + hdrs = ["internal/bits.h"], + visibility = [ + "//absl:__subpackages__", + ], + deps = [":core_headers"], +) + +cc_test( + name = "bits_test", + size = "small", + srcs = ["internal/bits_test.cc"], + copts = ABSL_TEST_COPTS, + deps = [ + ":bits", + "@com_google_googletest//:gtest_main", + ], +) diff --git a/absl/base/CMakeLists.txt b/absl/base/CMakeLists.txt index 01d2af085f58..04a6eb31955b 100644 --- a/absl/base/CMakeLists.txt +++ b/absl/base/CMakeLists.txt @@ -31,6 +31,7 @@ list(APPEND BASE_PUBLIC_HEADERS list(APPEND BASE_INTERNAL_HEADERS "internal/atomic_hook.h" + "internal/bits.h" "internal/cycleclock.h" "internal/direct_mmap.h" "internal/endian.h" diff --git a/absl/base/internal/bits.h b/absl/base/internal/bits.h new file mode 100644 index 000000000000..bc7faaee3b25 --- /dev/null +++ b/absl/base/internal/bits.h @@ -0,0 +1,193 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://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_BASE_INTERNAL_BITS_H_ +#define ABSL_BASE_INTERNAL_BITS_H_ + +// This file contains bitwise ops which are implementation details of various +// absl libraries. + +#include <cstdint> + +// Clang on Windows has __builtin_clzll; otherwise we need to use the +// windows intrinsic functions. +#if defined(_MSC_VER) +#include <intrin.h> +#if defined(_M_X64) +#pragma intrinsic(_BitScanReverse64) +#pragma intrinsic(_BitScanForward64) +#endif +#pragma intrinsic(_BitScanReverse) +#pragma intrinsic(_BitScanForward) +#endif + +#include "absl/base/attributes.h" + +#if defined(_MSC_VER) +// We can achieve something similar to attribute((always_inline)) with MSVC by +// using the __forceinline keyword, however this is not perfect. MSVC is +// much less aggressive about inlining, and even with the __forceinline keyword. +#define ABSL_BASE_INTERNAL_FORCEINLINE __forceinline +#else +// Use default attribute inline. +#define ABSL_BASE_INTERNAL_FORCEINLINE inline ABSL_ATTRIBUTE_ALWAYS_INLINE +#endif + + +namespace absl { +namespace base_internal { + +ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros64Slow(uint64_t n) { + int zeroes = 60; + if (n >> 32) zeroes -= 32, n >>= 32; + if (n >> 16) zeroes -= 16, n >>= 16; + if (n >> 8) zeroes -= 8, n >>= 8; + if (n >> 4) zeroes -= 4, n >>= 4; + return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[n] + zeroes; +} + +ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros64(uint64_t n) { +#if defined(_MSC_VER) && defined(_M_X64) + // MSVC does not have __buitin_clzll. Use _BitScanReverse64. + unsigned long result = 0; // NOLINT(runtime/int) + if (_BitScanReverse64(&result, n)) { + return 63 - result; + } + return 64; +#elif defined(_MSC_VER) + // MSVC does not have __buitin_clzll. Compose two calls to _BitScanReverse + unsigned long result = 0; // NOLINT(runtime/int) + if ((n >> 32) && _BitScanReverse(&result, n >> 32)) { + return 31 - result; + } + if (_BitScanReverse(&result, n)) { + return 63 - result; + } + return 64; +#elif defined(__GNUC__) + // Use __builtin_clzll, which uses the following instructions: + // x86: bsr + // ARM64: clz + // PPC: cntlzd + static_assert(sizeof(unsigned long long) == sizeof(n), // NOLINT(runtime/int) + "__builtin_clzll does not take 64-bit arg"); + + // Handle 0 as a special case because __builtin_clzll(0) is undefined. + if (n == 0) { + return 64; + } + return __builtin_clzll(n); +#else + return CountLeadingZeros64Slow(n); +#endif +} + +ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros32Slow(uint64_t n) { + int zeroes = 28; + if (n >> 16) zeroes -= 16, n >>= 16; + if (n >> 8) zeroes -= 8, n >>= 8; + if (n >> 4) zeroes -= 4, n >>= 4; + return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[n] + zeroes; +} + +ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros32(uint32_t n) { +#if defined(_MSC_VER) + unsigned long result = 0; // NOLINT(runtime/int) + if (_BitScanReverse(&result, n)) { + return 31 - result; + } + return 32; +#elif defined(__GNUC__) + // Use __builtin_clz, which uses the following instructions: + // x86: bsr + // ARM64: clz + // PPC: cntlzd + static_assert(sizeof(int) == sizeof(n), + "__builtin_clz does not take 32-bit arg"); + + // Handle 0 as a special case because __builtin_clz(0) is undefined. + if (n == 0) { + return 32; + } + return __builtin_clz(n); +#else + return CountLeadingZeros32Slow(n); +#endif +} + +ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero64Slow(uint64_t n) { + int c = 63; + n &= ~n + 1; + if (n & 0x00000000FFFFFFFF) c -= 32; + if (n & 0x0000FFFF0000FFFF) c -= 16; + if (n & 0x00FF00FF00FF00FF) c -= 8; + if (n & 0x0F0F0F0F0F0F0F0F) c -= 4; + if (n & 0x3333333333333333) c -= 2; + if (n & 0x5555555555555555) c -= 1; + return c; +} + +ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero64(uint64_t n) { +#if defined(_MSC_VER) && defined(_M_X64) + unsigned long result = 0; // NOLINT(runtime/int) + _BitScanForward64(&result, n); + return result; +#elif defined(_MSC_VER) + unsigned long result = 0; // NOLINT(runtime/int) + if (static_cast<uint32_t>(n) == 0) { + _BitScanForward(&result, n >> 32); + return result + 32; + } + _BitScanForward(&result, n); + return result; +#elif defined(__GNUC__) + static_assert(sizeof(unsigned long long) == sizeof(n), // NOLINT(runtime/int) + "__builtin_ctzll does not take 64-bit arg"); + return __builtin_ctzll(n); +#else + return CountTrailingZerosNonZero64Slow(n); +#endif +} + +ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero32Slow(uint32_t n) { + int c = 31; + n &= ~n + 1; + if (n & 0x0000FFFF) c -= 16; + if (n & 0x00FF00FF) c -= 8; + if (n & 0x0F0F0F0F) c -= 4; + if (n & 0x33333333) c -= 2; + if (n & 0x55555555) c -= 1; + return c; +} + +ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero32(uint32_t n) { +#if defined(_MSC_VER) + unsigned long result = 0; // NOLINT(runtime/int) + _BitScanForward(&result, n); + return result; +#elif defined(__GNUC__) + static_assert(sizeof(int) == sizeof(n), + "__builtin_ctz does not take 32-bit arg"); + return __builtin_ctz(n); +#else + return CountTrailingZerosNonZero32Slow(n); +#endif +} + +#undef ABSL_BASE_INTERNAL_FORCEINLINE + +} // namespace base_internal +} // namespace absl + +#endif // ABSL_BASE_INTERNAL_BITS_H_ diff --git a/absl/base/internal/bits_test.cc b/absl/base/internal/bits_test.cc new file mode 100644 index 000000000000..e5d991d67258 --- /dev/null +++ b/absl/base/internal/bits_test.cc @@ -0,0 +1,97 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://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/base/internal/bits.h" + +#include "gtest/gtest.h" + +namespace { + +int CLZ64(uint64_t n) { + int fast = absl::base_internal::CountLeadingZeros64(n); + int slow = absl::base_internal::CountLeadingZeros64Slow(n); + EXPECT_EQ(fast, slow) << n; + return fast; +} + +TEST(BitsTest, CountLeadingZeros64) { + EXPECT_EQ(64, CLZ64(uint64_t{})); + EXPECT_EQ(0, CLZ64(~uint64_t{})); + + for (int index = 0; index < 64; index++) { + uint64_t x = static_cast<uint64_t>(1) << index; + const auto cnt = 63 - index; + ASSERT_EQ(cnt, CLZ64(x)) << index; + ASSERT_EQ(cnt, CLZ64(x + x - 1)) << index; + } +} + +int CLZ32(uint32_t n) { + int fast = absl::base_internal::CountLeadingZeros32(n); + int slow = absl::base_internal::CountLeadingZeros32Slow(n); + EXPECT_EQ(fast, slow) << n; + return fast; +} + +TEST(BitsTest, CountLeadingZeros32) { + EXPECT_EQ(32, CLZ32(uint32_t{})); + EXPECT_EQ(0, CLZ32(~uint32_t{})); + + for (int index = 0; index < 32; index++) { + uint32_t x = static_cast<uint32_t>(1) << index; + const auto cnt = 31 - index; + ASSERT_EQ(cnt, CLZ32(x)) << index; + ASSERT_EQ(cnt, CLZ32(x + x - 1)) << index; + ASSERT_EQ(CLZ64(x), CLZ32(x) + 32); + } +} + +int CTZ64(uint64_t n) { + int fast = absl::base_internal::CountTrailingZerosNonZero64(n); + int slow = absl::base_internal::CountTrailingZerosNonZero64Slow(n); + EXPECT_EQ(fast, slow) << n; + return fast; +} + +TEST(BitsTest, CountTrailingZerosNonZero64) { + EXPECT_EQ(0, CTZ64(~uint64_t{})); + + for (int index = 0; index < 64; index++) { + uint64_t x = static_cast<uint64_t>(1) << index; + const auto cnt = index; + ASSERT_EQ(cnt, CTZ64(x)) << index; + ASSERT_EQ(cnt, CTZ64(~(x - 1))) << index; + } +} + +int CTZ32(uint32_t n) { + int fast = absl::base_internal::CountTrailingZerosNonZero32(n); + int slow = absl::base_internal::CountTrailingZerosNonZero32Slow(n); + EXPECT_EQ(fast, slow) << n; + return fast; +} + +TEST(BitsTest, CountTrailingZerosNonZero32) { + EXPECT_EQ(0, CTZ32(~uint32_t{})); + + for (int index = 0; index < 32; index++) { + uint32_t x = static_cast<uint32_t>(1) << index; + const auto cnt = index; + ASSERT_EQ(cnt, CTZ32(x)) << index; + ASSERT_EQ(cnt, CTZ32(~(x - 1))) << index; + } +} + + +} // namespace diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 0cb752b59392..6d7c2619a530 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -70,6 +70,7 @@ cc_library( deps = [ ":internal", "//absl/base", + "//absl/base:bits", "//absl/base:config", "//absl/base:core_headers", "//absl/base:endian", @@ -87,7 +88,6 @@ cc_library( "internal/utf8.cc", ], hdrs = [ - "internal/bits.h", "internal/char_map.h", "internal/ostringstream.h", "internal/resize_uninitialized.h", diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index cd122134729f..f3e4162387f1 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -32,7 +32,6 @@ list(APPEND STRINGS_PUBLIC_HEADERS list(APPEND STRINGS_INTERNAL_HEADERS - "internal/bits.h" "internal/char_map.h" "internal/charconv_bigint.h" "internal/charconv_parse.h" diff --git a/absl/strings/charconv.cc b/absl/strings/charconv.cc index 08c3947eccd4..c7b8c98b1b44 100644 --- a/absl/strings/charconv.cc +++ b/absl/strings/charconv.cc @@ -20,8 +20,8 @@ #include <cstring> #include "absl/base/casts.h" +#include "absl/base/internal/bits.h" #include "absl/numeric/int128.h" -#include "absl/strings/internal/bits.h" #include "absl/strings/internal/charconv_bigint.h" #include "absl/strings/internal/charconv_parse.h" @@ -243,9 +243,9 @@ struct CalculatedFloat { // minus the number of leading zero bits.) int BitWidth(uint128 value) { if (Uint128High64(value) == 0) { - return 64 - strings_internal::CountLeadingZeros64(Uint128Low64(value)); + return 64 - base_internal::CountLeadingZeros64(Uint128Low64(value)); } - return 128 - strings_internal::CountLeadingZeros64(Uint128High64(value)); + return 128 - base_internal::CountLeadingZeros64(Uint128High64(value)); } // Calculates how far to the right a mantissa needs to be shifted to create a @@ -518,7 +518,7 @@ CalculatedFloat CalculateFromParsedHexadecimal( const strings_internal::ParsedFloat& parsed_hex) { uint64_t mantissa = parsed_hex.mantissa; int exponent = parsed_hex.exponent; - int mantissa_width = 64 - strings_internal::CountLeadingZeros64(mantissa); + int mantissa_width = 64 - base_internal::CountLeadingZeros64(mantissa); const int shift = NormalizedShiftSize<FloatType>(mantissa_width, exponent); bool result_exact; exponent += shift; diff --git a/absl/strings/escaping.cc b/absl/strings/escaping.cc index c8f18d860798..4a45942daf3e 100644 --- a/absl/strings/escaping.cc +++ b/absl/strings/escaping.cc @@ -304,7 +304,7 @@ bool CUnescapeInternal(absl::string_view source, bool leave_nulls_escaped, ptrdiff_t dest_size; if (!CUnescapeInternal(source, leave_nulls_escaped, - const_cast<char*>(dest->data()), + &(*dest)[0], &dest_size, error)) { return false; diff --git a/absl/strings/internal/bits.h b/absl/strings/internal/bits.h deleted file mode 100644 index 901082ccddfc..000000000000 --- a/absl/strings/internal/bits.h +++ /dev/null @@ -1,53 +0,0 @@ -// Copyright 2018 The Abseil Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://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_STRINGS_INTERNAL_BITS_H_ -#define ABSL_STRINGS_INTERNAL_BITS_H_ - -#include <cstdint> - -#if defined(_MSC_VER) && defined(_M_X64) -#include <intrin.h> -#pragma intrinsic(_BitScanReverse64) -#endif - -namespace absl { -namespace strings_internal { - -// Returns the number of leading 0 bits in a 64-bit value. -inline int CountLeadingZeros64(uint64_t n) { -#if defined(__GNUC__) - static_assert(sizeof(unsigned long long) == sizeof(n), // NOLINT(runtime/int) - "__builtin_clzll does not take 64bit arg"); - return n == 0 ? 64 : __builtin_clzll(n); -#elif defined(_MSC_VER) && defined(_M_X64) - unsigned long result; // NOLINT(runtime/int) - if (_BitScanReverse64(&result, n)) { - return 63 - result; - } - return 64; -#else - int zeroes = 60; - if (n >> 32) zeroes -= 32, n >>= 32; - if (n >> 16) zeroes -= 16, n >>= 16; - if (n >> 8) zeroes -= 8, n >>= 8; - if (n >> 4) zeroes -= 4, n >>= 4; - return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0\0"[n] + zeroes; -#endif -} - -} // namespace strings_internal -} // namespace absl - -#endif // ABSL_STRINGS_INTERNAL_BITS_H_ diff --git a/absl/strings/numbers.cc b/absl/strings/numbers.cc index cc878f5b0016..9309f9da9dcc 100644 --- a/absl/strings/numbers.cc +++ b/absl/strings/numbers.cc @@ -30,10 +30,10 @@ #include <memory> #include <utility> +#include "absl/base/internal/bits.h" #include "absl/base/internal/raw_logging.h" #include "absl/strings/ascii.h" #include "absl/strings/charconv.h" -#include "absl/strings/internal/bits.h" #include "absl/strings/internal/memutil.h" #include "absl/strings/str_cat.h" @@ -344,7 +344,7 @@ static std::pair<uint64_t, uint64_t> Mul32(std::pair<uint64_t, uint64_t> num, uint64_t bits128_up = (bits96_127 >> 32) + (bits64_127 < bits64_95); if (bits128_up == 0) return {bits64_127, bits0_63}; - int shift = 64 - strings_internal::CountLeadingZeros64(bits128_up); + int shift = 64 - base_internal::CountLeadingZeros64(bits128_up); uint64_t lo = (bits0_63 >> shift) + (bits64_127 << (64 - shift)); uint64_t hi = (bits64_127 >> shift) + (bits128_up << (64 - shift)); return {hi, lo}; @@ -375,7 +375,7 @@ static std::pair<uint64_t, uint64_t> PowFive(uint64_t num, int expfive) { 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5, 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5}; result = Mul32(result, powers_of_five[expfive & 15]); - int shift = strings_internal::CountLeadingZeros64(result.first); + int shift = base_internal::CountLeadingZeros64(result.first); if (shift != 0) { result.first = (result.first << shift) + (result.second >> (64 - shift)); result.second = (result.second << shift); diff --git a/absl/time/time.h b/absl/time/time.h index d29d7e9a2061..f2a779f4edfa 100644 --- a/absl/time/time.h +++ b/absl/time/time.h @@ -25,11 +25,22 @@ // * `absl::TimeZone` defines geopolitical time zone regions (as collected // within the IANA Time Zone database (https://www.iana.org/time-zones)). // +// Note: Absolute times are distinct from civil times, which refer to the +// human-scale time commonly represented by `YYYY-MM-DD hh:mm:ss`. The mapping +// between absolute and civil times can be specified by use of time zones +// (`absl::TimeZone` within this API). That is: +// +// Civil Time = F(Absolute Time, Time Zone) +// Absolute Time = F(Civil Time, Time Zone) +// +// See civil_time.h for abstractions related to constructing and manipulating +// civil time. +// // Example: // // absl::TimeZone nyc; // -// // LoadTimeZone may fail so it's always better to check for success. +// // LoadTimeZone() may fail so it's always better to check for success. // if (!absl::LoadTimeZone("America/New_York", &nyc)) { // // handle error case // } @@ -496,7 +507,7 @@ inline std::ostream& operator<<(std::ostream& os, Duration d) { // decimal numbers, each with an optional fractional part and a unit // suffix. The valid suffixes are "ns", "us" "ms", "s", "m", and "h". // Simple examples include "300ms", "-1.5h", and "2h45m". Parses "0" as -// `ZeroDuration()`. Parses "inf" and "-inf" as +/- `InfiniteDuration()`. +// `ZeroDuration()`. Parses "inf" and "-inf" as +/- `InfiniteDuration()`. bool ParseDuration(const std::string& dur_string, Duration* d); // Support for flag values of type Duration. Duration flags must be specified @@ -689,7 +700,9 @@ constexpr Time InfinitePast() { // Examples: // // absl::TimeZone lax; -// if (!absl::LoadTimeZone("America/Los_Angeles", &lax)) { ... } +// if (!absl::LoadTimeZone("America/Los_Angeles", &lax)) { +// // handle error case +// } // // // A unique civil time // absl::TimeConversion jan01 = @@ -759,7 +772,9 @@ TimeConversion ConvertDateTime(int64_t year, int mon, int day, int hour, // Example: // // absl::TimeZone seattle; -// if (!absl::LoadTimeZone("America/Los_Angeles", &seattle)) { ... } +// if (!absl::LoadTimeZone("America/Los_Angeles", &seattle)) { +// // handle error case +// } // absl::Time t = absl::FromDateTime(2017, 9, 26, 9, 30, 0, seattle); Time FromDateTime(int64_t year, int mon, int day, int hour, int min, int sec, TimeZone tz); @@ -910,7 +925,9 @@ extern const char RFC1123_no_wday[]; // %d %b %E4Y %H:%M:%S %z // Example: // // absl::TimeZone lax; -// if (!absl::LoadTimeZone("America/Los_Angeles", &lax)) { ... } +// if (!absl::LoadTimeZone("America/Los_Angeles", &lax)) { +// // handle error case +// } // absl::Time t = absl::FromDateTime(2013, 1, 2, 3, 4, 5, lax); // // string f = absl::FormatTime("%H:%M:%S", t, lax); // "03:04:05" @@ -1028,7 +1045,9 @@ std::string UnparseFlag(Time t); // absl::TimeZone pst = absl::FixedTimeZone(-8 * 60 * 60); // absl::TimeZone loc = absl::LocalTimeZone(); // absl::TimeZone lax; -// if (!absl::LoadTimeZone("America/Los_Angeles", &lax)) { ... } +// if (!absl::LoadTimeZone("America/Los_Angeles", &lax)) { +// // handle error case +// } // // See also: // - https://github.com/google/cctz |