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 #include "src/bigint/bigint-internal.h"
6
7 namespace v8 {
8 namespace bigint {
9
10 // Used for checking consistency between library and public header.
11 #if DEBUG
12 #if V8_ADVANCED_BIGINT_ALGORITHMS
13 bool kAdvancedAlgorithmsEnabledInLibrary = true;
14 #else
15 bool kAdvancedAlgorithmsEnabledInLibrary = false;
16 #endif // V8_ADVANCED_BIGINT_ALGORITHMS
17 #endif // DEBUG
18
ProcessorImpl(Platform * platform)19 ProcessorImpl::ProcessorImpl(Platform* platform) : platform_(platform) {}
20
~ProcessorImpl()21 ProcessorImpl::~ProcessorImpl() { delete platform_; }
22
get_and_clear_status()23 Status ProcessorImpl::get_and_clear_status() {
24 Status result = status_;
25 status_ = Status::kOk;
26 return result;
27 }
28
New(Platform * platform)29 Processor* Processor::New(Platform* platform) {
30 ProcessorImpl* impl = new ProcessorImpl(platform);
31 return static_cast<Processor*>(impl);
32 }
33
Destroy()34 void Processor::Destroy() { delete static_cast<ProcessorImpl*>(this); }
35
Multiply(RWDigits Z,Digits X,Digits Y)36 void ProcessorImpl::Multiply(RWDigits Z, Digits X, Digits Y) {
37 X.Normalize();
38 Y.Normalize();
39 if (X.len() == 0 || Y.len() == 0) return Z.Clear();
40 if (X.len() < Y.len()) std::swap(X, Y);
41 if (Y.len() == 1) return MultiplySingle(Z, X, Y[0]);
42 if (Y.len() < kKaratsubaThreshold) return MultiplySchoolbook(Z, X, Y);
43 #if !V8_ADVANCED_BIGINT_ALGORITHMS
44 return MultiplyKaratsuba(Z, X, Y);
45 #else
46 if (Y.len() < kToomThreshold) return MultiplyKaratsuba(Z, X, Y);
47 if (Y.len() < kFftThreshold) return MultiplyToomCook(Z, X, Y);
48 return MultiplyFFT(Z, X, Y);
49 #endif
50 }
51
Divide(RWDigits Q,Digits A,Digits B)52 void ProcessorImpl::Divide(RWDigits Q, Digits A, Digits B) {
53 A.Normalize();
54 B.Normalize();
55 DCHECK(B.len() > 0);
56 int cmp = Compare(A, B);
57 if (cmp < 0) return Q.Clear();
58 if (cmp == 0) {
59 Q[0] = 1;
60 for (int i = 1; i < Q.len(); i++) Q[i] = 0;
61 return;
62 }
63 if (B.len() == 1) {
64 digit_t remainder;
65 return DivideSingle(Q, &remainder, A, B[0]);
66 }
67 if (B.len() < kBurnikelThreshold) {
68 return DivideSchoolbook(Q, RWDigits(nullptr, 0), A, B);
69 }
70 #if !V8_ADVANCED_BIGINT_ALGORITHMS
71 return DivideBurnikelZiegler(Q, RWDigits(nullptr, 0), A, B);
72 #else
73 if (B.len() < kBarrettThreshold || A.len() == B.len()) {
74 DivideBurnikelZiegler(Q, RWDigits(nullptr, 0), A, B);
75 } else {
76 ScratchDigits R(B.len());
77 DivideBarrett(Q, R, A, B);
78 }
79 #endif
80 }
81
Modulo(RWDigits R,Digits A,Digits B)82 void ProcessorImpl::Modulo(RWDigits R, Digits A, Digits B) {
83 A.Normalize();
84 B.Normalize();
85 DCHECK(B.len() > 0);
86 int cmp = Compare(A, B);
87 if (cmp < 0) {
88 for (int i = 0; i < B.len(); i++) R[i] = B[i];
89 for (int i = B.len(); i < R.len(); i++) R[i] = 0;
90 return;
91 }
92 if (cmp == 0) return R.Clear();
93 if (B.len() == 1) {
94 digit_t remainder;
95 DivideSingle(RWDigits(nullptr, 0), &remainder, A, B[0]);
96 R[0] = remainder;
97 for (int i = 1; i < R.len(); i++) R[i] = 0;
98 return;
99 }
100 if (B.len() < kBurnikelThreshold) {
101 return DivideSchoolbook(RWDigits(nullptr, 0), R, A, B);
102 }
103 int q_len = DivideResultLength(A, B);
104 ScratchDigits Q(q_len);
105 #if !V8_ADVANCED_BIGINT_ALGORITHMS
106 return DivideBurnikelZiegler(Q, R, A, B);
107 #else
108 if (B.len() < kBarrettThreshold || A.len() == B.len()) {
109 DivideBurnikelZiegler(Q, R, A, B);
110 } else {
111 DivideBarrett(Q, R, A, B);
112 }
113 #endif
114 }
115
Multiply(RWDigits Z,Digits X,Digits Y)116 Status Processor::Multiply(RWDigits Z, Digits X, Digits Y) {
117 ProcessorImpl* impl = static_cast<ProcessorImpl*>(this);
118 impl->Multiply(Z, X, Y);
119 return impl->get_and_clear_status();
120 }
121
Divide(RWDigits Q,Digits A,Digits B)122 Status Processor::Divide(RWDigits Q, Digits A, Digits B) {
123 ProcessorImpl* impl = static_cast<ProcessorImpl*>(this);
124 impl->Divide(Q, A, B);
125 return impl->get_and_clear_status();
126 }
127
Modulo(RWDigits R,Digits A,Digits B)128 Status Processor::Modulo(RWDigits R, Digits A, Digits B) {
129 ProcessorImpl* impl = static_cast<ProcessorImpl*>(this);
130 impl->Modulo(R, A, B);
131 return impl->get_and_clear_status();
132 }
133
134 } // namespace bigint
135 } // namespace v8
136