Ruby 1.9.2p136(2010-12-25revision30365)

- Main Page
- Modules
- Data Structures
- Files

- File List
- Globals

# bignum.c

Go to the documentation of this file.

    00001 /**********************************************************************
    00002
    00003   bignum.c -
    00004
    00005   $Author: mame $
    00006   created at: Fri Jun 10 00:48:55 JST 1994
    00007
    00008   Copyright (C) 1993-2007 Yukihiro Matsumoto
    00009
    00010 **********************************************************************/
    00011
    00012 #include "ruby/ruby.h"
    00013 #include "ruby/util.h"
    00014
    00015 #include <math.h>
    00016 #include <float.h>
    00017 #include <ctype.h>
    00018 #ifdef HAVE_IEEEFP_H
    00019 #include <ieeefp.h>
    00020 #endif
    00021 #include <assert.h>
    00022
    00023 VALUE rb_cBignum;
    00024
    00025 #if defined __MINGW32__
    00026 #define USHORT _USHORT
    00027 #endif
    00028
    00029 #define BDIGITS(x) (RBIGNUM_DIGITS(x))
    00030 #define BITSPERDIG (SIZEOF_BDIGITS*CHAR_BIT)
    00031 #define BIGRAD ((BDIGIT_DBL)1 << BITSPERDIG)
    00032 #define DIGSPERLONG (SIZEOF_LONG/SIZEOF_BDIGITS)
    00033 #if HAVE_LONG_LONG
    00034 # define DIGSPERLL (SIZEOF_LONG_LONG/SIZEOF_BDIGITS)
    00035 #endif
    00036 #define BIGUP(x) ((BDIGIT_DBL)(x) << BITSPERDIG)
    00037 #define BIGDN(x) RSHIFT(x,BITSPERDIG)
    00038 #define BIGLO(x) ((BDIGIT)((x) & (BIGRAD-1)))
    00039 #define BDIGMAX ((BDIGIT)-1)
    00040
    00041 #define BIGZEROP(x) (RBIGNUM_LEN(x) == 0 || \
    00042                      (BDIGITS(x)[0] == 0 && \
    00043                       (RBIGNUM_LEN(x) == 1 || bigzero_p(x))))
    00044
    00045 static int
    00046 bigzero_p(VALUE x)
    00047 {
    00048     long i;
    00049     BDIGIT *ds = BDIGITS(x);
    00050
    00051     for (i = RBIGNUM_LEN(x) - 1; 0 <= i; i--) {
    00052         if (ds[i]) return 0;
    00053     }
    00054     return 1;
    00055 }
    00056
    00057 int
    00058 rb_bigzero_p(VALUE x)
    00059 {
    00060     return BIGZEROP(x);
    00061 }
    00062
    00063 int
    00064 rb_cmpint(VALUE val, VALUE a, VALUE b)
    00065 {
    00066     if (NIL_P(val)) {
    00067         rb_cmperr(a, b);
    00068     }
    00069     if (FIXNUM_P(val)) {
    00070         long l = FIX2LONG(val);
    00071         if (l > 0) return 1;
    00072         if (l < 0) return -1;
    00073         return 0;
    00074     }
    00075     if (TYPE(val) == T_BIGNUM) {
    00076         if (BIGZEROP(val)) return 0;
    00077         if (RBIGNUM_SIGN(val)) return 1;
    00078         return -1;
    00079     }
    00080     if (RTEST(rb_funcall(val, '>', 1, INT2FIX(0)))) return 1;
    00081     if (RTEST(rb_funcall(val, '<', 1, INT2FIX(0)))) return -1;
    00082     return 0;
    00083 }
    00084
    00085 #define RBIGNUM_SET_LEN(b,l) \
    00086     ((RBASIC(b)->flags & RBIGNUM_EMBED_FLAG) ? \
    00087      (void)(RBASIC(b)->flags = \
    00088             (RBASIC(b)->flags & ~RBIGNUM_EMBED_LEN_MASK) | \
    00089             ((l) << RBIGNUM_EMBED_LEN_SHIFT)) : \
    00090      (void)(RBIGNUM(b)->as.heap.len = (l)))
    00091
    00092 static void
    00093 rb_big_realloc(VALUE big, long len)
    00094 {
    00095     BDIGIT *ds;
    00096     if (RBASIC(big)->flags & RBIGNUM_EMBED_FLAG) {
    00097         if (RBIGNUM_EMBED_LEN_MAX < len) {
    00098             ds = ALLOC_N(BDIGIT, len);
    00099             MEMCPY(ds, RBIGNUM(big)->as.ary, BDIGIT, RBIGNUM_EMBED_LEN_MAX);
    00100             RBIGNUM(big)->as.heap.len = RBIGNUM_LEN(big);
    00101             RBIGNUM(big)->as.heap.digits = ds;
    00102             RBASIC(big)->flags &= ~RBIGNUM_EMBED_FLAG;
    00103         }
    00104     }
    00105     else {
    00106         if (len <= RBIGNUM_EMBED_LEN_MAX) {
    00107             ds = RBIGNUM(big)->as.heap.digits;
    00108             RBASIC(big)->flags |= RBIGNUM_EMBED_FLAG;
    00109             RBIGNUM_SET_LEN(big, len);
    00110             if (ds) {
    00111                 MEMCPY(RBIGNUM(big)->as.ary, ds, BDIGIT, len);
    00112                 xfree(ds);
    00113             }
    00114         }
    00115         else {
    00116             if (RBIGNUM_LEN(big) == 0) {
    00117                 RBIGNUM(big)->as.heap.digits = ALLOC_N(BDIGIT, len);
    00118             }
    00119             else {
    00120                 REALLOC_N(RBIGNUM(big)->as.heap.digits, BDIGIT, len);
    00121             }
    00122         }
    00123     }
    00124 }
    00125
    00126 void
    00127 rb_big_resize(VALUE big, long len)
    00128 {
    00129     rb_big_realloc(big, len);
    00130     RBIGNUM_SET_LEN(big, len);
    00131 }
    00132
    00133 static VALUE
    00134 bignew_1(VALUE klass, long len, int sign)
    00135 {
    00136     NEWOBJ(big, struct RBignum);
    00137     OBJSETUP(big, klass, T_BIGNUM);
    00138     RBIGNUM_SET_SIGN(big, sign?1:0);
    00139     if (len <= RBIGNUM_EMBED_LEN_MAX) {
    00140         RBASIC(big)->flags |= RBIGNUM_EMBED_FLAG;
    00141         RBIGNUM_SET_LEN(big, len);
    00142     }
    00143     else {
    00144         RBIGNUM(big)->as.heap.digits = ALLOC_N(BDIGIT, len);
    00145         RBIGNUM(big)->as.heap.len = len;
    00146     }
    00147
    00148     return (VALUE)big;
    00149 }
    00150
    00151 #define bignew(len,sign) bignew_1(rb_cBignum,len,sign)
    00152
    00153 VALUE
    00154 rb_big_new(long len, int sign)
    00155 {
    00156     return bignew(len, sign != 0);
    00157 }
    00158
    00159 VALUE
    00160 rb_big_clone(VALUE x)
    00161 {
    00162     long len = RBIGNUM_LEN(x);
    00163     VALUE z = bignew_1(CLASS_OF(x), len, RBIGNUM_SIGN(x));
    00164
    00165     MEMCPY(BDIGITS(z), BDIGITS(x), BDIGIT, len);
    00166     return z;
    00167 }
    00168
    00169 /* modify a bignum by 2's complement */
    00170 static void
    00171 get2comp(VALUE x)
    00172 {
    00173     long i = RBIGNUM_LEN(x);
    00174     BDIGIT *ds = BDIGITS(x);
    00175     BDIGIT_DBL num;
    00176
    00177     if (!i) return;
    00178     while (i--) ds[i] = ~ds[i];
    00179     i = 0; num = 1;
    00180     do {
    00181         num += ds[i];
    00182         ds[i++] = BIGLO(num);
    00183         num = BIGDN(num);
    00184     } while (i < RBIGNUM_LEN(x));
    00185     if (num != 0) {
    00186         rb_big_resize(x, RBIGNUM_LEN(x)+1);
    00187         ds = BDIGITS(x);
    00188         ds[RBIGNUM_LEN(x)-1] = 1;
    00189     }
    00190 }
    00191
    00192 void
    00193 rb_big_2comp(VALUE x)                   /* get 2's complement */
    00194 {
    00195     get2comp(x);
    00196 }
    00197
    00198 static inline VALUE
    00199 bigtrunc(VALUE x)
    00200 {
    00201     long len = RBIGNUM_LEN(x);
    00202     BDIGIT *ds = BDIGITS(x);
    00203
    00204     if (len == 0) return x;
    00205     while (--len && !ds[len]);
    00206     if (RBIGNUM_LEN(x) > len+1) {
    00207         rb_big_resize(x, len+1);
    00208     }
    00209     return x;
    00210 }
    00211
    00212 static inline VALUE
    00213 bigfixize(VALUE x)
    00214 {
    00215     long len = RBIGNUM_LEN(x);
    00216     BDIGIT *ds = BDIGITS(x);
    00217
    00218     if (len == 0) return INT2FIX(0);
    00219     if ((size_t)(len*SIZEOF_BDIGITS) <= sizeof(long)) {
    00220         long num = 0;
    00221 #if 2*SIZEOF_BDIGITS > SIZEOF_LONG
    00222         num = (long)ds[0];
    00223 #else
    00224         while (len--) {
    00225             num = (long)(BIGUP(num) + ds[len]);
    00226         }
    00227 #endif
    00228         if (num >= 0) {
    00229             if (RBIGNUM_SIGN(x)) {
    00230                 if (POSFIXABLE(num)) return LONG2FIX(num);
    00231             }
    00232             else {
    00233                 if (NEGFIXABLE(-num)) return LONG2FIX(-num);
    00234             }
    00235         }
    00236     }
    00237     return x;
    00238 }
    00239
    00240 static VALUE
    00241 bignorm(VALUE x)
    00242 {
    00243     if (!FIXNUM_P(x) && TYPE(x) == T_BIGNUM) {
    00244         x = bigfixize(bigtrunc(x));
    00245     }
    00246     return x;
    00247 }
    00248
    00249 VALUE
    00250 rb_big_norm(VALUE x)
    00251 {
    00252     return bignorm(x);
    00253 }
    00254
    00255 VALUE
    00256 rb_uint2big(VALUE n)
    00257 {
    00258     BDIGIT_DBL num = n;
    00259     long i = 0;
    00260     BDIGIT *digits;
    00261     VALUE big;
    00262
    00263     big = bignew(DIGSPERLONG, 1);
    00264     digits = BDIGITS(big);
    00265     while (i < DIGSPERLONG) {
    00266         digits[i++] = BIGLO(num);
    00267         num = BIGDN(num);
    00268     }
    00269
    00270     i = DIGSPERLONG;
    00271     while (--i && !digits[i]) ;
    00272     RBIGNUM_SET_LEN(big, i+1);
    00273     return big;
    00274 }
    00275
    00276 VALUE
    00277 rb_int2big(SIGNED_VALUE n)
    00278 {
    00279     long neg = 0;
    00280     VALUE big;
    00281
    00282     if (n < 0) {
    00283         n = -n;
    00284         neg = 1;
    00285     }
    00286     big = rb_uint2big(n);
    00287     if (neg) {
    00288         RBIGNUM_SET_SIGN(big, 0);
    00289     }
    00290     return big;
    00291 }
    00292
    00293 VALUE
    00294 rb_uint2inum(VALUE n)
    00295 {
    00296     if (POSFIXABLE(n)) return LONG2FIX(n);
    00297     return rb_uint2big(n);
    00298 }
    00299
    00300 VALUE
    00301 rb_int2inum(SIGNED_VALUE n)
    00302 {
    00303     if (FIXABLE(n)) return LONG2FIX(n);
    00304     return rb_int2big(n);
    00305 }
    00306
    00307 #if SIZEOF_LONG % SIZEOF_BDIGITS != 0
    00308 # error unexpected SIZEOF_LONG : SIZEOF_BDIGITS ratio
    00309 #endif
    00310
    00311 /*
    00312  * buf is an array of long integers.
    00313  * buf is ordered from least significant word to most significant word.
    00314  * buf[0] is the least significant word and
    00315  * buf[num_longs-1] is the most significant word.
    00316  * This means words in buf is little endian.
    00317  * However each word in buf is native endian.
    00318  * (buf[i]&1) is the least significant bit and
    00319  * (buf[i]&(1<<(SIZEOF_LONG*CHAR_BIT-1))) is the most significant bit
    00320  * for each 0 <= i < num_longs.
    00321  * So buf is little endian at whole on a little endian machine.
    00322  * But buf is mixed endian on a big endian machine.
    00323  */
    00324 void
    00325 rb_big_pack(VALUE val, unsigned long *buf, long num_longs)
    00326 {
    00327     val = rb_to_int(val);
    00328     if (num_longs == 0)
    00329         return;
    00330     if (FIXNUM_P(val)) {
    00331         long i;
    00332         long tmp = FIX2LONG(val);
    00333         buf[0] = (unsigned long)tmp;
    00334         tmp = tmp < 0 ? ~0L : 0;
    00335         for (i = 1; i < num_longs; i++)
    00336             buf[i] = (unsigned long)tmp;
    00337         return;
    00338     }
    00339     else {
    00340         long len = RBIGNUM_LEN(val);
    00341         BDIGIT *ds = BDIGITS(val), *dend = ds + len;
    00342         long i, j;
    00343         for (i = 0; i < num_longs && ds < dend; i++) {
    00344             unsigned long l = 0;
    00345             for (j = 0; j < DIGSPERLONG && ds < dend; j++, ds++) {
    00346                 l |= ((unsigned long)*ds << (j * BITSPERDIG));
    00347             }
    00348             buf[i] = l;
    00349         }
    00350         for (; i < num_longs; i++)
    00351             buf[i] = 0;
    00352         if (RBIGNUM_NEGATIVE_P(val)) {
    00353             for (i = 0; i < num_longs; i++) {
    00354                 buf[i] = ~buf[i];
    00355             }
    00356             for (i = 0; i < num_longs; i++) {
    00357                 buf[i]++;
    00358                 if (buf[i] != 0)
    00359                     return;
    00360             }
    00361         }
    00362     }
    00363 }
    00364
    00365 /* See rb_big_pack comment for endianness of buf. */
    00366 VALUE
    00367 rb_big_unpack(unsigned long *buf, long num_longs)
    00368 {
    00369     while (2 <= num_longs) {
    00370         if (buf[num_longs-1] == 0 && (long)buf[num_longs-2] >= 0)
    00371             num_longs--;
    00372         else if (buf[num_longs-1] == ~0UL && (long)buf[num_longs-2] < 0)
    00373             num_longs--;
    00374         else
    00375             break;
    00376     }
    00377     if (num_longs == 0)
    00378         return INT2FIX(0);
    00379     else if (num_longs == 1)
    00380         return LONG2NUM((long)buf[0]);
    00381     else {
    00382         VALUE big;
    00383         BDIGIT *ds;
    00384         long len = num_longs * DIGSPERLONG;
    00385         long i;
    00386         big = bignew(len, 1);
    00387         ds = BDIGITS(big);
    00388         for (i = 0; i < num_longs; i++) {
    00389             unsigned long d = buf[i];
    00390 #if SIZEOF_LONG == SIZEOF_BDIGITS
    00391             *ds++ = d;
    00392 #else
    00393             int j;
    00394             for (j = 0; j < DIGSPERLONG; j++) {
    00395                 *ds++ = BIGLO(d);
    00396                 d = BIGDN(d);
    00397             }
    00398 #endif
    00399         }
    00400         if ((long)buf[num_longs-1] < 0) {
    00401             get2comp(big);
    00402             RBIGNUM_SET_SIGN(big, 0);
    00403         }
    00404         return bignorm(big);
    00405     }
    00406 }
    00407
    00408 #define QUAD_SIZE 8
    00409
    00410 #if SIZEOF_LONG_LONG == QUAD_SIZE && SIZEOF_BDIGITS*2 == SIZEOF_LONG_LONG
    00411
    00412 void
    00413 rb_quad_pack(char *buf, VALUE val)
    00414 {
    00415     LONG_LONG q;
    00416
    00417     val = rb_to_int(val);
    00418     if (FIXNUM_P(val)) {
    00419         q = FIX2LONG(val);
    00420     }
    00421     else {
    00422         long len = RBIGNUM_LEN(val);
    00423         BDIGIT *ds;
    00424
    00425         if (len > SIZEOF_LONG_LONG/SIZEOF_BDIGITS) {
    00426             len = SIZEOF_LONG_LONG/SIZEOF_BDIGITS;
    00427         }
    00428         ds = BDIGITS(val);
    00429         q = 0;
    00430         while (len--) {
    00431             q = BIGUP(q);
    00432             q += ds[len];
    00433         }
    00434         if (!RBIGNUM_SIGN(val)) q = -q;
    00435     }
    00436     memcpy(buf, (char*)&q, SIZEOF_LONG_LONG);
    00437 }
    00438
    00439 VALUE
    00440 rb_quad_unpack(const char *buf, int sign)
    00441 {
    00442     unsigned LONG_LONG q;
    00443     long neg = 0;
    00444     long i;
    00445     BDIGIT *digits;
    00446     VALUE big;
    00447
    00448     memcpy(&q, buf, SIZEOF_LONG_LONG);
    00449     if (sign) {
    00450         if (FIXABLE((LONG_LONG)q)) return LONG2FIX((LONG_LONG)q);
    00451         if ((LONG_LONG)q < 0) {
    00452             q = -(LONG_LONG)q;
    00453             neg = 1;
    00454         }
    00455     }
    00456     else {
    00457         if (POSFIXABLE(q)) return LONG2FIX(q);
    00458     }
    00459
    00460     i = 0;
    00461     big = bignew(DIGSPERLL, 1);
    00462     digits = BDIGITS(big);
    00463     while (i < DIGSPERLL) {
    00464         digits[i++] = BIGLO(q);
    00465         q = BIGDN(q);
    00466     }
    00467
    00468     i = DIGSPERLL;
    00469     while (i-- && !digits[i]) ;
    00470     RBIGNUM_SET_LEN(big, i+1);
    00471
    00472     if (neg) {
    00473         RBIGNUM_SET_SIGN(big, 0);
    00474     }
    00475     return bignorm(big);
    00476 }
    00477
    00478 #else
    00479
    00480 static int
    00481 quad_buf_complement(char *buf, size_t len)
    00482 {
    00483     size_t i;
    00484     for (i = 0; i < len; i++)
    00485         buf[i] = ~buf[i];
    00486     for (i = 0; i < len; i++) {
    00487         buf[i]++;
    00488         if (buf[i] != 0)
    00489             return 0;
    00490     }
    00491     return 1;
    00492 }
    00493
    00494 void
    00495 rb_quad_pack(char *buf, VALUE val)
    00496 {
    00497     long len;
    00498
    00499     memset(buf, 0, QUAD_SIZE);
    00500     val = rb_to_int(val);
    00501     if (FIXNUM_P(val)) {
    00502         val = rb_int2big(FIX2LONG(val));
    00503     }
    00504     len = RBIGNUM_LEN(val) * SIZEOF_BDIGITS;
    00505     if (len > QUAD_SIZE) {
    00506         len = QUAD_SIZE;
    00507     }
    00508     memcpy(buf, (char*)BDIGITS(val), len);
    00509     if (RBIGNUM_NEGATIVE_P(val)) {
    00510         quad_buf_complement(buf, QUAD_SIZE);
    00511     }
    00512 }
    00513
    00514 #define BNEG(b) (RSHIFT(((BDIGIT*)b)[QUAD_SIZE/SIZEOF_BDIGITS-1],BITSPERDIG-1) != 0)
    00515
    00516 VALUE
    00517 rb_quad_unpack(const char *buf, int sign)
    00518 {
    00519     VALUE big = bignew(QUAD_SIZE/SIZEOF_BDIGITS, 1);
    00520
    00521     memcpy((char*)BDIGITS(big), buf, QUAD_SIZE);
    00522     if (sign && BNEG(buf)) {
    00523         char *tmp = (char*)BDIGITS(big);
    00524
    00525         RBIGNUM_SET_SIGN(big, 0);
    00526         quad_buf_complement(tmp, QUAD_SIZE);
    00527     }
    00528
    00529     return bignorm(big);
    00530 }
    00531
    00532 #endif
    00533
    00534 VALUE
    00535 rb_cstr_to_inum(const char *str, int base, int badcheck)
    00536 {
    00537     const char *s = str;
    00538     char *end;
    00539     char sign = 1, nondigit = 0;
    00540     int c;
    00541     BDIGIT_DBL num;
    00542     long len, blen = 1;
    00543     long i;
    00544     VALUE z;
    00545     BDIGIT *zds;
    00546
    00547 #undef ISDIGIT
    00548 #define ISDIGIT(c) ('0' <= (c) && (c) <= '9')
    00549 #define conv_digit(c) \
    00550     (!ISASCII(c) ? -1 : \
    00551      ISDIGIT(c) ? ((c) - '0') : \
    00552      ISLOWER(c) ? ((c) - 'a' + 10) : \
    00553      ISUPPER(c) ? ((c) - 'A' + 10) : \
    00554      -1)
    00555
    00556     if (!str) {
    00557         if (badcheck) goto bad;
    00558         return INT2FIX(0);
    00559     }
    00560     while (ISSPACE(*str)) str++;
    00561
    00562     if (str[0] == '+') {
    00563         str++;
    00564     }
    00565     else if (str[0] == '-') {
    00566         str++;
    00567         sign = 0;
    00568     }
    00569     if (str[0] == '+' || str[0] == '-') {
    00570         if (badcheck) goto bad;
    00571         return INT2FIX(0);
    00572     }
    00573     if (base <= 0) {
    00574         if (str[0] == '0') {
    00575             switch (str[1]) {
    00576               case 'x': case 'X':
    00577                 base = 16;
    00578                 break;
    00579               case 'b': case 'B':
    00580                 base = 2;
    00581                 break;
    00582               case 'o': case 'O':
    00583                 base = 8;
    00584                 break;
    00585               case 'd': case 'D':
    00586                 base = 10;
    00587                 break;
    00588               default:
    00589                 base = 8;
    00590             }
    00591         }
    00592         else if (base < -1) {
    00593             base = -base;
    00594         }
    00595         else {
    00596             base = 10;
    00597         }
    00598     }
    00599     switch (base) {
    00600       case 2:
    00601         len = 1;
    00602         if (str[0] == '0' && (str[1] == 'b'||str[1] == 'B')) {
    00603             str += 2;
    00604         }
    00605         break;
    00606       case 3:
    00607         len = 2;
    00608         break;
    00609       case 8:
    00610         if (str[0] == '0' && (str[1] == 'o'||str[1] == 'O')) {
    00611             str += 2;
    00612         }
    00613       case 4: case 5: case 6: case 7:
    00614         len = 3;
    00615         break;
    00616       case 10:
    00617         if (str[0] == '0' && (str[1] == 'd'||str[1] == 'D')) {
    00618             str += 2;
    00619         }
    00620       case 9: case 11: case 12: case 13: case 14: case 15:
    00621         len = 4;
    00622         break;
    00623       case 16:
    00624         len = 4;
    00625         if (str[0] == '0' && (str[1] == 'x'||str[1] == 'X')) {
    00626             str += 2;
    00627         }
    00628         break;
    00629       default:
    00630         if (base < 2 || 36 < base) {
    00631             rb_raise(rb_eArgError, "invalid radix %d", base);
    00632         }
    00633         if (base <= 32) {
    00634             len = 5;
    00635         }
    00636         else {
    00637             len = 6;
    00638         }
    00639         break;
    00640     }
    00641     if (*str == '0') {          /* squeeze preceding 0s */
    00642         int us = 0;
    00643         while ((c = *++str) == '0' || c == '_') {
    00644             if (c == '_') {
    00645                 if (++us >= 2)
    00646                     break;
    00647             } else
    00648                 us = 0;
    00649         }
    00650         if (!(c = *str) || ISSPACE(c)) --str;
    00651     }
    00652     c = *str;
    00653     c = conv_digit(c);
    00654     if (c < 0 || c >= base) {
    00655         if (badcheck) goto bad;
    00656         return INT2FIX(0);
    00657     }
    00658     len *= strlen(str)*sizeof(char);
    00659
    00660     if ((size_t)len <= (sizeof(long)*CHAR_BIT)) {
    00661         unsigned long val = STRTOUL(str, &end, base);
    00662
    00663         if (str < end && *end == '_') goto bigparse;
    00664         if (badcheck) {
    00665             if (end == str) goto bad; /* no number */
    00666             while (*end && ISSPACE(*end)) end++;
    00667             if (*end) goto bad;       /* trailing garbage */
    00668         }
    00669
    00670         if (POSFIXABLE(val)) {
    00671             if (sign) return LONG2FIX(val);
    00672             else {
    00673                 long result = -(long)val;
    00674                 return LONG2FIX(result);
    00675             }
    00676         }
    00677         else {
    00678             VALUE big = rb_uint2big(val);
    00679             RBIGNUM_SET_SIGN(big, sign);
    00680             return bignorm(big);
    00681         }
    00682     }
    00683   bigparse:
    00684     len = (len/BITSPERDIG)+1;
    00685     if (badcheck && *str == '_') goto bad;
    00686
    00687     z = bignew(len, sign);
    00688     zds = BDIGITS(z);
    00689     for (i=len;i--;) zds[i]=0;
    00690     while ((c = *str++) != 0) {
    00691         if (c == '_') {
    00692             if (nondigit) {
    00693                 if (badcheck) goto bad;
    00694                 break;
    00695             }
    00696             nondigit = c;
    00697             continue;
    00698         }
    00699         else if ((c = conv_digit(c)) < 0) {
    00700             break;
    00701         }
    00702         if (c >= base) break;
    00703         nondigit = 0;
    00704         i = 0;
    00705         num = c;
    00706         for (;;) {
    00707             while (i<blen) {
    00708                 num += (BDIGIT_DBL)zds[i]*base;
    00709                 zds[i++] = BIGLO(num);
    00710                 num = BIGDN(num);
    00711             }
    00712             if (num) {
    00713                 blen++;
    00714                 continue;
    00715             }
    00716             break;
    00717         }
    00718     }
    00719     if (badcheck) {
    00720         str--;
    00721         if (s+1 < str && str[-1] == '_') goto bad;
    00722         while (*str && ISSPACE(*str)) str++;
    00723         if (*str) {
    00724           bad:
    00725             rb_invalid_str(s, "Integer()");
    00726         }
    00727     }
    00728
    00729     return bignorm(z);
    00730 }
    00731
    00732 VALUE
    00733 rb_str_to_inum(VALUE str, int base, int badcheck)
    00734 {
    00735     char *s;
    00736     long len;
    00737
    00738     StringValue(str);
    00739     if (badcheck) {
    00740         s = StringValueCStr(str);
    00741     }
    00742     else {
    00743         s = RSTRING_PTR(str);
    00744     }
    00745     if (s) {
    00746         len = RSTRING_LEN(str);
    00747         if (s[len]) {           /* no sentinel somehow */
    00748             char *p = ALLOCA_N(char, len+1);
    00749
    00750             MEMCPY(p, s, char, len);
    00751             p[len] = '\0';
    00752             s = p;
    00753         }
    00754     }
    00755     return rb_cstr_to_inum(s, base, badcheck);
    00756 }
    00757
    00758 #if HAVE_LONG_LONG
    00759
    00760 static VALUE
    00761 rb_ull2big(unsigned LONG_LONG n)
    00762 {
    00763     BDIGIT_DBL num = n;
    00764     long i = 0;
    00765     BDIGIT *digits;
    00766     VALUE big;
    00767
    00768     big = bignew(DIGSPERLL, 1);
    00769     digits = BDIGITS(big);
    00770     while (i < DIGSPERLL) {
    00771         digits[i++] = BIGLO(num);
    00772         num = BIGDN(num);
    00773     }
    00774
    00775     i = DIGSPERLL;
    00776     while (i-- && !digits[i]) ;
    00777     RBIGNUM_SET_LEN(big, i+1);
    00778     return big;
    00779 }
    00780
    00781 static VALUE
    00782 rb_ll2big(LONG_LONG n)
    00783 {
    00784     long neg = 0;
    00785     VALUE big;
    00786
    00787     if (n < 0) {
    00788         n = -n;
    00789         neg = 1;
    00790     }
    00791     big = rb_ull2big(n);
    00792     if (neg) {
    00793         RBIGNUM_SET_SIGN(big, 0);
    00794     }
    00795     return big;
    00796 }
    00797
    00798 VALUE
    00799 rb_ull2inum(unsigned LONG_LONG n)
    00800 {
    00801     if (POSFIXABLE(n)) return LONG2FIX(n);
    00802     return rb_ull2big(n);
    00803 }
    00804
    00805 VALUE
    00806 rb_ll2inum(LONG_LONG n)
    00807 {
    00808     if (FIXABLE(n)) return LONG2FIX(n);
    00809     return rb_ll2big(n);
    00810 }
    00811
    00812 #endif  /* HAVE_LONG_LONG */
    00813
    00814 VALUE
    00815 rb_cstr2inum(const char *str, int base)
    00816 {
    00817     return rb_cstr_to_inum(str, base, base==0);
    00818 }
    00819
    00820 VALUE
    00821 rb_str2inum(VALUE str, int base)
    00822 {
    00823     return rb_str_to_inum(str, base, base==0);
    00824 }
    00825
    00826 const char ruby_digitmap[] = "0123456789abcdefghijklmnopqrstuvwxyz";
    00827
    00828 static VALUE bigsqr(VALUE x);
    00829 static void bigdivmod(VALUE x, VALUE y, volatile VALUE *divp, volatile VALUE *modp);
    00830
    00831 #define POW2_P(x) (((x)&((x)-1))==0)
    00832
    00833 static inline int
    00834 ones(register unsigned long x)
    00835 {
    00836 #if SIZEOF_LONG == 8
    00837 # define MASK_55 0x5555555555555555UL
    00838 # define MASK_33 0x3333333333333333UL
    00839 # define MASK_0f 0x0f0f0f0f0f0f0f0fUL
    00840 #else
    00841 # define MASK_55 0x55555555UL
    00842 # define MASK_33 0x33333333UL
    00843 # define MASK_0f 0x0f0f0f0fUL
    00844 #endif
    00845     x -= (x >> 1) & MASK_55;
    00846     x = ((x >> 2) & MASK_33) + (x & MASK_33);
    00847     x = ((x >> 4) + x) & MASK_0f;
    00848     x += (x >> 8);
    00849     x += (x >> 16);
    00850 #if SIZEOF_LONG == 8
    00851     x += (x >> 32);
    00852 #endif
    00853     return (int)(x & 0x7f);
    00854 #undef MASK_0f
    00855 #undef MASK_33
    00856 #undef MASK_55
    00857 }
    00858
    00859 static inline unsigned long
    00860 next_pow2(register unsigned long x)
    00861 {
    00862     x |= x >> 1;
    00863     x |= x >> 2;
    00864     x |= x >> 4;
    00865     x |= x >> 8;
    00866     x |= x >> 16;
    00867 #if SIZEOF_LONG == 8
    00868     x |= x >> 32;
    00869 #endif
    00870     return x + 1;
    00871 }
    00872
    00873 static inline int
    00874 floor_log2(register unsigned long x)
    00875 {
    00876     x |= x >> 1;
    00877     x |= x >> 2;
    00878     x |= x >> 4;
    00879     x |= x >> 8;
    00880     x |= x >> 16;
    00881 #if SIZEOF_LONG == 8
    00882     x |= x >> 32;
    00883 #endif
    00884     return (int)ones(x) - 1;
    00885 }
    00886
    00887 static inline int
    00888 ceil_log2(register unsigned long x)
    00889 {
    00890     return floor_log2(x) + !POW2_P(x);
    00891 }
    00892
    00893 #define LOG2_KARATSUBA_DIGITS 7
    00894 #define KARATSUBA_DIGITS (1L<<LOG2_KARATSUBA_DIGITS)
    00895 #define MAX_BIG2STR_TABLE_ENTRIES 64
    00896
    00897 static VALUE big2str_power_cache[35][MAX_BIG2STR_TABLE_ENTRIES];
    00898
    00899 static void
    00900 power_cache_init(void)
    00901 {
    00902     int i, j;
    00903     for (i = 0; i < 35; ++i) {
    00904         for (j = 0; j < MAX_BIG2STR_TABLE_ENTRIES; ++j) {
    00905             big2str_power_cache[i][j] = Qnil;
    00906         }
    00907     }
    00908 }
    00909
    00910 static inline VALUE
    00911 power_cache_get_power0(int base, int i)
    00912 {
    00913     if (NIL_P(big2str_power_cache[base - 2][i])) {
    00914         big2str_power_cache[base - 2][i] =
    00915             i == 0 ? rb_big_pow(rb_int2big(base), INT2FIX(KARATSUBA_DIGITS))
    00916                    : bigsqr(power_cache_get_power0(base, i - 1));
    00917         rb_gc_register_mark_object(big2str_power_cache[base - 2][i]);
    00918     }
    00919     return big2str_power_cache[base - 2][i];
    00920 }
    00921
    00922 static VALUE
    00923 power_cache_get_power(int base, long n1, long* m1)
    00924 {
    00925     int i, m;
    00926     long j;
    00927     VALUE t;
    00928
    00929     if (n1 <= KARATSUBA_DIGITS)
    00930         rb_bug("n1 > KARATSUBA_DIGITS");
    00931
    00932     m = ceil_log2(n1);
    00933     if (m1) *m1 = 1 << m;
    00934     i = m - LOG2_KARATSUBA_DIGITS;
    00935     if (i >= MAX_BIG2STR_TABLE_ENTRIES)
    00936         i = MAX_BIG2STR_TABLE_ENTRIES - 1;
    00937     t = power_cache_get_power0(base, i);
    00938
    00939     j = KARATSUBA_DIGITS*(1 << i);
    00940     while (n1 > j) {
    00941         t = bigsqr(t);
    00942         j *= 2;
    00943     }
    00944     return t;
    00945 }
    00946
    00947 /* big2str_muraken_find_n1
    00948  *
    00949  * Let a natural number x is given by:
    00950  * x = 2^0 * x_0 + 2^1 * x_1 + ... + 2^(B*n_0 - 1) * x_{B*n_0 - 1},
    00951  * where B is BITSPERDIG (i.e. BDIGITS*CHAR_BIT) and n_0 is
    00952  * RBIGNUM_LEN(x).
    00953  *
    00954  * Now, we assume n_1 = min_n \{ n | 2^(B*n_0/2) <= b_1^(n_1) \}, so
    00955  * it is realized that 2^(B*n_0) <= {b_1}^{2*n_1}, where b_1 is a
    00956  * given radix number. And then, we have n_1 <= (B*n_0) /
    00957  * (2*log_2(b_1)), therefore n_1 is given by ceil((B*n_0) /
    00958  * (2*log_2(b_1))).
    00959  */
    00960 static long
    00961 big2str_find_n1(VALUE x, int base)
    00962 {
    00963     static const double log_2[] = {
    00964         1.0,              1.58496250072116, 2.0,
    00965         2.32192809488736, 2.58496250072116, 2.8073549220576,
    00966         3.0,              3.16992500144231, 3.32192809488736,
    00967         3.4594316186373,  3.58496250072116, 3.70043971814109,
    00968         3.8073549220576,  3.90689059560852, 4.0,
    00969         4.08746284125034, 4.16992500144231, 4.24792751344359,
    00970         4.32192809488736, 4.39231742277876, 4.4594316186373,
    00971         4.52356195605701, 4.58496250072116, 4.64385618977472,
    00972         4.70043971814109, 4.75488750216347, 4.8073549220576,
    00973         4.85798099512757, 4.90689059560852, 4.95419631038688,
    00974         5.0,              5.04439411935845, 5.08746284125034,
    00975         5.12928301694497, 5.16992500144231
    00976     };
    00977     long bits;
    00978
    00979     if (base < 2 || 36 < base)
    00980         rb_bug("invalid radix %d", base);
    00981
    00982     if (FIXNUM_P(x)) {
    00983         bits = (SIZEOF_LONG*CHAR_BIT - 1)/2 + 1;
    00984     }
    00985     else if (BIGZEROP(x)) {
    00986         return 0;
    00987     }
    00988     else if (RBIGNUM_LEN(x) >= LONG_MAX/BITSPERDIG) {
    00989         rb_raise(rb_eRangeError, "bignum too big to convert into `string'");
    00990     }
    00991     else {
    00992         bits = BITSPERDIG*RBIGNUM_LEN(x);
    00993     }
    00994
    00995     return (long)ceil(bits/log_2[base - 2]);
    00996 }
    00997
    00998 static long
    00999 big2str_orig(VALUE x, int base, char* ptr, long len, long hbase, int trim)
    01000 {
    01001     long i = RBIGNUM_LEN(x), j = len;
    01002     BDIGIT* ds = BDIGITS(x);
    01003
    01004     while (i && j > 0) {
    01005         long k = i;
    01006         BDIGIT_DBL num = 0;
    01007
    01008         while (k--) {               /* x / hbase */
    01009             num = BIGUP(num) + ds[k];
    01010             ds[k] = (BDIGIT)(num / hbase);
    01011             num %= hbase;
    01012         }
    01013         if (trim && ds[i-1] == 0) i--;
    01014         k = SIZEOF_BDIGITS;
    01015         while (k--) {
    01016             ptr[--j] = ruby_digitmap[num % base];
    01017             num /= base;
    01018             if (j <= 0) break;
    01019             if (trim && i == 0 && num == 0) break;
    01020         }
    01021     }
    01022     if (trim) {
    01023         while (j < len && ptr[j] == '0') j++;
    01024         MEMMOVE(ptr, ptr + j, char, len - j);
    01025         len -= j;
    01026     }
    01027     return len;
    01028 }
    01029
    01030 static long
    01031 big2str_karatsuba(VALUE x, int base, char* ptr,
    01032                   long n1, long len, long hbase, int trim)
    01033 {
    01034     long lh, ll, m1;
    01035     VALUE b, q, r;
    01036
    01037     if (BIGZEROP(x)) {
    01038         if (trim) return 0;
    01039         else {
    01040             memset(ptr, '0', len);
    01041             return len;
    01042         }
    01043     }
    01044
    01045     if (n1 <= KARATSUBA_DIGITS) {
    01046         return big2str_orig(x, base, ptr, len, hbase, trim);
    01047     }
    01048
    01049     b = power_cache_get_power(base, n1, &m1);
    01050     bigdivmod(x, b, &q, &r);
    01051     lh = big2str_karatsuba(q, base, ptr, (len - m1)/2,
    01052                            len - m1, hbase, trim);
    01053     rb_big_resize(q, 0);
    01054     ll = big2str_karatsuba(r, base, ptr + lh, m1/2,
    01055                            m1, hbase, !lh && trim);
    01056     rb_big_resize(r, 0);
    01057
    01058     return lh + ll;
    01059 }
    01060
    01061 VALUE
    01062 rb_big2str0(VALUE x, int base, int trim)
    01063 {
    01064     int off;
    01065     VALUE ss, xx;
    01066     long n1, n2, len, hbase;
    01067     char* ptr;
    01068
    01069     if (FIXNUM_P(x)) {
    01070         return rb_fix2str(x, base);
    01071     }
    01072     if (BIGZEROP(x)) {
    01073         return rb_usascii_str_new2("0");
    01074     }
    01075
    01076     if (base < 2 || 36 < base)
    01077         rb_raise(rb_eArgError, "invalid radix %d", base);
    01078
    01079     n2 = big2str_find_n1(x, base);
    01080     n1 = (n2 + 1) / 2;
    01081     ss = rb_usascii_str_new(0, n2 + 1); /* plus one for sign */
    01082     ptr = RSTRING_PTR(ss);
    01083     ptr[0] = RBIGNUM_SIGN(x) ? '+' : '-';
    01084
    01085     hbase = base*base;
    01086 #if SIZEOF_BDIGITS > 2
    01087     hbase *= hbase;
    01088 #endif
    01089     off = !(trim && RBIGNUM_SIGN(x)); /* erase plus sign if trim */
    01090     xx = rb_big_clone(x);
    01091     RBIGNUM_SET_SIGN(xx, 1);
    01092     if (n1 <= KARATSUBA_DIGITS) {
    01093         len = off + big2str_orig(xx, base, ptr + off, n2, hbase, trim);
    01094     }
    01095     else {
    01096         len = off + big2str_karatsuba(xx, base, ptr + off, n1,
    01097                                       n2, hbase, trim);
    01098     }
    01099     rb_big_resize(xx, 0);
    01100
    01101     ptr[len] = '\0';
    01102     rb_str_resize(ss, len);
    01103
    01104     return ss;
    01105 }
    01106
    01107 VALUE
    01108 rb_big2str(VALUE x, int base)
    01109 {
    01110     return rb_big2str0(x, base, 1);
    01111 }
    01112
    01113 /*
    01114  *  call-seq:
    01115  *     big.to_s(base=10)   ->  string
    01116  *
    01117  *  Returns a string containing the representation of <i>big</i> radix
    01118  *  <i>base</i> (2 through 36).
    01119  *
    01120  *     12345654321.to_s         #=> "12345654321"
    01121  *     12345654321.to_s(2)      #=> "1011011111110110111011110000110001"
    01122  *     12345654321.to_s(8)      #=> "133766736061"
    01123  *     12345654321.to_s(16)     #=> "2dfdbbc31"
    01124  *     78546939656932.to_s(36)  #=> "rubyrules"
    01125  */
    01126
    01127 static VALUE
    01128 rb_big_to_s(int argc, VALUE *argv, VALUE x)
    01129 {
    01130     int base;
    01131
    01132     if (argc == 0) base = 10;
    01133     else {
    01134         VALUE b;
    01135
    01136         rb_scan_args(argc, argv, "01", &b);
    01137         base = NUM2INT(b);
    01138     }
    01139     return rb_big2str(x, base);
    01140 }
    01141
    01142 static VALUE
    01143 big2ulong(VALUE x, const char *type, int check)
    01144 {
    01145     long len = RBIGNUM_LEN(x);
    01146     BDIGIT_DBL num;
    01147     BDIGIT *ds;
    01148
    01149     if (len > DIGSPERLONG) {
    01150         if (check)
    01151             rb_raise(rb_eRangeError, "bignum too big to convert into `%s'", type);
    01152         len = DIGSPERLONG;
    01153     }
    01154     ds = BDIGITS(x);
    01155     num = 0;
    01156     while (len--) {
    01157         num = BIGUP(num);
    01158         num += ds[len];
    01159     }
    01160     return (VALUE)num;
    01161 }
    01162
    01163 VALUE
    01164 rb_big2ulong_pack(VALUE x)
    01165 {
    01166     VALUE num = big2ulong(x, "unsigned long", FALSE);
    01167     if (!RBIGNUM_SIGN(x)) {
    01168         return (VALUE)(-(SIGNED_VALUE)num);
    01169     }
    01170     return num;
    01171 }
    01172
    01173 VALUE
    01174 rb_big2ulong(VALUE x)
    01175 {
    01176     VALUE num = big2ulong(x, "unsigned long", TRUE);
    01177
    01178     if (!RBIGNUM_SIGN(x)) {
    01179         if ((SIGNED_VALUE)num < 0) {
    01180             rb_raise(rb_eRangeError, "bignum out of range of unsigned long");
    01181         }
    01182         return (VALUE)(-(SIGNED_VALUE)num);
    01183     }
    01184     return num;
    01185 }
    01186
    01187 SIGNED_VALUE
    01188 rb_big2long(VALUE x)
    01189 {
    01190     VALUE num = big2ulong(x, "long", TRUE);
    01191
    01192     if ((SIGNED_VALUE)num < 0 &&
    01193         (RBIGNUM_SIGN(x) || (SIGNED_VALUE)num != LONG_MIN)) {
    01194         rb_raise(rb_eRangeError, "bignum too big to convert into `long'");
    01195     }
    01196     if (!RBIGNUM_SIGN(x)) return -(SIGNED_VALUE)num;
    01197     return num;
    01198 }
    01199
    01200 #if HAVE_LONG_LONG
    01201
    01202 static unsigned LONG_LONG
    01203 big2ull(VALUE x, const char *type)
    01204 {
    01205     long len = RBIGNUM_LEN(x);
    01206     BDIGIT_DBL num;
    01207     BDIGIT *ds;
    01208
    01209     if (len > SIZEOF_LONG_LONG/SIZEOF_BDIGITS)
    01210         rb_raise(rb_eRangeError, "bignum too big to convert into `%s'", type);
    01211     ds = BDIGITS(x);
    01212     num = 0;
    01213     while (len--) {
    01214         num = BIGUP(num);
    01215         num += ds[len];
    01216     }
    01217     return num;
    01218 }
    01219
    01220 unsigned LONG_LONG
    01221 rb_big2ull(VALUE x)
    01222 {
    01223     unsigned LONG_LONG num = big2ull(x, "unsigned long long");
    01224
    01225     if (!RBIGNUM_SIGN(x))
    01226         return (VALUE)(-(SIGNED_VALUE)num);
    01227     return num;
    01228 }
    01229
    01230 LONG_LONG
    01231 rb_big2ll(VALUE x)
    01232 {
    01233     unsigned LONG_LONG num = big2ull(x, "long long");
    01234
    01235     if ((LONG_LONG)num < 0 && (RBIGNUM_SIGN(x)
    01236                                || (LONG_LONG)num != LLONG_MIN)) {
    01237         rb_raise(rb_eRangeError, "bignum too big to convert into `long long'");
    01238     }
    01239     if (!RBIGNUM_SIGN(x)) return -(LONG_LONG)num;
    01240     return num;
    01241 }
    01242
    01243 #endif  /* HAVE_LONG_LONG */
    01244
    01245 static VALUE
    01246 dbl2big(double d)
    01247 {
    01248     long i = 0;
    01249     BDIGIT c;
    01250     BDIGIT *digits;
    01251     VALUE z;
    01252     double u = (d < 0)?-d:d;
    01253
    01254     if (isinf(d)) {
    01255         rb_raise(rb_eFloatDomainError, d < 0 ? "-Infinity" : "Infinity");
    01256     }
    01257     if (isnan(d)) {
    01258         rb_raise(rb_eFloatDomainError, "NaN");
    01259     }
    01260
    01261     while (!POSFIXABLE(u) || 0 != (long)u) {
    01262         u /= (double)(BIGRAD);
    01263         i++;
    01264     }
    01265     z = bignew(i, d>=0);
    01266     digits = BDIGITS(z);
    01267     while (i--) {
    01268         u *= BIGRAD;
    01269         c = (BDIGIT)u;
    01270         u -= c;
    01271         digits[i] = c;
    01272     }
    01273
    01274     return z;
    01275 }
    01276
    01277 VALUE
    01278 rb_dbl2big(double d)
    01279 {
    01280     return bignorm(dbl2big(d));
    01281 }
    01282
    01283 static int
    01284 nlz(BDIGIT x)
    01285 {
    01286     BDIGIT y;
    01287     int n = BITSPERDIG;
    01288 #if BITSPERDIG > 64
    01289     y = x >> 64; if (y) {n -= 64; x = y;}
    01290 #endif
    01291 #if BITSPERDIG > 32
    01292     y = x >> 32; if (y) {n -= 32; x = y;}
    01293 #endif
    01294 #if BITSPERDIG > 16
    01295     y = x >> 16; if (y) {n -= 16; x = y;}
    01296 #endif
    01297     y = x >>  8; if (y) {n -=  8; x = y;}
    01298     y = x >>  4; if (y) {n -=  4; x = y;}
    01299     y = x >>  2; if (y) {n -=  2; x = y;}
    01300     y = x >>  1; if (y) {return n - 2;}
    01301     return n - x;
    01302 }
    01303
    01304 static double
    01305 big2dbl(VALUE x)
    01306 {
    01307     double d = 0.0;
    01308     long i = (bigtrunc(x), RBIGNUM_LEN(x)), lo = 0, bits;
    01309     BDIGIT *ds = BDIGITS(x), dl;
    01310
    01311     if (i) {
    01312         bits = i * BITSPERDIG - nlz(ds[i-1]);
    01313         if (bits > DBL_MANT_DIG+DBL_MAX_EXP) {
    01314             d = HUGE_VAL;
    01315         }
    01316         else {
    01317             if (bits > DBL_MANT_DIG+1)
    01318                 lo = (bits -= DBL_MANT_DIG+1) / BITSPERDIG;
    01319             else
    01320                 bits = 0;
    01321             while (--i > lo) {
    01322                 d = ds[i] + BIGRAD*d;
    01323             }
    01324             dl = ds[i];
    01325             if (bits && (dl & (1UL << (bits %= BITSPERDIG)))) {
    01326                 int carry = dl & ~(~(BDIGIT)0 << bits);
    01327                 if (!carry) {
    01328                     while (i-- > 0) {
    01329                         if ((carry = ds[i]) != 0) break;
    01330                     }
    01331                 }
    01332                 if (carry) {
    01333                     dl &= (BDIGIT)~0 << bits;
    01334                     dl += (BDIGIT)1 << bits;
    01335                     if (!dl) d += 1;
    01336                 }
    01337             }
    01338             d = dl + BIGRAD*d;
    01339             if (lo) {
    01340                 if (lo > INT_MAX / BITSPERDIG)
    01341                     d = HUGE_VAL;
    01342                 else if (lo < INT_MIN / BITSPERDIG)
    01343                     d = 0.0;
    01344                 else
    01345                     d = ldexp(d, (int)(lo * BITSPERDIG));
    01346             }
    01347         }
    01348     }
    01349     if (!RBIGNUM_SIGN(x)) d = -d;
    01350     return d;
    01351 }
    01352
    01353 double
    01354 rb_big2dbl(VALUE x)
    01355 {
    01356     double d = big2dbl(x);
    01357
    01358     if (isinf(d)) {
    01359         rb_warning("Bignum out of Float range");
    01360         if (d < 0.0)
    01361             d = -HUGE_VAL;
    01362         else
    01363             d = HUGE_VAL;
    01364     }
    01365     return d;
    01366 }
    01367
    01368 /*
    01369  *  call-seq:
    01370  *     big.to_f -> float
    01371  *
    01372  *  Converts <i>big</i> to a <code>Float</code>. If <i>big</i> doesn't
    01373  *  fit in a <code>Float</code>, the result is infinity.
    01374  *
    01375  */
    01376
    01377 static VALUE
    01378 rb_big_to_f(VALUE x)
    01379 {
    01380     return DBL2NUM(rb_big2dbl(x));
    01381 }
    01382
    01383 /*
    01384  *  call-seq:
    01385  *     big <=> numeric   -> -1, 0, +1 or nil
    01386  *
    01387  *  Comparison---Returns -1, 0, or +1 depending on whether <i>big</i> is
    01388  *  less than, equal to, or greater than <i>numeric</i>. This is the
    01389  *  basis for the tests in <code>Comparable</code>.
    01390  *
    01391  */
    01392
    01393 VALUE
    01394 rb_big_cmp(VALUE x, VALUE y)
    01395 {
    01396     long xlen = RBIGNUM_LEN(x);
    01397     BDIGIT *xds, *yds;
    01398
    01399     switch (TYPE(y)) {
    01400       case T_FIXNUM:
    01401         y = rb_int2big(FIX2LONG(y));
    01402         break;
    01403
    01404       case T_BIGNUM:
    01405         break;
    01406
    01407       case T_FLOAT:
    01408         {
    01409             double a = RFLOAT_VALUE(y);
    01410
    01411             if (isinf(a)) {
    01412                 if (a > 0.0) return INT2FIX(-1);
    01413                 else return INT2FIX(1);
    01414             }
    01415             return rb_dbl_cmp(rb_big2dbl(x), a);
    01416         }
    01417
    01418       default:
    01419         return rb_num_coerce_cmp(x, y, rb_intern("<=>"));
    01420     }
    01421
    01422     if (RBIGNUM_SIGN(x) > RBIGNUM_SIGN(y)) return INT2FIX(1);
    01423     if (RBIGNUM_SIGN(x) < RBIGNUM_SIGN(y)) return INT2FIX(-1);
    01424     if (xlen < RBIGNUM_LEN(y))
    01425         return (RBIGNUM_SIGN(x)) ? INT2FIX(-1) : INT2FIX(1);
    01426     if (xlen > RBIGNUM_LEN(y))
    01427         return (RBIGNUM_SIGN(x)) ? INT2FIX(1) : INT2FIX(-1);
    01428
    01429     xds = BDIGITS(x);
    01430     yds = BDIGITS(y);
    01431
    01432     while(xlen-- && (xds[xlen]==yds[xlen]));
    01433     if (-1 == xlen) return INT2FIX(0);
    01434     return (xds[xlen] > yds[xlen]) ?
    01435         (RBIGNUM_SIGN(x) ? INT2FIX(1) : INT2FIX(-1)) :
    01436             (RBIGNUM_SIGN(x) ? INT2FIX(-1) : INT2FIX(1));
    01437 }
    01438
    01439 static VALUE
    01440 big_op(VALUE x, VALUE y, int op)
    01441 {
    01442     VALUE rel;
    01443     int n;
    01444
    01445     switch (TYPE(y)) {
    01446       case T_FIXNUM:
    01447       case T_BIGNUM:
    01448         rel = rb_big_cmp(x, y);
    01449         break;
    01450
    01451       case T_FLOAT:
    01452         {
    01453             double a = RFLOAT_VALUE(y);
    01454
    01455             if (isinf(a)) {
    01456                 if (a > 0.0) rel = INT2FIX(-1);
    01457                 else rel = INT2FIX(1);
    01458                 break;
    01459             }
    01460             rel = rb_dbl_cmp(rb_big2dbl(x), a);
    01461             break;
    01462         }
    01463
    01464       default:
    01465         {
    01466             ID id = 0;
    01467             switch (op) {
    01468                 case 0: id = '>'; break;
    01469                 case 1: id = rb_intern(">="); break;
    01470                 case 2: id = '<'; break;
    01471                 case 3: id = rb_intern("<="); break;
    01472             }
    01473             return rb_num_coerce_relop(x, y, id);
    01474         }
    01475     }
    01476
    01477     if (NIL_P(rel)) return Qfalse;
    01478     n = FIX2INT(rel);
    01479
    01480     switch (op) {
    01481         case 0: return n >  0 ? Qtrue : Qfalse;
    01482         case 1: return n >= 0 ? Qtrue : Qfalse;
    01483         case 2: return n <  0 ? Qtrue : Qfalse;
    01484         case 3: return n <= 0 ? Qtrue : Qfalse;
    01485     }
    01486     return Qundef;
    01487 }
    01488
    01489 /*
    01490  * call-seq:
    01491  *   big > real  ->  true or false
    01492  *
    01493  * Returns <code>true</code> if the value of <code>big</code> is
    01494  * greater than that of <code>real</code>.
    01495  */
    01496
    01497 static VALUE
    01498 big_gt(VALUE x, VALUE y)
    01499 {
    01500     return big_op(x, y, 0);
    01501 }
    01502
    01503 /*
    01504  * call-seq:
    01505  *   big >= real  ->  true or false
    01506  *
    01507  * Returns <code>true</code> if the value of <code>big</code> is
    01508  * greater than or equal to that of <code>real</code>.
    01509  */
    01510
    01511 static VALUE
    01512 big_ge(VALUE x, VALUE y)
    01513 {
    01514     return big_op(x, y, 1);
    01515 }
    01516
    01517 /*
    01518  * call-seq:
    01519  *   big < real  ->  true or false
    01520  *
    01521  * Returns <code>true</code> if the value of <code>big</code> is
    01522  * less than that of <code>real</code>.
    01523  */
    01524
    01525 static VALUE
    01526 big_lt(VALUE x, VALUE y)
    01527 {
    01528     return big_op(x, y, 2);
    01529 }
    01530
    01531 /*
    01532  * call-seq:
    01533  *   big <= real  ->  true or false
    01534  *
    01535  * Returns <code>true</code> if the value of <code>big</code> is
    01536  * less than or equal to that of <code>real</code>.
    01537  */
    01538
    01539 static VALUE
    01540 big_le(VALUE x, VALUE y)
    01541 {
    01542     return big_op(x, y, 3);
    01543 }
    01544
    01545 /*
    01546  *  call-seq:
    01547  *     big == obj  -> true or false
    01548  *
    01549  *  Returns <code>true</code> only if <i>obj</i> has the same value
    01550  *  as <i>big</i>. Contrast this with <code>Bignum#eql?</code>, which
    01551  *  requires <i>obj</i> to be a <code>Bignum</code>.
    01552  *
    01553  *     68719476736 == 68719476736.0   #=> true
    01554  */
    01555
    01556 VALUE
    01557 rb_big_eq(VALUE x, VALUE y)
    01558 {
    01559     switch (TYPE(y)) {
    01560       case T_FIXNUM:
    01561         y = rb_int2big(FIX2LONG(y));
    01562         break;
    01563       case T_BIGNUM:
    01564         break;
    01565       case T_FLOAT:
    01566         {
    01567             volatile double a, b;
    01568
    01569             a = RFLOAT_VALUE(y);
    01570             if (isnan(a)) return Qfalse;
    01571             b = rb_big2dbl(x);
    01572             return (a == b)?Qtrue:Qfalse;
    01573         }
    01574       default:
    01575         return rb_equal(y, x);
    01576     }
    01577     if (RBIGNUM_SIGN(x) != RBIGNUM_SIGN(y)) return Qfalse;
    01578     if (RBIGNUM_LEN(x) != RBIGNUM_LEN(y)) return Qfalse;
    01579     if (MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,RBIGNUM_LEN(y)) != 0) return Qfalse;
    01580     return Qtrue;
    01581 }
    01582
    01583 /*
    01584  *  call-seq:
    01585  *     big.eql?(obj)   -> true or false
    01586  *
    01587  *  Returns <code>true</code> only if <i>obj</i> is a
    01588  *  <code>Bignum</code> with the same value as <i>big</i>. Contrast this
    01589  *  with <code>Bignum#==</code>, which performs type conversions.
    01590  *
    01591  *     68719476736.eql?(68719476736.0)   #=> false
    01592  */
    01593
    01594 static VALUE
    01595 rb_big_eql(VALUE x, VALUE y)
    01596 {
    01597     if (TYPE(y) != T_BIGNUM) return Qfalse;
    01598     if (RBIGNUM_SIGN(x) != RBIGNUM_SIGN(y)) return Qfalse;
    01599     if (RBIGNUM_LEN(x) != RBIGNUM_LEN(y)) return Qfalse;
    01600     if (MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,RBIGNUM_LEN(y)) != 0) return Qfalse;
    01601     return Qtrue;
    01602 }
    01603
    01604 /*
    01605  * call-seq:
    01606  *    -big   ->  integer
    01607  *
    01608  * Unary minus (returns an integer whose value is 0-big)
    01609  */
    01610
    01611 static VALUE
    01612 rb_big_uminus(VALUE x)
    01613 {
    01614     VALUE z = rb_big_clone(x);
    01615
    01616     RBIGNUM_SET_SIGN(z, !RBIGNUM_SIGN(x));
    01617
    01618     return bignorm(z);
    01619 }
    01620
    01621 /*
    01622  * call-seq:
    01623  *     ~big  ->  integer
    01624  *
    01625  * Inverts the bits in big. As Bignums are conceptually infinite
    01626  * length, the result acts as if it had an infinite number of one
    01627  * bits to the left. In hex representations, this is displayed
    01628  * as two periods to the left of the digits.
    01629  *
    01630  *   sprintf("%X", ~0x1122334455)    #=> "..FEEDDCCBBAA"
    01631  */
    01632
    01633 static VALUE
    01634 rb_big_neg(VALUE x)
    01635 {
    01636     VALUE z = rb_big_clone(x);
    01637     BDIGIT *ds;
    01638     long i;
    01639
    01640     if (!RBIGNUM_SIGN(x)) get2comp(z);
    01641     ds = BDIGITS(z);
    01642     i = RBIGNUM_LEN(x);
    01643     if (!i) return INT2FIX(~(SIGNED_VALUE)0);
    01644     while (i--) {
    01645         ds[i] = ~ds[i];
    01646     }
    01647     RBIGNUM_SET_SIGN(z, !RBIGNUM_SIGN(z));
    01648     if (RBIGNUM_SIGN(x)) get2comp(z);
    01649
    01650     return bignorm(z);
    01651 }
    01652
    01653 static void
    01654 bigsub_core(BDIGIT *xds, long xn, BDIGIT *yds, long yn, BDIGIT *zds, long zn)
    01655 {
    01656     BDIGIT_DBL_SIGNED num;
    01657     long i;
    01658
    01659     for (i = 0, num = 0; i < yn; i++) {
    01660         num += (BDIGIT_DBL_SIGNED)xds[i] - yds[i];
    01661         zds[i] = BIGLO(num);
    01662         num = BIGDN(num);
    01663     }
    01664     while (num && i < xn) {
    01665         num += xds[i];
    01666         zds[i++] = BIGLO(num);
    01667         num = BIGDN(num);
    01668     }
    01669     while (i < xn) {
    01670         zds[i] = xds[i];
    01671         i++;
    01672     }
    01673     assert(i <= zn);
    01674     while (i < zn) {
    01675         zds[i++] = 0;
    01676     }
    01677 }
    01678
    01679 static VALUE
    01680 bigsub(VALUE x, VALUE y)
    01681 {
    01682     VALUE z = 0;
    01683     long i = RBIGNUM_LEN(x);
    01684     BDIGIT *xds, *yds;
    01685
    01686     /* if x is larger than y, swap */
    01687     if (RBIGNUM_LEN(x) < RBIGNUM_LEN(y)) {
    01688         z = x; x = y; y = z;    /* swap x y */
    01689     }
    01690     else if (RBIGNUM_LEN(x) == RBIGNUM_LEN(y)) {
    01691         xds = BDIGITS(x);
    01692         yds = BDIGITS(y);
    01693         while (i > 0) {
    01694             i--;
    01695             if (xds[i] > yds[i]) {
    01696                 break;
    01697             }
    01698             if (xds[i] < yds[i]) {
    01699                 z = x; x = y; y = z;    /* swap x y */
    01700                 break;
    01701             }
    01702         }
    01703     }
    01704
    01705     z = bignew(RBIGNUM_LEN(x), z==0);
    01706     bigsub_core(BDIGITS(x), RBIGNUM_LEN(x),
    01707                 BDIGITS(y), RBIGNUM_LEN(y),
    01708                 BDIGITS(z), RBIGNUM_LEN(z));
    01709
    01710     return z;
    01711 }
    01712
    01713 static VALUE bigadd_int(VALUE x, long y);
    01714
    01715 static VALUE
    01716 bigsub_int(VALUE x, long y0)
    01717 {
    01718     VALUE z;
    01719     BDIGIT *xds, *zds;
    01720     long xn;
    01721     BDIGIT_DBL_SIGNED num;
    01722     long i, y;
    01723
    01724     y = y0;
    01725     xds = BDIGITS(x);
    01726     xn = RBIGNUM_LEN(x);
    01727
    01728     z = bignew(xn, RBIGNUM_SIGN(x));
    01729     zds = BDIGITS(z);
    01730
    01731 #if SIZEOF_BDIGITS == SIZEOF_LONG
    01732     num = (BDIGIT_DBL_SIGNED)xds[0] - y;
    01733     if (xn == 1 && num < 0) {
    01734         RBIGNUM_SET_SIGN(z, !RBIGNUM_SIGN(x));
    01735         zds[0] = (BDIGIT)-num;
    01736         return bignorm(z);
    01737     }
    01738     zds[0] = BIGLO(num);
    01739     num = BIGDN(num);
    01740     i = 1;
    01741 #else
    01742     num = 0;
    01743     for (i=0; i<(int)(sizeof(y)/sizeof(BDIGIT)); i++) {
    01744         num += (BDIGIT_DBL_SIGNED)xds[i] - BIGLO(y);
    01745         zds[i] = BIGLO(num);
    01746         num = BIGDN(num);
    01747         y = BIGDN(y);
    01748     }
    01749 #endif
    01750     while (num && i < xn) {
    01751         num += xds[i];
    01752         zds[i++] = BIGLO(num);
    01753         num = BIGDN(num);
    01754     }
    01755     while (i < xn) {
    01756         zds[i] = xds[i];
    01757         i++;
    01758     }
    01759     if (num < 0) {
    01760         z = bigsub(x, rb_int2big(y0));
    01761     }
    01762     return bignorm(z);
    01763 }
    01764
    01765 static VALUE
    01766 bigadd_int(VALUE x, long y)
    01767 {
    01768     VALUE z;
    01769     BDIGIT *xds, *zds;
    01770     long xn, zn;
    01771     BDIGIT_DBL num;
    01772     long i;
    01773
    01774     xds = BDIGITS(x);
    01775     xn = RBIGNUM_LEN(x);
    01776
    01777     if (xn < 2) {
    01778         zn = 3;
    01779     }
    01780     else {
    01781         zn = xn + 1;
    01782     }
    01783     z = bignew(zn, RBIGNUM_SIGN(x));
    01784     zds = BDIGITS(z);
    01785
    01786 #if SIZEOF_BDIGITS == SIZEOF_LONG
    01787     num = (BDIGIT_DBL)xds[0] + y;
    01788     zds[0] = BIGLO(num);
    01789     num = BIGDN(num);
    01790     i = 1;
    01791 #else
    01792     num = 0;
    01793     for (i=0; i<(int)(sizeof(y)/sizeof(BDIGIT)); i++) {
    01794         num += (BDIGIT_DBL)xds[i] + BIGLO(y);
    01795         zds[i] = BIGLO(num);
    01796         num = BIGDN(num);
    01797         y = BIGDN(y);
    01798     }
    01799 #endif
    01800     while (num && i < xn) {
    01801         num += xds[i];
    01802         zds[i++] = BIGLO(num);
    01803         num = BIGDN(num);
    01804     }
    01805     if (num) zds[i++] = (BDIGIT)num;
    01806     else while (i < xn) {
    01807         zds[i] = xds[i];
    01808         i++;
    01809     }
    01810     assert(i <= zn);
    01811     while (i < zn) {
    01812         zds[i++] = 0;
    01813     }
    01814     return bignorm(z);
    01815 }
    01816
    01817 static void
    01818 bigadd_core(BDIGIT *xds, long xn, BDIGIT *yds, long yn, BDIGIT *zds, long zn)
    01819 {
    01820     BDIGIT_DBL num = 0;
    01821     long i;
    01822
    01823     if (xn > yn) {
    01824         BDIGIT *tds;
    01825         tds = xds; xds = yds; yds = tds;
    01826         i = xn; xn = yn; yn = i;
    01827     }
    01828
    01829     i = 0;
    01830     while (i < xn) {
    01831         num += (BDIGIT_DBL)xds[i] + yds[i];
    01832         zds[i++] = BIGLO(num);
    01833         num = BIGDN(num);
    01834     }
    01835     while (num && i < yn) {
    01836         num += yds[i];
    01837         zds[i++] = BIGLO(num);
    01838         num = BIGDN(num);
    01839     }
    01840     while (i < yn) {
    01841         zds[i] = yds[i];
    01842         i++;
    01843     }
    01844     if (num) zds[i++] = (BDIGIT)num;
    01845     assert(i <= zn);
    01846     while (i < zn) {
    01847         zds[i++] = 0;
    01848     }
    01849 }
    01850
    01851 static VALUE
    01852 bigadd(VALUE x, VALUE y, int sign)
    01853 {
    01854     VALUE z;
    01855     long len;
    01856
    01857     sign = (sign == RBIGNUM_SIGN(y));
    01858     if (RBIGNUM_SIGN(x) != sign) {
    01859         if (sign) return bigsub(y, x);
    01860         return bigsub(x, y);
    01861     }
    01862
    01863     if (RBIGNUM_LEN(x) > RBIGNUM_LEN(y)) {
    01864         len = RBIGNUM_LEN(x) + 1;
    01865     }
    01866     else {
    01867         len = RBIGNUM_LEN(y) + 1;
    01868     }
    01869     z = bignew(len, sign);
    01870
    01871     bigadd_core(BDIGITS(x), RBIGNUM_LEN(x),
    01872                 BDIGITS(y), RBIGNUM_LEN(y),
    01873                 BDIGITS(z), RBIGNUM_LEN(z));
    01874
    01875     return z;
    01876 }
    01877
    01878 /*
    01879  *  call-seq:
    01880  *     big + other  -> Numeric
    01881  *
    01882  *  Adds big and other, returning the result.
    01883  */
    01884
    01885 VALUE
    01886 rb_big_plus(VALUE x, VALUE y)
    01887 {
    01888     long n;
    01889
    01890     switch (TYPE(y)) {
    01891       case T_FIXNUM:
    01892         n = FIX2LONG(y);
    01893         if ((n > 0) != RBIGNUM_SIGN(x)) {
    01894             if (n < 0) {
    01895                 n = -n;
    01896             }
    01897             return bigsub_int(x, n);
    01898         }
    01899         if (n < 0) {
    01900             n = -n;
    01901         }
    01902         return bigadd_int(x, n);
    01903
    01904       case T_BIGNUM:
    01905         return bignorm(bigadd(x, y, 1));
    01906
    01907       case T_FLOAT:
    01908         return DBL2NUM(rb_big2dbl(x) + RFLOAT_VALUE(y));
    01909
    01910       default:
    01911         return rb_num_coerce_bin(x, y, '+');
    01912     }
    01913 }
    01914
    01915 /*
    01916  *  call-seq:
    01917  *     big - other  -> Numeric
    01918  *
    01919  *  Subtracts other from big, returning the result.
    01920  */
    01921
    01922 VALUE
    01923 rb_big_minus(VALUE x, VALUE y)
    01924 {
    01925     long n;
    01926
    01927     switch (TYPE(y)) {
    01928       case T_FIXNUM:
    01929         n = FIX2LONG(y);
    01930         if ((n > 0) != RBIGNUM_SIGN(x)) {
    01931             if (n < 0) {
    01932                 n = -n;
    01933             }
    01934             return bigadd_int(x, n);
    01935         }
    01936         if (n < 0) {
    01937             n = -n;
    01938         }
    01939         return bigsub_int(x, n);
    01940
    01941       case T_BIGNUM:
    01942         return bignorm(bigadd(x, y, 0));
    01943
    01944       case T_FLOAT:
    01945         return DBL2NUM(rb_big2dbl(x) - RFLOAT_VALUE(y));
    01946
    01947       default:
    01948         return rb_num_coerce_bin(x, y, '-');
    01949     }
    01950 }
    01951
    01952 static long
    01953 big_real_len(VALUE x)
    01954 {
    01955     long i = RBIGNUM_LEN(x);
    01956     BDIGIT *xds = BDIGITS(x);
    01957     while (--i && !xds[i]);
    01958     return i + 1;
    01959 }
    01960
    01961 static VALUE
    01962 bigmul1_single(VALUE x, VALUE y)
    01963 {
    01964     BDIGIT_DBL n;
    01965     VALUE z = bignew(2, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
    01966     BDIGIT *xds, *yds, *zds;
    01967
    01968     xds = BDIGITS(x);
    01969     yds = BDIGITS(y);
    01970     zds = BDIGITS(z);
    01971
    01972     n = (BDIGIT_DBL)xds[0] * yds[0];
    01973     zds[0] = BIGLO(n);
    01974     zds[1] = (BDIGIT)BIGDN(n);
    01975
    01976     return z;
    01977 }
    01978
    01979 static VALUE
    01980 bigmul1_normal(VALUE x, VALUE y)
    01981 {
    01982     long xl = RBIGNUM_LEN(x), yl = RBIGNUM_LEN(y), i, j = xl + yl + 1;
    01983     BDIGIT_DBL n = 0;
    01984     VALUE z = bignew(j, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
    01985     BDIGIT *xds, *yds, *zds;
    01986
    01987     xds = BDIGITS(x);
    01988     yds = BDIGITS(y);
    01989     zds = BDIGITS(z);
    01990     while (j--) zds[j] = 0;
    01991     for (i = 0; i < xl; i++) {
    01992         BDIGIT_DBL dd;
    01993         dd = xds[i];
    01994         if (dd == 0) continue;
    01995         n = 0;
    01996         for (j = 0; j < yl; j++) {
    01997             BDIGIT_DBL ee = n + (BDIGIT_DBL)dd * yds[j];
    01998             n = zds[i + j] + ee;
    01999             if (ee) zds[i + j] = BIGLO(n);
    02000             n = BIGDN(n);
    02001         }
    02002         if (n) {
    02003             zds[i + j] = (BDIGIT)n;
    02004         }
    02005     }
    02006     rb_thread_check_ints();
    02007     return z;
    02008 }
    02009
    02010 static VALUE bigmul0(VALUE x, VALUE y);
    02011
    02012 /* balancing multiplication by slicing larger argument */
    02013 static VALUE
    02014 bigmul1_balance(VALUE x, VALUE y)
    02015 {
    02016     VALUE z, t1, t2;
    02017     long i, xn, yn, r, n;
    02018     BDIGIT *yds, *zds, *t1ds;
    02019
    02020     xn = RBIGNUM_LEN(x);
    02021     yn = RBIGNUM_LEN(y);
    02022     assert(2 * xn <= yn);
    02023
    02024     z = bignew(xn + yn, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
    02025     t1 = bignew(xn, 1);
    02026
    02027     yds = BDIGITS(y);
    02028     zds = BDIGITS(z);
    02029     t1ds = BDIGITS(t1);
    02030
    02031     for (i = 0; i < xn + yn; i++) zds[i] = 0;
    02032
    02033     n = 0;
    02034     while (yn > 0) {
    02035         r = xn > yn ? yn : xn;
    02036         MEMCPY(t1ds, yds + n, BDIGIT, r);
    02037         RBIGNUM_SET_LEN(t1, r);
    02038         t2 = bigmul0(x, t1);
    02039         bigadd_core(zds + n, RBIGNUM_LEN(z) - n,
    02040                     BDIGITS(t2), big_real_len(t2),
    02041                     zds + n, RBIGNUM_LEN(z) - n);
    02042         yn -= r;
    02043         n += r;
    02044     }
    02045
    02046     return z;
    02047 }
    02048
    02049 /* split a bignum into high and low bignums */
    02050 static void
    02051 big_split(VALUE v, long n, volatile VALUE *ph, volatile VALUE *pl)
    02052 {
    02053     long hn = 0, ln = RBIGNUM_LEN(v);
    02054     VALUE h, l;
    02055     BDIGIT *vds = BDIGITS(v);
    02056
    02057     if (ln > n) {
    02058         hn = ln - n;
    02059         ln = n;
    02060     }
    02061
    02062     while (--hn && !vds[hn + ln]);
    02063     h = bignew(hn += 2, 1);
    02064     MEMCPY(BDIGITS(h), vds + ln, BDIGIT, hn - 1);
    02065     BDIGITS(h)[hn - 1] = 0; /* margin for carry */
    02066
    02067     while (--ln && !vds[ln]);
    02068     l = bignew(ln += 2, 1);
    02069     MEMCPY(BDIGITS(l), vds, BDIGIT, ln - 1);
    02070     BDIGITS(l)[ln - 1] = 0; /* margin for carry */
    02071
    02072     *pl = l;
    02073     *ph = h;
    02074 }
    02075
    02076 /* multiplication by karatsuba method */
    02077 static VALUE
    02078 bigmul1_karatsuba(VALUE x, VALUE y)
    02079 {
    02080     long i, n, xn, yn, t1n, t2n;
    02081     VALUE xh, xl, yh, yl, z, t1, t2, t3;
    02082     BDIGIT *zds;
    02083
    02084     xn = RBIGNUM_LEN(x);
    02085     yn = RBIGNUM_LEN(y);
    02086     n = yn / 2;
    02087     big_split(x, n, &xh, &xl);
    02088     if (x == y) {
    02089         yh = xh; yl = xl;
    02090     }
    02091     else big_split(y, n, &yh, &yl);
    02092
    02093     /* x = xh * b + xl
    02094      * y = yh * b + yl
    02095      *
    02096      * Karatsuba method:
    02097      *   x * y = z2 * b^2 + z1 * b + z0
    02098      *   where
    02099      *     z2 = xh * yh
    02100      *     z0 = xl * yl
    02101      *     z1 = (xh + xl) * (yh + yl) - z2 - z0
    02102      *
    02103      *  ref: http://en.wikipedia.org/wiki/Karatsuba_algorithm
    02104      */
    02105
    02106     /* allocate a result bignum */
    02107     z = bignew(xn + yn, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
    02108     zds = BDIGITS(z);
    02109
    02110     /* t1 <- xh * yh */
    02111     t1 = bigmul0(xh, yh);
    02112     t1n = big_real_len(t1);
    02113
    02114     /* copy t1 into high bytes of the result (z2) */
    02115     MEMCPY(zds + 2 * n, BDIGITS(t1), BDIGIT, t1n);
    02116     for (i = 2 * n + t1n; i < xn + yn; i++) zds[i] = 0;
    02117
    02118     if (!BIGZEROP(xl) && !BIGZEROP(yl)) {
    02119         /* t2 <- xl * yl */
    02120         t2 = bigmul0(xl, yl);
    02121         t2n = big_real_len(t2);
    02122
    02123         /* copy t2 into low bytes of the result (z0) */
    02124         MEMCPY(zds, BDIGITS(t2), BDIGIT, t2n);
    02125         for (i = t2n; i < 2 * n; i++) zds[i] = 0;
    02126     }
    02127     else {
    02128         t2 = Qundef;
    02129         t2n = 0;
    02130
    02131         /* copy 0 into low bytes of the result (z0) */
    02132         for (i = 0; i < 2 * n; i++) zds[i] = 0;
    02133     }
    02134
    02135     /* xh <- xh + xl */
    02136     if (RBIGNUM_LEN(xl) > RBIGNUM_LEN(xh)) {
    02137         t3 = xl; xl = xh; xh = t3;
    02138     }
    02139     /* xh has a margin for carry */
    02140     bigadd_core(BDIGITS(xh), RBIGNUM_LEN(xh),
    02141                 BDIGITS(xl), RBIGNUM_LEN(xl),
    02142                 BDIGITS(xh), RBIGNUM_LEN(xh));
    02143
    02144     /* yh <- yh + yl */
    02145     if (x != y) {
    02146         if (RBIGNUM_LEN(yl) > RBIGNUM_LEN(yh)) {
    02147             t3 = yl; yl = yh; yh = t3;
    02148         }
    02149         /* yh has a margin for carry */
    02150         bigadd_core(BDIGITS(yh), RBIGNUM_LEN(yh),
    02151                     BDIGITS(yl), RBIGNUM_LEN(yl),
    02152                     BDIGITS(yh), RBIGNUM_LEN(yh));
    02153     }
    02154     else yh = xh;
    02155
    02156     /* t3 <- xh * yh */
    02157     t3 = bigmul0(xh, yh);
    02158
    02159     i = xn + yn - n;
    02160     /* add t3 to middle bytes of the result (z1) */
    02161     bigadd_core(zds + n, i, BDIGITS(t3), big_real_len(t3), zds + n, i);
    02162
    02163     /* subtract t1 from middle bytes of the result (z1) */
    02164     bigsub_core(zds + n, i, BDIGITS(t1), t1n, zds + n, i);
    02165
    02166     /* subtract t2 from middle bytes of the result (z1) */
    02167     if (t2 != Qundef) bigsub_core(zds + n, i, BDIGITS(t2), t2n, zds + n, i);
    02168
    02169     return z;
    02170 }
    02171
    02172 /* efficient squaring (2 times faster than normal multiplication)
    02173  * ref: Handbook of Applied Cryptography, Algorithm 14.16
    02174  *      http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
    02175  */
    02176 static VALUE
    02177 bigsqr_fast(VALUE x)
    02178 {
    02179     long len = RBIGNUM_LEN(x), i, j;
    02180     VALUE z = bignew(2 * len + 1, 1);
    02181     BDIGIT *xds = BDIGITS(x), *zds = BDIGITS(z);
    02182     BDIGIT_DBL c, v, w;
    02183
    02184     for (i = 2 * len + 1; i--; ) zds[i] = 0;
    02185     for (i = 0; i < len; i++) {
    02186         v = (BDIGIT_DBL)xds[i];
    02187         if (!v) continue;
    02188         c = (BDIGIT_DBL)zds[i + i] + v * v;
    02189         zds[i + i] = BIGLO(c);
    02190         c = BIGDN(c);
    02191         v *= 2;
    02192         for (j = i + 1; j < len; j++) {
    02193             w = (BDIGIT_DBL)xds[j];
    02194             c += (BDIGIT_DBL)zds[i + j] + BIGLO(v) * w;
    02195             zds[i + j] = BIGLO(c);
    02196             c = BIGDN(c);
    02197             if (BIGDN(v)) c += w;
    02198         }
    02199         if (c) {
    02200             c += (BDIGIT_DBL)zds[i + len];
    02201             zds[i + len] = BIGLO(c);
    02202             c = BIGDN(c);
    02203         }
    02204         if (c) zds[i + len + 1] += (BDIGIT)c;
    02205     }
    02206     return z;
    02207 }
    02208
    02209 #define KARATSUBA_MUL_DIGITS 70
    02210
    02211
    02212 /* determine whether a bignum is sparse or not by random sampling */
    02213 static inline VALUE
    02214 big_sparse_p(VALUE x)
    02215 {
    02216     long c = 0, n = RBIGNUM_LEN(x);
    02217     unsigned long rb_rand_internal(unsigned long i);
    02218
    02219     if (          BDIGITS(x)[rb_rand_internal(n / 2) + n / 4]) c++;
    02220     if (c <= 1 && BDIGITS(x)[rb_rand_internal(n / 2) + n / 4]) c++;
    02221     if (c <= 1 && BDIGITS(x)[rb_rand_internal(n / 2) + n / 4]) c++;
    02222
    02223     return (c <= 1) ? Qtrue : Qfalse;
    02224 }
    02225
    02226 #if 0
    02227 static void
    02228 dump_bignum(VALUE x)
    02229 {
    02230     long i;
    02231     printf("0x0");
    02232     for (i = RBIGNUM_LEN(x); i--; ) {
    02233         printf("_%08x", BDIGITS(x)[i]);
    02234     }
    02235     puts("");
    02236 }
    02237 #endif
    02238
    02239 static VALUE
    02240 bigmul0(VALUE x, VALUE y)
    02241 {
    02242     long xn, yn;
    02243
    02244     xn = RBIGNUM_LEN(x);
    02245     yn = RBIGNUM_LEN(y);
    02246
    02247     /* make sure that y is longer than x */
    02248     if (xn > yn) {
    02249         VALUE t;
    02250         long tn;
    02251         t = x; x = y; y = t;
    02252         tn = xn; xn = yn; yn = tn;
    02253     }
    02254     assert(xn <= yn);
    02255
    02256     /* normal multiplication when x is small */
    02257     if (xn < KARATSUBA_MUL_DIGITS) {
    02258       normal:
    02259         if (x == y) return bigsqr_fast(x);
    02260         if (xn == 1 && yn == 1) return bigmul1_single(x, y);
    02261         return bigmul1_normal(x, y);
    02262     }
    02263
    02264     /* normal multiplication when x or y is a sparse bignum */
    02265     if (big_sparse_p(x)) goto normal;
    02266     if (big_sparse_p(y)) return bigmul1_normal(y, x);
    02267
    02268     /* balance multiplication by slicing y when x is much smaller than y */
    02269     if (2 * xn <= yn) return bigmul1_balance(x, y);
    02270
    02271     /* multiplication by karatsuba method */
    02272     return bigmul1_karatsuba(x, y);
    02273 }
    02274
    02275 /*
    02276  *  call-seq:
    02277  *     big * other  -> Numeric
    02278  *
    02279  *  Multiplies big and other, returning the result.
    02280  */
    02281
    02282 VALUE
    02283 rb_big_mul(VALUE x, VALUE y)
    02284 {
    02285     switch (TYPE(y)) {
    02286       case T_FIXNUM:
    02287         y = rb_int2big(FIX2LONG(y));
    02288         break;
    02289
    02290       case T_BIGNUM:
    02291         break;
    02292
    02293       case T_FLOAT:
    02294         return DBL2NUM(rb_big2dbl(x) * RFLOAT_VALUE(y));
    02295
    02296       default:
    02297         return rb_num_coerce_bin(x, y, '*');
    02298     }
    02299
    02300     return bignorm(bigmul0(x, y));
    02301 }
    02302
    02303 struct big_div_struct {
    02304     long nx, ny;
    02305     BDIGIT *yds, *zds;
    02306     VALUE stop;
    02307 };
    02308
    02309 static VALUE
    02310 bigdivrem1(void *ptr)
    02311 {
    02312     struct big_div_struct *bds = (struct big_div_struct*)ptr;
    02313     long nx = bds->nx, ny = bds->ny;
    02314     long i, j, nyzero;
    02315     BDIGIT *yds = bds->yds, *zds = bds->zds;
    02316     BDIGIT_DBL t2;
    02317     BDIGIT_DBL_SIGNED num;
    02318     BDIGIT q;
    02319
    02320     j = nx==ny?nx+1:nx;
    02321     for (nyzero = 0; !yds[nyzero]; nyzero++);
    02322     do {
    02323         if (bds->stop) return Qnil;
    02324         if (zds[j] ==  yds[ny-1]) q = (BDIGIT)BIGRAD-1;
    02325         else q = (BDIGIT)((BIGUP(zds[j]) + zds[j-1])/yds[ny-1]);
    02326         if (q) {
    02327            i = nyzero; num = 0; t2 = 0;
    02328             do {                        /* multiply and subtract */
    02329                 BDIGIT_DBL ee;
    02330                 t2 += (BDIGIT_DBL)yds[i] * q;
    02331                 ee = num - BIGLO(t2);
    02332                 num = (BDIGIT_DBL)zds[j - ny + i] + ee;
    02333                 if (ee) zds[j - ny + i] = BIGLO(num);
    02334                 num = BIGDN(num);
    02335                 t2 = BIGDN(t2);
    02336             } while (++i < ny);
    02337             num += zds[j - ny + i] - t2;/* borrow from high digit; don't update */
    02338             while (num) {               /* "add back" required */
    02339                 i = 0; num = 0; q--;
    02340                 do {
    02341                     BDIGIT_DBL ee = num + yds[i];
    02342                     num = (BDIGIT_DBL)zds[j - ny + i] + ee;
    02343                     if (ee) zds[j - ny + i] = BIGLO(num);
    02344                     num = BIGDN(num);
    02345                 } while (++i < ny);
    02346                 num--;
    02347             }
    02348         }
    02349         zds[j] = q;
    02350     } while (--j >= ny);
    02351     return Qnil;
    02352 }
    02353
    02354 static void
    02355 rb_big_stop(void *ptr)
    02356 {
    02357     VALUE *stop = (VALUE*)ptr;
    02358     *stop = Qtrue;
    02359 }
    02360
    02361 static VALUE
    02362 bigdivrem(VALUE x, VALUE y, volatile VALUE *divp, volatile VALUE *modp)
    02363 {
    02364     struct big_div_struct bds;
    02365     long nx = RBIGNUM_LEN(x), ny = RBIGNUM_LEN(y);
    02366     long i, j;
    02367     VALUE z, yy, zz;
    02368     BDIGIT *xds, *yds, *zds, *tds;
    02369     BDIGIT_DBL t2;
    02370     BDIGIT dd, q;
    02371
    02372     if (BIGZEROP(y)) rb_num_zerodiv();
    02373     xds = BDIGITS(x);
    02374     yds = BDIGITS(y);
    02375     if (nx < ny || (nx == ny && xds[nx - 1] < yds[ny - 1])) {
    02376         if (divp) *divp = rb_int2big(0);
    02377         if (modp) *modp = x;
    02378         return Qnil;
    02379     }
    02380     if (ny == 1) {
    02381         dd = yds[0];
    02382         z = rb_big_clone(x);
    02383         zds = BDIGITS(z);
    02384         t2 = 0; i = nx;
    02385         while (i--) {
    02386             t2 = BIGUP(t2) + zds[i];
    02387             zds[i] = (BDIGIT)(t2 / dd);
    02388             t2 %= dd;
    02389         }
    02390         RBIGNUM_SET_SIGN(z, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
    02391         if (modp) {
    02392             *modp = rb_uint2big((VALUE)t2);
    02393             RBIGNUM_SET_SIGN(*modp, RBIGNUM_SIGN(x));
    02394         }
    02395         if (divp) *divp = z;
    02396         return Qnil;
    02397     }
    02398     z = bignew(nx==ny?nx+2:nx+1, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
    02399     zds = BDIGITS(z);
    02400     if (nx==ny) zds[nx+1] = 0;
    02401     while (!yds[ny-1]) ny--;
    02402
    02403     dd = 0;
    02404     q = yds[ny-1];
    02405     while ((q & (BDIGIT)(1UL<<(BITSPERDIG-1))) == 0) {
    02406         q <<= 1UL;
    02407         dd++;
    02408     }
    02409     if (dd) {
    02410         yy = rb_big_clone(y);
    02411         tds = BDIGITS(yy);
    02412         j = 0;
    02413         t2 = 0;
    02414         while (j<ny) {
    02415             t2 += (BDIGIT_DBL)yds[j]<<dd;
    02416             tds[j++] = BIGLO(t2);
    02417             t2 = BIGDN(t2);
    02418         }
    02419         yds = tds;
    02420         RB_GC_GUARD(y) = yy;
    02421         j = 0;
    02422         t2 = 0;
    02423         while (j<nx) {
    02424             t2 += (BDIGIT_DBL)xds[j]<<dd;
    02425             zds[j++] = BIGLO(t2);
    02426             t2 = BIGDN(t2);
    02427         }
    02428         zds[j] = (BDIGIT)t2;
    02429     }
    02430     else {
    02431         zds[nx] = 0;
    02432         j = nx;
    02433         while (j--) zds[j] = xds[j];
    02434     }
    02435
    02436     bds.nx = nx;
    02437     bds.ny = ny;
    02438     bds.zds = zds;
    02439     bds.yds = yds;
    02440     bds.stop = Qfalse;
    02441     if (nx > 10000 || ny > 10000) {
    02442         rb_thread_blocking_region(bigdivrem1, &bds, rb_big_stop, &bds.stop);
    02443     }
    02444     else {
    02445         bigdivrem1(&bds);
    02446     }
    02447
    02448     if (divp) {                 /* move quotient down in z */
    02449         *divp = zz = rb_big_clone(z);
    02450         zds = BDIGITS(zz);
    02451         j = (nx==ny ? nx+2 : nx+1) - ny;
    02452         for (i = 0;i < j;i++) zds[i] = zds[i+ny];
    02453         if (!zds[i-1]) i--;
    02454         RBIGNUM_SET_LEN(zz, i);
    02455     }
    02456     if (modp) {                 /* normalize remainder */
    02457         *modp = zz = rb_big_clone(z);
    02458         zds = BDIGITS(zz);
    02459         while (--ny && !zds[ny]); ++ny;
    02460         if (dd) {
    02461             t2 = 0; i = ny;
    02462             while(i--) {
    02463                 t2 = (t2 | zds[i]) >> dd;
    02464                 q = zds[i];
    02465                 zds[i] = BIGLO(t2);
    02466                 t2 = BIGUP(q);
    02467             }
    02468         }
    02469         if (!zds[ny-1]) ny--;
    02470         RBIGNUM_SET_LEN(zz, ny);
    02471         RBIGNUM_SET_SIGN(zz, RBIGNUM_SIGN(x));
    02472     }
    02473     return z;
    02474 }
    02475
    02476 static void
    02477 bigdivmod(VALUE x, VALUE y, volatile VALUE *divp, volatile VALUE *modp)
    02478 {
    02479     VALUE mod;
    02480
    02481     bigdivrem(x, y, divp, &mod);
    02482     if (RBIGNUM_SIGN(x) != RBIGNUM_SIGN(y) && !BIGZEROP(mod)) {
    02483         if (divp) *divp = bigadd(*divp, rb_int2big(1), 0);
    02484         if (modp) *modp = bigadd(mod, y, 1);
    02485     }
    02486     else if (modp) {
    02487         *modp = mod;
    02488     }
    02489 }
    02490
    02491
    02492 static VALUE
    02493 rb_big_divide(VALUE x, VALUE y, ID op)
    02494 {
    02495     VALUE z;
    02496
    02497     switch (TYPE(y)) {
    02498       case T_FIXNUM:
    02499         y = rb_int2big(FIX2LONG(y));
    02500         break;
    02501
    02502       case T_BIGNUM:
    02503         break;
    02504
    02505       case T_FLOAT:
    02506         {
    02507             double div = rb_big2dbl(x) / RFLOAT_VALUE(y);
    02508             if (op == '/') {
    02509                 return DBL2NUM(div);
    02510             }
    02511             else {
    02512                 return rb_dbl2big(div);
    02513             }
    02514         }
    02515
    02516       default:
    02517         return rb_num_coerce_bin(x, y, op);
    02518     }
    02519     bigdivmod(x, y, &z, 0);
    02520
    02521     return bignorm(z);
    02522 }
    02523
    02524 /*
    02525  *  call-seq:
    02526  *     big / other     -> Numeric
    02527  *
    02528  * Performs division: the class of the resulting object depends on
    02529  * the class of <code>numeric</code> and on the magnitude of the
    02530  * result.
    02531  */
    02532
    02533 VALUE
    02534 rb_big_div(VALUE x, VALUE y)
    02535 {
    02536     return rb_big_divide(x, y, '/');
    02537 }
    02538
    02539 /*
    02540  *  call-seq:
    02541  *     big.div(other)  -> integer
    02542  *
    02543  * Performs integer division: returns integer value.
    02544  */
    02545
    02546 VALUE
    02547 rb_big_idiv(VALUE x, VALUE y)
    02548 {
    02549     return rb_big_divide(x, y, rb_intern("div"));
    02550 }
    02551
    02552 /*
    02553  *  call-seq:
    02554  *     big % other         -> Numeric
    02555  *     big.modulo(other)   -> Numeric
    02556  *
    02557  *  Returns big modulo other. See Numeric.divmod for more
    02558  *  information.
    02559  */
    02560
    02561 VALUE
    02562 rb_big_modulo(VALUE x, VALUE y)
    02563 {
    02564     VALUE z;
    02565
    02566     switch (TYPE(y)) {
    02567       case T_FIXNUM:
    02568         y = rb_int2big(FIX2LONG(y));
    02569         break;
    02570
    02571       case T_BIGNUM:
    02572         break;
    02573
    02574       default:
    02575         return rb_num_coerce_bin(x, y, '%');
    02576     }
    02577     bigdivmod(x, y, 0, &z);
    02578
    02579     return bignorm(z);
    02580 }
    02581
    02582 /*
    02583  *  call-seq:
    02584  *     big.remainder(numeric)    -> number
    02585  *
    02586  *  Returns the remainder after dividing <i>big</i> by <i>numeric</i>.
    02587  *
    02588  *     -1234567890987654321.remainder(13731)      #=> -6966
    02589  *     -1234567890987654321.remainder(13731.24)   #=> -9906.22531493148
    02590  */
    02591 static VALUE
    02592 rb_big_remainder(VALUE x, VALUE y)
    02593 {
    02594     VALUE z;
    02595
    02596     switch (TYPE(y)) {
    02597       case T_FIXNUM:
    02598         y = rb_int2big(FIX2LONG(y));
    02599         break;
    02600
    02601       case T_BIGNUM:
    02602         break;
    02603
    02604       default:
    02605         return rb_num_coerce_bin(x, y, rb_intern("remainder"));
    02606     }
    02607     bigdivrem(x, y, 0, &z);
    02608
    02609     return bignorm(z);
    02610 }
    02611
    02612 /*
    02613  *  call-seq:
    02614  *     big.divmod(numeric)   -> array
    02615  *
    02616  *  See <code>Numeric#divmod</code>.
    02617  *
    02618  */
    02619 VALUE
    02620 rb_big_divmod(VALUE x, VALUE y)
    02621 {
    02622     VALUE div, mod;
    02623
    02624     switch (TYPE(y)) {
    02625       case T_FIXNUM:
    02626         y = rb_int2big(FIX2LONG(y));
    02627         break;
    02628
    02629       case T_BIGNUM:
    02630         break;
    02631
    02632       default:
    02633         return rb_num_coerce_bin(x, y, rb_intern("divmod"));
    02634     }
    02635     bigdivmod(x, y, &div, &mod);
    02636
    02637     return rb_assoc_new(bignorm(div), bignorm(mod));
    02638 }
    02639
    02640 static int
    02641 bdigbitsize(BDIGIT x)
    02642 {
    02643     int size = 1;
    02644     int nb = BITSPERDIG / 2;
    02645     BDIGIT bits = (~0 << nb);
    02646
    02647     if (!x) return 0;
    02648     while (x > 1) {
    02649         if (x & bits) {
    02650             size += nb;
    02651             x >>= nb;
    02652         }
    02653         x &= ~bits;
    02654         nb /= 2;
    02655         bits >>= nb;
    02656     }
    02657
    02658     return size;
    02659 }
    02660
    02661 static VALUE big_lshift(VALUE, unsigned long);
    02662 static VALUE big_rshift(VALUE, unsigned long);
    02663
    02664 static VALUE
    02665 big_shift(VALUE x, long n)
    02666 {
    02667     if (n < 0)
    02668         return big_lshift(x, (unsigned long)-n);
    02669     else if (n > 0)
    02670         return big_rshift(x, (unsigned long)n);
    02671     return x;
    02672 }
    02673
    02674 static VALUE
    02675 big_fdiv(VALUE x, VALUE y)
    02676 {
    02677 #define DBL_BIGDIG ((DBL_MANT_DIG + BITSPERDIG) / BITSPERDIG)
    02678     VALUE z;
    02679     long l, ex, ey;
    02680     int i;
    02681
    02682     bigtrunc(x);
    02683     l = RBIGNUM_LEN(x) - 1;
    02684     ex = l * BITSPERDIG;
    02685     ex += bdigbitsize(BDIGITS(x)[l]);
    02686     ex -= 2 * DBL_BIGDIG * BITSPERDIG;
    02687     if (ex) x = big_shift(x, ex);
    02688
    02689     switch (TYPE(y)) {
    02690       case T_FIXNUM:
    02691         y = rb_int2big(FIX2LONG(y));
    02692       case T_BIGNUM: {
    02693         bigtrunc(y);
    02694         l = RBIGNUM_LEN(y) - 1;
    02695         ey = l * BITSPERDIG;
    02696         ey += bdigbitsize(BDIGITS(y)[l]);
    02697         ey -= DBL_BIGDIG * BITSPERDIG;
    02698         if (ey) y = big_shift(y, ey);
    02699       bignum:
    02700         bigdivrem(x, y, &z, 0);
    02701         l = ex - ey;
    02702 #if SIZEOF_LONG > SIZEOF_INT
    02703         {
    02704             /* Visual C++ can't be here */
    02705             if (l > INT_MAX) return DBL2NUM(INFINITY);
    02706             if (l < INT_MIN) return DBL2NUM(0.0);
    02707         }
    02708 #endif
    02709         return DBL2NUM(ldexp(big2dbl(z), (int)l));
    02710       }
    02711       case T_FLOAT:
    02712         y = dbl2big(ldexp(frexp(RFLOAT_VALUE(y), &i), DBL_MANT_DIG));
    02713         ey = i - DBL_MANT_DIG;
    02714         goto bignum;
    02715     }
    02716     rb_bug("big_fdiv");
    02717     /* NOTREACHED */
    02718 }
    02719
    02720 /*
    02721  *  call-seq:
    02722   *     big.fdiv(numeric) -> float
    02723  *
    02724  *  Returns the floating point result of dividing <i>big</i> by
    02725  *  <i>numeric</i>.
    02726  *
    02727  *     -1234567890987654321.fdiv(13731)      #=> -89910996357705.5
    02728  *     -1234567890987654321.fdiv(13731.24)   #=> -89909424858035.7
    02729  *
    02730  */
    02731
    02732
    02733 VALUE
    02734 rb_big_fdiv(VALUE x, VALUE y)
    02735 {
    02736     double dx, dy;
    02737
    02738     dx = big2dbl(x);
    02739     switch (TYPE(y)) {
    02740       case T_FIXNUM:
    02741         dy = (double)FIX2LONG(y);
    02742         if (isinf(dx))
    02743             return big_fdiv(x, y);
    02744         break;
    02745
    02746       case T_BIGNUM:
    02747         dy = rb_big2dbl(y);
    02748         if (isinf(dx) || isinf(dy))
    02749             return big_fdiv(x, y);
    02750         break;
    02751
    02752       case T_FLOAT:
    02753         dy = RFLOAT_VALUE(y);
    02754         if (isnan(dy))
    02755             return y;
    02756         if (isinf(dx))
    02757             return big_fdiv(x, y);
    02758         break;
    02759
    02760       default:
    02761         return rb_num_coerce_bin(x, y, rb_intern("fdiv"));
    02762     }
    02763     return DBL2NUM(dx / dy);
    02764 }
    02765
    02766 static VALUE
    02767 bigsqr(VALUE x)
    02768 {
    02769     return bigtrunc(bigmul0(x, x));
    02770 }
    02771
    02772 /*
    02773  *  call-seq:
    02774  *     big ** exponent   -> numeric
    02775  *
    02776  *  Raises _big_ to the _exponent_ power (which may be an integer, float,
    02777  *  or anything that will coerce to a number). The result may be
    02778  *  a Fixnum, Bignum, or Float
    02779  *
    02780  *    123456789 ** 2      #=> 15241578750190521
    02781  *    123456789 ** 1.2    #=> 5126464716.09932
    02782  *    123456789 ** -2     #=> 6.5610001194102e-17
    02783  */
    02784
    02785 VALUE
    02786 rb_big_pow(VALUE x, VALUE y)
    02787 {
    02788     double d;
    02789     SIGNED_VALUE yy;
    02790
    02791     if (y == INT2FIX(0)) return INT2FIX(1);
    02792     switch (TYPE(y)) {
    02793       case T_FLOAT:
    02794         d = RFLOAT_VALUE(y);
    02795         if ((!RBIGNUM_SIGN(x) && !BIGZEROP(x)) && d != round(d))
    02796             return rb_funcall(rb_complex_raw1(x), rb_intern("**"), 1, y);
    02797         break;
    02798
    02799       case T_BIGNUM:
    02800         rb_warn("in a**b, b may be too big");
    02801         d = rb_big2dbl(y);
    02802         break;
    02803
    02804       case T_FIXNUM:
    02805         yy = FIX2LONG(y);
    02806
    02807         if (yy < 0)
    02808             return rb_funcall(rb_rational_raw1(x), rb_intern("**"), 1, y);
    02809         else {
    02810             VALUE z = 0;
    02811             SIGNED_VALUE mask;
    02812             const long BIGLEN_LIMIT = 1024*1024 / SIZEOF_BDIGITS;
    02813
    02814             if ((RBIGNUM_LEN(x) > BIGLEN_LIMIT) ||
    02815                 (RBIGNUM_LEN(x) > BIGLEN_LIMIT / yy)) {
    02816                 rb_warn("in a**b, b may be too big");
    02817                 d = (double)yy;
    02818                 break;
    02819             }
    02820             for (mask = FIXNUM_MAX + 1; mask; mask >>= 1) {
    02821                 if (z) z = bigsqr(z);
    02822                 if (yy & mask) {
    02823                     z = z ? bigtrunc(bigmul0(z, x)) : x;
    02824                 }
    02825             }
    02826             return bignorm(z);
    02827         }
    02828         /* NOTREACHED */
    02829         break;
    02830
    02831       default:
    02832         return rb_num_coerce_bin(x, y, rb_intern("**"));
    02833     }
    02834     return DBL2NUM(pow(rb_big2dbl(x), d));
    02835 }
    02836
    02837 static inline VALUE
    02838 bit_coerce(VALUE x)
    02839 {
    02840     while (!FIXNUM_P(x) && TYPE(x) != T_BIGNUM) {
    02841         if (TYPE(x) == T_FLOAT) {
    02842             rb_raise(rb_eTypeError, "can't convert Float into Integer");
    02843         }
    02844         x = rb_to_int(x);
    02845     }
    02846     return x;
    02847 }
    02848
    02849 static VALUE
    02850 bigand_int(VALUE x, long y)
    02851 {
    02852     VALUE z;
    02853     BDIGIT *xds, *zds;
    02854     long xn, zn;
    02855     long i;
    02856     char sign;
    02857
    02858     if (y == 0) return INT2FIX(0);
    02859     sign = (y > 0);
    02860     xds = BDIGITS(x);
    02861     zn = xn = RBIGNUM_LEN(x);
    02862 #if SIZEOF_BDIGITS == SIZEOF_LONG
    02863     if (sign) {
    02864         y &= xds[0];
    02865         return LONG2NUM(y);
    02866     }
    02867 #endif
    02868
    02869     z = bignew(zn, RBIGNUM_SIGN(x) || sign);
    02870     zds = BDIGITS(z);
    02871
    02872 #if SIZEOF_BDIGITS == SIZEOF_LONG
    02873     i = 1;
    02874     zds[0] = xds[0] & y;
    02875 #else
    02876     {
    02877         BDIGIT_DBL num = y;
    02878
    02879         for (i=0; i<(int)(sizeof(y)/sizeof(BDIGIT)); i++) {
    02880             zds[i] = xds[i] & BIGLO(num);
    02881             num = BIGDN(num);
    02882         }
    02883     }
    02884 #endif
    02885     while (i < xn) {
    02886         zds[i] = sign?0:xds[i];
    02887         i++;
    02888     }
    02889     if (!RBIGNUM_SIGN(z)) get2comp(z);
    02890     return bignorm(z);
    02891 }
    02892
    02893 /*
    02894  * call-seq:
    02895  *     big & numeric   ->  integer
    02896  *
    02897  * Performs bitwise +and+ between _big_ and _numeric_.
    02898  */
    02899
    02900 VALUE
    02901 rb_big_and(VALUE xx, VALUE yy)
    02902 {
    02903     volatile VALUE x, y, z;
    02904     BDIGIT *ds1, *ds2, *zds;
    02905     long i, l1, l2;
    02906     char sign;
    02907
    02908     x = xx;
    02909     y = bit_coerce(yy);
    02910     if (!RBIGNUM_SIGN(x)) {
    02911         x = rb_big_clone(x);
    02912         get2comp(x);
    02913     }
    02914     if (FIXNUM_P(y)) {
    02915         return bigand_int(x, FIX2LONG(y));
    02916     }
    02917     if (!RBIGNUM_SIGN(y)) {
    02918         y = rb_big_clone(y);
    02919         get2comp(y);
    02920     }
    02921     if (RBIGNUM_LEN(x) > RBIGNUM_LEN(y)) {
    02922         l1 = RBIGNUM_LEN(y);
    02923         l2 = RBIGNUM_LEN(x);
    02924         ds1 = BDIGITS(y);
    02925         ds2 = BDIGITS(x);
    02926         sign = RBIGNUM_SIGN(y);
    02927     }
    02928     else {
    02929         l1 = RBIGNUM_LEN(x);
    02930         l2 = RBIGNUM_LEN(y);
    02931         ds1 = BDIGITS(x);
    02932         ds2 = BDIGITS(y);
    02933         sign = RBIGNUM_SIGN(x);
    02934     }
    02935     z = bignew(l2, RBIGNUM_SIGN(x) || RBIGNUM_SIGN(y));
    02936     zds = BDIGITS(z);
    02937
    02938     for (i=0; i<l1; i++) {
    02939         zds[i] = ds1[i] & ds2[i];
    02940     }
    02941     for (; i<l2; i++) {
    02942         zds[i] = sign?0:ds2[i];
    02943     }
    02944     if (!RBIGNUM_SIGN(z)) get2comp(z);
    02945     return bignorm(z);
    02946 }
    02947
    02948 static VALUE
    02949 bigor_int(VALUE x, long y)
    02950 {
    02951     VALUE z;
    02952     BDIGIT *xds, *zds;
    02953     long xn, zn;
    02954     long i;
    02955     char sign;
    02956
    02957     sign = (y >= 0);
    02958     xds = BDIGITS(x);
    02959     zn = xn = RBIGNUM_LEN(x);
    02960     z = bignew(zn, RBIGNUM_SIGN(x) && sign);
    02961     zds = BDIGITS(z);
    02962
    02963 #if SIZEOF_BDIGITS == SIZEOF_LONG
    02964     i = 1;
    02965     zds[0] = xds[0] | y;
    02966 #else
    02967     {
    02968         BDIGIT_DBL num = y;
    02969
    02970         for (i=0; i<(int)(sizeof(y)/sizeof(BDIGIT)); i++) {
    02971             zds[i] = xds[i] | BIGLO(num);
    02972             num = BIGDN(num);
    02973         }
    02974     }
    02975 #endif
    02976     while (i < xn) {
    02977         zds[i] = sign?xds[i]:(BDIGIT)(BIGRAD-1);
    02978         i++;
    02979     }
    02980     if (!RBIGNUM_SIGN(z)) get2comp(z);
    02981     return bignorm(z);
    02982 }
    02983
    02984 /*
    02985  * call-seq:
    02986  *     big | numeric   ->  integer
    02987  *
    02988  * Performs bitwise +or+ between _big_ and _numeric_.
    02989  */
    02990
    02991 VALUE
    02992 rb_big_or(VALUE xx, VALUE yy)
    02993 {
    02994     volatile VALUE x, y, z;
    02995     BDIGIT *ds1, *ds2, *zds;
    02996     long i, l1, l2;
    02997     char sign;
    02998
    02999     x = xx;
    03000     y = bit_coerce(yy);
    03001
    03002     if (!RBIGNUM_SIGN(x)) {
    03003         x = rb_big_clone(x);
    03004         get2comp(x);
    03005     }
    03006     if (FIXNUM_P(y)) {
    03007         return bigor_int(x, FIX2LONG(y));
    03008     }
    03009     if (!RBIGNUM_SIGN(y)) {
    03010         y = rb_big_clone(y);
    03011         get2comp(y);
    03012     }
    03013     if (RBIGNUM_LEN(x) > RBIGNUM_LEN(y)) {
    03014         l1 = RBIGNUM_LEN(y);
    03015         l2 = RBIGNUM_LEN(x);
    03016         ds1 = BDIGITS(y);
    03017         ds2 = BDIGITS(x);
    03018         sign = RBIGNUM_SIGN(y);
    03019     }
    03020     else {
    03021         l1 = RBIGNUM_LEN(x);
    03022         l2 = RBIGNUM_LEN(y);
    03023         ds1 = BDIGITS(x);
    03024         ds2 = BDIGITS(y);
    03025         sign = RBIGNUM_SIGN(x);
    03026     }
    03027     z = bignew(l2, RBIGNUM_SIGN(x) && RBIGNUM_SIGN(y));
    03028     zds = BDIGITS(z);
    03029
    03030     for (i=0; i<l1; i++) {
    03031         zds[i] = ds1[i] | ds2[i];
    03032     }
    03033     for (; i<l2; i++) {
    03034         zds[i] = sign?ds2[i]:(BDIGIT)(BIGRAD-1);
    03035     }
    03036     if (!RBIGNUM_SIGN(z)) get2comp(z);
    03037     return bignorm(z);
    03038 }
    03039
    03040 static VALUE
    03041 bigxor_int(VALUE x, long y)
    03042 {
    03043     VALUE z;
    03044     BDIGIT *xds, *zds;
    03045     long xn, zn;
    03046     long i;
    03047     char sign;
    03048
    03049     sign = (y >= 0) ? 1 : 0;
    03050     xds = BDIGITS(x);
    03051     zn = xn = RBIGNUM_LEN(x);
    03052     z = bignew(zn, !(RBIGNUM_SIGN(x) ^ sign));
    03053     zds = BDIGITS(z);
    03054
    03055 #if SIZEOF_BDIGITS == SIZEOF_LONG
    03056     i = 1;
    03057     zds[0] = xds[0] ^ y;
    03058 #else
    03059     {
    03060         BDIGIT_DBL num = y;
    03061
    03062         for (i=0; i<(int)(sizeof(y)/sizeof(BDIGIT)); i++) {
    03063             zds[i] = xds[i] ^ BIGLO(num);
    03064             num = BIGDN(num);
    03065         }
    03066     }
    03067 #endif
    03068     while (i < xn) {
    03069         zds[i] = sign?xds[i]:~xds[i];
    03070         i++;
    03071     }
    03072     if (!RBIGNUM_SIGN(z)) get2comp(z);
    03073     return bignorm(z);
    03074 }
    03075 /*
    03076  * call-seq:
    03077  *     big ^ numeric   ->  integer
    03078  *
    03079  * Performs bitwise +exclusive or+ between _big_ and _numeric_.
    03080  */
    03081
    03082 VALUE
    03083 rb_big_xor(VALUE xx, VALUE yy)
    03084 {
    03085     volatile VALUE x, y;
    03086     VALUE z;
    03087     BDIGIT *ds1, *ds2, *zds;
    03088     long i, l1, l2;
    03089     char sign;
    03090
    03091     x = xx;
    03092     y = bit_coerce(yy);
    03093
    03094     if (!RBIGNUM_SIGN(x)) {
    03095         x = rb_big_clone(x);
    03096         get2comp(x);
    03097     }
    03098     if (FIXNUM_P(y)) {
    03099         return bigxor_int(x, FIX2LONG(y));
    03100     }
    03101     if (!RBIGNUM_SIGN(y)) {
    03102         y = rb_big_clone(y);
    03103         get2comp(y);
    03104     }
    03105     if (RBIGNUM_LEN(x) > RBIGNUM_LEN(y)) {
    03106         l1 = RBIGNUM_LEN(y);
    03107         l2 = RBIGNUM_LEN(x);
    03108         ds1 = BDIGITS(y);
    03109         ds2 = BDIGITS(x);
    03110         sign = RBIGNUM_SIGN(y);
    03111     }
    03112     else {
    03113         l1 = RBIGNUM_LEN(x);
    03114         l2 = RBIGNUM_LEN(y);
    03115         ds1 = BDIGITS(x);
    03116         ds2 = BDIGITS(y);
    03117         sign = RBIGNUM_SIGN(x);
    03118     }
    03119     RBIGNUM_SET_SIGN(x, RBIGNUM_SIGN(x)?1:0);
    03120     RBIGNUM_SET_SIGN(y, RBIGNUM_SIGN(y)?1:0);
    03121     z = bignew(l2, !(RBIGNUM_SIGN(x) ^ RBIGNUM_SIGN(y)));
    03122     zds = BDIGITS(z);
    03123
    03124     for (i=0; i<l1; i++) {
    03125         zds[i] = ds1[i] ^ ds2[i];
    03126     }
    03127     for (; i<l2; i++) {
    03128         zds[i] = sign?ds2[i]:~ds2[i];
    03129     }
    03130     if (!RBIGNUM_SIGN(z)) get2comp(z);
    03131
    03132     return bignorm(z);
    03133 }
    03134
    03135 static VALUE
    03136 check_shiftdown(VALUE y, VALUE x)
    03137 {
    03138     if (!RBIGNUM_LEN(x)) return INT2FIX(0);
    03139     if (RBIGNUM_LEN(y) > SIZEOF_LONG / SIZEOF_BDIGITS) {
    03140         return RBIGNUM_SIGN(x) ? INT2FIX(0) : INT2FIX(-1);
    03141     }
    03142     return Qnil;
    03143 }
    03144
    03145 /*
    03146  * call-seq:
    03147  *     big << numeric   ->  integer
    03148  *
    03149  * Shifts big left _numeric_ positions (right if _numeric_ is negative).
    03150  */
    03151
    03152 VALUE
    03153 rb_big_lshift(VALUE x, VALUE y)
    03154 {
    03155     long shift;
    03156     int neg = 0;
    03157
    03158     for (;;) {
    03159         if (FIXNUM_P(y)) {
    03160             shift = FIX2LONG(y);
    03161             if (shift < 0) {
    03162                 neg = 1;
    03163                 shift = -shift;
    03164             }
    03165             break;
    03166         }
    03167         else if (TYPE(y) == T_BIGNUM) {
    03168             if (!RBIGNUM_SIGN(y)) {
    03169                 VALUE t = check_shiftdown(y, x);
    03170                 if (!NIL_P(t)) return t;
    03171                 neg = 1;
    03172             }
    03173             shift = big2ulong(y, "long", TRUE);
    03174             break;
    03175         }
    03176         y = rb_to_int(y);
    03177     }
    03178
    03179     x = neg ? big_rshift(x, shift) : big_lshift(x, shift);
    03180     return bignorm(x);
    03181 }
    03182
    03183 static VALUE
    03184 big_lshift(VALUE x, unsigned long shift)
    03185 {
    03186     BDIGIT *xds, *zds;
    03187     long s1 = shift/BITSPERDIG;
    03188     int s2 = (int)(shift%BITSPERDIG);
    03189     VALUE z;
    03190     BDIGIT_DBL num = 0;
    03191     long len, i;
    03192
    03193     len = RBIGNUM_LEN(x);
    03194     z = bignew(len+s1+1, RBIGNUM_SIGN(x));
    03195     zds = BDIGITS(z);
    03196     for (i=0; i<s1; i++) {
    03197         *zds++ = 0;
    03198     }
    03199     xds = BDIGITS(x);
    03200     for (i=0; i<len; i++) {
    03201         num = num | (BDIGIT_DBL)*xds++<<s2;
    03202         *zds++ = BIGLO(num);
    03203         num = BIGDN(num);
    03204     }
    03205     *zds = BIGLO(num);
    03206     return z;
    03207 }
    03208
    03209 /*
    03210  * call-seq:
    03211  *     big >> numeric   ->  integer
    03212  *
    03213  * Shifts big right _numeric_ positions (left if _numeric_ is negative).
    03214  */
    03215
    03216 VALUE
    03217 rb_big_rshift(VALUE x, VALUE y)
    03218 {
    03219     long shift;
    03220     int neg = 0;
    03221
    03222     for (;;) {
    03223         if (FIXNUM_P(y)) {
    03224             shift = FIX2LONG(y);
    03225             if (shift < 0) {
    03226                 neg = 1;
    03227                 shift = -shift;
    03228             }
    03229             break;
    03230         }
    03231         else if (TYPE(y) == T_BIGNUM) {
    03232             if (RBIGNUM_SIGN(y)) {
    03233                 VALUE t = check_shiftdown(y, x);
    03234                 if (!NIL_P(t)) return t;
    03235             }
    03236             else {
    03237                 neg = 1;
    03238             }
    03239             shift = big2ulong(y, "long", TRUE);
    03240             break;
    03241         }
    03242         y = rb_to_int(y);
    03243     }
    03244
    03245     x = neg ? big_lshift(x, shift) : big_rshift(x, shift);
    03246     return bignorm(x);
    03247 }
    03248
    03249 static VALUE
    03250 big_rshift(VALUE x, unsigned long shift)
    03251 {
    03252     BDIGIT *xds, *zds;
    03253     long s1 = shift/BITSPERDIG;
    03254     int s2 = (int)(shift%BITSPERDIG);
    03255     VALUE z;
    03256     BDIGIT_DBL num = 0;
    03257     long i, j;
    03258     volatile VALUE save_x;
    03259
    03260     if (s1 > RBIGNUM_LEN(x)) {
    03261         if (RBIGNUM_SIGN(x))
    03262             return INT2FIX(0);
    03263         else
    03264             return INT2FIX(-1);
    03265     }
    03266     if (!RBIGNUM_SIGN(x)) {
    03267         save_x = x = rb_big_clone(x);
    03268         get2comp(x);
    03269     }
    03270     xds = BDIGITS(x);
    03271     i = RBIGNUM_LEN(x); j = i - s1;
    03272     if (j == 0) {
    03273         if (RBIGNUM_SIGN(x)) return INT2FIX(0);
    03274         else return INT2FIX(-1);
    03275     }
    03276     z = bignew(j, RBIGNUM_SIGN(x));
    03277     if (!RBIGNUM_SIGN(x)) {
    03278         num = ((BDIGIT_DBL)~0) << BITSPERDIG;
    03279     }
    03280     zds = BDIGITS(z);
    03281     while (i--, j--) {
    03282         num = (num | xds[i]) >> s2;
    03283         zds[j] = BIGLO(num);
    03284         num = BIGUP(xds[i]);
    03285     }
    03286     if (!RBIGNUM_SIGN(x)) {
    03287         get2comp(z);
    03288     }
    03289     return z;
    03290 }
    03291
    03292 /*
    03293  *  call-seq:
    03294  *     big[n] -> 0, 1
    03295  *
    03296  *  Bit Reference---Returns the <em>n</em>th bit in the (assumed) binary
    03297  *  representation of <i>big</i>, where <i>big</i>[0] is the least
    03298  *  significant bit.
    03299  *
    03300  *     a = 9**15
    03301  *     50.downto(0) do |n|
    03302  *       print a[n]
    03303  *     end
    03304  *
    03305  *  <em>produces:</em>
    03306  *
    03307  *     000101110110100000111000011110010100111100010111001
    03308  *
    03309  */
    03310
    03311 static VALUE
    03312 rb_big_aref(VALUE x, VALUE y)
    03313 {
    03314     BDIGIT *xds;
    03315     BDIGIT_DBL num;
    03316     VALUE shift;
    03317     long i, s1, s2;
    03318
    03319     if (TYPE(y) == T_BIGNUM) {
    03320         if (!RBIGNUM_SIGN(y))
    03321             return INT2FIX(0);
    03322         bigtrunc(y);
    03323         if (RBIGNUM_LEN(y) > DIGSPERLONG) {
    03324           out_of_range:
    03325             return RBIGNUM_SIGN(x) ? INT2FIX(0) : INT2FIX(1);
    03326         }
    03327         shift = big2ulong(y, "long", FALSE);
    03328     }
    03329     else {
    03330         i = NUM2LONG(y);
    03331         if (i < 0) return INT2FIX(0);
    03332         shift = (VALUE)i;
    03333     }
    03334     s1 = shift/BITSPERDIG;
    03335     s2 = shift%BITSPERDIG;
    03336
    03337     if (s1 >= RBIGNUM_LEN(x)) goto out_of_range;
    03338     if (!RBIGNUM_SIGN(x)) {
    03339         xds = BDIGITS(x);
    03340         i = 0; num = 1;
    03341         while (num += ~xds[i], ++i <= s1) {
    03342             num = BIGDN(num);
    03343         }
    03344     }
    03345     else {
    03346         num = BDIGITS(x)[s1];
    03347     }
    03348     if (num & ((BDIGIT_DBL)1<<s2))
    03349         return INT2FIX(1);
    03350     return INT2FIX(0);
    03351 }
    03352
    03353 /*
    03354  * call-seq:
    03355  *   big.hash   -> fixnum
    03356  *
    03357  * Compute a hash based on the value of _big_.
    03358  */
    03359
    03360 static VALUE
    03361 rb_big_hash(VALUE x)
    03362 {
    03363     st_index_t hash;
    03364
    03365     hash = rb_memhash(BDIGITS(x), sizeof(BDIGIT)*RBIGNUM_LEN(x)) ^ RBIGNUM_SIGN(x);
    03366     return INT2FIX(hash);
    03367 }
    03368
    03369 /*
    03370  * MISSING: documentation
    03371  */
    03372
    03373 static VALUE
    03374 rb_big_coerce(VALUE x, VALUE y)
    03375 {
    03376     if (FIXNUM_P(y)) {
    03377         return rb_assoc_new(rb_int2big(FIX2LONG(y)), x);
    03378     }
    03379     else if (TYPE(y) == T_BIGNUM) {
    03380        return rb_assoc_new(y, x);
    03381     }
    03382     else {
    03383         rb_raise(rb_eTypeError, "can't coerce %s to Bignum",
    03384                  rb_obj_classname(y));
    03385     }
    03386     /* not reached */
    03387     return Qnil;
    03388 }
    03389
    03390 /*
    03391  *  call-seq:
    03392  *     big.abs -> aBignum
    03393  *
    03394  *  Returns the absolute value of <i>big</i>.
    03395  *
    03396  *     -1234567890987654321.abs   #=> 1234567890987654321
    03397  */
    03398
    03399 static VALUE
    03400 rb_big_abs(VALUE x)
    03401 {
    03402     if (!RBIGNUM_SIGN(x)) {
    03403         x = rb_big_clone(x);
    03404         RBIGNUM_SET_SIGN(x, 1);
    03405     }
    03406     return x;
    03407 }
    03408
    03409 /*
    03410  *  call-seq:
    03411  *     big.size -> integer
    03412  *
    03413  *  Returns the number of bytes in the machine representation of
    03414  *  <i>big</i>.
    03415  *
    03416  *     (256**10 - 1).size   #=> 12
    03417  *     (256**20 - 1).size   #=> 20
    03418  *     (256**40 - 1).size   #=> 40
    03419  */
    03420
    03421 static VALUE
    03422 rb_big_size(VALUE big)
    03423 {
    03424     return LONG2FIX(RBIGNUM_LEN(big)*SIZEOF_BDIGITS);
    03425 }
    03426
    03427 /*
    03428  *  call-seq:
    03429  *     big.odd? -> true or false
    03430  *
    03431  *  Returns <code>true</code> if <i>big</i> is an odd number.
    03432  */
    03433
    03434 static VALUE
    03435 rb_big_odd_p(VALUE num)
    03436 {
    03437     if (BDIGITS(num)[0] & 1) {
    03438         return Qtrue;
    03439     }
    03440     return Qfalse;
    03441 }
    03442
    03443 /*
    03444  *  call-seq:
    03445  *     big.even? -> true or false
    03446  *
    03447  *  Returns <code>true</code> if <i>big</i> is an even number.
    03448  */
    03449
    03450 static VALUE
    03451 rb_big_even_p(VALUE num)
    03452 {
    03453     if (BDIGITS(num)[0] & 1) {
    03454         return Qfalse;
    03455     }
    03456     return Qtrue;
    03457 }
    03458
    03459 /*
    03460  *  Bignum objects hold integers outside the range of
    03461  *  Fixnum. Bignum objects are created
    03462  *  automatically when integer calculations would otherwise overflow a
    03463  *  Fixnum. When a calculation involving
    03464  *  Bignum objects returns a result that will fit in a
    03465  *  Fixnum, the result is automatically converted.
    03466  *
    03467  *  For the purposes of the bitwise operations and <code>[]</code>, a
    03468  *  Bignum is treated as if it were an infinite-length
    03469  *  bitstring with 2's complement representation.
    03470  *
    03471  *  While Fixnum values are immediate, Bignum
    03472  *  objects are not---assignment and parameter passing work with
    03473  *  references to objects, not the objects themselves.
    03474  *
    03475  */
    03476
    03477 void
    03478 Init_Bignum(void)
    03479 {
    03480     rb_cBignum = rb_define_class("Bignum", rb_cInteger);
    03481
    03482     rb_define_method(rb_cBignum, "to_s", rb_big_to_s, -1);
    03483     rb_define_method(rb_cBignum, "coerce", rb_big_coerce, 1);
    03484     rb_define_method(rb_cBignum, "-@", rb_big_uminus, 0);
    03485     rb_define_method(rb_cBignum, "+", rb_big_plus, 1);
    03486     rb_define_method(rb_cBignum, "-", rb_big_minus, 1);
    03487     rb_define_method(rb_cBignum, "*", rb_big_mul, 1);
    03488     rb_define_method(rb_cBignum, "/", rb_big_div, 1);
    03489     rb_define_method(rb_cBignum, "%", rb_big_modulo, 1);
    03490     rb_define_method(rb_cBignum, "div", rb_big_idiv, 1);
    03491     rb_define_method(rb_cBignum, "divmod", rb_big_divmod, 1);
    03492     rb_define_method(rb_cBignum, "modulo", rb_big_modulo, 1);
    03493     rb_define_method(rb_cBignum, "remainder", rb_big_remainder, 1);
    03494     rb_define_method(rb_cBignum, "fdiv", rb_big_fdiv, 1);
    03495     rb_define_method(rb_cBignum, "**", rb_big_pow, 1);
    03496     rb_define_method(rb_cBignum, "&", rb_big_and, 1);
    03497     rb_define_method(rb_cBignum, "|", rb_big_or, 1);
    03498     rb_define_method(rb_cBignum, "^", rb_big_xor, 1);
    03499     rb_define_method(rb_cBignum, "~", rb_big_neg, 0);
    03500     rb_define_method(rb_cBignum, "<<", rb_big_lshift, 1);
    03501     rb_define_method(rb_cBignum, ">>", rb_big_rshift, 1);
    03502     rb_define_method(rb_cBignum, "[]", rb_big_aref, 1);
    03503
    03504     rb_define_method(rb_cBignum, "<=>", rb_big_cmp, 1);
    03505     rb_define_method(rb_cBignum, "==", rb_big_eq, 1);
    03506     rb_define_method(rb_cBignum, ">", big_gt, 1);
    03507     rb_define_method(rb_cBignum, ">=", big_ge, 1);
    03508     rb_define_method(rb_cBignum, "<", big_lt, 1);
    03509     rb_define_method(rb_cBignum, "<=", big_le, 1);
    03510     rb_define_method(rb_cBignum, "===", rb_big_eq, 1);
    03511     rb_define_method(rb_cBignum, "eql?", rb_big_eql, 1);
    03512     rb_define_method(rb_cBignum, "hash", rb_big_hash, 0);
    03513     rb_define_method(rb_cBignum, "to_f", rb_big_to_f, 0);
    03514     rb_define_method(rb_cBignum, "abs", rb_big_abs, 0);
    03515     rb_define_method(rb_cBignum, "magnitude", rb_big_abs, 0);
    03516     rb_define_method(rb_cBignum, "size", rb_big_size, 0);
    03517     rb_define_method(rb_cBignum, "odd?", rb_big_odd_p, 0);
    03518     rb_define_method(rb_cBignum, "even?", rb_big_even_p, 0);
    03519
    03520     power_cache_init();
    03521 }
    03522