Logo Search packages:      
Sourcecode: adanaxisgpl version File versions  Download package

bignum.c

//%Header {
/*****************************************************************************
 *
 * File: src/MushRuby/bignum.c (ruby)
 *
 * This file has been taken the ruby distribution and may have been modified.
 * For more information on the original see http://www.ruby-lang.org/.
 *
 * This file may contain original work and modifications by Andy Southgate.
 * In regard to these the author and his employer (Mushware Limited)
 * irrevocably waive all of their copyright rights vested in this particular
 * version of this file to the furthest extent permitted.  The author and
 * Mushware Limited also irrevocably waive any and all of their intellectual
 * property rights arising from said file and its modification and/or additions
 * that would otherwise restrict the rights of any party to use and/or
 * distribute the use of, the techniques and methods used herein.  A written
 * waiver can be obtained via http://www.mushware.com/.  This waiver does not
 * affect the rights of the original author or authors.
 *
 * This software carries NO WARRANTY of any kind from Andy Southgate or
 * Mushware Limited.
 *
 ****************************************************************************/
//%Header } SI6bp5tlsWuDYwOjp6bHEQ
/**********************************************************************

  bignum.c -

 
  $Date: 2006/04/21 00:10:43 $
  created at: Fri Jun 10 00:48:55 JST 1994

  Copyright (C) 1993-2003 Yukihiro Matsumoto

**********************************************************************/

#include "ruby.h"

#include <math.h>
#include <ctype.h>
#ifdef HAVE_IEEEFP_H
#include <ieeefp.h>
#endif

VALUE rb_cBignum;

#if defined __MINGW32__
#define USHORT _USHORT
#endif

#define BDIGITS(x) ((BDIGIT*)RBIGNUM(x)->digits)
#define BITSPERDIG (SIZEOF_BDIGITS*CHAR_BIT)
#define BIGRAD ((BDIGIT_DBL)1 << BITSPERDIG)
#define DIGSPERLONG ((unsigned int)(SIZEOF_LONG/SIZEOF_BDIGITS))
#if HAVE_LONG_LONG
# define DIGSPERLL ((unsigned int)(SIZEOF_LONG_LONG/SIZEOF_BDIGITS))
#endif
#define BIGUP(x) ((BDIGIT_DBL)(x) << BITSPERDIG)
#define BIGDN(x) RSHIFT(x,BITSPERDIG)
#define BIGLO(x) ((BDIGIT)((x) & (BIGRAD-1)))
#define BDIGMAX ((BDIGIT)-1)

#define BIGZEROP(x) (RBIGNUM(x)->len == 0 || (RBIGNUM(x)->len == 1 && BDIGITS(x)[0] == 0))

static VALUE
bignew_1(klass, len, sign)
    VALUE klass;
    long len;
    int sign;
{
    NEWOBJ(big, struct RBignum);
    OBJSETUP(big, klass, T_BIGNUM);
    big->sign = sign?1:0;
    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;
}

/* modify a bignum by 2's complement */
static void
get2comp(x)
    VALUE x;
{
    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 (num != 0) {
      REALLOC_N(RBIGNUM(x)->digits, BDIGIT, ++RBIGNUM(x)->len);
      ds = BDIGITS(x);
      ds[RBIGNUM(x)->len-1] = RBIGNUM(x)->sign ? ~0 : 1;
    }
}

void
rb_big_2comp(x)               /* get 2's complement */
    VALUE x;
{
    get2comp(x);
}

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_BDIGITS <= sizeof(VALUE)) {
          long num = 0;
          while (len--) {
            num = BIGUP(num) + ds[len];
          }
          if (num >= 0) {
            if (RBIGNUM(x)->sign) {
                if (POSFIXABLE(num)) return LONG2FIX(num);
            }
            else if (NEGFIXABLE(-(long)num)) return LONG2FIX(-(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;

    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 LONG2FIX(n);
    return rb_uint2big(n);
}

VALUE
rb_int2inum(n)
    long n;
{
    if (FIXABLE(n)) return LONG2FIX(n);
    return rb_int2big(n);
}

#ifdef HAVE_LONG_LONG

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;

      if (len > SIZEOF_LONG_LONG/SIZEOF_BDIGITS)
          rb_raise(rb_eRangeError, "bignum too big to convert into `quad int'");
      ds = BDIGITS(val);
      q = 0;
      while (len--) {
          q = BIGUP(q);
          q += ds[len];
      }
      if (!RBIGNUM(val)->sign) q = -q;
    }
    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;
    BDIGIT *digits;
    VALUE big;

    memcpy(&q, buf, SIZEOF_LONG_LONG);
    if (sign) {
      if (FIXABLE((LONG_LONG)q)) return LONG2FIX((LONG_LONG)q);
      if ((LONG_LONG)q < 0) {
          q = -(LONG_LONG)q;
          neg = 1;
      }
    }
    else {
      if (POSFIXABLE(q)) return LONG2FIX(q);
    }

    i = 0;
    big = bignew(DIGSPERLL, 1);
    digits = BDIGITS(big);
    while (i < DIGSPERLL) {
      digits[i++] = BIGLO(q);
      q = BIGDN(q);
    }

    i = DIGSPERLL;
    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_BDIGITS;
    if (len > QUAD_SIZE) {
      rb_raise(rb_eRangeError, "bignum too big to convert into `quad int'");
    }
    memcpy(buf, (char*)BDIGITS(val), len);
    if (!RBIGNUM(val)->sign) {
      len = QUAD_SIZE;
      while (len--) {
          *buf = ~*buf;
          buf++;
      }
    }
}

#define BNEG(b) (RSHIFT(((BDIGIT*)b)[QUAD_SIZE/SIZEOF_BDIGITS-1],BITSPERDIG-1) != 0)

VALUE
rb_quad_unpack(buf, sign)
    const char *buf;
    int sign;
{
    VALUE big = bignew(QUAD_SIZE/SIZEOF_BDIGITS, 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;
          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, nondigit = 0;
    int c;
    BDIGIT_DBL num;
    long len, blen = 1;
    long i;
    VALUE z;
    BDIGIT *zds;

    if (!str) {
      if (badcheck) goto bad;
      return INT2FIX(0);
    }
    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') {
          switch (str[1]) {
            case 'x': case 'X':
            base = 16;
            break;
            case 'b': case 'B':
            base = 2;
            break;
            case 'o': case 'O':
            base = 8;
            break;
            case 'd': case 'D':
            base = 10;
            break;
            default:
            base = 8;
          }
      }
      else if (base < -1) {
          base = -base;
      }
      else {
          base = 10;
      }
    }
    switch (base) {
      case 2:
      len = 1;
      if (str[0] == '0' && (str[1] == 'b'||str[1] == 'B')) {
          str += 2;
      }
      break;
      case 3:
      len = 2;
      break;
      case 8:
      if (str[0] == '0' && (str[1] == 'o'||str[1] == 'O')) {
          str += 2;
      }
      case 4: case 5: case 6: case 7:
      len = 3;
      break;
      case 10:
      if (str[0] == '0' && (str[1] == 'd'||str[1] == 'D')) {
          str += 2;
      }
      case 9: case 11: case 12: case 13: case 14: case 15:
      len = 4;
      break;
      case 16:
      len = 4;
      if (str[0] == '0' && (str[1] == 'x'||str[1] == 'X')) {
          str += 2;
      }
      break;
      default:
      if (base < 2 || 36 < base) {
          rb_raise(rb_eArgError, "illegal radix %d", base);
      }
      if (base <= 32) {
          len = 5;
      }
      else {
          len = 6;
      }
      break;
    }
    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) goto bad;       /* trailing garbage */
      }

      if (POSFIXABLE(val)) {
          if (sign) return LONG2FIX(val);
          else {
            long result = -(long)val;
            return LONG2FIX(result);
          }
      }
      else {
          VALUE big = rb_uint2big(val);
          RBIGNUM(big)->sign = sign;
          return bignorm(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++) {
      if (c == '_') {
          if (badcheck) {
            if (nondigit) goto bad;
            nondigit = c;
          }
          continue;
      }
      else if (!ISASCII(c)) {
          break;
      }
      else if (isdigit(c)) {
          c -= '0';
      }
      else if (islower(c)) {
          c -= 'a' - 10;
      }
      else if (isupper(c)) {
          c -= 'A' - 10;
      }
      else {
          break;
      }
      if (c >= base) break;
      nondigit = 0;
      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) {
        bad:
          rb_invalid_str(s, "Integer");
      }
    }

    return bignorm(z);
}

VALUE
rb_str_to_inum(str, base, badcheck)
    VALUE str;
    int base;
    int badcheck;
{
    char *s;
    long len;

    StringValue(str);
    if (badcheck) {
      s = StringValueCStr(str);
    }
    else {
      s = RSTRING(str)->ptr;
    }
    if (s) {
      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;
      }
    }
    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;

    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 LONG2FIX(n);
    return rb_ull2big(n);
}

VALUE
rb_ll2inum(n)
    LONG_LONG n;
{
    if (FIXABLE(n)) return LONG2FIX(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);
}

const char ruby_digitmap[] = "0123456789abcdefghijklmnopqrstuvwxyz";
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 (BIGZEROP(x)) {
      return rb_str_new2("0");
    }
    j = SIZEOF_BDIGITS*CHAR_BIT*i;
    switch (base) {
      case 2: break;
      case 3:
      j = j * 647L / 1024;
      break;
      case 4: case 5: case 6: case 7:
      j /= 2;
      break;
      case 8: case 9:
      j /= 3;
      break;
      case 10: case 11: case 12: case 13: case 14: case 15:
      j = j * 241L / 800;
      break;
      case 16: case 17: case 18: case 19: case 20: case 21:
      case 22: case 23: case 24: case 25: case 26: case 27:
      case 28: case 29: case 30: case 31:
      j /= 4;
      break;
      case 32: case 33: case 34: case 35: case 36:
      j /= 5;
      break;
      default:
      rb_raise(rb_eArgError, "illegal radix %d", base);
      break;
    }
    j += 2;

    hbase = base * base;
#if SIZEOF_BDIGITS > 2
    hbase *= hbase;
#endif

    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 = SIZEOF_BDIGITS;
      while (k--) {
          c = (char)(num % base);
          s[--j] = ruby_digitmap[(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;
}

/*
 *  call-seq:
 *     big.to_s(base=10)   =>  string
 *  
 *  Returns a string containing the representation of <i>big</i> radix
 *  <i>base</i> (2 through 36).
 *     
 *     12345654321.to_s         #=> "12345654321"
 *     12345654321.to_s(2)      #=> "1011011111110110111011110000110001"
 *     12345654321.to_s(8)      #=> "133766736061"
 *     12345654321.to_s(16)     #=> "2dfdbbc31"
 *     78546939656932.to_s(36)  #=> "rubyrules"
 */

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_BDIGITS)
      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_pack(x)   
    VALUE x;  
{   
    unsigned long num = big2ulong(x, "unsigned long");
    if (!RBIGNUM(x)->sign) {
      return -num;
    }
    return num;
}  

unsigned long
rb_big2ulong(x)
    VALUE x;
{
    unsigned long num = big2ulong(x, "unsigned long");

    if (!RBIGNUM(x)->sign) {
      if ((long)num < 0) {
          rb_raise(rb_eRangeError, "bignum out of range of unsigned long");
      }
      return -num;
    }
    return num;
}

long
rb_big2long(x)
    VALUE x;
{
    unsigned long num = big2ulong(x, "long");

    if ((long)num < 0 && (RBIGNUM(x)->sign || (long)num != LONG_MIN)) {
      rb_raise(rb_eRangeError, "bignum too big to convert into `long'");
    }
    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_BDIGITS)
      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 (isinf(d)) {
      rb_warn("Bignum out of Float range");
      d = HUGE_VAL;
    }
    if (!RBIGNUM(x)->sign) d = -d;
    return d;
}

/*
 *  call-seq:
 *     big.to_f -> float
 *  
 *  Converts <i>big</i> to a <code>Float</code>. If <i>big</i> doesn't
 *  fit in a <code>Float</code>, the result is infinity.
 *     
 */

static VALUE
rb_big_to_f(x)
    VALUE x;
{
    return rb_float_new(rb_big2dbl(x));
}

/*
 *  call-seq:
 *     big <=> numeric   => -1, 0, +1
 *  
 *  Comparison---Returns -1, 0, or +1 depending on whether <i>big</i> is
 *  less than, equal to, or greater than <i>numeric</i>. This is the
 *  basis for the tests in <code>Comparable</code>.
 *     
 */

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:
      return rb_dbl_cmp(rb_big2dbl(x), RFLOAT(y)->value);

      default:
      return rb_num_coerce_cmp(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));
}

/*
 *  call-seq:
 *     big == obj  => true or false
 *  
 *  Returns <code>true</code> only if <i>obj</i> has the same value
 *  as <i>big</i>. Contrast this with <code>Bignum#eql?</code>, which
 *  requires <i>obj</i> to be a <code>Bignum</code>.
 *     
 *     68719476736 == 68719476736.0   #=> true
 */

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:
        {
          volatile double a, b;

          a = RFLOAT(y)->value;
          if (isnan(a)) return Qfalse;
          b = rb_big2dbl(x);
          return (a == b)?Qtrue:Qfalse;
      }
      default:
      return rb_equal(y, x);
    }
    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;
}

/*
 *  call-seq:
 *     big.eql?(obj)   => true or false
 *  
 *  Returns <code>true</code> only if <i>obj</i> is a
 *  <code>Bignum</code> with the same value as <i>big</i>. Contrast this
 *  with <code>Bignum#==</code>, which performs type conversions.
 *     
 *     68719476736.eql?(68719476736.0)   #=> false
 */

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

/*
 * call-seq:
 *    -big   =>  other_big
 *
 * Unary minus (returns a new Bignum whose value is 0-big)
 */

static VALUE
rb_big_uminus(x)
    VALUE x;
{
    VALUE z = rb_big_clone(x);

    RBIGNUM(z)->sign = !RBIGNUM(x)->sign;

    return bignorm(z);
}

/*
 * call-seq:
 *     ~big  =>  integer
 *
 * Inverts the bits in big. As Bignums are conceptually infinite
 * length, the result acts as if it had an infinite number of one
 * bits to the left. In hex representations, this is displayed
 * as two periods to the left of the digits.
 *  
 *   sprintf("%X", ~0x1122334455)    #=> "..FEEDDCCBBAA"
 */

static VALUE
rb_big_neg(x)
    VALUE x;
{
    VALUE z = rb_big_clone(x);
    long i;
    BDIGIT *ds;

    if (!RBIGNUM(x)->sign) get2comp(z);
    ds = BDIGITS(z);
    i = RBIGNUM(x)->len;
    while (i--) ds[i] = ~ds[i];
    RBIGNUM(z)->sign = !RBIGNUM(z)->sign;
    if (RBIGNUM(x)->sign) get2comp(z);

    return bignorm(z);
}

static VALUE
bigsub(x, y)
    VALUE x, y;
{
    VALUE z = 0;
    BDIGIT *zds;
    BDIGIT_DBL_SIGNED num;
    long 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);
    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;
    int 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;
}

/*
 *  call-seq:
 *     big + other  => Numeric
 *
 *  Adds big and other, returning the result.
 */

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

/*
 *  call-seq:
 *     big - other  => Numeric
 *
 *  Subtracts other from big, returning the result.
 */

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

/*
 *  call-seq:
 *     big * other  => Numeric
 *
 *  Multiplies big and other, returning the result.
 */

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;

    if (BIGZEROP(y)) rb_num_zerodiv();
    yds = BDIGITS(y);
    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) {               /* 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 && !BIGZEROP(mod)) {
      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;
    }
}

/*
 *  call-seq:
 *     big / other     => Numeric
 *     big.div(other)  => Numeric
 *
 *  Divides big by other, returning the result.
 */

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

/*
 *  call-seq:
 *     big % other         => Numeric
 *     big.modulo(other)   => Numeric
 *
 *  Returns big modulo other. See Numeric.divmod for more
 *  information.
 */

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

/*
 *  call-seq:
 *     big.remainder(numeric)    => number
 *  
 *  Returns the remainder after dividing <i>big</i> by <i>numeric</i>.
 *     
 *     -1234567890987654321.remainder(13731)      #=> -6966
 *     -1234567890987654321.remainder(13731.24)   #=> -9906.22531493148
 */
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);
}

/*
 *  call-seq:
 *     big.divmod(numeric)   => array
 *  
 *  See <code>Numeric#divmod</code>.
 *     
 */
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));
}

/*
 *  call-seq:
 *     big.quo(numeric) -> float
 *  
 *  Returns the floating point result of dividing <i>big</i> by
 *  <i>numeric</i>.
 *     
 *     -1234567890987654321.quo(13731)      #=> -89910996357705.5
 *     -1234567890987654321.quo(13731.24)   #=> -89909424858035.7
 *     
 */

static VALUE
rb_big_quo(x, y)
    VALUE x, y;
{
    double dx = rb_big2dbl(x);
    double dy;

    switch (TYPE(y)) {
      case T_FIXNUM:
      dy = (double)FIX2LONG(y);
      break;

      case T_BIGNUM:
      dy = rb_big2dbl(y);
      break;

      case T_FLOAT:
      dy = RFLOAT(y)->value;
      break;

      default:
      return rb_num_coerce_bin(x, y);
    }
    return rb_float_new(dx / dy);
}

/*
 *  call-seq:
 *     big ** exponent   #=> numeric
 *
 *  Raises _big_ to the _exponent_ power (which may be an integer, float,
 *  or anything that will coerce to a number). The result may be
 *  a Fixnum, Bignum, or Float
 *
 *    123456789 ** 2      #=> 15241578750190521
 *    123456789 ** 1.2    #=> 5126464716.09932
 *    123456789 ** -2     #=> 6.5610001194102e-17
 */

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 = FIX2LONG(y);
      if (yy > 0) {
          VALUE z = x;

          for (;;) {
            yy -= 1;
            if (yy == 0) break;
            while (yy % 2 == 0) {
                yy /= 2;
                x = rb_big_mul(x, x);
            }
            z = rb_big_mul(z, x);
          }
          return bignorm(z);
      }
      d = (double)yy;
      break;

      default:
      return rb_num_coerce_bin(x, y);
    }
    return rb_float_new(pow(rb_big2dbl(x), d));
}

/*
 * call-seq:
 *     big & numeric   =>  integer
 *
 * Performs bitwise +and+ between _big_ and _numeric_.
 */

VALUE
rb_big_and(xx, yy)
    VALUE xx, yy;
{
    volatile VALUE x, y, z;
    BDIGIT *ds1, *ds2, *zds;
    long i, l1, l2;
    char sign;

    x = xx;
    y = rb_to_int(yy);
    if (FIXNUM_P(y)) {
      y = rb_int2big(FIX2LONG(y));
    }
    if (!RBIGNUM(y)->sign) {
      y = rb_big_clone(y);
      get2comp(y);
    }
    if (!RBIGNUM(x)->sign) {
      x = rb_big_clone(x);
      get2comp(x);
    }
    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);
    return bignorm(z);
}

/*
 * call-seq:
 *     big | numeric   =>  integer
 *
 * Performs bitwise +or+ between _big_ and _numeric_.
 */

VALUE
rb_big_or(xx, yy)
    VALUE xx, yy;
{
    volatile VALUE x, y, z;
    BDIGIT *ds1, *ds2, *zds;
    long i, l1, l2;
    char sign;

    x = xx;
    y = rb_to_int(yy);
    if (FIXNUM_P(y)) {
      y = rb_int2big(FIX2LONG(y));
    }
    if (!RBIGNUM(y)->sign) {
      y = rb_big_clone(y);
      get2comp(y);
    }
    if (!RBIGNUM(x)->sign) {
      x = rb_big_clone(x);
      get2comp(x);
    }
    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);

    return bignorm(z);
}

/*
 * call-seq:
 *     big ^ numeric   =>  integer
 *
 * Performs bitwise +exclusive or+ between _big_ and _numeric_.
 */

VALUE
rb_big_xor(xx, yy)
    VALUE xx, yy;
{
    volatile VALUE x, y;
    VALUE z;
    BDIGIT *ds1, *ds2, *zds;
    long i, l1, l2;
    char sign;

    x = xx;
    y = rb_to_int(yy);
    if (FIXNUM_P(y)) {
      y = rb_int2big(FIX2LONG(y));
    }
    if (!RBIGNUM(y)->sign) {
      y = rb_big_clone(y);
      get2comp(y);
    }
    if (!RBIGNUM(x)->sign) {
      x = rb_big_clone(x);
      get2comp(x);
    }
    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);

    return bignorm(z);
}

static VALUE rb_big_rshift _((VALUE,VALUE));

/*
 * call-seq:
 *     big << numeric   =>  integer
 *
 * Shifts big left _numeric_ positions (right if _numeric_ is negative).
 */

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

/*
 * call-seq:
 *     big >> numeric   =>  integer
 *
 * Shifts big right _numeric_ positions (left if _numeric_ is negative).
 */

static VALUE
rb_big_rshift(x, y)
    VALUE x, y;
{
    BDIGIT *xds, *zds;
    int shift = NUM2INT(y);
    long s1 = shift/BITSPERDIG;
    long s2 = shift%BITSPERDIG;
    VALUE z;
    BDIGIT_DBL num = 0;
    long i, j;
    volatile VALUE save_x;

    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) {
      save_x = x = rb_big_clone(x);
      get2comp(x);
    }
    xds = BDIGITS(x);
    i = RBIGNUM(x)->len; j = i - s1;
    z = bignew(j, RBIGNUM(x)->sign);
    if (!RBIGNUM(x)->sign) {
      num = ((BDIGIT_DBL)~0) << BITSPERDIG;
    }
    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);
    }
    return bignorm(z);
}

/*
 *  call-seq:
 *     big[n] -> 0, 1
 *  
 *  Bit Reference---Returns the <em>n</em>th bit in the (assumed) binary
 *  representation of <i>big</i>, where <i>big</i>[0] is the least
 *  significant bit.
 *     
 *     a = 9**15
 *     50.downto(0) do |n|
 *       print a[n]
 *     end
 *     
 *  <em>produces:</em>
 *     
 *     000101110110100000111000011110010100111100010111001
 *     
 */

static VALUE
rb_big_aref(x, y)
    VALUE x, y;
{
    BDIGIT *xds;
    int shift;
    long 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);
    }
    else {
      if (s1 >= RBIGNUM(x)->len) return INT2FIX(0);
    }
    xds = BDIGITS(x);
    if (xds[s1] & (1<<s2))
      return INT2FIX(1);
    return INT2FIX(0);
}

/*
 * call-seq:
 *   big.hash   => fixnum
 *
 * Compute a hash based on the value of _big_.
 */

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 LONG2FIX(key);
}

/*
 * MISSING: documentation
 */

static VALUE
rb_big_coerce(x, y)
    VALUE x, y;
{
    if (FIXNUM_P(y)) {
      return rb_assoc_new(rb_int2big(FIX2LONG(y)), x);
    }
    else if (TYPE(y) == T_BIGNUM) {
       return rb_assoc_new(y, x);
    }
    else {
      rb_raise(rb_eTypeError, "can't coerce %s to Bignum",
             rb_obj_classname(y));
    }
    /* not reached */
    return Qnil;
}

/*
 *  call-seq:
 *     big.abs -> aBignum
 *  
 *  Returns the absolute value of <i>big</i>.
 *     
 *     -1234567890987654321.abs   #=> 1234567890987654321
 */

static VALUE
rb_big_abs(x)
    VALUE x;
{
    if (!RBIGNUM(x)->sign) {
      x = rb_big_clone(x);
      RBIGNUM(x)->sign = 1;
    }
    return x;
}

VALUE
rb_big_rand(max, rand_buf)
    VALUE max;
    double *rand_buf;
{
    VALUE v;
    long len = RBIGNUM(max)->len;

    if (BIGZEROP(max)) {
      return rb_float_new(rand_buf[0]);
    }
    v = bignew(len,1);
    len--;
    BDIGITS(v)[len] = BDIGITS(max)[len] * rand_buf[len];    
    while (len--) {
      BDIGITS(v)[len] = ((BDIGIT)~0) * rand_buf[len];
    }

    return v;
}

/*
 *  call-seq:
 *     big.size -> integer
 *  
 *  Returns the number of bytes in the machine representation of
 *  <i>big</i>.
 *     
 *     (256**10 - 1).size   #=> 12
 *     (256**20 - 1).size   #=> 20
 *     (256**40 - 1).size   #=> 40
 */

static VALUE
rb_big_size(big)
    VALUE big;
{
    return LONG2FIX(RBIGNUM(big)->len*SIZEOF_BDIGITS);
}

/*
 *  Bignum objects hold integers outside the range of
 *  Fixnum. Bignum objects are created
 *  automatically when integer calculations would otherwise overflow a
 *  Fixnum. When a calculation involving
 *  Bignum objects returns a result that will fit in a
 *  Fixnum, the result is automatically converted.
 *     
 *  For the purposes of the bitwise operations and <code>[]</code>, a
 *  Bignum is treated as if it were an infinite-length
 *  bitstring with 2's complement representation.
 *     
 *  While Fixnum values are immediate, Bignum
 *  objects are not---assignment and parameter passing work with
 *  references to objects, not the objects themselves.
 *     
 */

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, "div", rb_big_div, 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, "quo", rb_big_quo, 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, "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);
}

Generated by  Doxygen 1.6.0   Back to index