summaryrefslogtreecommitdiff
path: root/bignum.c
diff options
context:
space:
mode:
Diffstat (limited to 'bignum.c')
-rw-r--r--bignum.c1121
1 files changed, 1121 insertions, 0 deletions
diff --git a/bignum.c b/bignum.c
new file mode 100644
index 0000000000..ce124a6362
--- /dev/null
+++ b/bignum.c
@@ -0,0 +1,1121 @@
+/************************************************
+
+ bignum.c -
+
+ $Author: matz $
+ $Date: 1994/06/27 15:48:21 $
+ created at: Fri Jun 10 00:48:55 JST 1994
+
+************************************************/
+
+#include "ruby.h"
+#include <ctype.h>
+
+extern VALUE C_Integer;
+VALUE C_Bignum;
+
+#define BDIGITS(x) RBIGNUM(x)->digits
+#define BITSPERDIG (sizeof(USHORT)*CHAR_BIT)
+#define BIGRAD (1L << BITSPERDIG)
+#define DIGSPERLONG ((UINT)(sizeof(long)/sizeof(USHORT)))
+#define BIGUP(x) ((unsigned long)(x) << BITSPERDIG)
+#define BIGDN(x) ((x) >> BITSPERDIG)
+#define BIGLO(x) ((x) & (BIGRAD-1))
+
+#define MAX(a,b) ((a)>(b)?(a):(b))
+#define MIN(a,b) ((a)<(b)?(a):(b))
+
+static VALUE
+bignew_1(class, len, sign)
+ VALUE class;
+ UINT len;
+ char sign;
+{
+ NEWOBJ(big, struct RBignum);
+ OBJSETUP(big, C_Bignum, T_BIGNUM);
+ big->sign = sign;
+ big->len = len;
+ BDIGITS(big) = ALLOC_N(USHORT, len);
+
+ return (VALUE)big;
+}
+
+#define bignew(len,sign) bignew_1(C_Bignum,len,sign)
+
+static VALUE
+Fbig_new(class, y)
+ VALUE class;
+ struct RBignum *y;
+{
+ Check_Type(y, T_BIGNUM);
+ return bignew_1(class, y->len, y->sign);
+}
+
+VALUE
+Fbig_clone(x)
+ struct RBignum *x;
+{
+ VALUE z = bignew_1(CLASS_OF(x), x->len, x->sign);
+
+ bcopy(BDIGITS(x), BDIGITS(z), x->len*sizeof(USHORT));
+ return (VALUE)z;
+}
+
+void
+big_2comp(x) /* get 2's complement */
+ struct RBignum *x;
+{
+ UINT i = x->len;
+ USHORT *ds = BDIGITS(x);
+ long num;
+
+ while (i--) ds[i] = ~ds[i];
+ i = 0; num = 1;
+ do {
+ num += (long)ds[i];
+ ds[i++] = BIGLO(num);
+ num = BIGDN(num);
+ } while (i < x->len);
+}
+
+VALUE
+bignorm(x)
+ struct RBignum *x;
+{
+ UINT len = x->len;
+ USHORT *ds = BDIGITS(x);
+
+ while (len-- && !ds[len]) ;
+ x->len = ++len;
+ if (len*sizeof(USHORT) <= sizeof(VALUE)) {
+ long num = 0;
+ while (len--) {
+ num = BIGUP(num) + ds[len];
+ }
+ if (x->sign) {
+ if (POSFIXABLE(num)) return INT2FIX(num);
+ }
+ else if (NEGFIXABLE(-num)) return INT2FIX(-num);
+ }
+ return (VALUE)x;
+}
+
+VALUE
+uint2big(n)
+ UINT n;
+{
+ UINT i = 0;
+ USHORT *digits;
+ struct RBignum *big;
+
+ i = 0;
+ big = (struct RBignum*)bignew(DIGSPERLONG, 1);
+ digits = BDIGITS(big);
+ while (i < DIGSPERLONG) {
+ digits[i++] = BIGLO(n);
+ n = BIGDN(n);
+ }
+
+ i = DIGSPERLONG;
+ while (i-- && !digits[i]) ;
+ big->len = i+1;
+ return (VALUE)big;
+}
+
+VALUE
+int2big(n)
+ int n;
+{
+ int neg = 0;
+ struct RBignum *big;
+
+ if (n < 0) {
+ n = -n;
+ neg = 1;
+ }
+ big = (struct RBignum*)uint2big(n);
+ if (neg) {
+ big->sign = FALSE;
+ }
+ return (VALUE)big;
+}
+
+VALUE
+uint2inum(n)
+ UINT n;
+{
+ if (POSFIXABLE(n)) return INT2FIX(n);
+ return uint2big(n);
+}
+
+VALUE
+int2inum(n)
+ int n;
+{
+ if (FIXABLE(n)) return INT2FIX(n);
+ return int2big(n);
+}
+
+VALUE
+str2inum(str, base)
+ char *str;
+ int base;
+{
+ char sign = 1, c;
+ unsigned long num;
+ UINT len, blen = 1, i;
+ VALUE z;
+ USHORT *zds;
+
+ while (isspace(*str)) str++;
+ if (*str == '-') {
+ str++;
+ sign = 0;
+ }
+ if (base == 0) {
+ if (*str == '0') {
+ str++;
+ if (*str == 'x' || *str == 'X') {
+ str++;
+ base = 16;
+ }
+ else {
+ base = 8;
+ }
+ if (*str == '\0') return INT2FIX(0);
+ }
+ else {
+ base = 10;
+ }
+ }
+ len = strlen(str);
+ if (base == 8) {
+ len = 3*len*sizeof(char);
+ }
+ else { /* base == 10 or 16 */
+ len = 4*len*sizeof(char);
+ }
+
+ if (len <= (sizeof(VALUE)*CHAR_BIT)) {
+ int result = strtoul(str, Qnil, base);
+
+ if (!sign) result = -result;
+ if (FIXABLE(result)) return INT2FIX(result);
+ return int2big(result);
+ }
+ len = (len/(sizeof(USHORT)*CHAR_BIT))+1;
+
+ z = bignew(len, sign);
+ zds = BDIGITS(z);
+ for (i=len;i--;) zds[i]=0;
+ while (c = *str++) {
+ switch (c) {
+ case '0': case '1': case '2': case '3': case '4':
+ case '5': case '6': case '7': case '8': case '9':
+ c = c - '0';
+ break;
+ case 'a': case 'b': case 'c':
+ case 'd': case 'e': case 'f':
+ c = c - 'a' + 10;
+ break;
+ case 'A': case 'B': case 'C':
+ case 'D': case 'E': case 'F':
+ c = c - 'A' + 10;
+ break;
+ default:
+ c = base;
+ break;
+ }
+ if (c >= base) break;
+ i = 0;
+ num = c;
+ for (;;) {
+ while (i<blen) {
+ num += zds[i]*base;
+ zds[i++] = BIGLO(num);
+ num = BIGDN(num);
+ }
+ if (num) {
+ blen++;
+ continue;
+ }
+ break;
+ }
+ }
+ return bignorm(z);
+}
+
+static char hexmap[] = "0123456789abcdef";
+VALUE
+big2str(x, base)
+ struct RBignum *x;
+ int base;
+{
+ VALUE t;
+ USHORT *ds;
+ UINT i, j, hbase;
+ VALUE ss;
+ char *s, c;
+
+ if (FIXNUM_P(x)) {
+ return fix2str(x, base);
+ }
+ i = x->len;
+ if (x->len == 0) return str_new2("0");
+ if (base == 10) {
+ j = (sizeof(USHORT)/sizeof(char)*CHAR_BIT*i*241L)/800+2;
+ hbase = 10000;
+ }
+ else if (base == 16) {
+ j = (sizeof(USHORT)/sizeof(char)*CHAR_BIT*i)/4+2;
+ hbase = 0x10000;
+ }
+ else if (base == 8) {
+ j = (sizeof(USHORT)/sizeof(char)*CHAR_BIT*i)+2;
+ hbase = 010000;
+ }
+ else if (base == 2) {
+ j = (sizeof(USHORT)*CHAR_BIT*i)+2;
+ hbase = 020;
+ }
+ else {
+ Fail("bignum cannot treat base %d", base);
+ }
+
+ GC_LINK;
+ GC_PRO3(t, Fbig_clone(x));
+ ds = BDIGITS(t);
+ GC_PRO3(ss, str_new(0, j));
+ s = RSTRING(ss)->ptr;
+
+ s[0] = x->sign ? '+' : '-';
+ while (i && j) {
+ int k = i;
+ unsigned long num = 0;
+ while (k--) {
+ num = BIGUP(num) + ds[k];
+ ds[k] = num / hbase;
+ num %= hbase;
+ }
+ if (ds[i-1] == 0) i--;
+ k = 4;
+ while (k--) {
+ c = num % base;
+ s[--j] = hexmap[(int)c];
+ num /= base;
+ if (i == 0 && num == 0) break;
+ }
+ }
+ while (s[j] == '0') j++;
+ RSTRING(ss)->len -= x->sign?j:j-1;
+ memmove(x->sign?s:s+1, s+j, RSTRING(ss)->len);
+ s[RSTRING(ss)->len] = '\0';
+ GC_UNLINK;
+ return ss;
+}
+
+static VALUE
+Fbig_to_s(x)
+ struct RBignum *x;
+{
+ return big2str(x, 10);
+}
+
+int
+big2int(x)
+ struct RBignum *x;
+{
+ unsigned long num;
+ UINT len = x->len;
+ USHORT *ds;
+
+ if (len > sizeof(long)/sizeof(USHORT))
+ Fail("Bignum too big to convert into fixnum");
+ ds = BDIGITS(x);
+ num = 0;
+ while (len--) {
+ num = BIGUP(num);
+ num += ds[len];
+ }
+ if (!x->sign) return -num;
+ return num;
+}
+
+VALUE
+Fbig_to_i(x)
+ VALUE x;
+{
+ int v = big2int(x);
+
+ if (FIXABLE(v)) {
+ return INT2FIX(v);
+ }
+ return x;
+}
+
+VALUE
+dbl2big(d)
+ double d;
+{
+ UINT i = 0;
+ long c;
+ USHORT *digits;
+ VALUE z;
+ double u = (d < 0)?-d:d;
+
+ while (0 != floor(u)) {
+ u /= BIGRAD;
+ i++;
+ }
+ GC_LINK;
+ GC_PRO3(z, bignew(i, d>=0));
+ digits = BDIGITS(z);
+ while (i--) {
+ u *= BIGRAD;
+ c = floor(u);
+ u -= c;
+ digits[i] = c;
+ }
+ GC_UNLINK;
+ return bignorm(z);
+}
+
+double
+big2dbl(x)
+ struct RBignum *x;
+{
+ double d = 0.0;
+ UINT i = x->len;
+ USHORT *ds = BDIGITS(x);
+
+ while (i--) d = ds[i] + BIGRAD*d;
+ if (!x->sign) d = -d;
+ return d;
+}
+
+VALUE
+Fbig_to_f(x)
+ VALUE x;
+{
+ return float_new(big2dbl(x));
+}
+
+static VALUE
+Fbig_uminus(x)
+ struct RBignum *x;
+{
+ VALUE z = Fbig_clone(x);
+
+ RBIGNUM(z)->sign = !x->sign;
+
+ return bignorm(z);
+}
+
+static VALUE
+bigadd(x, y, sign)
+ struct RBignum *x, *y;
+ char sign;
+{
+ struct RBignum *z;
+ USHORT *zds;
+ long num;
+ UINT i, len;
+
+ len = MAX(x->len, y->len) + 1;
+ z = (struct RBignum*)bignew(len, sign==y->sign);
+ zds = BDIGITS(z);
+
+ i = len;
+ while (i--) zds[i] = 0;
+ i = y->len;
+ while (i--) zds[i] = BDIGITS(y)[i];
+
+ GC_LINK;
+ GC_PRO(z);
+ i = 0; num = 0;
+ if (x->sign == z->sign) {
+ do {
+ num += (long)zds[i] + BDIGITS(x)[i];
+ zds[i++] = BIGLO(num);
+ num = BIGDN(num);
+ } while (i < x->len);
+ if (num) {
+ while (i < y->len) {
+ num += zds[i];
+ zds[i++] = BIGLO(num);
+ num = BIGDN(num);
+ }
+ BDIGITS(z)[i] = num;
+ }
+ }
+ else {
+ do {
+ num += (long)zds[i] - BDIGITS(x)[i];
+ if (num < 0) {
+ zds[i] = num + BIGRAD;
+ num = -1;
+ }
+ else {
+ zds[i] = BIGLO(num);
+ num = 0;
+ }
+ } while (++i < x->len);
+ if (num && x->len == y->len) {
+ num = 1; i = 0;
+ z->sign = 1;
+ do {
+ num += (BIGRAD-1) - zds[i];
+ zds[i++] = BIGLO(num);
+ num = BIGDN(num);
+ } while (i < y->len);
+ }
+ else while (i < y->len) {
+ num += zds[i];
+ if (num < 0) {
+ zds[i++] = num + BIGRAD;
+ num = -1;
+ }
+ else {
+ zds[i++] = BIGLO(num);
+ num = 0;
+ }
+ }
+ }
+ GC_UNLINK;
+ return bignorm(z);
+}
+
+VALUE
+Fbig_plus(x, y)
+ VALUE x, y;
+{
+ VALUE z;
+
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = int2big(FIX2INT(y));
+ else {
+ Check_Type(x, T_BIGNUM);
+ }
+ z = bigadd(x, y, 1);
+ GC_UNLINK;
+ return z;
+}
+
+VALUE
+Fbig_minus(x, y)
+ VALUE x, y;
+{
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = int2big(FIX2INT(y));
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+ x = bigadd(x, y, 0);
+ GC_UNLINK;
+
+ return x;
+}
+
+VALUE
+Fbig_mul(x, y)
+ struct RBignum *x, *y;
+{
+ UINT i = 0, j;
+ unsigned long n = 0;
+ VALUE z;
+ USHORT *zds;
+
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = (struct RBignum*)int2big(FIX2INT(y));
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+
+ j = x->len + y->len + 1;
+ z = bignew(j, x->sign==y->sign);
+ zds = BDIGITS(z);
+ while (j--) zds[j] = 0;
+ do {
+ j = 0;
+ if (BDIGITS(x)[i]) {
+ do {
+ n += zds[i + j] + ((unsigned long)BDIGITS(x)[i]*BDIGITS(y)[j]);
+ zds[i + j++] = BIGLO(n);
+ n = BIGDN(n);
+ } while (j < y->len);
+ if (n) {
+ zds[i + j] = n;
+ n = 0;
+ }
+ }
+ } while (++i < x->len);
+ GC_UNLINK;
+
+ return bignorm(z);
+}
+
+static void
+bigdivmod(x, y, div, mod)
+ struct RBignum *x, *y;
+ VALUE *div, *mod;
+{
+ UINT nx = x->len, ny = y->len, i, j;
+ VALUE z;
+ USHORT *xds, *yds, *zds, *tds;
+ unsigned long t2;
+ long num;
+ USHORT dd, q;
+
+ yds = BDIGITS(y);
+ if (ny == 0 && yds[0] == 0) Fail("divided by 0");
+ if (nx < ny) {
+ if (div) *div = INT2FIX(0);
+ if (mod) *mod = bignorm(x);
+ return;
+ }
+ xds = BDIGITS(x);
+ if (ny == 1) {
+ dd = yds[0];
+ GC_LINK;
+ GC_PRO3(z, Fbig_clone(x));
+ zds = BDIGITS(z);
+ t2 = 0; i = nx;
+ while(i--) {
+ t2 = BIGUP(t2) + zds[i];
+ zds[i] = t2 / dd;
+ t2 %= dd;
+ }
+ if (div) *div = bignorm(z);
+ if (mod) {
+ if (!y->sign) t2 = -t2;
+ *mod = FIX2INT(t2);
+ }
+ GC_UNLINK;
+ return;
+ }
+ GC_LINK;
+ GC_PRO3(z, bignew(nx==ny?nx+2:nx+1, x->sign==y->sign));
+ zds = BDIGITS(z);
+ if (nx==ny) zds[nx+1] = 0;
+ while (!yds[ny-1]) ny--;
+ if ((dd = BIGRAD/(yds[ny-1]+1)) != 1) {
+ GC_PRO3(y, (struct RBignum*)Fbig_clone(y));
+ tds = BDIGITS(y);
+ j = 0;
+ num = 0;
+ while (j<ny) {
+ num += (unsigned long)yds[j]*dd;
+ tds[j++] = BIGLO(num);
+ num = BIGDN(num);
+ }
+ yds = tds;
+ j = 0;
+ num = 0;
+ while (j<nx) {
+ num += (unsigned long)xds[j]*dd;
+ zds[j++] = BIGLO(num);
+ num = BIGDN(num);
+ }
+ zds[j] = num;
+ }
+ 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 = (BIGUP(zds[j]) + zds[j-1])/yds[ny-1];
+ if (q) {
+ i = 0; num = 0; t2 = 0;
+ do { /* multiply and subtract */
+ t2 += (unsigned long)yds[i] * q;
+ num += zds[j - ny + i] - BIGLO(t2);
+ if (num < 0) {
+ zds[j - ny + i] = num + BIGRAD;
+ num = -1;
+ }
+ else {
+ zds[j - ny + i] = num;
+ num = 0;
+ }
+ 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 {
+ num += (long) zds[j - ny + i] + yds[i];
+ zds[j - ny + i] = BIGLO(num);
+ num = BIGDN(num);
+ } while (++i < ny);
+ num--;
+ }
+ }
+ zds[j] = q;
+ } while (--j >= ny);
+ if (div) { /* move quotient down in z */
+ *div = Fbig_clone(z);
+ zds = BDIGITS(*div);
+ j = (nx==ny ? nx+2 : nx+1) - ny;
+ for (i = 0;i < j;i++) zds[i] = zds[i+ny];
+ RBIGNUM(*div)->len = i;
+ *div = bignorm(*div);
+ }
+ if (mod) { /* just normalize remainder */
+ *mod = Fbig_clone(z);
+ if (dd) {
+ zds = BDIGITS(*mod);
+ t2 = 0; i = ny;
+ while(i--) {
+ t2 = BIGUP(t2) + zds[i];
+ zds[i] = t2 / dd;
+ t2 %= dd;
+ }
+ }
+ RBIGNUM(*mod)->len = ny;
+ RBIGNUM(*mod)->sign = y->sign;
+ *mod = bignorm(*mod);
+ }
+ GC_UNLINK;
+}
+
+static VALUE
+Fbig_div(x, y)
+ VALUE x, y;
+{
+ VALUE z;
+
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = int2big(FIX2INT(y));
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+ bigdivmod(x, y, &z, Qnil);
+ GC_UNLINK;
+ return z;
+}
+
+static VALUE
+Fbig_mod(x, y)
+ VALUE x, y;
+{
+ VALUE z;
+
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = int2big(FIX2INT(y));
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+ bigdivmod(x, y, Qnil, &z);
+ GC_UNLINK;
+ return z;
+}
+
+static VALUE
+Fbig_divmod(x, y)
+ VALUE x, y;
+{
+ VALUE div, mod;
+
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = int2big(FIX2INT(y));
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+ bigdivmod(x, y, &div, &mod);
+ GC_UNLINK;
+
+ return assoc_new(div, mod);;
+}
+
+static VALUE
+Fbig_pow(x, y)
+ VALUE x, y;
+{
+ extern double pow();
+ double d1, d2;
+
+ GC_LINK;
+ GC_PRO(y);
+ if (FIXNUM_P(y)) y = int2big(FIX2INT(y));
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+
+ d1 = big2dbl(x);
+ d2 = big2dbl(y);
+ d1 = pow(d1, d2);
+ GC_UNLINK;
+
+ return dbl2big(d1);
+}
+
+VALUE
+Fbig_and(x, y)
+ struct RBignum *x, *y;
+{
+ VALUE z;
+ USHORT *ds1, *ds2, *zds;
+ UINT i, l1, l2;
+ char sign;
+
+ if (FIXNUM_P(y)) {
+ y = (struct RBignum*)int2big(FIX2INT(y));
+ }
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+
+ GC_LINK;
+ GC_PRO(y);
+ if (!y->sign) {
+ y = (struct RBignum*)Fbig_clone(y);
+ big_2comp(y);
+ }
+ if (!x->sign) {
+ GC_PRO3(x, (struct RBignum*)Fbig_clone(x));
+ big_2comp(x);
+ }
+ if (x->len > y->len) {
+ l1 = y->len;
+ l2 = x->len;
+ ds1 = BDIGITS(y);
+ ds2 = BDIGITS(x);
+ sign = y->sign;
+ }
+ else {
+ l1 = x->len;
+ l2 = y->len;
+ ds1 = BDIGITS(x);
+ ds2 = BDIGITS(y);
+ sign = x->sign;
+ }
+ z = bignew(l2, x->sign && 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) big_2comp(z);
+ GC_UNLINK;
+ return bignorm(z);
+}
+
+VALUE
+Fbig_or(x, y)
+ struct RBignum *x, *y;
+{
+ VALUE z;
+ USHORT *ds1, *ds2, *zds;
+ UINT i, l1, l2;
+ char sign;
+
+ if (FIXNUM_P(y)) {
+ y = (struct RBignum*)int2big(FIX2INT(y));
+ }
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+
+ GC_LINK;
+ GC_PRO(y);
+ if (!y->sign) {
+ y = (struct RBignum*)Fbig_clone(y);
+ big_2comp(y);
+ }
+ if (!x->sign) {
+ GC_PRO3(x, (struct RBignum*)Fbig_clone(x));
+ big_2comp(x);
+ }
+ if (x->len > y->len) {
+ l1 = y->len;
+ l2 = x->len;
+ ds1 = BDIGITS(y);
+ ds2 = BDIGITS(x);
+ sign = y->sign;
+ }
+ else {
+ l1 = x->len;
+ l2 = y->len;
+ ds1 = BDIGITS(x);
+ ds2 = BDIGITS(y);
+ sign = x->sign;
+ }
+ z = bignew(l2, x->sign || 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) big_2comp(z);
+ GC_UNLINK;
+ return bignorm(z);
+}
+
+VALUE
+Fbig_xor(x, y)
+ struct RBignum *x, *y;
+{
+ VALUE z;
+ USHORT *ds1, *ds2, *zds;
+ UINT i, l1, l2;
+ char sign;
+
+ if (FIXNUM_P(y)) {
+ y = (struct RBignum*)int2big(FIX2INT(y));
+ }
+ else {
+ Check_Type(y, T_BIGNUM);
+ }
+
+ GC_LINK;
+ GC_PRO(y);
+ if (!y->sign) {
+ y = (struct RBignum*)Fbig_clone(y);
+ big_2comp(y);
+ }
+ if (!x->sign) {
+ GC_PRO3(x, (struct RBignum*)Fbig_clone(x));
+ big_2comp(x);
+ }
+ if (x->len > y->len) {
+ l1 = y->len;
+ l2 = x->len;
+ ds1 = BDIGITS(y);
+ ds2 = BDIGITS(x);
+ sign = y->sign;
+ }
+ else {
+ l1 = x->len;
+ l2 = y->len;
+ ds1 = BDIGITS(x);
+ ds2 = BDIGITS(y);
+ sign = x->sign;
+ }
+ x->sign = x->sign?1:0;
+ y->sign = y->sign?1:0;
+ z = bignew(l2, !(x->sign ^ 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) big_2comp(z);
+ GC_UNLINK;
+ return bignorm(z);
+}
+
+static VALUE
+Fbig_neg(x)
+ struct RBignum *x;
+{
+ VALUE z = Fbig_clone(x);
+ UINT i = x->len;
+ USHORT *ds = BDIGITS(z);
+
+ if (!x->sign) big_2comp(z);
+ while (i--) ds[i] = ~ds[i];
+ if (x->sign) big_2comp(z);
+ RBIGNUM(z)->sign = !RBIGNUM(z)->sign;
+
+ return bignorm(z);
+}
+
+static VALUE Fbig_rshift();
+
+VALUE
+Fbig_lshift(x, y)
+ struct RBignum *x;
+ VALUE y;
+{
+ USHORT *xds, *zds;
+ UINT shift = NUM2INT(y);
+ UINT s1 = shift/(sizeof(USHORT)*CHAR_BIT);
+ UINT s2 = shift%(sizeof(USHORT)*CHAR_BIT);
+ VALUE z;
+ unsigned long num = 0;
+ UINT len, i;
+
+ if (shift < 0) return Fbig_rshift(x, INT2FIX(-shift));
+ xds = BDIGITS(x);
+ len = x->len;
+ z = bignew(len+s1+1, x->sign);
+ zds = BDIGITS(z);
+ for (i=0; i<s1; i++) {
+ *zds++ = 0;
+ }
+ for (i=0; i<len; i++) {
+ num = num | *xds++<<s2;
+ *zds++ = BIGLO(num);
+ num = BIGDN(num);
+ }
+ *zds = BIGLO(num);
+ return bignorm(z);
+}
+
+static VALUE
+Fbig_rshift(x, y)
+ struct RBignum *x;
+ VALUE y;
+{
+ USHORT *xds, *zds;
+ UINT shift = NUM2INT(y);
+ UINT s1 = shift/(sizeof(USHORT)*CHAR_BIT);
+ UINT s2 = shift%(sizeof(USHORT)*CHAR_BIT);
+ VALUE z;
+ unsigned long num = 0;
+ UINT i = x->len, j;
+
+ if (shift < 0) return Fbig_lshift(x, INT2FIX(-shift));
+ if (s1 > x->len) {
+ if (x->sign)
+ return INT2FIX(0);
+ else
+ return INT2FIX(-1);
+ }
+ xds = BDIGITS(x);
+ i = x->len; j = i - s1;
+ z = bignew(j, x->sign);
+ zds = BDIGITS(z);
+ while (i--, j--) {
+ num = (num | xds[i]) >> s2;
+ zds[j] = BIGLO(num);
+ num = BIGUP(xds[i]);
+ }
+ return bignorm(z);
+}
+
+static VALUE
+Fbig_aref(x, y)
+ struct RBignum *x;
+ VALUE y;
+{
+ USHORT *xds;
+ int shift = NUM2INT(y);
+ UINT s1, s2;
+
+ if (shift < 0) return INT2FIX(0);
+ s1 = shift/(sizeof(USHORT)*CHAR_BIT);
+ s2 = shift%(sizeof(USHORT)*CHAR_BIT);
+
+ if (!x->sign) {
+ if (s1 >= x->len) return INT2FIX(1);
+ x = (struct RBignum*)Fbig_clone(x);
+ big_2comp(x);
+ }
+ else {
+ if (s1 >= x->len) return INT2FIX(0);
+ }
+ xds = BDIGITS(x);
+ if (xds[s1] & (1<<s2))
+ return INT2FIX(1);
+ return INT2FIX(0);
+}
+
+static VALUE
+Fbig_cmp(x, y)
+ struct RBignum *x, *y;
+{
+ int xlen = x->len;
+
+ Check_Type(x, T_BIGNUM);
+ if (x->sign > y->sign) return INT2FIX(1);
+ if (x->sign < y->sign) return INT2FIX(-1);
+ if (xlen < y->len)
+ return (x->sign) ? INT2FIX(-1) : INT2FIX(1);
+ if (xlen > y->len)
+ return (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]) ?
+ (x->sign ? INT2FIX(1) : INT2FIX(-1)) :
+ (x->sign ? INT2FIX(-1) : INT2FIX(1));
+}
+
+static VALUE
+Fbig_hash(x)
+ struct RBignum *x;
+{
+ int i, len, key;
+ USHORT *digits;
+
+ key = 0; digits = BDIGITS(x);
+ for (i=0,len=x->len; i<x->len; i++) {
+ key ^= *digits++;
+ }
+ return INT2FIX(key);
+}
+
+static VALUE
+Fbig_coerce(x, y)
+ struct RBignum *x;
+ VALUE y;
+{
+ if (FIXNUM_P(y)) {
+ return int2big(FIX2INT(y));
+ }
+ else {
+ Fail("can't coerce %s to Bignum", rb_class2name(CLASS_OF(y)));
+ }
+ /* not reached */
+ return Qnil;
+}
+
+static VALUE
+Fbig_abs(x)
+ struct RBignum *x;
+{
+ if (!x->sign) {
+ x = (struct RBignum*)Fbig_clone(x);
+ x->sign = 1;
+ }
+ return (VALUE)x;
+}
+
+Init_Bignum()
+{
+ C_Bignum = rb_define_class("Bignum", C_Integer);
+ rb_define_single_method(C_Bignum, "new", Fbig_new, 1);
+ rb_define_method(C_Bignum, "clone", Fbig_clone, 0);
+ rb_define_method(C_Bignum, "to_s", Fbig_to_s, 0);
+ rb_define_method(C_Bignum, "coerce", Fbig_coerce, 1);
+ rb_define_method(C_Bignum, "-@", Fbig_uminus, 0);
+ rb_define_method(C_Bignum, "+", Fbig_plus, 1);
+ rb_define_method(C_Bignum, "-", Fbig_minus, 1);
+ rb_define_method(C_Bignum, "*", Fbig_mul, 1);
+ rb_define_method(C_Bignum, "/", Fbig_div, 1);
+ rb_define_method(C_Bignum, "%", Fbig_mod, 1);
+ rb_define_method(C_Bignum, "divmod", Fbig_divmod, 1);
+ rb_define_method(C_Bignum, "**", Fbig_pow, 1);
+ rb_define_method(C_Bignum, "&", Fbig_and, 1);
+ rb_define_method(C_Bignum, "|", Fbig_or, 1);
+ rb_define_method(C_Bignum, "^", Fbig_xor, 1);
+ rb_define_method(C_Bignum, "~", Fbig_neg, 0);
+ rb_define_method(C_Bignum, "<<", Fbig_lshift, 1);
+ rb_define_method(C_Bignum, ">>", Fbig_rshift, 1);
+ rb_define_method(C_Bignum, "[]", Fbig_aref, 1);
+
+ rb_define_method(C_Bignum, "<=>", Fbig_cmp, 1);
+ rb_define_method(C_Bignum, "hash", Fbig_hash, 0);
+ rb_define_method(C_Bignum, "to_i", Fbig_to_i, 0);
+ rb_define_method(C_Bignum, "to_f", Fbig_to_f, 0);
+ rb_define_method(C_Bignum, "abs_f", Fbig_abs, 0);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-27 13:29:44 +0000