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