Commit | Line | Data |
---|---|---|
05780f4b MM |
1 | #include "BigUnsigned.hh" |
2 | ||
3e132790 | 3 | // Memory management definitions have moved to the bottom of NumberlikeArray.hh. |
05780f4b | 4 | |
3e132790 | 5 | // CONSTRUCTION FROM PRIMITIVE INTEGERS |
05780f4b | 6 | |
3e132790 MM |
7 | /* Initialize this BigUnsigned from the given primitive integer. The same |
8 | * pattern works for all primitive integer types, so I put it into a template to | |
9 | * reduce code duplication. (Don't worry: this is protected and we instantiate | |
10 | * it only with primitive integer types.) Type X could be signed, but x is | |
11 | * known to be nonnegative. */ | |
12 | template <class X> | |
13 | void BigUnsigned::initFromPrimitive(X x) { | |
b3fe29df | 14 | if (x == 0) |
3e132790 | 15 | ; // NumberlikeArray already initialized us to zero. |
b3fe29df | 16 | else { |
3e132790 | 17 | // Create a single block. blk is NULL; no need to delete it. |
05780f4b | 18 | cap = 1; |
a8b42b68 | 19 | blk = new Blk[1]; |
05780f4b MM |
20 | len = 1; |
21 | blk[0] = Blk(x); | |
22 | } | |
23 | } | |
24 | ||
3e132790 MM |
25 | /* Ditto, but first check that x is nonnegative. I could have put the check in |
26 | * initFromPrimitive and let the compiler optimize it out for unsigned-type | |
27 | * instantiations, but I wanted to avoid the warning stupidly issued by g++ for | |
28 | * a condition that is constant in *any* instantiation, even if not in all. */ | |
29 | template <class X> | |
30 | void BigUnsigned::initFromSignedPrimitive(X x) { | |
31 | if (x < 0) | |
32 | throw "BigUnsigned constructor: " | |
33 | "Cannot construct a BigUnsigned from a negative number"; | |
34 | else | |
35 | initFromPrimitive(x); | |
05780f4b MM |
36 | } |
37 | ||
3e132790 MM |
38 | BigUnsigned::BigUnsigned(unsigned long x) { initFromPrimitive (x); } |
39 | BigUnsigned::BigUnsigned(unsigned int x) { initFromPrimitive (x); } | |
40 | BigUnsigned::BigUnsigned(unsigned short x) { initFromPrimitive (x); } | |
41 | BigUnsigned::BigUnsigned( long x) { initFromSignedPrimitive(x); } | |
42 | BigUnsigned::BigUnsigned( int x) { initFromSignedPrimitive(x); } | |
43 | BigUnsigned::BigUnsigned( short x) { initFromSignedPrimitive(x); } | |
05780f4b | 44 | |
3e132790 | 45 | // CONVERSION TO PRIMITIVE INTEGERS |
05780f4b | 46 | |
3e132790 MM |
47 | /* Template with the same idea as initFromPrimitive. This might be slightly |
48 | * slower than the previous version with the masks, but it's much shorter and | |
49 | * clearer, which is the library's stated goal. */ | |
50 | template <class X> | |
51 | X BigUnsigned::convertToPrimitive() const { | |
05780f4b | 52 | if (len == 0) |
3e132790 | 53 | // The number is zero; return zero. |
05780f4b | 54 | return 0; |
3e132790 MM |
55 | else if (len == 1) { |
56 | // The single block might fit in an X. Try the conversion. | |
57 | X x = X(blk[0]); | |
58 | // Make sure the result accurately represents the block. | |
59 | if (Blk(x) == blk[0]) | |
60 | // Successful conversion. | |
61 | return x; | |
62 | // Otherwise fall through. | |
63 | } | |
64 | throw "BigUnsigned::to<Primitive>: " | |
65 | "Value is too big to fit in the requested type"; | |
05780f4b MM |
66 | } |
67 | ||
3e132790 MM |
68 | /* Wrap the above in an x >= 0 test to make sure we got a nonnegative result, |
69 | * not a negative one that happened to convert back into the correct nonnegative | |
70 | * one. (E.g., catch incorrect conversion of 2^31 to the long -2^31.) Again, | |
71 | * separated to avoid a g++ warning. */ | |
72 | template <class X> | |
73 | X BigUnsigned::convertToSignedPrimitive() const { | |
74 | X x = convertToPrimitive<X>(); | |
75 | if (x >= 0) | |
76 | return x; | |
05780f4b | 77 | else |
3e132790 MM |
78 | throw "BigUnsigned::to(Primitive): " |
79 | "Value is too big to fit in the requested type"; | |
05780f4b MM |
80 | } |
81 | ||
3e132790 MM |
82 | unsigned long BigUnsigned::toUnsignedLong() const { |
83 | return convertToPrimitive<unsigned long>(); | |
05780f4b | 84 | } |
3e132790 MM |
85 | unsigned int BigUnsigned::toUnsignedInt() const { |
86 | return convertToPrimitive<unsigned int>(); | |
05780f4b | 87 | } |
3e132790 MM |
88 | unsigned short BigUnsigned::toUnsignedShort() const { |
89 | return convertToPrimitive<unsigned short>(); | |
05780f4b | 90 | } |
3e132790 MM |
91 | long BigUnsigned::toLong() const { |
92 | return convertToSignedPrimitive<long>(); | |
93 | } | |
94 | int BigUnsigned::toInt() const { | |
95 | return convertToSignedPrimitive<int>(); | |
96 | } | |
97 | short BigUnsigned::toShort() const { | |
98 | return convertToSignedPrimitive<short>(); | |
05780f4b MM |
99 | } |
100 | ||
101 | // COMPARISON | |
102 | BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const { | |
103 | // A bigger length implies a bigger number. | |
104 | if (len < x.len) | |
105 | return less; | |
106 | else if (len > x.len) | |
107 | return greater; | |
108 | else { | |
109 | // Compare blocks one by one from left to right. | |
110 | Index i = len; | |
111 | while (i > 0) { | |
112 | i--; | |
113 | if (blk[i] == x.blk[i]) | |
114 | continue; | |
115 | else if (blk[i] > x.blk[i]) | |
116 | return greater; | |
117 | else | |
118 | return less; | |
119 | } | |
120 | // If no blocks differed, the numbers are equal. | |
121 | return equal; | |
122 | } | |
123 | } | |
124 | ||
3e132790 | 125 | // COPY-LESS OPERATIONS |
4efbb076 | 126 | |
8c16728a | 127 | /* |
3e132790 | 128 | * On most calls to copy-less operations, it's safe to read the inputs little by |
8c16728a MM |
129 | * little and write the outputs little by little. However, if one of the |
130 | * inputs is coming from the same variable into which the output is to be | |
131 | * stored (an "aliased" call), we risk overwriting the input before we read it. | |
132 | * In this case, we first compute the result into a temporary BigUnsigned | |
133 | * variable and then copy it into the requested output variable *this. | |
ef2b7c59 | 134 | * Each put-here operation uses the DTRT_ALIASED macro (Do The Right Thing on |
8c16728a MM |
135 | * aliased calls) to generate code for this check. |
136 | * | |
137 | * I adopted this approach on 2007.02.13 (see Assignment Operators in | |
138 | * BigUnsigned.hh). Before then, put-here operations rejected aliased calls | |
139 | * with an exception. I think doing the right thing is better. | |
140 | * | |
141 | * Some of the put-here operations can probably handle aliased calls safely | |
142 | * without the extra copy because (for example) they process blocks strictly | |
143 | * right-to-left. At some point I might determine which ones don't need the | |
144 | * copy, but my reasoning would need to be verified very carefully. For now | |
145 | * I'll leave in the copy. | |
146 | */ | |
ef2b7c59 | 147 | #define DTRT_ALIASED(cond, op) \ |
8c16728a MM |
148 | if (cond) { \ |
149 | BigUnsigned tmpThis; \ | |
150 | tmpThis.op; \ | |
151 | *this = tmpThis; \ | |
152 | return; \ | |
153 | } | |
154 | ||
3e132790 MM |
155 | |
156 | ||
05780f4b | 157 | void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) { |
ef2b7c59 | 158 | DTRT_ALIASED(this == &a || this == &b, add(a, b)); |
05780f4b MM |
159 | // If one argument is zero, copy the other. |
160 | if (a.len == 0) { | |
161 | operator =(b); | |
162 | return; | |
163 | } else if (b.len == 0) { | |
164 | operator =(a); | |
165 | return; | |
166 | } | |
4efbb076 | 167 | // Some variables... |
05780f4b MM |
168 | // Carries in and out of an addition stage |
169 | bool carryIn, carryOut; | |
170 | Blk temp; | |
171 | Index i; | |
172 | // a2 points to the longer input, b2 points to the shorter | |
173 | const BigUnsigned *a2, *b2; | |
174 | if (a.len >= b.len) { | |
175 | a2 = &a; | |
176 | b2 = &b; | |
177 | } else { | |
178 | a2 = &b; | |
179 | b2 = &a; | |
180 | } | |
181 | // Set prelimiary length and make room in this BigUnsigned | |
182 | len = a2->len + 1; | |
183 | allocate(len); | |
184 | // For each block index that is present in both inputs... | |
185 | for (i = 0, carryIn = false; i < b2->len; i++) { | |
186 | // Add input blocks | |
187 | temp = a2->blk[i] + b2->blk[i]; | |
188 | // If a rollover occurred, the result is less than either input. | |
189 | // This test is used many times in the BigUnsigned code. | |
190 | carryOut = (temp < a2->blk[i]); | |
191 | // If a carry was input, handle it | |
192 | if (carryIn) { | |
193 | temp++; | |
194 | carryOut |= (temp == 0); | |
195 | } | |
196 | blk[i] = temp; // Save the addition result | |
197 | carryIn = carryOut; // Pass the carry along | |
198 | } | |
199 | // If there is a carry left over, increase blocks until | |
200 | // one does not roll over. | |
201 | for (; i < a2->len && carryIn; i++) { | |
202 | temp = a2->blk[i] + 1; | |
203 | carryIn = (temp == 0); | |
204 | blk[i] = temp; | |
205 | } | |
206 | // If the carry was resolved but the larger number | |
207 | // still has blocks, copy them over. | |
208 | for (; i < a2->len; i++) | |
209 | blk[i] = a2->blk[i]; | |
210 | // Set the extra block if there's still a carry, decrease length otherwise | |
211 | if (carryIn) | |
212 | blk[i] = 1; | |
213 | else | |
214 | len--; | |
215 | } | |
216 | ||
05780f4b | 217 | void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) { |
ef2b7c59 | 218 | DTRT_ALIASED(this == &a || this == &b, subtract(a, b)); |
05780f4b | 219 | if (b.len == 0) { |
3e132790 | 220 | // If b is zero, copy a. |
05780f4b MM |
221 | operator =(a); |
222 | return; | |
223 | } else if (a.len < b.len) | |
3e132790 MM |
224 | // If a is shorter than b, the result is negative. |
225 | throw "BigUnsigned::subtract: " | |
226 | "Negative result in unsigned calculation"; | |
4efbb076 | 227 | // Some variables... |
05780f4b MM |
228 | bool borrowIn, borrowOut; |
229 | Blk temp; | |
230 | Index i; | |
231 | // Set preliminary length and make room | |
232 | len = a.len; | |
233 | allocate(len); | |
234 | // For each block index that is present in both inputs... | |
235 | for (i = 0, borrowIn = false; i < b.len; i++) { | |
236 | temp = a.blk[i] - b.blk[i]; | |
3e132790 MM |
237 | // If a reverse rollover occurred, |
238 | // the result is greater than the block from a. | |
05780f4b MM |
239 | borrowOut = (temp > a.blk[i]); |
240 | // Handle an incoming borrow | |
241 | if (borrowIn) { | |
242 | borrowOut |= (temp == 0); | |
243 | temp--; | |
244 | } | |
245 | blk[i] = temp; // Save the subtraction result | |
246 | borrowIn = borrowOut; // Pass the borrow along | |
247 | } | |
248 | // If there is a borrow left over, decrease blocks until | |
249 | // one does not reverse rollover. | |
250 | for (; i < a.len && borrowIn; i++) { | |
251 | borrowIn = (a.blk[i] == 0); | |
252 | blk[i] = a.blk[i] - 1; | |
253 | } | |
3e132790 MM |
254 | /* If there's still a borrow, the result is negative. |
255 | * Throw an exception, but zero out this object so as to leave it in a | |
256 | * predictable state. */ | |
05780f4b MM |
257 | if (borrowIn) { |
258 | len = 0; | |
259 | throw "BigUnsigned::subtract: Negative result in unsigned calculation"; | |
3e132790 MM |
260 | } else |
261 | // Copy over the rest of the blocks | |
262 | for (; i < a.len; i++) | |
263 | blk[i] = a.blk[i]; | |
05780f4b MM |
264 | // Zap leading zeros |
265 | zapLeadingZeros(); | |
266 | } | |
267 | ||
4efbb076 | 268 | /* |
6e1e0f2f MM |
269 | * About the multiplication and division algorithms: |
270 | * | |
3e132790 | 271 | * I searched unsucessfully for fast C++ built-in operations like the `b_0' |
6e1e0f2f MM |
272 | * and `c_0' Knuth describes in Section 4.3.1 of ``The Art of Computer |
273 | * Programming'' (replace `place' by `Blk'): | |
274 | * | |
275 | * ``b_0[:] multiplication of a one-place integer by another one-place | |
276 | * integer, giving a two-place answer; | |
277 | * | |
278 | * ``c_0[:] division of a two-place integer by a one-place integer, | |
279 | * provided that the quotient is a one-place integer, and yielding | |
280 | * also a one-place remainder.'' | |
281 | * | |
282 | * I also missed his note that ``[b]y adjusting the word size, if | |
283 | * necessary, nearly all computers will have these three operations | |
284 | * available'', so I gave up on trying to use algorithms similar to his. | |
285 | * A future version of the library might include such algorithms; I | |
286 | * would welcome contributions from others for this. | |
287 | * | |
288 | * I eventually decided to use bit-shifting algorithms. To multiply `a' | |
289 | * and `b', we zero out the result. Then, for each `1' bit in `a', we | |
290 | * shift `b' left the appropriate amount and add it to the result. | |
291 | * Similarly, to divide `a' by `b', we shift `b' left varying amounts, | |
292 | * repeatedly trying to subtract it from `a'. When we succeed, we note | |
293 | * the fact by setting a bit in the quotient. While these algorithms | |
294 | * have the same O(n^2) time complexity as Knuth's, the ``constant factor'' | |
295 | * is likely to be larger. | |
296 | * | |
297 | * Because I used these algorithms, which require single-block addition | |
298 | * and subtraction rather than single-block multiplication and division, | |
299 | * the innermost loops of all four routines are very similar. Study one | |
300 | * of them and all will become clear. | |
301 | */ | |
4efbb076 MM |
302 | |
303 | /* | |
6e1e0f2f MM |
304 | * This is a little inline function used by both the multiplication |
305 | * routine and the division routine. | |
306 | * | |
307 | * `getShiftedBlock' returns the `x'th block of `num << y'. | |
308 | * `y' may be anything from 0 to N - 1, and `x' may be anything from | |
309 | * 0 to `num.len'. | |
310 | * | |
311 | * Two things contribute to this block: | |
312 | * | |
313 | * (1) The `N - y' low bits of `num.blk[x]', shifted `y' bits left. | |
314 | * | |
315 | * (2) The `y' high bits of `num.blk[x-1]', shifted `N - y' bits right. | |
316 | * | |
317 | * But we must be careful if `x == 0' or `x == num.len', in | |
318 | * which case we should use 0 instead of (2) or (1), respectively. | |
319 | * | |
320 | * If `y == 0', then (2) contributes 0, as it should. However, | |
321 | * in some computer environments, for a reason I cannot understand, | |
322 | * `a >> b' means `a >> (b % N)'. This means `num.blk[x-1] >> (N - y)' | |
323 | * will return `num.blk[x-1]' instead of the desired 0 when `y == 0'; | |
324 | * the test `y == 0' handles this case specially. | |
325 | */ | |
4efbb076 MM |
326 | inline BigUnsigned::Blk getShiftedBlock(const BigUnsigned &num, |
327 | BigUnsigned::Index x, unsigned int y) { | |
328 | BigUnsigned::Blk part1 = (x == 0 || y == 0) ? 0 : (num.blk[x - 1] >> (BigUnsigned::N - y)); | |
329 | BigUnsigned::Blk part2 = (x == num.len) ? 0 : (num.blk[x] << y); | |
330 | return part1 | part2; | |
331 | } | |
332 | ||
05780f4b | 333 | void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { |
ef2b7c59 | 334 | DTRT_ALIASED(this == &a || this == &b, multiply(a, b)); |
05780f4b MM |
335 | // If either a or b is zero, set to zero. |
336 | if (a.len == 0 || b.len == 0) { | |
337 | len = 0; | |
338 | return; | |
339 | } | |
4efbb076 | 340 | /* |
6e1e0f2f MM |
341 | * Overall method: |
342 | * | |
343 | * Set this = 0. | |
344 | * For each 1-bit of `a' (say the `i2'th bit of block `i'): | |
345 | * Add `b << (i blocks and i2 bits)' to *this. | |
346 | */ | |
05780f4b MM |
347 | // Variables for the calculation |
348 | Index i, j, k; | |
349 | unsigned int i2; | |
4efbb076 | 350 | Blk temp; |
05780f4b MM |
351 | bool carryIn, carryOut; |
352 | // Set preliminary length and make room | |
353 | len = a.len + b.len; | |
354 | allocate(len); | |
355 | // Zero out this object | |
356 | for (i = 0; i < len; i++) | |
357 | blk[i] = 0; | |
358 | // For each block of the first number... | |
359 | for (i = 0; i < a.len; i++) { | |
360 | // For each 1-bit of that block... | |
4efbb076 | 361 | for (i2 = 0; i2 < N; i2++) { |
26a5f52b | 362 | if ((a.blk[i] & (Blk(1) << i2)) == 0) |
05780f4b | 363 | continue; |
4efbb076 | 364 | /* |
6e1e0f2f MM |
365 | * Add b to this, shifted left i blocks and i2 bits. |
366 | * j is the index in b, and k = i + j is the index in this. | |
367 | * | |
368 | * `getShiftedBlock', a short inline function defined above, | |
369 | * is now used for the bit handling. It replaces the more | |
370 | * complex `bHigh' code, in which each run of the loop dealt | |
371 | * immediately with the low bits and saved the high bits to | |
372 | * be picked up next time. The last run of the loop used to | |
373 | * leave leftover high bits, which were handled separately. | |
374 | * Instead, this loop runs an additional time with j == b.len. | |
375 | * These changes were made on 2005.01.11. | |
376 | */ | |
4efbb076 MM |
377 | for (j = 0, k = i, carryIn = false; j <= b.len; j++, k++) { |
378 | /* | |
6e1e0f2f MM |
379 | * The body of this loop is very similar to the body of the first loop |
380 | * in `add', except that this loop does a `+=' instead of a `+'. | |
381 | */ | |
4efbb076 | 382 | temp = blk[k] + getShiftedBlock(b, j, i2); |
05780f4b MM |
383 | carryOut = (temp < blk[k]); |
384 | if (carryIn) { | |
385 | temp++; | |
386 | carryOut |= (temp == 0); | |
387 | } | |
388 | blk[k] = temp; | |
389 | carryIn = carryOut; | |
05780f4b | 390 | } |
4efbb076 MM |
391 | // No more extra iteration to deal with `bHigh'. |
392 | // Roll-over a carry as necessary. | |
05780f4b MM |
393 | for (; carryIn; k++) { |
394 | blk[k]++; | |
395 | carryIn = (blk[k] == 0); | |
396 | } | |
397 | } | |
398 | } | |
399 | // Zap possible leading zero | |
400 | if (blk[len - 1] == 0) | |
401 | len--; | |
402 | } | |
403 | ||
404 | /* | |
6e1e0f2f | 405 | * DIVISION WITH REMAINDER |
3e132790 MM |
406 | * This monstrous function mods *this by the given divisor b while storing the |
407 | * quotient in the given object q; at the end, *this contains the remainder. | |
408 | * The seemingly bizarre pattern of inputs and outputs was chosen so that the | |
409 | * function copies as little as possible (since it is implemented by repeated | |
410 | * subtraction of multiples of b from *this). | |
411 | * | |
412 | * "modWithQuotient" might be a better name for this function, but I would | |
413 | * rather not change the name now. | |
6e1e0f2f | 414 | */ |
05780f4b | 415 | void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { |
3e132790 MM |
416 | /* Defending against aliased calls is more complex than usual because we |
417 | * are writing to both *this and q. | |
8c16728a MM |
418 | * |
419 | * It would be silly to try to write quotient and remainder to the | |
3e132790 | 420 | * same variable. Rule that out right away. */ |
8c16728a MM |
421 | if (this == &q) |
422 | throw "BigUnsigned::divideWithRemainder: Cannot write quotient and remainder into the same variable"; | |
3e132790 MM |
423 | /* Now *this and q are separate, so the only concern is that b might be |
424 | * aliased to one of them. If so, use a temporary copy of b. */ | |
8c16728a MM |
425 | if (this == &b || &q == &b) { |
426 | BigUnsigned tmpB(b); | |
427 | divideWithRemainder(tmpB, q); | |
428 | return; | |
429 | } | |
5ff40cf5 | 430 | |
05780f4b | 431 | /* |
3e132790 MM |
432 | * Knuth's definition of mod (which this function uses) is somewhat |
433 | * different from the C++ definition of % in case of division by 0. | |
6e1e0f2f | 434 | * |
3e132790 MM |
435 | * We let a / 0 == 0 (it doesn't matter much) and a % 0 == a, no |
436 | * exceptions thrown. This allows us to preserve both Knuth's demand | |
437 | * that a mod 0 == a and the useful property that | |
438 | * (a / b) * b + (a % b) == a. | |
6e1e0f2f | 439 | */ |
05780f4b MM |
440 | if (b.len == 0) { |
441 | q.len = 0; | |
442 | return; | |
443 | } | |
5ff40cf5 | 444 | |
05780f4b | 445 | /* |
6e1e0f2f MM |
446 | * If *this.len < b.len, then *this < b, and we can be sure that b doesn't go into |
447 | * *this at all. The quotient is 0 and *this is already the remainder (so leave it alone). | |
448 | */ | |
05780f4b MM |
449 | if (len < b.len) { |
450 | q.len = 0; | |
451 | return; | |
452 | } | |
5ff40cf5 | 453 | |
3e132790 | 454 | // At this point we know (*this).len >= b.len > 0. (Whew!) |
5ff40cf5 | 455 | |
05780f4b | 456 | /* |
6e1e0f2f MM |
457 | * Overall method: |
458 | * | |
459 | * For each appropriate i and i2, decreasing: | |
3e132790 MM |
460 | * Subtract (b << (i blocks and i2 bits)) from *this, storing the |
461 | * result in subtractBuf. | |
462 | * If the subtraction succeeds with a nonnegative result: | |
6e1e0f2f | 463 | * Turn on bit i2 of block i of the quotient q. |
3e132790 MM |
464 | * Copy subtractBuf back into *this. |
465 | * Otherwise bit i2 of block i remains off, and *this is unchanged. | |
6e1e0f2f MM |
466 | * |
467 | * Eventually q will contain the entire quotient, and *this will | |
468 | * be left with the remainder. | |
469 | * | |
3e132790 MM |
470 | * subtractBuf[x] corresponds to blk[x], not blk[x+i], since 2005.01.11. |
471 | * But on a single iteration, we don't touch the i lowest blocks of blk | |
472 | * (and don't use those of subtractBuf) because these blocks are | |
473 | * unaffected by the subtraction: we are subtracting | |
474 | * (b << (i blocks and i2 bits)), which ends in at least `i' zero | |
475 | * blocks. */ | |
05780f4b MM |
476 | // Variables for the calculation |
477 | Index i, j, k; | |
478 | unsigned int i2; | |
4efbb076 | 479 | Blk temp; |
05780f4b | 480 | bool borrowIn, borrowOut; |
5ff40cf5 | 481 | |
2f145f11 | 482 | /* |
6e1e0f2f MM |
483 | * Make sure we have an extra zero block just past the value. |
484 | * | |
485 | * When we attempt a subtraction, we might shift `b' so | |
486 | * its first block begins a few bits left of the dividend, | |
487 | * and then we'll try to compare these extra bits with | |
488 | * a nonexistent block to the left of the dividend. The | |
489 | * extra zero block ensures sensible behavior; we need | |
3e132790 | 490 | * an extra block in `subtractBuf' for exactly the same reason. |
6e1e0f2f | 491 | */ |
4efbb076 | 492 | Index origLen = len; // Save real length. |
3e132790 MM |
493 | /* To avoid an out-of-bounds access in case of reallocation, allocate |
494 | * first and then increment the logical length. */ | |
495 | allocateAndCopy(len + 1); | |
496 | len++; | |
497 | blk[origLen] = 0; // Zero the added block. | |
5ff40cf5 | 498 | |
3e132790 MM |
499 | // subtractBuf holds part of the result of a subtraction; see above. |
500 | Blk *subtractBuf = new Blk[len]; | |
5ff40cf5 | 501 | |
05780f4b | 502 | // Set preliminary length for quotient and make room |
2f145f11 | 503 | q.len = origLen - b.len + 1; |
05780f4b MM |
504 | q.allocate(q.len); |
505 | // Zero out the quotient | |
506 | for (i = 0; i < q.len; i++) | |
507 | q.blk[i] = 0; | |
5ff40cf5 | 508 | |
05780f4b MM |
509 | // For each possible left-shift of b in blocks... |
510 | i = q.len; | |
511 | while (i > 0) { | |
512 | i--; | |
513 | // For each possible left-shift of b in bits... | |
4efbb076 | 514 | // (Remember, N is the number of bits in a Blk.) |
05780f4b | 515 | q.blk[i] = 0; |
4efbb076 | 516 | i2 = N; |
05780f4b MM |
517 | while (i2 > 0) { |
518 | i2--; | |
519 | /* | |
6e1e0f2f | 520 | * Subtract b, shifted left i blocks and i2 bits, from *this, |
3e132790 | 521 | * and store the answer in subtractBuf. In the for loop, `k == i + j'. |
6e1e0f2f MM |
522 | * |
523 | * Compare this to the middle section of `multiply'. They | |
524 | * are in many ways analogous. See especially the discussion | |
525 | * of `getShiftedBlock'. | |
526 | */ | |
4efbb076 MM |
527 | for (j = 0, k = i, borrowIn = false; j <= b.len; j++, k++) { |
528 | temp = blk[k] - getShiftedBlock(b, j, i2); | |
05780f4b MM |
529 | borrowOut = (temp > blk[k]); |
530 | if (borrowIn) { | |
531 | borrowOut |= (temp == 0); | |
532 | temp--; | |
533 | } | |
3e132790 MM |
534 | // Since 2005.01.11, indices of `subtractBuf' directly match those of `blk', so use `k'. |
535 | subtractBuf[k] = temp; | |
05780f4b | 536 | borrowIn = borrowOut; |
05780f4b | 537 | } |
4efbb076 MM |
538 | // No more extra iteration to deal with `bHigh'. |
539 | // Roll-over a borrow as necessary. | |
540 | for (; k < origLen && borrowIn; k++) { | |
05780f4b | 541 | borrowIn = (blk[k] == 0); |
3e132790 | 542 | subtractBuf[k] = blk[k] - 1; |
05780f4b | 543 | } |
4efbb076 | 544 | /* |
6e1e0f2f MM |
545 | * If the subtraction was performed successfully (!borrowIn), |
546 | * set bit i2 in block i of the quotient. | |
547 | * | |
3e132790 | 548 | * Then, copy the portion of subtractBuf filled by the subtraction |
6e1e0f2f MM |
549 | * back to *this. This portion starts with block i and ends-- |
550 | * where? Not necessarily at block `i + b.len'! Well, we | |
3e132790 MM |
551 | * increased k every time we saved a block into subtractBuf, so |
552 | * the region of subtractBuf we copy is just [i, k). | |
6e1e0f2f | 553 | */ |
05780f4b | 554 | if (!borrowIn) { |
26a5f52b | 555 | q.blk[i] |= (Blk(1) << i2); |
4efbb076 | 556 | while (k > i) { |
05780f4b | 557 | k--; |
3e132790 | 558 | blk[k] = subtractBuf[k]; |
05780f4b MM |
559 | } |
560 | } | |
561 | } | |
562 | } | |
563 | // Zap possible leading zero in quotient | |
564 | if (q.blk[q.len - 1] == 0) | |
565 | q.len--; | |
566 | // Zap any/all leading zeros in remainder | |
567 | zapLeadingZeros(); | |
3e132790 | 568 | // Deallocate subtractBuf. |
05780f4b | 569 | // (Thanks to Brad Spencer for noticing my accidental omission of this!) |
3e132790 | 570 | delete [] subtractBuf; |
05780f4b MM |
571 | } |
572 | ||
3e132790 MM |
573 | /* BITWISE OPERATORS |
574 | * These are straightforward blockwise operations except that they differ in | |
575 | * the output length and the necessity of zapLeadingZeros. */ | |
576 | ||
05780f4b | 577 | void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) { |
ef2b7c59 | 578 | DTRT_ALIASED(this == &a || this == &b, bitAnd(a, b)); |
3e132790 | 579 | // The bitwise & can't be longer than either operand. |
05780f4b MM |
580 | len = (a.len >= b.len) ? b.len : a.len; |
581 | allocate(len); | |
582 | Index i; | |
583 | for (i = 0; i < len; i++) | |
584 | blk[i] = a.blk[i] & b.blk[i]; | |
585 | zapLeadingZeros(); | |
586 | } | |
587 | ||
05780f4b | 588 | void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) { |
ef2b7c59 | 589 | DTRT_ALIASED(this == &a || this == &b, bitOr(a, b)); |
05780f4b MM |
590 | Index i; |
591 | const BigUnsigned *a2, *b2; | |
592 | if (a.len >= b.len) { | |
593 | a2 = &a; | |
594 | b2 = &b; | |
595 | } else { | |
596 | a2 = &b; | |
597 | b2 = &a; | |
598 | } | |
599 | allocate(a2->len); | |
600 | for (i = 0; i < b2->len; i++) | |
601 | blk[i] = a2->blk[i] | b2->blk[i]; | |
602 | for (; i < a2->len; i++) | |
603 | blk[i] = a2->blk[i]; | |
604 | len = a2->len; | |
3e132790 | 605 | // Doesn't need zapLeadingZeros. |
05780f4b MM |
606 | } |
607 | ||
05780f4b | 608 | void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) { |
ef2b7c59 | 609 | DTRT_ALIASED(this == &a || this == &b, bitXor(a, b)); |
05780f4b MM |
610 | Index i; |
611 | const BigUnsigned *a2, *b2; | |
612 | if (a.len >= b.len) { | |
613 | a2 = &a; | |
614 | b2 = &b; | |
615 | } else { | |
616 | a2 = &b; | |
617 | b2 = &a; | |
618 | } | |
3aaa5ce6 | 619 | allocate(a2->len); |
05780f4b MM |
620 | for (i = 0; i < b2->len; i++) |
621 | blk[i] = a2->blk[i] ^ b2->blk[i]; | |
622 | for (; i < a2->len; i++) | |
623 | blk[i] = a2->blk[i]; | |
624 | len = a2->len; | |
625 | zapLeadingZeros(); | |
626 | } | |
627 | ||
0afe80d5 | 628 | void BigUnsigned::bitShiftLeft(const BigUnsigned &a, int b) { |
ef2b7c59 | 629 | DTRT_ALIASED(this == &a, bitShiftLeft(a, b)); |
0afe80d5 MM |
630 | if (b < 0) { |
631 | if (b << 1 == 0) | |
632 | throw "BigUnsigned::bitShiftLeft: " | |
633 | "Pathological shift amount not implemented"; | |
634 | else { | |
635 | bitShiftRight(a, -b); | |
636 | return; | |
637 | } | |
638 | } | |
ef2b7c59 MM |
639 | Index shiftBlocks = b / N; |
640 | unsigned int shiftBits = b % N; | |
641 | // + 1: room for high bits nudged left into another block | |
642 | len = a.len + shiftBlocks + 1; | |
643 | allocate(len); | |
644 | Index i, j; | |
645 | for (i = 0; i < shiftBlocks; i++) | |
646 | blk[i] = 0; | |
647 | for (j = 0, i = shiftBlocks; j <= a.len; j++, i++) | |
648 | blk[i] = getShiftedBlock(a, j, shiftBits); | |
649 | // Zap possible leading zero | |
650 | if (blk[len - 1] == 0) | |
651 | len--; | |
652 | } | |
653 | ||
0afe80d5 | 654 | void BigUnsigned::bitShiftRight(const BigUnsigned &a, int b) { |
ef2b7c59 | 655 | DTRT_ALIASED(this == &a, bitShiftRight(a, b)); |
0afe80d5 MM |
656 | if (b < 0) { |
657 | if (b << 1 == 0) | |
658 | throw "BigUnsigned::bitShiftRight: " | |
659 | "Pathological shift amount not implemented"; | |
660 | else { | |
661 | bitShiftLeft(a, -b); | |
662 | return; | |
663 | } | |
664 | } | |
ef2b7c59 MM |
665 | // This calculation is wacky, but expressing the shift as a left bit shift |
666 | // within each block lets us use getShiftedBlock. | |
667 | Index rightShiftBlocks = (b + N - 1) / N; | |
668 | unsigned int leftShiftBits = N * rightShiftBlocks - b; | |
669 | // Now (N * rightShiftBlocks - leftShiftBits) == b | |
670 | // and 0 <= leftShiftBits < N. | |
671 | if (rightShiftBlocks >= a.len + 1) { | |
672 | // All of a is guaranteed to be shifted off, even considering the left | |
673 | // bit shift. | |
674 | len = 0; | |
675 | return; | |
676 | } | |
677 | // Now we're allocating a positive amount. | |
678 | // + 1: room for high bits nudged left into another block | |
679 | len = a.len + 1 - rightShiftBlocks; | |
680 | allocate(len); | |
681 | Index i, j; | |
682 | for (j = rightShiftBlocks, i = 0; j <= a.len; j++, i++) | |
683 | blk[i] = getShiftedBlock(a, j, leftShiftBits); | |
684 | // Zap possible leading zero | |
685 | if (blk[len - 1] == 0) | |
686 | len--; | |
687 | } | |
688 | ||
05780f4b MM |
689 | // INCREMENT/DECREMENT OPERATORS |
690 | ||
691 | // Prefix increment | |
692 | void BigUnsigned::operator ++() { | |
693 | Index i; | |
694 | bool carry = true; | |
695 | for (i = 0; i < len && carry; i++) { | |
696 | blk[i]++; | |
697 | carry = (blk[i] == 0); | |
698 | } | |
699 | if (carry) { | |
3e132790 | 700 | // Allocate and then increase length, as in divideWithRemainder |
918d66f2 | 701 | allocateAndCopy(len + 1); |
05780f4b | 702 | len++; |
05780f4b MM |
703 | blk[i] = 1; |
704 | } | |
705 | } | |
706 | ||
707 | // Postfix increment: same as prefix | |
708 | void BigUnsigned::operator ++(int) { | |
709 | operator ++(); | |
710 | } | |
711 | ||
712 | // Prefix decrement | |
713 | void BigUnsigned::operator --() { | |
714 | if (len == 0) | |
715 | throw "BigUnsigned::operator --(): Cannot decrement an unsigned zero"; | |
716 | Index i; | |
717 | bool borrow = true; | |
718 | for (i = 0; borrow; i++) { | |
719 | borrow = (blk[i] == 0); | |
720 | blk[i]--; | |
721 | } | |
722 | // Zap possible leading zero (there can only be one) | |
723 | if (blk[len - 1] == 0) | |
724 | len--; | |
725 | } | |
726 | ||
727 | // Postfix decrement: same as prefix | |
728 | void BigUnsigned::operator --(int) { | |
729 | operator --(); | |
730 | } |