Coverage Report

Created: 2024-09-23 06:29

/src/abseil-cpp/absl/strings/internal/charconv_bigint.h
Line
Count
Source (jump to first uncovered line)
1
// Copyright 2018 The Abseil Authors.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//      https://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14
15
#ifndef ABSL_STRINGS_INTERNAL_CHARCONV_BIGINT_H_
16
#define ABSL_STRINGS_INTERNAL_CHARCONV_BIGINT_H_
17
18
#include <algorithm>
19
#include <cstdint>
20
#include <iostream>
21
#include <string>
22
23
#include "absl/base/config.h"
24
#include "absl/strings/ascii.h"
25
#include "absl/strings/internal/charconv_parse.h"
26
#include "absl/strings/string_view.h"
27
28
namespace absl {
29
ABSL_NAMESPACE_BEGIN
30
namespace strings_internal {
31
32
// The largest power that 5 that can be raised to, and still fit in a uint32_t.
33
constexpr int kMaxSmallPowerOfFive = 13;
34
// The largest power that 10 that can be raised to, and still fit in a uint32_t.
35
constexpr int kMaxSmallPowerOfTen = 9;
36
37
ABSL_DLL extern const uint32_t
38
    kFiveToNth[kMaxSmallPowerOfFive + 1];
39
ABSL_DLL extern const uint32_t kTenToNth[kMaxSmallPowerOfTen + 1];
40
41
// Large, fixed-width unsigned integer.
42
//
43
// Exact rounding for decimal-to-binary floating point conversion requires very
44
// large integer math, but a design goal of absl::from_chars is to avoid
45
// allocating memory.  The integer precision needed for decimal-to-binary
46
// conversions is large but bounded, so a huge fixed-width integer class
47
// suffices.
48
//
49
// This is an intentionally limited big integer class.  Only needed operations
50
// are implemented.  All storage lives in an array data member, and all
51
// arithmetic is done in-place, to avoid requiring separate storage for operand
52
// and result.
53
//
54
// This is an internal class.  Some methods live in the .cc file, and are
55
// instantiated only for the values of max_words we need.
56
template <int max_words>
57
class BigUnsigned {
58
 public:
59
  static_assert(max_words == 4 || max_words == 84,
60
                "unsupported max_words value");
61
62
10.7k
  BigUnsigned() : size_(0), words_{} {}
absl::strings_internal::BigUnsigned<84>::BigUnsigned()
Line
Count
Source
62
10.7k
  BigUnsigned() : size_(0), words_{} {}
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::BigUnsigned()
63
  explicit constexpr BigUnsigned(uint64_t v)
64
      : size_((v >> 32) ? 2 : v ? 1 : 0),
65
        words_{static_cast<uint32_t>(v & 0xffffffffu),
66
10.7k
               static_cast<uint32_t>(v >> 32)} {}
absl::strings_internal::BigUnsigned<84>::BigUnsigned(unsigned long)
Line
Count
Source
66
10.7k
               static_cast<uint32_t>(v >> 32)} {}
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::BigUnsigned(unsigned long)
67
68
  // Constructs a BigUnsigned from the given string_view containing a decimal
69
  // value.  If the input string is not a decimal integer, constructs a 0
70
  // instead.
71
0
  explicit BigUnsigned(absl::string_view sv) : size_(0), words_{} {
72
    // Check for valid input, returning a 0 otherwise.  This is reasonable
73
    // behavior only because this constructor is for unit tests.
74
0
    if (std::find_if_not(sv.begin(), sv.end(), ascii_isdigit) != sv.end() ||
75
0
        sv.empty()) {
76
0
      return;
77
0
    }
78
0
    int exponent_adjust =
79
0
        ReadDigits(sv.data(), sv.data() + sv.size(), Digits10() + 1);
80
0
    if (exponent_adjust > 0) {
81
0
      MultiplyByTenToTheNth(exponent_adjust);
82
0
    }
83
0
  }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::BigUnsigned(std::__1::basic_string_view<char, std::__1::char_traits<char> >)
Unexecuted instantiation: absl::strings_internal::BigUnsigned<84>::BigUnsigned(std::__1::basic_string_view<char, std::__1::char_traits<char> >)
84
85
  // Loads the mantissa value of a previously-parsed float.
86
  //
87
  // Returns the associated decimal exponent.  The value of the parsed float is
88
  // exactly *this * 10**exponent.
89
  int ReadFloatMantissa(const ParsedFloat& fp, int significant_digits);
90
91
  // Returns the number of decimal digits of precision this type provides.  All
92
  // numbers with this many decimal digits or fewer are representable by this
93
  // type.
94
  //
95
  // Analogous to std::numeric_limits<BigUnsigned>::digits10.
96
8.75k
  static constexpr int Digits10() {
97
    // 9975007/1035508 is very slightly less than log10(2**32).
98
8.75k
    return static_cast<uint64_t>(max_words) * 9975007 / 1035508;
99
8.75k
  }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::Digits10()
absl::strings_internal::BigUnsigned<84>::Digits10()
Line
Count
Source
96
8.75k
  static constexpr int Digits10() {
97
    // 9975007/1035508 is very slightly less than log10(2**32).
98
8.75k
    return static_cast<uint64_t>(max_words) * 9975007 / 1035508;
99
8.75k
  }
100
101
  // Shifts left by the given number of bits.
102
10.7k
  void ShiftLeft(int count) {
103
10.7k
    if (count > 0) {
104
10.4k
      const int word_shift = count / 32;
105
10.4k
      if (word_shift >= max_words) {
106
266
        SetToZero();
107
266
        return;
108
266
      }
109
10.2k
      size_ = (std::min)(size_ + word_shift, max_words);
110
10.2k
      count %= 32;
111
10.2k
      if (count == 0) {
112
// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=warray-bounds
113
// shows a lot of bogus -Warray-bounds warnings under GCC.
114
// This is not the only one in Abseil.
115
#if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(14, 0)
116
#pragma GCC diagnostic push
117
#pragma GCC diagnostic ignored "-Warray-bounds"
118
#endif
119
457
        std::copy_backward(words_, words_ + size_ - word_shift, words_ + size_);
120
#if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(14, 0)
121
#pragma GCC diagnostic pop
122
#endif
123
9.74k
      } else {
124
140k
        for (int i = (std::min)(size_, max_words - 1); i > word_shift; --i) {
125
131k
          words_[i] = (words_[i - word_shift] << count) |
126
131k
                      (words_[i - word_shift - 1] >> (32 - count));
127
131k
        }
128
9.74k
        words_[word_shift] = words_[0] << count;
129
        // Grow size_ if necessary.
130
9.74k
        if (size_ < max_words && words_[size_]) {
131
6.34k
          ++size_;
132
6.34k
        }
133
9.74k
      }
134
10.2k
      std::fill_n(words_, word_shift, 0u);
135
10.2k
    }
136
10.7k
  }
absl::strings_internal::BigUnsigned<84>::ShiftLeft(int)
Line
Count
Source
102
10.7k
  void ShiftLeft(int count) {
103
10.7k
    if (count > 0) {
104
10.4k
      const int word_shift = count / 32;
105
10.4k
      if (word_shift >= max_words) {
106
266
        SetToZero();
107
266
        return;
108
266
      }
109
10.2k
      size_ = (std::min)(size_ + word_shift, max_words);
110
10.2k
      count %= 32;
111
10.2k
      if (count == 0) {
112
// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=warray-bounds
113
// shows a lot of bogus -Warray-bounds warnings under GCC.
114
// This is not the only one in Abseil.
115
#if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(14, 0)
116
#pragma GCC diagnostic push
117
#pragma GCC diagnostic ignored "-Warray-bounds"
118
#endif
119
457
        std::copy_backward(words_, words_ + size_ - word_shift, words_ + size_);
120
#if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(14, 0)
121
#pragma GCC diagnostic pop
122
#endif
123
9.74k
      } else {
124
140k
        for (int i = (std::min)(size_, max_words - 1); i > word_shift; --i) {
125
131k
          words_[i] = (words_[i - word_shift] << count) |
126
131k
                      (words_[i - word_shift - 1] >> (32 - count));
127
131k
        }
128
9.74k
        words_[word_shift] = words_[0] << count;
129
        // Grow size_ if necessary.
130
9.74k
        if (size_ < max_words && words_[size_]) {
131
6.34k
          ++size_;
132
6.34k
        }
133
9.74k
      }
134
10.2k
      std::fill_n(words_, word_shift, 0u);
135
10.2k
    }
136
10.7k
  }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::ShiftLeft(int)
137
138
139
  // Multiplies by v in-place.
140
448k
  void MultiplyBy(uint32_t v) {
141
448k
    if (size_ == 0 || v == 1) {
142
123k
      return;
143
123k
    }
144
325k
    if (v == 0) {
145
0
      SetToZero();
146
0
      return;
147
0
    }
148
325k
    const uint64_t factor = v;
149
325k
    uint64_t window = 0;
150
14.8M
    for (int i = 0; i < size_; ++i) {
151
14.5M
      window += factor * words_[i];
152
14.5M
      words_[i] = window & 0xffffffff;
153
14.5M
      window >>= 32;
154
14.5M
    }
155
    // If carry bits remain and there's space for them, grow size_.
156
325k
    if (window && size_ < max_words) {
157
216k
      words_[size_] = window & 0xffffffff;
158
216k
      ++size_;
159
216k
    }
160
325k
  }
absl::strings_internal::BigUnsigned<84>::MultiplyBy(unsigned int)
Line
Count
Source
140
448k
  void MultiplyBy(uint32_t v) {
141
448k
    if (size_ == 0 || v == 1) {
142
123k
      return;
143
123k
    }
144
325k
    if (v == 0) {
145
0
      SetToZero();
146
0
      return;
147
0
    }
148
325k
    const uint64_t factor = v;
149
325k
    uint64_t window = 0;
150
14.8M
    for (int i = 0; i < size_; ++i) {
151
14.5M
      window += factor * words_[i];
152
14.5M
      words_[i] = window & 0xffffffff;
153
14.5M
      window >>= 32;
154
14.5M
    }
155
    // If carry bits remain and there's space for them, grow size_.
156
325k
    if (window && size_ < max_words) {
157
216k
      words_[size_] = window & 0xffffffff;
158
216k
      ++size_;
159
216k
    }
160
325k
  }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::MultiplyBy(unsigned int)
161
162
7.30k
  void MultiplyBy(uint64_t v) {
163
7.30k
    uint32_t words[2];
164
7.30k
    words[0] = static_cast<uint32_t>(v);
165
7.30k
    words[1] = static_cast<uint32_t>(v >> 32);
166
7.30k
    if (words[1] == 0) {
167
0
      MultiplyBy(words[0]);
168
7.30k
    } else {
169
7.30k
      MultiplyBy(2, words);
170
7.30k
    }
171
7.30k
  }
absl::strings_internal::BigUnsigned<84>::MultiplyBy(unsigned long)
Line
Count
Source
162
7.30k
  void MultiplyBy(uint64_t v) {
163
7.30k
    uint32_t words[2];
164
7.30k
    words[0] = static_cast<uint32_t>(v);
165
7.30k
    words[1] = static_cast<uint32_t>(v >> 32);
166
7.30k
    if (words[1] == 0) {
167
0
      MultiplyBy(words[0]);
168
7.30k
    } else {
169
7.30k
      MultiplyBy(2, words);
170
7.30k
    }
171
7.30k
  }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::MultiplyBy(unsigned long)
172
173
  // Multiplies in place by 5 to the power of n.  n must be non-negative.
174
10.7k
  void MultiplyByFiveToTheNth(int n) {
175
191k
    while (n >= kMaxSmallPowerOfFive) {
176
181k
      MultiplyBy(kFiveToNth[kMaxSmallPowerOfFive]);
177
181k
      n -= kMaxSmallPowerOfFive;
178
181k
    }
179
10.7k
    if (n > 0) {
180
5.98k
      MultiplyBy(kFiveToNth[n]);
181
5.98k
    }
182
10.7k
  }
absl::strings_internal::BigUnsigned<84>::MultiplyByFiveToTheNth(int)
Line
Count
Source
174
10.7k
  void MultiplyByFiveToTheNth(int n) {
175
191k
    while (n >= kMaxSmallPowerOfFive) {
176
181k
      MultiplyBy(kFiveToNth[kMaxSmallPowerOfFive]);
177
181k
      n -= kMaxSmallPowerOfFive;
178
181k
    }
179
10.7k
    if (n > 0) {
180
5.98k
      MultiplyBy(kFiveToNth[n]);
181
5.98k
    }
182
10.7k
  }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::MultiplyByFiveToTheNth(int)
183
184
  // Multiplies in place by 10 to the power of n.  n must be non-negative.
185
0
  void MultiplyByTenToTheNth(int n) {
186
0
    if (n > kMaxSmallPowerOfTen) {
187
      // For large n, raise to a power of 5, then shift left by the same amount.
188
      // (10**n == 5**n * 2**n.)  This requires fewer multiplications overall.
189
0
      MultiplyByFiveToTheNth(n);
190
0
      ShiftLeft(n);
191
0
    } else if (n > 0) {
192
      // We can do this more quickly for very small N by using a single
193
      // multiplication.
194
0
      MultiplyBy(kTenToNth[n]);
195
0
    }
196
0
  }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::MultiplyByTenToTheNth(int)
Unexecuted instantiation: absl::strings_internal::BigUnsigned<84>::MultiplyByTenToTheNth(int)
197
198
  // Returns the value of 5**n, for non-negative n.  This implementation uses
199
  // a lookup table, and is faster then seeding a BigUnsigned with 1 and calling
200
  // MultiplyByFiveToTheNth().
201
  static BigUnsigned FiveToTheNth(int n);
202
203
  // Multiplies by another BigUnsigned, in-place.
204
  template <int M>
205
  void MultiplyBy(const BigUnsigned<M>& other) {
206
    MultiplyBy(other.size(), other.words());
207
  }
208
209
19.7k
  void SetToZero() {
210
19.7k
    std::fill_n(words_, size_, 0u);
211
19.7k
    size_ = 0;
212
19.7k
  }
absl::strings_internal::BigUnsigned<84>::SetToZero()
Line
Count
Source
209
19.7k
  void SetToZero() {
210
19.7k
    std::fill_n(words_, size_, 0u);
211
19.7k
    size_ = 0;
212
19.7k
  }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::SetToZero()
213
214
  // Returns the value of the nth word of this BigUnsigned.  This is
215
  // range-checked, and returns 0 on out-of-bounds accesses.
216
58.6k
  uint32_t GetWord(int index) const {
217
58.6k
    if (index < 0 || index >= size_) {
218
1.35k
      return 0;
219
1.35k
    }
220
57.3k
    return words_[index];
221
58.6k
  }
absl::strings_internal::BigUnsigned<84>::GetWord(int) const
Line
Count
Source
216
58.6k
  uint32_t GetWord(int index) const {
217
58.6k
    if (index < 0 || index >= size_) {
218
1.35k
      return 0;
219
1.35k
    }
220
57.3k
    return words_[index];
221
58.6k
  }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::GetWord(int) const
222
223
  // Returns this integer as a decimal string.  This is not used in the decimal-
224
  // to-binary conversion; it is intended to aid in testing.
225
  std::string ToString() const;
226
227
21.5k
  int size() const { return size_; }
absl::strings_internal::BigUnsigned<84>::size() const
Line
Count
Source
227
21.5k
  int size() const { return size_; }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::size() const
228
0
  const uint32_t* words() const { return words_; }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::words() const
Unexecuted instantiation: absl::strings_internal::BigUnsigned<84>::words() const
229
230
 private:
231
  // Reads the number between [begin, end), possibly containing a decimal point,
232
  // into this BigUnsigned.
233
  //
234
  // Callers are required to ensure [begin, end) contains a valid number, with
235
  // one or more decimal digits and at most one decimal point.  This routine
236
  // will behave unpredictably if these preconditions are not met.
237
  //
238
  // Only the first `significant_digits` digits are read.  Digits beyond this
239
  // limit are "sticky": If the final significant digit is 0 or 5, and if any
240
  // dropped digit is nonzero, then that final significant digit is adjusted up
241
  // to 1 or 6.  This adjustment allows for precise rounding.
242
  //
243
  // Returns `exponent_adjustment`, a power-of-ten exponent adjustment to
244
  // account for the decimal point and for dropped significant digits.  After
245
  // this function returns,
246
  //   actual_value_of_parsed_string ~= *this * 10**exponent_adjustment.
247
  int ReadDigits(const char* begin, const char* end, int significant_digits);
248
249
  // Performs a step of big integer multiplication.  This computes the full
250
  // (64-bit-wide) values that should be added at the given index (step), and
251
  // adds to that location in-place.
252
  //
253
  // Because our math all occurs in place, we must multiply starting from the
254
  // highest word working downward.  (This is a bit more expensive due to the
255
  // extra carries involved.)
256
  //
257
  // This must be called in steps, for each word to be calculated, starting from
258
  // the high end and working down to 0.  The first value of `step` should be
259
  //   `std::min(original_size + other.size_ - 2, max_words - 1)`.
260
  // The reason for this expression is that multiplying the i'th word from one
261
  // multiplicand and the j'th word of another multiplicand creates a
262
  // two-word-wide value to be stored at the (i+j)'th element.  The highest
263
  // word indices we will access are `original_size - 1` from this object, and
264
  // `other.size_ - 1` from our operand.  Therefore,
265
  // `original_size + other.size_ - 2` is the first step we should calculate,
266
  // but limited on an upper bound by max_words.
267
268
  // Working from high-to-low ensures that we do not overwrite the portions of
269
  // the initial value of *this which are still needed for later steps.
270
  //
271
  // Once called with step == 0, *this contains the result of the
272
  // multiplication.
273
  //
274
  // `original_size` is the size_ of *this before the first call to
275
  // MultiplyStep().  `other_words` and `other_size` are the contents of our
276
  // operand.  `step` is the step to perform, as described above.
277
  void MultiplyStep(int original_size, const uint32_t* other_words,
278
                    int other_size, int step);
279
280
9.31k
  void MultiplyBy(int other_size, const uint32_t* other_words) {
281
9.31k
    const int original_size = size_;
282
9.31k
    const int first_step =
283
9.31k
        (std::min)(original_size + other_size - 2, max_words - 1);
284
249k
    for (int step = first_step; step >= 0; --step) {
285
240k
      MultiplyStep(original_size, other_words, other_size, step);
286
240k
    }
287
9.31k
  }
absl::strings_internal::BigUnsigned<84>::MultiplyBy(int, unsigned int const*)
Line
Count
Source
280
9.31k
  void MultiplyBy(int other_size, const uint32_t* other_words) {
281
9.31k
    const int original_size = size_;
282
9.31k
    const int first_step =
283
9.31k
        (std::min)(original_size + other_size - 2, max_words - 1);
284
249k
    for (int step = first_step; step >= 0; --step) {
285
240k
      MultiplyStep(original_size, other_words, other_size, step);
286
240k
    }
287
9.31k
  }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::MultiplyBy(int, unsigned int const*)
288
289
  // Adds a 32-bit value to the index'th word, with carry.
290
375k
  void AddWithCarry(int index, uint32_t value) {
291
375k
    if (value) {
292
363k
      while (index < max_words && value > 0) {
293
185k
        words_[index] += value;
294
        // carry if we overflowed in this word:
295
185k
        if (value > words_[index]) {
296
6.96k
          value = 1;
297
6.96k
          ++index;
298
178k
        } else {
299
178k
          value = 0;
300
178k
        }
301
185k
      }
302
178k
      size_ = (std::min)(max_words, (std::max)(index + 1, size_));
303
178k
    }
304
375k
  }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::AddWithCarry(int, unsigned int)
absl::strings_internal::BigUnsigned<84>::AddWithCarry(int, unsigned int)
Line
Count
Source
290
375k
  void AddWithCarry(int index, uint32_t value) {
291
375k
    if (value) {
292
363k
      while (index < max_words && value > 0) {
293
185k
        words_[index] += value;
294
        // carry if we overflowed in this word:
295
185k
        if (value > words_[index]) {
296
6.96k
          value = 1;
297
6.96k
          ++index;
298
178k
        } else {
299
178k
          value = 0;
300
178k
        }
301
185k
      }
302
178k
      size_ = (std::min)(max_words, (std::max)(index + 1, size_));
303
178k
    }
304
375k
  }
305
306
240k
  void AddWithCarry(int index, uint64_t value) {
307
240k
    if (value && index < max_words) {
308
237k
      uint32_t high = value >> 32;
309
237k
      uint32_t low = value & 0xffffffff;
310
237k
      words_[index] += low;
311
237k
      if (words_[index] < low) {
312
79.7k
        ++high;
313
79.7k
        if (high == 0) {
314
          // Carry from the low word caused our high word to overflow.
315
          // Short circuit here to do the right thing.
316
0
          AddWithCarry(index + 2, static_cast<uint32_t>(1));
317
0
          return;
318
0
        }
319
79.7k
      }
320
237k
      if (high > 0) {
321
114k
        AddWithCarry(index + 1, high);
322
123k
      } else {
323
        // Normally 32-bit AddWithCarry() sets size_, but since we don't call
324
        // it when `high` is 0, do it ourselves here.
325
123k
        size_ = (std::min)(max_words, (std::max)(index + 1, size_));
326
123k
      }
327
237k
    }
328
240k
  }
Unexecuted instantiation: absl::strings_internal::BigUnsigned<4>::AddWithCarry(int, unsigned long)
absl::strings_internal::BigUnsigned<84>::AddWithCarry(int, unsigned long)
Line
Count
Source
306
240k
  void AddWithCarry(int index, uint64_t value) {
307
240k
    if (value && index < max_words) {
308
237k
      uint32_t high = value >> 32;
309
237k
      uint32_t low = value & 0xffffffff;
310
237k
      words_[index] += low;
311
237k
      if (words_[index] < low) {
312
79.7k
        ++high;
313
79.7k
        if (high == 0) {
314
          // Carry from the low word caused our high word to overflow.
315
          // Short circuit here to do the right thing.
316
0
          AddWithCarry(index + 2, static_cast<uint32_t>(1));
317
0
          return;
318
0
        }
319
79.7k
      }
320
237k
      if (high > 0) {
321
114k
        AddWithCarry(index + 1, high);
322
123k
      } else {
323
        // Normally 32-bit AddWithCarry() sets size_, but since we don't call
324
        // it when `high` is 0, do it ourselves here.
325
123k
        size_ = (std::min)(max_words, (std::max)(index + 1, size_));
326
123k
      }
327
237k
    }
328
240k
  }
329
330
  // Divide this in place by a constant divisor.  Returns the remainder of the
331
  // division.
332
  template <uint32_t divisor>
333
0
  uint32_t DivMod() {
334
0
    uint64_t accumulator = 0;
335
0
    for (int i = size_ - 1; i >= 0; --i) {
336
0
      accumulator <<= 32;
337
0
      accumulator += words_[i];
338
      // accumulator / divisor will never overflow an int32_t in this loop
339
0
      words_[i] = static_cast<uint32_t>(accumulator / divisor);
340
0
      accumulator = accumulator % divisor;
341
0
    }
342
0
    while (size_ > 0 && words_[size_ - 1] == 0) {
343
0
      --size_;
344
0
    }
345
0
    return static_cast<uint32_t>(accumulator);
346
0
  }
Unexecuted instantiation: unsigned int absl::strings_internal::BigUnsigned<4>::DivMod<10u>()
Unexecuted instantiation: unsigned int absl::strings_internal::BigUnsigned<84>::DivMod<10u>()
347
348
  // The number of elements in words_ that may carry significant values.
349
  // All elements beyond this point are 0.
350
  //
351
  // When size_ is 0, this BigUnsigned stores the value 0.
352
  // When size_ is nonzero, is *not* guaranteed that words_[size_ - 1] is
353
  // nonzero.  This can occur due to overflow truncation.
354
  // In particular, x.size_ != y.size_ does *not* imply x != y.
355
  int size_;
356
  uint32_t words_[max_words];
357
};
358
359
// Compares two big integer instances.
360
//
361
// Returns -1 if lhs < rhs, 0 if lhs == rhs, and 1 if lhs > rhs.
362
template <int N, int M>
363
10.7k
int Compare(const BigUnsigned<N>& lhs, const BigUnsigned<M>& rhs) {
364
10.7k
  int limit = (std::max)(lhs.size(), rhs.size());
365
30.1k
  for (int i = limit - 1; i >= 0; --i) {
366
29.3k
    const uint32_t lhs_word = lhs.GetWord(i);
367
29.3k
    const uint32_t rhs_word = rhs.GetWord(i);
368
29.3k
    if (lhs_word < rhs_word) {
369
7.92k
      return -1;
370
21.4k
    } else if (lhs_word > rhs_word) {
371
2.03k
      return 1;
372
2.03k
    }
373
29.3k
  }
374
806
  return 0;
375
10.7k
}
376
377
template <int N, int M>
378
bool operator==(const BigUnsigned<N>& lhs, const BigUnsigned<M>& rhs) {
379
  int limit = (std::max)(lhs.size(), rhs.size());
380
  for (int i = 0; i < limit; ++i) {
381
    if (lhs.GetWord(i) != rhs.GetWord(i)) {
382
      return false;
383
    }
384
  }
385
  return true;
386
}
387
388
template <int N, int M>
389
bool operator!=(const BigUnsigned<N>& lhs, const BigUnsigned<M>& rhs) {
390
  return !(lhs == rhs);
391
}
392
393
template <int N, int M>
394
bool operator<(const BigUnsigned<N>& lhs, const BigUnsigned<M>& rhs) {
395
  return Compare(lhs, rhs) == -1;
396
}
397
398
template <int N, int M>
399
bool operator>(const BigUnsigned<N>& lhs, const BigUnsigned<M>& rhs) {
400
  return rhs < lhs;
401
}
402
template <int N, int M>
403
bool operator<=(const BigUnsigned<N>& lhs, const BigUnsigned<M>& rhs) {
404
  return !(rhs < lhs);
405
}
406
template <int N, int M>
407
bool operator>=(const BigUnsigned<N>& lhs, const BigUnsigned<M>& rhs) {
408
  return !(lhs < rhs);
409
}
410
411
// Output operator for BigUnsigned, for testing purposes only.
412
template <int N>
413
std::ostream& operator<<(std::ostream& os, const BigUnsigned<N>& num) {
414
  return os << num.ToString();
415
}
416
417
// Explicit instantiation declarations for the sizes of BigUnsigned that we
418
// are using.
419
//
420
// For now, the choices of 4 and 84 are arbitrary; 4 is a small value that is
421
// still bigger than an int128, and 84 is a large value we will want to use
422
// in the from_chars implementation.
423
//
424
// Comments justifying the use of 84 belong in the from_chars implementation,
425
// and will be added in a follow-up CL.
426
extern template class BigUnsigned<4>;
427
extern template class BigUnsigned<84>;
428
429
}  // namespace strings_internal
430
ABSL_NAMESPACE_END
431
}  // namespace absl
432
433
#endif  // ABSL_STRINGS_INTERNAL_CHARCONV_BIGINT_H_