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 #include <google/protobuf/stubs/logging.h>
38
39 #include <google/protobuf/port_def.inc>
40
41 namespace google {
42 namespace protobuf {
43
44 const uint128_pod kuint128max = {uint64_t{0xFFFFFFFFFFFFFFFFu},
45 uint64_t{0xFFFFFFFFFFFFFFFFu}};
46
47 // Returns the 0-based position of the last set bit (i.e., most significant bit)
48 // in the given uint64. The argument may not be 0.
49 //
50 // For example:
51 // Given: 5 (decimal) == 101 (binary)
52 // Returns: 2
53 #define STEP(T, n, pos, sh) \
54 do { \
55 if ((n) >= (static_cast<T>(1) << (sh))) { \
56 (n) = (n) >> (sh); \
57 (pos) |= (sh); \
58 } \
59 } while (0)
Fls64(uint64_t n)60 static inline int Fls64(uint64_t n) {
61 GOOGLE_DCHECK_NE(0, n);
62 int pos = 0;
63 STEP(uint64_t, n, pos, 0x20);
64 uint32_t n32 = n;
65 STEP(uint32_t, n32, pos, 0x10);
66 STEP(uint32_t, n32, pos, 0x08);
67 STEP(uint32_t, n32, pos, 0x04);
68 return pos + ((uint64_t{0x3333333322221100u} >> (n32 << 2)) & 0x3);
69 }
70 #undef STEP
71
72 // Like Fls64() above, but returns the 0-based position of the last set bit
73 // (i.e., most significant bit) in the given uint128. The argument may not be 0.
Fls128(uint128 n)74 static inline int Fls128(uint128 n) {
75 if (uint64_t hi = Uint128High64(n)) {
76 return Fls64(hi) + 64;
77 }
78 return Fls64(Uint128Low64(n));
79 }
80
DivModImpl(uint128 dividend,uint128 divisor,uint128 * quotient_ret,uint128 * remainder_ret)81 void uint128::DivModImpl(uint128 dividend, uint128 divisor,
82 uint128* quotient_ret, uint128* remainder_ret) {
83 if (divisor == 0) {
84 GOOGLE_LOG(FATAL) << "Division or mod by zero: dividend.hi=" << dividend.hi_
85 << ", lo=" << dividend.lo_;
86 } else if (dividend < divisor) {
87 *quotient_ret = 0;
88 *remainder_ret = dividend;
89 return;
90 } else {
91 int dividend_bit_length = Fls128(dividend);
92 int divisor_bit_length = Fls128(divisor);
93 int difference = dividend_bit_length - divisor_bit_length;
94 uint128 quotient = 0;
95 while (difference >= 0) {
96 quotient <<= 1;
97 uint128 shifted_divisor = divisor << difference;
98 if (shifted_divisor <= dividend) {
99 dividend -= shifted_divisor;
100 quotient += 1;
101 }
102 difference -= 1;
103 }
104 //record the final quotient and remainder
105 *quotient_ret = quotient;
106 *remainder_ret = dividend;
107 }
108 }
109
110
operator /=(const uint128 & divisor)111 uint128& uint128::operator/=(const uint128& divisor) {
112 uint128 quotient = 0;
113 uint128 remainder = 0;
114 DivModImpl(*this, divisor, "ient, &remainder);
115 *this = quotient;
116 return *this;
117 }
operator %=(const uint128 & divisor)118 uint128& uint128::operator%=(const uint128& divisor) {
119 uint128 quotient = 0;
120 uint128 remainder = 0;
121 DivModImpl(*this, divisor, "ient, &remainder);
122 *this = remainder;
123 return *this;
124 }
125
operator <<(std::ostream & o,const uint128 & b)126 std::ostream& operator<<(std::ostream& o, const uint128& b) {
127 std::ios_base::fmtflags flags = o.flags();
128
129 // Select a divisor which is the largest power of the base < 2^64.
130 uint128 div;
131 std::streamsize div_base_log;
132 switch (flags & std::ios::basefield) {
133 case std::ios::hex:
134 div =
135 static_cast<uint64_t>(uint64_t{0x1000000000000000u}); // 16^15
136 div_base_log = 15;
137 break;
138 case std::ios::oct:
139 div = static_cast<uint64_t>(
140 uint64_t{01000000000000000000000u}); // 8^21
141 div_base_log = 21;
142 break;
143 default: // std::ios::dec
144 div = static_cast<uint64_t>(
145 uint64_t{10000000000000000000u}); // 10^19
146 div_base_log = 19;
147 break;
148 }
149
150 // Now piece together the uint128 representation from three chunks of
151 // the original value, each less than "div" and therefore representable
152 // as a uint64.
153 std::ostringstream os;
154 std::ios_base::fmtflags copy_mask =
155 std::ios::basefield | std::ios::showbase | std::ios::uppercase;
156 os.setf(flags & copy_mask, copy_mask);
157 uint128 high = b;
158 uint128 low;
159 uint128::DivModImpl(high, div, &high, &low);
160 uint128 mid;
161 uint128::DivModImpl(high, div, &high, &mid);
162 if (high.lo_ != 0) {
163 os << high.lo_;
164 os << std::noshowbase << std::setfill('0') << std::setw(div_base_log);
165 os << mid.lo_;
166 os << std::setw(div_base_log);
167 } else if (mid.lo_ != 0) {
168 os << mid.lo_;
169 os << std::noshowbase << std::setfill('0') << std::setw(div_base_log);
170 }
171 os << low.lo_;
172 std::string rep = os.str();
173
174 // Add the requisite padding.
175 std::streamsize width = o.width(0);
176 auto repSize = static_cast<std::streamsize>(rep.size());
177 if (width > repSize) {
178 if ((flags & std::ios::adjustfield) == std::ios::left) {
179 rep.append(width - repSize, o.fill());
180 } else {
181 rep.insert(static_cast<std::string::size_type>(0), width - repSize,
182 o.fill());
183 }
184 }
185
186 // Stream the final representation in a single "<<" call.
187 return o << rep;
188 }
189
190 } // namespace protobuf
191 } // namespace google
192
193 #include <google/protobuf/port_undef.inc> // NOLINT
194