1 // Protocol Buffers - Google's data interchange format 2 // Copyright 2008 Google Inc. All rights reserved. 3 // https://developers.google.com/protocol-buffers/ 4 // 5 // Redistribution and use in source and binary forms, with or without 6 // modification, are permitted provided that the following conditions are 7 // met: 8 // 9 // * Redistributions of source code must retain the above copyright 10 // notice, this list of conditions and the following disclaimer. 11 // * Redistributions in binary form must reproduce the above 12 // copyright notice, this list of conditions and the following disclaimer 13 // in the documentation and/or other materials provided with the 14 // distribution. 15 // * Neither the name of Google Inc. nor the names of its 16 // contributors may be used to endorse or promote products derived from 17 // this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31 #include <google/protobuf/stubs/int128.h> 32 33 #include <iomanip> 34 #include <ostream> // NOLINT(readability/streams) 35 #include <sstream> 36 37 namespace google { 38 namespace protobuf { 39 40 const uint128_pod kuint128max = { 41 static_cast<uint64>(GOOGLE_LONGLONG(0xFFFFFFFFFFFFFFFF)), 42 static_cast<uint64>(GOOGLE_LONGLONG(0xFFFFFFFFFFFFFFFF)) 43 }; 44 45 // Returns the 0-based position of the last set bit (i.e., most significant bit) 46 // in the given uint64. The argument may not be 0. 47 // 48 // For example: 49 // Given: 5 (decimal) == 101 (binary) 50 // Returns: 2 51 #define STEP(T, n, pos, sh) \ 52 do { \ 53 if ((n) >= (static_cast<T>(1) << (sh))) { \ 54 (n) = (n) >> (sh); \ 55 (pos) |= (sh); \ 56 } \ 57 } while (0) 58 static inline int Fls64(uint64 n) { 59 GOOGLE_DCHECK_NE(0, n); 60 int pos = 0; 61 STEP(uint64, n, pos, 0x20); 62 uint32 n32 = n; 63 STEP(uint32, n32, pos, 0x10); 64 STEP(uint32, n32, pos, 0x08); 65 STEP(uint32, n32, pos, 0x04); 66 return pos + ((GOOGLE_ULONGLONG(0x3333333322221100) >> (n32 << 2)) & 0x3); 67 } 68 #undef STEP 69 70 // Like Fls64() above, but returns the 0-based position of the last set bit 71 // (i.e., most significant bit) in the given uint128. The argument may not be 0. 72 static inline int Fls128(uint128 n) { 73 if (uint64 hi = Uint128High64(n)) { 74 return Fls64(hi) + 64; 75 } 76 return Fls64(Uint128Low64(n)); 77 } 78 79 // Long division/modulo for uint128 implemented using the shift-subtract 80 // division algorithm adapted from: 81 // http://stackoverflow.com/questions/5386377/division-without-using 82 void uint128::DivModImpl(uint128 dividend, uint128 divisor, 83 uint128* quotient_ret, uint128* remainder_ret) { 84 if (divisor == 0) { 85 GOOGLE_LOG(FATAL) << "Division or mod by zero: dividend.hi=" << dividend.hi_ 86 << ", lo=" << dividend.lo_; 87 } 88 89 if (divisor > dividend) { 90 *quotient_ret = 0; 91 *remainder_ret = dividend; 92 return; 93 } 94 95 if (divisor == dividend) { 96 *quotient_ret = 1; 97 *remainder_ret = 0; 98 return; 99 } 100 101 uint128 denominator = divisor; 102 uint128 position = 1; 103 uint128 quotient = 0; 104 105 // Left aligns the MSB of the denominator and the dividend. 106 int shift = Fls128(dividend) - Fls128(denominator); 107 denominator <<= shift; 108 position <<= shift; 109 110 // Uses shift-subtract algorithm to divide dividend by denominator. The 111 // remainder will be left in dividend. 112 while (position > 0) { 113 if (dividend >= denominator) { 114 dividend -= denominator; 115 quotient |= position; 116 } 117 position >>= 1; 118 denominator >>= 1; 119 } 120 121 *quotient_ret = quotient; 122 *remainder_ret = dividend; 123 } 124 125 uint128& uint128::operator/=(const uint128& divisor) { 126 uint128 quotient = 0; 127 uint128 remainder = 0; 128 DivModImpl(*this, divisor, "ient, &remainder); 129 *this = quotient; 130 return *this; 131 } 132 uint128& uint128::operator%=(const uint128& divisor) { 133 uint128 quotient = 0; 134 uint128 remainder = 0; 135 DivModImpl(*this, divisor, "ient, &remainder); 136 *this = remainder; 137 return *this; 138 } 139 140 std::ostream& operator<<(std::ostream& o, const uint128& b) { 141 std::ios_base::fmtflags flags = o.flags(); 142 143 // Select a divisor which is the largest power of the base < 2^64. 144 uint128 div; 145 std::streamsize div_base_log; 146 switch (flags & std::ios::basefield) { 147 case std::ios::hex: 148 div = GOOGLE_ULONGLONG(0x1000000000000000); // 16^15 149 div_base_log = 15; 150 break; 151 case std::ios::oct: 152 div = GOOGLE_ULONGLONG(01000000000000000000000); // 8^21 153 div_base_log = 21; 154 break; 155 default: // std::ios::dec 156 div = GOOGLE_ULONGLONG(10000000000000000000); // 10^19 157 div_base_log = 19; 158 break; 159 } 160 161 // Now piece together the uint128 representation from three chunks of 162 // the original value, each less than "div" and therefore representable 163 // as a uint64. 164 std::ostringstream os; 165 std::ios_base::fmtflags copy_mask = 166 std::ios::basefield | std::ios::showbase | std::ios::uppercase; 167 os.setf(flags & copy_mask, copy_mask); 168 uint128 high = b; 169 uint128 low; 170 uint128::DivModImpl(high, div, &high, &low); 171 uint128 mid; 172 uint128::DivModImpl(high, div, &high, &mid); 173 if (high.lo_ != 0) { 174 os << high.lo_; 175 os << std::noshowbase << std::setfill('0') << std::setw(div_base_log); 176 os << mid.lo_; 177 os << std::setw(div_base_log); 178 } else if (mid.lo_ != 0) { 179 os << mid.lo_; 180 os << std::noshowbase << std::setfill('0') << std::setw(div_base_log); 181 } 182 os << low.lo_; 183 std::string rep = os.str(); 184 185 // Add the requisite padding. 186 std::streamsize width = o.width(0); 187 if (width > rep.size()) { 188 if ((flags & std::ios::adjustfield) == std::ios::left) { 189 rep.append(width - rep.size(), o.fill()); 190 } else { 191 rep.insert(static_cast<std::string::size_type>(0), 192 width - rep.size(), o.fill()); 193 } 194 } 195 196 // Stream the final representation in a single "<<" call. 197 return o << rep; 198 } 199 200 } // namespace protobuf 201 } // namespace google 202
