| // Copyright 2021 the V8 project authors. All rights reserved. | |
| // Use of this source code is governed by a BSD-style license that can be | |
| // found in the LICENSE file. | |
| #ifndef V8_BIGINT_DIV_HELPERS_H_ | |
| #define V8_BIGINT_DIV_HELPERS_H_ | |
| #include <memory> | |
| #include "src/bigint/bigint.h" | |
| #include "src/bigint/util.h" | |
| namespace v8 { | |
| namespace bigint { | |
| void LeftShift(RWDigits Z, Digits X, int shift); | |
| void RightShift(RWDigits Z, Digits X, int shift); | |
| inline void PutAt(RWDigits Z, Digits A, int count) { | |
| int len = std::min(A.len(), count); | |
| int i = 0; | |
| for (; i < len; i++) Z[i] = A[i]; | |
| for (; i < count; i++) Z[i] = 0; | |
| } | |
| // Division algorithms typically need to left-shift their inputs into | |
| // "bit-normalized" form (i.e. top bit is set). The inputs are considered | |
| // read-only, and V8 relies on that by allowing concurrent reads from them, | |
| // so by default, {ShiftedDigits} allocate temporary storage for their | |
| // contents. In-place modification is opt-in for cases where callers can | |
| // guarantee that it is safe. | |
| // When callers allow in-place shifting and wish to undo it, they have to do | |
| // so manually using {Reset()}. | |
| // If {shift} is not given, it is auto-detected from {original}'s | |
| // leading zeros. | |
| class ShiftedDigits : public Digits { | |
| public: | |
| explicit ShiftedDigits(Digits& original, int shift = -1, | |
| bool allow_inplace = false) | |
| : Digits(original.digits_, original.len_) { | |
| int leading_zeros = CountLeadingZeros(original.msd()); | |
| if (shift < 0) { | |
| shift = leading_zeros; | |
| } else if (shift > leading_zeros) { | |
| allow_inplace = false; | |
| len_++; | |
| } | |
| shift_ = shift; | |
| if (shift == 0) { | |
| inplace_ = true; | |
| return; | |
| } | |
| inplace_ = allow_inplace; | |
| if (!inplace_) { | |
| digit_t* digits = new digit_t[len_]; | |
| storage_.reset(digits); | |
| digits_ = digits; | |
| } | |
| RWDigits rw_view(digits_, len_); | |
| LeftShift(rw_view, original, shift_); | |
| } | |
| ~ShiftedDigits() = default; | |
| void Reset() { | |
| if (inplace_) { | |
| RWDigits rw_view(digits_, len_); | |
| RightShift(rw_view, rw_view, shift_); | |
| } | |
| } | |
| int shift() { return shift_; } | |
| private: | |
| int shift_; | |
| bool inplace_; | |
| std::unique_ptr<digit_t[]> storage_; | |
| }; | |
| } // namespace bigint | |
| } // namespace v8 | |
| #endif // V8_BIGINT_DIV_HELPERS_H_ |