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 // Helper functions that operate on individual digits.
6
7 #ifndef V8_BIGINT_DIGIT_ARITHMETIC_H_
8 #define V8_BIGINT_DIGIT_ARITHMETIC_H_
9
10 #include "src/bigint/bigint.h"
11 #include "src/bigint/util.h"
12
13 namespace v8 {
14 namespace bigint {
15
16 static constexpr int kHalfDigitBits = kDigitBits / 2;
17 static constexpr digit_t kHalfDigitBase = digit_t{1} << kHalfDigitBits;
18 static constexpr digit_t kHalfDigitMask = kHalfDigitBase - 1;
19
digit_ismax(digit_t x)20 constexpr bool digit_ismax(digit_t x) { return static_cast<digit_t>(~x) == 0; }
21
22 // {carry} will be set to 0 or 1.
digit_add2(digit_t a,digit_t b,digit_t * carry)23 inline digit_t digit_add2(digit_t a, digit_t b, digit_t* carry) {
24 #if HAVE_TWODIGIT_T
25 twodigit_t result = twodigit_t{a} + b;
26 *carry = result >> kDigitBits;
27 return static_cast<digit_t>(result);
28 #else
29 digit_t result = a + b;
30 *carry = (result < a) ? 1 : 0;
31 return result;
32 #endif
33 }
34
35 // This compiles to slightly better machine code than repeated invocations
36 // of {digit_add2}.
digit_add3(digit_t a,digit_t b,digit_t c,digit_t * carry)37 inline digit_t digit_add3(digit_t a, digit_t b, digit_t c, digit_t* carry) {
38 #if HAVE_TWODIGIT_T
39 twodigit_t result = twodigit_t{a} + b + c;
40 *carry = result >> kDigitBits;
41 return static_cast<digit_t>(result);
42 #else
43 digit_t result = a + b;
44 *carry = (result < a) ? 1 : 0;
45 result += c;
46 if (result < c) *carry += 1;
47 return result;
48 #endif
49 }
50
51 // {borrow} will be set to 0 or 1.
digit_sub(digit_t a,digit_t b,digit_t * borrow)52 inline digit_t digit_sub(digit_t a, digit_t b, digit_t* borrow) {
53 #if HAVE_TWODIGIT_T
54 twodigit_t result = twodigit_t{a} - b;
55 *borrow = (result >> kDigitBits) & 1;
56 return static_cast<digit_t>(result);
57 #else
58 digit_t result = a - b;
59 *borrow = (result > a) ? 1 : 0;
60 return result;
61 #endif
62 }
63
64 // {borrow_out} will be set to 0 or 1.
digit_sub2(digit_t a,digit_t b,digit_t borrow_in,digit_t * borrow_out)65 inline digit_t digit_sub2(digit_t a, digit_t b, digit_t borrow_in,
66 digit_t* borrow_out) {
67 #if HAVE_TWODIGIT_T
68 twodigit_t subtrahend = twodigit_t{b} + borrow_in;
69 twodigit_t result = twodigit_t{a} - subtrahend;
70 *borrow_out = (result >> kDigitBits) & 1;
71 return static_cast<digit_t>(result);
72 #else
73 digit_t result = a - b;
74 *borrow_out = (result > a) ? 1 : 0;
75 if (result < borrow_in) *borrow_out += 1;
76 result -= borrow_in;
77 return result;
78 #endif
79 }
80
81 // Returns the low half of the result. High half is in {high}.
digit_mul(digit_t a,digit_t b,digit_t * high)82 inline digit_t digit_mul(digit_t a, digit_t b, digit_t* high) {
83 #if HAVE_TWODIGIT_T
84 twodigit_t result = twodigit_t{a} * b;
85 *high = result >> kDigitBits;
86 return static_cast<digit_t>(result);
87 #else
88 // Multiply in half-pointer-sized chunks.
89 // For inputs [AH AL]*[BH BL], the result is:
90 //
91 // [AL*BL] // r_low
92 // + [AL*BH] // r_mid1
93 // + [AH*BL] // r_mid2
94 // + [AH*BH] // r_high
95 // = [R4 R3 R2 R1] // high = [R4 R3], low = [R2 R1]
96 //
97 // Where of course we must be careful with carries between the columns.
98 digit_t a_low = a & kHalfDigitMask;
99 digit_t a_high = a >> kHalfDigitBits;
100 digit_t b_low = b & kHalfDigitMask;
101 digit_t b_high = b >> kHalfDigitBits;
102
103 digit_t r_low = a_low * b_low;
104 digit_t r_mid1 = a_low * b_high;
105 digit_t r_mid2 = a_high * b_low;
106 digit_t r_high = a_high * b_high;
107
108 digit_t carry = 0;
109 digit_t low = digit_add3(r_low, r_mid1 << kHalfDigitBits,
110 r_mid2 << kHalfDigitBits, &carry);
111 *high =
112 (r_mid1 >> kHalfDigitBits) + (r_mid2 >> kHalfDigitBits) + r_high + carry;
113 return low;
114 #endif
115 }
116
117 // Returns the quotient.
118 // quotient = (high << kDigitBits + low - remainder) / divisor
digit_div(digit_t high,digit_t low,digit_t divisor,digit_t * remainder)119 static inline digit_t digit_div(digit_t high, digit_t low, digit_t divisor,
120 digit_t* remainder) {
121 #if defined(DCHECK)
122 DCHECK(high < divisor);
123 DCHECK(divisor != 0);
124 #endif
125 #if __x86_64__ && (__GNUC__ || __clang__)
126 digit_t quotient;
127 digit_t rem;
128 __asm__("divq %[divisor]"
129 // Outputs: {quotient} will be in rax, {rem} in rdx.
130 : "=a"(quotient), "=d"(rem)
131 // Inputs: put {high} into rdx, {low} into rax, and {divisor} into
132 // any register or stack slot.
133 : "d"(high), "a"(low), [divisor] "rm"(divisor));
134 *remainder = rem;
135 return quotient;
136 #elif __i386__ && (__GNUC__ || __clang__)
137 digit_t quotient;
138 digit_t rem;
139 __asm__("divl %[divisor]"
140 // Outputs: {quotient} will be in eax, {rem} in edx.
141 : "=a"(quotient), "=d"(rem)
142 // Inputs: put {high} into edx, {low} into eax, and {divisor} into
143 // any register or stack slot.
144 : "d"(high), "a"(low), [divisor] "rm"(divisor));
145 *remainder = rem;
146 return quotient;
147 #else
148 // Adapted from Warren, Hacker's Delight, p. 152.
149 int s = CountLeadingZeros(divisor);
150 #if defined(DCHECK)
151 DCHECK(s != kDigitBits); // {divisor} is not 0.
152 #endif
153 divisor <<= s;
154
155 digit_t vn1 = divisor >> kHalfDigitBits;
156 digit_t vn0 = divisor & kHalfDigitMask;
157 // {s} can be 0. {low >> kDigitBits} would be undefined behavior, so
158 // we mask the shift amount with {kShiftMask}, and the result with
159 // {s_zero_mask} which is 0 if s == 0 and all 1-bits otherwise.
160 static_assert(sizeof(intptr_t) == sizeof(digit_t),
161 "intptr_t and digit_t must have the same size");
162 const int kShiftMask = kDigitBits - 1;
163 digit_t s_zero_mask =
164 static_cast<digit_t>(static_cast<intptr_t>(-s) >> (kDigitBits - 1));
165 digit_t un32 =
166 (high << s) | ((low >> ((kDigitBits - s) & kShiftMask)) & s_zero_mask);
167 digit_t un10 = low << s;
168 digit_t un1 = un10 >> kHalfDigitBits;
169 digit_t un0 = un10 & kHalfDigitMask;
170 digit_t q1 = un32 / vn1;
171 digit_t rhat = un32 - q1 * vn1;
172
173 while (q1 >= kHalfDigitBase || q1 * vn0 > rhat * kHalfDigitBase + un1) {
174 q1--;
175 rhat += vn1;
176 if (rhat >= kHalfDigitBase) break;
177 }
178
179 digit_t un21 = un32 * kHalfDigitBase + un1 - q1 * divisor;
180 digit_t q0 = un21 / vn1;
181 rhat = un21 - q0 * vn1;
182
183 while (q0 >= kHalfDigitBase || q0 * vn0 > rhat * kHalfDigitBase + un0) {
184 q0--;
185 rhat += vn1;
186 if (rhat >= kHalfDigitBase) break;
187 }
188
189 *remainder = (un21 * kHalfDigitBase + un0 - q0 * divisor) >> s;
190 return q1 * kHalfDigitBase + q0;
191 #endif
192 }
193
194 } // namespace bigint
195 } // namespace v8
196
197 #endif // V8_BIGINT_DIGIT_ARITHMETIC_H_
198