← Back to branch summary

~ubuntu-branches/ubuntu/intrepid/ruby1.9/intrepid-updates

« back to all changes in this revision

Viewing changes to bignum.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2007-09-04 16:01:17 UTC
  • mfrom: (1.1.8 upstream)
  • Revision ID: james.westby@ubuntu.com-20070904160117-i15zckg2nhxe9fyw
Tags: 1.9.0+20070830-2ubuntu1
* Sync from Debian; remaining changes:
  - Add -g to CFLAGS.
* Fixes build failure on ia64.
* Fixes build failure with gcc-4.2 on lpia.
* Robustify check for target_os, fixing build failure on lpia.
* Set Ubuntu maintainer address.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bignum.c
2
2
 
3
3
  bignum.c -
4
4
 
5
 
  $Author: nobu $
6
 
  $Date: 2007-05-09 12:49:18 +0900 (水, 09  5月 2007) $
 
5
  $Author: matz $
 
6
  $Date: 2007-08-25 12:29:39 +0900 (土, 25  8月 2007) $
7
7
  created at: Fri Jun 10 00:48:55 JST 1994
8
8
 
9
 
  Copyright (C) 1993-2003 Yukihiro Matsumoto
 
9
  Copyright (C) 1993-2007 Yukihiro Matsumoto
10
10
 
11
11
**********************************************************************/
12
12
 
13
 
#include "ruby.h"
 
13
#include "ruby/ruby.h"
14
14
 
15
15
#include <math.h>
16
16
#include <float.h>
70
70
    BDIGIT *ds = BDIGITS(x);
71
71
    BDIGIT_DBL num;
72
72
 
 
73
    if (!i) return;
73
74
    while (i--) ds[i] = ~ds[i];
74
75
    i = 0; num = 1;
75
76
    do {
96
97
    long len = RBIGNUM(x)->len;
97
98
    BDIGIT *ds = BDIGITS(x);
98
99
 
99
 
    while (len-- && !ds[len]);
 
100
    if (len == 0) return x;
 
101
    while (--len && !ds[len]);
100
102
    RBIGNUM(x)->len = ++len;
101
103
    return x;
102
104
}
107
109
    long len = RBIGNUM(x)->len;
108
110
    BDIGIT *ds = BDIGITS(x);
109
111
 
110
 
    if (len*SIZEOF_BDIGITS <= sizeof(VALUE)) {
111
 
        SIGNED_VALUE num = 0;
 
112
    if (len*SIZEOF_BDIGITS <= sizeof(long)) {
 
113
        long num = 0;
112
114
        while (len--) {
113
115
            num = BIGUP(num) + ds[len];
114
116
        }
324
326
    VALUE z;
325
327
    BDIGIT *zds;
326
328
 
 
329
#define conv_digit(c) \
 
330
    (!ISASCII(c) ? -1 : \
 
331
     isdigit(c) ? ((c) - '0') : \
 
332
     islower(c) ? ((c) - 'a' + 10) : \
 
333
     isupper(c) ? ((c) - 'A' + 10) : \
 
334
     -1)
 
335
 
327
336
    if (!str) {
328
337
        if (badcheck) goto bad;
329
338
        return INT2FIX(0);
411
420
    }
412
421
    if (*str == '0') {          /* squeeze preceeding 0s */
413
422
        while (*++str == '0');
414
 
        --str;
 
423
        if (!*str) --str;
 
424
    }
 
425
    c = *str;
 
426
    c = conv_digit(c);
 
427
    if (c < 0 || c >= base) {
 
428
        if (badcheck) goto bad;
 
429
        return INT2FIX(0);
415
430
    }
416
431
    len *= strlen(str)*sizeof(char);
417
432
 
418
 
    if (len <= (sizeof(VALUE)*CHAR_BIT)) {
 
433
    if (len <= (sizeof(long)*CHAR_BIT)) {
419
434
        unsigned long val = strtoul(str, &end, base);
420
435
 
421
436
        if (str < end && *end == '_') goto bigparse;
445
460
    z = bignew(len, sign);
446
461
    zds = BDIGITS(z);
447
462
    for (i=len;i--;) zds[i]=0;
448
 
    while (c = *str++) {
 
463
    while ((c = *str++) != 0) {
449
464
        if (c == '_') {
450
465
            if (badcheck) {
451
466
                if (nondigit) goto bad;
453
468
            }
454
469
            continue;
455
470
        }
456
 
        else if (!ISASCII(c)) {
457
 
            break;
458
 
        }
459
 
        else if (isdigit(c)) {
460
 
            c -= '0';
461
 
        }
462
 
        else if (islower(c)) {
463
 
            c -= 'a' - 10;
464
 
        }
465
 
        else if (isupper(c)) {
466
 
            c -= 'A' - 10;
467
 
        }
468
 
        else {
 
471
        else if ((c = conv_digit(c)) < 0) {
469
472
            break;
470
473
        }
471
474
        if (c >= base) break;
593
596
}
594
597
 
595
598
const char ruby_digitmap[] = "0123456789abcdefghijklmnopqrstuvwxyz";
 
599
 
 
600
static VALUE bigsqr(VALUE x);
 
601
static void bigdivmod(VALUE x, VALUE y, VALUE *divp, VALUE *modp);
 
602
 
 
603
#define POW2_P(x) (((x)&((x)-1))==0)
 
604
 
 
605
static inline int
 
606
ones(register unsigned long x)
 
607
{
 
608
#if SIZEOF_ULONG == 8
 
609
# define MASK_55 0x5555555555555555UL
 
610
# define MASK_33 0x3333333333333333UL
 
611
# define MASK_0f 0x0f0f0f0f0f0f0f0fUL
 
612
#else
 
613
# define MASK_55 0x55555555UL
 
614
# define MASK_33 0x33333333UL
 
615
# define MASK_0f 0x0f0f0f0fUL
 
616
#endif
 
617
    x -= (x >> 1) & MASK_55;
 
618
    x = ((x >> 2) & MASK_33) + (x & MASK_33);
 
619
    x = ((x >> 4) + x) & MASK_0f;
 
620
    x += (x >> 8);
 
621
    x += (x >> 16);
 
622
#if SIZEOF_ULONG == 8
 
623
    x += (x >> 32);
 
624
#endif
 
625
    return (int)(x & 0x7f);
 
626
#undef MASK_0f
 
627
#undef MASK_33
 
628
#undef MASK_55
 
629
}
 
630
 
 
631
static inline unsigned long
 
632
next_pow2(register unsigned long x)
 
633
{
 
634
    x |= x >> 1;
 
635
    x |= x >> 2;
 
636
    x |= x >> 4;
 
637
    x |= x >> 8;
 
638
    x |= x >> 16;
 
639
#if SIZEOF_ULONG == 8
 
640
    x |= x >> 32;
 
641
#endif
 
642
    return x + 1;
 
643
}
 
644
 
 
645
static inline int
 
646
floor_log2(register unsigned long x)
 
647
{
 
648
    x |= x >> 1;
 
649
    x |= x >> 2;
 
650
    x |= x >> 4;
 
651
    x |= x >> 8;
 
652
    x |= x >> 16;
 
653
#if SIZEOF_ULONG == 8
 
654
    x |= x >> 32;
 
655
#endif
 
656
    return (int)ones(x) - 1;
 
657
}
 
658
 
 
659
static inline int
 
660
ceil_log2(register unsigned long x)
 
661
{
 
662
    return floor_log2(x) + !POW2_P(x);
 
663
}
 
664
 
 
665
#define LOG2_KARATSUBA_DIGITS 7
 
666
#define KARATSUBA_DIGITS (1L<<LOG2_KARATSUBA_DIGITS)
 
667
#define MAX_BIG2STR_TABLE_ENTRIES 64
 
668
 
 
669
static VALUE big2str_power_cache[35][MAX_BIG2STR_TABLE_ENTRIES];
 
670
 
 
671
static void
 
672
power_cache_init(void)
 
673
{
 
674
    int i, j;
 
675
    for (i = 0; i < 35; ++i) {
 
676
        big2str_power_cache[i][0] =
 
677
            rb_big_pow(rb_int2big(i+2), INT2FIX(KARATSUBA_DIGITS));
 
678
        rb_global_variable(&big2str_power_cache[i][0]);
 
679
        for (j = 1; j < MAX_BIG2STR_TABLE_ENTRIES; ++j) {
 
680
            big2str_power_cache[i][j] = Qnil;
 
681
        }
 
682
    }
 
683
}
 
684
 
 
685
static inline VALUE
 
686
power_cache_get_power0(int base, int i)
 
687
{
 
688
    if (NIL_P(big2str_power_cache[base - 2][i])) {
 
689
        big2str_power_cache[base - 2][i] =
 
690
            bigsqr(power_cache_get_power0(base, i - 1));
 
691
        rb_global_variable(&big2str_power_cache[base - 2][i]);
 
692
    }
 
693
    return big2str_power_cache[base - 2][i];
 
694
}
 
695
 
 
696
static VALUE
 
697
power_cache_get_power(int base, long n1, long* m1)
 
698
{
 
699
    long i, j, m;
 
700
    VALUE t;
 
701
 
 
702
    if (n1 <= KARATSUBA_DIGITS)
 
703
        rb_bug("n1 > KARATSUBA_DIGITS");
 
704
 
 
705
    m = ceil_log2(n1);
 
706
    if (m1) *m1 = 1 << m;
 
707
    i = m - LOG2_KARATSUBA_DIGITS;
 
708
    if (i >= MAX_BIG2STR_TABLE_ENTRIES)
 
709
        i = MAX_BIG2STR_TABLE_ENTRIES - 1;
 
710
    t = power_cache_get_power0(base, i);
 
711
 
 
712
    j = KARATSUBA_DIGITS*(1 << i);
 
713
    while (n1 > j) {
 
714
        t = bigsqr(t);
 
715
        j *= 2;
 
716
    }
 
717
    return t;
 
718
}
 
719
 
 
720
/* big2str_muraken_find_n1
 
721
 *
 
722
 * Let a natural number x is given by:
 
723
 * x = 2^0 * x_0 + 2^1 * x_1 + ... + 2^(B*n_0 - 1) * x_{B*n_0 - 1},
 
724
 * where B is BITSPERDIG (i.e. BDIGITS*CHAR_BIT) and n_0 is
 
725
 * RBIGNUM(x)->len.
 
726
 *
 
727
 * Now, we assume n_1 = min_n \{ n | 2^(B*n_0/2) <= b_1^(n_1) \}, so
 
728
 * it is realized that 2^(B*n_0) <= {b_1}^{2*n_1}, where b_1 is a
 
729
 * given radix number. And then, we have n_1 <= (B*n_0) /
 
730
 * (2*log_2(b_1)), therefore n_1 is given by ceil((B*n_0) /
 
731
 * (2*log_2(b_1))).
 
732
 */
 
733
static long
 
734
big2str_find_n1(VALUE x, int base)
 
735
{
 
736
    static const double log_2[] = {
 
737
        1.0,              1.58496250072116, 2.0,
 
738
        2.32192809488736, 2.584962500721,   2.58496250072116,
 
739
        2.8073549220576,  3.0,              3.16992500144231,
 
740
        3.32192809488736, 3.4594316186373,  3.58496250072116,
 
741
        3.70043971814109, 3.8073549220576,  3.90689059560852,
 
742
        4.0,              4.08746284125034, 4.16992500144231,
 
743
        4.24792751344359, 4.32192809488736, 4.39231742277876,
 
744
        4.4594316186373,  4.52356195605701, 4.58496250072116,
 
745
        4.64385618977472, 4.70043971814109, 4.75488750216347,
 
746
        4.8073549220576,  4.85798099512757, 4.90689059560852,
 
747
        4.95419631038688, 5.0,              5.04439411935845,
 
748
        5.08746284125034, 5.12928301694497, 5.16992500144231
 
749
    };
 
750
    long bits;
 
751
 
 
752
    if (base < 2 && 36 < base)
 
753
        rb_bug("illegal radix %d", base);
 
754
 
 
755
    if (FIXNUM_P(x)) {
 
756
        bits = (SIZEOF_LONG*CHAR_BIT - 1)/2 + 1;
 
757
    }
 
758
    else if (BIGZEROP(x)) {
 
759
        return 0;
 
760
    }
 
761
    else {
 
762
        bits = BITSPERDIG*RBIGNUM(x)->len;
 
763
    }
 
764
 
 
765
    return (long)ceil(bits/(2*log_2[base - 2]));
 
766
}
 
767
 
 
768
static long
 
769
big2str_orig(VALUE x, int base, char* ptr, long len, long hbase, int trim)
 
770
{
 
771
    long i = RBIGNUM(x)->len, j = len;
 
772
    BDIGIT* ds = BDIGITS(x);
 
773
 
 
774
    while (i && j > 0) {
 
775
        long k = i;
 
776
        BDIGIT_DBL num = 0;
 
777
 
 
778
        while (k--) {               /* x / hbase */
 
779
            num = BIGUP(num) + ds[k];
 
780
            ds[k] = (BDIGIT)(num / hbase);
 
781
            num %= hbase;
 
782
        }
 
783
        if (trim && ds[i-1] == 0) i--;
 
784
        k = SIZEOF_BDIGITS;
 
785
        while (k--) {
 
786
            ptr[--j] = ruby_digitmap[num % base];
 
787
            num /= base;
 
788
            if (!trim && j <= 0) break;
 
789
            if (trim && i == 0 && num == 0) break;
 
790
        }
 
791
    }
 
792
    if (trim) {
 
793
        while (ptr[j] == '0') j++;
 
794
        MEMMOVE(ptr, ptr + j, char, len - j);
 
795
        len -= j;
 
796
    }
 
797
    return len;
 
798
}
 
799
 
 
800
static long
 
801
big2str_karatsuba(VALUE x, int base, char* ptr,
 
802
                  long n1, long len, long hbase, int trim)
 
803
{
 
804
    long lh, ll, m1;
 
805
    VALUE b, q, r;
 
806
 
 
807
    if (FIXNUM_P(x)) {
 
808
        VALUE str = rb_fix2str(x, base);
 
809
        char* str_ptr = RSTRING_PTR(str);
 
810
        long str_len = RSTRING_LEN(str);
 
811
        if (trim) {
 
812
            if (FIX2INT(x) == 0) return 0;
 
813
            MEMCPY(ptr, str_ptr, char, str_len);
 
814
            return str_len;
 
815
        }
 
816
        else {
 
817
            memset(ptr, '0', len - str_len);
 
818
            MEMCPY(ptr + len - str_len, str_ptr, char, str_len);
 
819
            return len;
 
820
        }
 
821
    }
 
822
    if (BIGZEROP(x)) {
 
823
        if (trim) return 0;
 
824
        else {
 
825
            memset(ptr, '0', len);
 
826
            return len;
 
827
        }
 
828
    }
 
829
 
 
830
    if (n1 <= KARATSUBA_DIGITS) {
 
831
        return big2str_orig(x, base, ptr, len, hbase, trim);
 
832
    }
 
833
 
 
834
    b = power_cache_get_power(base, n1, &m1);
 
835
    bigdivmod(x, b, &q, &r);
 
836
    lh = big2str_karatsuba(q, base, ptr,      (len - m1)/2,
 
837
                           len - m1, hbase, trim);
 
838
    ll = big2str_karatsuba(r, base, ptr + lh, m1/2,
 
839
                           m1,       hbase, !lh && trim);
 
840
 
 
841
    return lh + ll;
 
842
}
 
843
 
596
844
VALUE
597
845
rb_big2str0(VALUE x, int base, int trim)
598
846
{
599
 
    volatile VALUE t;
600
 
    BDIGIT *ds;
601
 
    long i, j, hbase;
602
 
    VALUE ss;
603
 
    char *s;
 
847
    int off;
 
848
    VALUE ss, xx;
 
849
    long n1, len, hbase;
 
850
    char* ptr;
604
851
 
605
852
    if (FIXNUM_P(x)) {
606
 
        return rb_fix2str(x, base);
 
853
        return rb_fix2str(x, base);
607
854
    }
608
855
    if (BIGZEROP(x)) {
609
 
        return rb_str_new2("0");
610
 
    }
611
 
    i = RBIGNUM(x)->len;
612
 
    j = SIZEOF_BDIGITS*CHAR_BIT*i;
613
 
    switch (base) {
614
 
      case 2: break;
615
 
      case 3:
616
 
        j = j * 53L / 84 + 1;
617
 
        break;
618
 
      case 4: case 5: case 6: case 7:
619
 
        j = (j + 1) / 2;
620
 
        break;
621
 
      case 8: case 9:
622
 
        j = (j + 2) / 3;
623
 
        break;
624
 
      case 10: case 11: case 12: case 13: case 14: case 15:
625
 
        j = j * 28L / 93 + 1;
626
 
        break;
627
 
      case 16: case 17: case 18: case 19: case 20: case 21:
628
 
      case 22: case 23: case 24: case 25: case 26: case 27:
629
 
      case 28: case 29: case 30: case 31:
630
 
        j = (j + 3) / 4;
631
 
        break;
632
 
      case 32: case 33: case 34: case 35: case 36:
633
 
        j = (j + 4) / 5;
634
 
        break;
635
 
      default:
636
 
        rb_raise(rb_eArgError, "illegal radix %d", base);
637
 
        break;
638
 
    }
639
 
    j++;                        /* space for sign */
640
 
 
641
 
    hbase = base * base;
 
856
        return rb_str_new2("0");
 
857
    }
 
858
 
 
859
    if (base < 2 && 36 < base)
 
860
        rb_raise(rb_eArgError, "illegal radix %d", base);
 
861
 
 
862
    n1 = big2str_find_n1(x, base);
 
863
    ss = rb_str_new(0, 2*n1 + 1); /* plus one for sign */
 
864
    ptr = RSTRING_PTR(ss);
 
865
    ptr[0] = RBIGNUM(x)->sign ? '+' : '-';
 
866
 
 
867
    hbase = base*base;
642
868
#if SIZEOF_BDIGITS > 2
643
869
    hbase *= hbase;
644
870
#endif
645
 
 
646
 
    t = rb_big_clone(x);
647
 
    ds = BDIGITS(t);
648
 
    ss = rb_str_new(0, j+1);
649
 
    s = RSTRING_PTR(ss);
650
 
 
651
 
    s[0] = RBIGNUM(x)->sign ? '+' : '-';
652
 
    while (i && j > 1) {
653
 
        long k = i;
654
 
        BDIGIT_DBL num = 0;
655
 
 
656
 
        while (k--) {
657
 
            num = BIGUP(num) + ds[k];
658
 
            ds[k] = (BDIGIT)(num / hbase);
659
 
            num %= hbase;
660
 
        }
661
 
        if (trim && ds[i-1] == 0) i--;
662
 
        k = SIZEOF_BDIGITS;
663
 
        while (k--) {
664
 
            s[--j] = ruby_digitmap[num % base];
665
 
            num /= base;
666
 
            if (!trim && j < 1) break;
667
 
            if (trim && i == 0 && num == 0) break;
668
 
        }
669
 
    }
670
 
    if (trim) {while (s[j] == '0') j++;}
671
 
    i = RSTRING_LEN(ss) - j;
672
 
    if (RBIGNUM(x)->sign) {
673
 
        memmove(s, s+j, i);
674
 
        i--;
 
871
    off = !(trim && RBIGNUM(x)->sign); /* erase plus sign if trim */
 
872
    xx = rb_big_clone(x);
 
873
    RBIGNUM(xx)->sign = 1;
 
874
    if (n1 <= KARATSUBA_DIGITS) {
 
875
        len = off + big2str_orig(xx, base, ptr + off, 2*n1, hbase, trim);
675
876
    }
676
877
    else {
677
 
        memmove(s+1, s+j, i);
 
878
        len = off + big2str_karatsuba(xx, base, ptr + off, n1,
 
879
                                      2*n1, hbase, trim);
678
880
    }
679
 
    rb_str_set_len(ss, i);
 
881
 
 
882
    ptr[len] = '\0';
 
883
    rb_str_resize(ss, len);
680
884
 
681
885
    return ss;
682
886
}
684
888
VALUE
685
889
rb_big2str(VALUE x, int base)
686
890
{
687
 
    return rb_big2str0(x, base, Qtrue);
 
891
    return rb_big2str0(x, base, 1);
688
892
}
689
893
 
690
894
/*
959
1163
      case T_BIGNUM:
960
1164
        break;
961
1165
      case T_FLOAT:
962
 
        {
 
1166
        {
963
1167
            volatile double a, b;
964
1168
 
965
1169
            a = RFLOAT(y)->value;
1036
1240
    if (!RBIGNUM(x)->sign) get2comp(z);
1037
1241
    ds = BDIGITS(z);
1038
1242
    i = RBIGNUM(x)->len;
 
1243
    if (!i) return INT2FIX(~(SIGNED_VALUE)0);
1039
1244
    while (i--) {
1040
1245
        ds[i] = ~ds[i];
1041
1246
    }
1106
1311
 
1107
1312
    if (RBIGNUM(x)->len > RBIGNUM(y)->len) {
1108
1313
        len = RBIGNUM(x)->len + 1;
1109
 
        z = x; x = y; y = z;
 
1314
        z = x; x = y; y = z;
1110
1315
    }
1111
1316
    else {
1112
1317
        len = RBIGNUM(y)->len + 1;
1526
1731
    return size;
1527
1732
}
1528
1733
 
1529
 
static VALUE rb_big_rshift(VALUE,VALUE);
 
1734
static VALUE big_lshift(VALUE, unsigned long);
 
1735
static VALUE big_rshift(VALUE, unsigned long);
 
1736
 
 
1737
static VALUE big_shift(VALUE x, int n)
 
1738
{
 
1739
    if (n < 0)
 
1740
        return big_lshift(x, (unsigned int)n);
 
1741
    else if (n > 0)
 
1742
        return big_rshift(x, (unsigned int)n);
 
1743
    return x;
 
1744
}
1530
1745
 
1531
1746
/*
1532
1747
 *  call-seq:
1555
1770
        ex = (RBIGNUM(bigtrunc(x))->len - 1) * BITSPERDIG;
1556
1771
        ex += bdigbitsize(BDIGITS(x)[RBIGNUM(x)->len - 1]);
1557
1772
        ex -= 2 * DBL_BIGDIG * BITSPERDIG;
1558
 
        if (ex) x = rb_big_rshift(x, INT2FIX(ex));
 
1773
        if (ex) x = big_shift(x, ex);
1559
1774
 
1560
1775
        switch (TYPE(y)) {
1561
1776
          case T_FIXNUM:
1564
1779
            ey = (RBIGNUM(bigtrunc(y))->len - 1) * BITSPERDIG;
1565
1780
            ey += bdigbitsize(BDIGITS(y)[RBIGNUM(y)->len - 1]);
1566
1781
            ey -= DBL_BIGDIG * BITSPERDIG;
1567
 
            if (ey) y = rb_big_rshift(y, INT2FIX(ey));
 
1782
            if (ey) y = big_shift(y, ey);
1568
1783
          bignum:
1569
1784
            bigdivrem(x, y, &z, 0);
1570
1785
            return rb_float_new(ldexp(big2dbl(z), ex - ey));
1602
1817
    BDIGIT_DBL num;
1603
1818
 
1604
1819
    if (len < 4000 / BITSPERDIG) {
1605
 
        return rb_big_mul0(x, x);
 
1820
        return bigtrunc(rb_big_mul0(x, x));
1606
1821
    }
1607
1822
 
1608
1823
    a = bignew(len - k, 1);
1671
1886
        yy = FIX2LONG(y);
1672
1887
        if (yy > 0) {
1673
1888
            VALUE z = 0;
1674
 
            SIGNED_VALUE mask, n = 1;
 
1889
            SIGNED_VALUE mask;
 
1890
            const long BIGLEN_LIMIT = 1024*1024 / SIZEOF_BDIGITS;
1675
1891
 
1676
 
            if (RBIGNUM(x)->len * SIZEOF_BDIGITS * yy > 1024*1024) {
 
1892
            if ((RBIGNUM(x)->len > BIGLEN_LIMIT) ||
 
1893
                (RBIGNUM(x)->len > BIGLEN_LIMIT / yy)) {
1677
1894
                rb_warn("in a**b, b may be too big");
1678
1895
                d = (double)yy;
1679
1896
                break;
1680
1897
            }
1681
1898
            for (mask = FIXNUM_MAX + 1; mask; mask >>= 1) {
1682
 
                if (!z) {
1683
 
                    SIGNED_VALUE n2 = n * n;
1684
 
                    if (!POSFIXABLE(n2) || (n2 / n != n)) {
1685
 
                        z = bigtrunc(bigsqr(rb_int2big(n)));
1686
 
                    }
1687
 
                    else {
1688
 
                        n = n2;
1689
 
                    }
1690
 
                }
1691
 
                else {
1692
 
                    z = bigtrunc(bigsqr(z));
1693
 
                }
 
1899
                if (z) z = bigtrunc(bigsqr(z));
1694
1900
                if (yy & mask) {
1695
 
                    if (!z) z = rb_int2big(n);
1696
 
                    z = bigtrunc(rb_big_mul0(z, x));
 
1901
                    z = z ? bigtrunc(rb_big_mul0(z, x)) : x;
1697
1902
                }
1698
1903
            }
1699
1904
            return bignorm(z);
1879
2084
    return bignorm(z);
1880
2085
}
1881
2086
 
 
2087
static VALUE
 
2088
check_shiftdown(VALUE y, VALUE x)
 
2089
{
 
2090
    if (!RBIGNUM(x)->len) return INT2FIX(0);
 
2091
    if (RBIGNUM(y)->len > SIZEOF_LONG / SIZEOF_BDIGITS) {
 
2092
        return RBIGNUM(x)->sign ? INT2FIX(0) : INT2FIX(-1);
 
2093
    }
 
2094
    return Qnil;
 
2095
}
 
2096
 
1882
2097
/*
1883
2098
 * call-seq:
1884
2099
 *     big << numeric   =>  integer
1889
2104
VALUE
1890
2105
rb_big_lshift(VALUE x, VALUE y)
1891
2106
{
 
2107
    long shift;
 
2108
    int neg = 0;
 
2109
 
 
2110
    for (;;) {
 
2111
        if (FIXNUM_P(y)) {
 
2112
            shift = FIX2LONG(y);
 
2113
            if (shift < 0) {
 
2114
                neg = 1;
 
2115
                shift = -shift;
 
2116
            }
 
2117
            break;
 
2118
        }
 
2119
        else if (TYPE(y) == T_BIGNUM) {
 
2120
            if (!RBIGNUM(y)->sign) {
 
2121
                VALUE t = check_shiftdown(y, x);
 
2122
                if (!NIL_P(t)) return t;
 
2123
                neg = 1;
 
2124
            }
 
2125
            shift = big2ulong(y, "long", Qtrue);
 
2126
            break;
 
2127
        }
 
2128
        y = rb_to_int(y);
 
2129
    }
 
2130
 
 
2131
    if (neg) return big_rshift(x, shift);
 
2132
    return big_lshift(x, shift);
 
2133
}
 
2134
 
 
2135
static VALUE
 
2136
big_lshift(VALUE x, unsigned long shift)
 
2137
{
1892
2138
    BDIGIT *xds, *zds;
1893
 
    int shift = NUM2INT(y);
1894
 
    int s1 = shift/BITSPERDIG;
 
2139
    long s1 = shift/BITSPERDIG;
1895
2140
    int s2 = shift%BITSPERDIG;
1896
2141
    VALUE z;
1897
2142
    BDIGIT_DBL num = 0;
1898
2143
    long len, i;
1899
2144
 
1900
 
    if (shift < 0) return rb_big_rshift(x, INT2FIX(-shift));
1901
2145
    len = RBIGNUM(x)->len;
1902
2146
    z = bignew(len+s1+1, RBIGNUM(x)->sign);
1903
2147
    zds = BDIGITS(z);
1921
2165
 * Shifts big right _numeric_ positions (left if _numeric_ is negative).
1922
2166
 */
1923
2167
 
1924
 
static VALUE
 
2168
VALUE
1925
2169
rb_big_rshift(VALUE x, VALUE y)
1926
2170
{
 
2171
    long shift;
 
2172
    int neg = 0;
 
2173
 
 
2174
    for (;;) {
 
2175
        if (FIXNUM_P(y)) {
 
2176
            shift = FIX2LONG(y);
 
2177
            if (shift < 0) {
 
2178
                neg = 1;
 
2179
                shift = -shift;
 
2180
            }
 
2181
            break;
 
2182
        }
 
2183
        else if (TYPE(y) == T_BIGNUM) {
 
2184
            if (RBIGNUM(y)->sign) {
 
2185
                VALUE t = check_shiftdown(y, x);
 
2186
                if (!NIL_P(t)) return t;
 
2187
            }
 
2188
            else {
 
2189
                neg = 1;
 
2190
            }
 
2191
            shift = big2ulong(y, "long", Qtrue);
 
2192
            break;
 
2193
        }
 
2194
        y = rb_to_int(y);
 
2195
    }
 
2196
 
 
2197
    if (neg) return big_lshift(x, shift);
 
2198
    return big_rshift(x, shift);
 
2199
}
 
2200
 
 
2201
static VALUE
 
2202
big_rshift(VALUE x, unsigned long shift)
 
2203
{
1927
2204
    BDIGIT *xds, *zds;
1928
 
    int shift = NUM2INT(y);
1929
2205
    long s1 = shift/BITSPERDIG;
1930
 
    long s2 = shift%BITSPERDIG;
 
2206
    int s2 = shift%BITSPERDIG;
1931
2207
    VALUE z;
1932
2208
    BDIGIT_DBL num = 0;
1933
2209
    long i, j;
1934
2210
    volatile VALUE save_x;
1935
2211
 
1936
 
    if (shift < 0) return rb_big_lshift(x, INT2FIX(-shift));
1937
 
 
1938
2212
    if (s1 > RBIGNUM(x)->len) {
1939
2213
        if (RBIGNUM(x)->sign)
1940
2214
            return INT2FIX(0);
1990
2264
rb_big_aref(VALUE x, VALUE y)
1991
2265
{
1992
2266
    BDIGIT *xds;
1993
 
    int shift;
1994
 
    long s1, s2;
 
2267
    BDIGIT_DBL num;
 
2268
    VALUE shift;
 
2269
    long i, s1, s2;
1995
2270
 
1996
2271
    if (TYPE(y) == T_BIGNUM) {
1997
 
        if (!RBIGNUM(y)->sign || RBIGNUM(x)->sign)
 
2272
        if (!RBIGNUM(y)->sign)
1998
2273
            return INT2FIX(0);
1999
 
        return INT2FIX(1);
2000
 
    }
2001
 
    shift = NUM2INT(y);
2002
 
    if (shift < 0) return INT2FIX(0);
 
2274
        if (RBIGNUM(bigtrunc(y))->len > SIZEOF_VALUE/SIZEOF_BDIGITS) {
 
2275
          out_of_range:
 
2276
            return RBIGNUM(x)->sign ? INT2FIX(0) : INT2FIX(1);
 
2277
        }
 
2278
        shift = big2ulong(y, "long", Qfalse);
 
2279
    }
 
2280
    else {
 
2281
        i = NUM2LONG(y);
 
2282
        if (i < 0) return INT2FIX(0);
 
2283
        shift = (VALUE)i;
 
2284
    }
2003
2285
    s1 = shift/BITSPERDIG;
2004
2286
    s2 = shift%BITSPERDIG;
2005
2287
 
 
2288
    if (s1 >= RBIGNUM(x)->len) goto out_of_range;
2006
2289
    if (!RBIGNUM(x)->sign) {
2007
 
        if (s1 >= RBIGNUM(x)->len) return INT2FIX(1);
2008
 
        x = rb_big_clone(x);
2009
 
        get2comp(x);
 
2290
        xds = BDIGITS(x);
 
2291
        i = 0; num = 1;
 
2292
        while (num += ~xds[i], ++i <= s1) {
 
2293
            num = BIGDN(num);
 
2294
        }
2010
2295
    }
2011
2296
    else {
2012
 
        if (s1 >= RBIGNUM(x)->len) return INT2FIX(0);
 
2297
        num = BDIGITS(x)[s1];
2013
2298
    }
2014
 
    xds = BDIGITS(x);
2015
 
    if (xds[s1] & (1<<s2))
 
2299
    if (num & ((BDIGIT_DBL)1<<s2))
2016
2300
        return INT2FIX(1);
2017
2301
    return INT2FIX(0);
2018
2302
}
2029
2313
{
2030
2314
    int hash;
2031
2315
 
2032
 
    hash = rb_memhash(BDIGITS(x), BITSPERDIG*RBIGNUM(x)->len) ^ RBIGNUM(x)->sign;
 
2316
    hash = rb_memhash(BDIGITS(x), sizeof(BDIGIT)*RBIGNUM(x)->len) ^ RBIGNUM(x)->sign;
2033
2317
    return INT2FIX(hash);
2034
2318
}
2035
2319
 
2144
2428
    rb_define_method(rb_cBignum, "to_f", rb_big_to_f, 0);
2145
2429
    rb_define_method(rb_cBignum, "abs", rb_big_abs, 0);
2146
2430
    rb_define_method(rb_cBignum, "size", rb_big_size, 0);
 
2431
 
 
2432
    power_cache_init();
2147
2433
}