OLD | NEW |
---|---|
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 // Copyright 2009 The Go Authors. All rights reserved. | 5 // Copyright 2009 The Go Authors. All rights reserved. |
6 // Use of this source code is governed by a BSD-style | 6 // Use of this source code is governed by a BSD-style |
7 // license that can be found in the LICENSE file. | 7 // license that can be found in the LICENSE file. |
8 | 8 |
9 /* | 9 /* |
10 * Copyright (c) 2003-2005 Tom Wu | 10 * Copyright (c) 2003-2005 Tom Wu |
(...skipping 20 matching lines...) Expand all Loading... | |
31 * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF | 31 * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF |
32 * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT | 32 * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT |
33 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | 33 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
34 * | 34 * |
35 * In addition, the following condition applies: | 35 * In addition, the following condition applies: |
36 * | 36 * |
37 * All redistributions must retain an intact copy of this copyright notice | 37 * All redistributions must retain an intact copy of this copyright notice |
38 * and disclaimer. | 38 * and disclaimer. |
39 */ | 39 */ |
40 | 40 |
41 // A big integer number is represented by a sign, an array of 32-bit unsigned | |
rmacnak
2015/02/04 23:49:14
Nice!
| |
42 // integers in little endian format, and a number of used digits in that array. | |
43 // The code makes sure that an even number of digits is always accessible and | |
44 // meaningful, so that pairs of digits can be processed as 64-bit unsigned | |
45 // numbers on a 64-bit platform. This requires the initialization of a leading | |
46 // zero if the number of used digits is odd. | |
41 class _Bigint extends _IntegerImplementation implements int { | 47 class _Bigint extends _IntegerImplementation implements int { |
42 // Bits per digit. | 48 // Bits per digit. |
43 static const int DIGIT_BITS = 32; | 49 static const int _DIGIT_BITS = 32; |
44 static const int DIGIT_BASE = 1 << DIGIT_BITS; | 50 static const int _DIGIT_BASE = 1 << _DIGIT_BITS; |
45 static const int DIGIT_MASK = (1 << DIGIT_BITS) - 1; | 51 static const int _DIGIT_MASK = (1 << _DIGIT_BITS) - 1; |
46 | 52 |
47 // Bits per half digit. | 53 // Bits per half digit. |
48 static const int DIGIT2_BITS = DIGIT_BITS >> 1; | 54 static const int _DIGIT2_BITS = _DIGIT_BITS >> 1; |
49 static const int DIGIT2_MASK = (1 << DIGIT2_BITS) - 1; | 55 static const int _DIGIT2_MASK = (1 << _DIGIT2_BITS) - 1; |
50 | |
51 // Allocate extra digits so the bigint can be reused. | |
52 static const int EXTRA_DIGITS = 4; | |
53 | 56 |
54 // Min and max of non bigint values. | 57 // Min and max of non bigint values. |
55 static const int MIN_INT64 = (-1) << 63; | 58 static const int _MIN_INT64 = (-1) << 63; |
56 static const int MAX_INT64 = 0x7fffffffffffffff; | 59 static const int _MAX_INT64 = 0x7fffffffffffffff; |
57 | 60 |
58 // Bigint constant values. | 61 // Bigint constant values. |
59 // Note: Not declared as final in order to satisfy optimizer, which expects | 62 // Note: Not declared as final in order to satisfy optimizer, which expects |
60 // constants to be in canonical form (Smi). | 63 // constants to be in canonical form (Smi). |
61 static _Bigint ONE = new _Bigint._fromInt(1); | 64 static _Bigint _MINUS_ONE = new _Bigint._fromInt(-1); |
62 | 65 static _Bigint _ZERO = new _Bigint._fromInt(0); |
63 // Digit conversion table for parsing. | 66 static _Bigint _ONE = new _Bigint._fromInt(1); |
64 static final Map<int, int> DIGIT_TABLE = _createDigitTable(); | |
65 | 67 |
66 // Internal data structure. | 68 // Internal data structure. |
67 // TODO(regis): Remove the 3 native setters below and provide a constructor | |
68 // taking all 3 field values, which is equivalent to making the fields final. | |
69 bool get _neg native "Bigint_getNeg"; | 69 bool get _neg native "Bigint_getNeg"; |
70 void set _neg(bool value) native "Bigint_setNeg"; | |
71 int get _used native "Bigint_getUsed"; | 70 int get _used native "Bigint_getUsed"; |
72 void set _used(int value) native "Bigint_setUsed"; | |
73 Uint32List get _digits native "Bigint_getDigits"; | 71 Uint32List get _digits native "Bigint_getDigits"; |
74 void set _digits(Uint32List value) native "Bigint_setDigits"; | |
75 | 72 |
76 // Factory returning an instance initialized to value 0. | 73 // Factory returning an instance initialized with the given field values. |
77 factory _Bigint() native "Bigint_allocate"; | 74 // The 'digits' array is first clamped and 'used' is reduced accordingly. |
75 // A leading zero digit may be initialized to guarantee that digit pairs can | |
76 // be processed as 64-bit values on 64-bit platforms. | |
77 factory _Bigint(bool neg, int used, Uint32List digits) | |
78 native "Bigint_allocate"; | |
78 | 79 |
79 // Factory returning an instance initialized to an integer value no larger | 80 // Factory returning an instance initialized to an integer value no larger |
80 // than a Mint. | 81 // than a Mint. |
81 factory _Bigint._fromInt(int i) { | 82 factory _Bigint._fromInt(int i) { |
82 assert(i is! _Bigint); | 83 assert(i is! _Bigint); |
83 bool neg; | 84 var neg; |
84 var l, h; | 85 var l, h; |
85 if (i < 0) { | 86 if (i < 0) { |
86 neg = true; | 87 neg = true; |
87 if (i == MIN_INT64) { | 88 if (i == _MIN_INT64) { |
88 l = 0; | 89 l = 0; |
89 h = 0x80000000; | 90 h = 0x80000000; |
90 } else { | 91 } else { |
91 l = (-i) & DIGIT_MASK; | 92 l = (-i) & _DIGIT_MASK; |
92 h = (-i) >> DIGIT_BITS; | 93 h = (-i) >> _DIGIT_BITS; |
93 } | 94 } |
94 } else { | 95 } else { |
95 neg = false; | 96 neg = false; |
96 l = i & DIGIT_MASK; | 97 l = i & _DIGIT_MASK; |
97 h = i >> DIGIT_BITS; | 98 h = i >> _DIGIT_BITS; |
98 } | 99 } |
99 var result = new _Bigint(); | 100 var digits = new Uint32List(2); |
100 result._ensureLength(2); | 101 digits[0] = l; |
101 result._neg = neg; | 102 digits[1] = h; |
102 result._used = 2; | 103 return new _Bigint(neg, 2, digits); |
103 result._digits[0] = l; | |
104 result._digits[1] = h; | |
105 result._clamp(); | |
106 return result; | |
107 } | 104 } |
108 | 105 |
109 // Create digit conversion table for parsing. | 106 // Allocate an array of the given length (+1 for at least one leading zero |
110 static Map<int, int> _createDigitTable() { | 107 // digit if odd) and copy digits[from..to-1] starting at index 0, followed by |
111 Map table = new HashMap(); | 108 // leading zero digits. |
112 int digit, value; | 109 static Uint32List _cloneDigits(Uint32List digits, int from, int to, |
113 digit = "0".codeUnitAt(0); | 110 int length) { |
114 for(value = 0; value <= 9; ++value) table[digit++] = value; | 111 length += length & 1; // Even number of digits. |
115 digit = "a".codeUnitAt(0); | 112 var r_digits = new Uint32List(length); |
116 for(value = 10; value < 36; ++value) table[digit++] = value; | 113 var n = to - from; |
117 digit = "A".codeUnitAt(0); | 114 for (var i = 0; i < n; i++) { |
118 for(value = 10; value < 36; ++value) table[digit++] = value; | 115 r_digits[i] = digits[from + i]; |
119 return table; | 116 } |
117 return r_digits; | |
120 } | 118 } |
121 | 119 |
122 // Return most compact integer (i.e. possibly Smi or Mint). | 120 // Return most compact integer (i.e. possibly Smi or Mint). |
123 // TODO(regis): Intrinsify. | |
124 int _toValidInt() { | 121 int _toValidInt() { |
125 assert(DIGIT_BITS == 32); // Otherwise this code needs to be revised. | 122 assert(_DIGIT_BITS == 32); // Otherwise this code needs to be revised. |
126 var used = _used; | 123 var used = _used; |
127 if (used == 0) return 0; | 124 if (used == 0) return 0; |
128 var digits = _digits; | 125 var digits = _digits; |
129 if (used == 1) return _neg ? -digits[0] : digits[0]; | 126 if (used == 1) return _neg ? -digits[0] : digits[0]; |
130 if (used > 2) return this; | 127 if (used > 2) return this; |
131 if (_neg) { | 128 if (_neg) { |
132 if (digits[1] > 0x80000000) return this; | 129 if (digits[1] > 0x80000000) return this; |
133 if (digits[1] == 0x80000000) { | 130 if (digits[1] == 0x80000000) { |
134 if (digits[0] > 0) return this; | 131 if (digits[0] > 0) return this; |
135 return MIN_INT64; | 132 return _MIN_INT64; |
136 } | 133 } |
137 return -((digits[1] << DIGIT_BITS) | digits[0]); | 134 return -((digits[1] << _DIGIT_BITS) | digits[0]); |
138 } | 135 } |
139 if (digits[1] >= 0x80000000) return this; | 136 if (digits[1] >= 0x80000000) return this; |
140 return (digits[1] << DIGIT_BITS) | digits[0]; | 137 return (digits[1] << _DIGIT_BITS) | digits[0]; |
141 } | 138 } |
142 | 139 |
143 // Conversion from int to bigint. | 140 // Conversion from int to bigint. |
144 _Bigint _toBigint() => this; | 141 _Bigint _toBigint() => this; |
145 | 142 |
146 // Make sure at least 'length' _digits are allocated. | 143 // Return -this. |
147 // Copy existing and used _digits if reallocation is necessary. | 144 _Bigint _negate() { |
148 // Avoid preserving _digits unnecessarily by calling this function with a | 145 var used = _used; |
149 // meaningful _used field. | 146 if (used == 0) { |
150 void _ensureLength(int length) { | 147 return this; |
151 length++; // Account for leading zero for 64-bit processing. | |
152 var digits = _digits; | |
153 if (length > digits.length) { | |
154 var new_digits = new Uint32List(length + EXTRA_DIGITS); | |
155 _digits = new_digits; | |
156 var used = _used; | |
157 if (used > 0) { | |
158 var i = used + 1; // Copy leading zero for 64-bit processing. | |
159 while (--i >= 0) { | |
160 new_digits[i] = digits[i]; | |
161 } | |
162 } | |
163 } | 148 } |
149 return new _Bigint(!_neg, used, _digits); | |
164 } | 150 } |
165 | 151 |
166 // Clamp off excess high _digits. | 152 // Return abs(this). |
167 void _clamp() { | 153 _Bigint _abs() { |
168 var used = _used; | 154 var neg = _neg; |
169 if (used > 0) { | 155 if (!neg) { |
170 var digits = _digits; | 156 return this; |
171 if (digits[used - 1] == 0) { | |
172 do { | |
173 --used; | |
174 } while (used > 0 && digits[used - 1] == 0); | |
175 _used = used; | |
176 } | |
177 digits[used] = 0; // Set leading zero for 64-bit processing. | |
178 } | 157 } |
179 } | 158 return new _Bigint(!neg, _used, _digits); |
180 | |
181 // Copy this to r. | |
182 void _copyTo(_Bigint r) { | |
183 var used = _used; | |
184 if (used > 0) { | |
185 // We could set r._used to 0 in order to avoid preserving digits. However, | |
186 // it would be wrong to do so if this === r. Checking is too expensive. | |
187 // This case does not occur in the current implementation, but we want to | |
188 // remain safe. | |
189 r._ensureLength(used); | |
190 var digits = _digits; | |
191 var r_digits = r._digits; | |
192 var i = used + 1; // Copy leading zero for 64-bit processing. | |
193 while (--i >= 0) { | |
194 r_digits[i] = digits[i]; | |
195 } | |
196 } | |
197 r._used = used; | |
198 r._neg = _neg; | |
199 } | 159 } |
200 | 160 |
201 // Return the bit length of digit x. | 161 // Return the bit length of digit x. |
202 int _nbits(int x) { | 162 static int _nbits(int x) { |
203 var r = 1, t; | 163 var r = 1, t; |
204 if ((t = x >> 16) != 0) { x = t; r += 16; } | 164 if ((t = x >> 16) != 0) { x = t; r += 16; } |
205 if ((t = x >> 8) != 0) { x = t; r += 8; } | 165 if ((t = x >> 8) != 0) { x = t; r += 8; } |
206 if ((t = x >> 4) != 0) { x = t; r += 4; } | 166 if ((t = x >> 4) != 0) { x = t; r += 4; } |
207 if ((t = x >> 2) != 0) { x = t; r += 2; } | 167 if ((t = x >> 2) != 0) { x = t; r += 2; } |
208 if ((x >> 1) != 0) { r += 1; } | 168 if ((x >> 1) != 0) { r += 1; } |
209 return r; | 169 return r; |
210 } | 170 } |
211 | 171 |
212 // r = this << n*DIGIT_BITS. | 172 // Return this << n*_DIGIT_BITS. |
213 void _dlShiftTo(int n, _Bigint r) { | 173 _Bigint _dlShift(int n) { |
214 var used = _used; | 174 var used = _used; |
215 if (used == 0) { | 175 if (used == 0) { |
216 r._used = 0; | 176 return _ZERO; |
217 r._neg = false; | |
218 return; | |
219 } | 177 } |
220 var r_used = used + n; | 178 var r_used = used + n; |
221 r._ensureLength(r_used); | |
222 var digits = _digits; | 179 var digits = _digits; |
223 var r_digits = r._digits; | 180 var r_digits = new Uint32List(r_used + (r_used & 1)); |
224 var i = used + 1; // Copy leading zero for 64-bit processing. | 181 var i = used; |
225 while (--i >= 0) { | 182 while (--i >= 0) { |
226 r_digits[i + n] = digits[i]; | 183 r_digits[i + n] = digits[i]; |
227 } | 184 } |
185 return new _Bigint(_neg, r_used, r_digits); | |
186 } | |
187 | |
188 // r_digits[0..r_used-1] = x_digits[0..x_used-1] << n*_DIGIT_BITS. | |
189 // Return r_used. | |
190 static int _dlShiftDigits(Uint32List x_digits, int x_used, int n, | |
191 Uint32List r_digits) { | |
192 if (x_used == 0) { | |
193 return 0; | |
194 } | |
195 if (n == 0 && r_digits == x_digits) { | |
196 return x_used; | |
197 } | |
198 var r_used = x_used + n; | |
199 assert(r_digits.length >= r_used + (r_used & 1)); | |
200 var i = x_used; | |
201 while (--i >= 0) { | |
202 r_digits[i + n] = x_digits[i]; | |
203 } | |
228 i = n; | 204 i = n; |
229 while (--i >= 0) { | 205 while (--i >= 0) { |
230 r_digits[i] = 0; | 206 r_digits[i] = 0; |
231 } | 207 } |
232 r._used = r_used; | 208 if (r_used.isOdd) { |
233 r._neg = _neg; | 209 r_digits[r_used] = 0; |
210 } | |
211 return r_used; | |
234 } | 212 } |
235 | 213 |
236 // r = this >> n*DIGIT_BITS. | 214 // Return this >> n*_DIGIT_BITS. |
237 void _drShiftTo(int n, _Bigint r) { | 215 _Bigint _drShift(int n) { |
238 var used = _used; | 216 var used = _used; |
239 if (used == 0) { | 217 if (used == 0) { |
240 r._used = 0; | 218 return _ZERO; |
241 r._neg = false; | |
242 return; | |
243 } | 219 } |
244 var r_used = used - n; | 220 var r_used = used - n; |
245 if (r_used <= 0) { | 221 if (r_used <= 0) { |
246 if (_neg) { | 222 return _neg ? _MINUS_ONE : _ZERO; |
247 // Set r to -1. | |
248 r._used = 0; // No digits to preserve. | |
249 r._ensureLength(1); | |
250 r._neg = true; | |
251 r._used = 1; | |
252 r._digits[0] = 1; | |
253 r._digits[1] = 0; // Set leading zero for 64-bit processing. | |
254 } else { | |
255 // Set r to 0. | |
256 r._neg = false; | |
257 r._used = 0; | |
258 } | |
259 return; | |
260 } | 223 } |
261 r._ensureLength(r_used); | |
262 var digits = _digits; | 224 var digits = _digits; |
263 var r_digits = r._digits; | 225 var r_digits = new Uint32List(r_used + (r_used & 1)); |
264 for (var i = n; i < used + 1; i++) { // Copy leading zero for 64-bit proc. | 226 for (var i = n; i < used; i++) { |
265 r_digits[i - n] = digits[i]; | 227 r_digits[i - n] = digits[i]; |
266 } | 228 } |
267 r._used = r_used; | 229 var r = new _Bigint(_neg, r_used, r_digits); |
268 r._neg = _neg; | |
269 if (_neg) { | 230 if (_neg) { |
270 // Round down if any bit was shifted out. | 231 // Round down if any bit was shifted out. |
271 for (var i = 0; i < n; i++) { | 232 for (var i = 0; i < n; i++) { |
272 if (digits[i] != 0) { | 233 if (digits[i] != 0) { |
273 r._subTo(ONE, r); | 234 return r._sub(_ONE); |
274 break; | |
275 } | 235 } |
276 } | 236 } |
277 } | 237 } |
238 return r; | |
278 } | 239 } |
279 | 240 |
280 // r = this << n. | 241 // r_digits[0..r_used-1] = x_digits[0..x_used-1] >> n*_DIGIT_BITS. |
281 void _lShiftTo(int n, _Bigint r) { | 242 // Return r_used. |
282 var ds = n ~/ DIGIT_BITS; | 243 static int _drShiftDigits(Uint32List x_digits, int x_used, int n, |
283 var bs = n % DIGIT_BITS; | 244 Uint32List r_digits) { |
245 var r_used = x_used - n; | |
246 if (r_used <= 0) { | |
247 return 0; | |
248 } | |
249 assert(r_digits.length >= r_used + (r_used & 1)); | |
250 for (var i = n; i < x_used; i++) { | |
251 r_digits[i - n] = x_digits[i]; | |
252 } | |
253 if (r_used.isOdd) { | |
254 r_digits[r_used] = 0; | |
255 } | |
256 return r_used; | |
257 } | |
258 | |
259 // Return this << n. | |
260 _Bigint _lShift(int n) { | |
261 var ds = n ~/ _DIGIT_BITS; | |
262 var bs = n % _DIGIT_BITS; | |
284 if (bs == 0) { | 263 if (bs == 0) { |
285 _dlShiftTo(ds, r); | 264 return _dlShift(ds); |
286 return; | |
287 } | 265 } |
288 var cbs = DIGIT_BITS - bs; | 266 var cbs = _DIGIT_BITS - bs; |
289 var bm = (1 << cbs) - 1; | 267 var bm = (1 << cbs) - 1; |
290 var r_used = _used + ds + 1; | 268 var r_used = _used + ds + 1; |
291 r._ensureLength(r_used); | |
292 var digits = _digits; | 269 var digits = _digits; |
293 var r_digits = r._digits; | 270 var r_digits = new Uint32List(r_used + (r_used & 1)); |
294 var c = 0; | 271 var c = 0; |
295 var i = _used; | 272 var i = _used; |
296 while (--i >= 0) { | 273 while (--i >= 0) { |
297 r_digits[i + ds + 1] = (digits[i] >> cbs) | c; | 274 r_digits[i + ds + 1] = (digits[i] >> cbs) | c; |
298 c = (digits[i] & bm) << bs; | 275 c = (digits[i] & bm) << bs; |
299 } | 276 } |
277 r_digits[ds] = c; | |
278 return new _Bigint(_neg, r_used, r_digits); | |
279 } | |
280 | |
281 // r_digits[0..r_used-1] = x_digits[0..x_used-1] << n. | |
282 // Return r_used. | |
283 static int _lShiftDigits(Uint32List x_digits, int x_used, int n, | |
284 Uint32List r_digits) { | |
285 var ds = n ~/ _DIGIT_BITS; | |
286 var bs = n % _DIGIT_BITS; | |
287 if (bs == 0) { | |
288 return _dlShiftDigits(x_digits, x_used, ds, r_digits); | |
289 } | |
290 var cbs = _DIGIT_BITS - bs; | |
291 var bm = (1 << cbs) - 1; | |
292 var r_used = x_used + ds + 1; | |
293 assert(r_digits.length >= r_used + (r_used & 1)); | |
294 var c = 0; | |
295 var i = x_used; | |
296 while (--i >= 0) { | |
297 r_digits[i + ds + 1] = (x_digits[i] >> cbs) | c; | |
298 c = (x_digits[i] & bm) << bs; | |
299 } | |
300 r_digits[ds] = c; | |
300 i = ds; | 301 i = ds; |
301 while (--i >= 0) { | 302 while (--i >= 0) { |
302 r_digits[i] = 0; | 303 r_digits[i] = 0; |
303 } | 304 } |
304 r_digits[ds] = c; | 305 if (r_used.isOdd) { |
305 r._used = r_used; | 306 r_digits[r_used] = 0; |
306 r._neg = _neg; | 307 } |
307 r._clamp(); | 308 return r_used; |
308 } | 309 } |
309 | 310 |
310 // r = this >> n. | 311 // Return this >> n. |
311 void _rShiftTo(int n, _Bigint r) { | 312 _Bigint _rShift(int n) { |
312 var ds = n ~/ DIGIT_BITS; | 313 var ds = n ~/ _DIGIT_BITS; |
313 var bs = n % DIGIT_BITS; | 314 var bs = n % _DIGIT_BITS; |
314 if (bs == 0) { | 315 if (bs == 0) { |
315 _drShiftTo(ds, r); | 316 return _drShift(ds); |
316 return; | |
317 } | 317 } |
318 var r_used = _used - ds; | 318 var r_used = _used - ds; |
319 if (r_used <= 0) { | 319 if (r_used <= 0) { |
320 if (_neg) { | 320 return _neg ? _MINUS_ONE : _ZERO; |
321 // Set r to -1. | |
322 r._neg = true; | |
323 r._used = 0; // No digits to preserve. | |
324 r._ensureLength(1); | |
325 r._used = 1; | |
326 r._digits[0] = 1; | |
327 r._digits[1] = 0; // Set leading zero for 64-bit processing. | |
328 } else { | |
329 // Set r to 0. | |
330 r._neg = false; | |
331 r._used = 0; | |
332 } | |
333 return; | |
334 } | 321 } |
335 var cbs = DIGIT_BITS - bs; | 322 var cbs = _DIGIT_BITS - bs; |
336 var bm = (1 << bs) - 1; | 323 var bm = (1 << bs) - 1; |
337 r._ensureLength(r_used); | |
338 var digits = _digits; | 324 var digits = _digits; |
339 var r_digits = r._digits; | 325 var r_digits = new Uint32List(r_used + (r_used & 1)); |
340 r_digits[0] = digits[ds] >> bs; | 326 r_digits[0] = digits[ds] >> bs; |
341 var used = _used; | 327 var used = _used; |
342 for (var i = ds + 1; i < used; i++) { | 328 for (var i = ds + 1; i < used; i++) { |
343 r_digits[i - ds - 1] |= (digits[i] & bm) << cbs; | 329 r_digits[i - ds - 1] |= (digits[i] & bm) << cbs; |
344 r_digits[i - ds] = digits[i] >> bs; | 330 r_digits[i - ds] = digits[i] >> bs; |
345 } | 331 } |
346 r._neg = _neg; | 332 var r = new _Bigint(_neg, r_used, r_digits); |
347 r._used = r_used; | |
348 r._clamp(); | |
349 if (_neg) { | 333 if (_neg) { |
350 // Round down if any bit was shifted out. | 334 // Round down if any bit was shifted out. |
351 if ((digits[ds] & bm) != 0) { | 335 if ((digits[ds] & bm) != 0) { |
352 r._subTo(ONE, r); | 336 return r._sub(_ONE); |
353 return; | |
354 } | 337 } |
355 for (var i = 0; i < ds; i++) { | 338 for (var i = 0; i < ds; i++) { |
356 if (digits[i] != 0) { | 339 if (digits[i] != 0) { |
357 r._subTo(ONE, r); | 340 return r._sub(_ONE); |
358 return; | |
359 } | 341 } |
360 } | 342 } |
361 } | 343 } |
344 return r; | |
345 } | |
346 | |
347 // r_digits[0..r_used-1] = x_digits[0..x_used-1] >> n. | |
348 // Return r_used. | |
349 static int _rShiftDigits(Uint32List x_digits, int x_used, int n, | |
350 Uint32List r_digits) { | |
351 var ds = n ~/ _DIGIT_BITS; | |
352 var bs = n % _DIGIT_BITS; | |
353 if (bs == 0) { | |
354 return _drShiftDigits(x_digits, x_used, ds, r_digits); | |
355 } | |
356 var r_used = x_used - ds; | |
357 if (r_used <= 0) { | |
358 return 0; | |
359 } | |
360 var cbs = _DIGIT_BITS - bs; | |
361 var bm = (1 << bs) - 1; | |
362 assert(r_digits.length >= r_used + (r_used & 1)); | |
363 r_digits[0] = x_digits[ds] >> bs; | |
364 for (var i = ds + 1; i < x_used; i++) { | |
365 r_digits[i - ds - 1] |= (x_digits[i] & bm) << cbs; | |
366 r_digits[i - ds] = x_digits[i] >> bs; | |
367 } | |
368 if (r_used.isOdd) { | |
369 r_digits[r_used] = 0; | |
370 } | |
371 return r_used; | |
362 } | 372 } |
363 | 373 |
364 // Return 0 if abs(this) == abs(a). | 374 // Return 0 if abs(this) == abs(a). |
365 // Return a positive number if abs(this) > abs(a). | 375 // Return a positive number if abs(this) > abs(a). |
366 // Return a negative number if abs(this) < abs(a). | 376 // Return a negative number if abs(this) < abs(a). |
367 int _absCompareTo(_Bigint a) { | 377 int _absCompare(_Bigint a) { |
368 var r = _used - a._used; | 378 var r = _used - a._used; |
369 if (r == 0) { | 379 if (r == 0) { |
370 var i = _used; | 380 var i = _used; |
371 var digits = _digits; | 381 var digits = _digits; |
372 var a_digits = a._digits; | 382 var a_digits = a._digits; |
373 while (--i >= 0 && (r = digits[i] - a_digits[i]) == 0); | 383 while (--i >= 0 && (r = digits[i] - a_digits[i]) == 0); |
374 } | 384 } |
375 return r; | 385 return r; |
376 } | 386 } |
377 | 387 |
378 // Return 0 if this == a. | 388 // Return 0 if this == a. |
379 // Return a positive number if this > a. | 389 // Return a positive number if this > a. |
380 // Return a negative number if this < a. | 390 // Return a negative number if this < a. |
381 int _compareTo(_Bigint a) { | 391 int _compare(_Bigint a) { |
382 var r; | |
383 if (_neg == a._neg) { | 392 if (_neg == a._neg) { |
384 r = _absCompareTo(a); | 393 var r = _absCompare(a); |
385 if (_neg) { | 394 return _neg ? -r : r; |
386 r = -r; | 395 } |
387 } | 396 return _neg ? -1 : 1; |
388 } else if (_neg) { | 397 } |
389 r = -1; | 398 |
390 } else { | 399 // Compare digits[0..used-1] with a_digits[0..a_used-1]. |
391 r = 1; | 400 // Return 0 if equal. |
401 // Return a positive number if larger. | |
402 // Return a negative number if smaller. | |
403 static int _compareDigits(Uint32List digits, int used, | |
404 Uint32List a_digits, int a_used) { | |
405 var r = used - a_used; | |
406 if (r == 0) { | |
407 var i = a_used; | |
408 while (--i >= 0 && (r = digits[i] - a_digits[i]) == 0); | |
392 } | 409 } |
393 return r; | 410 return r; |
394 } | 411 } |
395 | 412 |
396 // r_digits[0..used] = digits[0..used-1] + a_digits[0..a_used-1]. | 413 // r_digits[0..used] = digits[0..used-1] + a_digits[0..a_used-1]. |
397 // used >= a_used > 0. | 414 // used >= a_used > 0. |
415 // Note: Intrinsics on 64-bit platforms process digit pairs at even indices. | |
398 static void _absAdd(Uint32List digits, int used, | 416 static void _absAdd(Uint32List digits, int used, |
399 Uint32List a_digits, int a_used, | 417 Uint32List a_digits, int a_used, |
400 Uint32List r_digits) { | 418 Uint32List r_digits) { |
419 assert(used >= a_used && a_used > 0); | |
420 // Verify that digit pairs are accessible for 64-bit processing. | |
421 assert(digits.length > ((used - 1) | 1)); | |
422 assert(a_digits.length > ((a_used - 1) | 1)); | |
423 assert(r_digits.length > (used | 1)); | |
401 var c = 0; | 424 var c = 0; |
402 for (var i = 0; i < a_used; i++) { | 425 for (var i = 0; i < a_used; i++) { |
403 c += digits[i] + a_digits[i]; | 426 c += digits[i] + a_digits[i]; |
404 r_digits[i] = c & DIGIT_MASK; | 427 r_digits[i] = c & _DIGIT_MASK; |
405 c >>= DIGIT_BITS; | 428 c >>= _DIGIT_BITS; |
406 } | 429 } |
407 for (var i = a_used; i < used; i++) { | 430 for (var i = a_used; i < used; i++) { |
408 c += digits[i]; | 431 c += digits[i]; |
409 r_digits[i] = c & DIGIT_MASK; | 432 r_digits[i] = c & _DIGIT_MASK; |
410 c >>= DIGIT_BITS; | 433 c >>= _DIGIT_BITS; |
411 } | 434 } |
412 r_digits[used] = c; | 435 r_digits[used] = c; |
413 } | 436 } |
414 | 437 |
415 // r_digits[0..used-1] = digits[0..used-1] - a_digits[0..a_used-1]. | 438 // r_digits[0..used-1] = digits[0..used-1] - a_digits[0..a_used-1]. |
416 // used >= a_used > 0. | 439 // used >= a_used > 0. |
440 // Note: Intrinsics on 64-bit platforms process digit pairs at even indices. | |
417 static void _absSub(Uint32List digits, int used, | 441 static void _absSub(Uint32List digits, int used, |
418 Uint32List a_digits, int a_used, | 442 Uint32List a_digits, int a_used, |
419 Uint32List r_digits) { | 443 Uint32List r_digits) { |
444 assert(used >= a_used && a_used > 0); | |
445 // Verify that digit pairs are accessible for 64-bit processing. | |
446 assert(digits.length > ((used - 1) | 1)); | |
447 assert(a_digits.length > ((a_used - 1) | 1)); | |
448 assert(r_digits.length > ((used - 1) | 1)); | |
420 var c = 0; | 449 var c = 0; |
421 for (var i = 0; i < a_used; i++) { | 450 for (var i = 0; i < a_used; i++) { |
422 c += digits[i] - a_digits[i]; | 451 c += digits[i] - a_digits[i]; |
423 r_digits[i] = c & DIGIT_MASK; | 452 r_digits[i] = c & _DIGIT_MASK; |
424 c >>= DIGIT_BITS; | 453 c >>= _DIGIT_BITS; |
425 } | 454 } |
426 for (var i = a_used; i < used; i++) { | 455 for (var i = a_used; i < used; i++) { |
427 c += digits[i]; | 456 c += digits[i]; |
428 r_digits[i] = c & DIGIT_MASK; | 457 r_digits[i] = c & _DIGIT_MASK; |
429 c >>= DIGIT_BITS; | 458 c >>= _DIGIT_BITS; |
430 } | 459 } |
431 } | 460 } |
432 | 461 |
433 // r = abs(this) + abs(a). | 462 // Return abs(this) + abs(a) with sign set according to neg. |
434 void _absAddTo(_Bigint a, _Bigint r) { | 463 _Bigint _absAddSetSign(_Bigint a, bool neg) { |
435 var used = _used; | 464 var used = _used; |
436 var a_used = a._used; | 465 var a_used = a._used; |
437 if (used < a_used) { | 466 if (used < a_used) { |
438 a._absAddTo(this, r); | 467 return a._absAddSetSign(this, neg); |
439 return; | |
440 } | 468 } |
441 if (used == 0) { | 469 if (used == 0) { |
442 // Set r to 0. | 470 assert(!neg); |
443 r._neg = false; | 471 return _ZERO; |
444 r._used = 0; | |
445 return; | |
446 } | 472 } |
447 if (a_used == 0) { | 473 if (a_used == 0) { |
448 _copyTo(r); | 474 return _neg == neg ? this : this._negate(); |
449 return; | |
450 } | 475 } |
451 r._ensureLength(used + 1); | 476 var r_used = used + 1; |
452 _absAdd(_digits, used, a._digits, a_used, r._digits); | 477 var r_digits = new Uint32List(r_used + (r_used & 1)); |
453 r._used = used + 1; | 478 _absAdd(_digits, used, a._digits, a_used, r_digits); |
454 r._clamp(); | 479 return new _Bigint(neg, r_used, r_digits); |
455 } | 480 } |
456 | 481 |
457 // r = abs(this) - abs(a), with abs(this) >= abs(a). | 482 // Return abs(this) - abs(a) with sign set according to neg. |
458 void _absSubTo(_Bigint a, _Bigint r) { | 483 // Requirement: abs(this) >= abs(a). |
459 assert(_absCompareTo(a) >= 0); | 484 _Bigint _absSubSetSign(_Bigint a, bool neg) { |
485 assert(_absCompare(a) >= 0); | |
460 var used = _used; | 486 var used = _used; |
461 if (used == 0) { | 487 if (used == 0) { |
462 // Set r to 0. | 488 assert(!neg); |
463 r._neg = false; | 489 return _ZERO; |
464 r._used = 0; | |
465 return; | |
466 } | 490 } |
467 var a_used = a._used; | 491 var a_used = a._used; |
468 if (a_used == 0) { | 492 if (a_used == 0) { |
469 _copyTo(r); | 493 return _neg == neg ? this : this._negate(); |
470 return; | |
471 } | 494 } |
472 r._ensureLength(used); | 495 var r_digits = new Uint32List(used + (used & 1)); |
473 _absSub(_digits, used, a._digits, a_used, r._digits); | 496 _absSub(_digits, used, a._digits, a_used, r_digits); |
474 r._used = used; | 497 return new _Bigint(neg, used, r_digits); |
475 r._clamp(); | |
476 } | 498 } |
477 | 499 |
478 // r = abs(this) & abs(a). | 500 // Return abs(this) & abs(a) with sign set according to neg. |
479 void _absAndTo(_Bigint a, _Bigint r) { | 501 _Bigint _absAndSetSign(_Bigint a, bool neg) { |
480 var r_used = (_used < a._used) ? _used : a._used; | 502 var r_used = (_used < a._used) ? _used : a._used; |
481 r._ensureLength(r_used); | |
482 var digits = _digits; | 503 var digits = _digits; |
483 var a_digits = a._digits; | 504 var a_digits = a._digits; |
484 var r_digits = r._digits; | 505 var r_digits = new Uint32List(r_used + (r_used & 1)); |
485 for (var i = 0; i < r_used; i++) { | 506 for (var i = 0; i < r_used; i++) { |
486 r_digits[i] = digits[i] & a_digits[i]; | 507 r_digits[i] = digits[i] & a_digits[i]; |
487 } | 508 } |
488 r._used = r_used; | 509 return new _Bigint(neg, r_used, r_digits); |
489 r._clamp(); | |
490 } | 510 } |
491 | 511 |
492 // r = abs(this) &~ abs(a). | 512 // Return abs(this) &~ abs(a) with sign set according to neg. |
493 void _absAndNotTo(_Bigint a, _Bigint r) { | 513 _Bigint _absAndNotSetSign(_Bigint a, bool neg) { |
494 var r_used = _used; | 514 var r_used = _used; |
495 r._ensureLength(r_used); | |
496 var digits = _digits; | 515 var digits = _digits; |
497 var a_digits = a._digits; | 516 var a_digits = a._digits; |
498 var r_digits = r._digits; | 517 var r_digits = new Uint32List(r_used + (r_used & 1)); |
499 var m = (r_used < a._used) ? r_used : a._used; | 518 var m = (r_used < a._used) ? r_used : a._used; |
500 for (var i = 0; i < m; i++) { | 519 for (var i = 0; i < m; i++) { |
501 r_digits[i] = digits[i] &~ a_digits[i]; | 520 r_digits[i] = digits[i] &~ a_digits[i]; |
502 } | 521 } |
503 for (var i = m; i < r_used; i++) { | 522 for (var i = m; i < r_used; i++) { |
504 r_digits[i] = digits[i]; | 523 r_digits[i] = digits[i]; |
505 } | 524 } |
506 r._used = r_used; | 525 return new _Bigint(neg, r_used, r_digits); |
507 r._clamp(); | |
508 } | 526 } |
509 | 527 |
510 // r = abs(this) | abs(a). | 528 // Return abs(this) | abs(a) with sign set according to neg. |
511 void _absOrTo(_Bigint a, _Bigint r) { | 529 _Bigint _absOrSetSign(_Bigint a, bool neg) { |
512 var used = _used; | 530 var used = _used; |
513 var a_used = a._used; | 531 var a_used = a._used; |
514 var r_used = (used > a_used) ? used : a_used; | 532 var r_used = (used > a_used) ? used : a_used; |
515 r._ensureLength(r_used); | |
516 var digits = _digits; | 533 var digits = _digits; |
517 var a_digits = a._digits; | 534 var a_digits = a._digits; |
518 var r_digits = r._digits; | 535 var r_digits = new Uint32List(r_used + (r_used & 1)); |
519 var l, m; | 536 var l, m; |
520 if (used < a_used) { | 537 if (used < a_used) { |
521 l = a; | 538 l = a; |
522 m = used; | 539 m = used; |
523 } else { | 540 } else { |
524 l = this; | 541 l = this; |
525 m = a_used; | 542 m = a_used; |
526 } | 543 } |
527 for (var i = 0; i < m; i++) { | 544 for (var i = 0; i < m; i++) { |
528 r_digits[i] = digits[i] | a_digits[i]; | 545 r_digits[i] = digits[i] | a_digits[i]; |
529 } | 546 } |
530 var l_digits = l._digits; | 547 var l_digits = l._digits; |
531 for (var i = m; i < r_used; i++) { | 548 for (var i = m; i < r_used; i++) { |
532 r_digits[i] = l_digits[i]; | 549 r_digits[i] = l_digits[i]; |
533 } | 550 } |
534 r._used = r_used; | 551 return new _Bigint(neg, r_used, r_digits); |
535 r._clamp(); | |
536 } | 552 } |
537 | 553 |
538 // r = abs(this) ^ abs(a). | 554 // Return abs(this) ^ abs(a) with sign set according to neg. |
539 void _absXorTo(_Bigint a, _Bigint r) { | 555 _Bigint _absXorSetSign(_Bigint a, bool neg) { |
540 var used = _used; | 556 var used = _used; |
541 var a_used = a._used; | 557 var a_used = a._used; |
542 var r_used = (used > a_used) ? used : a_used; | 558 var r_used = (used > a_used) ? used : a_used; |
543 r._ensureLength(r_used); | |
544 var digits = _digits; | 559 var digits = _digits; |
545 var a_digits = a._digits; | 560 var a_digits = a._digits; |
546 var r_digits = r._digits; | 561 var r_digits = new Uint32List(r_used + (r_used & 1)); |
547 var l, m; | 562 var l, m; |
548 if (used < a_used) { | 563 if (used < a_used) { |
549 l = a; | 564 l = a; |
550 m = used; | 565 m = used; |
551 } else { | 566 } else { |
552 l = this; | 567 l = this; |
553 m = a_used; | 568 m = a_used; |
554 } | 569 } |
555 for (var i = 0; i < m; i++) { | 570 for (var i = 0; i < m; i++) { |
556 r_digits[i] = digits[i] ^ a_digits[i]; | 571 r_digits[i] = digits[i] ^ a_digits[i]; |
557 } | 572 } |
558 var l_digits = l._digits; | 573 var l_digits = l._digits; |
559 for (var i = m; i < r_used; i++) { | 574 for (var i = m; i < r_used; i++) { |
560 r_digits[i] = l_digits[i]; | 575 r_digits[i] = l_digits[i]; |
561 } | 576 } |
562 r._used = r_used; | 577 return new _Bigint(neg, r_used, r_digits); |
563 r._clamp(); | |
564 } | 578 } |
565 | 579 |
566 // Return r = this & a. | 580 // Return this & a. |
567 _Bigint _andTo(_Bigint a, _Bigint r) { | 581 _Bigint _and(_Bigint a) { |
568 if (_neg == a._neg) { | 582 if (_neg == a._neg) { |
569 if (_neg) { | 583 if (_neg) { |
570 // (-this) & (-a) == ~(this-1) & ~(a-1) | 584 // (-this) & (-a) == ~(this-1) & ~(a-1) |
571 // == ~((this-1) | (a-1)) | 585 // == ~((this-1) | (a-1)) |
572 // == -(((this-1) | (a-1)) + 1) | 586 // == -(((this-1) | (a-1)) + 1) |
573 _Bigint t1 = new _Bigint(); | 587 _Bigint t1 = _absSubSetSign(_ONE, true); |
574 _absSubTo(ONE, t1); | 588 _Bigint a1 = a._absSubSetSign(_ONE, true); |
575 _Bigint a1 = new _Bigint(); | 589 // Result cannot be zero if this and a are negative. |
576 a._absSubTo(ONE, a1); | 590 return t1._absOrSetSign(a1, true)._absAddSetSign(_ONE, true); |
577 t1._absOrTo(a1, r); | |
578 r._absAddTo(ONE, r); | |
579 r._neg = true; // r cannot be zero if this and a are negative. | |
580 return r; | |
581 } | 591 } |
582 _absAndTo(a, r); | 592 return _absAndSetSign(a, false); |
583 r._neg = false; | |
584 return r; | |
585 } | 593 } |
586 // _neg != a._neg | 594 // _neg != a._neg |
587 var p, n; | 595 var p, n; |
588 if (_neg) { | 596 if (_neg) { |
589 p = a; | 597 p = a; |
590 n = this; | 598 n = this; |
591 } else { // & is symmetric. | 599 } else { // & is symmetric. |
592 p = this; | 600 p = this; |
593 n = a; | 601 n = a; |
594 } | 602 } |
595 // p & (-n) == p & ~(n-1) == p &~ (n-1) | 603 // p & (-n) == p & ~(n-1) == p &~ (n-1) |
596 _Bigint n1 = new _Bigint(); | 604 _Bigint n1 = n._absSubSetSign(_ONE, false); |
597 n._absSubTo(ONE, n1); | 605 return p._absAndNotSetSign(n1, false); |
598 p._absAndNotTo(n1, r); | |
599 r._neg = false; | |
600 return r; | |
601 } | 606 } |
602 | 607 |
603 // Return r = this &~ a. | 608 // Return this &~ a. |
604 _Bigint _andNotTo(_Bigint a, _Bigint r) { | 609 _Bigint _andNot(_Bigint a) { |
605 if (_neg == a._neg) { | 610 if (_neg == a._neg) { |
606 if (_neg) { | 611 if (_neg) { |
607 // (-this) &~ (-a) == ~(this-1) &~ ~(a-1) | 612 // (-this) &~ (-a) == ~(this-1) &~ ~(a-1) |
608 // == ~(this-1) & (a-1) | 613 // == ~(this-1) & (a-1) |
609 // == (a-1) &~ (this-1) | 614 // == (a-1) &~ (this-1) |
610 _Bigint t1 = new _Bigint(); | 615 _Bigint t1 = _absSubSetSign(_ONE, true); |
611 _absSubTo(ONE, t1); | 616 _Bigint a1 = a._absSubSetSign(_ONE, true); |
612 _Bigint a1 = new _Bigint(); | 617 return a1._absAndNotSetSign(t1, false); |
613 a._absSubTo(ONE, a1); | |
614 a1._absAndNotTo(t1, r); | |
615 r._neg = false; | |
616 return r; | |
617 } | 618 } |
618 _absAndNotTo(a, r); | 619 return _absAndNotSetSign(a, false); |
619 r._neg = false; | |
620 return r; | |
621 } | 620 } |
622 if (_neg) { | 621 if (_neg) { |
623 // (-this) &~ a == ~(this-1) &~ a | 622 // (-this) &~ a == ~(this-1) &~ a |
624 // == ~(this-1) & ~a | 623 // == ~(this-1) & ~a |
625 // == ~((this-1) | a) | 624 // == ~((this-1) | a) |
626 // == -(((this-1) | a) + 1) | 625 // == -(((this-1) | a) + 1) |
627 _Bigint t1 = new _Bigint(); | 626 _Bigint t1 = _absSubSetSign(_ONE, true); |
628 _absSubTo(ONE, t1); | 627 // Result cannot be zero if this is negative and a is positive. |
629 t1._absOrTo(a, r); | 628 return t1._absOrSetSign(a, true)._absAddSetSign(_ONE, true); |
630 r._absAddTo(ONE, r); | |
631 r._neg = true; // r cannot be zero if this is negative and a is positive. | |
632 return r; | |
633 } | 629 } |
634 // this &~ (-a) == this &~ ~(a-1) == this & (a-1) | 630 // this &~ (-a) == this &~ ~(a-1) == this & (a-1) |
635 _Bigint a1 = new _Bigint(); | 631 _Bigint a1 = a._absSubSetSign(_ONE, true); |
636 a._absSubTo(ONE, a1); | 632 return _absAndSetSign(a1, false); |
637 _absAndTo(a1, r); | |
638 r._neg = false; | |
639 return r; | |
640 } | 633 } |
641 | 634 |
642 // Return r = this | a. | 635 // Return this | a. |
643 _Bigint _orTo(_Bigint a, _Bigint r) { | 636 _Bigint _or(_Bigint a) { |
644 if (_neg == a._neg) { | 637 if (_neg == a._neg) { |
645 if (_neg) { | 638 if (_neg) { |
646 // (-this) | (-a) == ~(this-1) | ~(a-1) | 639 // (-this) | (-a) == ~(this-1) | ~(a-1) |
647 // == ~((this-1) & (a-1)) | 640 // == ~((this-1) & (a-1)) |
648 // == -(((this-1) & (a-1)) + 1) | 641 // == -(((this-1) & (a-1)) + 1) |
649 _Bigint t1 = new _Bigint(); | 642 _Bigint t1 = _absSubSetSign(_ONE, true); |
650 _absSubTo(ONE, t1); | 643 _Bigint a1 = a._absSubSetSign(_ONE, true); |
651 _Bigint a1 = new _Bigint(); | 644 // Result cannot be zero if this and a are negative. |
652 a._absSubTo(ONE, a1); | 645 return t1._absAndSetSign(a1, true)._absAddSetSign(_ONE, true); |
653 t1._absAndTo(a1, r); | |
654 r._absAddTo(ONE, r); | |
655 r._neg = true; // r cannot be zero if this and a are negative. | |
656 return r; | |
657 } | 646 } |
658 _absOrTo(a, r); | 647 return _absOrSetSign(a, false); |
659 r._neg = false; | |
660 return r; | |
661 } | 648 } |
662 // _neg != a._neg | 649 // _neg != a._neg |
663 var p, n; | 650 var p, n; |
664 if (_neg) { | 651 if (_neg) { |
665 p = a; | 652 p = a; |
666 n = this; | 653 n = this; |
667 } else { // | is symmetric. | 654 } else { // | is symmetric. |
668 p = this; | 655 p = this; |
669 n = a; | 656 n = a; |
670 } | 657 } |
671 // p | (-n) == p | ~(n-1) == ~((n-1) &~ p) == -(~((n-1) &~ p) + 1) | 658 // p | (-n) == p | ~(n-1) == ~((n-1) &~ p) == -(~((n-1) &~ p) + 1) |
672 _Bigint n1 = new _Bigint(); | 659 _Bigint n1 = n._absSubSetSign(_ONE, true); |
673 n._absSubTo(ONE, n1); | 660 // Result cannot be zero if only one of this or a is negative. |
674 n1._absAndNotTo(p, r); | 661 return n1._absAndNotSetSign(p, true)._absAddSetSign(_ONE, true); |
675 r._absAddTo(ONE, r); | |
676 r._neg = true; // r cannot be zero if only one of this or a is negative. | |
677 return r; | |
678 } | 662 } |
679 | 663 |
680 // Return r = this ^ a. | 664 // Return this ^ a. |
681 _Bigint _xorTo(_Bigint a, _Bigint r) { | 665 _Bigint _xor(_Bigint a) { |
682 if (_neg == a._neg) { | 666 if (_neg == a._neg) { |
683 if (_neg) { | 667 if (_neg) { |
684 // (-this) ^ (-a) == ~(this-1) ^ ~(a-1) == (this-1) ^ (a-1) | 668 // (-this) ^ (-a) == ~(this-1) ^ ~(a-1) == (this-1) ^ (a-1) |
685 _Bigint t1 = new _Bigint(); | 669 _Bigint t1 = _absSubSetSign(_ONE, true); |
686 _absSubTo(ONE, t1); | 670 _Bigint a1 = a._absSubSetSign(_ONE, true); |
687 _Bigint a1 = new _Bigint(); | 671 return t1._absXorSetSign(a1, false); |
688 a._absSubTo(ONE, a1); | |
689 t1._absXorTo(a1, r); | |
690 r._neg = false; | |
691 return r; | |
692 } | 672 } |
693 _absXorTo(a, r); | 673 return _absXorSetSign(a, false); |
694 r._neg = false; | |
695 return r; | |
696 } | 674 } |
697 // _neg != a._neg | 675 // _neg != a._neg |
698 var p, n; | 676 var p, n; |
699 if (_neg) { | 677 if (_neg) { |
700 p = a; | 678 p = a; |
701 n = this; | 679 n = this; |
702 } else { // ^ is symmetric. | 680 } else { // ^ is symmetric. |
703 p = this; | 681 p = this; |
704 n = a; | 682 n = a; |
705 } | 683 } |
706 // p ^ (-n) == p ^ ~(n-1) == ~(p ^ (n-1)) == -((p ^ (n-1)) + 1) | 684 // p ^ (-n) == p ^ ~(n-1) == ~(p ^ (n-1)) == -((p ^ (n-1)) + 1) |
707 _Bigint n1 = new _Bigint(); | 685 _Bigint n1 = n._absSubSetSign(_ONE, true); |
708 n._absSubTo(ONE, n1); | 686 // Result cannot be zero if only one of this or a is negative. |
709 p._absXorTo(n1, r); | 687 return p._absXorSetSign(n1, true)._absAddSetSign(_ONE, true); |
710 r._absAddTo(ONE, r); | |
711 r._neg = true; // r cannot be zero if only one of this or a is negative. | |
712 return r; | |
713 } | 688 } |
714 | 689 |
715 // Return r = ~this. | 690 // Return ~this. |
716 _Bigint _notTo(_Bigint r) { | 691 _Bigint _not() { |
717 if (_neg) { | 692 if (_neg) { |
718 // ~(-this) == ~(~(this-1)) == this-1 | 693 // ~(-this) == ~(~(this-1)) == this-1 |
719 _absSubTo(ONE, r); | 694 return _absSubSetSign(_ONE, false); |
720 r._neg = false; | |
721 return r; | |
722 } | 695 } |
723 // ~this == -this-1 == -(this+1) | 696 // ~this == -this-1 == -(this+1) |
724 _absAddTo(ONE, r); | 697 // Result cannot be zero if this is positive. |
725 r._neg = true; // r cannot be zero if this is positive. | 698 return _absAddSetSign(_ONE, true); |
726 return r; | |
727 } | 699 } |
728 | 700 |
729 // Return r = this + a. | 701 // Return this + a. |
730 _Bigint _addTo(_Bigint a, _Bigint r) { | 702 _Bigint _add(_Bigint a) { |
731 var r_neg = _neg; | 703 var neg = _neg; |
732 if (_neg == a._neg) { | 704 if (neg == a._neg) { |
733 // this + a == this + a | 705 // this + a == this + a |
734 // (-this) + (-a) == -(this + a) | 706 // (-this) + (-a) == -(this + a) |
735 _absAddTo(a, r); | 707 return _absAddSetSign(a, neg); |
736 } else { | |
737 // this + (-a) == this - a == -(this - a) | |
738 // (-this) + a == a - this == -(this - a) | |
739 if (_absCompareTo(a) >= 0) { | |
740 _absSubTo(a, r); | |
741 } else { | |
742 r_neg = !r_neg; | |
743 a._absSubTo(this, r); | |
744 } | |
745 } | 708 } |
746 » r._neg = r_neg; | 709 // this + (-a) == this - a == -(this - a) |
747 return r; | 710 // (-this) + a == a - this == -(this - a) |
711 if (_absCompare(a) >= 0) { | |
712 return _absSubSetSign(a, neg); | |
713 } | |
714 return a._absSubSetSign(this, !neg); | |
748 } | 715 } |
749 | 716 |
750 // Return r = this - a. | 717 // Return this - a. |
751 _Bigint _subTo(_Bigint a, _Bigint r) { | 718 _Bigint _sub(_Bigint a) { |
752 » var r_neg = _neg; | 719 var neg = _neg; |
753 if (_neg != a._neg) { | 720 if (neg != a._neg) { |
754 » » // this - (-a) == this + a | 721 // this - (-a) == this + a |
755 » » // (-this) - a == -(this + a) | 722 // (-this) - a == -(this + a) |
756 _absAddTo(a, r); | 723 return _absAddSetSign(a, neg); |
757 » } else { | |
758 » » // this - a == this - a == -(this - a) | |
759 » » // (-this) - (-a) == a - this == -(this - a) | |
760 if (_absCompareTo(a) >= 0) { | |
761 _absSubTo(a, r); | |
762 » » } else { | |
763 r_neg = !r_neg; | |
764 a._absSubTo(this, r); | |
765 } | |
766 } | 724 } |
767 » r._neg = r_neg; | 725 // this - a == this - a == -(this - a) |
768 return r; | 726 // (-this) - (-a) == a - this == -(this - a) |
727 if (_absCompare(a) >= 0) { | |
728 return _absSubSetSign(a, neg); | |
729 } | |
730 return a._absSubSetSign(this, !neg); | |
769 } | 731 } |
770 | 732 |
771 // Multiply and accumulate. | 733 // Multiply and accumulate. |
772 // Input: | 734 // Input: |
773 // x_digits[xi]: multiplier digit x. | 735 // x_digits[xi]: multiplier digit x. |
774 // m_digits[i..i+n-1]: multiplicand digits. | 736 // m_digits[i..i+n-1]: multiplicand digits. |
775 // a_digits[j..j+n-1]: accumulator digits. | 737 // a_digits[j..j+n-1]: accumulator digits. |
776 // Operation: | 738 // Operation: |
777 // a_digits[j..j+n] += x_digits[xi]*m_digits[i..i+n-1]. | 739 // a_digits[j..j+n] += x_digits[xi]*m_digits[i..i+n-1]. |
778 // return 1. | 740 // return 1. |
779 // Note: intrinsics on 64-bit platform may process a digit pair: | 741 // Note: Intrinsics on 64-bit platforms process digit pairs at even indices |
780 // a_digits[j..j+n] += x_digits[xi..xi+1]*m_digits[i..i+n-1]. | 742 // and return 2. |
781 // return 2. | |
782 static int _mulAdd(Uint32List x_digits, int xi, | 743 static int _mulAdd(Uint32List x_digits, int xi, |
783 Uint32List m_digits, int i, | 744 Uint32List m_digits, int i, |
784 Uint32List a_digits, int j, int n) { | 745 Uint32List a_digits, int j, int n) { |
746 // Verify that digit pairs are accessible for 64-bit processing. | |
747 assert(x_digits.length > (xi | 1)); | |
748 assert(m_digits.length > ((i + n - 1) | 1)); | |
749 assert(a_digits.length > ((j + n) | 1)); | |
785 int x = x_digits[xi]; | 750 int x = x_digits[xi]; |
786 if (x == 0) { | 751 if (x == 0) { |
787 // No-op if x is 0. | 752 // No-op if x is 0. |
788 return 1; | 753 return 1; |
789 } | 754 } |
790 int c = 0; | 755 int c = 0; |
791 int xl = x & DIGIT2_MASK; | 756 int xl = x & _DIGIT2_MASK; |
792 int xh = x >> DIGIT2_BITS; | 757 int xh = x >> _DIGIT2_BITS; |
793 while (--n >= 0) { | 758 while (--n >= 0) { |
794 int l = m_digits[i] & DIGIT2_MASK; | 759 int l = m_digits[i] & _DIGIT2_MASK; |
795 int h = m_digits[i++] >> DIGIT2_BITS; | 760 int h = m_digits[i++] >> _DIGIT2_BITS; |
796 int m = xh*l + h*xl; | 761 int m = xh*l + h*xl; |
797 l = xl*l + ((m & DIGIT2_MASK) << DIGIT2_BITS) + a_digits[j] + c; | 762 l = xl*l + ((m & _DIGIT2_MASK) << _DIGIT2_BITS) + a_digits[j] + c; |
798 c = (l >> DIGIT_BITS) + (m >> DIGIT2_BITS) + xh*h; | 763 c = (l >> _DIGIT_BITS) + (m >> _DIGIT2_BITS) + xh*h; |
799 a_digits[j++] = l & DIGIT_MASK; | 764 a_digits[j++] = l & _DIGIT_MASK; |
800 } | 765 } |
801 while (c != 0) { | 766 while (c != 0) { |
802 int l = a_digits[j] + c; | 767 int l = a_digits[j] + c; |
803 c = l >> DIGIT_BITS; | 768 c = l >> _DIGIT_BITS; |
804 a_digits[j++] = l & DIGIT_MASK; | 769 a_digits[j++] = l & _DIGIT_MASK; |
805 } | 770 } |
806 return 1; | 771 return 1; |
807 } | 772 } |
808 | 773 |
809 // Square and accumulate. | 774 // Square and accumulate. |
810 // Input: | 775 // Input: |
811 // x_digits[i..used-1]: digits of operand being squared. | 776 // x_digits[i..used-1]: digits of operand being squared. |
812 // a_digits[2*i..i+used-1]: accumulator digits. | 777 // a_digits[2*i..i+used-1]: accumulator digits. |
813 // Operation: | 778 // Operation: |
814 // a_digits[2*i..i+used-1] += x_digits[i]*x_digits[i] + | 779 // a_digits[2*i..i+used-1] += x_digits[i]*x_digits[i] + |
815 // 2*x_digits[i]*x_digits[i+1..used-1]. | 780 // 2*x_digits[i]*x_digits[i+1..used-1]. |
816 // return 1. | 781 // return 1. |
817 // Note: intrinsics on 64-bit platform may process a digit pair: | 782 // Note: Intrinsics on 64-bit platforms process digit pairs at even indices |
818 // a_digits[2*i..i+used-1] += x_digits[i..i+1]*x_digits[i..i+1] + | 783 // and return 2. |
819 // 2*x_digits[i..i+1]*x_digits[i+2..used-1]. | |
820 // return 2. | |
821 static int _sqrAdd(Uint32List x_digits, int i, | 784 static int _sqrAdd(Uint32List x_digits, int i, |
822 Uint32List a_digits, int used) { | 785 Uint32List a_digits, int used) { |
786 // Verify that digit pairs are accessible for 64-bit processing. | |
787 assert(x_digits.length > ((used - 1) | 1)); | |
788 assert(a_digits.length > ((i + used - 1) | 1)); | |
823 int x = x_digits[i]; | 789 int x = x_digits[i]; |
824 if (x == 0) return 1; | 790 if (x == 0) return 1; |
825 int j = 2*i; | 791 int j = 2*i; |
826 int c = 0; | 792 int c = 0; |
827 int xl = x & DIGIT2_MASK; | 793 int xl = x & _DIGIT2_MASK; |
828 int xh = x >> DIGIT2_BITS; | 794 int xh = x >> _DIGIT2_BITS; |
829 int m = 2*xh*xl; | 795 int m = 2*xh*xl; |
830 int l = xl*xl + ((m & DIGIT2_MASK) << DIGIT2_BITS) + a_digits[j]; | 796 int l = xl*xl + ((m & _DIGIT2_MASK) << _DIGIT2_BITS) + a_digits[j]; |
831 c = (l >> DIGIT_BITS) + (m >> DIGIT2_BITS) + xh*xh; | 797 c = (l >> _DIGIT_BITS) + (m >> _DIGIT2_BITS) + xh*xh; |
832 a_digits[j] = l & DIGIT_MASK; | 798 a_digits[j] = l & _DIGIT_MASK; |
833 x <<= 1; | 799 x <<= 1; |
834 xl = x & DIGIT2_MASK; | 800 xl = x & _DIGIT2_MASK; |
835 xh = x >> DIGIT2_BITS; | 801 xh = x >> _DIGIT2_BITS; |
836 int n = used - i - 1; | 802 int n = used - i - 1; |
837 int k = i + 1; | 803 int k = i + 1; |
838 j++; | 804 j++; |
839 while (--n >= 0) { | 805 while (--n >= 0) { |
840 int l = x_digits[k] & DIGIT2_MASK; | 806 int l = x_digits[k] & _DIGIT2_MASK; |
841 int h = x_digits[k++] >> DIGIT2_BITS; | 807 int h = x_digits[k++] >> _DIGIT2_BITS; |
842 int m = xh*l + h*xl; | 808 int m = xh*l + h*xl; |
843 l = xl*l + ((m & DIGIT2_MASK) << DIGIT2_BITS) + a_digits[j] + c; | 809 l = xl*l + ((m & _DIGIT2_MASK) << _DIGIT2_BITS) + a_digits[j] + c; |
844 c = (l >> DIGIT_BITS) + (m >> DIGIT2_BITS) + xh*h; | 810 c = (l >> _DIGIT_BITS) + (m >> _DIGIT2_BITS) + xh*h; |
845 a_digits[j++] = l & DIGIT_MASK; | 811 a_digits[j++] = l & _DIGIT_MASK; |
846 } | 812 } |
847 c += a_digits[i + used]; | 813 c += a_digits[i + used]; |
848 if (c >= DIGIT_BASE) { | 814 if (c >= _DIGIT_BASE) { |
849 a_digits[i + used] = c - DIGIT_BASE; | 815 a_digits[i + used] = c - _DIGIT_BASE; |
850 a_digits[i + used + 1] = 1; | 816 a_digits[i + used + 1] = 1; |
851 } else { | 817 } else { |
852 a_digits[i + used] = c; | 818 a_digits[i + used] = c; |
853 } | 819 } |
854 return 1; | 820 return 1; |
855 } | 821 } |
856 | 822 |
857 // r = this * a. | 823 // Return this * a. |
858 void _mulTo(_Bigint a, _Bigint r) { | 824 _Bigint _mul(_Bigint a) { |
859 // TODO(regis): Use karatsuba multiplication when appropriate. | 825 // TODO(regis): Use karatsuba multiplication when appropriate. |
860 var used = _used; | 826 var used = _used; |
861 var a_used = a._used; | 827 var a_used = a._used; |
862 if (used == 0 || a_used == 0) { | 828 if (used == 0 || a_used == 0) { |
863 r._used = 0; | 829 return _ZERO; |
864 r._neg = false; | |
865 return; | |
866 } | 830 } |
867 var r_used = used + a_used; | 831 var r_used = used + a_used; |
868 r._ensureLength(r_used); | |
869 var digits = _digits; | 832 var digits = _digits; |
870 var a_digits = a._digits; | 833 var a_digits = a._digits; |
871 var r_digits = r._digits; | 834 var r_digits = new Uint32List(r_used + (r_used & 1)); |
872 r._used = r_used; | 835 var i = 0; |
873 var i = r_used + 1; // Set leading zero for 64-bit processing. | 836 while (i < a_used) { |
837 i += _mulAdd(a_digits, i, digits, 0, r_digits, i, used); | |
838 } | |
839 return new _Bigint(_neg != a._neg, r_used, r_digits); | |
840 } | |
841 | |
842 // r_digits[0..r_used-1] = x_digits[0..x_used-1]*a_digits[0..a_used-1]. | |
843 // Return r_used = x_used + a_used. | |
844 static int _mulDigits(Uint32List x_digits, int x_used, | |
845 Uint32List a_digits, int a_used, | |
846 Uint32List r_digits) { | |
847 var r_used = x_used + a_used; | |
848 var i = r_used + (r_used & 1); | |
849 assert(r_digits.length >= i); | |
874 while (--i >= 0) { | 850 while (--i >= 0) { |
875 r_digits[i] = 0; | 851 r_digits[i] = 0; |
876 } | 852 } |
877 i = 0; | 853 i = 0; |
878 while (i < a_used) { | 854 while (i < a_used) { |
879 i += _mulAdd(a_digits, i, digits, 0, r_digits, i, used); | 855 i += _mulAdd(a_digits, i, x_digits, 0, r_digits, i, x_used); |
880 } | 856 } |
881 r._clamp(); | 857 return r_used; |
882 r._neg = r._used > 0 && _neg != a._neg; // Zero cannot be negative. | |
883 } | 858 } |
884 | 859 |
885 // r = this^2, r != this. | 860 // Return this^2. |
886 void _sqrTo(_Bigint r) { | 861 _Bigint _sqr() { |
887 var used = _used; | 862 var used = _used; |
888 if (used == 0) { | 863 if (used == 0) { |
889 r._used = 0; | 864 return _ZERO; |
890 r._neg = false; | |
891 return; | |
892 } | 865 } |
893 var r_used = 2 * used; | 866 var r_used = 2 * used; |
894 r._ensureLength(r_used); | |
895 var digits = _digits; | 867 var digits = _digits; |
896 var r_digits = r._digits; | 868 var r_digits = new Uint32List(r_used); |
897 var i = r_used + 1; // Set leading zero for 64-bit processing. | 869 // Since r_used is even, no need for a leading zero for 64-bit processing. |
870 var i = 0; | |
871 while (i < used - 1) { | |
872 i += _sqrAdd(digits, i, r_digits, used); | |
873 } | |
874 // The last step is already done if digit pairs were processed above. | |
875 if (i < used) { | |
876 _mulAdd(digits, i, digits, i, r_digits, 2*i, 1); | |
877 } | |
878 return new _Bigint(false, r_used, r_digits); | |
879 } | |
880 | |
881 // r_digits[0..r_used-1] = x_digits[0..x_used-1]*x_digits[0..x_used-1]. | |
882 // Return r_used = 2*x_used. | |
883 static int _sqrDigits(Uint32List x_digits, int x_used, Uint32List r_digits) { | |
884 var r_used = 2 * x_used; | |
885 assert(r_digits.length >= r_used); | |
886 // Since r_used is even, no need for a leading zero for 64-bit processing. | |
887 var i = r_used; | |
898 while (--i >= 0) { | 888 while (--i >= 0) { |
899 r_digits[i] = 0; | 889 r_digits[i] = 0; |
900 } | 890 } |
901 i = 0; | 891 i = 0; |
902 while (i < used - 1) { | 892 while (i < x_used - 1) { |
903 i += _sqrAdd(digits, i, r_digits, used); | 893 i += _sqrAdd(x_digits, i, r_digits, x_used); |
904 } | 894 } |
905 if (r_used > 0) { | 895 // The last step is already done if digit pairs were processed above. |
906 _mulAdd(digits, i, digits, i, r_digits, 2*i, 1); | 896 if (i < x_used) { |
897 _mulAdd(x_digits, i, x_digits, i, r_digits, 2*i, 1); | |
907 } | 898 } |
908 r._used = r_used; | 899 return r_used; |
909 r._neg = false; | |
910 r._clamp(); | |
911 } | 900 } |
912 | 901 |
913 // Indices of the arguments of _estQuotientDigit. | 902 // Indices of the arguments of _estQuotientDigit. |
914 // For 64-bit processing by intrinsics on 64-bit platforms, the top digit pair | 903 // For 64-bit processing by intrinsics on 64-bit platforms, the top digit pair |
915 // of divisor y is provided in the args array, and a 64-bit estimated quotient | 904 // of divisor y is provided in the args array, and a 64-bit estimated quotient |
916 // is returned. However, on 32-bit platforms, the low 32-bit digit is ignored | 905 // is returned. However, on 32-bit platforms, the low 32-bit digit is ignored |
917 // and only one 32-bit digit is returned as the estimated quotient. | 906 // and only one 32-bit digit is returned as the estimated quotient. |
918 static const int _YT_LO = 0; // Low digit of top digit pair of y, for 64-bit. | 907 static const int _YT_LO = 0; // Low digit of top digit pair of y, for 64-bit. |
919 static const int _YT = 1; // Top digit of divisor y. | 908 static const int _YT = 1; // Top digit of divisor y. |
920 static const int _QD = 2; // Estimated quotient. | 909 static const int _QD = 2; // Estimated quotient. |
921 static const int _QD_HI = 3; // High digit of estimated quotient, for 64-bit. | 910 static const int _QD_HI = 3; // High digit of estimated quotient, for 64-bit. |
922 | 911 |
923 // Operation: | 912 // Operation: |
924 // Estimate args[_QD] = digits[i-1..i] ~/ args[_YT] | 913 // Estimate args[_QD] = digits[i-1..i] ~/ args[_YT] |
925 // return 1 | 914 // return 1 |
926 // Note: intrinsics on 64-bit platform may process a digit pair: | 915 // Note: Intrinsics on 64-bit platforms process a digit pair (i always odd): |
927 // Estimate args[_QD.._QD_HI] = digits[i-3..i] ~/ args[_YT_LO.._YT] | 916 // Estimate args[_QD.._QD_HI] = digits[i-3..i] ~/ args[_YT_LO.._YT] |
928 // return 2 | 917 // return 2 |
929 static int _estQuotientDigit(Uint32List args, Uint32List digits, int i) { | 918 static int _estQuotientDigit(Uint32List args, Uint32List digits, int i) { |
919 // Verify that digit pairs are accessible for 64-bit processing. | |
920 assert(digits.length >= 4); | |
930 if (digits[i] == args[_YT]) { | 921 if (digits[i] == args[_YT]) { |
931 args[_QD] = DIGIT_MASK; | 922 args[_QD] = _DIGIT_MASK; |
932 } else { | 923 } else { |
933 // Chop off one bit, since a Mint cannot hold 2 DIGITs. | 924 // Chop off one bit, since a Mint cannot hold 2 DIGITs. |
934 var qd = ((digits[i] << (DIGIT_BITS - 1)) | (digits[i - 1] >> 1)) | 925 var qd = ((digits[i] << (_DIGIT_BITS - 1)) | (digits[i - 1] >> 1)) |
935 ~/ (args[_YT] >> 1); | 926 ~/ (args[_YT] >> 1); |
936 if (qd > DIGIT_MASK) { | 927 if (qd > _DIGIT_MASK) { |
937 args[_QD] = DIGIT_MASK; | 928 args[_QD] = _DIGIT_MASK; |
938 } else { | 929 } else { |
939 args[_QD] = qd; | 930 args[_QD] = qd; |
940 } | 931 } |
941 } | 932 } |
942 return 1; | 933 return 1; |
943 } | 934 } |
944 | 935 |
936 // Return trunc(this / a), a != 0. | |
937 _Bigint _div(_Bigint a) { | |
938 return _divRem(a, true); | |
939 } | |
945 | 940 |
946 // Truncating division and remainder. | 941 // Return this - a * trunc(this / a), a != 0. |
947 // If q != null, q = trunc(this / a). | 942 _Bigint _rem(_Bigint a) { |
948 // If r != null, r = this - a * trunc(this / a). | 943 return _divRem(a, false); |
949 void _divRemTo(_Bigint a, _Bigint q, _Bigint r) { | 944 } |
950 if (a._used == 0) return; | 945 |
946 // Return trunc(this / a), a != 0, if div == true. | |
947 // Return this - a * trunc(this / a), a != 0, if div == false. | |
948 _Bigint _divRem(_Bigint a, bool div) { | |
949 assert(a._used > 0); | |
951 if (_used < a._used) { | 950 if (_used < a._used) { |
952 if (q != null) { | 951 return div ? _ZERO : this; |
953 // Set q to 0. | |
954 q._neg = false; | |
955 q._used = 0; | |
956 } | |
957 if (r != null) { | |
958 _copyTo(r); | |
959 } | |
960 return; | |
961 } | 952 } |
962 if (r == null) { | 953 var nsh = _DIGIT_BITS - _nbits(a._digits[a._used - 1]); |
963 r = new _Bigint(); | 954 // For 64-bit processing, make sure y has an even number of digits. |
955 if (a._used.isOdd) { | |
956 nsh += _DIGIT_BITS; | |
964 } | 957 } |
965 var y = new _Bigint(); // Normalized modulus. | 958 var y; // Normalized positive divisor. |
966 var nsh = DIGIT_BITS - _nbits(a._digits[a._used - 1]); | 959 var r; // Concatenated positive quotient and normalized positive remainder. |
967 // For 64-bit processing, make sure y has an even number of digits. | |
968 if ((a._used & 1) == 1) { | |
969 nsh += DIGIT_BITS; | |
970 } | |
971 if (nsh > 0) { | 960 if (nsh > 0) { |
972 a._lShiftTo(nsh, y); | 961 y = a._lShift(nsh)._abs(); |
973 _lShiftTo(nsh, r); | 962 r = _lShift(nsh)._abs(); |
974 } | 963 } |
975 else { | 964 else { |
976 a._copyTo(y); | 965 y = a._abs(); |
977 _copyTo(r); | 966 r = _abs(); |
978 } | 967 } |
979 // We consider this and a positive. Ignore the copied sign. | |
980 y._neg = false; | |
981 r._neg = false; | |
982 var y_used = y._used; | 968 var y_used = y._used; |
983 assert((y_used & 1) == 0); | |
984 var y_digits = y._digits; | 969 var y_digits = y._digits; |
985 Uint32List args = new Uint32List(4); | 970 Uint32List args = new Uint32List(4); |
986 args[_YT_LO] = y_digits[y_used - 2]; | 971 args[_YT_LO] = y_digits[y_used - 2]; |
987 args[_YT] = y_digits[y_used - 1]; | 972 args[_YT] = y_digits[y_used - 1]; |
988 var r_digits = r._digits; | 973 var r_used = r._used; |
989 var i = r._used; | 974 // For 64-bit processing, make sure y_used, i, and j are even. |
990 if ((i & 1) == 1) { | 975 assert(y_used.isEven); |
991 // For 64-bit processing, make sure r has an even number of digits. | 976 var i = r_used + (r_used & 1); |
992 r_digits[i++] = 0; | 977 var j = i - y_used; |
978 var t = y._dlShift(j); | |
979 if (r._compare(t) >= 0) { | |
980 assert(i == r_used); | |
981 r = r._or(_ONE._dlShift(r_used++))._sub(t); | |
982 assert(r._used == r_used && (i + 1) == r_used); | |
993 } | 983 } |
994 var j = i - y_used; | 984 // Negate y so we can later use _mulAdd instead of non-existent _mulSub. |
995 _Bigint t = (q == null) ? new _Bigint() : q; | 985 y = _ONE._dlShift(y_used)._sub(y); |
996 y._dlShiftTo(j, t); | 986 if (y._used < y_used) { |
997 if (r._compareTo(t) >= 0) { | 987 y_digits = _cloneDigits(y._digits, 0, y._used, y_used); |
998 r_digits[r._used++] = 1; | 988 } else { |
999 r_digits[r._used] = 0; // Set leading zero for 64-bit processing. | 989 y_digits = y._digits; |
1000 r._subTo(t, r); | |
1001 } | 990 } |
1002 ONE._dlShiftTo(y_used, t); | 991 // y_digits is read-only and has y_used digits (possibly including several |
1003 t._subTo(y, y); // Negate y so we can replace sub with _mulAdd later. | 992 // leading zeros) plus a leading zero for 64-bit processing. |
1004 while (y._used < y_used) { | 993 var r_digits = _cloneDigits(r._digits, 0, r._used, i + 1); |
1005 y_digits[y._used++] = 0; | 994 // r_digits is modified during iteration. |
1006 } | 995 // r_digits[0..y_used-1] is the current remainder. |
1007 y_digits[y._used] = 0; // Set leading zero for 64-bit processing. | 996 // r_digits[y_used..r_used-1] is the current quotient. |
997 --i; | |
1008 while (j > 0) { | 998 while (j > 0) { |
1009 var d0 = _estQuotientDigit(args, r_digits, --i); | 999 var d0 = _estQuotientDigit(args, r_digits, i); |
1010 j -= d0; | 1000 j -= d0; |
1011 var d1 = _mulAdd(args, _QD, y_digits, 0, r_digits, j, y_used); | 1001 var d1 = _mulAdd(args, _QD, y_digits, 0, r_digits, j, y_used); |
1012 // _estQuotientDigit and _mulAdd must agree on the number of digits to | 1002 // _estQuotientDigit and _mulAdd must agree on the number of digits to |
1013 // process. | 1003 // process. |
1014 assert(d0 == d1); | 1004 assert(d0 == d1); |
1015 if (d0 == 1) { | 1005 if (d0 == 1) { |
1016 if (r_digits[i] < args[_QD]) { | 1006 if (r_digits[i] < args[_QD]) { |
1017 y._dlShiftTo(j, t); | 1007 var t = y._dlShift(j); |
1018 r._subTo(t, r); | 1008 var t_digits = t._digits; |
1009 var t_used = t._used; | |
1010 _absSub(r_digits, r_used, t_digits, t_used, r_digits); | |
1019 while (r_digits[i] < --args[_QD]) { | 1011 while (r_digits[i] < --args[_QD]) { |
1020 r._subTo(t, r); | 1012 _absSub(r_digits, r_used, t_digits, t_used, r_digits); |
1021 } | 1013 } |
1022 } | 1014 } |
1023 } else { | 1015 } else { |
1024 assert(d0 == 2); | 1016 assert(d0 == 2); |
1025 assert(r_digits[i] <= args[_QD_HI]); | 1017 assert(r_digits[i] <= args[_QD_HI]); |
1026 if ((r_digits[i] < args[_QD_HI]) || (r_digits[i-1] < args[_QD])) { | 1018 if ((r_digits[i] < args[_QD_HI]) || (r_digits[i-1] < args[_QD])) { |
1027 y._dlShiftTo(j, t); | 1019 var t = y._dlShift(j); |
1028 r._subTo(t, r); | 1020 var t_digits = t._digits; |
1021 var t_used = t._used; | |
1022 _absSub(r_digits, r_used, t_digits, t_used, r_digits); | |
1029 if (args[_QD] == 0) { | 1023 if (args[_QD] == 0) { |
1030 --args[_QD_HI]; | 1024 --args[_QD_HI]; |
1031 } | 1025 } |
1032 --args[_QD]; | 1026 --args[_QD]; |
1033 assert(r_digits[i] <= args[_QD_HI]); | 1027 assert(r_digits[i] <= args[_QD_HI]); |
1034 while ((r_digits[i] < args[_QD_HI]) || (r_digits[i-1] < args[_QD])) { | 1028 while ((r_digits[i] < args[_QD_HI]) || (r_digits[i-1] < args[_QD])) { |
1035 r._subTo(t, r); | 1029 _absSub(r_digits, r_used, t_digits, t_used, r_digits); |
1036 if (args[_QD] == 0) { | 1030 if (args[_QD] == 0) { |
1037 --args[_QD_HI]; | 1031 --args[_QD_HI]; |
1038 } | 1032 } |
1039 --args[_QD]; | 1033 --args[_QD]; |
1040 assert(r_digits[i] <= args[_QD_HI]); | 1034 assert(r_digits[i] <= args[_QD_HI]); |
1041 } | 1035 } |
1042 } | 1036 } |
1043 --i; | |
1044 } | 1037 } |
1038 i -= d0; | |
1045 } | 1039 } |
1046 if (q != null) { | 1040 if (div) { |
1047 r._drShiftTo(y_used, q); | 1041 // Return quotient, i.e. r_digits[y_used..r_used-1] with proper sign. |
1048 if (_neg != a._neg && q._used > 0) { | 1042 r_digits = _cloneDigits(r_digits, y_used, r_used, r_used - y_used); |
1049 q._neg = !q._neg; | 1043 r = new _Bigint(false, r_used - y_used, r_digits); |
1044 if (_neg != a._neg && r._used > 0) { | |
1045 r = r._negate(); | |
1050 } | 1046 } |
1047 return r; | |
1051 } | 1048 } |
1052 r._used = y_used; | 1049 // Return remainder, i.e. denormalized r_digits[0..y_used-1] with |
1053 r._clamp(); | 1050 // proper sign. |
1051 r_digits = _cloneDigits(r_digits, 0, y_used, y_used); | |
1052 r = new _Bigint(false, y_used, r_digits); | |
1054 if (nsh > 0) { | 1053 if (nsh > 0) { |
1055 r._rShiftTo(nsh, r); // Denormalize remainder. | 1054 r = r._rShift(nsh); // Denormalize remainder. |
1056 } | 1055 } |
1057 if (_neg && r._used > 0) { | 1056 if (_neg && r._used > 0) { |
1058 r._neg = !r._neg; | 1057 r = r._negate(); |
1059 } | 1058 } |
1059 return r; | |
1060 } | |
1061 | |
1062 // Customized version of _rem() minimizing allocations for use in reduction. | |
1063 // Input: | |
1064 // x_digits[0..x_used-1]: positive dividend. | |
1065 // y_digits[0..y_used-1]: normalized positive divisor. | |
1066 // ny_digits[0..y_used-1]: negated y_digits. | |
1067 // nsh: normalization shift amount. | |
1068 // yt_qd: top y digit(s) and place holder for estimated quotient digit(s). | |
1069 // t_digits: temp array of 2*y_used digits. | |
1070 // r_digits: result digits array large enough to temporarily hold | |
1071 // concatenated quotient and normalized remainder. | |
1072 // Output: | |
1073 // r_digits[0..r_used-1]: positive remainder. | |
1074 // Returns r_used. | |
1075 static int _remDigits(Uint32List x_digits, int x_used, | |
1076 Uint32List y_digits, int y_used, Uint32List ny_digits, | |
1077 int nsh, | |
1078 Uint32List yt_qd, | |
1079 Uint32List t_digits, | |
1080 Uint32List r_digits) { | |
1081 assert(y_used > 0 && x_used >= y_used); | |
1082 // Initialize r_digits to normalized positive dividend. | |
1083 var r_used = _lShiftDigits(x_digits, x_used, nsh, r_digits); | |
1084 // For 64-bit processing, make sure y_used, i, and j are even. | |
1085 assert(y_used.isEven); | |
1086 var i = r_used + (r_used & 1); | |
1087 var j = i - y_used; | |
1088 var t_used = _dlShiftDigits(y_digits, y_used, j, t_digits); | |
1089 // Explicit first division step in case normalized dividend is larger or | |
1090 // equal to shifted normalized divisor. | |
1091 if (_compareDigits(r_digits, r_used, t_digits, t_used) >= 0) { | |
1092 assert(i == r_used); | |
1093 r_digits[r_used++] = 1; // Quotient = 1. | |
1094 r_digits[r_used] = 0; // Leading zero. | |
1095 // Subtract divisor from remainder. | |
1096 _absSub(r_digits, r_used, t_digits, t_used, r_digits); | |
1097 } | |
1098 // Negated y_digits passed in ny_digits allow the use of _mulAdd instead of | |
1099 // unimplemented _mulSub. | |
1100 // ny_digits is read-only and has y_used digits (possibly including several | |
1101 // leading zeros) plus a leading zero for 64-bit processing. | |
1102 // r_digits is modified during iteration. | |
1103 // r_digits[0..y_used-1] is the current remainder. | |
1104 // r_digits[y_used..r_used-1] is the current quotient. | |
1105 --i; | |
1106 while (j > 0) { | |
1107 var d0 = _estQuotientDigit(yt_qd, r_digits, i); | |
1108 j -= d0; | |
1109 var d1 = _mulAdd(yt_qd, _QD, ny_digits, 0, r_digits, j, y_used); | |
1110 // _estQuotientDigit and _mulAdd must agree on the number of digits to | |
1111 // process. | |
1112 assert(d0 == d1); | |
1113 if (d0 == 1) { | |
1114 if (r_digits[i] < yt_qd[_QD]) { | |
1115 var t_used = _dlShiftDigits(ny_digits, y_used, j, t_digits); | |
1116 _absSub(r_digits, r_used, t_digits, t_used, r_digits); | |
1117 while (r_digits[i] < --yt_qd[_QD]) { | |
1118 _absSub(r_digits, r_used, t_digits, t_used, r_digits); | |
1119 } | |
1120 } | |
1121 } else { | |
1122 assert(d0 == 2); | |
1123 assert(r_digits[i] <= yt_qd[_QD_HI]); | |
1124 if ((r_digits[i] < yt_qd[_QD_HI]) || (r_digits[i-1] < yt_qd[_QD])) { | |
1125 var t_used = _dlShiftDigits(ny_digits, y_used, j, t_digits); | |
1126 _absSub(r_digits, r_used, t_digits, t_used, r_digits); | |
1127 if (yt_qd[_QD] == 0) { | |
1128 --yt_qd[_QD_HI]; | |
1129 } | |
1130 --yt_qd[_QD]; | |
1131 assert(r_digits[i] <= yt_qd[_QD_HI]); | |
1132 while ((r_digits[i] < yt_qd[_QD_HI]) || | |
1133 (r_digits[i-1] < yt_qd[_QD])) { | |
1134 _absSub(r_digits, r_used, t_digits, t_used, r_digits); | |
1135 if (yt_qd[_QD] == 0) { | |
1136 --yt_qd[_QD_HI]; | |
1137 } | |
1138 --yt_qd[_QD]; | |
1139 assert(r_digits[i] <= yt_qd[_QD_HI]); | |
1140 } | |
1141 } | |
1142 } | |
1143 i -= d0; | |
1144 } | |
1145 // Return remainder, i.e. denormalized r_digits[0..y_used-1]. | |
1146 r_used = y_used; | |
1147 if (nsh > 0) { | |
1148 // Denormalize remainder. | |
1149 r_used = _rShiftDigits(r_digits, r_used, nsh, r_digits); | |
1150 } | |
1151 return r_used; | |
1060 } | 1152 } |
1061 | 1153 |
1062 int get _identityHashCode { | 1154 int get _identityHashCode { |
1063 return this; | 1155 return this; |
1064 } | 1156 } |
1065 int operator ~() { | 1157 int operator ~() { |
1066 _Bigint result = new _Bigint(); | 1158 return _not()._toValidInt(); |
1067 _notTo(result); | |
1068 return result._toValidInt(); | |
1069 } | 1159 } |
1070 | 1160 |
1071 int get bitLength { | 1161 int get bitLength { |
1072 if (_used == 0) return 0; | 1162 if (_used == 0) return 0; |
1073 if (_neg) return (~this).bitLength; | 1163 if (_neg) return (~this).bitLength; |
1074 return DIGIT_BITS*(_used - 1) + _nbits(_digits[_used - 1]); | 1164 return _DIGIT_BITS*(_used - 1) + _nbits(_digits[_used - 1]); |
1075 } | 1165 } |
1076 | 1166 |
1077 // This method must support smi._toBigint()._shrFromInt(int). | 1167 // This method must support smi._toBigint()._shrFromInt(int). |
1078 int _shrFromInt(int other) { | 1168 int _shrFromInt(int other) { |
1079 if (_used == 0) return other; // Shift amount is zero. | 1169 if (_used == 0) return other; // Shift amount is zero. |
1080 if (_neg) throw "negative shift amount"; // TODO(regis): What exception? | 1170 if (_neg) throw "negative shift amount"; // TODO(regis): What exception? |
1081 assert(DIGIT_BITS == 32); // Otherwise this code needs to be revised. | 1171 assert(_DIGIT_BITS == 32); // Otherwise this code needs to be revised. |
1082 var shift; | 1172 var shift; |
1083 if ((_used > 2) || ((_used == 2) && (_digits[1] > 0x10000000))) { | 1173 if ((_used > 2) || ((_used == 2) && (_digits[1] > 0x10000000))) { |
1084 if (other < 0) { | 1174 if (other < 0) { |
1085 return -1; | 1175 return -1; |
1086 } else { | 1176 } else { |
1087 return 0; | 1177 return 0; |
1088 } | 1178 } |
1089 } else { | 1179 } else { |
1090 shift = ((_used == 2) ? (_digits[1] << DIGIT_BITS) : 0) + _digits[0]; | 1180 shift = ((_used == 2) ? (_digits[1] << _DIGIT_BITS) : 0) + _digits[0]; |
1091 } | 1181 } |
1092 _Bigint result = new _Bigint(); | 1182 return other._toBigint()._rShift(shift)._toValidInt(); |
1093 other._toBigint()._rShiftTo(shift, result); | |
1094 return result._toValidInt(); | |
1095 } | 1183 } |
1096 | 1184 |
1097 // This method must support smi._toBigint()._shlFromInt(int). | 1185 // This method must support smi._toBigint()._shlFromInt(int). |
1098 // An out of memory exception is thrown if the result cannot be allocated. | 1186 // An out of memory exception is thrown if the result cannot be allocated. |
1099 int _shlFromInt(int other) { | 1187 int _shlFromInt(int other) { |
1100 if (_used == 0) return other; // Shift amount is zero. | 1188 if (_used == 0) return other; // Shift amount is zero. |
1101 if (_neg) throw "negative shift amount"; // TODO(regis): What exception? | 1189 if (_neg) throw "negative shift amount"; // TODO(regis): What exception? |
1102 assert(DIGIT_BITS == 32); // Otherwise this code needs to be revised. | 1190 assert(_DIGIT_BITS == 32); // Otherwise this code needs to be revised. |
1103 var shift; | 1191 var shift; |
1104 if (_used > 2 || (_used == 2 && _digits[1] > 0x10000000)) { | 1192 if (_used > 2 || (_used == 2 && _digits[1] > 0x10000000)) { |
1105 throw new OutOfMemoryError(); | 1193 throw new OutOfMemoryError(); |
1106 } else { | 1194 } else { |
1107 shift = ((_used == 2) ? (_digits[1] << DIGIT_BITS) : 0) + _digits[0]; | 1195 shift = ((_used == 2) ? (_digits[1] << _DIGIT_BITS) : 0) + _digits[0]; |
1108 } | 1196 } |
1109 _Bigint result = new _Bigint(); | 1197 return other._toBigint()._lShift(shift)._toValidInt(); |
1110 other._toBigint()._lShiftTo(shift, result); | |
1111 return result._toValidInt(); | |
1112 } | 1198 } |
1113 | 1199 |
1114 // Overriden operators and methods. | 1200 // Overriden operators and methods. |
1115 | 1201 |
1116 // The following operators override operators of _IntegerImplementation for | 1202 // The following operators override operators of _IntegerImplementation for |
1117 // efficiency, but are not necessary for correctness. They shortcut native | 1203 // efficiency, but are not necessary for correctness. They shortcut native |
1118 // calls that would return null because the receiver is _Bigint. | 1204 // calls that would return null because the receiver is _Bigint. |
1119 num operator +(num other) { | 1205 num operator +(num other) { |
1120 return other._toBigintOrDouble()._addFromInteger(this); | 1206 return other._toBigintOrDouble()._addFromInteger(this); |
1121 } | 1207 } |
(...skipping 26 matching lines...) Expand all Loading... | |
1148 } | 1234 } |
1149 int operator >>(int other) { | 1235 int operator >>(int other) { |
1150 return other._toBigintOrDouble()._shrFromInt(this); | 1236 return other._toBigintOrDouble()._shrFromInt(this); |
1151 } | 1237 } |
1152 int operator <<(int other) { | 1238 int operator <<(int other) { |
1153 return other._toBigintOrDouble()._shlFromInt(this); | 1239 return other._toBigintOrDouble()._shlFromInt(this); |
1154 } | 1240 } |
1155 // End of operator shortcuts. | 1241 // End of operator shortcuts. |
1156 | 1242 |
1157 int operator -() { | 1243 int operator -() { |
1158 if (_used == 0) { | 1244 return _negate()._toValidInt(); |
1159 return this; | |
1160 } | |
1161 var r = new _Bigint(); | |
1162 _copyTo(r); | |
1163 r._neg = !_neg; | |
1164 return r._toValidInt(); | |
1165 } | 1245 } |
1166 | 1246 |
1167 int get sign { | 1247 int get sign { |
1168 return (_used == 0) ? 0 : _neg ? -1 : 1; | 1248 return (_used == 0) ? 0 : _neg ? -1 : 1; |
1169 } | 1249 } |
1170 | 1250 |
1171 bool get isEven => _used == 0 || (_digits[0] & 1) == 0; | 1251 bool get isEven => _used == 0 || (_digits[0] & 1) == 0; |
1172 bool get isNegative => _neg; | 1252 bool get isNegative => _neg; |
1173 | 1253 |
1174 String _toPow2String(int radix) { | 1254 String _toPow2String(int radix) { |
1175 if (_used == 0) return "0"; | 1255 if (_used == 0) return "0"; |
1176 assert(radix & (radix - 1) == 0); | 1256 assert(radix & (radix - 1) == 0); |
1177 final bitsPerChar = radix.bitLength - 1; | 1257 final bitsPerChar = radix.bitLength - 1; |
1178 final firstcx = _neg ? 1 : 0; // Index of first char in str after the sign. | 1258 final firstcx = _neg ? 1 : 0; // Index of first char in str after the sign. |
1179 final lastdx = _used - 1; // Index of last digit in bigint. | 1259 final lastdx = _used - 1; // Index of last digit in bigint. |
1180 final bitLength = lastdx*DIGIT_BITS + _nbits(_digits[lastdx]); | 1260 final bitLength = lastdx*_DIGIT_BITS + _nbits(_digits[lastdx]); |
1181 // Index of char in str. Initialize with str length. | 1261 // Index of char in str. Initialize with str length. |
1182 var cx = firstcx + (bitLength + bitsPerChar - 1) ~/ bitsPerChar; | 1262 var cx = firstcx + (bitLength + bitsPerChar - 1) ~/ bitsPerChar; |
1183 _OneByteString str = _OneByteString._allocate(cx); | 1263 _OneByteString str = _OneByteString._allocate(cx); |
1184 str._setAt(0, 0x2d); // '-'. Is overwritten if not negative. | 1264 str._setAt(0, 0x2d); // '-'. Is overwritten if not negative. |
1185 final mask = radix - 1; | 1265 final mask = radix - 1; |
1186 var dx = 0; // Digit index in bigint. | 1266 var dx = 0; // Digit index in bigint. |
1187 var bx = 0; // Bit index in bigint digit. | 1267 var bx = 0; // Bit index in bigint digit. |
1188 do { | 1268 do { |
1189 var ch; | 1269 var ch; |
1190 if (bx > (DIGIT_BITS - bitsPerChar)) { | 1270 if (bx > (_DIGIT_BITS - bitsPerChar)) { |
1191 ch = _digits[dx++] >> bx; | 1271 ch = _digits[dx++] >> bx; |
1192 bx += bitsPerChar - DIGIT_BITS; | 1272 bx += bitsPerChar - _DIGIT_BITS; |
1193 if (dx <= lastdx) { | 1273 if (dx <= lastdx) { |
1194 ch |= (_digits[dx] & ((1 << bx) - 1)) << (bitsPerChar - bx); | 1274 ch |= (_digits[dx] & ((1 << bx) - 1)) << (bitsPerChar - bx); |
1195 } | 1275 } |
1196 } else { | 1276 } else { |
1197 ch = (_digits[dx] >> bx) & mask; | 1277 ch = (_digits[dx] >> bx) & mask; |
1198 bx += bitsPerChar; | 1278 bx += bitsPerChar; |
1199 if (bx >= DIGIT_BITS) { | 1279 if (bx >= _DIGIT_BITS) { |
1200 bx -= DIGIT_BITS; | 1280 bx -= _DIGIT_BITS; |
1201 dx++; | 1281 dx++; |
1202 } | 1282 } |
1203 } | 1283 } |
1204 str._setAt(--cx, _IntegerImplementation._digits.codeUnitAt(ch)); | 1284 str._setAt(--cx, _IntegerImplementation._digits.codeUnitAt(ch)); |
1205 } while (cx > firstcx); | 1285 } while (cx > firstcx); |
1206 return str; | 1286 return str; |
1207 } | 1287 } |
1208 | 1288 |
1209 _leftShiftWithMask32(int count, int mask) { | 1289 _leftShiftWithMask32(int count, int mask) { |
1210 if (_used == 0) return 0; | 1290 if (_used == 0) return 0; |
1211 if (count is! _Smi) { | 1291 if (count is! _Smi) { |
1212 _shlFromInt(count); // Throws out of memory exception. | 1292 _shlFromInt(count); // Throws out of memory exception. |
1213 } | 1293 } |
1214 assert(DIGIT_BITS == 32); // Otherwise this code needs to be revised. | 1294 assert(_DIGIT_BITS == 32); // Otherwise this code needs to be revised. |
1215 if (count > 31) return 0; | 1295 if (count > 31) return 0; |
1216 return (_digits[0] << count) & mask; | 1296 return (_digits[0] << count) & mask; |
1217 } | 1297 } |
1218 | 1298 |
1219 int _bitAndFromInteger(int other) { | 1299 int _bitAndFromInteger(int other) { |
1220 _Bigint result = new _Bigint(); | 1300 return other._toBigint()._and(this)._toValidInt(); |
1221 other._toBigint()._andTo(this, result); | |
1222 return result._toValidInt(); | |
1223 } | 1301 } |
1224 int _bitOrFromInteger(int other) { | 1302 int _bitOrFromInteger(int other) { |
1225 _Bigint result = new _Bigint(); | 1303 return other._toBigint()._or(this)._toValidInt(); |
1226 other._toBigint()._orTo(this, result); | |
1227 return result._toValidInt(); | |
1228 } | 1304 } |
1229 int _bitXorFromInteger(int other) { | 1305 int _bitXorFromInteger(int other) { |
1230 _Bigint result = new _Bigint(); | 1306 return other._toBigint()._xor(this)._toValidInt(); |
1231 other._toBigint()._xorTo(this, result); | |
1232 return result._toValidInt(); | |
1233 } | 1307 } |
1234 int _addFromInteger(int other) { | 1308 int _addFromInteger(int other) { |
1235 _Bigint result = new _Bigint(); | 1309 return other._toBigint()._add(this)._toValidInt(); |
1236 other._toBigint()._addTo(this, result); | |
1237 return result._toValidInt(); | |
1238 } | 1310 } |
1239 int _subFromInteger(int other) { | 1311 int _subFromInteger(int other) { |
1240 _Bigint result = new _Bigint(); | 1312 return other._toBigint()._sub(this)._toValidInt(); |
1241 other._toBigint()._subTo(this, result); | |
1242 return result._toValidInt(); | |
1243 } | 1313 } |
1244 int _mulFromInteger(int other) { | 1314 int _mulFromInteger(int other) { |
1245 _Bigint result = new _Bigint(); | 1315 return other._toBigint()._mul(this)._toValidInt(); |
1246 other._toBigint()._mulTo(this, result); | |
1247 return result._toValidInt(); | |
1248 } | 1316 } |
1249 int _truncDivFromInteger(int other) { | 1317 int _truncDivFromInteger(int other) { |
1250 _Bigint result = new _Bigint(); | 1318 return other._toBigint()._div(this)._toValidInt(); |
1251 other._toBigint()._divRemTo(this, result, null); | |
1252 return result._toValidInt(); | |
1253 } | 1319 } |
1254 int _moduloFromInteger(int other) { | 1320 int _moduloFromInteger(int other) { |
1255 _Bigint result = new _Bigint(); | 1321 _Bigint result = other._toBigint()._rem(this); |
1256 other._toBigint()._divRemTo(this, null, result); | |
1257 if (result._neg) { | 1322 if (result._neg) { |
1258 if (_neg) { | 1323 if (_neg) { |
1259 result._subTo(this, result); | 1324 result = result._sub(this); |
1260 } else { | 1325 } else { |
1261 result._addTo(this, result); | 1326 result = result._add(this); |
1262 } | 1327 } |
1263 } | 1328 } |
1264 return result._toValidInt(); | 1329 return result._toValidInt(); |
1265 } | 1330 } |
1266 int _remainderFromInteger(int other) { | 1331 int _remainderFromInteger(int other) { |
1267 _Bigint result = new _Bigint(); | 1332 return other._toBigint()._rem(this)._toValidInt(); |
1268 other._toBigint()._divRemTo(this, null, result); | |
1269 return result._toValidInt(); | |
1270 } | 1333 } |
1271 bool _greaterThanFromInteger(int other) { | 1334 bool _greaterThanFromInteger(int other) { |
1272 return other._toBigint()._compareTo(this) > 0; | 1335 return other._toBigint()._compare(this) > 0; |
1273 } | 1336 } |
1274 bool _equalToInteger(int other) { | 1337 bool _equalToInteger(int other) { |
1275 return other._toBigint()._compareTo(this) == 0; | 1338 return other._toBigint()._compare(this) == 0; |
1276 } | 1339 } |
1277 | 1340 |
1278 // TODO(regis): Make this method private once the plumbing to invoke it from | 1341 // Return pow(this, e) % m, with e >= 0, m > 0. |
1279 // dart:math is in place. Move the argument checking to dart:math. | |
1280 // Return pow(this, e) % m. | |
1281 int modPow(int e, int m) { | 1342 int modPow(int e, int m) { |
1282 if (e is! int) throw new ArgumentError(e); | 1343 if (e is! int || e < 0) throw new ArgumentError(e); |
1283 if (m is! int) throw new ArgumentError(m); | 1344 if (m is! int || m <= 0) throw new ArgumentError(m); |
1284 int i = e.bitLength; | 1345 final m_used = m._used; |
1285 if (i <= 0) return 1; | 1346 final m_used2p2 = 2*m_used + 1 + 1; // +1 for leading zero. |
1347 final e_bitlen = e.bitLength; | |
1348 if (e_bitlen <= 0) return 1; | |
1286 if ((e is! _Bigint) || m.isEven) { | 1349 if ((e is! _Bigint) || m.isEven) { |
1287 _Reduction z = (i < 8 || m.isEven) ? new _Classic(m) : new _Montgomery(m); | 1350 _Reduction z = (e_bitlen < 8 || m.isEven) ? |
1351 new _Classic(m) : new _Montgomery(m); | |
1288 // TODO(regis): Should we use Barrett reduction for an even modulus? | 1352 // TODO(regis): Should we use Barrett reduction for an even modulus? |
1289 var r = new _Bigint(); | 1353 var m_used = m._used; |
1290 var r2 = new _Bigint(); | 1354 var r_digits = new Uint32List(m_used2p2); |
1291 var g = z._convert(this); | 1355 var r2_digits = new Uint32List(m_used2p2); |
1292 i--; | 1356 var g_digits = new Uint32List(m_used + (m_used & 1)); |
1293 g._copyTo(r); | 1357 var g_used = z._convert(this, g_digits); |
1358 // Initialize r with g. | |
1359 var j = g_used + (g_used & 1); // Copy leading zero if any. | |
1360 while (--j >= 0) { | |
1361 r_digits[j] = g_digits[j]; | |
1362 } | |
1363 var r_used = g_used; | |
1364 var r2_used; | |
1365 var i = e_bitlen - 1; | |
1294 while (--i >= 0) { | 1366 while (--i >= 0) { |
1295 z._sqrTo(r, r2); | 1367 r2_used = z._sqr(r_digits, r_used, r2_digits); |
1296 if ((e & (1 << i)) != 0) { | 1368 if ((e & (1 << i)) != 0) { |
1297 z._mulTo(r2, g, r); | 1369 r_used = z._mul(r2_digits, r2_used, g_digits, g_used, r_digits); |
1298 } else { | 1370 } else { |
1299 var t = r; | 1371 var t_digits = r_digits; |
1300 r = r2; | 1372 var t_used = r_used; |
1301 r2 = t; | 1373 r_digits = r2_digits; |
1374 r_used = r2_used; | |
1375 r2_digits = t_digits; | |
1376 r2_used = t_used; | |
1302 } | 1377 } |
1303 } | 1378 } |
1304 return z._revert(r)._toValidInt(); | 1379 return z._revert(r_digits, r_used)._toValidInt(); |
1305 } | 1380 } |
1306 var k; | 1381 var k; |
1307 // TODO(regis): Are these values of k really optimal for our implementation? | 1382 if (e_bitlen < 18) k = 1; |
1308 if (i < 18) k = 1; | 1383 else if (e_bitlen < 48) k = 3; |
1309 else if (i < 48) k = 3; | 1384 else if (e_bitlen < 144) k = 4; |
1310 else if (i < 144) k = 4; | 1385 else if (e_bitlen < 768) k = 5; |
1311 else if (i < 768) k = 5; | |
1312 else k = 6; | 1386 else k = 6; |
1313 _Reduction z = new _Montgomery(m); | 1387 _Reduction z = new _Montgomery(m); |
1314 var n = 3; | 1388 var n = 3; |
1315 var k1 = k - 1; | 1389 final k1 = k - 1; |
1316 var km = (1 << k) - 1; | 1390 final km = (1 << k) - 1; |
1317 List g = new List(km + 1); | 1391 List g_digits = new List(km + 1); |
1318 g[1] = z._convert(this); | 1392 List g_used = new List(km + 1); |
1393 g_digits[1] = new Uint32List(m_used + (m_used & 1)); | |
1394 g_used[1] = z._convert(this, g_digits[1]); | |
1319 if (k > 1) { | 1395 if (k > 1) { |
1320 var g2 = new _Bigint(); | 1396 var g2_digits = new Uint32List(m_used2p2); |
1321 z._sqrTo(g[1], g2); | 1397 var g2_used = z._sqr(g_digits[1], g_used[1], g2_digits); |
1322 while (n <= km) { | 1398 while (n <= km) { |
1323 g[n] = new _Bigint(); | 1399 g_digits[n] = new Uint32List(m_used2p2); |
1324 z._mulTo(g2, g[n - 2], g[n]); | 1400 g_used[n] = z._mul(g2_digits, g2_used, |
1401 g_digits[n - 2], g_used[n - 2], | |
1402 g_digits[n]); | |
1325 n += 2; | 1403 n += 2; |
1326 } | 1404 } |
1327 } | 1405 } |
1328 var j = e._used - 1; | |
1329 var w; | 1406 var w; |
1330 var is1 = true; | 1407 var is1 = true; |
1331 var r = new _Bigint._fromInt(1); | 1408 var r_digits = _ONE._digits; |
1332 var r2 = new _Bigint(); | 1409 var r_used = _ONE._used; |
1333 var t; | 1410 var r2_digits = new Uint32List(m_used2p2); |
1411 var r2_used; | |
1334 var e_digits = e._digits; | 1412 var e_digits = e._digits; |
1335 i = _nbits(e_digits[j]) - 1; | 1413 var j = e._used - 1; |
1414 var i = _nbits(e_digits[j]) - 1; | |
1336 while (j >= 0) { | 1415 while (j >= 0) { |
1337 if (i >= k1) { | 1416 if (i >= k1) { |
1338 w = (e_digits[j] >> (i - k1)) & km; | 1417 w = (e_digits[j] >> (i - k1)) & km; |
1339 } else { | 1418 } else { |
1340 w = (e_digits[j] & ((1 << (i + 1)) - 1)) << (k1 - i); | 1419 w = (e_digits[j] & ((1 << (i + 1)) - 1)) << (k1 - i); |
1341 if (j > 0) { | 1420 if (j > 0) { |
1342 w |= e_digits[j - 1] >> (DIGIT_BITS + i - k1); | 1421 w |= e_digits[j - 1] >> (_DIGIT_BITS + i - k1); |
1343 } | 1422 } |
1344 } | 1423 } |
1345 n = k; | 1424 n = k; |
1346 while ((w & 1) == 0) { | 1425 while ((w & 1) == 0) { |
1347 w >>= 1; | 1426 w >>= 1; |
1348 --n; | 1427 --n; |
1349 } | 1428 } |
1350 if ((i -= n) < 0) { | 1429 if ((i -= n) < 0) { |
1351 i += DIGIT_BITS; | 1430 i += _DIGIT_BITS; |
1352 --j; | 1431 --j; |
1353 } | 1432 } |
1354 if (is1) { // r == 1, don't bother squaring or multiplying it. | 1433 if (is1) { // r == 1, don't bother squaring or multiplying it. |
1355 g[w]._copyTo(r); | 1434 r_digits = new Uint32List(m_used2p2); |
1435 r_used = g_used[w]; | |
1436 var gw_digits = g_digits[w]; | |
1437 var ri = r_used + (r_used & 1); // Copy leading zero if any. | |
1438 while (--ri >= 0) { | |
1439 r_digits[ri] = gw_digits[ri]; | |
1440 } | |
1356 is1 = false; | 1441 is1 = false; |
1357 } | 1442 } |
1358 else { | 1443 else { |
1359 while (n > 1) { | 1444 while (n > 1) { |
1360 z._sqrTo(r, r2); | 1445 r2_used = z._sqr(r_digits, r_used, r2_digits); |
1361 z._sqrTo(r2, r); | 1446 r_used = z._sqr(r2_digits, r2_used, r_digits); |
1362 n -= 2; | 1447 n -= 2; |
1363 } | 1448 } |
1364 if (n > 0) { | 1449 if (n > 0) { |
1365 z._sqrTo(r, r2); | 1450 r2_used = z._sqr(r_digits, r_used, r2_digits); |
1366 } else { | 1451 } else { |
1367 t = r; | 1452 var t_digits = r_digits; |
1368 r = r2; | 1453 var t_used = r_used; |
1369 r2 = t; | 1454 r_digits = r2_digits; |
1455 r_used = r2_used; | |
1456 r2_digits = t_digits; | |
1457 r2_used = t_used; | |
1370 } | 1458 } |
1371 z._mulTo(r2,g[w], r); | 1459 r_used = z._mul(r2_digits, r2_used, g_digits[w], g_used[w], r_digits); |
1372 } | 1460 } |
1373 | |
1374 while (j >= 0 && (e_digits[j] & (1 << i)) == 0) { | 1461 while (j >= 0 && (e_digits[j] & (1 << i)) == 0) { |
1375 z._sqrTo(r, r2); | 1462 r2_used = z._sqr(r_digits, r_used, r2_digits); |
1376 t = r; | 1463 var t_digits = r_digits; |
1377 r = r2; | 1464 var t_used = r_used; |
1378 r2 = t; | 1465 r_digits = r2_digits; |
1466 r_used = r2_used; | |
1467 r2_digits = t_digits; | |
1468 r2_used = t_used; | |
1379 if (--i < 0) { | 1469 if (--i < 0) { |
1380 i = DIGIT_BITS - 1; | 1470 i = _DIGIT_BITS - 1; |
1381 --j; | 1471 --j; |
1382 } | 1472 } |
1383 } | 1473 } |
1384 } | 1474 } |
1385 return z._revert(r)._toValidInt(); | 1475 assert(!is1); |
1476 return z._revert(r_digits, r_used)._toValidInt(); | |
1386 } | 1477 } |
1387 } | 1478 } |
1388 | 1479 |
1389 // Interface for modular reduction. | 1480 // Interface for modular reduction. |
1390 class _Reduction { | 1481 class _Reduction { |
1391 _Bigint _convert(_Bigint x); | 1482 // Return the number of digits used by r_digits. |
1392 _Bigint _revert(_Bigint x); | 1483 int _convert(_Bigint x, Uint32List r_digits); |
1393 void _mulTo(_Bigint x, _Bigint y, _Bigint r); | 1484 int _mul(Uint32List x_digits, int x_used, |
1394 void _sqrTo(_Bigint x, _Bigint r); | 1485 Uint32List y_digits, int y_used, Uint32List r_digits); |
1486 int _sqr(Uint32List x_digits, int x_used, Uint32List r_digits); | |
1487 | |
1488 // Return x reverted to _Bigint. | |
1489 _Bigint _revert(Uint32List x_digits, int x_used); | |
1395 } | 1490 } |
1396 | 1491 |
1397 // Montgomery reduction on _Bigint. | 1492 // Montgomery reduction on _Bigint. |
1398 class _Montgomery implements _Reduction { | 1493 class _Montgomery implements _Reduction { |
1399 _Bigint _m; | 1494 _Bigint _m; // Modulus. |
1400 int _mused2; | 1495 int _mused2p2; |
1401 Uint32List _args; | 1496 Uint32List _args; |
1402 int _digits_per_step; // Number of digits processed in one step. 1 or 2. | 1497 int _digits_per_step; // Number of digits processed in one step. 1 or 2. |
1403 static const int _X = 0; // Index of x. | 1498 static const int _X = 0; // Index of x. |
1404 static const int _X_HI = 1; // Index of high 32-bits of x (64-bit only). | 1499 static const int _X_HI = 1; // Index of high 32-bits of x (64-bit only). |
1405 static const int _RHO = 2; // Index of rho. | 1500 static const int _RHO = 2; // Index of rho. |
1406 static const int _RHO_HI = 3; // Index of high 32-bits of rho (64-bit only). | 1501 static const int _RHO_HI = 3; // Index of high 32-bits of rho (64-bit only). |
1407 static const int _MU = 4; // Index of mu. | 1502 static const int _MU = 4; // Index of mu. |
1408 static const int _MU_HI = 5; // Index of high 32-bits of mu (64-bit only). | 1503 static const int _MU_HI = 5; // Index of high 32-bits of mu (64-bit only). |
1409 | 1504 |
1410 _Montgomery(m) { | 1505 _Montgomery(m) { |
1411 _m = m._toBigint(); | 1506 _m = m._toBigint(); |
1412 _mused2 = 2*_m._used; | 1507 _mused2p2 = 2*_m._used + 2; |
1413 _args = new Uint32List(6); | 1508 _args = new Uint32List(6); |
1414 // Determine if we can process digit pairs by calling an intrinsic. | 1509 // Determine if we can process digit pairs by calling an intrinsic. |
1415 _digits_per_step = _mulMod(_args, _args, 0); | 1510 _digits_per_step = _mulMod(_args, _args, 0); |
1416 _args[_X] = _m._digits[0]; | 1511 _args[_X] = _m._digits[0]; |
1417 if (_digits_per_step == 1) { | 1512 if (_digits_per_step == 1) { |
1418 _invDigit(_args); | 1513 _invDigit(_args); |
1419 } else { | 1514 } else { |
1420 assert(_digits_per_step == 2); | 1515 assert(_digits_per_step == 2); |
1421 _args[_X_HI] = _m._digits[1]; | 1516 _args[_X_HI] = _m._digits[1]; |
1422 _invDigitPair(_args); | 1517 _invDigitPair(_args); |
1423 } | 1518 } |
1424 } | 1519 } |
1425 | 1520 |
1426 // Calculates -1/x % DIGIT_BASE, x is 32-bit digit. | 1521 // Calculates -1/x % _DIGIT_BASE, x is 32-bit digit. |
1427 // xy == 1 (mod m) | 1522 // xy == 1 (mod m) |
1428 // xy = 1+km | 1523 // xy = 1+km |
1429 // xy(2-xy) = (1+km)(1-km) | 1524 // xy(2-xy) = (1+km)(1-km) |
1430 // x(y(2-xy)) = 1-k^2 m^2 | 1525 // x(y(2-xy)) = 1-k^2 m^2 |
1431 // x(y(2-xy)) == 1 (mod m^2) | 1526 // x(y(2-xy)) == 1 (mod m^2) |
1432 // if y is 1/x mod m, then y(2-xy) is 1/x mod m^2 | 1527 // if y is 1/x mod m, then y(2-xy) is 1/x mod m^2 |
1433 // Should reduce x and y(2-xy) by m^2 at each step to keep size bounded. | 1528 // Should reduce x and y(2-xy) by m^2 at each step to keep size bounded. |
1434 // | 1529 // |
1435 // Operation: | 1530 // Operation: |
1436 // args[_RHO] = 1/args[_X] mod DIGIT_BASE. | 1531 // args[_RHO] = 1/args[_X] mod _DIGIT_BASE. |
1437 static void _invDigit(Uint32List args) { | 1532 static void _invDigit(Uint32List args) { |
1438 var x = args[_X]; | 1533 var x = args[_X]; |
1439 var y = x & 3; // y == 1/x mod 2^2 | 1534 var y = x & 3; // y == 1/x mod 2^2 |
1440 y = (y*(2 - (x & 0xf)*y)) & 0xf; // y == 1/x mod 2^4 | 1535 y = (y*(2 - (x & 0xf)*y)) & 0xf; // y == 1/x mod 2^4 |
1441 y = (y*(2 - (x & 0xff)*y)) & 0xff; // y == 1/x mod 2^8 | 1536 y = (y*(2 - (x & 0xff)*y)) & 0xff; // y == 1/x mod 2^8 |
1442 y = (y*(2 - (((x & 0xffff)*y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16 | 1537 y = (y*(2 - (((x & 0xffff)*y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16 |
1443 // Last step - calculate inverse mod DIGIT_BASE directly; | 1538 // Last step - calculate inverse mod _DIGIT_BASE directly; |
1444 // Assumes 16 < DIGIT_BITS <= 32 and assumes ability to handle 48-bit ints. | 1539 // Assumes 16 < _DIGIT_BITS <= 32 and assumes ability to handle 48-bit ints. |
1445 y = (y*(2 - x*y % _Bigint.DIGIT_BASE)) % _Bigint.DIGIT_BASE; | 1540 y = (y*(2 - x*y % _Bigint._DIGIT_BASE)) % _Bigint._DIGIT_BASE; |
1446 // y == 1/x mod DIGIT_BASE | 1541 // y == 1/x mod _DIGIT_BASE |
1447 y = -y; // We really want the negative inverse. | 1542 y = -y; // We really want the negative inverse. |
1448 args[_RHO] = y & _Bigint.DIGIT_MASK; | 1543 args[_RHO] = y & _Bigint._DIGIT_MASK; |
1449 } | 1544 } |
1450 | 1545 |
1451 | 1546 // Calculates -1/x % _DIGIT_BASE^2, x is a pair of 32-bit digits. |
1452 // Calculates -1/x % DIGIT_BASE^2, x is a pair of 32-bit digits. | |
1453 // Operation: | 1547 // Operation: |
1454 // args[_RHO.._RHO_HI] = 1/args[_X.._X_HI] mod DIGIT_BASE^2. | 1548 // args[_RHO.._RHO_HI] = 1/args[_X.._X_HI] mod _DIGIT_BASE^2. |
1455 static void _invDigitPair(Uint32List args) { | 1549 static void _invDigitPair(Uint32List args) { |
1456 var xl = args[_X]; // Lower 32-bit digit of x. | 1550 var xl = args[_X]; // Lower 32-bit digit of x. |
1457 var y = xl & 3; // y == 1/x mod 2^2 | 1551 var y = xl & 3; // y == 1/x mod 2^2 |
1458 y = (y*(2 - (xl & 0xf)*y)) & 0xf; // y == 1/x mod 2^4 | 1552 y = (y*(2 - (xl & 0xf)*y)) & 0xf; // y == 1/x mod 2^4 |
1459 y = (y*(2 - (xl & 0xff)*y)) & 0xff; // y == 1/x mod 2^8 | 1553 y = (y*(2 - (xl & 0xff)*y)) & 0xff; // y == 1/x mod 2^8 |
1460 y = (y*(2 - (((xl & 0xffff)*y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16 | 1554 y = (y*(2 - (((xl & 0xffff)*y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16 |
1461 y = (y*(2 - ((xl*y) & 0xffffffff))) & 0xffffffff; // y == 1/x mod 2^32 | 1555 y = (y*(2 - ((xl*y) & 0xffffffff))) & 0xffffffff; // y == 1/x mod 2^32 |
1462 var x = (args[_X_HI] << _Bigint.DIGIT_BITS) | xl; | 1556 var x = (args[_X_HI] << _Bigint._DIGIT_BITS) | xl; |
1463 y = (y*(2 - ((x*y) & 0xffffffffffffffff))) & 0xffffffffffffffff; | 1557 y = (y*(2 - ((x*y) & 0xffffffffffffffff))) & 0xffffffffffffffff; |
1464 // y == 1/x mod DIGIT_BASE^2 | 1558 // y == 1/x mod _DIGIT_BASE^2 |
1465 y = -y; // We really want the negative inverse. | 1559 y = -y; // We really want the negative inverse. |
1466 args[_RHO] = y & _Bigint.DIGIT_MASK; | 1560 args[_RHO] = y & _Bigint._DIGIT_MASK; |
1467 args[_RHO_HI] = (y >> _Bigint.DIGIT_BITS) & _Bigint.DIGIT_MASK; | 1561 args[_RHO_HI] = (y >> _Bigint._DIGIT_BITS) & _Bigint._DIGIT_MASK; |
1468 } | 1562 } |
1469 | 1563 |
1470 | |
1471 // Operation: | 1564 // Operation: |
1472 // args[_MU] = args[_RHO]*digits[i] mod DIGIT_BASE. | 1565 // args[_MU] = args[_RHO]*digits[i] mod _DIGIT_BASE. |
1473 // return 1. | 1566 // return 1. |
1474 // Note: intrinsics on 64-bit platform may process a digit pair: | 1567 // Note: Intrinsics on 64-bit platforms process digit pairs at even indices: |
1475 // args[_MU.._MU_HI] = args[_RHO.._RHO_HI]*digits[i..i+1] mod DIGIT_BASE^2. | 1568 // args[_MU.._MU_HI] = args[_RHO.._RHO_HI]*digits[i..i+1] mod _DIGIT_BASE^2. |
1476 // return 2. | 1569 // return 2. |
1477 static int _mulMod(Uint32List args, Uint32List digits, int i) { | 1570 static int _mulMod(Uint32List args, Uint32List digits, int i) { |
1478 const int MU_MASK = (1 << (_Bigint.DIGIT_BITS - _Bigint.DIGIT2_BITS)) - 1; | 1571 // Verify that digit pairs are accessible for 64-bit processing. |
1479 var rhol = args[_RHO] & _Bigint.DIGIT2_MASK; | 1572 assert(digits.length > (i | 1)); |
1480 var rhoh = args[_RHO] >> _Bigint.DIGIT2_BITS; | 1573 const int MU_MASK = (1 << (_Bigint._DIGIT_BITS - _Bigint._DIGIT2_BITS)) - 1; |
1481 var dh = digits[i] >> _Bigint.DIGIT2_BITS; | 1574 var rhol = args[_RHO] & _Bigint._DIGIT2_MASK; |
1482 var dl = digits[i] & _Bigint.DIGIT2_MASK; | 1575 var rhoh = args[_RHO] >> _Bigint._DIGIT2_BITS; |
1576 var dh = digits[i] >> _Bigint._DIGIT2_BITS; | |
1577 var dl = digits[i] & _Bigint._DIGIT2_MASK; | |
1483 args[_MU] = | 1578 args[_MU] = |
1484 (dl*rhol + (((dl*rhoh + dh*rhol) & MU_MASK) << _Bigint.DIGIT2_BITS)) | 1579 (dl*rhol + (((dl*rhoh + dh*rhol) & MU_MASK) << _Bigint._DIGIT2_BITS)) |
1485 & _Bigint.DIGIT_MASK; | 1580 & _Bigint._DIGIT_MASK; |
1486 return 1; | 1581 return 1; |
1487 } | 1582 } |
1488 | 1583 |
1489 // Return x*R mod _m | 1584 // r = x*R mod _m. |
1490 _Bigint _convert(_Bigint x) { | 1585 // Return r_used. |
1491 var r = new _Bigint(); | 1586 int _convert(_Bigint x, Uint32List r_digits) { |
1492 x.abs()._dlShiftTo(_m._used, r); | 1587 var r = x._abs()._dlShift(_m._used)._rem(_m); |
1493 r._divRemTo(_m, null, r); | |
1494 if (x._neg && !r._neg && r._used > 0) { | 1588 if (x._neg && !r._neg && r._used > 0) { |
1495 _m._subTo(r, r); | 1589 r = _m._sub(r); |
1496 } | 1590 } |
1497 return r; | 1591 var used = r._used; |
1592 var digits = r._digits; | |
1593 var i = used + (used & 1); | |
1594 while (--i >= 0) { | |
1595 r_digits[i] = digits[i]; | |
1596 } | |
1597 return used; | |
1498 } | 1598 } |
1499 | 1599 |
1500 // Return x/R mod _m | 1600 _Bigint _revert(Uint32List x_digits, int x_used) { |
1501 _Bigint _revert(_Bigint x) { | 1601 var r_digits = new Uint32List(_mused2p2); |
1502 var r = new _Bigint(); | 1602 var i = x_used + (x_used & 1); |
1503 x._copyTo(r); | 1603 while (--i >= 0) { |
1504 _reduce(r); | 1604 r_digits[i] = x_digits[i]; |
1505 return r; | 1605 } |
1606 var r_used = _reduce(r_digits, x_used); | |
1607 return new _Bigint(false, r_used, r_digits); | |
1506 } | 1608 } |
1507 | 1609 |
1508 // x = x/R mod _m | 1610 // x = x/R mod _m. |
1509 void _reduce(_Bigint x) { | 1611 // Return x_used. |
1510 x._ensureLength(_mused2 + 1); | 1612 int _reduce(Uint32List x_digits, int x_used) { |
1511 var x_digits = x._digits; | 1613 while (x_used < _mused2p2) { // Pad x so _mulAdd has enough room later. |
1512 while (x._used <= _mused2) { // Pad x so _mulAdd has enough room later. | 1614 x_digits[x_used++] = 0; |
1513 x_digits[x._used++] = 0; | |
1514 } | 1615 } |
1515 x_digits[x._used] = 0; // Set leading zero for 64-bit processing. | |
1516 var m_used = _m._used; | 1616 var m_used = _m._used; |
1517 var m_digits = _m._digits; | 1617 var m_digits = _m._digits; |
1518 var i = 0; | 1618 var i = 0; |
1519 while (i < m_used) { | 1619 while (i < m_used) { |
1520 var d = _mulMod(_args, x_digits, i); | 1620 var d = _mulMod(_args, x_digits, i); |
1521 assert(d == _digits_per_step); | 1621 assert(d == _digits_per_step); |
1522 d = _Bigint._mulAdd(_args, _MU, m_digits, 0, x_digits, i, m_used); | 1622 d = _Bigint._mulAdd(_args, _MU, m_digits, 0, x_digits, i, m_used); |
1523 assert(d == _digits_per_step); | 1623 assert(d == _digits_per_step); |
1524 i += d; | 1624 i += d; |
1525 } | 1625 } |
1526 x._clamp(); | 1626 // Clamp x. |
1527 x._drShiftTo(m_used, x); | 1627 while (x_used > 0 && x_digits[x_used - 1] == 0) { |
1528 if (x._compareTo(_m) >= 0) { | 1628 --x_used; |
1529 x._subTo(_m, x); | |
1530 } | 1629 } |
1630 x_used = _Bigint._drShiftDigits(x_digits, x_used, m_used, x_digits); | |
1631 if (_Bigint._compareDigits(x_digits, x_used, m_digits, m_used) >= 0) { | |
1632 _Bigint._absSub(x_digits, x_used, m_digits, m_used, x_digits); | |
1633 } | |
1634 // Clamp x. | |
1635 while (x_used > 0 && x_digits[x_used - 1] == 0) { | |
1636 --x_used; | |
1637 } | |
1638 return x_used; | |
1531 } | 1639 } |
1532 | 1640 |
1533 // r = x^2/R mod _m ; x != r | 1641 int _sqr(Uint32List x_digits, int x_used, Uint32List r_digits) { |
1534 void _sqrTo(_Bigint x, _Bigint r) { | 1642 var r_used = _Bigint._sqrDigits(x_digits, x_used, r_digits); |
1535 x._sqrTo(r); | 1643 return _reduce(r_digits, r_used); |
1536 _reduce(r); | |
1537 } | 1644 } |
1538 | 1645 |
1539 // r = x*y/R mod _m ; x, y != r | 1646 int _mul(Uint32List x_digits, int x_used, |
1540 void _mulTo(_Bigint x, _Bigint y, _Bigint r) { | 1647 Uint32List y_digits, int y_used, |
1541 x._mulTo(y, r); | 1648 Uint32List r_digits) { |
1542 _reduce(r); | 1649 var r_used = _Bigint._mulDigits(x_digits, x_used, |
1650 y_digits, y_used, | |
1651 r_digits); | |
1652 return _reduce(r_digits, r_used); | |
1543 } | 1653 } |
1544 } | 1654 } |
1545 | 1655 |
1546 // Modular reduction using "classic" algorithm. | 1656 // Modular reduction using "classic" algorithm. |
1547 class _Classic implements _Reduction { | 1657 class _Classic implements _Reduction { |
1548 _Bigint _m; | 1658 _Bigint _m; // Modulus. |
1659 _Bigint _norm_m; // Normalized _m. | |
1660 Uint32List _neg_norm_m_digits; // Negated _norm_m digits. | |
1661 int _m_nsh; // Normalization shift amount. | |
1662 Uint32List _mt_qd; // Top _norm_m digit(s) and place holder for | |
1663 // estimated quotient digit(s). | |
1664 Uint32List _t_digits; // Temporary digits used during reduction. | |
1549 | 1665 |
1550 _Classic(int m) { | 1666 _Classic(int m) { |
1551 _m = m._toBigint(); | 1667 _m = m._toBigint(); |
1668 // Preprocess arguments to _remDigits. | |
1669 var nsh = _Bigint._DIGIT_BITS - _Bigint._nbits(_m._digits[_m._used - 1]); | |
1670 // For 64-bit processing, make sure _norm_m_digits has an even number of | |
1671 // digits. | |
1672 if (_m._used.isOdd) { | |
1673 nsh += _Bigint._DIGIT_BITS; | |
1674 } | |
1675 _m_nsh = nsh; | |
1676 _norm_m = _m._lShift(nsh); | |
1677 var nm_used = _norm_m._used; | |
1678 assert(nm_used.isEven); | |
1679 _mt_qd = new Uint32List(4); | |
1680 _mt_qd[_Bigint._YT_LO] = _norm_m._digits[nm_used - 2]; | |
1681 _mt_qd[_Bigint._YT] = _norm_m._digits[nm_used - 1]; | |
1682 // Negate _norm_m so we can use _mulAdd instead of unimplemented _mulSub. | |
1683 var neg_norm_m = _Bigint._ONE._dlShift(nm_used)._sub(_norm_m); | |
1684 if (neg_norm_m._used < nm_used) { | |
1685 _neg_norm_m_digits = | |
1686 _Bigint._cloneDigits(neg_norm_m._digits, 0, nm_used, nm_used); | |
1687 } else { | |
1688 _neg_norm_m_digits = neg_norm_m._digits; | |
1689 } | |
1690 // _neg_norm_m_digits is read-only and has nm_used digits (possibly | |
1691 // including several leading zeros) plus a leading zero for 64-bit | |
1692 // processing. | |
1693 _t_digits = new Uint32List(2*nm_used); | |
1552 } | 1694 } |
1553 | 1695 |
1554 _Bigint _convert(_Bigint x) { | 1696 int _convert(_Bigint x, Uint32List r_digits) { |
1555 if (x._neg || x._compareTo(_m) >= 0) { | 1697 var digits; |
1556 var r = new _Bigint(); | 1698 var used; |
1557 x._divRemTo(_m, null, r); | 1699 if (x._neg || x._compare(_m) >= 0) { |
1700 var r = x.rem(_m); | |
1558 if (x._neg && !r._neg && r._used > 0) { | 1701 if (x._neg && !r._neg && r._used > 0) { |
1559 _m._subTo(r, r); | 1702 r = _m._sub(r); |
1560 } | 1703 } |
1561 return r; | 1704 assert(!r._neg); |
1705 used = r._used; | |
1706 digits = r._digits; | |
1707 } else { | |
1708 used = x._used; | |
1709 digits = x._digits; | |
1562 } | 1710 } |
1563 return x; | 1711 var i = used + (used + 1); // Copy leading zero if any. |
1712 while (--i >= 0) { | |
1713 r_digits[i] = digits[i]; | |
1714 } | |
1715 return used; | |
1564 } | 1716 } |
1565 | 1717 |
1566 _Bigint _revert(_Bigint x) { | 1718 _Bigint _revert(Uint32List x_digits, int x_used) { |
1567 return x; | 1719 return new _Bigint(false, x_used, x_digits); |
1568 } | 1720 } |
1569 | 1721 |
1570 void _reduce(_Bigint x) { | 1722 int _reduce(Uint32List x_digits, int x_used) { |
1571 x._divRemTo(_m, null, x); | 1723 // The function _remDigits(...) is optimized for reduction and equivalent to |
1724 // calling _convert(_revert(x_digits, x_used)._rem(_m), x_digits); | |
1725 return _Bigint._remDigits(x_digits, x_used, | |
1726 _norm_m._digits, _norm_m._used, | |
1727 _neg_norm_m_digits, | |
1728 _m_nsh, | |
1729 _mt_qd, | |
1730 _t_digits, | |
1731 x_digits); | |
1572 } | 1732 } |
1573 | 1733 |
1574 void _sqrTo(_Bigint x, _Bigint r) { | 1734 int _sqr(Uint32List x_digits, int x_used, Uint32List r_digits) { |
1575 x._sqrTo(r); | 1735 var r_used = _Bigint._sqrDigits(x_digits, x_used, r_digits); |
1576 _reduce(r); | 1736 return _reduce(r_digits, r_used); |
1577 } | 1737 } |
1578 | 1738 |
1579 void _mulTo(_Bigint x, _Bigint y, _Bigint r) { | 1739 int _mul(Uint32List x_digits, int x_used, |
1580 x._mulTo(y, r); | 1740 Uint32List y_digits, int y_used, |
1581 _reduce(r); | 1741 Uint32List r_digits) { |
1742 var r_used = _Bigint._mulDigits(x_digits, x_used, | |
1743 y_digits, y_used, | |
1744 r_digits); | |
1745 return _reduce(r_digits, r_used); | |
1582 } | 1746 } |
1583 } | 1747 } |
OLD | NEW |