28 #if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H)
33 #define RB_BIGNUM_TYPE_P(x) RB_TYPE_P((x), T_BIGNUM)
38 #ifndef SIZEOF_BDIGIT_DBL
39 # if SIZEOF_INT*2 <= SIZEOF_LONG_LONG
40 # define SIZEOF_BDIGIT_DBL SIZEOF_LONG_LONG
42 # define SIZEOF_BDIGIT_DBL SIZEOF_LONG
55 #if SIZEOF_BDIGITS < SIZEOF_LONG
61 #ifdef WORDS_BIGENDIAN
62 # define HOST_BIGENDIAN_P 1
64 # define HOST_BIGENDIAN_P 0
66 #define ALIGNOF(type) ((int)offsetof(struct { char f1; type f2; }, f2))
68 #define LSHIFTABLE(d, n) ((n) < sizeof(d) * CHAR_BIT)
69 #define LSHIFTX(d, n) (!LSHIFTABLE(d, n) ? 0 : ((d) << (!LSHIFTABLE(d, n) ? 0 : (n))))
70 #define CLEAR_LOWBITS(d, numbits) ((d) & LSHIFTX(~((d)*0), (numbits)))
71 #define FILL_LOWBITS(d, numbits) ((d) | (LSHIFTX(((d)*0+1), (numbits))-1))
72 #define POW2_P(x) (((x)&((x)-1))==0)
74 #define BDIGITS(x) (RBIGNUM_DIGITS(x))
75 #define BITSPERDIG (SIZEOF_BDIGITS*CHAR_BIT)
76 #define BIGRAD ((BDIGIT_DBL)1 << BITSPERDIG)
77 #define BIGRAD_HALF ((BDIGIT)(BIGRAD >> 1))
78 #define BDIGIT_MSB(d) (((d) & BIGRAD_HALF) != 0)
79 #define BIGUP(x) LSHIFTX(((x) + (BDIGIT_DBL)0), BITSPERDIG)
80 #define BIGDN(x) RSHIFT((x),BITSPERDIG)
81 #define BIGLO(x) ((BDIGIT)((x) & BDIGMAX))
82 #define BDIGMAX ((BDIGIT)(BIGRAD-1))
83 #define BDIGIT_DBL_MAX (~(BDIGIT_DBL)0)
85 #if SIZEOF_BDIGITS == 2
86 # define swap_bdigit(x) swap16(x)
87 #elif SIZEOF_BDIGITS == 4
88 # define swap_bdigit(x) swap32(x)
89 #elif SIZEOF_BDIGITS == 8
90 # define swap_bdigit(x) swap64(x)
93 #define BIGZEROP(x) (RBIGNUM_LEN(x) == 0 || \
94 (BDIGITS(x)[0] == 0 && \
95 (RBIGNUM_LEN(x) == 1 || bigzero_p(x))))
96 #define BIGSIZE(x) (RBIGNUM_LEN(x) == 0 ? (size_t)0 : \
97 BDIGITS(x)[RBIGNUM_LEN(x)-1] ? \
98 (size_t)(RBIGNUM_LEN(x)*SIZEOF_BDIGITS - nlz(BDIGITS(x)[RBIGNUM_LEN(x)-1])/CHAR_BIT) : \
99 rb_absint_size(x, NULL))
101 #define BIGDIVREM_EXTRA_WORDS 1
102 #define roomof(n, m) ((long)(((n)+(m)-1) / (m)))
103 #define bdigit_roomof(n) roomof(n, SIZEOF_BDIGITS)
104 #define BARY_ARGS(ary) ary, numberof(ary)
106 #define BARY_ADD(z, x, y) bary_add(BARY_ARGS(z), BARY_ARGS(x), BARY_ARGS(y))
107 #define BARY_SUB(z, x, y) bary_sub(BARY_ARGS(z), BARY_ARGS(x), BARY_ARGS(y))
108 #define BARY_SHORT_MUL(z, x, y) bary_short_mul(BARY_ARGS(z), BARY_ARGS(x), BARY_ARGS(y))
109 #define BARY_DIVMOD(q, r, x, y) bary_divmod(BARY_ARGS(q), BARY_ARGS(r), BARY_ARGS(x), BARY_ARGS(y))
110 #define BARY_ZERO_P(x) bary_zero_p(BARY_ARGS(x))
112 #define RBIGNUM_SET_NEGATIVE_SIGN(b) RBIGNUM_SET_SIGN(b, 0)
113 #define RBIGNUM_SET_POSITIVE_SIGN(b) RBIGNUM_SET_SIGN(b, 1)
115 #define bignew(len,sign) bignew_1(rb_cBignum,(len),(sign))
117 #define BDIGITS_ZERO(ptr, n) do { \
118 BDIGIT *bdigitz_zero_ptr = (ptr); \
119 size_t bdigitz_zero_n = (n); \
120 while (bdigitz_zero_n) { \
121 *bdigitz_zero_ptr++ = 0; \
126 #define BARY_TRUNC(ds, n) do { \
127 while (0 < (n) && (ds)[(n)-1] == 0) \
131 #define KARATSUBA_BALANCED(xn, yn) ((yn)/2 < (xn))
132 #define TOOM3_BALANCED(xn, yn) (((yn)+2)/3 * 2 < (xn))
134 #define GMP_MUL_DIGITS 20
135 #define KARATSUBA_MUL_DIGITS 70
136 #define TOOM3_MUL_DIGITS 150
138 #define GMP_DIV_DIGITS 20
139 #define GMP_BIG2STR_DIGITS 20
140 #define GMP_STR2BIG_DIGITS 20
158 #if SIZEOF_BDIGITS <= SIZEOF_INT
160 #elif SIZEOF_BDIGITS <= SIZEOF_LONG
162 #elif SIZEOF_BDIGITS <= SIZEOF_LONG_LONG
164 #elif SIZEOF_BDIGITS <= SIZEOF_INT128_T
168 #define U16(a) ((uint16_t)(a))
169 #define U32(a) ((uint32_t)(a))
171 #define U64(a,b) (((uint64_t)(a) << 32) | (b))
173 #ifdef HAVE_UINT128_T
174 #define U128(a,b,c,d) (((uint128_t)U64(a,b) << 64) | U64(c,d))
221 #if SIZEOF_BDIGIT_DBL == 2
222 static const int maxpow16_exp[35] = {
223 15, 10, 7, 6, 6, 5, 5, 5, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3,
224 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
226 static const uint16_t maxpow16_num[35] = {
227 U16(0x00008000),
U16(0x0000e6a9),
U16(0x00004000),
U16(0x00003d09),
228 U16(0x0000b640),
U16(0x000041a7),
U16(0x00008000),
U16(0x0000e6a9),
229 U16(0x00002710),
U16(0x00003931),
U16(0x00005100),
U16(0x00006f91),
230 U16(0x00009610),
U16(0x0000c5c1),
U16(0x00001000),
U16(0x00001331),
231 U16(0x000016c8),
U16(0x00001acb),
U16(0x00001f40),
U16(0x0000242d),
232 U16(0x00002998),
U16(0x00002f87),
U16(0x00003600),
U16(0x00003d09),
233 U16(0x000044a8),
U16(0x00004ce3),
U16(0x000055c0),
U16(0x00005f45),
234 U16(0x00006978),
U16(0x0000745f),
U16(0x00008000),
U16(0x00008c61),
235 U16(0x00009988),
U16(0x0000a77b),
U16(0x0000b640),
237 #elif SIZEOF_BDIGIT_DBL == 4
238 static const int maxpow32_exp[35] = {
239 31, 20, 15, 13, 12, 11, 10, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7,
240 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
242 static const uint32_t maxpow32_num[35] = {
243 U32(0x80000000),
U32(0xcfd41b91),
U32(0x40000000),
U32(0x48c27395),
244 U32(0x81bf1000),
U32(0x75db9c97),
U32(0x40000000),
U32(0xcfd41b91),
245 U32(0x3b9aca00),
U32(0x8c8b6d2b),
U32(0x19a10000),
U32(0x309f1021),
246 U32(0x57f6c100),
U32(0x98c29b81),
U32(0x10000000),
U32(0x18754571),
247 U32(0x247dbc80),
U32(0x3547667b),
U32(0x4c4b4000),
U32(0x6b5a6e1d),
248 U32(0x94ace180),
U32(0xcaf18367),
U32(0x0b640000),
U32(0x0e8d4a51),
249 U32(0x1269ae40),
U32(0x17179149),
U32(0x1cb91000),
U32(0x23744899),
250 U32(0x2b73a840),
U32(0x34e63b41),
U32(0x40000000),
U32(0x4cfa3cc1),
251 U32(0x5c13d840),
U32(0x6d91b519),
U32(0x81bf1000),
253 #elif SIZEOF_BDIGIT_DBL == 8 && defined HAVE_UINT64_T
254 static const int maxpow64_exp[35] = {
255 63, 40, 31, 27, 24, 22, 21, 20, 19, 18, 17, 17, 16, 16, 15, 15, 15,
256 15, 14, 14, 14, 14, 13, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12,
259 static const uint64_t maxpow64_num[35] = {
260 U64(0x80000000,0x00000000), U64(0xa8b8b452,0x291fe821),
261 U64(0x40000000,0x00000000), U64(0x6765c793,0xfa10079d),
262 U64(0x41c21cb8,0xe1000000), U64(0x36427987,0x50226111),
263 U64(0x80000000,0x00000000), U64(0xa8b8b452,0x291fe821),
264 U64(0x8ac72304,0x89e80000), U64(0x4d28cb56,0xc33fa539),
265 U64(0x1eca170c,0x00000000), U64(0x780c7372,0x621bd74d),
266 U64(0x1e39a505,0x7d810000), U64(0x5b27ac99,0x3df97701),
267 U64(0x10000000,0x00000000), U64(0x27b95e99,0x7e21d9f1),
268 U64(0x5da0e1e5,0x3c5c8000), U64(0xd2ae3299,0xc1c4aedb),
269 U64(0x16bcc41e,0x90000000), U64(0x2d04b7fd,0xd9c0ef49),
270 U64(0x5658597b,0xcaa24000), U64(0xa0e20737,0x37609371),
271 U64(0x0c29e980,0x00000000), U64(0x14adf4b7,0x320334b9),
272 U64(0x226ed364,0x78bfa000), U64(0x383d9170,0xb85ff80b),
273 U64(0x5a3c23e3,0x9c000000), U64(0x8e651373,0x88122bcd),
274 U64(0xdd41bb36,0xd259e000), U64(0x0aee5720,0xee830681),
275 U64(0x10000000,0x00000000), U64(0x172588ad,0x4f5f0981),
276 U64(0x211e44f7,0xd02c1000), U64(0x2ee56725,0xf06e5c71),
277 U64(0x41c21cb8,0xe1000000),
279 #elif SIZEOF_BDIGIT_DBL == 16 && defined HAVE_UINT128_T
280 static const int maxpow128_exp[35] = {
281 127, 80, 63, 55, 49, 45, 42, 40, 38, 37, 35, 34, 33, 32, 31, 31, 30,
282 30, 29, 29, 28, 28, 27, 27, 27, 26, 26, 26, 26, 25, 25, 25, 25, 24,
285 static const uint128_t maxpow128_num[35] = {
286 U128(0x80000000,0x00000000,0x00000000,0x00000000),
287 U128(0x6f32f1ef,0x8b18a2bc,0x3cea5978,0x9c79d441),
288 U128(0x40000000,0x00000000,0x00000000,0x00000000),
289 U128(0xd0cf4b50,0xcfe20765,0xfff4b4e3,0xf741cf6d),
290 U128(0x6558e2a0,0x921fe069,0x42860000,0x00000000),
291 U128(0x5080c7b7,0xd0e31ba7,0x5911a67d,0xdd3d35e7),
292 U128(0x40000000,0x00000000,0x00000000,0x00000000),
293 U128(0x6f32f1ef,0x8b18a2bc,0x3cea5978,0x9c79d441),
294 U128(0x4b3b4ca8,0x5a86c47a,0x098a2240,0x00000000),
295 U128(0xffd1390a,0x0adc2fb8,0xdabbb817,0x4d95c99b),
296 U128(0x2c6fdb36,0x4c25e6c0,0x00000000,0x00000000),
297 U128(0x384bacd6,0x42c343b4,0xe90c4272,0x13506d29),
298 U128(0x31f5db32,0xa34aced6,0x0bf13a0e,0x00000000),
299 U128(0x20753ada,0xfd1e839f,0x53686d01,0x3143ee01),
300 U128(0x10000000,0x00000000,0x00000000,0x00000000),
301 U128(0x68ca11d6,0xb4f6d1d1,0xfaa82667,0x8073c2f1),
302 U128(0x223e493b,0xb3bb69ff,0xa4b87d6c,0x40000000),
303 U128(0xad62418d,0x14ea8247,0x01c4b488,0x6cc66f59),
304 U128(0x2863c1f5,0xcdae42f9,0x54000000,0x00000000),
305 U128(0xa63fd833,0xb9386b07,0x36039e82,0xbe651b25),
306 U128(0x1d1f7a9c,0xd087a14d,0x28cdf3d5,0x10000000),
307 U128(0x651b5095,0xc2ea8fc1,0xb30e2c57,0x77aaf7e1),
308 U128(0x0ddef20e,0xff760000,0x00000000,0x00000000),
309 U128(0x29c30f10,0x29939b14,0x6664242d,0x97d9f649),
310 U128(0x786a435a,0xe9558b0e,0x6aaf6d63,0xa8000000),
311 U128(0x0c5afe6f,0xf302bcbf,0x94fd9829,0xd87f5079),
312 U128(0x1fce575c,0xe1692706,0x07100000,0x00000000),
313 U128(0x4f34497c,0x8597e144,0x36e91802,0x00528229),
314 U128(0xbf3a8e1d,0x41ef2170,0x7802130d,0x84000000),
315 U128(0x0e7819e1,0x7f1eb0fb,0x6ee4fb89,0x01d9531f),
316 U128(0x20000000,0x00000000,0x00000000,0x00000000),
317 U128(0x4510460d,0xd9e879c0,0x14a82375,0x2f22b321),
318 U128(0x91abce3c,0x4b4117ad,0xe76d35db,0x22000000),
319 U128(0x08973ea3,0x55d75bc2,0x2e42c391,0x727d69e1),
320 U128(0x10e425c5,0x6daffabc,0x35c10000,0x00000000),
330 assert(2 <= base && base <= 36);
333 #if SIZEOF_BDIGIT_DBL == 2
334 maxpow = maxpow16_num[base-2];
335 exponent = maxpow16_exp[base-2];
336 #elif SIZEOF_BDIGIT_DBL == 4
337 maxpow = maxpow32_num[base-2];
338 exponent = maxpow32_exp[base-2];
339 #elif SIZEOF_BDIGIT_DBL == 8 && defined HAVE_UINT64_T
340 maxpow = maxpow64_num[base-2];
341 exponent = maxpow64_exp[base-2];
342 #elif SIZEOF_BDIGIT_DBL == 16 && defined HAVE_UINT128_T
343 maxpow = maxpow128_num[base-2];
344 exponent = maxpow128_exp[base-2];
365 return ds[0] |
BIGUP(ds[1]);
391 while (xn-- && xds[xn] == yds[xn])
393 if (xn == (
size_t)-1)
395 return xds[xn] < yds[xn] ? -1 : 1;
405 for (i=0; i<
n; i++) {
421 num =
BIGUP(higher_bdigit);
423 num = (num | xds[
n]) >> shift;
436 if (xds[--xn])
return 0;
453 for (i = 0; i <
n; i++) {
461 ds[
i] =
BIGLO(~ds[i] + 1);
473 BDIGIT *p2 = ds + num_bdigits - 1;
474 for (; p1 < p2; p1++, p2--) {
481 #define INTEGER_PACK_WORDORDER_MASK \
482 (INTEGER_PACK_MSWORD_FIRST | \
483 INTEGER_PACK_LSWORD_FIRST)
484 #define INTEGER_PACK_BYTEORDER_MASK \
485 (INTEGER_PACK_MSBYTE_FIRST | \
486 INTEGER_PACK_LSBYTE_FIRST | \
487 INTEGER_PACK_NATIVE_BYTE_ORDER)
495 if (flags & ~supported_flags) {
498 if (wordorder_bits == 0) {
505 if (byteorder_bits == 0) {
524 size_t numwords,
size_t wordsize,
size_t nails,
int flags,
525 size_t *word_num_fullbytes_ret,
526 int *word_num_partialbits_ret,
527 size_t *word_start_ret,
528 ssize_t *word_step_ret,
529 size_t *word_last_ret,
530 size_t *byte_start_ret,
535 size_t word_num_fullbytes;
536 int word_num_partialbits;
544 if (word_num_partialbits == CHAR_BIT)
545 word_num_partialbits = 0;
546 word_num_fullbytes = wordsize - (nails /
CHAR_BIT);
547 if (word_num_partialbits != 0) {
548 word_num_fullbytes--;
552 word_start = wordsize*(numwords-1);
553 word_step = -(ssize_t)wordsize;
558 word_step = wordsize;
559 word_last = wordsize*(numwords-1);
563 #ifdef WORDS_BIGENDIAN
570 byte_start = wordsize-1;
578 *word_num_partialbits_ret = word_num_partialbits;
579 *word_num_fullbytes_ret = word_num_fullbytes;
580 *word_start_ret = word_start;
581 *word_step_ret = word_step;
582 *word_last_ret = word_last;
583 *byte_start_ret = byte_start;
584 *byte_step_ret = byte_step;
591 *ddp |= (
BDIGIT_DBL)(*(*dpp)++) << *numbits_in_dd_p;
594 else if (*dpp == *dep) {
606 *numbits_in_dd_p -=
n;
610 #if !defined(WORDS_BIGENDIAN)
615 for (i = 0; i <
len; i++)
617 for (i = 0; i <
len; i++) {
627 bary_pack(
int sign,
BDIGIT *ds,
size_t num_bdigits,
void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
630 unsigned char *
buf, *bufend;
633 de = ds + num_bdigits;
644 while (dp < de && de[-1] == 0)
652 MEMZERO(words,
unsigned char, numwords * wordsize);
655 if (nails == 0 && numwords == 1) {
656 int need_swap = wordsize != 1 &&
662 *((
unsigned char *)words) = (
unsigned char)(d = dp[0]);
663 return ((1 < de - dp ||
CLEAR_LOWBITS(d, 8) != 0) ? 2 : 1) * sign;
665 #if defined(HAVE_UINT16_T) && 2 <= SIZEOF_BDIGITS
667 uint16_t u = (uint16_t)(d = dp[0]);
668 if (need_swap) u =
swap16(u);
669 *((uint16_t *)words) = u;
670 return ((1 < de - dp ||
CLEAR_LOWBITS(d, 16) != 0) ? 2 : 1) * sign;
673 #if defined(HAVE_UINT32_T) && 4 <= SIZEOF_BDIGITS
676 if (need_swap) u =
swap32(u);
678 return ((1 < de - dp ||
CLEAR_LOWBITS(d, 32) != 0) ? 2 : 1) * sign;
681 #if defined(HAVE_UINT64_T) && 8 <= SIZEOF_BDIGITS
684 if (need_swap) u = swap64(u);
686 return ((1 < de - dp ||
CLEAR_LOWBITS(d, 64) != 0) ? 2 : 1) * sign;
694 return (1 < de - dp ||
FILL_LOWBITS(d, 8) != -1) ? -2 : -1;
696 #if defined(HAVE_UINT16_T) && 2 <= SIZEOF_BDIGITS
699 if (need_swap) u =
swap16(u);
700 *((uint16_t *)words) = u;
701 return (wordsize ==
SIZEOF_BDIGITS && de - dp == 2 && dp[1] == 1 && dp[0] == 0) ? -1 :
705 #if defined(HAVE_UINT32_T) && 4 <= SIZEOF_BDIGITS
708 if (need_swap) u =
swap32(u);
710 return (wordsize ==
SIZEOF_BDIGITS && de - dp == 2 && dp[1] == 1 && dp[0] == 0) ? -1 :
714 #if defined(HAVE_UINT64_T) && 8 <= SIZEOF_BDIGITS
717 if (need_swap) u = swap64(u);
719 return (wordsize ==
SIZEOF_BDIGITS && de - dp == 2 && dp[1] == 1 && dp[0] == 0) ? -1 :
725 #if !defined(WORDS_BIGENDIAN)
730 size_t dst_size = numwords * wordsize;
732 while (0 < src_size && ((
unsigned char *)ds)[src_size-1] == 0)
734 if (src_size <= dst_size) {
735 MEMCPY(words, dp,
char, src_size);
736 MEMZERO((
char*)words + src_size,
char, dst_size - src_size);
739 MEMCPY(words, dp,
char, dst_size);
744 if (zero_p && overflow) {
745 unsigned char *
p = (
unsigned char *)dp;
746 if (dst_size == src_size-1 &&
760 size_t src_num_bdigits = de -
dp;
761 size_t dst_num_bdigits = numwords * bdigits_per_word;
766 if (src_num_bdigits <= dst_num_bdigits) {
775 int zero_p =
bary_2comp(words, dst_num_bdigits);
776 if (zero_p && overflow &&
777 dst_num_bdigits == src_num_bdigits-1 &&
778 dp[dst_num_bdigits] == 1)
783 for (i = 0; i < dst_num_bdigits; i++) {
785 ((
BDIGIT*)words)[
i] = swap_bdigit(d);
788 if (mswordfirst_p ? !msbytefirst_p : msbytefirst_p) {
791 for (i = 0; i < numwords; i++) {
793 p += bdigits_per_word;
806 bufend = buf + numwords * wordsize;
813 if (de - dp == 1 && dp[0] == 1)
820 memset(buf,
'\0', bufend - buf);
822 else if (dp < de && buf < bufend) {
823 int word_num_partialbits;
824 size_t word_num_fullbytes;
830 size_t word_start, word_last;
831 unsigned char *wordp, *last_wordp;
836 &word_num_fullbytes, &word_num_partialbits,
837 &word_start, &word_step, &word_last, &byte_start, &byte_step);
839 wordp = buf + word_start;
840 last_wordp = buf + word_last;
846 integer_pack_fill_dd(&dp, &de, &dd, &numbits_in_dd)
847 #define TAKE_LOWBITS(n) \
848 integer_pack_take_lowbits(n, &dd, &numbits_in_dd)
851 size_t index_in_word = 0;
852 unsigned char *bytep = wordp + byte_start;
853 while (index_in_word < word_num_fullbytes) {
859 if (word_num_partialbits) {
865 while (index_in_word < wordsize) {
871 if (wordp == last_wordp)
878 if (dp != de || 1 < dd) {
889 while (dp < de && *dp == 0)
903 int word_num_partialbits;
904 size_t word_num_fullbytes;
910 size_t word_start, word_last;
911 unsigned char *wordp, *last_wordp;
913 unsigned int partialbits_mask;
917 &word_num_fullbytes, &word_num_partialbits,
918 &word_start, &word_step, &word_last, &byte_start, &byte_step);
920 partialbits_mask = (1 << word_num_partialbits) - 1;
923 wordp = buf + word_start;
924 last_wordp = buf + word_last;
928 size_t index_in_word = 0;
929 unsigned char *bytep = wordp + byte_start;
930 while (index_in_word < word_num_fullbytes) {
931 carry += (
unsigned char)~*bytep;
932 *bytep = (
unsigned char)carry;
937 if (word_num_partialbits) {
938 carry += (*bytep & partialbits_mask) ^ partialbits_mask;
939 *bytep = carry & partialbits_mask;
940 carry >>= word_num_partialbits;
945 if (wordp == last_wordp)
961 size_t num_bits = (wordsize *
CHAR_BIT - nails) * numwords;
975 size_t num_bytes1 = wordsize * numwords;
982 size_t num_bytes2 = num_bytes1 - nails * q1;
989 size_t num_bytes3 = num_bytes2 - q2 * r1;
1013 size_t num_digits2 = num_digits1 +
CHAR_BIT - q4;
1018 size_t tmp1 = r1 * r2 -
CHAR_BIT * r3;
1021 size_t num_digits2 = num_digits1 - q4;
1034 #ifdef DEBUG_INTEGER_PACK
1038 assert(num_bdigits == num_bdigits1);
1039 assert(*nlp_bits_ret == nlp_bits1);
1052 (*ddp) |= ((
BDIGIT_DBL)data) << (*numbits_in_dd_p);
1053 *numbits_in_dd_p += numbits;
1055 *(*dpp)++ =
BIGLO(*ddp);
1068 ((u >> (size *
CHAR_BIT - 1)) ? -1 : 1);
1084 const unsigned char *
buf = words;
1089 de = dp + num_bdigits;
1092 if (nails == 0 && numwords == 1) {
1093 int need_swap = wordsize != 1 &&
1096 if (wordsize == 1) {
1099 #if defined(HAVE_UINT16_T) && 2 <= SIZEOF_BDIGITS
1101 uint16_t u = *(uint16_t *)buf;
1105 #if defined(HAVE_UINT32_T) && 4 <= SIZEOF_BDIGITS
1111 #if defined(HAVE_UINT64_T) && 8 <= SIZEOF_BDIGITS
1118 #if !defined(WORDS_BIGENDIAN)
1122 size_t src_size = numwords * wordsize;
1124 MEMCPY(dp, words,
char, src_size);
1128 memset((
char*)dp + src_size, 0xff, dst_size - src_size);
1130 sign = zero_p ? -2 : -1;
1132 else if (buf[src_size-1] >> (
CHAR_BIT-1)) {
1133 memset((
char*)dp + src_size, 0xff, dst_size - src_size);
1138 MEMZERO((
char*)dp + src_size,
char, dst_size - src_size);
1143 MEMZERO((
char*)dp + src_size,
char, dst_size - src_size);
1156 if (mswordfirst_p) {
1159 if (mswordfirst_p ? !msbytefirst_p : msbytefirst_p) {
1162 for (i = 0; i < numwords; i++) {
1164 p += bdigits_per_word;
1169 for (p = dp; p < de; p++) {
1171 *p = swap_bdigit(d);
1177 sign = zero_p ? -2 : -1;
1194 if (num_bdigits != 0) {
1195 int word_num_partialbits;
1196 size_t word_num_fullbytes;
1202 size_t word_start, word_last;
1203 const unsigned char *wordp, *last_wordp;
1208 &word_num_fullbytes, &word_num_partialbits,
1209 &word_start, &word_step, &word_last, &byte_start, &byte_step);
1211 wordp = buf + word_start;
1212 last_wordp = buf + word_last;
1217 #define PUSH_BITS(data, numbits) \
1218 integer_unpack_push_bits(data, numbits, &dd, &numbits_in_dd, &dp)
1221 size_t index_in_word = 0;
1222 const unsigned char *bytep = wordp + byte_start;
1223 while (index_in_word < word_num_fullbytes) {
1228 if (word_num_partialbits) {
1229 PUSH_BITS(*bytep & ((1 << word_num_partialbits) - 1), word_num_partialbits);
1234 if (wordp == last_wordp)
1253 (bdigits[num_bdigits-1] >> (
BITSPERDIG - nlp_bits - 1))) {
1263 sign =
bary_zero_p(bdigits, num_bdigits) ? -2 : -1;
1266 if (num_bdigits != 0 &&
BDIGIT_MSB(bdigits[num_bdigits-1]))
1272 if (sign == -1 && num_bdigits != 0) {
1281 bary_unpack(
BDIGIT *bdigits,
size_t num_bdigits,
const void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
1283 size_t num_bdigits0;
1300 assert(num_bdigits0 <= num_bdigits);
1302 sign =
bary_unpack_internal(bdigits, num_bdigits0, words, numwords, wordsize, nails, flags, nlp_bits);
1304 if (num_bdigits0 < num_bdigits) {
1305 BDIGITS_ZERO(bdigits + num_bdigits0, num_bdigits - num_bdigits0);
1307 bdigits[num_bdigits0] = 1;
1322 sn = xn < yn ? xn : yn;
1324 num = borrow ? -1 : 0;
1325 for (i = 0; i < sn; i++) {
1331 for (; i < xn; i++) {
1332 if (num == 0)
goto num_is_zero;
1339 for (; i < yn; i++) {
1345 if (num == 0)
goto num_is_zero;
1346 for (; i < zn; i++) {
1352 if (xds == zds && xn == zn)
1354 for (; i < xn; i++) {
1357 for (; i < zn; i++) {
1366 return bary_subb(zds, zn, xds, xn, yds, yn, 0);
1386 tds = xds; xds = yds; yds = tds;
1387 i = xn; xn = yn; yn =
i;
1390 num = carry ? 1 : 0;
1391 for (i = 0; i < xn; i++) {
1396 for (; i < yn; i++) {
1397 if (num == 0)
goto num_is_zero;
1402 for (; i < zn; i++) {
1403 if (num == 0)
goto num_is_zero;
1410 if (yds == zds && yn == zn)
1412 for (; i < yn; i++) {
1415 for (; i < zn; i++) {
1424 return bary_addc(zds, zn, xds, xn, yds, yn, 0);
1431 for (i = 0; i <
n; i++) {
1464 for (j = 0; j < yn; j++) {
1476 for (; j < zn; j++) {
1502 ee = num -
BIGLO(t2);
1504 if (ee) zds[
i] =
BIGLO(num);
1520 zds[yn] =
BIGLO(num);
1534 for (i = 0; i < xn; i++) {
1569 for (i = 0; i < xn-1; i++) {
1579 for (j = i + 1; j < xn; j++) {
1589 zds[i + xn] =
BIGLO(c);
1592 zds[i + xn + 1] += (
BDIGIT)c;
1604 zds[i + xn] +=
BIGLO(c);
1636 r = xn > yn ? yn : xn;
1638 if (2 * (xn + r) <= zn - n) {
1639 tds = zds + n + xn +
r;
1640 mulfunc(tds, tn, xds, xn, yds + n, r, wds, wn);
1653 mulfunc(tds, tn, xds, xn, yds + n, r, wds+xn, wn-xn);
1685 int sub_p, borrow, carry1, carry2, carry3;
1691 const BDIGIT *xds0, *xds1, *yds0, *yds1;
1692 BDIGIT *zds0, *zds1, *zds2, *zds3;
1698 sq = xds == yds && xn == yn;
1748 if (
bary_sub(zds0, n, xds, n, xds+n, xn-n)) {
1760 if (
bary_sub(wds, n, yds, n, yds+n, n)) {
1786 carry1 =
bary_add(wds, n, wds, n, zds0, n);
1787 carry1 =
bary_addc(zds2, n, zds2, n, zds1, n, carry1);
1791 carry2 =
bary_add(zds1, n, zds1, n, wds, n);
1803 carry3 =
bary_add(zds1, n, zds1, n, zds2, n);
1807 carry3 =
bary_addc(zds2, n, zds2, n, zds3, (4*n < zn ? n : zn-3*n), carry3);
1811 bary_add(zds2, zn-2*n, zds2, zn-2*n, wds, n);
1818 if (carry1 + carry3 - borrow < 0)
1820 else if (carry1 + carry3 - borrow > 0) {
1821 BDIGIT c = carry1 + carry3 - borrow;
1822 bary_add(zds3, zn-3*n, zds3, zn-3*n, &c, 1);
1869 size_t x0n;
const BDIGIT *x0ds;
1870 size_t x1n;
const BDIGIT *x1ds;
1871 size_t x2n;
const BDIGIT *x2ds;
1872 size_t y0n;
const BDIGIT *y0ds;
1873 size_t y1n;
const BDIGIT *y1ds;
1874 size_t y2n;
const BDIGIT *y2ds;
1876 size_t u1n;
BDIGIT *u1ds;
int u1p;
1877 size_t u2n;
BDIGIT *u2ds;
int u2p;
1878 size_t u3n;
BDIGIT *u3ds;
int u3p;
1880 size_t v1n;
BDIGIT *v1ds;
int v1p;
1881 size_t v2n;
BDIGIT *v2ds;
int v2p;
1882 size_t v3n;
BDIGIT *v3ds;
int v3p;
1884 size_t t0n;
BDIGIT *t0ds;
int t0p;
1885 size_t t1n;
BDIGIT *t1ds;
int t1p;
1886 size_t t2n;
BDIGIT *t2ds;
int t2p;
1887 size_t t3n;
BDIGIT *t3ds;
int t3p;
1888 size_t t4n;
BDIGIT *t4ds;
int t4p;
1890 size_t z0n;
BDIGIT *z0ds;
1891 size_t z1n;
BDIGIT *z1ds;
int z1p;
1892 size_t z2n;
BDIGIT *z2ds;
int z2p;
1893 size_t z3n;
BDIGIT *z3ds;
int z3p;
1894 size_t z4n;
BDIGIT *z4ds;
1896 size_t zzn;
BDIGIT *zzds;
1898 int sq = xds == yds && xn == yn;
1916 wnc += (t1n = 2*n+2);
1917 wnc += (t2n = 2*n+2);
1918 wnc += (t3n = 2*n+2);
1921 wnc += (z1n = 2*n+1);
1922 wnc += (z2n = 2*n+1);
1923 wnc += (z3n = 2*n+1);
1930 u1ds = wds; wds += u1n;
1931 u2ds = wds; wds += u2n;
1932 u3ds = wds; wds += u3n;
1934 v1ds = wds; wds += v1n;
1935 v2ds = wds; wds += v2n;
1936 v3ds = wds; wds += v3n;
1938 t0ds = wds; wds += t0n;
1939 t1ds = wds; wds += t1n;
1940 t2ds = wds; wds += t2n;
1941 t3ds = wds; wds += t3n;
1942 t4ds = wds; wds += t4n;
1944 z1ds = wds; wds += z1n;
1945 z2ds = wds; wds += z2n;
1946 z3ds = wds; wds += z3n;
2012 bary_add(u1ds, u1n, x0ds, x0n, x2ds, x2n);
2016 if (
bary_sub(u2ds, u2n, u1ds, u1n, x1ds, x1n)) {
2025 bary_add(u1ds, u1n, u1ds, u1n, x1ds, x1n);
2030 bary_add(u3ds, u3n, u2ds, u2n, x2ds, x2n);
2032 else if (
bary_sub(u3ds, u3n, x2ds, x2n, u2ds, u2n)) {
2038 bary_add(u3ds, u3n, u3ds, u3n, x0ds, x0n);
2040 else if (
bary_sub(u3ds, u3n, u3ds, u3n, x0ds, x0n)) {
2046 v1n = u1n; v1ds = u1ds; v1p = u1p;
2047 v2n = u2n; v2ds = u2ds; v2p = u2p;
2048 v3n = u3n; v3ds = u3ds; v3p = u3p;
2052 bary_add(v1ds, v1n, y0ds, y0n, y2ds, y2n);
2057 if (
bary_sub(v2ds, v2n, v1ds, v1n, y1ds, y1n)) {
2063 bary_add(v1ds, v1n, v1ds, v1n, y1ds, y1n);
2068 bary_add(v3ds, v3n, v2ds, v2n, y2ds, y2n);
2070 else if (
bary_sub(v3ds, v3n, y2ds, y2n, v2ds, v2n)) {
2076 bary_add(v3ds, v3n, v3ds, v3n, y0ds, y0n);
2078 else if (
bary_sub(v3ds, v3n, v3ds, v3n, y0ds, y0n)) {
2091 assert(t1ds[t1n-1] == 0);
2097 assert(t2ds[t2n-1] == 0);
2103 assert(t3ds[t3n-1] == 0);
2115 z0n = t0n; z0ds = t0ds;
2118 z4n = t4n; z4ds = t4ds;
2123 if (
bary_sub(z3ds, z3n, t3ds, t3n, t1ds, t1n)) {
2130 bary_add(z3ds, z3n, t3ds, t3n, t1ds, t1n);
2137 if (
bary_sub(z1ds, z1n, t1ds, t1n, t2ds, t2n)) {
2144 bary_add(z1ds, z1n, t1ds, t1n, t2ds, t2n);
2151 if (
bary_sub(z2ds, z2n, t2ds, t2n, t0ds, t0n)) {
2158 bary_add(z2ds, z2n, t2ds, t2n, t0ds, t0n);
2164 if (
bary_sub(z3ds, z3n, z2ds, z2n, z3ds, z3n)) {
2171 bary_add(z3ds, z3n, z2ds, z2n, z3ds, z3n);
2186 bary_add(z2ds, z2n, z2ds, z2n, z1ds, z1n);
2189 if (
bary_sub(z2ds, z2n, z2ds, z2n, z1ds, z1n)) {
2196 if (
bary_sub(z2ds, z2n, z2ds, z2n, t4ds, t4n)) {
2202 bary_add(z2ds, z2n, z2ds, z2n, t4ds, t4n);
2207 if (
bary_sub(z1ds, z1n, z1ds, z1n, z3ds, z3n)) {
2213 bary_add(z1ds, z1n, z1ds, z1n, z3ds, z3n);
2225 bary_add(zzds + n, zzn - n, zzds + n, zzn - n, z1ds, z1n);
2227 bary_sub(zzds + n, zzn - n, zzds + n, zzn - n, z1ds, z1n);
2229 bary_add(zzds + 2*n, zzn - 2*n, zzds + 2*n, zzn - 2*n, z2ds, z2n);
2231 bary_sub(zzds + 2*n, zzn - 2*n, zzds + 2*n, zzn - 2*n, z2ds, z2n);
2233 bary_add(zzds + 3*n, zzn - 3*n, zzds + 3*n, zzn - 3*n, z3ds, z3n);
2235 bary_sub(zzds + 3*n, zzn - 3*n, zzds + 3*n, zzn - 3*n, z3ds, z3n);
2260 bary_mul_gmp(
BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2271 mpz_import(x, xn, -1,
sizeof(
BDIGIT), 0, nails, xds);
2272 if (xds == yds && xn == yn) {
2276 mpz_import(y, yn, -1,
sizeof(
BDIGIT), 0, nails, yds);
2279 mpz_export(zds, &count, -1,
sizeof(
BDIGIT), 0, nails, z);
2303 if (xn == 1 && yn == 1) {
2322 return (c <= 1) ? 1 : 0;
2332 const BDIGIT *xds = *xdsp;
2334 const BDIGIT *yds = *ydsp;
2342 if (xds[xn-1] == 0) {
2358 if (yds[yn-1] == 0) {
2383 tds = xds; xds = yds; yds = tds;
2384 tn = xn; xn = yn; yn = tn;
2404 if (yn == 1 && yds[0] == 1) {
2429 if (xds == yds && xn == yn)
2496 if (xn < naive_threshold) {
2497 if (xds == yds && xn == yn)
2505 if (yn < naive_threshold) {
2512 bary_mul_gmp(zds, zn, xds, xn, yds, yn);
2528 size_t yn = bds->
yn;
2529 size_t zn = bds->
zn;
2539 if (zds[zn-1] == yds[yn-1]) q =
BDIGMAX;
2540 else q = (
BDIGIT)((
BIGUP(zds[zn-1]) + zds[zn-2])/yds[yn-1]);
2570 assert(x_higher_bdigit < y);
2580 t2 = x_higher_bdigit;
2605 assert(zds[zn-1] < yds[yn-1]);
2607 for (ynzero = 0; !yds[ynzero]; ynzero++);
2609 if (ynzero+1 == yn) {
2616 bds.
yn = yn - ynzero;
2617 bds.
zds = zds + ynzero;
2618 bds.
yds = yds + ynzero;
2620 bds.
zn = zn - ynzero;
2621 if (bds.
zn > 10000 || bds.
yn > 10000) {
2644 assert(yn < xn || (xn == yn && yds[yn - 1] <= xds[xn - 1]));
2645 assert(qds ? (xn - yn + 1) <= qn : 1);
2646 assert(rds ? yn <= rn : 1);
2650 shift =
nlz(yds[yn-1]);
2653 int alloc_z = !qds || qn <
zn;
2654 if (alloc_y && alloc_z) {
2666 if (qds && zn <= qn)
2709 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1]))
2733 bary_divmod_gmp(
BDIGIT *qds,
size_t qn,
BDIGIT *rds,
size_t rn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2739 assert(yn < xn || (xn == yn && yds[yn - 1] <= xds[xn - 1]));
2740 assert(qds ? (xn - yn + 1) <= qn : 1);
2741 assert(rds ? yn <= rn : 1);
2746 if (qds) mpz_init(q);
2747 if (rds) mpz_init(r);
2749 mpz_import(x, xn, -1,
sizeof(
BDIGIT), 0, nails, xds);
2750 mpz_import(y, yn, -1,
sizeof(
BDIGIT), 0, nails, yds);
2753 mpz_fdiv_q(q, x, y);
2756 mpz_fdiv_r(r, x, y);
2759 mpz_fdiv_qr(q, r, x, y);
2766 mpz_export(qds, &count, -1,
sizeof(
BDIGIT), 0, nails, q);
2772 mpz_export(rds, &count, -1,
sizeof(
BDIGIT), 0, nails, r);
2790 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1]))
2801 bary_divmod_gmp(qds, qn, rds, rn, xds, xn, yds, yn);
2818 bary_divmod_gmp(qds, qn, rds, rn, xds, xn, yds, yn);
2842 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1])) {
2853 else if (xn == 2 && yn == 2) {
2871 #define BIGNUM_DEBUG 0
2873 #define ON_DEBUG(x) do { x; } while (0)
2875 dump_bignum(
VALUE x)
2887 rb_big_dump(
VALUE x)
2916 if (l > 0)
return 1;
2917 if (l < 0)
return -1;
2930 #define RBIGNUM_SET_LEN(b,l) \
2931 ((RBASIC(b)->flags & RBIGNUM_EMBED_FLAG) ? \
2932 (void)(RBASIC(b)->flags = \
2933 (RBASIC(b)->flags & ~RBIGNUM_EMBED_LEN_MASK) | \
2934 ((l) << RBIGNUM_EMBED_LEN_SHIFT)) : \
2935 (void)(RBIGNUM(b)->as.heap.len = (l)))
2946 RBIGNUM(big)->as.heap.digits = ds;
2947 RBASIC(big)->flags &= ~RBIGNUM_EMBED_FLAG;
2952 ds =
RBIGNUM(big)->as.heap.digits;
3000 return bignew(len, sign != 0);
3074 if (len == 0)
return x;
3075 while (--len && !ds[len]);
3087 #if SIZEOF_BDIGITS < SIZEOF_LONG
3095 if (n == 0)
return INT2FIX(0);
3097 #if SIZEOF_BDIGITS < SIZEOF_LONG
3104 u = (
unsigned long)(
BIGUP(u) + ds[
i]);
3148 #if SIZEOF_BDIGITS >= SIZEOF_VALUE
3158 while (--i && !digits[i]) ;
3171 u = 1 + (
VALUE)(-(n + 1));
3237 int num_leading_zeros;
3246 #if SIZEOF_BDIGITS >= SIZEOF_LONG
3251 for (i = 0; i <
numberof(fixbuf); i++) {
3264 while (dp < de && de[-1] == 0)
3271 num_leading_zeros =
nlz(de[-1]);
3273 *nlz_bits_ret = num_leading_zeros %
CHAR_BIT;
3280 size_t val_numbits = numbytes *
CHAR_BIT - nlz_bits_in_msbyte;
3281 size_t div = val_numbits / word_numbits;
3282 size_t mod = val_numbits % word_numbits;
3285 numwords = mod == 0 ? div : div + 1;
3286 nlz_bits = mod == 0 ? 0 : word_numbits -
mod;
3287 *nlz_bits_ret = nlz_bits;
3297 BDIGIT nlz_bits_in_msbyte_bary[1];
3307 nlz_bits_in_msbyte_bary[0] = nlz_bits_in_msbyte;
3319 if (nlz_bits_in_msbyte)
3320 BARY_SUB(val_numbits_bary, val_numbits_bary, nlz_bits_in_msbyte_bary);
3323 BARY_DIVMOD(div_bary, mod_bary, val_numbits_bary, word_numbits_bary);
3331 nlz_bits = word_numbits -
mod;
3337 #if defined __GNUC__ && (__GNUC__ == 4 && __GNUC_MINOR__ == 4)
3342 *nlz_bits_ret = nlz_bits;
3369 int nlz_bits_in_msbyte;
3373 if (word_numbits == 0)
3380 #ifdef DEBUG_INTEGER_PACK
3382 size_t numwords0, nlz_bits0;
3384 assert(numwords0 == numwords);
3385 assert(nlz_bits0 == nlz_bits);
3392 if (numwords == (
size_t)-1)
3396 *nlz_bits_ret = nlz_bits;
3444 #if SIZEOF_BDIGITS >= SIZEOF_LONG
3449 for (i = 0; i <
numberof(fixbuf); i++) {
3462 while (dp < de && de[-1] == 0)
3464 while (dp < de && dp[0] == 0)
3549 #if SIZEOF_BDIGITS >= SIZEOF_LONG
3554 for (i = 0; i <
numberof(fixbuf); i++) {
3569 return bary_pack(sign, ds, num_bdigits, words, numwords, wordsize, nails, flags);
3624 BDIGIT fixbuf[2] = { 0, 0 };
3646 val =
bignew((
long)num_bdigits, 0);
3649 sign =
bary_unpack_internal(ds, num_bdigits, words, numwords, wordsize, nails, flags, nlp_bits);
3655 else if (num_bdigits ==
numberof(fixbuf)) {
3656 val =
bignew((
long)num_bdigits+1, 0);
3658 BDIGITS(val)[num_bdigits++] = 1;
3661 ds[num_bdigits++] = 1;
3671 if (sign < 0 &&
BDIGIT_MSB(fixbuf[1]) == 0 &&
3674 val =
bignew((
long)num_bdigits, 0 <= sign);
3678 if ((flags & INTEGER_PACK_FORCE_BIGNUM) && sign != 0 &&
3683 if (flags & INTEGER_PACK_FORCE_BIGNUM)
3706 #define conv_digit(c) (ruby_digit36_to_number_table[(unsigned char)(c)])
3712 size_t num_digits = 0;
3713 const char *digits_start =
str;
3714 const char *digits_end =
str;
3718 if (badcheck && *str ==
'_')
goto bad;
3720 while ((c = *str++) != 0) {
3723 if (badcheck)
goto bad;
3726 nondigit = (char) c;
3732 if (c >= base)
break;
3739 if (s+1 < str && str[-1] ==
'_')
goto bad;
3740 while (*str &&
ISSPACE(*str)) str++;
3746 *num_digits_p = num_digits;
3747 *len_p = digits_end - digits_start;
3753 const char *digits_start,
3754 const char *digits_end,
3768 z =
bignew(num_bdigits, sign);
3772 for (p = digits_end; digits_start <
p; p--) {
3776 numbits += bits_per_digit;
3777 if (BITSPERDIG <= numbits) {
3794 const char *digits_start,
3795 const char *digits_end,
3808 z =
bignew(num_bdigits, sign);
3812 for (p = digits_start; p < digits_end; p++) {
3820 zds[i++] =
BIGLO(num);
3829 assert(blen <= num_bdigits);
3838 const char *digits_start,
3839 const char *digits_end,
3842 int digits_per_bdigits_dbl,
3852 int power_level = 0;
3860 vds = uds + num_bdigits;
3867 m = digits_per_bdigits_dbl;
3868 if (num_digits < (
size_t)m)
3869 m = (
int)num_digits;
3870 for (p = digits_end; digits_start <
p; p--) {
3873 dd = dd + c * current_base;
3874 current_base *= base;
3878 uds[i++] =
BIGLO(dd);
3881 m = digits_per_bdigits_dbl;
3882 if (num_digits < (
size_t)
m)
3883 m = (
int)num_digits;
3887 assert(i == num_bdigits);
3888 for (unit = 2; unit < num_bdigits; unit *= 2) {
3889 for (i = 0; i < num_bdigits; i += unit*2) {
3890 if (2*unit <= num_bdigits - i) {
3892 bary_add(vds+i, unit*2, vds+i, unit*2, uds+i, unit);
3894 else if (unit <= num_bdigits - i) {
3896 bary_add(vds+i, num_bdigits-i, vds+i, num_bdigits-i, uds+i, unit);
3909 z =
bignew(num_bdigits, sign);
3922 const char *digits_start,
3923 const char *digits_end,
3937 buf =
ALLOCV_N(
char, tmps, num_digits+1);
3939 for (q = digits_start; q < digits_end; q++) {
3947 mpz_set_str(mz, buf, base);
3951 mpz_export(
BDIGITS(z), &count, -1,
sizeof(
BDIGIT), 0, nails, mz);
3965 const char *
s =
str;
3972 const char *digits_start, *digits_end;
3986 if (str[0] ==
'+') {
3989 else if (str[0] ==
'-') {
3993 if (str[0] ==
'+' || str[0] ==
'-') {
3994 if (badcheck)
goto bad;
3998 if (str[0] ==
'0') {
4020 else if (base < -1) {
4027 else if (base == 2) {
4028 if (str[0] ==
'0' && (str[1] ==
'b'||str[1] ==
'B')) {
4032 else if (base == 8) {
4033 if (str[0] ==
'0' && (str[1] ==
'o'||str[1] ==
'O')) {
4037 else if (base == 10) {
4038 if (str[0] ==
'0' && (str[1] ==
'd'||str[1] ==
'D')) {
4042 else if (base == 16) {
4043 if (str[0] ==
'0' && (str[1] ==
'x'||str[1] ==
'X')) {
4047 if (base < 2 || 36 < base) {
4052 while ((c = *++str) ==
'0' || c ==
'_') {
4063 if (c < 0 || c >= base) {
4064 if (badcheck)
goto bad;
4071 unsigned long val =
STRTOUL(str, &end, base);
4073 if (str < end && *end ==
'_')
goto bigparse;
4075 if (end == str)
goto bad;
4076 while (*end &&
ISSPACE(*end)) end++;
4083 long result = -(long)val;
4097 digits_end = digits_start +
len;
4104 int digits_per_bdigits_dbl;
4106 num_bdigits =
roomof(num_digits, digits_per_bdigits_dbl)*2;
4110 z = str2big_gmp(sign, digits_start, digits_end, num_digits,
4121 num_bdigits, digits_per_bdigits_dbl, base);
4147 char *p =
ALLOCV(v, len+1);
4164 const char *
s, *
str;
4165 const char *digits_start, *digits_end;
4170 if (base < 2 || 36 < base || !
POW2_P(base)) {
4183 digits_end = digits_start +
len;
4197 const char *
s, *
str;
4198 const char *digits_start, *digits_end;
4203 int digits_per_bdigits_dbl;
4206 if (base < 2 || 36 < base) {
4219 digits_end = digits_start +
len;
4222 num_bdigits =
roomof(num_digits, digits_per_bdigits_dbl)*2;
4236 const char *
s, *
str;
4237 const char *digits_start, *digits_end;
4242 int digits_per_bdigits_dbl;
4245 if (base < 2 || 36 < base) {
4258 digits_end = digits_start +
len;
4261 num_bdigits =
roomof(num_digits, digits_per_bdigits_dbl)*2;
4264 num_bdigits, digits_per_bdigits_dbl, base);
4273 rb_str2big_gmp(
VALUE arg,
int base,
int badcheck)
4276 const char *
s, *
str;
4277 const char *digits_start, *digits_end;
4282 int digits_per_bdigits_dbl;
4285 if (base < 2 || 36 < base) {
4298 digits_end = digits_start +
len;
4301 num_bdigits =
roomof(num_digits, digits_per_bdigits_dbl)*2;
4303 z = str2big_gmp(positive_p, digits_start, digits_end, num_digits, num_bdigits, base);
4314 rb_ull2big(
unsigned LONG_LONG
n)
4320 #if SIZEOF_BDIGITS >= SIZEOF_LONG_LONG
4330 while (i-- && !digits[i]) ;
4336 rb_ll2big(LONG_LONG n)
4339 unsigned LONG_LONG u;
4343 u = 1 + (
unsigned LONG_LONG)(-(n + 1));
4349 big = rb_ull2big(u);
4357 rb_ull2inum(
unsigned LONG_LONG n)
4360 return rb_ull2big(n);
4364 rb_ll2inum(LONG_LONG n)
4367 return rb_ll2big(n);
4397 s1 = shift_numdigits;
4416 s1 = shift_numdigits;
4438 size_t shift_numdigits;
4449 lshift_p = !lshift_p;
4453 if (1 < sign ||
CHAR_BIT <= lens[1])
4457 if (1 < sign ||
CHAR_BIT <= lens[1])
4463 return big_shift3(x, lshift_p, shift_numdigits, shift_numbits);
4482 #define MAX_BASE36_POWER_TABLE_ENTRIES (SIZEOF_SIZE_T * CHAR_BIT + 1)
4491 for (i = 0; i < 35; ++
i) {
4493 base36_power_cache[
i][
j] =
Qnil;
4516 rb_bug(
"too big power number requested: maxpow_in_bdigit_dbl(%d)**(2**%d)", base, power_level);
4518 if (
NIL_P(base36_power_cache[base - 2][power_level])) {
4521 if (power_level == 0) {
4526 numdigits = numdigits0;
4533 base36_power_cache[base - 2][power_level] = power;
4534 base36_numdigits_cache[base - 2][power_level] = numdigits;
4538 *numdigits_ret = base36_numdigits_cache[base - 2][power_level];
4539 return base36_power_cache[base - 2][power_level];
4561 static const double log_2[] = {
4562 1.0, 1.58496250072116, 2.0,
4563 2.32192809488736, 2.58496250072116, 2.8073549220576,
4564 3.0, 3.16992500144231, 3.32192809488736,
4565 3.4594316186373, 3.58496250072116, 3.70043971814109,
4566 3.8073549220576, 3.90689059560852, 4.0,
4567 4.08746284125034, 4.16992500144231, 4.24792751344359,
4568 4.32192809488736, 4.39231742277876, 4.4594316186373,
4569 4.52356195605701, 4.58496250072116, 4.64385618977472,
4570 4.70043971814109, 4.75488750216347, 4.8073549220576,
4571 4.85798099512757, 4.90689059560852, 4.95419631038688,
4572 5.0, 5.04439411935845, 5.08746284125034,
4573 5.12928301694497, 5.16992500144231
4577 if (base < 2 || 36 < base)
4578 rb_bug(
"invalid radix %d", base);
4581 bits = (SIZEOF_LONG*
CHAR_BIT - 1)/2 + 1;
4594 return (
long)ceil(((
double)bits)/log_2[base - 2]);
4623 int beginning = !b2s->
ptr;
4638 len =
sizeof(
buf) - j;
4656 int power_level,
size_t taillen)
4659 size_t half_numdigits, lower_numdigits;
4660 int lower_power_level;
4695 if (power_level == 0) {
4700 lower_power_level = power_level-1;
4705 half_numdigits = lower_numdigits;
4707 while (0 < lower_power_level &&
4709 (xn == bn &&
bary_cmp(xds, xn, bds, bn) < 0))) {
4710 lower_power_level--;
4716 if (lower_power_level == 0 &&
4718 (xn == bn &&
bary_cmp(xds, xn, bds, bn) < 0))) {
4720 len = half_numdigits * 2 - lower_numdigits;
4732 if (lower_power_level != power_level-1 && b2s->
ptr) {
4733 len = (half_numdigits - lower_numdigits) * 2;
4738 shift =
nlz(bds[bn-1]);
4752 assert(qn + bn <= xn + wn);
4771 big2str_karatsuba(b2s, qds, qn, xn+wn - (rn+qn), lower_power_level, lower_numdigits+taillen);
4780 int word_numbits =
ffs(base) - 1;
4800 while (0 < numwords) {
4831 if (base < 2 || 36 < base)
4868 if (power_level == 0) {
4884 *b2s_data.
ptr =
'\0';
4899 big2str_gmp(
VALUE x,
int base)
4909 mpz_import(mx, xn, -1,
sizeof(
BDIGIT), 0, nails, xds);
4911 size = mpz_sizeinbase(mx, base);
4932 rb_big2str_gmp(
VALUE x,
int base)
4934 return big2str_gmp(x, base);
4957 if (base < 2 || 36 < base)
4971 return big2str_gmp(x, base);
5001 if (oldlen-1 < n2) {
5002 long off = n2 - (oldlen-1);
5038 if (argc == 0) base = 10;
5048 static unsigned long
5057 if (
BIGSIZE(x) >
sizeof(
long)) {
5061 #if SIZEOF_LONG <= SIZEOF_BDIGITS
5062 num = (
unsigned long)ds[0];
5067 num += (
unsigned long)ds[len];
5086 unsigned long num =
big2ulong(x,
"unsigned long");
5094 if (num == 1+(
unsigned long)(-(
LONG_MIN+1)))
5103 unsigned long num =
big2ulong(x,
"long");
5112 if (num == 1+(
unsigned long)(-(
LONG_MIN+1)))
5120 static unsigned LONG_LONG
5124 unsigned LONG_LONG num;
5129 if (
BIGSIZE(x) > SIZEOF_LONG_LONG)
5131 #if SIZEOF_LONG_LONG <= SIZEOF_BDIGITS
5132 num = (
unsigned LONG_LONG)ds[0];
5146 unsigned LONG_LONG num = big2ull(x,
"unsigned long long");
5152 if (num <= LLONG_MAX)
5153 return -(LONG_LONG)num;
5154 if (num == 1+(
unsigned LONG_LONG)(-(LLONG_MIN+1)))
5163 unsigned LONG_LONG num = big2ull(x,
"long long");
5166 if (num <= LLONG_MAX)
5170 if (num <= LLONG_MAX)
5171 return -(LONG_LONG)num;
5172 if (num == 1+(
unsigned LONG_LONG)(-(LLONG_MIN+1)))
5187 double u = (d < 0)?-d:d;
5240 int carry = (dl & ~(
BDIGMAX << bits)) != 0;
5308 if (yd > 0.0)
return INT2FIX(-1);
5313 #if SIZEOF_LONG * CHAR_BIT < DBL_MANT_DIG
5341 if (yf == 0.0 || rel !=
INT2FIX(0))
5360 #if SIZEOF_LONG * CHAR_BIT < DBL_MANT_DIG
5634 zn = xn < yn ? yn : xn;
5642 if (
bary_sub(zds, zn, xds, xn, yds, yn)) {
5669 #if SIZEOF_BDIGITS < SIZEOF_LONG
5676 #if SIZEOF_BDIGITS >= SIZEOF_LONG
5679 if (xn == 1 && num < 0) {
5685 zds[0] =
BIGLO(num);
5693 for (i=0; i < xn; i++) {
5694 if (y == 0)
goto y_is_zero_x;
5700 for (; i < zn; i++) {
5701 if (y == 0)
goto y_is_zero_z;
5710 for (; i < xn; i++) {
5712 if (num == 0)
goto num_is_zero_x;
5717 #if SIZEOF_BDIGITS < SIZEOF_LONG
5718 for (; i < zn; i++) {
5720 if (num == 0)
goto num_is_zero_z;
5727 for (; i < xn; i++) {
5731 #if SIZEOF_BDIGITS < SIZEOF_LONG
5732 for (; i < zn; i++) {
5740 assert(num == 0 || num == -1);
5765 #if SIZEOF_BDIGITS < SIZEOF_LONG
5774 #if SIZEOF_BDIGITS >= SIZEOF_LONG
5776 zds[0] =
BIGLO(num);
5784 for (i=0; i < xn; i++) {
5785 if (y == 0)
goto y_is_zero_x;
5791 for (; i < zn; i++) {
5792 if (y == 0)
goto y_is_zero_z;
5802 for (;i < xn; i++) {
5804 if (num == 0)
goto num_is_zero_x;
5809 for (; i < zn; i++) {
5811 if (num == 0)
goto num_is_zero_z;
5817 for (;i < xn; i++) {
5821 for (; i < zn; i++) {
5840 if (sign)
return bigsub(y, x);
5950 bary_mul(zds, zn, xds, xn, xds, xn);
5955 bary_mul(zds, zn, xds, xn, xds, xn);
5982 bary_mul(zds, zn, xds, xn, yds, yn);
6034 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1])) {
6036 if (modp) *modp = x;
6048 if (divp) *divp = z;
6051 if (xn == 2 && yn == 2) {
6115 if (modp) *modp =
bigadd(mod, y, 1);
6256 return big_lshift(x, 1+(
unsigned long)(-(n+1)));
6265 #define DBL_BIGDIG ((DBL_MANT_DIG + BITSPERDIG) / BITSPERDIG)
6277 #if SIZEOF_LONG > SIZEOF_INT
6281 if (l < INT_MIN)
return DBL2NUM(0.0);
6379 rb_warn(
"in a**b, b may be too big");
6391 const size_t BIGLEN_LIMIT = 32*1024*1024;
6393 if (xbits == (
size_t)-1 ||
6394 (xbits > BIGLEN_LIMIT) ||
6395 (xbits * yy > BIGLEN_LIMIT)) {
6396 rb_warn(
"in a**b, b may be too big");
6400 for (mask =
FIXNUM_MAX + 1; mask; mask >>= 1) {
6401 if (z) z =
bigsq(z);
6425 if (y == 0)
return INT2FIX(0);
6426 if (xn == 0)
return hibitsx ?
LONG2NUM(y) : 0;
6427 hibitsy = 0 <= y ? 0 :
BDIGMAX;
6429 #if SIZEOF_BDIGITS >= SIZEOF_LONG
6437 #if SIZEOF_BDIGITS < SIZEOF_LONG
6445 #if SIZEOF_BDIGITS >= SIZEOF_LONG
6447 zds[0] = xds[0] &
BIGLO(y);
6449 for (i=0; i < xn; i++) {
6450 if (y == 0 || y == -1)
break;
6454 for (; i < zn; i++) {
6455 if (y == 0 || y == -1)
break;
6456 zds[
i] = hibitsx &
BIGLO(y);
6460 for (;i < xn; i++) {
6461 zds[
i] = xds[
i] & hibitsy;
6463 for (;i < zn; i++) {
6464 zds[
i] = hibitsx & hibitsy;
6483 long i, xn, yn, n1, n2;
6500 tmpv = x; x = y; y = tmpv;
6501 tmpn = xn; xn = yn; yn = tmpn;
6502 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6517 for (i=0; i<n1; i++) {
6518 zds[
i] = ds1[
i] & ds2[
i];
6521 zds[
i] = hibits1 & ds2[
i];
6538 if (y == -1)
return INT2FIX(-1);
6540 hibitsy = 0 <= y ? 0 :
BDIGMAX;
6544 #if SIZEOF_BDIGITS < SIZEOF_LONG
6551 #if SIZEOF_BDIGITS >= SIZEOF_LONG
6553 zds[0] = xds[0] |
BIGLO(y);
6555 goto y_is_fixed_point;
6558 for (i=0; i < xn; i++) {
6559 if (y == 0 || y == -1)
goto y_is_fixed_point;
6565 for (; i < zn; i++) {
6566 if (y == 0 || y == -1)
goto y_is_fixed_point;
6576 for (; i < xn; i++) {
6581 for (; i < zn; i++) {
6587 for (; i < zn; i++) {
6609 long i, xn, yn, n1, n2;
6626 tmpv = x; x = y; y = tmpv;
6627 tmpn = xn; xn = yn; yn = tmpn;
6628 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6643 for (i=0; i<n1; i++) {
6644 zds[
i] = ds1[
i] | ds2[
i];
6647 zds[
i] = hibits1 | ds2[
i];
6664 hibitsy = 0 <= y ? 0 :
BDIGMAX;
6667 #if SIZEOF_BDIGITS < SIZEOF_LONG
6674 #if SIZEOF_BDIGITS >= SIZEOF_LONG
6676 zds[0] = xds[0] ^
BIGLO(y);
6678 for (i = 0; i < xn; i++) {
6682 for (; i < zn; i++) {
6683 zds[
i] = hibitsx ^
BIGLO(y);
6687 for (; i < xn; i++) {
6688 zds[
i] = xds[
i] ^ hibitsy;
6690 for (; i < zn; i++) {
6691 zds[
i] = hibitsx ^ hibitsy;
6709 long i, xn, yn, n1, n2;
6726 tmpv = x; x = y; y = tmpv;
6727 tmpn = xn; xn = yn; yn = tmpn;
6728 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6740 for (i=0; i<n1; i++) {
6741 zds[
i] = ds1[
i] ^ ds2[
i];
6744 zds[
i] = hibitsx ^ ds2[
i];
6763 size_t shift_numdigits;
6769 unsigned long shift;
6776 shift = 1+(
unsigned long)(-(l+1));
6801 size_t shift_numdigits;
6807 unsigned long shift;
6814 shift = 1+(
unsigned long)(-(l+1));
6850 unsigned long shift;
6858 if (
BIGSIZE(y) >
sizeof(
long)) {
6878 if (xds[s1] & (bit-1))
6880 for (i = 0; i < s1; i++)
7028 nlz_bary[0] = nlz_bits;
7033 BARY_SUB(result_bary, result_bary, nlz_bary);
static unsigned long big2ulong(VALUE x, const char *type)
VALUE rb_big_modulo(VALUE x, VALUE y)
int rb_bigzero_p(VALUE x)
static VALUE bignorm(VALUE x)
static VALUE rb_big2str1(VALUE x, int base)
VALUE rb_big_clone(VALUE x)
#define BARY_TRUNC(ds, n)
VALUE rb_str2big_poweroftwo(VALUE arg, int base, int badcheck)
int rb_integer_pack(VALUE val, void *words, size_t numwords, size_t wordsize, size_t nails, int flags)
#define RBIGNUM_POSITIVE_P(b)
static VALUE bigtrunc(VALUE x)
#define INTEGER_PACK_MSWORD_FIRST
void rb_bug(const char *fmt,...)
VALUE rb_uint2big(VALUE n)
#define RBIGNUM_EMBED_LEN_SHIFT
static size_t integer_unpack_num_bdigits_generic(size_t numwords, size_t wordsize, size_t nails, int *nlp_bits_ret)
static void twocomp2abs_bang(VALUE x, int hibits)
void( mulfunc_t)(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn, BDIGIT *wds, size_t wn)
static VALUE rb_big_even_p(VALUE num)
static VALUE big_shift(VALUE x, long n)
size_t strlen(const char *)
static VALUE rb_big_bit_length(VALUE big)
#define INTEGER_PACK_NEGATIVE
static mulfunc_t bary_mul_toom3_start
const char * rb_obj_classname(VALUE)
static void integer_pack_loop_setup(size_t numwords, size_t wordsize, size_t nails, int flags, size_t *word_num_fullbytes_ret, int *word_num_partialbits_ret, size_t *word_start_ret, ssize_t *word_step_ret, size_t *word_last_ret, size_t *byte_start_ret, int *byte_step_ret)
VALUE rb_big2ulong(VALUE x)
static VALUE big2str_base_poweroftwo(VALUE x, int base)
static void rb_big_realloc(VALUE big, long len)
static size_t absint_numwords_small(size_t numbytes, int nlz_bits_in_msbyte, size_t word_numbits, size_t *nlz_bits_ret)
static BDIGIT bigdivrem_single1(BDIGIT *qds, const BDIGIT *xds, size_t xn, BDIGIT x_higher_bdigit, BDIGIT y)
static int bary_addc(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn, int carry)
#define KARATSUBA_BALANCED(xn, yn)
static VALUE rb_big_size(VALUE big)
static void * bigdivrem1(void *ptr)
VALUE rb_num_coerce_relop(VALUE, VALUE, ID)
rb_funcall(memo->yielder, id_lshift, 1, rb_assoc_new(memo->prev_value, memo->prev_elts))
#define rb_usascii_str_new2
#define INTEGER_PACK_FORCE_BIGNUM
void rb_big_pack(VALUE val, unsigned long *buf, long num_longs)
static VALUE big_fdiv(VALUE x, VALUE y, long ey)
static void rb_big_stop(void *ptr)
static void bary_swap(BDIGIT *ds, size_t num_bdigits)
static VALUE dbl2big(double d)
const char ruby_digitmap[]
static BDIGIT bigdivrem_single(BDIGIT *qds, const BDIGIT *xds, size_t xn, BDIGIT y)
static VALUE big_lt(VALUE x, VALUE y)
static void bary_mul_karatsuba_branch(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn, BDIGIT *wds, size_t wn)
static VALUE str2big_normal(int sign, const char *digits_start, const char *digits_end, size_t num_bdigits, int base)
VALUE rb_big_eql(VALUE x, VALUE y)
VALUE rb_big_plus(VALUE x, VALUE y)
#define RBIGNUM_SET_LEN(b, l)
static void bary_divmod_branch(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn)
VALUE rb_big_mul_normal(VALUE x, VALUE y)
static VALUE bigand_int(VALUE x, long xn, BDIGIT hibitsx, long y)
static VALUE rb_big_abs(VALUE x)
#define bignew(len, sign)
static int bary_cmp(const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn)
static VALUE big_shift2(VALUE x, int lshift_p, VALUE y)
#define MAX_BASE36_POWER_TABLE_ENTRIES
VALUE rb_str2big_normal(VALUE arg, int base, int badcheck)
#define BARY_DIVMOD(q, r, x, y)
#define MEMMOVE(p1, p2, type, n)
static VALUE bigfixize(VALUE x)
VALUE rb_big_fdiv(VALUE x, VALUE y)
void rb_raise(VALUE exc, const char *fmt,...)
#define MEMCMP(p1, p2, type, n)
VALUE rb_integer_float_cmp(VALUE x, VALUE y)
static VALUE bigxor_int(VALUE x, long xn, BDIGIT hibitsx, long y)
static VALUE rb_big_neg(VALUE x)
static VALUE bigadd_int(VALUE x, long y)
static int bary_zero_p(BDIGIT *xds, size_t xn)
double rb_big2dbl(VALUE x)
static void power_cache_init(void)
void rb_must_asciicompat(VALUE)
static void bary_mul_balance_with_mulfunc(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn, BDIGIT *wds, size_t wn, mulfunc_t *mulfunc)
void rb_big_resize(VALUE big, long len)
static VALUE big_le(VALUE x, VALUE y)
VALUE rb_big_unpack(unsigned long *buf, long num_longs)
VALUE rb_big_new(long len, int sign)
static VALUE str2big_poweroftwo(int sign, const char *digits_start, const char *digits_end, size_t num_digits, int bits_per_digit)
#define STRTOUL(str, endptr, base)
RUBY_EXTERN double round(double)
static VALUE big_fdiv_int(VALUE x, VALUE y)
int rb_cmpint(VALUE val, VALUE a, VALUE b)
static int bary_add_one(BDIGIT *ds, size_t n)
static VALUE big_rshift(VALUE x, unsigned long shift)
VALUE rb_equal(VALUE, VALUE)
static void bary_mul_toom3_branch(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn, BDIGIT *wds, size_t wn)
static int bary_unpack_internal(BDIGIT *bdigits, size_t num_bdigits, const void *words, size_t numwords, size_t wordsize, size_t nails, int flags, int nlp_bits)
#define FILL_LOWBITS(d, numbits)
static VALUE rb_big_aref(VALUE x, VALUE y)
#define rb_complex_raw1(x)
#define MEMZERO(p, type, n)
int rb_absint_singlebit_p(VALUE val)
static void bary_divmod_normal(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn)
VALUE rb_usascii_str_new(const char *, long)
static VALUE rb_big_divide(VALUE x, VALUE y, ID op)
#define INTEGER_PACK_BIG_ENDIAN
static BDIGIT_DBL maxpow_in_bdigit_dbl(int base, int *exp_ret)
unsigned long rb_genrand_ulong_limited(unsigned long i)
VALUE rb_big2ulong_pack(VALUE x)
VALUE rb_big_divmod(VALUE x, VALUE y)
#define STATIC_ASSERT(name, expr)
#define RBIGNUM_EMBED_LEN_MASK
static int bary_subb(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn, int borrow)
memset(y->frac+ix+1, 0,(y->Prec-(ix+1))*sizeof(BDIGIT))
unsigned long long uint64_t
VALUE rb_big_mul_balance(VALUE x, VALUE y)
static size_t base36_numdigits_cache[35][MAX_BASE36_POWER_TABLE_ENTRIES]
VALUE rb_big_sq_fast(VALUE x)
VALUE rb_dbl2big(double d)
VALUE rb_big_eq(VALUE x, VALUE y)
#define RB_BIGNUM_TYPE_P(x)
static void bary_mul(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn)
static void big2str_alloc(struct big2str_struct *b2s, size_t len)
VALUE rb_str_to_inum(VALUE str, int base, int badcheck)
#define INTEGER_PACK_LSBYTE_FIRST
VALUE rb_big2str_generic(VALUE x, int base)
static int bary_add(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn)
static VALUE big_op(VALUE x, VALUE y, enum big_op_t op)
#define StringValueCStr(v)
VALUE rb_big_cmp(VALUE x, VALUE y)
#define RBIGNUM_SET_POSITIVE_SIGN(b)
void rb_define_const(VALUE, const char *, VALUE)
VALUE rb_define_class(const char *name, VALUE super)
Defines a top-level class.
#define SIZEOF_BDIGIT_DBL
#define BDIGIT_DBL_SIGNED
static void bary_unpack(BDIGIT *bdigits, size_t num_bdigits, const void *words, size_t numwords, size_t wordsize, size_t nails, int flags)
static void bary_mul_normal(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn)
static VALUE bigmul0(VALUE x, VALUE y)
static BDIGIT_DBL integer_pack_take_lowbits(int n, BDIGIT_DBL *ddp, int *numbits_in_dd_p)
unsigned char buf[MIME_BUF_SIZE]
VALUE rb_num_coerce_cmp(VALUE, VALUE, ID)
#define RBIGNUM_NEGATIVE_P(b)
SIGNED_VALUE rb_big2long(VALUE x)
void rb_num_zerodiv(void)
VALUE rb_big2str(VALUE x, int base)
static int bary_sparse_p(const BDIGIT *ds, size_t n)
void * rb_thread_call_without_gvl(void *(*func)(void *), void *data1, rb_unblock_function_t *ubf, void *data2)
static VALUE bigor_int(VALUE x, long xn, BDIGIT hibitsx, long y)
VALUE rb_integer_unpack(const void *words, size_t numwords, size_t wordsize, size_t nails, int flags)
static int nlz_long(unsigned long x)
static VALUE bigsub_int(VALUE x, long y0)
#define INTEGER_PACK_MSBYTE_FIRST
VALUE rb_obj_hide(VALUE obj)
RUBY_EXTERN VALUE rb_cInteger
static VALUE big2str_generic(VALUE x, int base)
void rb_define_alias(VALUE klass, const char *name1, const char *name2)
Defines an alias of a method.
VALUE rb_big_minus(VALUE x, VALUE y)
VALUE rb_str_resize(VALUE, long)
#define BDIGITS_ZERO(ptr, n)
#define GMP_BIG2STR_DIGITS
#define RBIGNUM_SET_SIGN(b, sign)
static VALUE rb_big_to_s(int argc, VALUE *argv, VALUE x)
static void integer_unpack_push_bits(int data, int numbits, BDIGIT_DBL *ddp, int *numbits_in_dd_p, BDIGIT **dpp)
static int bary_sub(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn)
#define rb_rational_raw1(x)
static VALUE big_shift3(VALUE x, int lshift_p, size_t shift_numdigits, int shift_numbits)
VALUE rb_sprintf(const char *format,...)
VALUE rb_big_div(VALUE x, VALUE y)
VALUE rb_big_idiv(VALUE x, VALUE y)
static size_t integer_unpack_num_bdigits(size_t numwords, size_t wordsize, size_t nails, int *nlp_bits_ret)
void rb_gc_register_mark_object(VALUE)
#define BARY_SUB(z, x, y)
static void bary_neg(BDIGIT *ds, size_t n)
VALUE rb_big2str_poweroftwo(VALUE x, int base)
int rb_scan_args(int argc, const VALUE *argv, const char *fmt,...)
static void integer_pack_fill_dd(BDIGIT **dpp, BDIGIT **dep, BDIGIT_DBL *ddp, int *numbits_in_dd_p)
#define TOOM3_BALANCED(xn, yn)
static void bdigitdbl2bary(BDIGIT *ds, size_t n, BDIGIT_DBL num)
#define INTEGER_PACK_FORCE_GENERIC_IMPLEMENTATION
VALUE rb_assoc_new(VALUE car, VALUE cdr)
#define INTEGER_PACK_WORDORDER_MASK
#define RBIGNUM_EMBED_LEN_MAX
static BDIGIT bary_small_lshift(BDIGIT *zds, const BDIGIT *xds, size_t n, int shift)
VALUE rb_quad_unpack(const char *buf, int signed_p)
VALUE rb_big_mul(VALUE x, VALUE y)
static VALUE rb_big_remainder(VALUE x, VALUE y)
#define BIGDIVREM_EXTRA_WORDS
static void big2str_karatsuba(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t wn, int power_level, size_t taillen)
#define INTEGER_PACK_2COMP
static BDIGIT_DBL_SIGNED bigdivrem_mulsub(BDIGIT *zds, size_t zn, BDIGIT x, const BDIGIT *yds, size_t yn)
static void bary_small_rshift(BDIGIT *zds, const BDIGIT *xds, size_t n, int shift, BDIGIT higher_bdigit)
static int bytes_2comp(unsigned char *buf, size_t len)
static size_t integer_unpack_num_bdigits_small(size_t numwords, size_t wordsize, size_t nails, int *nlp_bits_ret)
static VALUE rb_big_coerce(VALUE x, VALUE y)
VALUE rb_big_mul_karatsuba(VALUE x, VALUE y)
#define INTEGER_PACK_LSWORD_FIRST
static void bigdivrem_restoring(BDIGIT *zds, size_t zn, BDIGIT *yds, size_t yn)
size_t rb_absint_size(VALUE val, int *nlz_bits_ret)
RUBY_EXTERN int isinf(double)
static int nlz_int(unsigned int x)
static VALUE big_lshift(VALUE x, unsigned long shift)
static void big2str_2bdigits(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t taillen)
#define BARY_SHORT_MUL(z, x, y)
#define VALGRIND_MAKE_MEM_UNDEFINED(p, n)
static VALUE big_fdiv_float(VALUE x, VALUE y)
static VALUE rb_big_odd_p(VALUE num)
static void bary_mul_toom3(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn, BDIGIT *wds, size_t wn)
#define MEMCPY(p1, p2, type, n)
static int integer_unpack_single_bdigit(BDIGIT u, size_t size, int flags, BDIGIT *dp)
static VALUE bignew_1(VALUE klass, long len, int sign)
static VALUE rb_big_to_f(VALUE x)
static void bary_short_mul(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn)
#define RGENGC_WB_PROTECTED_BIGNUM
#define NEWOBJ_OF(obj, type, klass, flags)
VALUE rb_big_uminus(VALUE x)
VALUE rb_str2inum(VALUE str, int base)
static void bary_mul_single(BDIGIT *zds, size_t zn, BDIGIT x, BDIGIT y)
VALUE rb_big_and(VALUE x, VALUE y)
VALUE rb_num_coerce_bit(VALUE, VALUE, ID)
st_index_t rb_memhash(const void *ptr, long len)
static int bary_2comp(BDIGIT *ds, size_t n)
static int bary_mul_precheck(BDIGIT **zdsp, size_t *znp, const BDIGIT **xdsp, size_t *xnp, const BDIGIT **ydsp, size_t *ynp)
static VALUE base36_power_cache[35][MAX_BASE36_POWER_TABLE_ENTRIES]
static VALUE power_cache_get_power(int base, int power_level, size_t *numdigits_ret)
static void bary_sq_fast(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn)
static void get2comp(VALUE x)
static BDIGIT abs2twocomp(VALUE *xp, long *n_ret)
VALUE rb_big_divrem_normal(VALUE x, VALUE y)
VALUE rb_big_norm(VALUE x)
#define RBIGNUM_SET_NEGATIVE_SIGN(b)
VALUE rb_big_mul_toom3(VALUE x, VALUE y)
VALUE rb_big_lshift(VALUE x, VALUE y)
VALUE rb_big2str0(VALUE x, int base, int trim)
VALUE rb_uint2inum(VALUE n)
#define RB_FLOAT_TYPE_P(obj)
static VALUE rb_big_hash(VALUE x)
static void big_extend_carry(VALUE x)
static VALUE bigadd(VALUE x, VALUE y, int sign)
static long big2str_find_n1(VALUE x, int base)
static mulfunc_t bary_mul_karatsuba_start
VALUE rb_big_pow(VALUE x, VALUE y)
static void str2big_scan_digits(const char *s, const char *str, int base, int badcheck, size_t *num_digits_p, size_t *len_p)
size_t rb_absint_numwords(VALUE val, size_t word_numbits, size_t *nlz_bits_ret)
static void bary_divmod(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn)
VALUE rb_int2big(SIGNED_VALUE n)
VALUE rb_integer_float_eq(VALUE x, VALUE y)
static int bary_sub_one(BDIGIT *zds, size_t zn)
#define assert(condition)
static int bary_mulsub_1xN(BDIGIT *zds, size_t zn, BDIGIT x, const BDIGIT *yds, size_t yn)
static double big2dbl(VALUE x)
VALUE rb_int2inum(SIGNED_VALUE n)
static void bary_mul_karatsuba(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn, BDIGIT *wds, size_t wn)
VALUE rb_fix2str(VALUE, int)
void rb_warning(const char *fmt,...)
#define BARY_ADD(z, x, y)
void rb_big_2comp(VALUE x)
static BDIGIT_DBL bary2bdigitdbl(const BDIGIT *ds, size_t n)
VALUE rb_big_rshift(VALUE x, VALUE y)
static void validate_integer_pack_format(size_t numwords, size_t wordsize, size_t nails, int flags, int supported_flags)
#define GMP_STR2BIG_DIGITS
#define INTEGER_PACK_NATIVE_BYTE_ORDER
VALUE rb_cstr_to_inum(const char *str, int base, int badcheck)
static int bigzero_p(VALUE x)
static int bary_muladd_1xN(BDIGIT *zds, size_t zn, BDIGIT x, const BDIGIT *yds, size_t yn)
static VALUE str2big_karatsuba(int sign, const char *digits_start, const char *digits_end, size_t num_digits, size_t num_bdigits, int digits_per_bdigits_dbl, int base)
VALUE rb_num_coerce_bin(VALUE, VALUE, ID)
VALUE rb_str2big_karatsuba(VALUE arg, int base, int badcheck)
RUBY_EXTERN VALUE rb_eFloatDomainError
static VALUE bigsub(VALUE x, VALUE y)
static VALUE bigsq(VALUE x)
#define INTEGER_PACK_BYTEORDER_MASK
#define REALLOC_N(var, type, n)
void rb_define_method(VALUE klass, const char *name, VALUE(*func)(ANYARGS), int argc)
void rb_quad_pack(char *buf, VALUE val)
#define ALLOCV_N(type, v, n)
void rb_warn(const char *fmt,...)
#define RBIGNUM_EMBED_FLAG
void rb_invalid_str(const char *str, const char *type)
VALUE rb_big_or(VALUE x, VALUE y)
static VALUE big_ge(VALUE x, VALUE y)
VALUE rb_cstr2inum(const char *str, int base)
void rb_cmperr(VALUE x, VALUE y)
static VALUE bigdivrem(VALUE x, VALUE y, volatile VALUE *divp, volatile VALUE *modp)
static void bigdivmod(VALUE x, VALUE y, volatile VALUE *divp, volatile VALUE *modp)
static int bary_pack(int sign, BDIGIT *ds, size_t num_bdigits, void *words, size_t numwords, size_t wordsize, size_t nails, int flags)
#define CLEAR_LOWBITS(d, numbits)
VALUE rb_big_xor(VALUE x, VALUE y)
#define PUSH_BITS(data, numbits)
#define KARATSUBA_MUL_DIGITS
static VALUE big_gt(VALUE x, VALUE y)
static size_t absint_numwords_generic(size_t numbytes, int nlz_bits_in_msbyte, size_t word_numbits, size_t *nlz_bits_ret)
void rb_str_set_len(VALUE, long)