| 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 |
} |