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
39namespace c10 {
40
41const 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)
58static 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.
72static 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
79void 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
111uint128& uint128::operator/=(const uint128& divisor) {
112 uint128 quotient = 0;
113 uint128 remainder = 0;
114 DivModImpl(*this, divisor, &quotient, &remainder);
115 *this = quotient;
116 return *this;
117}
118uint128& uint128::operator%=(const uint128& divisor) {
119 uint128 quotient = 0;
120 uint128 remainder = 0;
121 DivModImpl(*this, divisor, &quotient, &remainder);
122 *this = remainder;
123 return *this;
124}
125
126std::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