diff options
Diffstat (limited to 'bignum.c')
-rw-r--r-- | bignum.c | 1760 |
1 files changed, 0 insertions, 1760 deletions
diff --git a/bignum.c b/bignum.c deleted file mode 100644 index e090f9b0dc..0000000000 --- a/bignum.c +++ /dev/null @@ -1,1760 +0,0 @@ -/********************************************************************** - - bignum.c - - - $Author$ - $Date$ - created at: Fri Jun 10 00:48:55 JST 1994 - - Copyright (C) 1993-2002 Yukihiro Matsumoto - -**********************************************************************/ - -#include <math.h> -#include <ctype.h> -#include "ruby.h" - -VALUE rb_cBignum; - -#if defined __MINGW32__ -#define USHORT _USHORT -#endif - -#if SIZEOF_INT*2 <= SIZEOF_LONG_LONG -typedef unsigned int BDIGIT; -typedef unsigned LONG_LONG BDIGIT_DBL; -typedef LONG_LONG BDIGIT_DBL_SIGNED; -#elif SIZEOF_INT*2 <= SIZEOF_LONG -typedef unsigned int BDIGIT; -typedef unsigned long BDIGIT_DBL; -typedef LONG_LONG BDIGIT_DBL_SIGNED; -#else -typedef unsigned short BDIGIT; -typedef unsigned long BDIGIT_DBL; -typedef long BDIGIT_DBL_SIGNED; -#endif - -#define BDIGITS(x) ((BDIGIT*)RBIGNUM(x)->digits) -#define BITSPERDIG (sizeof(BDIGIT)*CHAR_BIT) -#define BIGRAD ((BDIGIT_DBL)1 << BITSPERDIG) -#define DIGSPERLONG ((unsigned int)(sizeof(long)/sizeof(BDIGIT))) -#if HAVE_LONG_LONG -# define DIGSPERLL ((unsigned int)(sizeof(LONG_LONG)/sizeof(BDIGIT))) -#endif -#define BIGUP(x) ((BDIGIT_DBL)(x) << BITSPERDIG) -#define BIGDN(x) RSHIFT(x,BITSPERDIG) -#define BIGLO(x) ((BDIGIT)((x) & (BIGRAD-1))) - -static VALUE -bignew_1(klass, len, sign) - VALUE klass; - long len; - char sign; -{ - NEWOBJ(big, struct RBignum); - OBJSETUP(big, klass, T_BIGNUM); - big->sign = sign; - big->len = len; - big->digits = ALLOC_N(BDIGIT, len); - - return (VALUE)big; -} - -#define bignew(len,sign) bignew_1(rb_cBignum,len,sign) - -VALUE -rb_big_clone(x) - VALUE x; -{ - VALUE z = bignew_1(CLASS_OF(x), RBIGNUM(x)->len, RBIGNUM(x)->sign); - - MEMCPY(BDIGITS(z), BDIGITS(x), BDIGIT, RBIGNUM(x)->len); - return z; -} - -static void -get2comp(x, carry) /* get 2's complement */ - VALUE x; - int carry; -{ - long i = RBIGNUM(x)->len; - BDIGIT *ds = BDIGITS(x); - BDIGIT_DBL num; - - while (i--) ds[i] = ~ds[i]; - i = 0; num = 1; - do { - num += ds[i]; - ds[i++] = BIGLO(num); - num = BIGDN(num); - } while (i < RBIGNUM(x)->len); - if (!carry) return; - if (ds[0] == 1 || ds[0] == 0) { - if (RBIGNUM(x)->len == 1) return; - for (i=1; i<RBIGNUM(x)->len; i++) { - if (ds[i] != 0) return; - } - REALLOC_N(RBIGNUM(x)->digits, BDIGIT, RBIGNUM(x)->len++); - ds = BDIGITS(x); - ds[RBIGNUM(x)->len-1] = 1; - } -} - -void -rb_big_2comp(x) /* get 2's complement */ - VALUE x; -{ - get2comp(x, Qtrue); -} - -static VALUE -bignorm(x) - VALUE x; -{ - if (!FIXNUM_P(x)) { - long len = RBIGNUM(x)->len; - BDIGIT *ds = BDIGITS(x); - - while (len-- && !ds[len]) ; - RBIGNUM(x)->len = ++len; - - if (len*sizeof(BDIGIT) <= sizeof(VALUE)) { - long num = 0; - while (len--) { - num = BIGUP(num) + ds[len]; - } - if (num >= 0) { - if (RBIGNUM(x)->sign) { - if (POSFIXABLE(num)) return INT2FIX(num); - } - else if (NEGFIXABLE(-(long)num)) return INT2FIX(-(long)num); - } - } - } - return x; -} - -VALUE -rb_big_norm(x) - VALUE x; -{ - return bignorm(x); -} - -VALUE -rb_uint2big(n) - unsigned long n; -{ - BDIGIT_DBL num = n; - long i = 0; - BDIGIT *digits; - VALUE big; - - i = 0; - big = bignew(DIGSPERLONG, 1); - digits = BDIGITS(big); - while (i < DIGSPERLONG) { - digits[i++] = BIGLO(num); - num = BIGDN(num); - } - - i = DIGSPERLONG; - while (i-- && !digits[i]) ; - RBIGNUM(big)->len = i+1; - return big; -} - -VALUE -rb_int2big(n) - long n; -{ - long neg = 0; - VALUE big; - - if (n < 0) { - n = -n; - neg = 1; - } - big = rb_uint2big(n); - if (neg) { - RBIGNUM(big)->sign = 0; - } - return big; -} - -VALUE -rb_uint2inum(n) - unsigned long n; -{ - if (POSFIXABLE(n)) return INT2FIX(n); - return rb_uint2big(n); -} - -VALUE -rb_int2inum(n) - long n; -{ - if (FIXABLE(n)) return INT2FIX(n); - return rb_int2big(n); -} - -#ifdef HAVE_LONG_LONG - -#define DIGSPERLONGLONG ((unsigned int)(sizeof(LONG_LONG)/sizeof(BDIGIT))) - -void -rb_quad_pack(buf, val) - char *buf; - VALUE val; -{ - LONG_LONG q; - - val = rb_to_int(val); - if (FIXNUM_P(val)) { - q = FIX2LONG(val); - } - else { - long len = RBIGNUM(val)->len; - BDIGIT *ds; - - ds = BDIGITS(val); - q = 0; - while (len--) { - q = BIGUP(q); - q += ds[len]; - } - } - memcpy(buf, (char*)&q, sizeof(LONG_LONG)); -} - -VALUE -rb_quad_unpack(buf, sign) - const char *buf; - int sign; -{ - unsigned LONG_LONG q; - long neg = 0; - long i = 0; - BDIGIT *digits; - VALUE big; - - memcpy(&q, buf, sizeof(LONG_LONG)); - if (sign) { - if (FIXABLE((LONG_LONG)q)) return INT2FIX((LONG_LONG)q); - if ((LONG_LONG)q < 0) { - q = -(LONG_LONG)q; - neg = 1; - } - } - else { - if (POSFIXABLE(q)) return INT2FIX(q); - } - - i = 0; - big = bignew(DIGSPERLONGLONG, 1); - digits = BDIGITS(big); - while (i < DIGSPERLONGLONG) { - digits[i++] = BIGLO(q); - q = BIGDN(q); - } - - i = DIGSPERLONGLONG; - while (i-- && !digits[i]) ; - RBIGNUM(big)->len = i+1; - - if (neg) { - RBIGNUM(big)->sign = 0; - } - return bignorm(big); -} - -#else - -#define QUAD_SIZE 8 - -void -rb_quad_pack(buf, val) - char *buf; - VALUE val; -{ - long len; - - memset(buf, 0, QUAD_SIZE); - val = rb_to_int(val); - if (FIXNUM_P(val)) { - val = rb_int2big(FIX2LONG(val)); - } - len = RBIGNUM(val)->len * sizeof(BDIGIT); - if (len > QUAD_SIZE) len = QUAD_SIZE; - memcpy(buf, (char*)BDIGITS(val), len); - if (!RBIGNUM(val)->sign) { - len = QUAD_SIZE; - while (len--) { - *buf = ~*buf++; - } - } -} - -#define BNEG(b) (RSHIFT(((BDIGIT*)b)[QUAD_SIZE/sizeof(BDIGIT)-1],BITSPERDIG-1) != 0) - -VALUE -rb_quad_unpack(buf, sign) - const char *buf; - int sign; -{ - VALUE big = bignew(QUAD_SIZE/sizeof(BDIGIT), 1); - - memcpy((char*)BDIGITS(big), buf, QUAD_SIZE); - if (sign && BNEG(buf)) { - long len = QUAD_SIZE; - char *tmp = (char*)BDIGITS(big); - - RBIGNUM(big)->sign = 0; - while (len--) { - *tmp = ~*tmp++; - } - } - - return bignorm(big); -} - -#endif - -VALUE -rb_cstr_to_inum(str, base, badcheck) - const char *str; - int base; - int badcheck; -{ - const char *s = str; - char *end; - char sign = 1, c, nondigit = 0; - BDIGIT_DBL num; - long len, blen = 1; - long i; - VALUE z; - BDIGIT *zds; - - if (badcheck) { - while (ISSPACE(*str)) str++; - } - else { - while (ISSPACE(*str) || *str == '_') str++; - } - - if (str[0] == '+') { - str++; - } - else if (str[0] == '-') { - str++; - sign = 0; - } - if (str[0] == '+' || str[0] == '-') { - if (badcheck) goto bad; - return INT2FIX(0); - } - if (base <= 0) { - if (str[0] == '0') { - if (str[1] == 'x' || str[1] == 'X') { - base = 16; - } - else if (str[1] == 'b' || str[1] == 'B') { - base = 2; - } - else { - base = 8; - } - } - else if (base < -1) { - base = -base; - } - else { - base = 10; - } - } - if (base == 8) { - len = 3; - } - else { /* base == 10, 2 or 16 */ - if (base == 16 && str[0] == '0' && (str[1] == 'x'||str[1] == 'X')) { - str += 2; - } - else if (base == 2 && str[0] == '0' && (str[1] == 'b'||str[1] == 'B')) { - str += 2; - } - len = 4; - } - if (*str == '0') { /* squeeze preceeding 0s */ - while (*++str == '0'); - --str; - } - len *= strlen(str)*sizeof(char); - - if (len <= (sizeof(VALUE)*CHAR_BIT)) { - unsigned long val = strtoul((char*)str, &end, base); - - if (*end == '_') goto bigparse; - if (badcheck) { - if (end == str) goto bad; /* no number */ - while (*end && ISSPACE(*end)) end++; - if (*end) { /* trailing garbage */ - bad: - rb_invalid_str(s, "Integer"); - } - } - - if (POSFIXABLE(val)) { - if (sign) return INT2FIX(val); - else { - long result = -(long)val; - return INT2FIX(result); - } - } - else { - VALUE big = rb_uint2big(val); - RBIGNUM(big)->sign = sign; - return big; - } - } - bigparse: - len = (len/BITSPERDIG)+1; - if (badcheck && *str == '_') goto bad; - - z = bignew(len, sign); - zds = BDIGITS(z); - for (i=len;i--;) zds[i]=0; - while (c = *str++) { - switch (c) { - case '8': case '9': - if (base == 8) { - c = base; - break; - } - case '0': case '1': case '2': case '3': case '4': - case '5': case '6': case '7': - c = c - '0'; - nondigit = 0; - break; - case 'a': case 'b': case 'c': - case 'd': case 'e': case 'f': - c -= 'a' - 'A'; - case 'A': case 'B': case 'C': - case 'D': case 'E': case 'F': - if (base != 16) { - nondigit = c; - c = base; - } - else { - c = c - 'A' + 10; - nondigit = 0; - } - break; - case '_': - if (badcheck) { - if (nondigit) goto bad; - nondigit = c; - } - continue; - default: - c = base; - break; - } - if (c >= base) break; - i = 0; - num = c; - for (;;) { - while (i<blen) { - num += (BDIGIT_DBL)zds[i]*base; - zds[i++] = BIGLO(num); - num = BIGDN(num); - } - if (num) { - blen++; - continue; - } - break; - } - } - if (badcheck) { - str--; - if (s+1 < str && str[-1] == '_') goto bad; - while (*str && ISSPACE(*str)) str++; - if (*str) goto bad; - } - - return bignorm(z); -} - -VALUE -rb_str_to_inum(str, base, badcheck) - VALUE str; - int base; - int badcheck; -{ - char *s; - int len; - - StringValue(str); - s = RSTRING(str)->ptr; - len = RSTRING(str)->len; - if (s[len]) { /* no sentinel somehow */ - char *p = ALLOCA_N(char, len+1); - - MEMCPY(p, s, char, len); - p[len] = '\0'; - s = p; - } - if (badcheck && len != strlen(s)) { - rb_raise(rb_eArgError, "string for Integer contains null byte"); - } - return rb_cstr_to_inum(s, base, badcheck); -} - -#if HAVE_LONG_LONG - -VALUE -rb_ull2big(n) - unsigned LONG_LONG n; -{ - BDIGIT_DBL num = n; - long i = 0; - BDIGIT *digits; - VALUE big; - - i = 0; - big = bignew(DIGSPERLL, 1); - digits = BDIGITS(big); - while (i < DIGSPERLL) { - digits[i++] = BIGLO(num); - num = BIGDN(num); - } - - i = DIGSPERLL; - while (i-- && !digits[i]) ; - RBIGNUM(big)->len = i+1; - return big; -} - -VALUE -rb_ll2big(n) - LONG_LONG n; -{ - long neg = 0; - VALUE big; - - if (n < 0) { - n = -n; - neg = 1; - } - big = rb_ull2big(n); - if (neg) { - RBIGNUM(big)->sign = 0; - } - return big; -} - -VALUE -rb_ull2inum(n) - unsigned LONG_LONG n; -{ - if (POSFIXABLE(n)) return INT2FIX(n); - return rb_ull2big(n); -} - -VALUE -rb_ll2inum(n) - LONG_LONG n; -{ - if (FIXABLE(n)) return INT2FIX(n); - return rb_ll2big(n); -} - -#endif /* HAVE_LONG_LONG */ - -VALUE -rb_cstr2inum(str, base) - const char *str; - int base; -{ - return rb_cstr_to_inum(str, base, base==0); -} - -VALUE -rb_str2inum(str, base) - VALUE str; - int base; -{ - return rb_str_to_inum(str, base, base==0); -} - -static char hexmap[] = "0123456789abcdef"; -VALUE -rb_big2str(x, base) - VALUE x; - int base; -{ - volatile VALUE t; - BDIGIT *ds; - long i, j, hbase; - VALUE ss; - char *s, c; - - if (FIXNUM_P(x)) { - return rb_fix2str(x, base); - } - i = RBIGNUM(x)->len; - if (i == 0) return rb_str_new2("0"); - if (base == 10) { - j = (sizeof(BDIGIT)/sizeof(char)*CHAR_BIT*i*241L)/800+2; - hbase = 10000; - } - else if (base == 16) { - j = (sizeof(BDIGIT)/sizeof(char)*CHAR_BIT*i)/4+2; - hbase = 0x10000; - } - else if (base == 8) { - j = (sizeof(BDIGIT)/sizeof(char)*CHAR_BIT*i)+2; - hbase = 010000; - } - else if (base == 2) { - j = (sizeof(BDIGIT)*CHAR_BIT*i)+2; - hbase = 020; - } - else { - rb_raise(rb_eArgError, "illegal radix %d", base); - } - - t = rb_big_clone(x); - ds = BDIGITS(t); - ss = rb_str_new(0, j); - s = RSTRING(ss)->ptr; - - s[0] = RBIGNUM(x)->sign ? '+' : '-'; - while (i && j) { - long k = i; - BDIGIT_DBL num = 0; - - while (k--) { - num = BIGUP(num) + ds[k]; - ds[k] = (BDIGIT)(num / hbase); - num %= hbase; - } - if (ds[i-1] == 0) i--; - k = 4; - while (k--) { - c = (char)(num % base); - s[--j] = hexmap[(int)c]; - num /= base; - if (i == 0 && num == 0) break; - } - } - while (s[j] == '0') j++; - RSTRING(ss)->len -= RBIGNUM(x)->sign?j:j-1; - memmove(RBIGNUM(x)->sign?s:s+1, s+j, RSTRING(ss)->len); - s[RSTRING(ss)->len] = '\0'; - - return ss; -} - -static VALUE -rb_big_to_s(argc, argv, x) - int argc; - VALUE *argv; - VALUE x; -{ - VALUE b; - int base; - - rb_scan_args(argc, argv, "01", &b); - if (argc == 0) base = 10; - else base = NUM2INT(b); - return rb_big2str(x, base); -} - -static unsigned long -big2ulong(x, type) - VALUE x; - char *type; -{ - long len = RBIGNUM(x)->len; - BDIGIT_DBL num; - BDIGIT *ds; - - if (len > sizeof(long)/sizeof(BDIGIT)) - rb_raise(rb_eRangeError, "bignum too big to convert into `%s'", type); - ds = BDIGITS(x); - num = 0; - while (len--) { - num = BIGUP(num); - num += ds[len]; - } - return num; -} - -unsigned long -rb_big2ulong(x) - VALUE x; -{ - unsigned long num = big2ulong(x, "unsigned long"); - - if (!RBIGNUM(x)->sign) return -num; - return num; -} - -long -rb_big2long(x) - VALUE x; -{ - unsigned long num = big2ulong(x, "int"); - - if ((long)num < 0 && (RBIGNUM(x)->sign || (long)num != LONG_MIN)) { - rb_raise(rb_eRangeError, "bignum too big to convert into `int'"); - } - if (!RBIGNUM(x)->sign) return -(long)num; - return num; -} - -#if HAVE_LONG_LONG - -static unsigned LONG_LONG -big2ull(x, type) - VALUE x; - char *type; -{ - long len = RBIGNUM(x)->len; - BDIGIT_DBL num; - BDIGIT *ds; - - if (len > sizeof(LONG_LONG)/sizeof(BDIGIT)) - rb_raise(rb_eRangeError, "bignum too big to convert into `%s'", type); - ds = BDIGITS(x); - num = 0; - while (len--) { - num = BIGUP(num); - num += ds[len]; - } - return num; -} - -unsigned LONG_LONG -rb_big2ull(x) - VALUE x; -{ - unsigned LONG_LONG num = big2ull(x, "unsigned long long"); - - if (!RBIGNUM(x)->sign) return -num; - return num; -} - -LONG_LONG -rb_big2ll(x) - VALUE x; -{ - unsigned LONG_LONG num = big2ull(x, "long long"); - - if ((LONG_LONG)num < 0 && (RBIGNUM(x)->sign - || (LONG_LONG)num != LLONG_MIN)) { - rb_raise(rb_eRangeError, "bignum too big to convert into `long long'"); - } - if (!RBIGNUM(x)->sign) return -(LONG_LONG)num; - return num; -} - -#endif /* HAVE_LONG_LONG */ - -static VALUE -dbl2big(d) - double d; -{ - long i = 0; - BDIGIT c; - BDIGIT *digits; - VALUE z; - double u = (d < 0)?-d:d; - - if (isinf(d)) { - rb_raise(rb_eFloatDomainError, d < 0 ? "-Infinity" : "Infinity"); - } - if (isnan(d)) { - rb_raise(rb_eFloatDomainError, "NaN"); - } - - while (!POSFIXABLE(u) || 0 != (long)u) { - u /= (double)(BIGRAD); - i++; - } - z = bignew(i, d>=0); - digits = BDIGITS(z); - while (i--) { - u *= BIGRAD; - c = (BDIGIT)u; - u -= c; - digits[i] = c; - } - - return z; -} - -VALUE -rb_dbl2big(d) - double d; -{ - return bignorm(dbl2big(d)); -} - -double -rb_big2dbl(x) - VALUE x; -{ - double d = 0.0; - long i = RBIGNUM(x)->len; - BDIGIT *ds = BDIGITS(x); - - while (i--) { - d = ds[i] + BIGRAD*d; - } - if (!RBIGNUM(x)->sign) d = -d; - return d; -} - -static VALUE -rb_big_to_f(x) - VALUE x; -{ - return rb_float_new(rb_big2dbl(x)); -} - -static VALUE -rb_big_cmp(x, y) - VALUE x, y; -{ - long xlen = RBIGNUM(x)->len; - - switch (TYPE(y)) { - case T_FIXNUM: - y = rb_int2big(FIX2LONG(y)); - break; - - case T_BIGNUM: - break; - - case T_FLOAT: - { - double d = rb_big2dbl(x); - - if (d == RFLOAT(y)->value) return INT2FIX(0); - if (d > RFLOAT(y)->value) return INT2FIX(1); - if (d < RFLOAT(y)->value) return INT2FIX(-1); - } - break; - - default: - return rb_num_coerce_bin(x, y); - } - - if (RBIGNUM(x)->sign > RBIGNUM(y)->sign) return INT2FIX(1); - if (RBIGNUM(x)->sign < RBIGNUM(y)->sign) return INT2FIX(-1); - if (xlen < RBIGNUM(y)->len) - return (RBIGNUM(x)->sign) ? INT2FIX(-1) : INT2FIX(1); - if (xlen > RBIGNUM(y)->len) - return (RBIGNUM(x)->sign) ? INT2FIX(1) : INT2FIX(-1); - - while(xlen-- && (BDIGITS(x)[xlen]==BDIGITS(y)[xlen])); - if (-1 == xlen) return INT2FIX(0); - return (BDIGITS(x)[xlen] > BDIGITS(y)[xlen]) ? - (RBIGNUM(x)->sign ? INT2FIX(1) : INT2FIX(-1)) : - (RBIGNUM(x)->sign ? INT2FIX(-1) : INT2FIX(1)); -} - -static VALUE -rb_big_eq(x, y) - VALUE x, y; -{ - switch (TYPE(y)) { - case T_FIXNUM: - y = rb_int2big(FIX2LONG(y)); - break; - case T_BIGNUM: - break; - case T_FLOAT: - return (rb_big2dbl(x) == RFLOAT(y)->value)?Qtrue:Qfalse; - default: - return Qfalse; - } - if (RBIGNUM(x)->sign != RBIGNUM(y)->sign) return Qfalse; - if (RBIGNUM(x)->len != RBIGNUM(y)->len) return Qfalse; - if (MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,RBIGNUM(y)->len) != 0) return Qfalse; - return Qtrue; -} - -static VALUE -rb_big_eql(x, y) - VALUE x, y; -{ - if (TYPE(y) != T_BIGNUM) return Qfalse; - if (RBIGNUM(x)->sign != RBIGNUM(y)->sign) return Qfalse; - if (RBIGNUM(x)->len != RBIGNUM(y)->len) return Qfalse; - if (MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,RBIGNUM(y)->len) != 0) return Qfalse; - return Qtrue; -} - -static VALUE -rb_big_uminus(x) - VALUE x; -{ - VALUE z = rb_big_clone(x); - - RBIGNUM(z)->sign = !RBIGNUM(x)->sign; - - return bignorm(z); -} - -static VALUE -rb_big_neg(x) - VALUE x; -{ - VALUE z = rb_big_clone(x); - long i = RBIGNUM(x)->len; - BDIGIT *ds = BDIGITS(z); - - if (!RBIGNUM(x)->sign) get2comp(z, Qtrue); - while (i--) ds[i] = ~ds[i]; - if (RBIGNUM(x)->sign) get2comp(z, Qfalse); - RBIGNUM(z)->sign = !RBIGNUM(z)->sign; - - return bignorm(z); -} - -static VALUE -bigsub(x, y) - VALUE x, y; -{ - VALUE z = 0; - BDIGIT *zds; - BDIGIT_DBL_SIGNED num; - long i; - - i = RBIGNUM(x)->len; - /* if x is larger than y, swap */ - if (RBIGNUM(x)->len < RBIGNUM(y)->len) { - z = x; x = y; y = z; /* swap x y */ - } - else if (RBIGNUM(x)->len == RBIGNUM(y)->len) { - while (i > 0) { - i--; - if (BDIGITS(x)[i] > BDIGITS(y)[i]) { - break; - } - if (BDIGITS(x)[i] < BDIGITS(y)[i]) { - z = x; x = y; y = z; /* swap x y */ - break; - } - } - } - - z = bignew(RBIGNUM(x)->len, (z == 0)?1:0); - zds = BDIGITS(z); - - for (i = 0, num = 0; i < RBIGNUM(y)->len; i++) { - num += (BDIGIT_DBL_SIGNED)BDIGITS(x)[i] - BDIGITS(y)[i]; - zds[i] = BIGLO(num); - num = BIGDN(num); - } - while (num && i < RBIGNUM(x)->len) { - num += BDIGITS(x)[i]; - zds[i++] = BIGLO(num); - num = BIGDN(num); - } - while (i < RBIGNUM(x)->len) { - zds[i] = BDIGITS(x)[i]; - i++; - } - - return z; -} - -static VALUE -bigadd(x, y, sign) - VALUE x, y; - char sign; -{ - VALUE z; - BDIGIT_DBL num; - long i, len; - - sign = (sign == RBIGNUM(y)->sign); - if (RBIGNUM(x)->sign != sign) { - if (sign) return bigsub(y, x); - return bigsub(x, y); - } - - if (RBIGNUM(x)->len > RBIGNUM(y)->len) { - len = RBIGNUM(x)->len + 1; - z = x; x = y; y = z; - } - else { - len = RBIGNUM(y)->len + 1; - } - z = bignew(len, sign); - - len = RBIGNUM(x)->len; - for (i = 0, num = 0; i < len; i++) { - num += (BDIGIT_DBL)BDIGITS(x)[i] + BDIGITS(y)[i]; - BDIGITS(z)[i] = BIGLO(num); - num = BIGDN(num); - } - len = RBIGNUM(y)->len; - while (num && i < len) { - num += BDIGITS(y)[i]; - BDIGITS(z)[i++] = BIGLO(num); - num = BIGDN(num); - } - while (i < len) { - BDIGITS(z)[i] = BDIGITS(y)[i]; - i++; - } - BDIGITS(z)[i] = (BDIGIT)num; - - return z; -} - -VALUE -rb_big_plus(x, y) - VALUE x, y; -{ - switch (TYPE(y)) { - case T_FIXNUM: - y = rb_int2big(FIX2LONG(y)); - /* fall through */ - case T_BIGNUM: - return bignorm(bigadd(x, y, 1)); - - case T_FLOAT: - return rb_float_new(rb_big2dbl(x) + RFLOAT(y)->value); - - default: - return rb_num_coerce_bin(x, y); - } -} - -VALUE -rb_big_minus(x, y) - VALUE x, y; -{ - switch (TYPE(y)) { - case T_FIXNUM: - y = rb_int2big(FIX2LONG(y)); - /* fall through */ - case T_BIGNUM: - return bignorm(bigadd(x, y, 0)); - - case T_FLOAT: - return rb_float_new(rb_big2dbl(x) - RFLOAT(y)->value); - - default: - return rb_num_coerce_bin(x, y); - } -} - -VALUE -rb_big_mul(x, y) - VALUE x, y; -{ - long i, j; - BDIGIT_DBL n = 0; - VALUE z; - BDIGIT *zds; - - if (FIXNUM_P(x)) x = rb_int2big(FIX2LONG(x)); - switch (TYPE(y)) { - case T_FIXNUM: - y = rb_int2big(FIX2LONG(y)); - break; - - case T_BIGNUM: - break; - - case T_FLOAT: - return rb_float_new(rb_big2dbl(x) * RFLOAT(y)->value); - - default: - return rb_num_coerce_bin(x, y); - } - - j = RBIGNUM(x)->len + RBIGNUM(y)->len + 1; - z = bignew(j, RBIGNUM(x)->sign==RBIGNUM(y)->sign); - zds = BDIGITS(z); - while (j--) zds[j] = 0; - for (i = 0; i < RBIGNUM(x)->len; i++) { - BDIGIT_DBL dd = BDIGITS(x)[i]; - if (dd == 0) continue; - n = 0; - for (j = 0; j < RBIGNUM(y)->len; j++) { - BDIGIT_DBL ee = n + (BDIGIT_DBL)dd * BDIGITS(y)[j]; - n = zds[i + j] + ee; - if (ee) zds[i + j] = BIGLO(n); - n = BIGDN(n); - } - if (n) { - zds[i + j] = n; - } - } - - return bignorm(z); -} - -static void -bigdivrem(x, y, divp, modp) - VALUE x, y; - VALUE *divp, *modp; -{ - long nx = RBIGNUM(x)->len, ny = RBIGNUM(y)->len; - long i, j; - VALUE yy, z; - BDIGIT *xds, *yds, *zds, *tds; - BDIGIT_DBL t2; - BDIGIT_DBL_SIGNED num; - BDIGIT dd, q; - - yds = BDIGITS(y); - if (ny == 0 && yds[0] == 0) rb_num_zerodiv(); - if (nx < ny || nx == ny && BDIGITS(x)[nx - 1] < BDIGITS(y)[ny - 1]) { - if (divp) *divp = rb_int2big(0); - if (modp) *modp = x; - return; - } - xds = BDIGITS(x); - if (ny == 1) { - dd = yds[0]; - z = rb_big_clone(x); - zds = BDIGITS(z); - t2 = 0; i = nx; - while (i--) { - t2 = BIGUP(t2) + zds[i]; - zds[i] = (BDIGIT)(t2 / dd); - t2 %= dd; - } - RBIGNUM(z)->sign = RBIGNUM(x)->sign==RBIGNUM(y)->sign; - if (modp) { - *modp = rb_uint2big((unsigned long)t2); - RBIGNUM(*modp)->sign = RBIGNUM(x)->sign; - } - if (divp) *divp = z; - return; - } - z = bignew(nx==ny?nx+2:nx+1, RBIGNUM(x)->sign==RBIGNUM(y)->sign); - zds = BDIGITS(z); - if (nx==ny) zds[nx+1] = 0; - while (!yds[ny-1]) ny--; - - dd = 0; - q = yds[ny-1]; - while ((q & (1<<(BITSPERDIG-1))) == 0) { - q <<= 1; - dd++; - } - if (dd) { - yy = rb_big_clone(y); - tds = BDIGITS(yy); - j = 0; - t2 = 0; - while (j<ny) { - t2 += (BDIGIT_DBL)yds[j]<<dd; - tds[j++] = BIGLO(t2); - t2 = BIGDN(t2); - } - yds = tds; - j = 0; - t2 = 0; - while (j<nx) { - t2 += (BDIGIT_DBL)xds[j]<<dd; - zds[j++] = BIGLO(t2); - t2 = BIGDN(t2); - } - zds[j] = (BDIGIT)t2; - } - else { - zds[nx] = 0; - j = nx; - while (j--) zds[j] = xds[j]; - } - - j = nx==ny?nx+1:nx; - do { - if (zds[j] == yds[ny-1]) q = BIGRAD-1; - else q = (BDIGIT)((BIGUP(zds[j]) + zds[j-1])/yds[ny-1]); - if (q) { - i = 0; num = 0; t2 = 0; - do { /* multiply and subtract */ - BDIGIT_DBL ee; - t2 += (BDIGIT_DBL)yds[i] * q; - ee = num - BIGLO(t2); - num = (BDIGIT_DBL)zds[j - ny + i] + ee; - if (ee) zds[j - ny + i] = BIGLO(num); - num = BIGDN(num); - t2 = BIGDN(t2); - } while (++i < ny); - num += zds[j - ny + i] - t2;/* borrow from high digit; don't update */ - while (num) { /* "add back" required */ - i = 0; num = 0; q--; - do { - BDIGIT_DBL ee = num + yds[i]; - num = (BDIGIT_DBL)zds[j - ny + i] + ee; - if (ee) zds[j - ny + i] = BIGLO(num); - num = BIGDN(num); - } while (++i < ny); - num--; - } - } - zds[j] = q; - } while (--j >= ny); - if (divp) { /* move quotient down in z */ - *divp = rb_big_clone(z); - zds = BDIGITS(*divp); - j = (nx==ny ? nx+2 : nx+1) - ny; - for (i = 0;i < j;i++) zds[i] = zds[i+ny]; - RBIGNUM(*divp)->len = i; - } - if (modp) { /* just normalize remainder */ - *modp = rb_big_clone(z); - zds = BDIGITS(*modp); - while (ny-- && !zds[ny]); ++ny; - if (dd) { - t2 = 0; i = ny; - while(i--) { - t2 = (t2 | zds[i]) >> dd; - q = zds[i]; - zds[i] = BIGLO(t2); - t2 = BIGUP(q); - } - } - RBIGNUM(*modp)->len = ny; - RBIGNUM(*modp)->sign = RBIGNUM(x)->sign; - } -} - -static void -bigdivmod(x, y, divp, modp) - VALUE x, y; - VALUE *divp, *modp; -{ - VALUE mod; - - bigdivrem(x, y, divp, &mod); - if (RBIGNUM(x)->sign != RBIGNUM(y)->sign && RBIGNUM(mod)->len > 0) { - if (divp) *divp = bigadd(*divp, rb_int2big(1), 0); - if (modp) *modp = bigadd(mod, y, 1); - } - else { - if (divp) *divp = *divp; - if (modp) *modp = mod; - } -} - -static VALUE -rb_big_div(x, y) - VALUE x, y; -{ - VALUE z; - - switch (TYPE(y)) { - case T_FIXNUM: - y = rb_int2big(FIX2LONG(y)); - break; - - case T_BIGNUM: - break; - - case T_FLOAT: - return rb_float_new(rb_big2dbl(x) / RFLOAT(y)->value); - - default: - return rb_num_coerce_bin(x, y); - } - bigdivmod(x, y, &z, 0); - - return bignorm(z); -} - - -static VALUE -rb_big_modulo(x, y) - VALUE x, y; -{ - VALUE z; - - switch (TYPE(y)) { - case T_FIXNUM: - y = rb_int2big(FIX2LONG(y)); - break; - - case T_BIGNUM: - break; - - default: - return rb_num_coerce_bin(x, y); - } - bigdivmod(x, y, 0, &z); - - return bignorm(z); -} - -static VALUE -rb_big_remainder(x, y) - VALUE x, y; -{ - VALUE z; - - switch (TYPE(y)) { - case T_FIXNUM: - y = rb_int2big(FIX2LONG(y)); - break; - - case T_BIGNUM: - break; - - default: - return rb_num_coerce_bin(x, y); - } - bigdivrem(x, y, 0, &z); - - return bignorm(z); -} - -VALUE -rb_big_divmod(x, y) - VALUE x, y; -{ - VALUE div, mod; - - switch (TYPE(y)) { - case T_FIXNUM: - y = rb_int2big(FIX2LONG(y)); - break; - - case T_BIGNUM: - break; - - default: - return rb_num_coerce_bin(x, y); - } - bigdivmod(x, y, &div, &mod); - - return rb_assoc_new(bignorm(div), bignorm(mod)); -} - -VALUE -rb_big_pow(x, y) - VALUE x, y; -{ - double d; - long yy; - - if (y == INT2FIX(0)) return INT2FIX(1); - switch (TYPE(y)) { - case T_FLOAT: - d = RFLOAT(y)->value; - break; - - case T_BIGNUM: - rb_warn("in a**b, b may be too big"); - d = rb_big2dbl(y); - break; - - case T_FIXNUM: - yy = NUM2LONG(y); - if (yy > 0) { - VALUE z; - - z = x; - for (;;) { - yy = yy - 1; - if (yy == 0) break; - while (yy % 2 == 0) { - yy = yy / 2; - x = rb_big_mul(x, x); - } - z = rb_big_mul(z, x); - } - if (!FIXNUM_P(z)) z = bignorm(z); - return z; - } - d = (double)yy; - break; - - default: - return rb_num_coerce_bin(x, y); - } - return rb_float_new(pow(rb_big2dbl(x), d)); -} - -VALUE -rb_big_and(x, y) - VALUE x, y; -{ - VALUE z; - BDIGIT *ds1, *ds2, *zds; - long i, l1, l2; - char sign; - - if (FIXNUM_P(y)) { - y = rb_int2big(FIX2LONG(y)); - } - else { - Check_Type(y, T_BIGNUM); - } - - if (!RBIGNUM(y)->sign) { - y = rb_big_clone(y); - get2comp(y, Qtrue); - } - if (!RBIGNUM(x)->sign) { - x = rb_big_clone(x); - get2comp(x, Qtrue); - } - if (RBIGNUM(x)->len > RBIGNUM(y)->len) { - l1 = RBIGNUM(y)->len; - l2 = RBIGNUM(x)->len; - ds1 = BDIGITS(y); - ds2 = BDIGITS(x); - sign = RBIGNUM(y)->sign; - } - else { - l1 = RBIGNUM(x)->len; - l2 = RBIGNUM(y)->len; - ds1 = BDIGITS(x); - ds2 = BDIGITS(y); - sign = RBIGNUM(x)->sign; - } - z = bignew(l2, RBIGNUM(x)->sign || RBIGNUM(y)->sign); - zds = BDIGITS(z); - - for (i=0; i<l1; i++) { - zds[i] = ds1[i] & ds2[i]; - } - for (; i<l2; i++) { - zds[i] = sign?0:ds2[i]; - } - if (!RBIGNUM(z)->sign) get2comp(z, Qfalse); - return bignorm(z); -} - -VALUE -rb_big_or(x, y) - VALUE x, y; -{ - VALUE z; - BDIGIT *ds1, *ds2, *zds; - long i, l1, l2; - char sign; - - if (FIXNUM_P(y)) { - y = rb_int2big(FIX2LONG(y)); - } - else { - Check_Type(y, T_BIGNUM); - } - - if (!RBIGNUM(y)->sign) { - y = rb_big_clone(y); - get2comp(y, Qtrue); - } - if (!RBIGNUM(x)->sign) { - x = rb_big_clone(x); - get2comp(x, Qtrue); - } - if (RBIGNUM(x)->len > RBIGNUM(y)->len) { - l1 = RBIGNUM(y)->len; - l2 = RBIGNUM(x)->len; - ds1 = BDIGITS(y); - ds2 = BDIGITS(x); - sign = RBIGNUM(y)->sign; - } - else { - l1 = RBIGNUM(x)->len; - l2 = RBIGNUM(y)->len; - ds1 = BDIGITS(x); - ds2 = BDIGITS(y); - sign = RBIGNUM(x)->sign; - } - z = bignew(l2, RBIGNUM(x)->sign && RBIGNUM(y)->sign); - zds = BDIGITS(z); - - for (i=0; i<l1; i++) { - zds[i] = ds1[i] | ds2[i]; - } - for (; i<l2; i++) { - zds[i] = sign?ds2[i]:(BIGRAD-1); - } - if (!RBIGNUM(z)->sign) get2comp(z, Qfalse); - - return bignorm(z); -} - -VALUE -rb_big_xor(x, y) - VALUE x, y; -{ - VALUE z; - BDIGIT *ds1, *ds2, *zds; - long i, l1, l2; - char sign; - - if (FIXNUM_P(y)) { - y = rb_int2big(FIX2LONG(y)); - } - else { - Check_Type(y, T_BIGNUM); - } - - if (!RBIGNUM(y)->sign) { - y = rb_big_clone(y); - get2comp(y, Qtrue); - } - if (!RBIGNUM(x)->sign) { - x = rb_big_clone(x); - get2comp(x, Qtrue); - } - if (RBIGNUM(x)->len > RBIGNUM(y)->len) { - l1 = RBIGNUM(y)->len; - l2 = RBIGNUM(x)->len; - ds1 = BDIGITS(y); - ds2 = BDIGITS(x); - sign = RBIGNUM(y)->sign; - } - else { - l1 = RBIGNUM(x)->len; - l2 = RBIGNUM(y)->len; - ds1 = BDIGITS(x); - ds2 = BDIGITS(y); - sign = RBIGNUM(x)->sign; - } - RBIGNUM(x)->sign = RBIGNUM(x)->sign?1:0; - RBIGNUM(y)->sign = RBIGNUM(y)->sign?1:0; - z = bignew(l2, !(RBIGNUM(x)->sign ^ RBIGNUM(y)->sign)); - zds = BDIGITS(z); - - for (i=0; i<l1; i++) { - zds[i] = ds1[i] ^ ds2[i]; - } - for (; i<l2; i++) { - zds[i] = sign?ds2[i]:~ds2[i]; - } - if (!RBIGNUM(z)->sign) get2comp(z, Qfalse); - - return bignorm(z); -} - -static VALUE rb_big_rshift _((VALUE,VALUE)); - -VALUE -rb_big_lshift(x, y) - VALUE x, y; -{ - BDIGIT *xds, *zds; - int shift = NUM2INT(y); - int s1 = shift/BITSPERDIG; - int s2 = shift%BITSPERDIG; - VALUE z; - BDIGIT_DBL num = 0; - long len, i; - - if (shift < 0) return rb_big_rshift(x, INT2FIX(-shift)); - len = RBIGNUM(x)->len; - z = bignew(len+s1+1, RBIGNUM(x)->sign); - zds = BDIGITS(z); - for (i=0; i<s1; i++) { - *zds++ = 0; - } - xds = BDIGITS(x); - for (i=0; i<len; i++) { - num = num | (BDIGIT_DBL)*xds++<<s2; - *zds++ = BIGLO(num); - num = BIGDN(num); - } - *zds = BIGLO(num); - return bignorm(z); -} - -static VALUE -rb_big_rshift(x, y) - VALUE x, y; -{ - BDIGIT *xds, *zds; - int shift = NUM2INT(y); - int s1 = shift/BITSPERDIG; - int s2 = shift%BITSPERDIG; - VALUE z; - BDIGIT_DBL num = 0; - long i = RBIGNUM(x)->len; - long j; - - if (shift < 0) return rb_big_lshift(x, INT2FIX(-shift)); - - if (s1 > RBIGNUM(x)->len) { - if (RBIGNUM(x)->sign) - return INT2FIX(0); - else - return INT2FIX(-1); - } - if (!RBIGNUM(x)->sign) { - x = rb_big_clone(x); - get2comp(x, Qtrue); - } - xds = BDIGITS(x); - i = RBIGNUM(x)->len; j = i - s1; - z = bignew(j, RBIGNUM(x)->sign); - zds = BDIGITS(z); - while (i--, j--) { - num = (num | xds[i]) >> s2; - zds[j] = BIGLO(num); - num = BIGUP(xds[i]); - } - if (!RBIGNUM(x)->sign) { - get2comp(z, Qfalse); - } - return bignorm(z); -} - -static VALUE -rb_big_aref(x, y) - VALUE x, y; -{ - BDIGIT *xds; - int shift; - int s1, s2; - - if (TYPE(y) == T_BIGNUM) { - if (!RBIGNUM(y)->sign || RBIGNUM(x)->sign) - return INT2FIX(0); - return INT2FIX(1); - } - shift = NUM2INT(y); - if (shift < 0) return INT2FIX(0); - s1 = shift/BITSPERDIG; - s2 = shift%BITSPERDIG; - - if (!RBIGNUM(x)->sign) { - if (s1 >= RBIGNUM(x)->len) return INT2FIX(1); - x = rb_big_clone(x); - get2comp(x, Qtrue); - } - else { - if (s1 >= RBIGNUM(x)->len) return INT2FIX(0); - } - xds = BDIGITS(x); - if (xds[s1] & (1<<s2)) - return INT2FIX(1); - return INT2FIX(0); -} - -static VALUE -rb_big_hash(x) - VALUE x; -{ - long i, len, key; - BDIGIT *digits; - - key = 0; digits = BDIGITS(x); len = RBIGNUM(x)->len; - for (i=0; i<len; i++) { - key ^= *digits++; - } - return INT2FIX(key); -} - -static VALUE -rb_big_coerce(x, y) - VALUE x, y; -{ - if (FIXNUM_P(y)) { - return rb_assoc_new(rb_int2big(FIX2LONG(y)), x); - } - else { - rb_raise(rb_eTypeError, "Can't coerce %s to Bignum", - rb_class2name(CLASS_OF(y))); - } - /* not reached */ - return Qnil; -} - -static VALUE -rb_big_abs(x) - VALUE x; -{ - if (!RBIGNUM(x)->sign) { - x = rb_big_clone(x); - RBIGNUM(x)->sign = 1; - } - return x; -} - -/* !!!warnig!!!! - this is not really a random number!! -*/ - -VALUE -rb_big_rand(max, rand) - VALUE max; - double rand; -{ - VALUE v; - long len; - - len = RBIGNUM(max)->len; - v = bignew(len,1); - while (len--) { - BDIGITS(v)[len] = ((BDIGIT)~0) * rand; - } - - return rb_big_modulo((VALUE)v, max); -} - -static VALUE -rb_big_size(big) - VALUE big; -{ - return INT2FIX(RBIGNUM(big)->len*sizeof(BDIGIT)); -} - -static VALUE -rb_big_zero_p(big) - VALUE big; -{ - return Qfalse; -} - -void -Init_Bignum() -{ - rb_cBignum = rb_define_class("Bignum", rb_cInteger); - - rb_define_method(rb_cBignum, "to_s", rb_big_to_s, -1); - rb_define_method(rb_cBignum, "coerce", rb_big_coerce, 1); - rb_define_method(rb_cBignum, "-@", rb_big_uminus, 0); - rb_define_method(rb_cBignum, "+", rb_big_plus, 1); - rb_define_method(rb_cBignum, "-", rb_big_minus, 1); - rb_define_method(rb_cBignum, "*", rb_big_mul, 1); - rb_define_method(rb_cBignum, "/", rb_big_div, 1); - rb_define_method(rb_cBignum, "%", rb_big_modulo, 1); - rb_define_method(rb_cBignum, "divmod", rb_big_divmod, 1); - rb_define_method(rb_cBignum, "modulo", rb_big_modulo, 1); - rb_define_method(rb_cBignum, "remainder", rb_big_remainder, 1); - rb_define_method(rb_cBignum, "**", rb_big_pow, 1); - rb_define_method(rb_cBignum, "&", rb_big_and, 1); - rb_define_method(rb_cBignum, "|", rb_big_or, 1); - rb_define_method(rb_cBignum, "^", rb_big_xor, 1); - rb_define_method(rb_cBignum, "~", rb_big_neg, 0); - rb_define_method(rb_cBignum, "<<", rb_big_lshift, 1); - rb_define_method(rb_cBignum, ">>", rb_big_rshift, 1); - rb_define_method(rb_cBignum, "[]", rb_big_aref, 1); - - rb_define_method(rb_cBignum, "<=>", rb_big_cmp, 1); - rb_define_method(rb_cBignum, "==", rb_big_eq, 1); - rb_define_method(rb_cBignum, "===", rb_big_eq, 1); - rb_define_method(rb_cBignum, "eql?", rb_big_eql, 1); - rb_define_method(rb_cBignum, "hash", rb_big_hash, 0); - rb_define_method(rb_cBignum, "to_f", rb_big_to_f, 0); - rb_define_method(rb_cBignum, "abs", rb_big_abs, 0); - rb_define_method(rb_cBignum, "size", rb_big_size, 0); - rb_define_method(rb_cBignum, "zero?", rb_big_zero_p, 0); -} |