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)
Fls64(uint64 n)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.
Fls128(uint128 n)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
DivModImpl(uint128 dividend,uint128 divisor,uint128 * quotient_ret,uint128 * remainder_ret)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
operator /=(const uint128 & divisor)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 }
operator %=(const uint128 & divisor)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
operator <<(std::ostream & o,const uint128 & b)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