1 | // This file is based on the uint128 implementation of protobuf at |
2 | // https://github.com/protocolbuffers/protobuf/blob/1e88936fce10cf773cb72b44c6a7f48b38c7578b/src/google/protobuf/stubs/int128.cc |
3 | // |
4 | // Protocol Buffers - Google's data interchange format |
5 | // Copyright 2008 Google Inc. All rights reserved. |
6 | // https://developers.google.com/protocol-buffers/ |
7 | // |
8 | // Redistribution and use in source and binary forms, with or without |
9 | // modification, are permitted provided that the following conditions are |
10 | // met: |
11 | // |
12 | // * Redistributions of source code must retain the above copyright |
13 | // notice, this list of conditions and the following disclaimer. |
14 | // * Redistributions in binary form must reproduce the above |
15 | // copyright notice, this list of conditions and the following disclaimer |
16 | // in the documentation and/or other materials provided with the |
17 | // distribution. |
18 | // * Neither the name of Google Inc. nor the names of its |
19 | // contributors may be used to endorse or promote products derived from |
20 | // this software without specific prior written permission. |
21 | // |
22 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
23 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
24 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
25 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
26 | // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
27 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
28 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
29 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
30 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
31 | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
32 | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
33 | |
34 | #include <c10/util/Logging.h> |
35 | #include <c10/util/int128.h> |
36 | #include <iomanip> |
37 | #include <ostream> // NOLINT(readability/streams) |
38 | |
39 | namespace c10 { |
40 | |
41 | const uint128_pod kuint128max = { |
42 | uint64_t{0xFFFFFFFFFFFFFFFFu}, |
43 | uint64_t{0xFFFFFFFFFFFFFFFFu}}; |
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_t n) { |
59 | // GOOGLE_DCHECK_NE(0, n); |
60 | int pos = 0; |
61 | STEP(uint64_t, n, pos, 0x20); |
62 | uint32_t n32 = n; |
63 | STEP(uint32_t, n32, pos, 0x10); |
64 | STEP(uint32_t, n32, pos, 0x08); |
65 | STEP(uint32_t, n32, pos, 0x04); |
66 | return pos + ((uint64_t{0x3333333322221100u} >> (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_t hi = Uint128High64(n)) { |
74 | return Fls64(hi) + 64; |
75 | } |
76 | return Fls64(Uint128Low64(n)); |
77 | } |
78 | |
79 | void uint128::DivModImpl( |
80 | uint128 dividend, |
81 | uint128 divisor, |
82 | uint128* quotient_ret, |
83 | uint128* remainder_ret) { |
84 | if (divisor == 0) { |
85 | LOG(FATAL) << "Division or mod by zero: dividend.hi=" << dividend.hi_ |
86 | << ", lo=" << dividend.lo_; |
87 | } else if (dividend < divisor) { |
88 | *quotient_ret = 0; |
89 | *remainder_ret = dividend; |
90 | return; |
91 | } else { |
92 | int dividend_bit_length = Fls128(dividend); |
93 | int divisor_bit_length = Fls128(divisor); |
94 | int difference = dividend_bit_length - divisor_bit_length; |
95 | uint128 quotient = 0; |
96 | while (difference >= 0) { |
97 | quotient <<= 1; |
98 | uint128 shifted_divisor = divisor << difference; |
99 | if (shifted_divisor <= dividend) { |
100 | dividend -= shifted_divisor; |
101 | quotient += 1; |
102 | } |
103 | difference -= 1; |
104 | } |
105 | // record the final quotient and remainder |
106 | *quotient_ret = quotient; |
107 | *remainder_ret = dividend; |
108 | } |
109 | } |
110 | |
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 | } |
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 | |
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 = 0; |
132 | switch (flags & std::ios::basefield) { |
133 | case std::ios::hex: |
134 | div = (uint64_t)0x1000000000000000u; // 16^15 |
135 | div_base_log = 15; |
136 | break; |
137 | case std::ios::oct: |
138 | div = (uint64_t)01000000000000000000000u; // 8^21 |
139 | div_base_log = 21; |
140 | break; |
141 | default: // std::ios::dec |
142 | div = (uint64_t)10000000000000000000u; // 10^19 |
143 | div_base_log = 19; |
144 | break; |
145 | } |
146 | |
147 | // Now piece together the uint128 representation from three chunks of |
148 | // the original value, each less than "div" and therefore representable |
149 | // as a uint64. |
150 | std::ostringstream os; |
151 | std::ios_base::fmtflags copy_mask = |
152 | std::ios::basefield | std::ios::showbase | std::ios::uppercase; |
153 | os.setf(flags & copy_mask, copy_mask); |
154 | uint128 high = b; |
155 | uint128 low; |
156 | uint128::DivModImpl(high, div, &high, &low); |
157 | uint128 mid; |
158 | uint128::DivModImpl(high, div, &high, &mid); |
159 | if (high.lo_ != 0) { |
160 | os << high.lo_; |
161 | os << std::noshowbase << std::setfill('0') << std::setw(div_base_log); |
162 | os << mid.lo_; |
163 | os << std::setw(div_base_log); |
164 | } else if (mid.lo_ != 0) { |
165 | os << mid.lo_; |
166 | os << std::noshowbase << std::setfill('0') << std::setw(div_base_log); |
167 | } |
168 | os << low.lo_; |
169 | std::string rep = os.str(); |
170 | |
171 | // Add the requisite padding. |
172 | std::streamsize width = o.width(0); |
173 | if (width > static_cast<std::streamsize>(rep.size())) { |
174 | if ((flags & std::ios::adjustfield) == std::ios::left) { |
175 | rep.append(width - rep.size(), o.fill()); |
176 | } else { |
177 | rep.insert( |
178 | static_cast<std::string::size_type>(0), width - rep.size(), o.fill()); |
179 | } |
180 | } |
181 | |
182 | // Stream the final representation in a single "<<" call. |
183 | return o << rep; |
184 | } |
185 | |
186 | } // namespace c10 |
187 | |