From 04dd99d8c1813ded74cd2a9c90ecb7eaa2d68ab1 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Mon, 14 May 2018 13:41:38 -0700 Subject: - abe587c2360b21f085b7d65a77d840015bc04cf6 Factor an internal interface into its own header, as it w... by Greg Falcon - 2201f1644336e64280dbd20207d8fbc3bfea2bf4 Internal change. by Abseil Team - 94e6b5b20d2cc754c99a18c575a4f1f3cd1f28d4 Rename no_throw_ctor to nothrow_ctor to match the standar... by Abseil Team - 86aa34d2129c4914c5133b7b619480aae786288e Update header files in debugging target by Tom Manshreck - ed234519ced458724a7267b8fdf184eaae1c97c7 Remove CMAKE_CXX_WARNING_VLA from our c++ flags in the cm... by Jon Cohen GitOrigin-RevId: abe587c2360b21f085b7d65a77d840015bc04cf6 Change-Id: I92f9301c69419d3830c358b88984967185aa33f6 --- absl/strings/BUILD.bazel | 1 + absl/strings/CMakeLists.txt | 1 + absl/strings/internal/bits.h | 53 ++++++++++++++++++++++++++++++++++++++++++++ absl/strings/numbers.cc | 17 +++----------- 4 files changed, 58 insertions(+), 14 deletions(-) create mode 100644 absl/strings/internal/bits.h (limited to 'absl/strings') diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 13badb7b9c25..1e52312b47c6 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -84,6 +84,7 @@ 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 83cb934dba9d..9dc47328c731 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -31,6 +31,7 @@ list(APPEND STRINGS_PUBLIC_HEADERS list(APPEND STRINGS_INTERNAL_HEADERS + "internal/bits.h" "internal/char_map.h" "internal/memutil.h" "internal/ostringstream.h" diff --git a/absl/strings/internal/bits.h b/absl/strings/internal/bits.h new file mode 100644 index 000000000000..901082ccddfc --- /dev/null +++ b/absl/strings/internal/bits.h @@ -0,0 +1,53 @@ +// 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 + +#if defined(_MSC_VER) && defined(_M_X64) +#include +#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 b4140b3605bc..68ef7999a981 100644 --- a/absl/strings/numbers.cc +++ b/absl/strings/numbers.cc @@ -32,6 +32,7 @@ #include "absl/base/internal/raw_logging.h" #include "absl/strings/ascii.h" +#include "absl/strings/internal/bits.h" #include "absl/strings/internal/memutil.h" #include "absl/strings/str_cat.h" @@ -302,18 +303,6 @@ char* numbers_internal::FastIntToBuffer(int64_t i, char* buffer) { return numbers_internal::FastIntToBuffer(u, buffer); } -// Returns the number of leading 0 bits in a 64-bit value. -// TODO(jorg): Replace with builtin_clzll if available. -// Are we shipping util/bits in absl? -static inline int CountLeadingZeros64(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\0"[n] + zeroes; -} - // Given a 128-bit number expressed as a pair of uint64_t, high half first, // return that number multiplied by the given 32-bit value. If the result is // too large to fit in a 128-bit number, divide it by 2 until it fits. @@ -351,7 +340,7 @@ static std::pair Mul32(std::pair num, uint64_t bits128_up = (bits96_127 >> 32) + (bits64_127 < bits64_95); if (bits128_up == 0) return {bits64_127, bits0_63}; - int shift = 64 - CountLeadingZeros64(bits128_up); + int shift = 64 - strings_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}; @@ -382,7 +371,7 @@ static std::pair 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 = CountLeadingZeros64(result.first); + int shift = strings_internal::CountLeadingZeros64(result.first); if (shift != 0) { result.first = (result.first << shift) + (result.second >> (64 - shift)); result.second = (result.second << shift); -- cgit 1.4.1