bignum.c

DEFINITIONS

This source file includes following functions.
  1. bignew_1
  2. rb_big_clone
  3. get2comp
  4. rb_big_2comp
  5. bignorm
  6. rb_big_norm
  7. rb_uint2big
  8. rb_int2big
  9. rb_uint2inum
  10. rb_int2inum
  11. rb_quad_pack
  12. rb_quad_unpack
  13. rb_quad_pack
  14. rb_quad_unpack
  15. rb_cstr_to_inum
  16. rb_str_to_inum
  17. rb_ull2big
  18. rb_ll2big
  19. rb_ull2inum
  20. rb_ll2inum
  21. rb_cstr2inum
  22. rb_str2inum
  23. rb_big2str
  24. rb_big_to_s
  25. big2ulong
  26. rb_big2ulong
  27. rb_big2long
  28. big2ull
  29. rb_big2ull
  30. rb_big2ll
  31. dbl2big
  32. rb_dbl2big
  33. rb_big2dbl
  34. rb_big_to_f
  35. rb_big_cmp
  36. rb_big_eq
  37. rb_big_eql
  38. rb_big_uminus
  39. rb_big_neg
  40. bigsub
  41. bigadd
  42. rb_big_plus
  43. rb_big_minus
  44. rb_big_mul
  45. bigdivrem
  46. bigdivmod
  47. rb_big_div
  48. rb_big_modulo
  49. rb_big_remainder
  50. rb_big_divmod
  51. rb_big_pow
  52. rb_big_and
  53. rb_big_or
  54. rb_big_xor
  55. rb_big_lshift
  56. rb_big_rshift
  57. rb_big_aref
  58. rb_big_hash
  59. rb_big_coerce
  60. rb_big_abs
  61. rb_big_rand
  62. rb_big_size
  63. Init_Bignum 

   1  /**********************************************************************
   2  
   3    bignum.c -
   4  
   5    $Author: michal $
   6    $Date: 2002/08/21 15:47:54 $
   7    created at: Fri Jun 10 00:48:55 JST 1994
   8  
   9    Copyright (C) 1993-2002 Yukihiro Matsumoto
  10  
  11  **********************************************************************/
  12  
  13  #include "ruby.h"
  14  
  15  #include <math.h>
  16  #include <ctype.h>
  17  
  18  VALUE rb_cBignum;
  19  
  20  #if defined __MINGW32__
  21  #define USHORT _USHORT
  22  #endif
  23  
  24  #define BDIGITS(x) ((BDIGIT*)RBIGNUM(x)->digits)
  25  #define BITSPERDIG (SIZEOF_BDIGITS*CHAR_BIT)
  26  #define BIGRAD ((BDIGIT_DBL)1 << BITSPERDIG)
  27  #define DIGSPERLONG ((unsigned int)(SIZEOF_LONG/SIZEOF_BDIGITS))
  28  #if HAVE_LONG_LONG
  29  # define DIGSPERLL ((unsigned int)(SIZEOF_LONG_LONG/SIZEOF_BDIGITS))
  30  #endif
  31  #define BIGUP(x) ((BDIGIT_DBL)(x) << BITSPERDIG)
  32  #define BIGDN(x) RSHIFT(x,BITSPERDIG)
  33  #define BIGLO(x) ((BDIGIT)((x) & (BIGRAD-1)))
  34  
  35  static VALUE
  36  bignew_1(klass, len, sign)
  37      VALUE klass;
  38      long len;
  39      char sign;
  40  {
  41      NEWOBJ(big, struct RBignum);
  42      OBJSETUP(big, klass, T_BIGNUM);
  43      big->sign = sign;
  44      big->len = len;
  45      big->digits = ALLOC_N(BDIGIT, len);
  46  
  47      return (VALUE)big;
  48  }
  49  
  50  #define bignew(len,sign) bignew_1(rb_cBignum,len,sign)
  51  
  52  VALUE
  53  rb_big_clone(x)
  54      VALUE x;
  55  {
  56      VALUE z = bignew_1(CLASS_OF(x), RBIGNUM(x)->len, RBIGNUM(x)->sign);
  57  
  58      MEMCPY(BDIGITS(z), BDIGITS(x), BDIGIT, RBIGNUM(x)->len);
  59      return z;
  60  }
  61  
  62  static void
  63  get2comp(x, carry)              /* get 2's complement */
  64      VALUE x;
  65      int carry;
  66  {
  67      long i = RBIGNUM(x)->len;
  68      BDIGIT *ds = BDIGITS(x);
  69      BDIGIT_DBL num;
  70  
  71      while (i--) ds[i] = ~ds[i];
  72      i = 0; num = 1;
  73      do {
  74          num += ds[i];
  75          ds[i++] = BIGLO(num);
  76          num = BIGDN(num);
  77      } while (i < RBIGNUM(x)->len);
  78      if (!carry) return;
  79      if ((ds[RBIGNUM(x)->len-1] & (1<<(BITSPERDIG-1))) == 0) {
  80          REALLOC_N(RBIGNUM(x)->digits, BDIGIT, ++RBIGNUM(x)->len);
  81          ds = BDIGITS(x);
  82          ds[RBIGNUM(x)->len-1] = ~0;
  83      }
  84  }
  85  
  86  void
  87  rb_big_2comp(x)                 /* get 2's complement */
  88      VALUE x;
  89  {
  90      get2comp(x, Qtrue);
  91  }
  92  
  93  static VALUE
  94  bignorm(x)
  95      VALUE x;
  96  {
  97      if (!FIXNUM_P(x)) {
  98          long len = RBIGNUM(x)->len;
  99          BDIGIT *ds = BDIGITS(x);
 100  
 101          while (len-- && !ds[len]) ;
 102          RBIGNUM(x)->len = ++len;
 103  
 104          if (len*SIZEOF_BDIGITS <= sizeof(VALUE)) {
 105              long num = 0;
 106              while (len--) {
 107                  num = BIGUP(num) + ds[len];
 108              }
 109              if (num >= 0) {
 110                  if (RBIGNUM(x)->sign) {
 111                      if (POSFIXABLE(num)) return LONG2FIX(num);
 112                  }
 113                  else if (NEGFIXABLE(-(long)num)) return LONG2FIX(-(long)num);
 114              }
 115          }
 116      }
 117      return x;
 118  }
 119  
 120  VALUE
 121  rb_big_norm(x)
 122      VALUE x;
 123  {
 124      return bignorm(x);
 125  }
 126  
 127  VALUE
 128  rb_uint2big(n)
 129      unsigned long n;
 130  {
 131      BDIGIT_DBL num = n;
 132      long i = 0;
 133      BDIGIT *digits;
 134      VALUE big;
 135  
 136      big = bignew(DIGSPERLONG, 1);
 137      digits = BDIGITS(big);
 138      while (i < DIGSPERLONG) {
 139          digits[i++] = BIGLO(num);
 140          num = BIGDN(num);
 141      }
 142  
 143      i = DIGSPERLONG;
 144      while (--i && !digits[i]) ;
 145      RBIGNUM(big)->len = i+1;
 146      return big;
 147  }
 148  
 149  VALUE
 150  rb_int2big(n)
 151      long n;
 152  {
 153      long neg = 0;
 154      VALUE big;
 155  
 156      if (n < 0) {
 157          n = -n;
 158          neg = 1;
 159      }
 160      big = rb_uint2big(n);
 161      if (neg) {
 162          RBIGNUM(big)->sign = 0;
 163      }
 164      return big;
 165  }
 166  
 167  VALUE
 168  rb_uint2inum(n)
 169      unsigned long n;
 170  {
 171      if (POSFIXABLE(n)) return LONG2FIX(n);
 172      return rb_uint2big(n);
 173  }
 174  
 175  VALUE
 176  rb_int2inum(n)
 177      long n;
 178  {
 179      if (FIXABLE(n)) return LONG2FIX(n);
 180      return rb_int2big(n);
 181  }
 182  
 183  #ifdef HAVE_LONG_LONG
 184  
 185  #define DIGSPERLONGLONG ((unsigned int)(SIZEOF_LONG_LONG/SIZEOF_BDIGITS))
 186  
 187  void
 188  rb_quad_pack(buf, val)
 189      char *buf;
 190      VALUE val;
 191  {
 192      LONG_LONG q;
 193  
 194      val = rb_to_int(val);
 195      if (FIXNUM_P(val)) {
 196          q = FIX2LONG(val);
 197      }
 198      else {
 199          long len = RBIGNUM(val)->len;
 200          BDIGIT *ds;
 201  
 202          ds = BDIGITS(val);
 203          q = 0;
 204          while (len--) {
 205              q = BIGUP(q);
 206              q += ds[len];
 207          }
 208      }
 209      memcpy(buf, (char*)&q, SIZEOF_LONG_LONG);
 210  }
 211  
 212  VALUE
 213  rb_quad_unpack(buf, sign)
 214      const char *buf;
 215      int sign;
 216  {
 217      unsigned LONG_LONG q;
 218      long neg = 0;
 219      long i;
 220      BDIGIT *digits;
 221      VALUE big;
 222  
 223      memcpy(&q, buf, SIZEOF_LONG_LONG);
 224      if (sign) {
 225          if (FIXABLE((LONG_LONG)q)) return LONG2FIX((LONG_LONG)q);
 226          if ((LONG_LONG)q < 0) {
 227              q = -(LONG_LONG)q;
 228              neg = 1;
 229          }
 230      }
 231      else {
 232          if (POSFIXABLE(q)) return LONG2FIX(q);
 233      }
 234  
 235      i = 0;
 236      big = bignew(DIGSPERLONGLONG, 1);
 237      digits = BDIGITS(big);
 238      while (i < DIGSPERLONGLONG) {
 239          digits[i++] = BIGLO(q);
 240          q = BIGDN(q);
 241      }
 242  
 243      i = DIGSPERLONGLONG;
 244      while (i-- && !digits[i]) ;
 245      RBIGNUM(big)->len = i+1;
 246  
 247      if (neg) {
 248          RBIGNUM(big)->sign = 0;
 249      }
 250      return bignorm(big);
 251  }
 252  
 253  #else
 254  
 255  #define QUAD_SIZE 8
 256  
 257  void
 258  rb_quad_pack(buf, val)
 259      char *buf;
 260      VALUE val;
 261  {
 262      long len;
 263  
 264      memset(buf, 0, QUAD_SIZE);
 265      val = rb_to_int(val);
 266      if (FIXNUM_P(val)) {
 267          val = rb_int2big(FIX2LONG(val));
 268      }
 269      len = RBIGNUM(val)->len * SIZEOF_BDIGITS;
 270      if (len > QUAD_SIZE) len = QUAD_SIZE;
 271      memcpy(buf, (char*)BDIGITS(val), len);
 272      if (!RBIGNUM(val)->sign) {
 273          len = QUAD_SIZE;
 274          while (len--) {
 275              *buf = ~*buf;
 276              buf++;
 277          }
 278      }
 279  }
 280  
 281  #define BNEG(b) (RSHIFT(((BDIGIT*)b)[QUAD_SIZE/SIZEOF_BDIGITS-1],BITSPERDIG-1) != 0)
 282  
 283  VALUE
 284  rb_quad_unpack(buf, sign)
 285      const char *buf;
 286      int sign;
 287  {
 288      VALUE big = bignew(QUAD_SIZE/SIZEOF_BDIGITS, 1);
 289  
 290      memcpy((char*)BDIGITS(big), buf, QUAD_SIZE);
 291      if (sign && BNEG(buf)) {
 292          long len = QUAD_SIZE;
 293          char *tmp = (char*)BDIGITS(big);
 294  
 295          RBIGNUM(big)->sign = 0;
 296          while (len--) {
 297              *tmp = ~*tmp;
 298              tmp++;
 299          }
 300      }
 301  
 302      return bignorm(big);
 303  }
 304  
 305  #endif
 306  
 307  VALUE
 308  rb_cstr_to_inum(str, base, badcheck)
 309      const char *str;
 310      int base;
 311      int badcheck;
 312  {
 313      const char *s = str;
 314      char *end;
 315      char sign = 1, c, nondigit = 0;
 316      BDIGIT_DBL num;
 317      long len, blen = 1;
 318      long i;
 319      VALUE z;
 320      BDIGIT *zds;
 321  
 322      if (badcheck) {
 323          while (ISSPACE(*str)) str++;
 324      }
 325      else {
 326          while (ISSPACE(*str) || *str == '_') str++;
 327      }
 328  
 329      if (str[0] == '+') {
 330          str++;
 331      }
 332      else if (str[0] == '-') {
 333          str++;
 334          sign = 0;
 335      }
 336      if (str[0] == '+' || str[0] == '-') {
 337          if (badcheck) goto bad;
 338          return INT2FIX(0);
 339      }
 340      if (base <= 0) {
 341          if (str[0] == '0') {
 342              switch (str[1]) {
 343                case 'x': case 'X':
 344                  base = 16;
 345                  break;
 346                case 'b': case 'B':
 347                  base = 2;
 348                  break;
 349                case 'o': case 'O':
 350                  base = 8;
 351                  break;
 352                case 'd': case 'D':
 353                  base = 10;
 354                  break;
 355                default:
 356                  base = 8;
 357              }
 358          }
 359          else if (base < -1) {
 360              base = -base;
 361          }
 362          else {
 363              base = 10;
 364          }
 365      }
 366      switch (base) {
 367        case 2:
 368          len = 1;
 369          if (str[0] == '0' && (str[1] == 'b'||str[1] == 'B')) {
 370              str += 2;
 371          }
 372          break;
 373        case 8:
 374          len = 3;
 375          if (str[0] == '0' && (str[1] == 'o'||str[1] == 'O')) {
 376              str += 2;
 377          }
 378          break;
 379        case 10:
 380          len = 4;
 381          if (str[0] == '0' && (str[1] == 'd'||str[1] == 'D')) {
 382              str += 2;
 383          }
 384          break;
 385        case 16:
 386          len = 4;
 387          if (str[0] == '0' && (str[1] == 'x'||str[1] == 'X')) {
 388              str += 2;
 389          }
 390          break;
 391      }
 392      if (*str == '0') {          /* squeeze preceeding 0s */
 393          while (*++str == '0');
 394          --str;
 395      }
 396      len *= strlen(str)*sizeof(char);
 397  
 398      if (len <= (sizeof(VALUE)*CHAR_BIT)) {
 399          unsigned long val = strtoul((char*)str, &end, base);
 400  
 401          if (*end == '_') goto bigparse;
 402          if (badcheck) {
 403              if (end == str) goto bad; /* no number */
 404              while (*end && ISSPACE(*end)) end++;
 405              if (*end) {               /* trailing garbage */
 406                bad:
 407                  rb_invalid_str(s, "Integer");
 408              }
 409          }
 410  
 411          if (POSFIXABLE(val)) {
 412              if (sign) return LONG2FIX(val);
 413              else {
 414                  long result = -(long)val;
 415                  return LONG2FIX(result);
 416              }
 417          }
 418          else {
 419              VALUE big = rb_uint2big(val);
 420              RBIGNUM(big)->sign = sign;
 421              return bignorm(big);
 422          }
 423      }
 424    bigparse:
 425      len = (len/BITSPERDIG)+1;
 426      if (badcheck && *str == '_') goto bad;
 427  
 428      z = bignew(len, sign);
 429      zds = BDIGITS(z);
 430      for (i=len;i--;) zds[i]=0;
 431      while (c = *str++) {
 432          switch (c) {
 433            case '8': case '9':
 434              if (base == 8) {
 435                  c = base;
 436                  break;
 437              }
 438            case '0': case '1': case '2': case '3': case '4':
 439            case '5': case '6': case '7': 
 440              c = c - '0';
 441              nondigit = 0;
 442              break;
 443            case 'a': case 'b': case 'c':
 444            case 'd': case 'e': case 'f':
 445              c -= 'a' - 'A';
 446            case 'A': case 'B': case 'C':
 447            case 'D': case 'E': case 'F':
 448              if (base != 16) {
 449                  nondigit = c;
 450                  c = base;
 451              }
 452              else {
 453                  c = c - 'A' + 10;
 454                  nondigit = 0;
 455              }
 456              break;
 457            case '_':
 458              if (badcheck) {
 459                  if (nondigit) goto bad;
 460                  nondigit = c;
 461              }
 462              continue;
 463            default:
 464              c = base;
 465              break;
 466          }
 467          if (c >= base) break;
 468          i = 0;
 469          num = c;
 470          for (;;) {
 471              while (i<blen) {
 472                  num += (BDIGIT_DBL)zds[i]*base;
 473                  zds[i++] = BIGLO(num);
 474                  num = BIGDN(num);
 475              }
 476              if (num) {
 477                  blen++;
 478                  continue;
 479              }
 480              break;
 481          }
 482      }
 483      if (badcheck) {
 484          str--;
 485          if (s+1 < str && str[-1] == '_') goto bad;
 486          while (*str && ISSPACE(*str)) str++;
 487          if (*str) goto bad;
 488      }
 489  
 490      return bignorm(z);
 491  }
 492  
 493  VALUE
 494  rb_str_to_inum(str, base, badcheck)
 495      VALUE str;
 496      int base;
 497      int badcheck;
 498  {
 499      char *s;
 500      long len;
 501  
 502      StringValue(str);
 503      s = RSTRING(str)->ptr;
 504      len = RSTRING(str)->len;
 505      if (s[len]) {               /* no sentinel somehow */
 506          char *p = ALLOCA_N(char, len+1);
 507  
 508          MEMCPY(p, s, char, len);
 509          p[len] = '\0';
 510          s = p;
 511      }
 512      if (badcheck && len != strlen(s)) {
 513          rb_raise(rb_eArgError, "string for Integer contains null byte");
 514      }
 515      return rb_cstr_to_inum(s, base, badcheck); 
 516  }
 517  
 518  #if HAVE_LONG_LONG
 519  
 520  VALUE
 521  rb_ull2big(n)
 522      unsigned LONG_LONG n;
 523  {
 524      BDIGIT_DBL num = n;
 525      long i = 0;
 526      BDIGIT *digits;
 527      VALUE big;
 528  
 529      big = bignew(DIGSPERLL, 1);
 530      digits = BDIGITS(big);
 531      while (i < DIGSPERLL) {
 532          digits[i++] = BIGLO(num);
 533          num = BIGDN(num);
 534      }
 535  
 536      i = DIGSPERLL;
 537      while (i-- && !digits[i]) ;
 538      RBIGNUM(big)->len = i+1;
 539      return big;
 540  }
 541  
 542  VALUE
 543  rb_ll2big(n)
 544      LONG_LONG n;
 545  {
 546      long neg = 0;
 547      VALUE big;
 548  
 549      if (n < 0) {
 550          n = -n;
 551          neg = 1;
 552      }
 553      big = rb_ull2big(n);
 554      if (neg) {
 555          RBIGNUM(big)->sign = 0;
 556      }
 557      return big;
 558  }
 559  
 560  VALUE
 561  rb_ull2inum(n)
 562      unsigned LONG_LONG n;
 563  {
 564      if (POSFIXABLE(n)) return LONG2FIX(n);
 565      return rb_ull2big(n);
 566  }
 567  
 568  VALUE
 569  rb_ll2inum(n)
 570      LONG_LONG n;
 571  {
 572      if (FIXABLE(n)) return LONG2FIX(n);
 573      return rb_ll2big(n);
 574  }
 575  
 576  #endif  /* HAVE_LONG_LONG */
 577   
 578  VALUE
 579  rb_cstr2inum(str, base)
 580      const char *str;
 581      int base;
 582  {
 583      return rb_cstr_to_inum(str, base, base==0);
 584  }
 585  
 586  VALUE
 587  rb_str2inum(str, base)
 588      VALUE str;
 589      int base;
 590  {
 591      return rb_str_to_inum(str, base, base==0);
 592  }
 593  
 594  static char hexmap[] = "0123456789abcdef";
 595  VALUE
 596  rb_big2str(x, base)
 597      VALUE x;
 598      int base;
 599  {
 600      volatile VALUE t;
 601      BDIGIT *ds;
 602      long i, j, hbase;
 603      VALUE ss;
 604      char *s, c;
 605  
 606      if (FIXNUM_P(x)) {
 607          return rb_fix2str(x, base);
 608      }
 609      i = RBIGNUM(x)->len;
 610      if (i == 0 || (i == 1 && BDIGITS(x)[0] == 0)) {
 611          return rb_str_new2("0");
 612      }
 613      if (base == 10) {
 614          j = (SIZEOF_BDIGITS/sizeof(char)*CHAR_BIT*i*241L)/800+2;
 615          hbase = 10000;
 616      }
 617      else if (base == 16) {
 618          j = (SIZEOF_BDIGITS/sizeof(char)*CHAR_BIT*i)/4+2;
 619          hbase = 0x10000;
 620      }
 621      else if (base == 8) {
 622          j = (SIZEOF_BDIGITS/sizeof(char)*CHAR_BIT*i)+2;
 623          hbase = 010000;
 624      }
 625      else if (base == 2) {
 626          j = (SIZEOF_BDIGITS*CHAR_BIT*i)+2;
 627          hbase = 020;
 628      }
 629      else {
 630          rb_raise(rb_eArgError, "illegal radix %d", base);
 631      }
 632  
 633      t = rb_big_clone(x);
 634      ds = BDIGITS(t);
 635      ss = rb_str_new(0, j);
 636      s = RSTRING(ss)->ptr;
 637  
 638      s[0] = RBIGNUM(x)->sign ? '+' : '-';
 639      while (i && j) {
 640          long k = i;
 641          BDIGIT_DBL num = 0;
 642  
 643          while (k--) {
 644              num = BIGUP(num) + ds[k];
 645              ds[k] = (BDIGIT)(num / hbase);
 646              num %= hbase;
 647          }
 648          if (ds[i-1] == 0) i--;
 649          k = 4;
 650          while (k--) {
 651              c = (char)(num % base);
 652              s[--j] = hexmap[(int)c];
 653              num /= base;
 654              if (i == 0 && num == 0) break;
 655          }
 656      }
 657      while (s[j] == '0') j++;
 658      RSTRING(ss)->len -= RBIGNUM(x)->sign?j:j-1;
 659      memmove(RBIGNUM(x)->sign?s:s+1, s+j, RSTRING(ss)->len);
 660      s[RSTRING(ss)->len] = '\0';
 661  
 662      return ss;
 663  }
 664  
 665  static VALUE
 666  rb_big_to_s(argc, argv, x)
 667      int argc;
 668      VALUE *argv;
 669      VALUE x;
 670  {
 671      VALUE b;
 672      int base;
 673  
 674      rb_scan_args(argc, argv, "01", &b);
 675      if (argc == 0) base = 10;
 676      else base = NUM2INT(b);
 677      return rb_big2str(x, base);
 678  }
 679  
 680  static unsigned long
 681  big2ulong(x, type)
 682      VALUE x;
 683      char *type;
 684  {
 685      long len = RBIGNUM(x)->len;
 686      BDIGIT_DBL num;
 687      BDIGIT *ds;
 688  
 689      if (len > SIZEOF_LONG/SIZEOF_BDIGITS)
 690          rb_raise(rb_eRangeError, "bignum too big to convert into `%s'", type);
 691      ds = BDIGITS(x);
 692      num = 0;
 693      while (len--) {
 694          num = BIGUP(num);
 695          num += ds[len];
 696      }
 697      return num;
 698  }
 699  
 700  unsigned long
 701  rb_big2ulong(x)
 702      VALUE x;
 703  {
 704      unsigned long num = big2ulong(x, "unsigned long");
 705  
 706      if (!RBIGNUM(x)->sign) return -num;
 707      return num;
 708  }
 709  
 710  long
 711  rb_big2long(x)
 712      VALUE x;
 713  {
 714      unsigned long num = big2ulong(x, "int");
 715  
 716      if ((long)num < 0 && (RBIGNUM(x)->sign || (long)num != LONG_MIN)) {
 717          rb_raise(rb_eRangeError, "bignum too big to convert into `int'");
 718      }
 719      if (!RBIGNUM(x)->sign) return -(long)num;
 720      return num;
 721  }
 722  
 723  #if HAVE_LONG_LONG
 724  
 725  static unsigned LONG_LONG
 726  big2ull(x, type)
 727      VALUE x;
 728      char *type;
 729  {
 730      long len = RBIGNUM(x)->len;
 731      BDIGIT_DBL num;
 732      BDIGIT *ds;
 733  
 734      if (len > SIZEOF_LONG_LONG/SIZEOF_BDIGITS)
 735          rb_raise(rb_eRangeError, "bignum too big to convert into `%s'", type);
 736      ds = BDIGITS(x);
 737      num = 0;
 738      while (len--) {
 739          num = BIGUP(num);
 740          num += ds[len];
 741      }
 742      return num;
 743  }
 744  
 745  unsigned LONG_LONG
 746  rb_big2ull(x)
 747      VALUE x;
 748  {
 749      unsigned LONG_LONG num = big2ull(x, "unsigned long long");
 750  
 751      if (!RBIGNUM(x)->sign) return -num;
 752      return num;
 753  }
 754  
 755  LONG_LONG
 756  rb_big2ll(x)
 757      VALUE x;
 758  {
 759      unsigned LONG_LONG num = big2ull(x, "long long");
 760  
 761      if ((LONG_LONG)num < 0 && (RBIGNUM(x)->sign
 762                                 || (LONG_LONG)num != LLONG_MIN)) {
 763          rb_raise(rb_eRangeError, "bignum too big to convert into `long long'");
 764      }
 765      if (!RBIGNUM(x)->sign) return -(LONG_LONG)num;
 766      return num;
 767  }
 768  
 769  #endif  /* HAVE_LONG_LONG */
 770  
 771  static VALUE
 772  dbl2big(d)
 773      double d;
 774  {
 775      long i = 0;
 776      BDIGIT c;
 777      BDIGIT *digits;
 778      VALUE z;
 779      double u = (d < 0)?-d:d;
 780  
 781      if (isinf(d)) {
 782          rb_raise(rb_eFloatDomainError, d < 0 ? "-Infinity" : "Infinity");
 783      }
 784      if (isnan(d)) {
 785          rb_raise(rb_eFloatDomainError, "NaN");
 786      }
 787  
 788      while (!POSFIXABLE(u) || 0 != (long)u) {
 789          u /= (double)(BIGRAD);
 790          i++;
 791      }
 792      z = bignew(i, d>=0);
 793      digits = BDIGITS(z);
 794      while (i--) {
 795          u *= BIGRAD;
 796          c = (BDIGIT)u;
 797          u -= c;
 798          digits[i] = c;
 799      }
 800  
 801      return z;
 802  }
 803  
 804  VALUE
 805  rb_dbl2big(d)
 806      double d;
 807  {
 808      return bignorm(dbl2big(d));
 809  }
 810  
 811  double
 812  rb_big2dbl(x)
 813      VALUE x;
 814  {
 815      double d = 0.0;
 816      long i = RBIGNUM(x)->len;
 817      BDIGIT *ds = BDIGITS(x);
 818  
 819      while (i--) {
 820          d = ds[i] + BIGRAD*d;
 821      }
 822      if (isinf(d)) d = HUGE_VAL;
 823      if (!RBIGNUM(x)->sign) d = -d;
 824      return d;
 825  }
 826  
 827  static VALUE
 828  rb_big_to_f(x)
 829      VALUE x;
 830  {
 831      return rb_float_new(rb_big2dbl(x));
 832  }
 833  
 834  static VALUE
 835  rb_big_cmp(x, y)
 836      VALUE x, y;
 837  {
 838      long xlen = RBIGNUM(x)->len;
 839  
 840      switch (TYPE(y)) {
 841        case T_FIXNUM:
 842          y = rb_int2big(FIX2LONG(y));
 843          break;
 844  
 845        case T_BIGNUM:
 846          break;
 847  
 848        case T_FLOAT:
 849          return rb_dbl_cmp(rb_big2dbl(x), RFLOAT(y)->value);
 850  
 851        default:
 852          return rb_num_coerce_bin(x, y);
 853      }
 854  
 855      if (RBIGNUM(x)->sign > RBIGNUM(y)->sign) return INT2FIX(1);
 856      if (RBIGNUM(x)->sign < RBIGNUM(y)->sign) return INT2FIX(-1);
 857      if (xlen < RBIGNUM(y)->len)
 858          return (RBIGNUM(x)->sign) ? INT2FIX(-1) : INT2FIX(1);
 859      if (xlen > RBIGNUM(y)->len)
 860          return (RBIGNUM(x)->sign) ? INT2FIX(1) : INT2FIX(-1);
 861  
 862      while(xlen-- && (BDIGITS(x)[xlen]==BDIGITS(y)[xlen]));
 863      if (-1 == xlen) return INT2FIX(0);
 864      return (BDIGITS(x)[xlen] > BDIGITS(y)[xlen]) ?
 865          (RBIGNUM(x)->sign ? INT2FIX(1) : INT2FIX(-1)) :
 866              (RBIGNUM(x)->sign ? INT2FIX(-1) : INT2FIX(1));
 867  }
 868  
 869  static VALUE
 870  rb_big_eq(x, y)
 871      VALUE x, y;
 872  {
 873      switch (TYPE(y)) {
 874        case T_FIXNUM:
 875          y = rb_int2big(FIX2LONG(y));
 876          break;
 877        case T_BIGNUM:
 878          break;
 879        case T_FLOAT:
 880          if (rb_big2dbl(x) == RFLOAT(y)->value)
 881              return Qtrue;
 882          else
 883              return Qfalse;
 884        default:
 885          return rb_equal(y, x);
 886      }
 887      if (RBIGNUM(x)->sign != RBIGNUM(y)->sign) return Qfalse;
 888      if (RBIGNUM(x)->len != RBIGNUM(y)->len) return Qfalse;
 889      if (MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,RBIGNUM(y)->len) != 0) return Qfalse;
 890      return Qtrue;
 891  }
 892  
 893  static VALUE
 894  rb_big_eql(x, y)
 895      VALUE x, y;
 896  {
 897      if (TYPE(y) != T_BIGNUM) return Qfalse;
 898      if (RBIGNUM(x)->sign != RBIGNUM(y)->sign) return Qfalse;
 899      if (RBIGNUM(x)->len != RBIGNUM(y)->len) return Qfalse;
 900      if (MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,RBIGNUM(y)->len) != 0) return Qfalse;
 901      return Qtrue;
 902  }
 903  
 904  static VALUE
 905  rb_big_uminus(x)
 906      VALUE x;
 907  {
 908      VALUE z = rb_big_clone(x);
 909  
 910      RBIGNUM(z)->sign = !RBIGNUM(x)->sign;
 911  
 912      return bignorm(z);
 913  }
 914  
 915  static VALUE
 916  rb_big_neg(x)
 917      VALUE x;
 918  {
 919      VALUE z = rb_big_clone(x);
 920      long i = RBIGNUM(x)->len;
 921      BDIGIT *ds = BDIGITS(z);
 922  
 923      if (!RBIGNUM(x)->sign) get2comp(z, Qtrue);
 924      while (i--) ds[i] = ~ds[i];
 925      if (RBIGNUM(x)->sign) get2comp(z, Qfalse);
 926      RBIGNUM(z)->sign = !RBIGNUM(z)->sign;
 927  
 928      return bignorm(z);
 929  }
 930  
 931  static VALUE
 932  bigsub(x, y)
 933      VALUE x, y;
 934  {
 935      VALUE z = 0;
 936      BDIGIT *zds;
 937      BDIGIT_DBL_SIGNED num;
 938      long i = RBIGNUM(x)->len;
 939      
 940      /* if x is larger than y, swap */
 941      if (RBIGNUM(x)->len < RBIGNUM(y)->len) {
 942          z = x; x = y; y = z;    /* swap x y */
 943      }
 944      else if (RBIGNUM(x)->len == RBIGNUM(y)->len) {
 945          while (i > 0) {
 946              i--;
 947              if (BDIGITS(x)[i] > BDIGITS(y)[i]) {
 948                  break;
 949              }
 950              if (BDIGITS(x)[i] < BDIGITS(y)[i]) {
 951                  z = x; x = y; y = z;    /* swap x y */
 952                  break;
 953              }
 954          }
 955      }
 956  
 957      z = bignew(RBIGNUM(x)->len, (z == 0)?1:0);
 958      zds = BDIGITS(z);
 959  
 960      for (i = 0, num = 0; i < RBIGNUM(y)->len; i++) { 
 961          num += (BDIGIT_DBL_SIGNED)BDIGITS(x)[i] - BDIGITS(y)[i];
 962          zds[i] = BIGLO(num);
 963          num = BIGDN(num);
 964      } 
 965      while (num && i < RBIGNUM(x)->len) {
 966          num += BDIGITS(x)[i];
 967          zds[i++] = BIGLO(num);
 968          num = BIGDN(num);
 969      }
 970      while (i < RBIGNUM(x)->len) {
 971          zds[i] = BDIGITS(x)[i];
 972          i++;
 973      }
 974      
 975      return z;
 976  }
 977  
 978  static VALUE
 979  bigadd(x, y, sign)
 980      VALUE x, y;
 981      char sign;
 982  {
 983      VALUE z;
 984      BDIGIT_DBL num;
 985      long i, len;
 986  
 987      sign = (sign == RBIGNUM(y)->sign);
 988      if (RBIGNUM(x)->sign != sign) {
 989          if (sign) return bigsub(y, x);
 990          return bigsub(x, y);
 991      }
 992  
 993      if (RBIGNUM(x)->len > RBIGNUM(y)->len) {
 994          len = RBIGNUM(x)->len + 1;
 995          z = x; x = y; y = z;
 996      }
 997      else {
 998          len = RBIGNUM(y)->len + 1;
 999      }
1000      z = bignew(len, sign);
1001  
1002      len = RBIGNUM(x)->len;
1003      for (i = 0, num = 0; i < len; i++) {
1004          num += (BDIGIT_DBL)BDIGITS(x)[i] + BDIGITS(y)[i];
1005          BDIGITS(z)[i] = BIGLO(num);
1006          num = BIGDN(num);
1007      }
1008      len = RBIGNUM(y)->len;
1009      while (num && i < len) {
1010          num += BDIGITS(y)[i];
1011          BDIGITS(z)[i++] = BIGLO(num);
1012          num = BIGDN(num);
1013      }
1014      while (i < len) {
1015          BDIGITS(z)[i] = BDIGITS(y)[i];
1016          i++;
1017      }
1018      BDIGITS(z)[i] = (BDIGIT)num;
1019  
1020      return z;
1021  }
1022  
1023  VALUE
1024  rb_big_plus(x, y)
1025      VALUE x, y;
1026  {
1027      switch (TYPE(y)) {
1028        case T_FIXNUM:
1029          y = rb_int2big(FIX2LONG(y));
1030          /* fall through */
1031        case T_BIGNUM:
1032          return bignorm(bigadd(x, y, 1));
1033  
1034        case T_FLOAT:
1035          return rb_float_new(rb_big2dbl(x) + RFLOAT(y)->value);
1036  
1037        default:
1038          return rb_num_coerce_bin(x, y);
1039      }
1040  }
1041  
1042  VALUE
1043  rb_big_minus(x, y)
1044      VALUE x, y;
1045  {
1046      switch (TYPE(y)) {
1047        case T_FIXNUM:
1048          y = rb_int2big(FIX2LONG(y));
1049          /* fall through */
1050        case T_BIGNUM:
1051          return bignorm(bigadd(x, y, 0));
1052  
1053        case T_FLOAT:
1054          return rb_float_new(rb_big2dbl(x) - RFLOAT(y)->value);
1055  
1056        default:
1057          return rb_num_coerce_bin(x, y);
1058      }
1059  }
1060  
1061  VALUE
1062  rb_big_mul(x, y)
1063      VALUE x, y;
1064  {
1065      long i, j;
1066      BDIGIT_DBL n = 0;
1067      VALUE z;
1068      BDIGIT *zds;
1069  
1070      if (FIXNUM_P(x)) x = rb_int2big(FIX2LONG(x));
1071      switch (TYPE(y)) {
1072        case T_FIXNUM:
1073          y = rb_int2big(FIX2LONG(y));
1074          break;
1075  
1076        case T_BIGNUM:
1077          break;
1078  
1079        case T_FLOAT:
1080          return rb_float_new(rb_big2dbl(x) * RFLOAT(y)->value);
1081  
1082        default:
1083          return rb_num_coerce_bin(x, y);
1084      }
1085  
1086      j = RBIGNUM(x)->len + RBIGNUM(y)->len + 1;
1087      z = bignew(j, RBIGNUM(x)->sign==RBIGNUM(y)->sign);
1088      zds = BDIGITS(z);
1089      while (j--) zds[j] = 0;
1090      for (i = 0; i < RBIGNUM(x)->len; i++) {
1091          BDIGIT_DBL dd = BDIGITS(x)[i]; 
1092          if (dd == 0) continue;
1093          n = 0;
1094          for (j = 0; j < RBIGNUM(y)->len; j++) {
1095              BDIGIT_DBL ee = n + (BDIGIT_DBL)dd * BDIGITS(y)[j];
1096              n = zds[i + j] + ee;
1097              if (ee) zds[i + j] = BIGLO(n);
1098              n = BIGDN(n);
1099          }
1100          if (n) {
1101              zds[i + j] = n;
1102          }
1103      }
1104  
1105      return bignorm(z);
1106  }
1107  
1108  static void
1109  bigdivrem(x, y, divp, modp)
1110      VALUE x, y;
1111      VALUE *divp, *modp;
1112  {
1113      long nx = RBIGNUM(x)->len, ny = RBIGNUM(y)->len;
1114      long i, j;
1115      VALUE yy, z;
1116      BDIGIT *xds, *yds, *zds, *tds;
1117      BDIGIT_DBL t2;
1118      BDIGIT_DBL_SIGNED num;
1119      BDIGIT dd, q;
1120  
1121      yds = BDIGITS(y);
1122      if (ny == 0 && yds[0] == 0) rb_num_zerodiv();
1123      if (nx < ny || nx == ny && BDIGITS(x)[nx - 1] < BDIGITS(y)[ny - 1]) {
1124          if (divp) *divp = rb_int2big(0);
1125          if (modp) *modp = x;
1126          return;
1127      }
1128      xds = BDIGITS(x);
1129      if (ny == 1) {
1130          dd = yds[0];
1131          z = rb_big_clone(x);
1132          zds = BDIGITS(z);
1133          t2 = 0; i = nx;
1134          while (i--) {
1135              t2 = BIGUP(t2) + zds[i];
1136              zds[i] = (BDIGIT)(t2 / dd);
1137              t2 %= dd;
1138          }
1139          RBIGNUM(z)->sign = RBIGNUM(x)->sign==RBIGNUM(y)->sign;
1140          if (modp) {
1141              *modp = rb_uint2big((unsigned long)t2);
1142              RBIGNUM(*modp)->sign = RBIGNUM(x)->sign;
1143          }
1144          if (divp) *divp = z;
1145          return;
1146      }
1147      z = bignew(nx==ny?nx+2:nx+1, RBIGNUM(x)->sign==RBIGNUM(y)->sign);
1148      zds = BDIGITS(z);
1149      if (nx==ny) zds[nx+1] = 0;
1150      while (!yds[ny-1]) ny--;
1151  
1152      dd = 0;
1153      q = yds[ny-1];
1154      while ((q & (1<<(BITSPERDIG-1))) == 0) {
1155          q <<= 1;
1156          dd++;
1157      }
1158      if (dd) {
1159          yy = rb_big_clone(y);
1160          tds = BDIGITS(yy);
1161          j = 0;
1162          t2 = 0;
1163          while (j<ny) {
1164              t2 += (BDIGIT_DBL)yds[j]<<dd;
1165              tds[j++] = BIGLO(t2);
1166              t2 = BIGDN(t2);
1167          }
1168          yds = tds;
1169          j = 0;
1170          t2 = 0;
1171          while (j<nx) {
1172              t2 += (BDIGIT_DBL)xds[j]<<dd;
1173              zds[j++] = BIGLO(t2);
1174              t2 = BIGDN(t2);
1175          }
1176          zds[j] = (BDIGIT)t2;
1177      }
1178      else {
1179          zds[nx] = 0;
1180          j = nx;
1181          while (j--) zds[j] = xds[j];
1182      }
1183  
1184      j = nx==ny?nx+1:nx;
1185      do {
1186          if (zds[j] ==  yds[ny-1]) q = BIGRAD-1;
1187          else q = (BDIGIT)((BIGUP(zds[j]) + zds[j-1])/yds[ny-1]);
1188          if (q) {
1189              i = 0; num = 0; t2 = 0;
1190              do {                        /* multiply and subtract */
1191                  BDIGIT_DBL ee;
1192                  t2 += (BDIGIT_DBL)yds[i] * q;
1193                  ee = num - BIGLO(t2);
1194                  num = (BDIGIT_DBL)zds[j - ny + i] + ee;
1195                  if (ee) zds[j - ny + i] = BIGLO(num);
1196                  num = BIGDN(num);
1197                  t2 = BIGDN(t2);
1198              } while (++i < ny);
1199              num += zds[j - ny + i] - t2;/* borrow from high digit; don't update */
1200              while (num) {               /* "add back" required */
1201                  i = 0; num = 0; q--;
1202                  do {
1203                      BDIGIT_DBL ee = num + yds[i];
1204                      num = (BDIGIT_DBL)zds[j - ny + i] + ee;
1205                      if (ee) zds[j - ny + i] = BIGLO(num);
1206                      num = BIGDN(num);
1207                  } while (++i < ny);
1208                  num--;
1209              }
1210          }
1211          zds[j] = q;
1212      } while (--j >= ny);
1213      if (divp) {                 /* move quotient down in z */
1214          *divp = rb_big_clone(z);
1215          zds = BDIGITS(*divp);
1216          j = (nx==ny ? nx+2 : nx+1) - ny;
1217          for (i = 0;i < j;i++) zds[i] = zds[i+ny];
1218          RBIGNUM(*divp)->len = i;
1219      }
1220      if (modp) {                 /* just normalize remainder */
1221          *modp = rb_big_clone(z);
1222          zds = BDIGITS(*modp);
1223          while (ny-- && !zds[ny]); ++ny;
1224          if (dd) {
1225              t2 = 0; i = ny;
1226              while(i--) {
1227                  t2 = (t2 | zds[i]) >> dd;
1228                  q = zds[i];
1229                  zds[i] = BIGLO(t2);
1230                  t2 = BIGUP(q);
1231              }
1232          }
1233          RBIGNUM(*modp)->len = ny;
1234          RBIGNUM(*modp)->sign = RBIGNUM(x)->sign;
1235      }
1236  }
1237  
1238  static void
1239  bigdivmod(x, y, divp, modp)
1240      VALUE x, y;
1241      VALUE *divp, *modp;
1242  {
1243      VALUE mod;
1244  
1245      bigdivrem(x, y, divp, &mod);
1246      if (RBIGNUM(x)->sign != RBIGNUM(y)->sign && RBIGNUM(mod)->len > 0) {
1247          if (divp) *divp = bigadd(*divp, rb_int2big(1), 0);
1248          if (modp) *modp = bigadd(mod, y, 1);
1249      }
1250      else {
1251          if (divp) *divp = *divp;
1252          if (modp) *modp = mod;
1253      }
1254  }
1255  
1256  static VALUE
1257  rb_big_div(x, y)
1258      VALUE x, y;
1259  {
1260      VALUE z;
1261  
1262      switch (TYPE(y)) {
1263        case T_FIXNUM:
1264          y = rb_int2big(FIX2LONG(y));
1265          break;
1266  
1267        case T_BIGNUM:
1268          break;
1269  
1270        case T_FLOAT:
1271          return rb_float_new(rb_big2dbl(x) / RFLOAT(y)->value);
1272  
1273        default:
1274          return rb_num_coerce_bin(x, y);
1275      }
1276      bigdivmod(x, y, &z, 0);
1277  
1278      return bignorm(z);
1279  }
1280  
1281  
1282  static VALUE
1283  rb_big_modulo(x, y)
1284      VALUE x, y;
1285  {
1286      VALUE z;
1287  
1288      switch (TYPE(y)) {
1289        case T_FIXNUM:
1290          y = rb_int2big(FIX2LONG(y));
1291          break;
1292  
1293        case T_BIGNUM:
1294          break;
1295  
1296        default:
1297          return rb_num_coerce_bin(x, y);
1298      }
1299      bigdivmod(x, y, 0, &z);
1300  
1301      return bignorm(z);
1302  }
1303  
1304  static VALUE
1305  rb_big_remainder(x, y)
1306      VALUE x, y;
1307  {
1308      VALUE z;
1309  
1310      switch (TYPE(y)) {
1311        case T_FIXNUM:
1312          y = rb_int2big(FIX2LONG(y));
1313          break;
1314  
1315        case T_BIGNUM:
1316          break;
1317  
1318        default:
1319          return rb_num_coerce_bin(x, y);
1320      }
1321      bigdivrem(x, y, 0, &z);
1322  
1323      return bignorm(z);
1324  }
1325  
1326  VALUE
1327  rb_big_divmod(x, y)
1328      VALUE x, y;
1329  {
1330      VALUE div, mod;
1331  
1332      switch (TYPE(y)) {
1333        case T_FIXNUM:
1334          y = rb_int2big(FIX2LONG(y));
1335          break;
1336  
1337        case T_BIGNUM:
1338          break;
1339  
1340        default:
1341          return rb_num_coerce_bin(x, y);
1342      }
1343      bigdivmod(x, y, &div, &mod);
1344  
1345      return rb_assoc_new(bignorm(div), bignorm(mod));
1346  }
1347  
1348  VALUE
1349  rb_big_pow(x, y)
1350      VALUE x, y;
1351  {
1352      double d;
1353      long yy;
1354      
1355      if (y == INT2FIX(0)) return INT2FIX(1);
1356      switch (TYPE(y)) {
1357        case T_FLOAT:
1358          d = RFLOAT(y)->value;
1359          break;
1360  
1361        case T_BIGNUM:
1362          rb_warn("in a**b, b may be too big");
1363          d = rb_big2dbl(y);
1364          break;
1365  
1366        case T_FIXNUM:
1367          yy = NUM2LONG(y);
1368          if (yy > 0) {
1369              VALUE z = x;
1370  
1371              for (;;) {
1372                  yy -= 1;
1373                  if (yy == 0) break;
1374                  while (yy % 2 == 0) {
1375                      yy /= 2;
1376                      x = rb_big_mul(x, x);
1377                  }
1378                  z = rb_big_mul(z, x);
1379              }
1380              return bignorm(z);
1381          }
1382          d = (double)yy;
1383          break;
1384  
1385        default:
1386          return rb_num_coerce_bin(x, y);
1387      }
1388      return rb_float_new(pow(rb_big2dbl(x), d));
1389  }
1390  
1391  VALUE
1392  rb_big_and(x, y)
1393      VALUE x, y;
1394  {
1395      VALUE z;
1396      BDIGIT *ds1, *ds2, *zds;
1397      long i, l1, l2;
1398      char sign;
1399  
1400      if (FIXNUM_P(y)) {
1401          y = rb_int2big(FIX2LONG(y));
1402      }
1403      else {
1404          Check_Type(y, T_BIGNUM);
1405      }
1406  
1407      if (!RBIGNUM(y)->sign) {
1408          y = rb_big_clone(y);
1409          get2comp(y, Qtrue);
1410      }
1411      if (!RBIGNUM(x)->sign) {
1412          x = rb_big_clone(x);
1413          get2comp(x, Qtrue);
1414      }
1415      if (RBIGNUM(x)->len > RBIGNUM(y)->len) {
1416          l1 = RBIGNUM(y)->len;
1417          l2 = RBIGNUM(x)->len;
1418          ds1 = BDIGITS(y);
1419          ds2 = BDIGITS(x);
1420          sign = RBIGNUM(y)->sign;
1421      }
1422      else {
1423          l1 = RBIGNUM(x)->len;
1424          l2 = RBIGNUM(y)->len;
1425          ds1 = BDIGITS(x);
1426          ds2 = BDIGITS(y);
1427          sign = RBIGNUM(x)->sign;
1428      }
1429      z = bignew(l2, RBIGNUM(x)->sign || RBIGNUM(y)->sign);
1430      zds = BDIGITS(z);
1431  
1432      for (i=0; i<l1; i++) {
1433          zds[i] = ds1[i] & ds2[i];
1434      }
1435      for (; i<l2; i++) {
1436          zds[i] = sign?0:ds2[i];
1437      }
1438      if (!RBIGNUM(z)->sign) get2comp(z, Qfalse);
1439      return bignorm(z);
1440  }
1441  
1442  VALUE
1443  rb_big_or(x, y)
1444      VALUE x, y;
1445  {
1446      VALUE z;
1447      BDIGIT *ds1, *ds2, *zds;
1448      long i, l1, l2;
1449      char sign;
1450  
1451      if (FIXNUM_P(y)) {
1452          y = rb_int2big(FIX2LONG(y));
1453      }
1454      else {
1455          Check_Type(y, T_BIGNUM);
1456      }
1457  
1458      if (!RBIGNUM(y)->sign) {
1459          y = rb_big_clone(y);
1460          get2comp(y, Qtrue);
1461      }
1462      if (!RBIGNUM(x)->sign) {
1463          x = rb_big_clone(x);
1464          get2comp(x, Qtrue);
1465      }
1466      if (RBIGNUM(x)->len > RBIGNUM(y)->len) {
1467          l1 = RBIGNUM(y)->len;
1468          l2 = RBIGNUM(x)->len;
1469          ds1 = BDIGITS(y);
1470          ds2 = BDIGITS(x);
1471          sign = RBIGNUM(y)->sign;
1472      }
1473      else {
1474          l1 = RBIGNUM(x)->len;
1475          l2 = RBIGNUM(y)->len;
1476          ds1 = BDIGITS(x);
1477          ds2 = BDIGITS(y);
1478          sign = RBIGNUM(x)->sign;
1479      }
1480      z = bignew(l2, RBIGNUM(x)->sign && RBIGNUM(y)->sign);
1481      zds = BDIGITS(z);
1482  
1483      for (i=0; i<l1; i++) {
1484          zds[i] = ds1[i] | ds2[i];
1485      }
1486      for (; i<l2; i++) {
1487          zds[i] = sign?ds2[i]:(BIGRAD-1);
1488      }
1489      if (!RBIGNUM(z)->sign) get2comp(z, Qfalse);
1490  
1491      return bignorm(z);
1492  }
1493  
1494  VALUE
1495  rb_big_xor(x, y)
1496      VALUE x, y;
1497  {
1498      VALUE z;
1499      BDIGIT *ds1, *ds2, *zds;
1500      long i, l1, l2;
1501      char sign;
1502  
1503      if (FIXNUM_P(y)) {
1504          y = rb_int2big(FIX2LONG(y));
1505      }
1506      else {
1507          Check_Type(y, T_BIGNUM);
1508      }
1509  
1510      if (!RBIGNUM(y)->sign) {
1511          y = rb_big_clone(y);
1512          get2comp(y, Qtrue);
1513      }
1514      if (!RBIGNUM(x)->sign) {
1515          x = rb_big_clone(x);
1516          get2comp(x, Qtrue);
1517      }
1518      if (RBIGNUM(x)->len > RBIGNUM(y)->len) {
1519          l1 = RBIGNUM(y)->len;
1520          l2 = RBIGNUM(x)->len;
1521          ds1 = BDIGITS(y);
1522          ds2 = BDIGITS(x);
1523          sign = RBIGNUM(y)->sign;
1524      }
1525      else {
1526          l1 = RBIGNUM(x)->len;
1527          l2 = RBIGNUM(y)->len;
1528          ds1 = BDIGITS(x);
1529          ds2 = BDIGITS(y);
1530          sign = RBIGNUM(x)->sign;
1531      }
1532      RBIGNUM(x)->sign = RBIGNUM(x)->sign?1:0;
1533      RBIGNUM(y)->sign = RBIGNUM(y)->sign?1:0;
1534      z = bignew(l2, !(RBIGNUM(x)->sign ^ RBIGNUM(y)->sign));
1535      zds = BDIGITS(z);
1536  
1537      for (i=0; i<l1; i++) {
1538          zds[i] = ds1[i] ^ ds2[i];
1539      }
1540      for (; i<l2; i++) {
1541          zds[i] = sign?ds2[i]:~ds2[i];
1542      }
1543      if (!RBIGNUM(z)->sign) get2comp(z, Qfalse);
1544  
1545      return bignorm(z);
1546  }
1547  
1548  static VALUE rb_big_rshift _((VALUE,VALUE));
1549  
1550  VALUE
1551  rb_big_lshift(x, y)
1552      VALUE x, y;
1553  {
1554      BDIGIT *xds, *zds;
1555      int shift = NUM2INT(y);
1556      int s1 = shift/BITSPERDIG;
1557      int s2 = shift%BITSPERDIG;
1558      VALUE z;
1559      BDIGIT_DBL num = 0;
1560      long len, i;
1561  
1562      if (shift < 0) return rb_big_rshift(x, INT2FIX(-shift));
1563      len = RBIGNUM(x)->len;
1564      z = bignew(len+s1+1, RBIGNUM(x)->sign);
1565      zds = BDIGITS(z);
1566      for (i=0; i<s1; i++) {
1567          *zds++ = 0;
1568      }
1569      xds = BDIGITS(x);
1570      for (i=0; i<len; i++) {
1571          num = num | (BDIGIT_DBL)*xds++<<s2;
1572          *zds++ = BIGLO(num);
1573          num = BIGDN(num);
1574      }
1575      *zds = BIGLO(num);
1576      return bignorm(z);
1577  }
1578  
1579  static VALUE
1580  rb_big_rshift(x, y)
1581      VALUE x, y;
1582  {
1583      BDIGIT *xds, *zds;
1584      int shift = NUM2INT(y);
1585      long s1 = shift/BITSPERDIG;
1586      long s2 = shift%BITSPERDIG;
1587      VALUE z;
1588      BDIGIT_DBL num = 0;
1589      long i, j;
1590  
1591      if (shift < 0) return rb_big_lshift(x, INT2FIX(-shift));
1592  
1593      if (s1 > RBIGNUM(x)->len) {
1594          if (RBIGNUM(x)->sign)
1595              return INT2FIX(0);
1596          else
1597              return INT2FIX(-1);
1598      }
1599      if (!RBIGNUM(x)->sign) {
1600          x = rb_big_clone(x);
1601          get2comp(x, Qtrue);
1602      }
1603      xds = BDIGITS(x);
1604      i = RBIGNUM(x)->len; j = i - s1;
1605      z = bignew(j, RBIGNUM(x)->sign);
1606      zds = BDIGITS(z);
1607      while (i--, j--) {
1608          num = (num | xds[i]) >> s2;
1609          zds[j] = BIGLO(num);
1610          num = BIGUP(xds[i]);
1611      }
1612      if (!RBIGNUM(x)->sign) {
1613          get2comp(z, Qfalse);
1614      }
1615      return bignorm(z);
1616  }
1617  
1618  static VALUE
1619  rb_big_aref(x, y)
1620      VALUE x, y;
1621  {
1622      BDIGIT *xds;
1623      int shift;
1624      long s1, s2;
1625  
1626      if (TYPE(y) == T_BIGNUM) {
1627          if (!RBIGNUM(y)->sign || RBIGNUM(x)->sign)
1628              return INT2FIX(0);
1629          return INT2FIX(1);
1630      }
1631      shift = NUM2INT(y);
1632      if (shift < 0) return INT2FIX(0);
1633      s1 = shift/BITSPERDIG;
1634      s2 = shift%BITSPERDIG;
1635  
1636      if (!RBIGNUM(x)->sign) {
1637          if (s1 >= RBIGNUM(x)->len) return INT2FIX(1);
1638          x = rb_big_clone(x);
1639          get2comp(x, Qtrue);
1640      }
1641      else {
1642          if (s1 >= RBIGNUM(x)->len) return INT2FIX(0);
1643      }
1644      xds = BDIGITS(x);
1645      if (xds[s1] & (1<<s2))
1646          return INT2FIX(1);
1647      return INT2FIX(0);
1648  }
1649  
1650  static VALUE
1651  rb_big_hash(x)
1652      VALUE x;
1653  {
1654      long i, len, key;
1655      BDIGIT *digits;
1656  
1657      key = 0; digits = BDIGITS(x); len = RBIGNUM(x)->len;
1658      for (i=0; i<len; i++) {
1659          key ^= *digits++;
1660      }
1661      return LONG2FIX(key);
1662  }
1663  
1664  static VALUE
1665  rb_big_coerce(x, y)
1666      VALUE x, y;
1667  {
1668      if (FIXNUM_P(y)) {
1669          return rb_assoc_new(rb_int2big(FIX2LONG(y)), x);
1670      }
1671      else {
1672          rb_raise(rb_eTypeError, "Can't coerce %s to Bignum",
1673                   rb_class2name(CLASS_OF(y)));
1674      }
1675      /* not reached */
1676      return Qnil;
1677  }
1678  
1679  static VALUE
1680  rb_big_abs(x)
1681      VALUE x;
1682  {
1683      if (!RBIGNUM(x)->sign) {
1684          x = rb_big_clone(x);
1685          RBIGNUM(x)->sign = 1;
1686      }
1687      return x;
1688  }
1689  
1690  VALUE
1691  rb_big_rand(max, rand_buf)
1692      VALUE max;
1693      double *rand_buf;
1694  {
1695      VALUE v;
1696      long len = RBIGNUM(max)->len;
1697      
1698      if (len == 0 && BDIGITS(max)[0] == 0) {
1699          return rb_float_new(rand_buf[0]);
1700      }
1701      v = bignew(len,1);
1702      while (len--) {
1703          BDIGITS(v)[len] = ((BDIGIT)~0) * rand_buf[len];
1704      }
1705  
1706      return rb_big_modulo((VALUE)v, max);
1707  }
1708  
1709  static VALUE
1710  rb_big_size(big)
1711      VALUE big;
1712  {
1713      return LONG2FIX(RBIGNUM(big)->len*SIZEOF_BDIGITS);
1714  }
1715  
1716  void
1717  Init_Bignum()
1718  {
1719      rb_cBignum = rb_define_class("Bignum", rb_cInteger);
1720  
1721      rb_define_method(rb_cBignum, "to_s", rb_big_to_s, -1);
1722      rb_define_method(rb_cBignum, "coerce", rb_big_coerce, 1);
1723      rb_define_method(rb_cBignum, "-@", rb_big_uminus, 0);
1724      rb_define_method(rb_cBignum, "+", rb_big_plus, 1);
1725      rb_define_method(rb_cBignum, "-", rb_big_minus, 1);
1726      rb_define_method(rb_cBignum, "*", rb_big_mul, 1);
1727      rb_define_method(rb_cBignum, "/", rb_big_div, 1);
1728      rb_define_method(rb_cBignum, "%", rb_big_modulo, 1);
1729      rb_define_method(rb_cBignum, "divmod", rb_big_divmod, 1);
1730      rb_define_method(rb_cBignum, "modulo", rb_big_modulo, 1);
1731      rb_define_method(rb_cBignum, "remainder", rb_big_remainder, 1);
1732      rb_define_method(rb_cBignum, "**", rb_big_pow, 1);
1733      rb_define_method(rb_cBignum, "&", rb_big_and, 1);
1734      rb_define_method(rb_cBignum, "|", rb_big_or, 1);
1735      rb_define_method(rb_cBignum, "^", rb_big_xor, 1);
1736      rb_define_method(rb_cBignum, "~", rb_big_neg, 0);
1737      rb_define_method(rb_cBignum, "<<", rb_big_lshift, 1);
1738      rb_define_method(rb_cBignum, ">>", rb_big_rshift, 1);
1739      rb_define_method(rb_cBignum, "[]", rb_big_aref, 1);
1740  
1741      rb_define_method(rb_cBignum, "<=>", rb_big_cmp, 1);
1742      rb_define_method(rb_cBignum, "==", rb_big_eq, 1);
1743      rb_define_method(rb_cBignum, "===", rb_big_eq, 1);
1744      rb_define_method(rb_cBignum, "eql?", rb_big_eql, 1);
1745      rb_define_method(rb_cBignum, "hash", rb_big_hash, 0);
1746      rb_define_method(rb_cBignum, "to_f", rb_big_to_f, 0);
1747      rb_define_method(rb_cBignum, "abs", rb_big_abs, 0);
1748      rb_define_method(rb_cBignum, "size", rb_big_size, 0);
1749  }