1 // Copyright 2021 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef V8_BIGINT_DIV_HELPERS_H_
6 #define V8_BIGINT_DIV_HELPERS_H_
7
8 #include <memory>
9
10 #include "src/bigint/bigint.h"
11 #include "src/bigint/util.h"
12
13 namespace v8 {
14 namespace bigint {
15
16 void LeftShift(RWDigits Z, Digits X, int shift);
17 void RightShift(RWDigits Z, Digits X, int shift);
18
PutAt(RWDigits Z,Digits A,int count)19 inline void PutAt(RWDigits Z, Digits A, int count) {
20 int len = std::min(A.len(), count);
21 int i = 0;
22 for (; i < len; i++) Z[i] = A[i];
23 for (; i < count; i++) Z[i] = 0;
24 }
25
26 // Division algorithms typically need to left-shift their inputs into
27 // "bit-normalized" form (i.e. top bit is set). The inputs are considered
28 // read-only, and V8 relies on that by allowing concurrent reads from them,
29 // so by default, {ShiftedDigits} allocate temporary storage for their
30 // contents. In-place modification is opt-in for cases where callers can
31 // guarantee that it is safe.
32 // When callers allow in-place shifting and wish to undo it, they have to do
33 // so manually using {Reset()}.
34 // If {shift} is not given, it is auto-detected from {original}'s
35 // leading zeros.
36 class ShiftedDigits : public Digits {
37 public:
38 explicit ShiftedDigits(Digits& original, int shift = -1,
39 bool allow_inplace = false)
40 : Digits(original.digits_, original.len_) {
41 int leading_zeros = CountLeadingZeros(original.msd());
42 if (shift < 0) {
43 shift = leading_zeros;
44 } else if (shift > leading_zeros) {
45 allow_inplace = false;
46 len_++;
47 }
48 shift_ = shift;
49 if (shift == 0) {
50 inplace_ = true;
51 return;
52 }
53 inplace_ = allow_inplace;
54 if (!inplace_) {
55 digit_t* digits = new digit_t[len_];
56 storage_.reset(digits);
57 digits_ = digits;
58 }
59 RWDigits rw_view(digits_, len_);
60 LeftShift(rw_view, original, shift_);
61 }
62 ~ShiftedDigits() = default;
63
Reset()64 void Reset() {
65 if (inplace_) {
66 RWDigits rw_view(digits_, len_);
67 RightShift(rw_view, rw_view, shift_);
68 }
69 }
70
shift()71 int shift() { return shift_; }
72
73 private:
74 int shift_;
75 bool inplace_;
76 std::unique_ptr<digit_t[]> storage_;
77 };
78
79 } // namespace bigint
80 } // namespace v8
81
82 #endif // V8_BIGINT_DIV_HELPERS_H_
83