From b0f661181d10bddc08e380992590a1cdd92be92b Mon Sep 17 00:00:00 2001 From: Jisi Liu Date: Fri, 21 Aug 2015 11:18:45 -0700 Subject: Down-integrate from internal branch. Change-Id: Ieb7a2c2fbf35bc2a8fa65b915a5ecb68c83863e4 --- src/google/protobuf/stubs/common.cc | 63 ++- src/google/protobuf/stubs/common.h | 24 ++ src/google/protobuf/stubs/hash.h | 15 + src/google/protobuf/stubs/int128.cc | 200 +++++++++ src/google/protobuf/stubs/int128.h | 381 ++++++++++++++++++ src/google/protobuf/stubs/int128_unittest.cc | 513 ++++++++++++++++++++++++ src/google/protobuf/stubs/logging.h | 4 +- src/google/protobuf/stubs/port.h | 12 +- src/google/protobuf/stubs/structurally_valid.cc | 52 +++ 9 files changed, 1242 insertions(+), 22 deletions(-) create mode 100644 src/google/protobuf/stubs/int128.cc create mode 100644 src/google/protobuf/stubs/int128.h create mode 100644 src/google/protobuf/stubs/int128_unittest.cc (limited to 'src/google/protobuf/stubs') diff --git a/src/google/protobuf/stubs/common.cc b/src/google/protobuf/stubs/common.cc index d470fc72..54dbafab 100644 --- a/src/google/protobuf/stubs/common.cc +++ b/src/google/protobuf/stubs/common.cc @@ -35,8 +35,10 @@ #include #include #include -#include +#include #include +#include +#include #include #ifdef _WIN32 @@ -48,6 +50,9 @@ #else #error "No suitable threading library available." #endif +#if defined(__ANDROID__) +#include +#endif namespace google { namespace protobuf { @@ -104,7 +109,43 @@ string VersionString(int version) { // emulates google3/base/logging.cc namespace internal { +#if defined(__ANDROID__) +inline void DefaultLogHandler(LogLevel level, const char* filename, int line, + const string& message) { +#ifdef GOOGLE_PROTOBUF_MIN_LOG_LEVEL + if (level < GOOGLE_PROTOBUF_MIN_LOG_LEVEL) { + return; + } + static const char* level_names[] = {"INFO", "WARNING", "ERROR", "FATAL"}; + + static const int android_log_levels[] = { + ANDROID_LOG_INFO, // LOG(INFO), + ANDROID_LOG_WARN, // LOG(WARNING) + ANDROID_LOG_ERROR, // LOG(ERROR) + ANDROID_LOG_FATAL, // LOG(FATAL) + }; + // Bound the logging level. + const int android_log_level = android_log_levels[level]; + ::std::ostringstream ostr; + ostr << "[libprotobuf " << level_names[level] << " " << filename << ":" + << line << "] " << message.c_str(); + + // Output the log string the Android log at the appropriate level. + __android_log_write(android_log_level, "libprotobuf-native", + ostr.str().c_str()); + // Also output to std::cerr. + fprintf(stderr, "%s", ostr.str().c_str()); + fflush(stderr); + + // Indicate termination if needed. + if (android_log_level == ANDROID_LOG_FATAL) { + __android_log_write(ANDROID_LOG_FATAL, "libprotobuf-native", + "terminating.\n"); + } +#endif +} +#else void DefaultLogHandler(LogLevel level, const char* filename, int line, const string& message) { static const char* level_names[] = { "INFO", "WARNING", "ERROR", "FATAL" }; @@ -115,6 +156,7 @@ void DefaultLogHandler(LogLevel level, const char* filename, int line, level_names[level], filename, line, message.c_str()); fflush(stderr); // Needed on MSVC. } +#endif void NullLogHandler(LogLevel /* level */, const char* /* filename */, int /* line */, const string& /* message */) { @@ -154,22 +196,19 @@ LogMessage& LogMessage::operator<<(const StringPiece& value) { return *this; } -LogMessage& LogMessage::operator<<(long long value) { - message_ += SimpleItoa(value); - return *this; -} - -LogMessage& LogMessage::operator<<(unsigned long long value) { - message_ += SimpleItoa(value); - return *this; -} - LogMessage& LogMessage::operator<<( const ::google::protobuf::util::Status& status) { message_ += status.ToString(); return *this; } +LogMessage& LogMessage::operator<<(const uint128& value) { + std::ostringstream str; + str << value; + message_ += str.str(); + return *this; +} + // Since this is just for logging, we don't care if the current locale changes // the results -- in fact, we probably prefer that. So we use snprintf() // instead of Simple*toa(). @@ -194,6 +233,8 @@ DECLARE_STREAM_OPERATOR(long , "%ld") DECLARE_STREAM_OPERATOR(unsigned long, "%lu") DECLARE_STREAM_OPERATOR(double , "%g" ) DECLARE_STREAM_OPERATOR(void* , "%p" ) +DECLARE_STREAM_OPERATOR(long long , "%" GOOGLE_LL_FORMAT "d") +DECLARE_STREAM_OPERATOR(unsigned long long, "%" GOOGLE_LL_FORMAT "u") #undef DECLARE_STREAM_OPERATOR LogMessage::LogMessage(LogLevel level, const char* filename, int line) diff --git a/src/google/protobuf/stubs/common.h b/src/google/protobuf/stubs/common.h index de866e14..88e7084f 100644 --- a/src/google/protobuf/stubs/common.h +++ b/src/google/protobuf/stubs/common.h @@ -35,6 +35,7 @@ #ifndef GOOGLE_PROTOBUF_COMMON_H__ #define GOOGLE_PROTOBUF_COMMON_H__ +#include #include #include @@ -137,12 +138,35 @@ std::string LIBPROTOBUF_EXPORT VersionString(int version); // =================================================================== // from google3/util/utf8/public/unilib.h +class StringPiece; namespace internal { // Checks if the buffer contains structurally-valid UTF-8. Implemented in // structurally_valid.cc. LIBPROTOBUF_EXPORT bool IsStructurallyValidUTF8(const char* buf, int len); +inline bool IsStructurallyValidUTF8(const std::string& str) { + return IsStructurallyValidUTF8(str.data(), str.length()); +} + +// Returns initial number of bytes of structually valid UTF-8. +LIBPROTOBUF_EXPORT int UTF8SpnStructurallyValid(const StringPiece& str); + +// Coerce UTF-8 byte string in src_str to be +// a structurally-valid equal-length string by selectively +// overwriting illegal bytes with replace_char (typically ' ' or '?'). +// replace_char must be legal printable 7-bit Ascii 0x20..0x7e. +// src_str is read-only. +// +// Returns pointer to output buffer, src_str.data() if no changes were made, +// or idst if some bytes were changed. idst is allocated by the caller +// and must be at least as big as src_str +// +// Optimized for: all structurally valid and no byte copying is done. +// +LIBPROTOBUF_EXPORT char* UTF8CoerceToStructurallyValid( + const StringPiece& str, char* dst, char replace_char); + } // namespace internal diff --git a/src/google/protobuf/stubs/hash.h b/src/google/protobuf/stubs/hash.h index 9a6b217a..0d94ad80 100755 --- a/src/google/protobuf/stubs/hash.h +++ b/src/google/protobuf/stubs/hash.h @@ -143,6 +143,21 @@ # define GOOGLE_PROTOBUF_HASH_SET_CLASS unordered_set #endif +#ifndef GOOGLE_PROTOBUF_HASH_NAMESPACE +# define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_START +# define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END +#elif !defined(GOOGLE_PROTOBUF_HAS_CXX11_HASH) && \ + defined(GOOGLE_PROTOBUF_HAS_TR1) +# define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_START \ + namespace std { \ + namespace tr1 { +# define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END }} +#else +# define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_START \ + namespace GOOGLE_PROTOBUF_HASH_NAMESPACE { +# define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END } +#endif + #undef GOOGLE_PROTOBUF_HAS_CXX11_HASH #undef GOOGLE_PROTOBUF_HAS_TR1 diff --git a/src/google/protobuf/stubs/int128.cc b/src/google/protobuf/stubs/int128.cc new file mode 100644 index 00000000..9f4fb824 --- /dev/null +++ b/src/google/protobuf/stubs/int128.cc @@ -0,0 +1,200 @@ +// Protocol Buffers - Google's data interchange format +// Copyright 2008 Google Inc. All rights reserved. +// https://developers.google.com/protocol-buffers/ +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following disclaimer +// in the documentation and/or other materials provided with the +// distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include + +#include +#include // NOLINT(readability/streams) +#include + +namespace google { +namespace protobuf { + +const uint128_pod kuint128max = { + static_cast(GOOGLE_LONGLONG(0xFFFFFFFFFFFFFFFF)), + static_cast(GOOGLE_LONGLONG(0xFFFFFFFFFFFFFFFF)) +}; + +// Returns the 0-based position of the last set bit (i.e., most significant bit) +// in the given uint64. The argument may not be 0. +// +// For example: +// Given: 5 (decimal) == 101 (binary) +// Returns: 2 +#define STEP(T, n, pos, sh) \ + do { \ + if ((n) >= (static_cast(1) << (sh))) { \ + (n) = (n) >> (sh); \ + (pos) |= (sh); \ + } \ + } while (0) +static inline int Fls64(uint64 n) { + GOOGLE_DCHECK_NE(0, n); + int pos = 0; + STEP(uint64, n, pos, 0x20); + uint32 n32 = n; + STEP(uint32, n32, pos, 0x10); + STEP(uint32, n32, pos, 0x08); + STEP(uint32, n32, pos, 0x04); + return pos + ((GOOGLE_ULONGLONG(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) { + if (uint64 hi = Uint128High64(n)) { + return Fls64(hi) + 64; + } + return Fls64(Uint128Low64(n)); +} + +// Long division/modulo for uint128 implemented using the shift-subtract +// division algorithm adapted from: +// http://stackoverflow.com/questions/5386377/division-without-using +void uint128::DivModImpl(uint128 dividend, uint128 divisor, + uint128* quotient_ret, uint128* remainder_ret) { + if (divisor == 0) { + GOOGLE_LOG(FATAL) << "Division or mod by zero: dividend.hi=" << dividend.hi_ + << ", lo=" << dividend.lo_; + } + + if (divisor > dividend) { + *quotient_ret = 0; + *remainder_ret = dividend; + return; + } + + if (divisor == dividend) { + *quotient_ret = 1; + *remainder_ret = 0; + return; + } + + uint128 denominator = divisor; + uint128 position = 1; + uint128 quotient = 0; + + // Left aligns the MSB of the denominator and the dividend. + int shift = Fls128(dividend) - Fls128(denominator); + denominator <<= shift; + position <<= shift; + + // Uses shift-subtract algorithm to divide dividend by denominator. The + // remainder will be left in dividend. + while (position > 0) { + if (dividend >= denominator) { + dividend -= denominator; + quotient |= position; + } + position >>= 1; + denominator >>= 1; + } + + *quotient_ret = quotient; + *remainder_ret = dividend; +} + +uint128& uint128::operator/=(const uint128& divisor) { + uint128 quotient = 0; + uint128 remainder = 0; + DivModImpl(*this, divisor, "ient, &remainder); + *this = quotient; + return *this; +} +uint128& uint128::operator%=(const uint128& divisor) { + uint128 quotient = 0; + uint128 remainder = 0; + DivModImpl(*this, divisor, "ient, &remainder); + *this = remainder; + return *this; +} + +std::ostream& operator<<(std::ostream& o, const uint128& b) { + std::ios_base::fmtflags flags = o.flags(); + + // Select a divisor which is the largest power of the base < 2^64. + uint128 div; + std::streamsize div_base_log; + switch (flags & std::ios::basefield) { + case std::ios::hex: + div = GOOGLE_ULONGLONG(0x1000000000000000); // 16^15 + div_base_log = 15; + break; + case std::ios::oct: + div = GOOGLE_ULONGLONG(01000000000000000000000); // 8^21 + div_base_log = 21; + break; + default: // std::ios::dec + div = GOOGLE_ULONGLONG(10000000000000000000); // 10^19 + div_base_log = 19; + break; + } + + // Now piece together the uint128 representation from three chunks of + // the original value, each less than "div" and therefore representable + // as a uint64. + std::ostringstream os; + std::ios_base::fmtflags copy_mask = + std::ios::basefield | std::ios::showbase | std::ios::uppercase; + os.setf(flags & copy_mask, copy_mask); + uint128 high = b; + uint128 low; + uint128::DivModImpl(high, div, &high, &low); + uint128 mid; + uint128::DivModImpl(high, div, &high, &mid); + if (high.lo_ != 0) { + os << high.lo_; + os << std::noshowbase << std::setfill('0') << std::setw(div_base_log); + os << mid.lo_; + os << std::setw(div_base_log); + } else if (mid.lo_ != 0) { + os << mid.lo_; + os << std::noshowbase << std::setfill('0') << std::setw(div_base_log); + } + os << low.lo_; + std::string rep = os.str(); + + // Add the requisite padding. + std::streamsize width = o.width(0); + if (width > rep.size()) { + if ((flags & std::ios::adjustfield) == std::ios::left) { + rep.append(width - rep.size(), o.fill()); + } else { + rep.insert(0, width - rep.size(), o.fill()); + } + } + + // Stream the final representation in a single "<<" call. + return o << rep; +} + +} // namespace protobuf +} // namespace google diff --git a/src/google/protobuf/stubs/int128.h b/src/google/protobuf/stubs/int128.h new file mode 100644 index 00000000..1e63037f --- /dev/null +++ b/src/google/protobuf/stubs/int128.h @@ -0,0 +1,381 @@ +// Protocol Buffers - Google's data interchange format +// Copyright 2008 Google Inc. All rights reserved. +// https://developers.google.com/protocol-buffers/ +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following disclaimer +// in the documentation and/or other materials provided with the +// distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#ifndef GOOGLE_PROTOBUF_STUBS_INT128_H_ +#define GOOGLE_PROTOBUF_STUBS_INT128_H_ + +#include + +#include + +namespace google { +namespace protobuf { + +struct uint128_pod; + +// TODO(xiaofeng): Define GOOGLE_PROTOBUF_HAS_CONSTEXPR when constexpr is +// available. +#ifdef GOOGLE_PROTOBUF_HAS_CONSTEXPR +# define UINT128_CONSTEXPR constexpr +#else +# define UINT128_CONSTEXPR +#endif + +// An unsigned 128-bit integer type. Thread-compatible. +class uint128 { + public: + UINT128_CONSTEXPR uint128(); // Sets to 0, but don't trust on this behavior. + UINT128_CONSTEXPR uint128(uint64 top, uint64 bottom); +#ifndef SWIG + UINT128_CONSTEXPR uint128(int bottom); + UINT128_CONSTEXPR uint128(uint32 bottom); // Top 96 bits = 0 +#endif + UINT128_CONSTEXPR uint128(uint64 bottom); // hi_ = 0 + UINT128_CONSTEXPR uint128(const uint128_pod &val); + + // Trivial copy constructor, assignment operator and destructor. + + void Initialize(uint64 top, uint64 bottom); + + // Arithmetic operators. + uint128& operator+=(const uint128& b); + uint128& operator-=(const uint128& b); + uint128& operator*=(const uint128& b); + // Long division/modulo for uint128. + uint128& operator/=(const uint128& b); + uint128& operator%=(const uint128& b); + uint128 operator++(int); + uint128 operator--(int); + uint128& operator<<=(int); + uint128& operator>>=(int); + uint128& operator&=(const uint128& b); + uint128& operator|=(const uint128& b); + uint128& operator^=(const uint128& b); + uint128& operator++(); + uint128& operator--(); + + friend uint64 Uint128Low64(const uint128& v); + friend uint64 Uint128High64(const uint128& v); + + // We add "std::" to avoid including all of port.h. + friend std::ostream& operator<<(std::ostream& o, const uint128& b); + + private: + static void DivModImpl(uint128 dividend, uint128 divisor, + uint128* quotient_ret, uint128* remainder_ret); + + // Little-endian memory order optimizations can benefit from + // having lo_ first, hi_ last. + // See util/endian/endian.h and Load128/Store128 for storing a uint128. + uint64 lo_; + uint64 hi_; + + // Not implemented, just declared for catching automatic type conversions. + uint128(uint8); + uint128(uint16); + uint128(float v); + uint128(double v); +}; + +// This is a POD form of uint128 which can be used for static variables which +// need to be operated on as uint128. +struct uint128_pod { + // Note: The ordering of fields is different than 'class uint128' but the + // same as its 2-arg constructor. This enables more obvious initialization + // of static instances, which is the primary reason for this struct in the + // first place. This does not seem to defeat any optimizations wrt + // operations involving this struct. + uint64 hi; + uint64 lo; +}; + +extern const uint128_pod kuint128max; + +// allow uint128 to be logged +extern std::ostream& operator<<(std::ostream& o, const uint128& b); + +// Methods to access low and high pieces of 128-bit value. +// Defined externally from uint128 to facilitate conversion +// to native 128-bit types when compilers support them. +inline uint64 Uint128Low64(const uint128& v) { return v.lo_; } +inline uint64 Uint128High64(const uint128& v) { return v.hi_; } + +// TODO: perhaps it would be nice to have int128, a signed 128-bit type? + +// -------------------------------------------------------------------------- +// Implementation details follow +// -------------------------------------------------------------------------- +inline bool operator==(const uint128& lhs, const uint128& rhs) { + return (Uint128Low64(lhs) == Uint128Low64(rhs) && + Uint128High64(lhs) == Uint128High64(rhs)); +} +inline bool operator!=(const uint128& lhs, const uint128& rhs) { + return !(lhs == rhs); +} + +inline UINT128_CONSTEXPR uint128::uint128() : lo_(0), hi_(0) {} +inline UINT128_CONSTEXPR uint128::uint128(uint64 top, uint64 bottom) + : lo_(bottom), hi_(top) {} +inline UINT128_CONSTEXPR uint128::uint128(const uint128_pod& v) + : lo_(v.lo), hi_(v.hi) {} +inline UINT128_CONSTEXPR uint128::uint128(uint64 bottom) + : lo_(bottom), hi_(0) {} +#ifndef SWIG +inline UINT128_CONSTEXPR uint128::uint128(uint32 bottom) + : lo_(bottom), hi_(0) {} +inline UINT128_CONSTEXPR uint128::uint128(int bottom) + : lo_(bottom), hi_(static_cast((bottom < 0) ? -1 : 0)) {} +#endif + +#undef UINT128_CONSTEXPR + +inline void uint128::Initialize(uint64 top, uint64 bottom) { + hi_ = top; + lo_ = bottom; +} + +// Comparison operators. + +#define CMP128(op) \ +inline bool operator op(const uint128& lhs, const uint128& rhs) { \ + return (Uint128High64(lhs) == Uint128High64(rhs)) ? \ + (Uint128Low64(lhs) op Uint128Low64(rhs)) : \ + (Uint128High64(lhs) op Uint128High64(rhs)); \ +} + +CMP128(<) +CMP128(>) +CMP128(>=) +CMP128(<=) + +#undef CMP128 + +// Unary operators + +inline uint128 operator-(const uint128& val) { + const uint64 hi_flip = ~Uint128High64(val); + const uint64 lo_flip = ~Uint128Low64(val); + const uint64 lo_add = lo_flip + 1; + if (lo_add < lo_flip) { + return uint128(hi_flip + 1, lo_add); + } + return uint128(hi_flip, lo_add); +} + +inline bool operator!(const uint128& val) { + return !Uint128High64(val) && !Uint128Low64(val); +} + +// Logical operators. + +inline uint128 operator~(const uint128& val) { + return uint128(~Uint128High64(val), ~Uint128Low64(val)); +} + +#define LOGIC128(op) \ +inline uint128 operator op(const uint128& lhs, const uint128& rhs) { \ + return uint128(Uint128High64(lhs) op Uint128High64(rhs), \ + Uint128Low64(lhs) op Uint128Low64(rhs)); \ +} + +LOGIC128(|) +LOGIC128(&) +LOGIC128(^) + +#undef LOGIC128 + +#define LOGICASSIGN128(op) \ +inline uint128& uint128::operator op(const uint128& other) { \ + hi_ op other.hi_; \ + lo_ op other.lo_; \ + return *this; \ +} + +LOGICASSIGN128(|=) +LOGICASSIGN128(&=) +LOGICASSIGN128(^=) + +#undef LOGICASSIGN128 + +// Shift operators. + +inline uint128 operator<<(const uint128& val, int amount) { + // uint64 shifts of >= 64 are undefined, so we will need some special-casing. + if (amount < 64) { + if (amount == 0) { + return val; + } + uint64 new_hi = (Uint128High64(val) << amount) | + (Uint128Low64(val) >> (64 - amount)); + uint64 new_lo = Uint128Low64(val) << amount; + return uint128(new_hi, new_lo); + } else if (amount < 128) { + return uint128(Uint128Low64(val) << (amount - 64), 0); + } else { + return uint128(0, 0); + } +} + +inline uint128 operator>>(const uint128& val, int amount) { + // uint64 shifts of >= 64 are undefined, so we will need some special-casing. + if (amount < 64) { + if (amount == 0) { + return val; + } + uint64 new_hi = Uint128High64(val) >> amount; + uint64 new_lo = (Uint128Low64(val) >> amount) | + (Uint128High64(val) << (64 - amount)); + return uint128(new_hi, new_lo); + } else if (amount < 128) { + return uint128(0, Uint128High64(val) >> (amount - 64)); + } else { + return uint128(0, 0); + } +} + +inline uint128& uint128::operator<<=(int amount) { + // uint64 shifts of >= 64 are undefined, so we will need some special-casing. + if (amount < 64) { + if (amount != 0) { + hi_ = (hi_ << amount) | (lo_ >> (64 - amount)); + lo_ = lo_ << amount; + } + } else if (amount < 128) { + hi_ = lo_ << (amount - 64); + lo_ = 0; + } else { + hi_ = 0; + lo_ = 0; + } + return *this; +} + +inline uint128& uint128::operator>>=(int amount) { + // uint64 shifts of >= 64 are undefined, so we will need some special-casing. + if (amount < 64) { + if (amount != 0) { + lo_ = (lo_ >> amount) | (hi_ << (64 - amount)); + hi_ = hi_ >> amount; + } + } else if (amount < 128) { + lo_ = hi_ >> (amount - 64); + hi_ = 0; + } else { + lo_ = 0; + hi_ = 0; + } + return *this; +} + +inline uint128 operator+(const uint128& lhs, const uint128& rhs) { + return uint128(lhs) += rhs; +} + +inline uint128 operator-(const uint128& lhs, const uint128& rhs) { + return uint128(lhs) -= rhs; +} + +inline uint128 operator*(const uint128& lhs, const uint128& rhs) { + return uint128(lhs) *= rhs; +} + +inline uint128 operator/(const uint128& lhs, const uint128& rhs) { + return uint128(lhs) /= rhs; +} + +inline uint128 operator%(const uint128& lhs, const uint128& rhs) { + return uint128(lhs) %= rhs; +} + +inline uint128& uint128::operator+=(const uint128& b) { + hi_ += b.hi_; + uint64 lolo = lo_ + b.lo_; + if (lolo < lo_) + ++hi_; + lo_ = lolo; + return *this; +} + +inline uint128& uint128::operator-=(const uint128& b) { + hi_ -= b.hi_; + if (b.lo_ > lo_) + --hi_; + lo_ -= b.lo_; + return *this; +} + +inline uint128& uint128::operator*=(const uint128& b) { + uint64 a96 = hi_ >> 32; + uint64 a64 = hi_ & 0xffffffffu; + uint64 a32 = lo_ >> 32; + uint64 a00 = lo_ & 0xffffffffu; + uint64 b96 = b.hi_ >> 32; + uint64 b64 = b.hi_ & 0xffffffffu; + uint64 b32 = b.lo_ >> 32; + uint64 b00 = b.lo_ & 0xffffffffu; + // multiply [a96 .. a00] x [b96 .. b00] + // terms higher than c96 disappear off the high side + // terms c96 and c64 are safe to ignore carry bit + uint64 c96 = a96 * b00 + a64 * b32 + a32 * b64 + a00 * b96; + uint64 c64 = a64 * b00 + a32 * b32 + a00 * b64; + this->hi_ = (c96 << 32) + c64; + this->lo_ = 0; + // add terms after this one at a time to capture carry + *this += uint128(a32 * b00) << 32; + *this += uint128(a00 * b32) << 32; + *this += a00 * b00; + return *this; +} + +inline uint128 uint128::operator++(int) { + uint128 tmp(*this); + *this += 1; + return tmp; +} + +inline uint128 uint128::operator--(int) { + uint128 tmp(*this); + *this -= 1; + return tmp; +} + +inline uint128& uint128::operator++() { + *this += 1; + return *this; +} + +inline uint128& uint128::operator--() { + *this -= 1; + return *this; +} + +} // namespace protobuf +} // namespace google + +#endif // GOOGLE_PROTOBUF_STUBS_INT128_H_ diff --git a/src/google/protobuf/stubs/int128_unittest.cc b/src/google/protobuf/stubs/int128_unittest.cc new file mode 100644 index 00000000..5d33292c --- /dev/null +++ b/src/google/protobuf/stubs/int128_unittest.cc @@ -0,0 +1,513 @@ +// Protocol Buffers - Google's data interchange format +// Copyright 2008 Google Inc. All rights reserved. +// https://developers.google.com/protocol-buffers/ +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following disclaimer +// in the documentation and/or other materials provided with the +// distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include + +#include +#include +#include + +#include +#include + +namespace google { +namespace protobuf { + +TEST(Int128, AllTests) { + uint128 zero(0); + uint128 one(1); + uint128 one_2arg(0, 1); + uint128 two(0, 2); + uint128 three(0, 3); + uint128 big(2000, 2); + uint128 big_minus_one(2000, 1); + uint128 bigger(2001, 1); + uint128 biggest(kuint128max); + uint128 high_low(1, 0); + uint128 low_high(0, kuint64max); + EXPECT_LT(one, two); + EXPECT_GT(two, one); + EXPECT_LT(one, big); + EXPECT_LT(one, big); + EXPECT_EQ(one, one_2arg); + EXPECT_NE(one, two); + EXPECT_GT(big, one); + EXPECT_GE(big, two); + EXPECT_GE(big, big_minus_one); + EXPECT_GT(big, big_minus_one); + EXPECT_LT(big_minus_one, big); + EXPECT_LE(big_minus_one, big); + EXPECT_NE(big_minus_one, big); + EXPECT_LT(big, biggest); + EXPECT_LE(big, biggest); + EXPECT_GT(biggest, big); + EXPECT_GE(biggest, big); + EXPECT_EQ(big, ~~big); + EXPECT_EQ(one, one | one); + EXPECT_EQ(big, big | big); + EXPECT_EQ(one, one | zero); + EXPECT_EQ(one, one & one); + EXPECT_EQ(big, big & big); + EXPECT_EQ(zero, one & zero); + EXPECT_EQ(zero, big & ~big); + EXPECT_EQ(zero, one ^ one); + EXPECT_EQ(zero, big ^ big); + EXPECT_EQ(one, one ^ zero); + + // Shift operators. + EXPECT_EQ(big, big << 0); + EXPECT_EQ(big, big >> 0); + EXPECT_GT(big << 1, big); + EXPECT_LT(big >> 1, big); + EXPECT_EQ(big, (big << 10) >> 10); + EXPECT_EQ(big, (big >> 1) << 1); + EXPECT_EQ(one, (one << 80) >> 80); + EXPECT_EQ(zero, (one >> 80) << 80); + EXPECT_EQ(zero, big >> 128); + EXPECT_EQ(zero, big << 128); + + // Shift assignments. + uint128 big_copy = big; + EXPECT_EQ(big << 0, big_copy <<= 0); + big_copy = big; + EXPECT_EQ(big >> 0, big_copy >>= 0); + big_copy = big; + EXPECT_EQ(big << 1, big_copy <<= 1); + big_copy = big; + EXPECT_EQ(big >> 1, big_copy >>= 1); + big_copy = big; + EXPECT_EQ(big << 10, big_copy <<= 10); + big_copy = big; + EXPECT_EQ(big >> 10, big_copy >>= 10); + big_copy = big; + EXPECT_EQ(big << 64, big_copy <<= 64); + big_copy = big; + EXPECT_EQ(big >> 64, big_copy >>= 64); + big_copy = big; + EXPECT_EQ(big << 73, big_copy <<= 73); + big_copy = big; + EXPECT_EQ(big >> 73, big_copy >>= 73); + big_copy = big; + EXPECT_EQ(big << 128, big_copy <<= 128); + big_copy = big; + EXPECT_EQ(big >> 128, big_copy >>= 128); + + EXPECT_EQ(Uint128High64(biggest), kuint64max); + EXPECT_EQ(Uint128Low64(biggest), kuint64max); + EXPECT_EQ(zero + one, one); + EXPECT_EQ(one + one, two); + EXPECT_EQ(big_minus_one + one, big); + EXPECT_EQ(one - one, zero); + EXPECT_EQ(one - zero, one); + EXPECT_EQ(zero - one, biggest); + EXPECT_EQ(big - big, zero); + EXPECT_EQ(big - one, big_minus_one); + EXPECT_EQ(big + kuint64max, bigger); + EXPECT_EQ(biggest + 1, zero); + EXPECT_EQ(zero - 1, biggest); + EXPECT_EQ(high_low - one, low_high); + EXPECT_EQ(low_high + one, high_low); + EXPECT_EQ(Uint128High64((uint128(1) << 64) - 1), 0); + EXPECT_EQ(Uint128Low64((uint128(1) << 64) - 1), kuint64max); + EXPECT_TRUE(!!one); + EXPECT_TRUE(!!high_low); + EXPECT_FALSE(!!zero); + EXPECT_FALSE(!one); + EXPECT_FALSE(!high_low); + EXPECT_TRUE(!zero); + EXPECT_TRUE(zero == 0); + EXPECT_FALSE(zero != 0); + EXPECT_FALSE(one == 0); + EXPECT_TRUE(one != 0); + + uint128 test = zero; + EXPECT_EQ(++test, one); + EXPECT_EQ(test, one); + EXPECT_EQ(test++, one); + EXPECT_EQ(test, two); + EXPECT_EQ(test -= 2, zero); + EXPECT_EQ(test, zero); + EXPECT_EQ(test += 2, two); + EXPECT_EQ(test, two); + EXPECT_EQ(--test, one); + EXPECT_EQ(test, one); + EXPECT_EQ(test--, one); + EXPECT_EQ(test, zero); + EXPECT_EQ(test |= three, three); + EXPECT_EQ(test &= one, one); + EXPECT_EQ(test ^= three, two); + EXPECT_EQ(test >>= 1, one); + EXPECT_EQ(test <<= 1, two); + + EXPECT_EQ(big, -(-big)); + EXPECT_EQ(two, -((-one) - 1)); + EXPECT_EQ(kuint128max, -one); + EXPECT_EQ(zero, -zero); + + GOOGLE_LOG(INFO) << one; + GOOGLE_LOG(INFO) << big_minus_one; +} + +TEST(Int128, PodTests) { + uint128_pod pod = { 12345, 67890 }; + uint128 from_pod(pod); + EXPECT_EQ(12345, Uint128High64(from_pod)); + EXPECT_EQ(67890, Uint128Low64(from_pod)); + + uint128 zero(0); + uint128_pod zero_pod = {0, 0}; + uint128 one(1); + uint128_pod one_pod = {0, 1}; + uint128 two(2); + uint128_pod two_pod = {0, 2}; + uint128 three(3); + uint128_pod three_pod = {0, 3}; + uint128 big(1, 0); + uint128_pod big_pod = {1, 0}; + + EXPECT_EQ(zero, zero_pod); + EXPECT_EQ(zero_pod, zero); + EXPECT_EQ(zero_pod, zero_pod); + EXPECT_EQ(one, one_pod); + EXPECT_EQ(one_pod, one); + EXPECT_EQ(one_pod, one_pod); + EXPECT_EQ(two, two_pod); + EXPECT_EQ(two_pod, two); + EXPECT_EQ(two_pod, two_pod); + + EXPECT_NE(one, two_pod); + EXPECT_NE(one_pod, two); + EXPECT_NE(one_pod, two_pod); + + EXPECT_LT(one, two_pod); + EXPECT_LT(one_pod, two); + EXPECT_LT(one_pod, two_pod); + EXPECT_LE(one, one_pod); + EXPECT_LE(one_pod, one); + EXPECT_LE(one_pod, one_pod); + EXPECT_LE(one, two_pod); + EXPECT_LE(one_pod, two); + EXPECT_LE(one_pod, two_pod); + + EXPECT_GT(two, one_pod); + EXPECT_GT(two_pod, one); + EXPECT_GT(two_pod, one_pod); + EXPECT_GE(two, two_pod); + EXPECT_GE(two_pod, two); + EXPECT_GE(two_pod, two_pod); + EXPECT_GE(two, one_pod); + EXPECT_GE(two_pod, one); + EXPECT_GE(two_pod, one_pod); + + EXPECT_EQ(three, one | two_pod); + EXPECT_EQ(three, one_pod | two); + EXPECT_EQ(three, one_pod | two_pod); + EXPECT_EQ(one, three & one_pod); + EXPECT_EQ(one, three_pod & one); + EXPECT_EQ(one, three_pod & one_pod); + EXPECT_EQ(two, three ^ one_pod); + EXPECT_EQ(two, three_pod ^ one); + EXPECT_EQ(two, three_pod ^ one_pod); + EXPECT_EQ(two, three & (~one)); + EXPECT_EQ(three, ~~three); + + EXPECT_EQ(two, two_pod << 0); + EXPECT_EQ(two, one_pod << 1); + EXPECT_EQ(big, one_pod << 64); + EXPECT_EQ(zero, one_pod << 128); + EXPECT_EQ(two, two_pod >> 0); + EXPECT_EQ(one, two_pod >> 1); + EXPECT_EQ(one, big_pod >> 64); + + EXPECT_EQ(one, zero + one_pod); + EXPECT_EQ(one, zero_pod + one); + EXPECT_EQ(one, zero_pod + one_pod); + EXPECT_EQ(one, two - one_pod); + EXPECT_EQ(one, two_pod - one); + EXPECT_EQ(one, two_pod - one_pod); +} + +TEST(Int128, OperatorAssignReturnRef) { + uint128 v(1); + (v += 4) -= 3; + EXPECT_EQ(2, v); +} + +TEST(Int128, Multiply) { + uint128 a, b, c; + + // Zero test. + a = 0; + b = 0; + c = a * b; + EXPECT_EQ(0, c); + + // Max carries. + a = uint128(0) - 1; + b = uint128(0) - 1; + c = a * b; + EXPECT_EQ(1, c); + + // Self-operation with max carries. + c = uint128(0) - 1; + c *= c; + EXPECT_EQ(1, c); + + // 1-bit x 1-bit. + for (int i = 0; i < 64; ++i) { + for (int j = 0; j < 64; ++j) { + a = uint128(1) << i; + b = uint128(1) << j; + c = a * b; + EXPECT_EQ(uint128(1) << (i+j), c); + } + } + + // Verified with dc. + a = uint128(GOOGLE_ULONGLONG(0xffffeeeeddddcccc), + GOOGLE_ULONGLONG(0xbbbbaaaa99998888)); + b = uint128(GOOGLE_ULONGLONG(0x7777666655554444), + GOOGLE_ULONGLONG(0x3333222211110000)); + c = a * b; + EXPECT_EQ(uint128(GOOGLE_ULONGLONG(0x530EDA741C71D4C3), + GOOGLE_ULONGLONG(0xBF25975319080000)), c); + EXPECT_EQ(0, c - b * a); + EXPECT_EQ(a*a - b*b, (a+b) * (a-b)); + + // Verified with dc. + a = uint128(GOOGLE_ULONGLONG(0x0123456789abcdef), + GOOGLE_ULONGLONG(0xfedcba9876543210)); + b = uint128(GOOGLE_ULONGLONG(0x02468ace13579bdf), + GOOGLE_ULONGLONG(0xfdb97531eca86420)); + c = a * b; + EXPECT_EQ(uint128(GOOGLE_ULONGLONG(0x97a87f4f261ba3f2), + GOOGLE_ULONGLONG(0x342d0bbf48948200)), c); + EXPECT_EQ(0, c - b * a); + EXPECT_EQ(a*a - b*b, (a+b) * (a-b)); +} + +TEST(Int128, AliasTests) { + uint128 x1(1, 2); + uint128 x2(2, 4); + x1 += x1; + EXPECT_EQ(x2, x1); + + uint128 x3(1, static_cast(1) << 63); + uint128 x4(3, 0); + x3 += x3; + EXPECT_EQ(x4, x3); +} + +#ifdef PROTOBUF_HAS_DEATH_TEST +TEST(Int128, DivideByZeroCheckFails) { + uint128 a = 0; + uint128 b = 0; + EXPECT_DEATH(a / b, "Division or mod by zero:"); + a = 123; + EXPECT_DEATH(a / b, "Division or mod by zero:"); +} + +TEST(Int128, ModByZeroCheckFails) { + uint128 a = 0; + uint128 b = 0; + EXPECT_DEATH(a % b, "Division or mod by zero:"); + a = 123; + EXPECT_DEATH(a % b, "Division or mod by zero:"); +} +#endif // PROTOBUF_HAS_DEATH_TEST + +TEST(Int128, DivideAndMod) { + // a := q * b + r + uint128 a, b, q, r; + + // Zero test. + a = 0; + b = 123; + q = a / b; + r = a % b; + EXPECT_EQ(0, q); + EXPECT_EQ(0, r); + + a = uint128(GOOGLE_ULONGLONG(0x530eda741c71d4c3), + GOOGLE_ULONGLONG(0xbf25975319080000)); + q = uint128(GOOGLE_ULONGLONG(0x4de2cab081), + GOOGLE_ULONGLONG(0x14c34ab4676e4bab)); + b = uint128(0x1110001); + r = uint128(0x3eb455); + ASSERT_EQ(a, q * b + r); // Sanity-check. + + uint128 result_q, result_r; + result_q = a / b; + result_r = a % b; + EXPECT_EQ(q, result_q); + EXPECT_EQ(r, result_r); + + // Try the other way around. + swap(q, b); + result_q = a / b; + result_r = a % b; + EXPECT_EQ(q, result_q); + EXPECT_EQ(r, result_r); + // Restore. + swap(b, q); + + // Dividend < divisor; result should be q:0 r:. + swap(a, b); + result_q = a / b; + result_r = a % b; + EXPECT_EQ(0, result_q); + EXPECT_EQ(a, result_r); + // Try the other way around. + swap(a, q); + result_q = a / b; + result_r = a % b; + EXPECT_EQ(0, result_q); + EXPECT_EQ(a, result_r); + // Restore. + swap(q, a); + swap(b, a); + + // Try a large remainder. + b = a / 2 + 1; + uint128 expected_r(GOOGLE_ULONGLONG(0x29876d3a0e38ea61), + GOOGLE_ULONGLONG(0xdf92cba98c83ffff)); + // Sanity checks. + ASSERT_EQ(a / 2 - 1, expected_r); + ASSERT_EQ(a, b + expected_r); + result_q = a / b; + result_r = a % b; + EXPECT_EQ(1, result_q); + EXPECT_EQ(expected_r, result_r); +} + +static uint64 RandomUint64() { + uint64 v1 = rand(); + uint64 v2 = rand(); + uint64 v3 = rand(); + return v1 * v2 + v3; +} + +TEST(Int128, DivideAndModRandomInputs) { + const int kNumIters = 1 << 18; + for (int i = 0; i < kNumIters; ++i) { + const uint128 a(RandomUint64(), RandomUint64()); + const uint128 b(RandomUint64(), RandomUint64()); + if (b == 0) { + continue; // Avoid a div-by-zero. + } + const uint128 q = a / b; + const uint128 r = a % b; + ASSERT_EQ(a, b * q + r); + } +} + +#ifdef GOOGLE_PROTOBUF_HAS_CONSTEXPR +TEST(Int128, ConstexprTest) { + constexpr uint128 zero; + constexpr uint128 one = 1; + constexpr uint128_pod pod = {2, 3}; + constexpr uint128 from_pod = pod; + constexpr uint128 minus_two = -2; + EXPECT_EQ(one, uint128(1)); + EXPECT_EQ(from_pod, uint128(2, 3)); + EXPECT_EQ(minus_two, uint128(-1ULL, -2ULL)); +} + +TEST(Int128, Traits) { + EXPECT_TRUE(std::is_trivially_copy_constructible::value); + EXPECT_TRUE(std::is_trivially_copy_assignable::value); + EXPECT_TRUE(std::is_trivially_destructible::value); +} +#endif // GOOGLE_PROTOBUF_HAS_CONSTEXPR + +TEST(Int128, OStream) { + struct { + uint128 val; + std::ios_base::fmtflags flags; + std::streamsize width; + char fill; + const char* rep; + } cases[] = { + // zero with different bases + {uint128(0), std::ios::dec, 0, '_', "0"}, + {uint128(0), std::ios::oct, 0, '_', "0"}, + {uint128(0), std::ios::hex, 0, '_', "0"}, + // crossover between lo_ and hi_ + {uint128(0, -1), std::ios::dec, 0, '_', "18446744073709551615"}, + {uint128(0, -1), std::ios::oct, 0, '_', "1777777777777777777777"}, + {uint128(0, -1), std::ios::hex, 0, '_', "ffffffffffffffff"}, + {uint128(1, 0), std::ios::dec, 0, '_', "18446744073709551616"}, + {uint128(1, 0), std::ios::oct, 0, '_', "2000000000000000000000"}, + {uint128(1, 0), std::ios::hex, 0, '_', "10000000000000000"}, + // just the top bit + {uint128(GOOGLE_ULONGLONG(0x8000000000000000), 0), std::ios::dec, 0, '_', + "170141183460469231731687303715884105728"}, + {uint128(GOOGLE_ULONGLONG(0x8000000000000000), 0), std::ios::oct, 0, '_', + "2000000000000000000000000000000000000000000"}, + {uint128(GOOGLE_ULONGLONG(0x8000000000000000), 0), std::ios::hex, 0, '_', + "80000000000000000000000000000000"}, + // maximum uint128 value + {uint128(-1, -1), std::ios::dec, 0, '_', + "340282366920938463463374607431768211455"}, + {uint128(-1, -1), std::ios::oct, 0, '_', + "3777777777777777777777777777777777777777777"}, + {uint128(-1, -1), std::ios::hex, 0, '_', + "ffffffffffffffffffffffffffffffff"}, + // uppercase + {uint128(-1, -1), std::ios::hex | std::ios::uppercase, 0, '_', + "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"}, + // showbase + {uint128(1), std::ios::dec | std::ios::showbase, 0, '_', "1"}, + {uint128(1), std::ios::oct | std::ios::showbase, 0, '_', "01"}, + {uint128(1), std::ios::hex | std::ios::showbase, 0, '_', "0x1"}, + // showbase does nothing on zero + {uint128(0), std::ios::dec | std::ios::showbase, 0, '_', "0"}, + {uint128(0), std::ios::oct | std::ios::showbase, 0, '_', "0"}, + {uint128(0), std::ios::hex | std::ios::showbase, 0, '_', "0"}, + // showpos does nothing on unsigned types + {uint128(1), std::ios::dec | std::ios::showpos, 0, '_', "1"}, + // padding + {uint128(9), std::ios::dec, 6, '_', "_____9"}, + {uint128(12345), std::ios::dec, 6, '_', "_12345"}, + // left adjustment + {uint128(9), std::ios::dec | std::ios::left, 6, '_', "9_____"}, + {uint128(12345), std::ios::dec | std::ios::left, 6, '_', "12345_"}, + }; + for (size_t i = 0; i < GOOGLE_ARRAYSIZE(cases); ++i) { + ostringstream os; + os.flags(cases[i].flags); + os.width(cases[i].width); + os.fill(cases[i].fill); + os << cases[i].val; + EXPECT_EQ(cases[i].rep, os.str()); + } +} +} // namespace protobuf +} // namespace google diff --git a/src/google/protobuf/stubs/logging.h b/src/google/protobuf/stubs/logging.h index 330d33d2..3108db8c 100644 --- a/src/google/protobuf/stubs/logging.h +++ b/src/google/protobuf/stubs/logging.h @@ -65,6 +65,7 @@ class StringPiece; namespace util { class Status; } +class uint128; namespace internal { class LogFinisher; @@ -78,7 +79,7 @@ class LIBPROTOBUF_EXPORT LogMessage { LogMessage& operator<<(const char* value); LogMessage& operator<<(char value); LogMessage& operator<<(int value); - LogMessage& operator<<(unsigned int value); + LogMessage& operator<<(uint value); LogMessage& operator<<(long value); LogMessage& operator<<(unsigned long value); LogMessage& operator<<(long long value); @@ -87,6 +88,7 @@ class LIBPROTOBUF_EXPORT LogMessage { LogMessage& operator<<(void* value); LogMessage& operator<<(const StringPiece& value); LogMessage& operator<<(const ::google::protobuf::util::Status& status); + LogMessage& operator<<(const uint128& value); private: friend class LogFinisher; diff --git a/src/google/protobuf/stubs/port.h b/src/google/protobuf/stubs/port.h index c86cf35b..7d84b92f 100644 --- a/src/google/protobuf/stubs/port.h +++ b/src/google/protobuf/stubs/port.h @@ -100,20 +100,12 @@ typedef unsigned __int64 uint64; typedef signed char int8; typedef short int16; typedef int int32; -// NOTE: This should be "long long" for consistency with upstream, but -// something is stacked against this particular type for 64bit hashing. -// Switching it causes an obvious missing hash function (with an unobvious -// cause) when building the tests. -typedef int64_t int64; +typedef long long int64; typedef unsigned char uint8; typedef unsigned short uint16; typedef unsigned int uint32; -// NOTE: This should be "unsigned long long" for consistency with upstream, but -// something is stacked against this particular type for 64bit hashing. -// Switching it causes an obvious missing hash function (with an unobvious -// cause) when building the tests. -typedef uint64_t uint64; +typedef unsigned long long uint64; #endif // long long macros to be used because gcc and vc++ use different suffixes, diff --git a/src/google/protobuf/stubs/structurally_valid.cc b/src/google/protobuf/stubs/structurally_valid.cc index 0f6afe6d..d79a6ee4 100644 --- a/src/google/protobuf/stubs/structurally_valid.cc +++ b/src/google/protobuf/stubs/structurally_valid.cc @@ -3,6 +3,8 @@ #include +#include + namespace google { namespace protobuf { namespace internal { @@ -531,6 +533,56 @@ bool IsStructurallyValidUTF8(const char* buf, int len) { return (bytes_consumed == len); } +int UTF8SpnStructurallyValid(const StringPiece& str) { + if (!module_initialized_) return str.size(); + + int bytes_consumed = 0; + UTF8GenericScanFastAscii(&utf8acceptnonsurrogates_obj, + str.data(), str.size(), &bytes_consumed); + return bytes_consumed; +} + +// Coerce UTF-8 byte string in src_str to be +// a structurally-valid equal-length string by selectively +// overwriting illegal bytes with replace_char (typically blank). +// replace_char must be legal printable 7-bit Ascii 0x20..0x7e. +// src_str is read-only. If any overwriting is needed, a modified byte string +// is created in idst, length isrclen. +// +// Returns pointer to output buffer, isrc if no changes were made, +// or idst if some bytes were changed. +// +// Fast case: all is structurally valid and no byte copying is done. +// +char* UTF8CoerceToStructurallyValid(const StringPiece& src_str, + char* idst, + const char replace_char) { + const char* isrc = src_str.data(); + const int len = src_str.length(); + int n = UTF8SpnStructurallyValid(src_str); + if (n == len) { // Normal case -- all is cool, return + return const_cast(isrc); + } else { // Unusual case -- copy w/o bad bytes + const char* src = isrc; + const char* srclimit = isrc + len; + char* dst = idst; + memmove(dst, src, n); // Copy initial good chunk + src += n; + dst += n; + while (src < srclimit) { // src points to bogus byte or is off the end + dst[0] = replace_char; // replace one bad byte + src++; + dst++; + StringPiece str2(src, srclimit - src); + n = UTF8SpnStructurallyValid(str2); // scan the remainder + memmove(dst, src, n); // copy next good chunk + src += n; + dst += n; + } + } + return idst; +} + } // namespace internal } // namespace protobuf } // namespace google -- cgit v1.2.3