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 #include "src/bigint/digit-arithmetic.h"
7 #include "src/bigint/vector-arithmetic.h"
8
9 namespace v8 {
10 namespace bigint {
11
12 // Z := X * y, where y is a single digit.
MultiplySingle(RWDigits Z,Digits X,digit_t y)13 void ProcessorImpl::MultiplySingle(RWDigits Z, Digits X, digit_t y) {
14 DCHECK(y != 0); // NOLINT(readability/check)
15 digit_t carry = 0;
16 digit_t high = 0;
17 for (int i = 0; i < X.len(); i++) {
18 digit_t new_high;
19 digit_t low = digit_mul(X[i], y, &new_high);
20 Z[i] = digit_add3(low, high, carry, &carry);
21 high = new_high;
22 }
23 AddWorkEstimate(X.len());
24 Z[X.len()] = carry + high;
25 for (int i = X.len() + 1; i < Z.len(); i++) Z[i] = 0;
26 }
27
28 #define BODY(min, max) \
29 for (int j = min; j <= max; j++) { \
30 digit_t high; \
31 digit_t low = digit_mul(X[j], Y[i - j], &high); \
32 digit_t carrybit; \
33 zi = digit_add2(zi, low, &carrybit); \
34 carry += carrybit; \
35 next = digit_add2(next, high, &carrybit); \
36 next_carry += carrybit; \
37 } \
38 Z[i] = zi
39
40 // Z := X * Y.
41 // O(n²) "schoolbook" multiplication algorithm. Optimized to minimize
42 // bounds and overflow checks: rather than looping over X for every digit
43 // of Y (or vice versa), we loop over Z. The {BODY} macro above is what
44 // computes one of Z's digits as a sum of the products of relevant digits
45 // of X and Y. This yields a nearly 2x improvement compared to more obvious
46 // implementations.
47 // This method is *highly* performance sensitive even for the advanced
48 // algorithms, which use this as the base case of their recursive calls.
MultiplySchoolbook(RWDigits Z,Digits X,Digits Y)49 void ProcessorImpl::MultiplySchoolbook(RWDigits Z, Digits X, Digits Y) {
50 DCHECK(IsDigitNormalized(X));
51 DCHECK(IsDigitNormalized(Y));
52 DCHECK(X.len() >= Y.len());
53 DCHECK(Z.len() >= X.len() + Y.len());
54 if (X.len() == 0 || Y.len() == 0) return Z.Clear();
55 digit_t next, next_carry = 0, carry = 0;
56 // Unrolled first iteration: it's trivial.
57 Z[0] = digit_mul(X[0], Y[0], &next);
58 int i = 1;
59 // Unrolled second iteration: a little less setup.
60 if (i < Y.len()) {
61 digit_t zi = next;
62 next = 0;
63 BODY(0, 1);
64 i++;
65 }
66 // Main part: since X.len() >= Y.len() > i, no bounds checks are needed.
67 for (; i < Y.len(); i++) {
68 digit_t zi = digit_add2(next, carry, &carry);
69 next = next_carry + carry;
70 carry = 0;
71 next_carry = 0;
72 BODY(0, i);
73 AddWorkEstimate(i);
74 }
75 // Last part: i exceeds Y now, we have to be careful about bounds.
76 int loop_end = X.len() + Y.len() - 2;
77 for (; i <= loop_end; i++) {
78 int max_x_index = std::min(i, X.len() - 1);
79 int max_y_index = Y.len() - 1;
80 int min_x_index = i - max_y_index;
81 digit_t zi = digit_add2(next, carry, &carry);
82 next = next_carry + carry;
83 carry = 0;
84 next_carry = 0;
85 BODY(min_x_index, max_x_index);
86 AddWorkEstimate(max_x_index - min_x_index);
87 }
88 // Write the last digit, and zero out any extra space in Z.
89 Z[i++] = digit_add2(next, carry, &carry);
90 DCHECK(carry == 0); // NOLINT(readability/check)
91 for (; i < Z.len(); i++) Z[i] = 0;
92 }
93
94 #undef BODY
95
96 } // namespace bigint
97 } // namespace v8
98