Debian Codegraph @

src/bignum.c

raw
1 /*
2 * bignum.c - multiple precision exact integer arithmetic
3 *
4 * Copyright (c) 2000-2024 Shiro Kawai <[email protected]>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the authors nor the names of its contributors
18 * may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 /* Bignum library. Not optimized well yet---I think bignum performance
35 * is not very critical for Gauche, except a few special cases (like
36 * the cases used in the numeric I/O routine). So the implementation
37 * emphasizes robustness rather than performance.
38 *
39 * Bignum is represented by ScmBignum structure. There are "normalized"
40 * and "denormalized" bignums. Scheme part only sees the normalized
41 * bignums. Normalized bignum uses the minimum words to represent the
42 * given number, and no normalized bignums for the numbers that can be
43 * representable in fixnum. Most external bignum API expects normalized
44 * bignums, and return normalized bignums. Normalized bignums should
45 * be seen as read-only construct.
46 *
47 * Denormalized bignums are used to keep intermediate results.
48 * Denormalized forms shouldn't "leak out" to the Scheme world; but
49 * can be useful to write efficient routine.
50 */
51 /* Cf: Knuth: The Art of Computer Programming, sectin 4.3 */
52
53 /* They say AIX requires this to be the first thing in the file, so
54 I include gauche/config.h before the real "gauche.h" */
55 #include <gauche/config.h>
56 #ifndef __GNUC__
57 # if HAVE_ALLOCA_H
58 # include <alloca.h>
59 # else
60 # ifdef _AIX
61 #pragma alloca
62 # else
63 # ifndef alloca /* predefined by HP cc +Olibcalls */
64 char *alloca ();
65 # endif
66 # endif
67 # endif
68 #else
69 # if HAVE_ALLOCA_H
70 # include <alloca.h>
71 # endif
72 # if HAVE_MALLOC_H
73 /* MinGW helds alloca() in "malloc.h" instead of "alloca.h" */
74 # include <malloc.h>
75 # endif
76 #endif
77
78 #include <stdlib.h>
79 #include <math.h>
80 #include <limits.h>
81 #define LIBGAUCHE_BODY
82 #include "gauche.h"
83 #include "gauche/priv/configP.h"
84 #include "gauche/priv/arith.h"
85 #include "gauche/bits.h"
86 #include "gauche/bits_inline.h"
87 #include "gauche/priv/bignumP.h"
88
89 #undef min
90 #define min(x, y) (((x) < (y))? (x) : (y))
91 #undef max
92 #define max(x, y) (((x) > (y))? (x) : (y))
93
94 static ScmBignum *bignum_rshift(ScmBignum *br, const ScmBignum *bx, int amount);
95 static ScmBignum *bignum_lshift(ScmBignum *br, const ScmBignum *bx, int amount);
96 static int bignum_safe_size_for_add(const ScmBignum *x, const ScmBignum *y);
97 static ScmBignum *bignum_add_int(ScmBignum *br, const ScmBignum *bx, const ScmBignum *by);
98 static ScmBignum *bignum_2scmpl(ScmBignum *br);
99
100 /*---------------------------------------------------------------------
101 * Constructor
102 *
103 * Scm_MakeBignum* always returns bignum, possibly denormalized.
104 */
105 static ScmBignum *bignum_clear(ScmBignum *b)
106 {
107 for (u_int i=0; i<b->size; i++) b->values[i] = 0;
108 return b;
109 }
110
111 #define BIGNUM_SIZE(size) (sizeof(ScmBignum)+((size)-1)*sizeof(long))
112
113 static ScmBignum *make_bignum(int size)
114 {
115 if (size < 0) Scm_Error("invalid bignum size (internal error): %d", size);
116 if (size > (int)SCM_BIGNUM_MAX_DIGITS) Scm_Error("too large bignum");
117 ScmBignum *b = SCM_NEW_ATOMIC2(ScmBignum*, BIGNUM_SIZE(size));
118 SCM_SET_CLASS(b, SCM_CLASS_INTEGER);
119 b->size = size;
120 b->sign = 1;
121 return bignum_clear(b);
122 }
123
124
125 /* Allocate temporary bignum in the current function's stack frame
126 if alloca() is available. */
127 #ifdef HAVE_ALLOCA
128 #define ALLOC_TEMP_BIGNUM(var_, size_) \
129 (var_) = SCM_BIGNUM(alloca(BIGNUM_SIZE(size_))); \
130 SCM_SET_CLASS(var_, SCM_CLASS_INTEGER); \
131 (var_)->size = (size_); \
132 (var_)->sign = 1; \
133 bignum_clear(var_)
134 #else /*!HAVE_ALLOCA*/
135 #define ALLOC_TEMP_BIGNUM(var_, size_) (var_) = make_bignum(size_);
136 #endif /*!HAVE_ALLOCA*/
137
138 ScmObj Scm_MakeBignumFromSI(long val)
139 {
140 ScmBignum *b;
141 if (val == LONG_MIN) {
142 b = make_bignum(1);
143 b->sign = -1;
144 b->values[0] = (unsigned long)LONG_MAX+1;
145 } else if (val < 0) {
146 b = make_bignum(1);
147 b->sign = -1;
148 b->values[0] = -val;
149 } else {
150 b = make_bignum(1);
151 b->sign = 1;
152 b->values[0] = val;
153 }
154 return SCM_OBJ(b);
155 }
156
157 ScmObj Scm_MakeBignumFromUI(u_long val)
158 {
159 ScmBignum *b = make_bignum(1);
160 b->sign = 1;
161 b->values[0] = val;
162 return SCM_OBJ(b);
163 }
164
165 /* If sign > 0 or sign < 0, values[] has absolute value.
166 If sign == 0, values[] has 2's complement signed representation */
167 ScmObj Scm_MakeBignumFromUIArray(int sign, const u_long *values, int size)
168 {
169 ScmBignum *b = make_bignum(size);
170 if (sign != 0) {
171 b->sign = (sign > 0)? 1 : -1;
172 for (int i=0; i<size; i++) b->values[i] = values[i];
173 } else {
174 int nonzerop = FALSE;
175 for (int i=0; i<size; i++) {
176 if ((b->values[i] = values[i]) != 0) nonzerop = TRUE;
177 }
178 if (nonzerop) {
179 if (values[size-1] <= LONG_MAX) b->sign = 1;
180 else { b->sign = -1; bignum_2scmpl(b); }
181 } else {
182 b->sign = 0;
183 }
184 }
185 return SCM_OBJ(b);
186 }
187
188 ScmObj Scm_MakeBignumFromDouble(double val)
189 {
190 if (LONG_MIN <= val
191 #if SIZEOF_LONG == 4
192 && val <= LONG_MAX
193 #else
194 && val <= nextafter((double)LONG_MAX, 0.0)
195 #endif
196 )
197 return Scm_MakeBignumFromSI((long)val);
198
199 int exponent, sign;
200 ScmObj mantissa = Scm_DecodeFlonum(val, &exponent, &sign);
201 if (!SCM_NUMBERP(mantissa)) {
202 Scm_Error("can't convert %lf to an integer", val);
203 }
204 ScmObj b = Scm_Ash(mantissa, exponent);
205 if (sign < 0) b = Scm_Negate(b);
206 /* always returns bignum */
207 if (SCM_INTP(b)) {
208 return Scm_MakeBignumFromSI(SCM_INT_VALUE(b));
209 } else {
210 return b;
211 }
212 }
213
214 ScmObj Scm_BignumCopy(const ScmBignum *b)
215 {
216 ScmBignum *c = make_bignum(b->size);
217 c->sign = b->sign;
218 for (u_int i=0; i<b->size; i++) c->values[i] = b->values[i];
219 return SCM_OBJ(c);
220 }
221
222 /*-----------------------------------------------------------------------
223 * Conversion
224 */
225
226 /* Modifies B and return it. */
227 ScmObj Scm_NormalizeBignum(ScmBignum *b)
228 {
229 int size = b->size;
230 int i;
231 for (i=size-1; i>0; i--) {
232 if (b->values[i] == 0) size--;
233 else break;
234 }
235 if (i==0) {
236 if (b->sign == 0) {
237 return SCM_MAKE_INT(0);
238 }
239 if (b->sign > 0 && b->values[0] <= (u_long)SCM_SMALL_INT_MAX) {
240 return SCM_MAKE_INT(b->values[0]);
241 }
242 if (b->sign < 0 && b->values[0] <= (u_long)-SCM_SMALL_INT_MIN) {
243 return SCM_MAKE_INT(-((signed long)b->values[0]));
244 }
245 }
246 b->size = size;
247 return SCM_OBJ(b);
248 }
249
250 /* b must be normalized. */
251 long Scm_BignumToSI(const ScmBignum *b, int clamp, int *oor)
252 {
253 if (clamp == SCM_CLAMP_NONE && oor != NULL) *oor = FALSE;
254 if (b->sign >= 0) {
255 if (b->values[0] > LONG_MAX || b->size >= 2) {
256 if (clamp & SCM_CLAMP_HI) return LONG_MAX;
257 else goto err;
258 } else {
259 return (long)b->values[0];
260 }
261 } else {
262 if (b->values[0] > (u_long)LONG_MAX+1 || b->size >= 2) {
263 if (clamp & SCM_CLAMP_LO) return LONG_MIN;
264 else goto err;
265 } else {
266 return -(long)b->values[0];
267 }
268 }
269 err:
270 if (clamp == SCM_CLAMP_NONE && oor != NULL) {
271 *oor = TRUE;
272 } else {
273 Scm_Error("argument out of range: %S", SCM_OBJ(b));
274 }
275 return 0;
276 }
277
278 /* b must be normalized. */
279 u_long Scm_BignumToUI(const ScmBignum *b, int clamp, int *oor)
280 {
281 if (clamp == SCM_CLAMP_NONE && oor != NULL) *oor = FALSE;
282 if (b->sign >= 0) {
283 if (b->size >= 2) {
284 if (clamp & SCM_CLAMP_HI) return SCM_ULONG_MAX;
285 else goto err;
286 } else {
287 return b->values[0];
288 }
289 } else {
290 if (clamp & SCM_CLAMP_LO) return 0;
291 else goto err;
292 }
293 err:
294 if (clamp == SCM_CLAMP_NONE && oor != NULL) {
295 *oor = TRUE;
296 } else {
297 Scm_Error("argument out of range: %S", SCM_OBJ(b));
298 }
299 return 0;
300 }
301
302 #if SIZEOF_LONG == 4
303 /* we need special routines for int64 */
304 int64_t Scm_BignumToSI64(const ScmBignum *b, int clamp, int *oor)
305 {
306 int64_t r = 0;
307 if (clamp == SCM_CLAMP_NONE && oor != NULL) *oor = FALSE;
308 if (b->sign > 0) {
309 if (b->size == 1) {
310 r = b->values[0];
311 } else if (b->size > 2 || b->values[1] > LONG_MAX) {
312 if (!(clamp & SCM_CLAMP_HI)) goto err;
313 r = INT64_MAX;
314 } else {
315 r = ((int64_t)b->values[1] << 32) + (uint64_t)b->values[0];
316 }
317 } else { /* b->sign < 0 */
318 if (b->size == 1) {
319 r = -(int64_t)b->values[0];
320 } else if (b->size > 2 || (b->values[1] > LONG_MAX && b->values[0] > 0)) {
321 if (!(clamp&SCM_CLAMP_LO)) goto err;
322 r = INT64_MIN;
323 } else {
324 r = -(int64_t)(((int64_t)b->values[1] << 32) + (uint64_t)b->values[0]);
325 }
326 }
327 return r;
328 err:
329 if (clamp == SCM_CLAMP_NONE && oor != NULL) {
330 *oor = TRUE;
331 } else {
332 Scm_Error("argument out of range: %S", SCM_OBJ(b));
333 }
334 return r;
335 }
336
337 uint64_t Scm_BignumToUI64(const ScmBignum *b, int clamp, int *oor)
338 {
339 uint64_t r = 0;
340 if (clamp == SCM_CLAMP_NONE && oor != NULL) *oor = FALSE;
341 if (b->sign > 0) {
342 if (b->size > 2) {
343 if (!(clamp&SCM_CLAMP_HI)) goto err;
344 r = UINT64_MAX;
345 } else if (b->size == 2) {
346 r = (((uint64_t)b->values[1]) << 32) + (uint64_t)b->values[0];
347 } else {
348 r = (uint64_t)b->values[0];
349 }
350 } else { /* b->sign < 0 */
351 if (!(clamp&SCM_CLAMP_LO)) goto err;
352 }
353 return r;
354 err:
355 if (clamp == SCM_CLAMP_NONE && oor != NULL) {
356 *oor = TRUE;
357 } else {
358 Scm_Error("argument out of range: %S", SCM_OBJ(b));
359 }
360 return r;
361 }
362 #endif /* SIZEOF_LONG == 4 */
363
364 extern double Scm__EncodeDouble(u_long, u_long, int, int);
365
366 /* Converts a bignum b to a double. b must be normalized.
367 We don't rely on double arithmetic, for it may result
368 an error in the LSB from multiple roundings. Instead we
369 extract bits directly from the bignum values array.
370 (We use ScmBits API by casting b->values to ScmBits*).
371 */
372 double Scm_BignumToDouble(const ScmBignum *b)
373 {
374 ScmBits *bits = (ScmBits*)b->values;
375 ScmBits dst[2];
376
377 /* first, filter out a special case. */
378 if (b->size == 0) return 0.0;
379
380 int maxbit = Scm_BitsHighest1(bits, 0, b->size*WORD_BITS);
381 int exponent = maxbit+1023;
382 #if SIZEOF_LONG >= 8
383 SCM_ASSERT(maxbit >= 54); /* because b is normalized */
384 dst[0] = 0;
385 Scm_BitsCopyX(dst, 0, bits, maxbit-52, maxbit);
386 /* Rounding. We have to round up if maxbit-53 == 1, EXCEPT
387 the special case where maxbit-52==0, maxbit-53==1, and all
388 bits below are 0 (round-to-even rule) */
389 if (SCM_BITS_TEST(bits, maxbit-53)
390 && ((dst[0]&1) == 1
391 || (Scm_BitsCount1(bits, 0, maxbit-53) > 0))) {
392 dst[0]++;
393 if (dst[0] >= (1UL<<52)) {
394 /* Overflow. We mask the hidden bit, then shift. */
395 dst[0] &= ~(1UL<<52);
396 dst[0] >>= 1;
397 exponent++;
398 }
399 }
400 if (exponent > 2046) return Scm__EncodeDouble(0, 0, 2047, (b->sign < 0));
401 else return Scm__EncodeDouble(dst[0], 0, exponent, (b->sign < 0));
402 #else /*SIZEOF_LONG == 4 */
403 dst[0] = dst[1] = 0;
404 if (maxbit < 53) {
405 Scm_BitsCopyX(dst, 52-maxbit, bits, 0, maxbit);
406 } else {
407 Scm_BitsCopyX(dst, 0, bits, maxbit-52, maxbit);
408 /* Rounding. See the above comment. */
409 if (SCM_BITS_TEST(bits, maxbit-53)
410 && ((dst[0]&1) == 1
411 || (maxbit > 53 && Scm_BitsCount1(bits, 0, maxbit-53) > 0))) {
412 u_long inc = dst[0] + 1;
413 if (inc < dst[0]) dst[1]++;
414 dst[0] = inc;
415 if (dst[1] >= (1UL<<(52-32))) {
416 /* Overflow. We mask the hidden bit, then shift. */
417 dst[1] &= ~(1UL<<(52-32));
418 dst[0] = (dst[0] >> 1) | ((u_long)(dst[1]&1) << 31);
419 dst[1] >>= 1;
420 exponent++;
421 }
422 }
423 }
424 if (exponent > 2046) return Scm__EncodeDouble(0, 0, 2047, (b->sign < 0));
425 else return Scm__EncodeDouble(dst[0], dst[1], exponent, (b->sign < 0));
426 #endif /*SIZEOF_LONG==4*/
427 }
428
429 /* return -b, normalized */
430 ScmObj Scm_BignumNegate(const ScmBignum *b)
431 {
432 ScmObj c = Scm_BignumCopy(b);
433 SCM_BIGNUM_SIGN(c) = -SCM_BIGNUM_SIGN(c);
434 return Scm_NormalizeBignum(SCM_BIGNUM(c));
435 }
436
437 /*-----------------------------------------------------------------------
438 * Compare
439 */
440
441 /* bx and by must be normalized */
442 int Scm_BignumCmp(const ScmBignum *bx, const ScmBignum *by)
443 {
444 if (bx->sign < by->sign) return -1;
445 if (bx->sign > by->sign) return 1;
446 if (bx->size < by->size) return (bx->sign > 0) ? -1 : 1;
447 if (bx->size > by->size) return (bx->sign > 0) ? 1 : -1;
448
449 for (int i=(int)bx->size-1; i>=0; i--) {
450 if (bx->values[i] < by->values[i]) return (bx->sign > 0) ? -1 : 1;
451 if (bx->values[i] > by->values[i]) return (bx->sign > 0) ? 1 : -1;
452 }
453 return 0;
454 }
455
456 /* compare absolute values. assume bx and by are nomalized. */
457 int Scm_BignumAbsCmp(const ScmBignum *bx, const ScmBignum *by)
458 {
459 if (bx->size < by->size) return -1;
460 if (bx->size > by->size) return 1;
461 for (int i=(int)bx->size-1; i>=0; i--) {
462 if (bx->values[i] < by->values[i]) return -1;
463 if (bx->values[i] > by->values[i]) return 1;
464 }
465 return 0;
466 }
467
468 /* Compare bx + off and by. All arguments must be positive. bx and by
469 must be normalized. off may be denormalized if it is created directly
470 by Scm_MakeBignumFromUI call.
471 Expect bx >> off for most cases.
472 Screen out the obvious case without actually calculating bx+off.
473 Experimentary, the following set of conditions avoid 93% of cases from
474 doing actual bignum addition. */
475 int Scm_BignumCmp3U(const ScmBignum *bx,
476 const ScmBignum *off,
477 const ScmBignum *by)
478 {
479 u_int xsize = SCM_BIGNUM_SIZE(bx), ysize = SCM_BIGNUM_SIZE(by);
480 u_int osize = SCM_BIGNUM_SIZE(off);
481
482 if (xsize > ysize) return 1;
483 if (xsize < ysize) {
484 if (osize < ysize && by->values[ysize-1] > 1) {
485 return -1;
486 }
487 if (osize == ysize) {
488 if (off->values[osize-1] > by->values[ysize-1]) return 1;
489 if (off->values[osize-1] < by->values[ysize-1]-1) return -1;
490 }
491 /* fallthrough */
492 } else {
493 /* xsize == ysize */
494 u_long w, c = 0;
495 if (osize > ysize) return 1;
496 if (bx->values[xsize-1] > by->values[ysize-1]) return 1;
497 if (osize < xsize) {
498 if (bx->values[xsize-1] < by->values[ysize-1]-1) return -1;
499 } else {
500 /* osize == xsize */
501 u_long xx = bx->values[xsize-1], oo = off->values[osize-1];
502 UADD(w, c, xx, oo);
503 if (c > 0 || w > by->values[ysize-1]) return 1;
504 if (w < by->values[ysize-1] - 1) return -1;
505 }
506 /* fallthrough */
507 }
508 u_int tsize = bignum_safe_size_for_add(bx, off);
509 ScmBignum *br;
510 ALLOC_TEMP_BIGNUM(br, tsize);
511 bignum_add_int(br, bx, off);
512
513 if (br->size < by->size) return -1;
514 for (int i=(int)br->size-1; i>=0; i--) {
515 if (i >= (int)by->size) {
516 if (br->values[i]) return 1;
517 continue;
518 }
519 if (br->values[i] < by->values[i]) return -1;
520 if (br->values[i] > by->values[i]) return 1;
521 }
522 return 0;
523 }
524
525 /*-----------------------------------------------------------------------
526 * Add & subtract
527 */
528 static int bignum_safe_size_for_add(const ScmBignum *x, const ScmBignum *y)
529 {
530 int xsize = SCM_BIGNUM_SIZE(x);
531 int ysize = SCM_BIGNUM_SIZE(y);
532 if (xsize > ysize) {
533 if (x->values[xsize-1] == SCM_ULONG_MAX) return xsize+1;
534 else return xsize;
535 } else if (ysize > xsize) {
536 if (y->values[ysize-1] == SCM_ULONG_MAX) return ysize+1;
537 else return ysize;
538 } else {
539 return xsize+1;
540 }
541 }
542
543 /* take 2's complement */
544 static ScmBignum *bignum_2scmpl(ScmBignum *br)
545 {
546 int rsize = SCM_BIGNUM_SIZE(br);
547 u_long c = 1;
548 for (int i=0; i<rsize; i++) {
549 unsigned long x = ~br->values[i];
550 UADD(br->values[i], c, x, 0);
551 }
552 return br;
553 }
554
555 ScmObj Scm_BignumComplement(const ScmBignum *bx)
556 {
557 ScmBignum *r = SCM_BIGNUM(Scm_BignumCopy(bx));
558 return SCM_OBJ(bignum_2scmpl(r));
559 }
560
561 /* br = abs(bx) + abs(by), assuming br has enough size. br and bx can be
562 the same object. */
563 static ScmBignum *bignum_add_int(ScmBignum *br,
564 const ScmBignum *bx, const ScmBignum *by)
565 {
566 int rsize = SCM_BIGNUM_SIZE(br);
567 int xsize = SCM_BIGNUM_SIZE(bx);
568 int ysize = SCM_BIGNUM_SIZE(by);
569 u_long c = 0;
570
571 for (int i=0; i<rsize; i++, xsize--, ysize--) {
572 if (xsize <= 0) {
573 if (ysize <= 0) {
574 UADD(br->values[i], c, 0, 0);
575 continue;
576 }
577 u_long y = by->values[i];
578 UADD(br->values[i], c, 0, y);
579 continue;
580 }
581 if (ysize <= 0) {
582 u_long x = bx->values[i];
583 UADD(br->values[i], c, x, 0);
584 continue;
585 }
586 u_long x = bx->values[i];
587 u_long y = by->values[i];
588 UADD(br->values[i], c, x, y);
589 }
590 return br;
591 }
592
593 /* br = abs(bx) - abs(by), assuming br has enough size. br and bx can be
594 the same object. */
595 static ScmBignum *bignum_sub_int(ScmBignum *br,
596 const ScmBignum *bx, const ScmBignum *by)
597 {
598 int rsize = SCM_BIGNUM_SIZE(br);
599 int xsize = SCM_BIGNUM_SIZE(bx);
600 int ysize = SCM_BIGNUM_SIZE(by);
601 u_long c = 0;
602
603 for (int i=0; i<rsize; i++, xsize--, ysize--) {
604 if (xsize <= 0) {
605 if (ysize <= 0) {
606 USUB(br->values[i], c, 0, 0);
607 continue;
608 }
609 u_long y = by->values[i];
610 USUB(br->values[i], c, 0, y);
611 continue;
612 }
613 if (ysize <= 0) {
614 u_long x = bx->values[i];
615 USUB(br->values[i], c, x, 0);
616 continue;
617 }
618 u_long x = bx->values[i];
619 u_long y = by->values[i];
620 USUB(br->values[i], c, x, y);
621 }
622 if (c != 0) {
623 bignum_2scmpl(br);
624 br->sign = 0 - br->sign; /* flip sign */
625 }
626 return br;
627 }
628
629 /* returns bx + by, not normalized */
630 static ScmBignum *bignum_add(const ScmBignum *bx, const ScmBignum *by)
631 {
632 int rsize = bignum_safe_size_for_add(bx, by);
633 ScmBignum *br = make_bignum(rsize);
634 br->sign = SCM_BIGNUM_SIGN(bx);
635 if (SCM_BIGNUM_SIGN(bx) == SCM_BIGNUM_SIGN(by)) {
636 bignum_add_int(br, bx, by);
637 } else {
638 bignum_sub_int(br, bx, by);
639 }
640 return br;
641 }
642
643 /* returns bx - by, not normalized */
644 static ScmBignum *bignum_sub(const ScmBignum *bx, const ScmBignum *by)
645 {
646 int rsize = bignum_safe_size_for_add(bx, by);
647 ScmBignum *br = make_bignum(rsize);
648 br->sign = SCM_BIGNUM_SIGN(bx);
649 if (SCM_BIGNUM_SIGN(bx) == SCM_BIGNUM_SIGN(by)) {
650 bignum_sub_int(br, bx, by);
651 } else {
652 bignum_add_int(br, bx, by);
653 }
654 return br;
655 }
656
657 /* returns bx + y, not nomalized */
658 static ScmBignum *bignum_add_si(const ScmBignum *bx, long y)
659 {
660 long c = 0;
661 u_int rsize = bx->size+1;
662 u_long yabs = ((y < 0)? -y : y);
663 int ysign = ((y < 0)? -1 : 1);
664 ScmBignum *br = make_bignum(rsize);
665 br->sign = bx->sign;
666 if (SCM_BIGNUM_SIGN(bx) == ysign) {
667 for (u_int i=0; i<bx->size; i++) {
668 UADD(br->values[i], c, bx->values[i], yabs);
669 yabs = 0;
670 }
671 } else {
672 for (u_int i=0; i<bx->size; i++) {
673 USUB(br->values[i], c, bx->values[i], yabs);
674 yabs = 0;
675 }
676 }
677 br->values[rsize-1] = c;
678 return br;
679 }
680
681 ScmObj Scm_BignumAdd(const ScmBignum *bx, const ScmBignum *by)
682 {
683 return Scm_NormalizeBignum(bignum_add(bx, by));
684 }
685
686 ScmObj Scm_BignumSub(const ScmBignum *bx, const ScmBignum *by)
687 {
688 return Scm_NormalizeBignum(bignum_sub(bx, by));
689 }
690
691 ScmObj Scm_BignumAddSI(const ScmBignum *bx, long y)
692 {
693 if (y == 0) return SCM_OBJ(bx);
694 else return Scm_NormalizeBignum(bignum_add_si(bx, y));
695 }
696
697 ScmObj Scm_BignumSubSI(const ScmBignum *bx, long y)
698 {
699 if (y == 0) return SCM_OBJ(bx);
700 else return Scm_NormalizeBignum(bignum_add_si(bx, -y));
701 }
702
703 /*-----------------------------------------------------------------------
704 * Shifter
705 */
706
707 /* br = bx >> amount. amount >= 0. no normalization. assumes br
708 has enough size to hold the result. br and bx can be the same object. */
709 static ScmBignum *bignum_rshift(ScmBignum *br, const ScmBignum *bx, int amount)
710 {
711 u_int nwords = amount / WORD_BITS;
712 u_int nbits = amount % WORD_BITS;
713 int i;
714
715 if (bx->size <= nwords) {
716 br->size = 0; br->values[0] = 0;
717 } else if (nbits == 0) {
718 for (i = (int)nwords; i < (int)bx->size; i++) {
719 br->values[i-nwords] = bx->values[i];
720 }
721 br->size = bx->size - nwords;
722 br->sign = bx->sign;
723 } else {
724 u_long x;
725 for (i = (int)nwords; i < (int)bx->size-1; i++) {
726 x = (bx->values[i+1]<<(WORD_BITS-nbits))|(bx->values[i]>>nbits);
727 br->values[i-nwords] = x;
728 }
729 br->values[i-nwords] = bx->values[i]>>nbits;
730 br->size = bx->size - nwords;
731 br->sign = bx->sign;
732 }
733 return br;
734 }
735
736 /* br = bx << amount, amount > 0. no normalization. assumes br
737 has enough size. br and bx can be the same object. */
738 static ScmBignum *bignum_lshift(ScmBignum *br, const ScmBignum *bx, int amount)
739 {
740 int nwords = amount / WORD_BITS;
741 int nbits = amount % WORD_BITS;
742
743 if (nbits == 0) {
744 /* short path */
745 for (int i = (int)bx->size-1; i>=0; i--) {
746 if ((int)br->size > i+nwords) br->values[i+nwords] = bx->values[i];
747 }
748 for (int i = nwords-1; i>=0; i--) br->values[i] = 0;
749 } else {
750 if (br->size > bx->size + nwords) {
751 br->values[bx->size+nwords] =
752 bx->values[bx->size-1]>>(WORD_BITS-nbits);
753 }
754 int i;
755 for (i = (int)bx->size-1; i > 0; i--) {
756 u_long x = (bx->values[i]<<nbits)|(bx->values[i-1]>>(WORD_BITS-nbits));
757 if ((int)br->size > i+nwords) br->values[i+nwords] = x;
758 }
759 br->values[nwords] = bx->values[0]<<nbits;
760 for (i = nwords-1; i>=0; i--) br->values[i] = 0;
761 }
762 if (br != bx) {
763 br->sign = bx->sign;
764 }
765 return br;
766 }
767
768 /*-----------------------------------------------------------------------
769 * Multiplication
770 */
771
772 /* br += bx * (y << off*WORD_BITS). br must have enough size. */
773 static ScmBignum *bignum_mul_word(ScmBignum *br, const ScmBignum *bx,
774 u_long y, int off)
775 {
776 for (int i=0; i<bx->size; i++) {
777 u_long hi, lo, r1;
778 u_long x = bx->values[i];
779 UMUL(hi, lo, x, y);
780
781 u_long c = 0;
782 u_long r0 = br->values[i+off];
783 UADD(r1, c, r0, lo);
784 br->values[i+off] = r1;
785
786 r0 = br->values[i+off+1];
787 UADD(r1, c, r0, hi);
788 br->values[i+off+1] = r1;
789
790 for (int j=i+off+2; c && j<br->size; j++) {
791 r0 = br->values[j];
792 UADD(r1, c, r0, 0);
793 br->values[j] = r1;
794 }
795 }
796 return br;
797 }
798
799 /* returns bx * by. not normalized */
800 static ScmBignum *bignum_mul(const ScmBignum *bx, const ScmBignum *by)
801 {
802 ScmBignum *br = make_bignum(bx->size + by->size);
803 for (u_int i=0; i<by->size; i++) {
804 bignum_mul_word(br, bx, by->values[i], i);
805 }
806 br->sign = bx->sign * by->sign;
807 return br;
808 }
809
810 /* return bx * y, y != 0 and y != 1 */
811 static ScmBignum *bignum_mul_si(const ScmBignum *bx, long y)
812 {
813 if (y == -1) {
814 ScmBignum *br = SCM_BIGNUM(Scm_BignumCopy(bx));
815 br->sign = -br->sign;
816 return br;
817 }
818 ScmBignum *br;
819 br = make_bignum(bx->size + 1); /* TODO: more accurate estimation */
820 if (y & (y-1)) {
821 /* general case */
822 u_long yabs = (y<0)? -y:y;
823 br->sign = bx->sign;
824 bignum_mul_word(br, bx, yabs, 0);
825 if (y<0) br->sign = -br->sign;
826 } else {
827 /* fast path when y is a power of two (note that y != 0). */
828 int n = Scm__LowestBitNumber((u_long)y);
829 bignum_lshift(br, bx, n);
830 }
831 return br;
832 }
833
834 ScmObj Scm_BignumMul(const ScmBignum *bx, const ScmBignum *by)
835 {
836 ScmBignum *br = bignum_mul(bx, by);
837 return Scm_NormalizeBignum(br);
838 }
839
840 ScmObj Scm_BignumMulSI(const ScmBignum *bx, long y)
841 {
842 if (y == 1) return SCM_OBJ(bx);
843 else if (y == 0) return SCM_MAKE_INT(0);
844 else return Scm_NormalizeBignum(bignum_mul_si(bx, y));
845 }
846
847 /*-----------------------------------------------------------------------
848 * Division
849 */
850
851 /* returns # of bits in the leftmost '1' in the word, counting from MSB. */
852 static inline int div_normalization_factor(u_long w)
853 {
854 u_long b = (1L<<(WORD_BITS-1)), c = 0;
855 for (; b > 0; b>>=1, c++) {
856 if (w & b) return c;
857 }
858 /* something got wrong here */
859 Scm_Panic("bignum.c: div_normalization_factor: can't be here");
860 return 0; /* dummy */
861 }
862
863 /* General case of division. We use each half word as a digit.
864 Assumes digitsof(dividend) >= digitsof(divisor) > 1.
865 Assumes enough digits are allocated to quotient.
866 Remainder is returned (not normalized) */
867 static ScmBignum *bignum_gdiv(const ScmBignum *dividend,
868 const ScmBignum *divisor,
869 ScmBignum *quotient)
870 {
871 int d = div_normalization_factor(divisor->values[divisor->size-1]);
872 int n, m;
873 u_long vv, uj, uj2, cy;
874
875 #define DIGIT(num, n) (((n)%2)? HI((num)->values[(n)/2]) : LO((num)->values[(n)/2]))
876 #define DIGIT2(num, n) \
877 (((n)%2)? \
878 ((LO((num)->values[(n)/2+1])<<HALF_BITS)|HI((num)->values[(n)/2])): \
879 (num)->values[(n)/2])
880 #define SETDIGIT(num, n, v) \
881 (((n)%2)? \
882 (num->values[(n)/2] = (num->values[(n)/2] & LOMASK)|((v) << HALF_BITS)) :\
883 (num->values[(n)/2] = (num->values[(n)/2] & HIMASK)|((v) & LOMASK)))
884 #define SETDIGIT2(num, n, v) \
885 (((n)%2)? \
886 ((num->values[(n)/2] = LO(num->values[(n)/2])|((v)<<HALF_BITS)), \
887 (num->values[(n)/2+1] = (num->values[(n)/2+1] & HIMASK)|HI(v))) : \
888 (num->values[(n)/2] = (v)))
889
890 /* normalize */
891 ScmBignum *u, *v;
892 u = make_bignum(dividend->size + 1); /* will be returned as a remainder */
893 ALLOC_TEMP_BIGNUM(v, divisor->size);
894 if (d >= HALF_BITS) {
895 d -= HALF_BITS;
896 n = divisor->size*2 - 1;
897 m = dividend->size*2 - n;
898 } else {
899 n = divisor->size*2;
900 m = dividend->size*2 - n;
901 }
902 bignum_lshift(u, dividend, d);
903 bignum_lshift(v, divisor, d);
904 u_long vn_1 = DIGIT(v, n-1);
905 u_long vn_2 = DIGIT(v, n-2);
906 #undef DIV_DEBUG
907 #ifdef DIV_DEBUG
908 Scm_Printf(SCM_CUROUT, "shift=%d, n=%d, m=%d\n", d, n, m);
909 Scm_Printf(SCM_CUROUT, "u="); Scm_BignumDump(u, SCM_CUROUT);
910 Scm_Printf(SCM_CUROUT, "\nv="); Scm_BignumDump(v, SCM_CUROUT);
911 Scm_Printf(SCM_CUROUT, "\nvn_1=%08lx, vn_2=%08lx\n", vn_1, vn_2);
912 #endif
913
914 for (int j = m; j >= 0; j--) {
915 u_long uu = (DIGIT(u, j+n) << HALF_BITS) + DIGIT(u, j+n-1);
916 u_long qq = uu/vn_1;
917 u_long rr = uu%vn_1;
918 #ifdef DIV_DEBUG
919 Scm_Printf(SCM_CUROUT, "loop on j=%d, uu=%08lx, qq=%08lx, rr=%08lx\n",
920 j, uu, qq, rr);
921 #endif
922 while (qq >= HALF_WORD) { qq--; rr += vn_1; }
923 while ((qq*vn_2 > (rr<<HALF_BITS)+DIGIT(u, j+n-2)) && (rr < HALF_WORD)) {
924 qq--; rr += vn_1;
925 }
926 #ifdef DIV_DEBUG
927 Scm_Printf(SCM_CUROUT, "estimate uu=%08lx, qq=%08lx, rr=%08lx\n",
928 uu, qq, rr);
929 #endif
930 cy = 0;
931 for (int k = 0; k < n; k++) {
932 vv = qq * DIGIT(v, k);
933 uj = DIGIT2(u, j+k);
934 uj2 = uj - vv - cy;
935 cy = (uj2 > uj)? HALF_WORD : 0;
936 SETDIGIT2(u, j+k, uj2);
937 }
938 #ifdef DIV_DEBUG
939 Scm_Printf(SCM_CUROUT, "subtract cy = %d, ", cy);
940 Scm_Printf(SCM_CUROUT, "u="); Scm_BignumDump(u, SCM_CUROUT);
941 Scm_Printf(SCM_CUROUT, "\n");
942 #endif
943 if (cy) {
944 qq--;
945 cy = 0;
946 for (int k = 0; k < n; k++) {
947 vv = DIGIT(v, k);
948 uj = DIGIT(u, j+k) + vv + cy;
949 cy = (uj >= HALF_WORD)? 1 : 0;
950 SETDIGIT(u, j+k, uj);
951 }
952 uj = DIGIT(u, j+n) + cy;
953 SETDIGIT(u, j+n, uj);
954 }
955 SETDIGIT(quotient, j, qq);
956 }
957 bignum_rshift(u, u, d);
958 #ifdef DIV_DEBUG
959 Scm_Printf(SCM_CUROUT, "quot q="); Scm_BignumDump(quotient, SCM_CUROUT);
960 Scm_Printf(SCM_CUROUT, "\nrem u="); Scm_BignumDump(u, SCM_CUROUT);
961 Scm_Printf(SCM_CUROUT, "\n");
962 #endif
963 return u;
964 }
965
966 /* Fast path if divisor fits in a half word. Quotient remains in the
967 dividend's memory. Remainder returned. Quotient not normalized. */
968 static u_long bignum_sdiv(ScmBignum *dividend, u_long divisor)
969 {
970 int n = dividend->size - 1;
971 u_long *pu = dividend->values;
972 u_long q0 = 0, r0 = 0, q1, r1;
973
974 for (; n > 0; n--) {
975 q1 = pu[n] / divisor + q0;
976 r1 = ((pu[n] % divisor) << HALF_BITS) + HI(pu[n-1]);
977 q0 = ((r1 / divisor) << HALF_BITS);
978 r0 = r1 % divisor;
979 pu[n] = q1;
980 pu[n-1] = (r0 << HALF_BITS) + LO(pu[n-1]);
981 }
982 q1 = pu[0] / divisor + q0;
983 r1 = pu[0] % divisor;
984 pu[0] = q1;
985 return r1;
986 }
987
988 /* assuming dividend is normalized. */
989 ScmObj Scm_BignumDivSI(const ScmBignum *dividend, long divisor, long *remainder)
990 {
991 u_long dd = (divisor < 0)? -divisor : divisor;
992 u_long rr;
993 int d_sign = (divisor < 0)? -1 : 1;
994 ScmBignum *q;
995
996 if (dd < HALF_WORD) {
997 q = SCM_BIGNUM(Scm_BignumCopy(dividend));
998 rr = bignum_sdiv(q, dd);
999 } else {
1000 ScmBignum *bv = SCM_BIGNUM(Scm_MakeBignumFromSI(dd));
1001 ScmBignum *br;
1002 q = make_bignum(dividend->size + 1);
1003 br = bignum_gdiv(dividend, bv, q);
1004 rr = br->values[0];
1005 }
1006 if (remainder) {
1007 *remainder = ((dividend->sign < 0)? -(signed long)rr : (signed long)rr);
1008 }
1009 q->sign = dividend->sign * d_sign;
1010 return Scm_NormalizeBignum(q);
1011 }
1012
1013 /* If we only need rem(bignum, fixnum), we don't need to copy bignum
1014 to keep quotient. */
1015 long Scm_BignumRemSI(const ScmBignum *dividend, long divisor)
1016 {
1017 #if (SIZEOF_LONG == 4) && HAVE_UINT64_T
1018 /* ILP32 with 64bit integer - easy one. */
1019 uint64_t dd = (divisor < 0)? -divisor : divisor;
1020 int sign = SCM_BIGNUM_SIGN(dividend);
1021 int k = SCM_BIGNUM_SIZE(dividend) - 1;
1022 uint64_t m = 0;
1023 for (;k >= 0; k--) {
1024 uint64_t x = (uint64_t)dividend->values[k] + (m << WORD_BITS);
1025 m = x % dd;
1026 }
1027 return (long)m * sign;
1028 #else /* SIZEOF_LONG >= 4 || !HAVE_UINT64_T*/
1029 /* Here we need double-machine-word `rem` machine-word. */
1030 u_long dd = (divisor < 0)? -divisor : divisor;
1031 int sign = SCM_BIGNUM_SIGN(dividend);
1032 int k = SCM_BIGNUM_SIZE(dividend) - 1;
1033 int shift = WORD_BITS - Scm__HighestBitNumber(dd) - 1;
1034 u_long m = 0;
1035 for (;k >= 0; k--) {
1036 u_long x = dividend->values[k];
1037 int total_shift = 0;
1038 /* we calculate [m;x] modulo dd. since always m < dd it's safe to
1039 shift m first. */
1040 while (total_shift < WORD_BITS) {
1041 int s = ((total_shift + shift < WORD_BITS)?
1042 shift : WORD_BITS-total_shift);
1043 m = (m << s) | (x >> (WORD_BITS - s));
1044 x <<= s;
1045 m %= dd;
1046 total_shift += s;
1047 }
1048 }
1049 return (long)m * sign;
1050 #endif
1051 }
1052
1053 /* assuming dividend and divisor is normalized. returns quotient and
1054 remainder */
1055 ScmObj Scm_BignumDivRem(const ScmBignum *dividend, const ScmBignum *divisor)
1056 {
1057 /* special case */
1058 if (Scm_BignumAbsCmp(dividend, divisor) < 0) {
1059 return Scm_Cons(SCM_MAKE_INT(0), SCM_OBJ(dividend));
1060 }
1061
1062 ScmBignum *q = make_bignum(dividend->size - divisor->size + 1);
1063 ScmBignum *r = bignum_gdiv(dividend, divisor, q);
1064 q->sign = dividend->sign * divisor->sign;
1065 r->sign = dividend->sign;
1066
1067 return Scm_Cons(Scm_NormalizeBignum(q), Scm_NormalizeBignum(r));
1068 }
1069
1070 /*-----------------------------------------------------------------------
1071 * Logical (bitwise) operations
1072 */
1073
1074 ScmObj Scm_BignumAsh(const ScmBignum *x, int cnt)
1075 {
1076 if (cnt == 0) return SCM_OBJ(x);
1077 if (cnt > 0) {
1078 int rsize = SCM_BIGNUM_SIZE(x) + (cnt+WORD_BITS-1)/WORD_BITS;
1079 ScmBignum *r = make_bignum(rsize);
1080 return Scm_NormalizeBignum(bignum_lshift(r, x, cnt));
1081 } else {
1082 int rsize = SCM_BIGNUM_SIZE(x) + cnt/WORD_BITS;
1083 if (rsize < 1) {
1084 if (SCM_BIGNUM_SIGN(x) < 0) {
1085 return SCM_MAKE_INT(-1);
1086 } else {
1087 return SCM_MAKE_INT(0);
1088 }
1089 } else {
1090 if (SCM_BIGNUM_SIGN(x) < 0) {
1091 /* painful way */
1092 ScmObj r = Scm_Quotient(Scm_Add(SCM_OBJ(x), SCM_MAKE_INT(1)),
1093 Scm_Ash(SCM_MAKE_INT(1), -cnt),
1094 NULL);
1095 return Scm_Add(r, SCM_MAKE_INT(-1));
1096 } else {
1097 ScmBignum *r = make_bignum(rsize);
1098 return Scm_NormalizeBignum(bignum_rshift(r, x, -cnt));
1099 }
1100 }
1101 }
1102 }
1103
1104 /* internal routine for logand. z = x & y. assumes z has enough size.
1105 * assumes x and y are in 2's complement form (sign is ignored).
1106 */
1107 static ScmBignum *bignum_and(ScmBignum *z,
1108 const ScmBignum *x, const ScmBignum *y,
1109 int commsize, int xsize, int ysize)
1110 {
1111 int i;
1112 for (i = 0; i < commsize; i++) {
1113 z->values[i] = x->values[i] & y->values[i];
1114 }
1115 if (i < xsize) {
1116 for (; i < xsize; i++) z->values[i] = x->values[i];
1117 } else if (i < ysize) {
1118 for (; i < ysize; i++) z->values[i] = y->values[i];
1119 }
1120 return z;
1121 }
1122
1123 ScmObj Scm_BignumLogAnd(const ScmBignum *x, const ScmBignum *y)
1124 {
1125 int xsize = SCM_BIGNUM_SIZE(x), xsign = SCM_BIGNUM_SIGN(x);
1126 int ysize = SCM_BIGNUM_SIZE(y), ysign = SCM_BIGNUM_SIGN(y);
1127 int zsize, minsize = min(xsize, ysize);
1128
1129 if (xsign > 0) {
1130 if (ysign > 0) {
1131 ScmBignum *z = bignum_and(make_bignum(minsize), x, y, minsize,
1132 0, 0);
1133 return Scm_NormalizeBignum(z);
1134 } else {
1135 ScmBignum *yy = SCM_BIGNUM(Scm_BignumComplement(y));
1136 ScmBignum *z = bignum_and(make_bignum(xsize), x, yy, minsize,
1137 xsize, 0);
1138 return Scm_NormalizeBignum(z);
1139 }
1140 } else {
1141 if (ysign > 0) {
1142 ScmBignum *xx = SCM_BIGNUM(Scm_BignumComplement(x));
1143 ScmBignum *z = bignum_and(make_bignum(ysize), xx, y, minsize,
1144 0, ysize);
1145 return Scm_NormalizeBignum(z);
1146 } else {
1147 ScmBignum *xx = SCM_BIGNUM(Scm_BignumComplement(x));
1148 ScmBignum *yy = SCM_BIGNUM(Scm_BignumComplement(y));
1149 zsize = max(xsize, ysize);
1150 ScmBignum *z = bignum_and(make_bignum(zsize), xx, yy, minsize,
1151 xsize, ysize);
1152 SCM_BIGNUM_SIGN(z) = -1;
1153 bignum_2scmpl(z);
1154 return Scm_NormalizeBignum(z);
1155 }
1156 }
1157 }
1158
1159 /* internal routine for logior. z = x | y. assumes z has enough size.
1160 * assumes x and y are in 2's complement form (sign is ignored).
1161 */
1162 static ScmBignum *bignum_ior(ScmBignum *z,
1163 const ScmBignum *x, const ScmBignum *y,
1164 int commsize, int xsize, int ysize)
1165 {
1166 int i;
1167 for (i = 0; i < commsize; i++) {
1168 z->values[i] = x->values[i] | y->values[i];
1169 }
1170 if (i < xsize) {
1171 for (; i < xsize; i++) z->values[i] = x->values[i];
1172 } else if (i < ysize) {
1173 for (; i < ysize; i++) z->values[i] = y->values[i];
1174 }
1175 return z;
1176 }
1177
1178 ScmObj Scm_BignumLogIor(const ScmBignum *x, const ScmBignum *y)
1179 {
1180 int xsize = SCM_BIGNUM_SIZE(x), xsign = SCM_BIGNUM_SIGN(x);
1181 int ysize = SCM_BIGNUM_SIZE(y), ysign = SCM_BIGNUM_SIGN(y);
1182 int minsize = min(xsize, ysize);
1183
1184 if (xsign >= 0) {
1185 if (ysign >= 0) {
1186 int zsize = max(xsize, ysize);
1187 ScmBignum *z = bignum_ior(make_bignum(zsize), x, y, minsize,
1188 xsize, ysize);
1189 return Scm_NormalizeBignum(z);
1190 } else {
1191 ScmBignum *yy = SCM_BIGNUM(Scm_BignumComplement(y));
1192 ScmBignum *z = bignum_ior(make_bignum(ysize), x, yy, minsize,
1193 0, ysize);
1194 SCM_BIGNUM_SIGN(z) = -1;
1195 bignum_2scmpl(z);
1196 return Scm_NormalizeBignum(z);
1197 }
1198 } else {
1199 if (ysign >= 0) {
1200 ScmBignum *xx = SCM_BIGNUM(Scm_BignumComplement(x));
1201 ScmBignum *z = bignum_ior(make_bignum(xsize), xx, y, minsize,
1202 xsize, 0);
1203 SCM_BIGNUM_SIGN(z) = -1;
1204 bignum_2scmpl(z);
1205 return Scm_NormalizeBignum(z);
1206 } else {
1207 ScmBignum *xx = SCM_BIGNUM(Scm_BignumComplement(x));
1208 ScmBignum *yy = SCM_BIGNUM(Scm_BignumComplement(y));
1209 ScmBignum *z = bignum_ior(make_bignum(minsize), xx, yy, minsize,
1210 0, 0);
1211 SCM_BIGNUM_SIGN(z) = -1;
1212 bignum_2scmpl(z);
1213 return Scm_NormalizeBignum(z);
1214 }
1215 }
1216 }
1217
1218 ScmObj Scm_BignumLogXor(const ScmBignum *x, const ScmBignum *y)
1219 {
1220 /* TODO: more efficient implementation */
1221 ScmObj xandy = Scm_BignumLogAnd(x, y);
1222 ScmObj xory = Scm_BignumLogIor(x, y);
1223 return Scm_LogAnd(xory, Scm_LogNot(xandy));
1224 }
1225
1226 int Scm_BignumLogCount(const ScmBignum *b)
1227 {
1228 const ScmBignum *z = (SCM_BIGNUM_SIGN(b)>0)? b : SCM_BIGNUM(Scm_BignumComplement(b));
1229 int size = SCM_BIGNUM_SIZE(z) * SCM_WORD_BITS;
1230
1231 ScmBits *bits = (ScmBits*)z->values;
1232 if (b->sign > 0) {
1233 return Scm_BitsCount1(bits, 0, size);
1234 } else {
1235 return Scm_BitsCount0(bits, 0, size);
1236 }
1237 }
1238
1239
1240 /*-----------------------------------------------------------------------
1241 * Printing
1242 */
1243
1244 ScmObj Scm_BignumToString(const ScmBignum *b, int radix, int use_upper)
1245 {
1246 static const char ltab[] = "0123456789abcdefghijklmnopqrstuvwxyz";
1247 static const char utab[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
1248 const char *tab = use_upper? utab : ltab;
1249 ScmObj h = SCM_NIL, t = SCM_NIL;
1250 if (radix < SCM_RADIX_MIN || radix > SCM_RADIX_MAX)
1251 Scm_Error("radix out of range: %d", radix);
1252 ScmBignum *q = SCM_BIGNUM(Scm_BignumCopy(b));
1253 for (;q->size > 0;) {
1254 long rem = bignum_sdiv(q, radix);
1255 SCM_ASSERT(rem >= 0 && rem < radix);
1256 SCM_APPEND1(h, t, SCM_MAKE_CHAR(tab[rem]));
1257 for (; q->values[q->size-1] == 0 && q->size > 0; q->size--)
1258 ;
1259 }
1260 if (q->sign < 0) SCM_APPEND1(h, t, SCM_MAKE_CHAR('-'));
1261 return Scm_ListToString(Scm_ReverseX(h));
1262 }
1263
1264 void Scm_BignumDump(const ScmBignum *b, ScmPort *out)
1265 {
1266 Scm_Printf(out, "#<bignum ");
1267 if (b->sign < 0) SCM_PUTC('-', out);
1268 for (int i=(int)b->size-1; i>=0; i--) {
1269 Scm_Printf(out, "%08lx ", b->values[i]);
1270 }
1271 SCM_PUTC('>', out);
1272 }
1273
1274 /*-----------------------------------------------------------------------
1275 * Denormalized bignum API
1276 * These are provided for optimization of specific cases.
1277 */
1278
1279 /* Returns a bignum of specified size, initializing the least significant
1280 word by init. */
1281 ScmBignum *Scm_MakeBignumWithSize(int size, u_long init)
1282 {
1283 ScmBignum *b = make_bignum(size);
1284 b->values[0] = init;
1285 return b;
1286 }
1287
1288 /* Calculate acc * coef + c and store the result to acc, if the result fits
1289 in acc. If acc's size is not enough, allocate new bignum, which is at
1290 least sizeincr words bigger than acc.
1291 Returns the bignum that has the result, without normalizing.
1292 Acc need not be normalized. */
1293 ScmBignum *Scm_BignumAccMultAddUI(ScmBignum *acc, u_long coef, u_long c)
1294 {
1295 ScmBignum *r;
1296 u_int rsize = acc->size + 1;
1297 ALLOC_TEMP_BIGNUM(r, rsize);
1298 r->values[0] = c;
1299 bignum_mul_word(r, acc, coef, 0);
1300 if (r->values[rsize-1] == 0) {
1301 for (u_int i=0; i<acc->size; i++) {
1302 acc->values[i] = r->values[i];
1303 }
1304 return acc;
1305 } else {
1306 ScmBignum *rr;
1307 rr = make_bignum(rsize + 3); /* 3 is arbitrary size increment */
1308 rr->sign = acc->sign;
1309 for (u_int i=0; i<rsize; i++) {
1310 rr->values[i] = r->values[i];
1311 }
1312 return rr;
1313 }
1314 }