Line data Source code
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 <iostream> // 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 0 : static inline int Fls64(uint64 n) {
59 : GOOGLE_DCHECK_NE(0, n);
60 0 : int pos = 0;
61 0 : STEP(uint64, n, pos, 0x20);
62 0 : uint32 n32 = n;
63 0 : STEP(uint32, n32, pos, 0x10);
64 0 : STEP(uint32, n32, pos, 0x08);
65 0 : STEP(uint32, n32, pos, 0x04);
66 0 : 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 0 : static inline int Fls128(uint128 n) {
73 0 : if (uint64 hi = Uint128High64(n)) {
74 0 : return Fls64(hi) + 64;
75 : }
76 0 : 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 0 : void uint128::DivModImpl(uint128 dividend, uint128 divisor,
83 : uint128* quotient_ret, uint128* remainder_ret) {
84 0 : if (divisor == 0) {
85 0 : GOOGLE_LOG(FATAL) << "Division or mod by zero: dividend.hi=" << dividend.hi_
86 0 : << ", lo=" << dividend.lo_;
87 : }
88 :
89 0 : if (divisor > dividend) {
90 0 : *quotient_ret = 0;
91 0 : *remainder_ret = dividend;
92 0 : return;
93 : }
94 :
95 0 : if (divisor == dividend) {
96 0 : *quotient_ret = 1;
97 0 : *remainder_ret = 0;
98 0 : return;
99 : }
100 :
101 0 : uint128 denominator = divisor;
102 : uint128 position = 1;
103 : uint128 quotient = 0;
104 :
105 : // Left aligns the MSB of the denominator and the dividend.
106 0 : int shift = Fls128(dividend) - Fls128(denominator);
107 0 : denominator <<= shift;
108 0 : position <<= shift;
109 :
110 : // Uses shift-subtract algorithm to divide dividend by denominator. The
111 : // remainder will be left in dividend.
112 0 : while (position > 0) {
113 0 : if (dividend >= denominator) {
114 : dividend -= denominator;
115 : quotient |= position;
116 : }
117 0 : position >>= 1;
118 0 : denominator >>= 1;
119 : }
120 :
121 0 : *quotient_ret = quotient;
122 0 : *remainder_ret = dividend;
123 : }
124 :
125 0 : uint128& uint128::operator/=(const uint128& divisor) {
126 : uint128 quotient = 0;
127 : uint128 remainder = 0;
128 0 : DivModImpl(*this, divisor, "ient, &remainder);
129 0 : *this = quotient;
130 0 : return *this;
131 : }
132 0 : uint128& uint128::operator%=(const uint128& divisor) {
133 : uint128 quotient = 0;
134 : uint128 remainder = 0;
135 0 : DivModImpl(*this, divisor, "ient, &remainder);
136 0 : *this = remainder;
137 0 : return *this;
138 : }
139 :
140 0 : std::ostream& operator<<(std::ostream& o, const uint128& b) {
141 0 : 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 0 : switch (flags & std::ios::basefield) {
147 : case std::ios::hex:
148 0 : div = GOOGLE_ULONGLONG(0x1000000000000000); // 16^15
149 0 : div_base_log = 15;
150 0 : break;
151 : case std::ios::oct:
152 0 : div = GOOGLE_ULONGLONG(01000000000000000000000); // 8^21
153 0 : div_base_log = 21;
154 0 : break;
155 : default: // std::ios::dec
156 0 : div = GOOGLE_ULONGLONG(10000000000000000000); // 10^19
157 0 : div_base_log = 19;
158 0 : 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 0 : std::ostringstream os;
165 : std::ios_base::fmtflags copy_mask =
166 0 : std::ios::basefield | std::ios::showbase | std::ios::uppercase;
167 0 : os.setf(flags & copy_mask, copy_mask);
168 0 : uint128 high = b;
169 : uint128 low;
170 0 : uint128::DivModImpl(high, div, &high, &low);
171 : uint128 mid;
172 0 : uint128::DivModImpl(high, div, &high, &mid);
173 0 : if (high.lo_ != 0) {
174 0 : os << high.lo_;
175 0 : os << std::noshowbase << std::setfill('0') << std::setw(div_base_log);
176 0 : os << mid.lo_;
177 0 : os << std::setw(div_base_log);
178 0 : } else if (mid.lo_ != 0) {
179 0 : os << mid.lo_;
180 0 : os << std::noshowbase << std::setfill('0') << std::setw(div_base_log);
181 : }
182 0 : os << low.lo_;
183 : std::string rep = os.str();
184 :
185 : // Add the requisite padding.
186 0 : std::streamsize width = o.width(0);
187 0 : if (width > rep.size()) {
188 0 : if ((flags & std::ios::adjustfield) == std::ios::left) {
189 0 : rep.append(width - rep.size(), o.fill());
190 : } else {
191 0 : rep.insert(0, width - rep.size(), o.fill());
192 : }
193 : }
194 :
195 : // Stream the final representation in a single "<<" call.
196 0 : return o << rep;
197 : }
198 :
199 : } // namespace protobuf
200 138 : } // namespace google
|
