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
4
// Protocol Buffers - Google's data interchange format
5
// Copyright 2008 Google Inc. All rights reserved.
6
// https://developers.google.com/protocol-buffers/
8
// Redistribution and use in source and binary forms, with or without
9
// modification, are permitted provided that the following conditions are
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
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.
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.
34
#include <c10/util/Logging.h>
35
#include <c10/util/int128.h>
37
#include <ostream> // NOLINT(readability/streams)
41
const uint128_pod kuint128max = {
42
uint64_t{0xFFFFFFFFFFFFFFFFu},
43
uint64_t{0xFFFFFFFFFFFFFFFFu}};
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.
49
// Given: 5 (decimal) == 101 (binary)
51
#define STEP(T, n, pos, sh) \
53
if ((n) >= (static_cast<T>(1) << (sh))) { \
58
static inline int Fls64(uint64_t n) {
59
// GOOGLE_DCHECK_NE(0, n);
61
STEP(uint64_t, n, pos, 0x20);
63
STEP(uint32_t, n32, pos, 0x10);
64
STEP(uint32_t, n32, pos, 0x08);
65
STEP(uint32_t, n32, pos, 0x04);
66
return static_cast<int>(
67
pos + ((uint64_t{0x3333333322221100u} >> (n32 << 2)) & 0x3));
71
// Like Fls64() above, but returns the 0-based position of the last set bit
72
// (i.e., most significant bit) in the given uint128. The argument may not be 0.
73
static inline int Fls128(uint128 n) {
74
if (uint64_t hi = Uint128High64(n)) {
75
return Fls64(hi) + 64;
77
return Fls64(Uint128Low64(n));
80
void uint128::DivModImpl(
83
uint128* quotient_ret,
84
uint128* remainder_ret) {
86
LOG(FATAL) << "Division or mod by zero: dividend.hi=" << dividend.hi_
87
<< ", lo=" << dividend.lo_;
88
} else if (dividend < divisor) {
90
*remainder_ret = dividend;
93
int dividend_bit_length = Fls128(dividend);
94
int divisor_bit_length = Fls128(divisor);
95
int difference = dividend_bit_length - divisor_bit_length;
97
while (difference >= 0) {
99
uint128 shifted_divisor = divisor << difference;
100
if (shifted_divisor <= dividend) {
101
dividend -= shifted_divisor;
106
// record the final quotient and remainder
107
*quotient_ret = quotient;
108
*remainder_ret = dividend;
112
uint128& uint128::operator/=(const uint128& divisor) {
113
uint128 quotient = 0;
114
uint128 remainder = 0;
115
DivModImpl(*this, divisor, "ient, &remainder);
119
uint128& uint128::operator%=(const uint128& divisor) {
120
uint128 quotient = 0;
121
uint128 remainder = 0;
122
DivModImpl(*this, divisor, "ient, &remainder);
127
std::ostream& operator<<(std::ostream& o, const uint128& b) {
128
std::ios_base::fmtflags flags = o.flags();
130
// Select a divisor which is the largest power of the base < 2^64.
132
int div_base_log = 0;
133
switch (flags & std::ios::basefield) {
135
div = (uint64_t)0x1000000000000000u; // 16^15
139
div = (uint64_t)01000000000000000000000u; // 8^21
142
default: // std::ios::dec
143
div = (uint64_t)10000000000000000000u; // 10^19
148
// Now piece together the uint128 representation from three chunks of
149
// the original value, each less than "div" and therefore representable
151
std::ostringstream os;
152
std::ios_base::fmtflags copy_mask =
153
std::ios::basefield | std::ios::showbase | std::ios::uppercase;
154
os.setf(flags & copy_mask, copy_mask);
157
uint128::DivModImpl(high, div, &high, &low);
159
uint128::DivModImpl(high, div, &high, &mid);
162
os << std::noshowbase << std::setfill('0') << std::setw(div_base_log);
164
os << std::setw(div_base_log);
165
} else if (mid.lo_ != 0) {
167
os << std::noshowbase << std::setfill('0') << std::setw(div_base_log);
170
std::string rep = os.str();
172
// Add the requisite padding.
173
std::streamsize width = o.width(0);
174
if (width > static_cast<std::streamsize>(rep.size())) {
175
if ((flags & std::ios::adjustfield) == std::ios::left) {
176
rep.append(width - rep.size(), o.fill());
179
static_cast<std::string::size_type>(0), width - rep.size(), o.fill());
183
// Stream the final representation in a single "<<" call.