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_BIGINT_INTERNAL_H_
6 #define V8_BIGINT_BIGINT_INTERNAL_H_
7
8 #include <memory>
9
10 #include "src/bigint/bigint.h"
11
12 namespace v8 {
13 namespace bigint {
14
15 constexpr int kKaratsubaThreshold = 34;
16 constexpr int kToomThreshold = 193;
17 constexpr int kFftThreshold = 1500;
18 constexpr int kFftInnerThreshold = 200;
19
20 constexpr int kBurnikelThreshold = 57;
21 constexpr int kNewtonInversionThreshold = 50;
22 // kBarrettThreshold is defined in bigint.h.
23
24 constexpr int kToStringFastThreshold = 43;
25 constexpr int kFromStringLargeThreshold = 300;
26
27 class ProcessorImpl : public Processor {
28 public:
29 explicit ProcessorImpl(Platform* platform);
30 ~ProcessorImpl();
31
32 Status get_and_clear_status();
33
34 void Multiply(RWDigits Z, Digits X, Digits Y);
35 void MultiplySingle(RWDigits Z, Digits X, digit_t y);
36 void MultiplySchoolbook(RWDigits Z, Digits X, Digits Y);
37
38 void MultiplyKaratsuba(RWDigits Z, Digits X, Digits Y);
39 void KaratsubaStart(RWDigits Z, Digits X, Digits Y, RWDigits scratch, int k);
40 void KaratsubaChunk(RWDigits Z, Digits X, Digits Y, RWDigits scratch);
41 void KaratsubaMain(RWDigits Z, Digits X, Digits Y, RWDigits scratch, int n);
42
43 void Divide(RWDigits Q, Digits A, Digits B);
44 void DivideSingle(RWDigits Q, digit_t* remainder, Digits A, digit_t b);
45 void DivideSchoolbook(RWDigits Q, RWDigits R, Digits A, Digits B);
46 void DivideBurnikelZiegler(RWDigits Q, RWDigits R, Digits A, Digits B);
47
48 void Modulo(RWDigits R, Digits A, Digits B);
49
50 #if V8_ADVANCED_BIGINT_ALGORITHMS
51 void MultiplyToomCook(RWDigits Z, Digits X, Digits Y);
52 void Toom3Main(RWDigits Z, Digits X, Digits Y);
53
54 void MultiplyFFT(RWDigits Z, Digits X, Digits Y);
55
56 void DivideBarrett(RWDigits Q, RWDigits R, Digits A, Digits B);
57 void DivideBarrett(RWDigits Q, RWDigits R, Digits A, Digits B, Digits I,
58 RWDigits scratch);
59
60 void Invert(RWDigits Z, Digits V, RWDigits scratch);
61 void InvertBasecase(RWDigits Z, Digits V, RWDigits scratch);
62 void InvertNewton(RWDigits Z, Digits V, RWDigits scratch);
63 #endif // V8_ADVANCED_BIGINT_ALGORITHMS
64
65 // {out_length} initially contains the allocated capacity of {out}, and
66 // upon return will be set to the actual length of the result string.
67 void ToString(char* out, int* out_length, Digits X, int radix, bool sign);
68 void ToStringImpl(char* out, int* out_length, Digits X, int radix, bool sign,
69 bool use_fast_algorithm);
70
71 void FromString(RWDigits Z, FromStringAccumulator* accumulator);
72 void FromStringClassic(RWDigits Z, FromStringAccumulator* accumulator);
73 void FromStringLarge(RWDigits Z, FromStringAccumulator* accumulator);
74 void FromStringBasePowerOfTwo(RWDigits Z, FromStringAccumulator* accumulator);
75
should_terminate()76 bool should_terminate() { return status_ == Status::kInterrupted; }
77
78 // Each unit is supposed to represent approximately one CPU {mul} instruction.
79 // Doesn't need to be accurate; we just want to make sure to check for
80 // interrupt requests every now and then (roughly every 10-100 ms; often
81 // enough not to appear stuck, rarely enough not to cause noticeable
82 // overhead).
83 static const uintptr_t kWorkEstimateThreshold = 5000000;
84
AddWorkEstimate(uintptr_t estimate)85 void AddWorkEstimate(uintptr_t estimate) {
86 work_estimate_ += estimate;
87 if (work_estimate_ >= kWorkEstimateThreshold) {
88 work_estimate_ = 0;
89 if (platform_->InterruptRequested()) {
90 status_ = Status::kInterrupted;
91 }
92 }
93 }
94
95 private:
96 uintptr_t work_estimate_{0};
97 Status status_{Status::kOk};
98 Platform* platform_;
99 };
100
101 // These constants are primarily needed for Barrett division in div-barrett.cc,
102 // and they're also needed by fast to-string conversion in tostring.cc.
DivideBarrettScratchSpace(int n)103 constexpr int DivideBarrettScratchSpace(int n) { return n + 2; }
104 // Local values S and W need "n plus a few" digits; U needs 2*n "plus a few".
105 // In all tested cases the "few" were either 2 or 3, so give 5 to be safe.
106 // S and W are not live at the same time.
107 constexpr int kInvertNewtonExtraSpace = 5;
InvertNewtonScratchSpace(int n)108 constexpr int InvertNewtonScratchSpace(int n) {
109 return 3 * n + 2 * kInvertNewtonExtraSpace;
110 }
InvertScratchSpace(int n)111 constexpr int InvertScratchSpace(int n) {
112 return n < kNewtonInversionThreshold ? 2 * n : InvertNewtonScratchSpace(n);
113 }
114
115 #define CHECK(cond) \
116 if (!(cond)) { \
117 std::cerr << __FILE__ << ":" << __LINE__ << ": "; \
118 std::cerr << "Assertion failed: " #cond "\n"; \
119 abort(); \
120 }
121
122 #ifdef DEBUG
123 #define DCHECK(cond) CHECK(cond)
124 #else
125 #define DCHECK(cond) (void(0))
126 #endif
127
128 #define USE(var) ((void)var)
129
130 // RAII memory for a Digits array.
131 class Storage {
132 public:
Storage(int count)133 explicit Storage(int count) : ptr_(new digit_t[count]) {}
134
get()135 digit_t* get() { return ptr_.get(); }
136
137 private:
138 std::unique_ptr<digit_t[]> ptr_;
139 };
140
141 // A writable Digits array with attached storage.
142 class ScratchDigits : public RWDigits {
143 public:
ScratchDigits(int len)144 explicit ScratchDigits(int len) : RWDigits(nullptr, len), storage_(len) {
145 digits_ = storage_.get();
146 }
147
148 private:
149 Storage storage_;
150 };
151
152 } // namespace bigint
153 } // namespace v8
154
155 #endif // V8_BIGINT_BIGINT_INTERNAL_H_
156