12 #include "ruby/internal/config.h"
27 #if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H)
36 #include "internal/bignum.h"
37 #include "internal/complex.h"
38 #include "internal/gc.h"
39 #include "internal/numeric.h"
40 #include "internal/object.h"
41 #include "internal/sanitizers.h"
42 #include "internal/variable.h"
43 #include "internal/warnings.h"
46 #include "ruby_assert.h"
57 static const bool debug_integer_pack = (
58 #ifdef DEBUG_INTEGER_PACK
65 const char ruby_digitmap[] =
"0123456789abcdefghijklmnopqrstuvwxyz";
67 #ifndef SIZEOF_BDIGIT_DBL
68 # if SIZEOF_INT*2 <= SIZEOF_LONG_LONG
69 # define SIZEOF_BDIGIT_DBL SIZEOF_LONG_LONG
71 # define SIZEOF_BDIGIT_DBL SIZEOF_LONG
75 STATIC_ASSERT(sizeof_bdigit_dbl,
sizeof(BDIGIT_DBL) == SIZEOF_BDIGIT_DBL);
76 STATIC_ASSERT(sizeof_bdigit_dbl_signed,
sizeof(BDIGIT_DBL_SIGNED) == SIZEOF_BDIGIT_DBL);
77 STATIC_ASSERT(sizeof_bdigit, SIZEOF_BDIGIT <=
sizeof(BDIGIT));
78 STATIC_ASSERT(sizeof_bdigit_and_dbl, SIZEOF_BDIGIT*2 <= SIZEOF_BDIGIT_DBL);
79 STATIC_ASSERT(bdigit_signedness, 0 < (BDIGIT)-1);
80 STATIC_ASSERT(bdigit_dbl_signedness, 0 < (BDIGIT_DBL)-1);
81 STATIC_ASSERT(bdigit_dbl_signed_signedness, 0 > (BDIGIT_DBL_SIGNED)-1);
82 STATIC_ASSERT(rbignum_embed_len_max, BIGNUM_EMBED_LEN_MAX <= (BIGNUM_EMBED_LEN_MASK >> BIGNUM_EMBED_LEN_SHIFT));
84 #if SIZEOF_BDIGIT < SIZEOF_LONG
85 STATIC_ASSERT(sizeof_long_and_sizeof_bdigit, SIZEOF_LONG % SIZEOF_BDIGIT == 0);
87 STATIC_ASSERT(sizeof_long_and_sizeof_bdigit, SIZEOF_BDIGIT % SIZEOF_LONG == 0);
90 #ifdef WORDS_BIGENDIAN
91 # define HOST_BIGENDIAN_P 1
93 # define HOST_BIGENDIAN_P 0
96 #define LSHIFTABLE(d, n) ((n) < sizeof(d) * CHAR_BIT)
97 #define LSHIFTX(d, n) (!LSHIFTABLE(d, n) ? 0 : ((d) << (!LSHIFTABLE(d, n) ? 0 : (n))))
98 #define CLEAR_LOWBITS(d, numbits) ((d) & LSHIFTX(~((d)*0), (numbits)))
99 #define FILL_LOWBITS(d, numbits) ((d) | (LSHIFTX(((d)*0+1), (numbits))-1))
100 #define POW2_P(x) (((x)&((x)-1))==0)
102 #define BDIGITS(x) (BIGNUM_DIGITS(x))
103 #define BITSPERDIG (SIZEOF_BDIGIT*CHAR_BIT)
104 #define BIGRAD ((BDIGIT_DBL)1 << BITSPERDIG)
105 #define BIGRAD_HALF ((BDIGIT)(BIGRAD >> 1))
106 #define BDIGIT_MSB(d) (((d) & BIGRAD_HALF) != 0)
107 #define BIGUP(x) LSHIFTX(((x) + (BDIGIT_DBL)0), BITSPERDIG)
108 #define BIGDN(x) RSHIFT((x),BITSPERDIG)
109 #define BIGLO(x) ((BDIGIT)((x) & BDIGMAX))
110 #define BDIGMAX ((BDIGIT)(BIGRAD-1))
111 #define BDIGIT_DBL_MAX (~(BDIGIT_DBL)0)
113 #if SIZEOF_BDIGIT == 2
114 # define swap_bdigit(x) swap16(x)
115 #elif SIZEOF_BDIGIT == 4
116 # define swap_bdigit(x) swap32(x)
117 #elif SIZEOF_BDIGIT == 8
118 # define swap_bdigit(x) swap64(x)
121 #define BIGZEROP(x) (BIGNUM_LEN(x) == 0 || \
122 (BDIGITS(x)[0] == 0 && \
123 (BIGNUM_LEN(x) == 1 || bigzero_p(x))))
124 #define BIGSIZE(x) (BIGNUM_LEN(x) == 0 ? (size_t)0 : \
125 BDIGITS(x)[BIGNUM_LEN(x)-1] ? \
126 (size_t)(BIGNUM_LEN(x)*SIZEOF_BDIGIT - nlz(BDIGITS(x)[BIGNUM_LEN(x)-1])/CHAR_BIT) : \
127 rb_absint_size(x, NULL))
129 #define BIGDIVREM_EXTRA_WORDS 1
130 #define bdigit_roomof(n) roomof(n, SIZEOF_BDIGIT)
131 #define BARY_ARGS(ary) ary, numberof(ary)
133 #define BARY_ADD(z, x, y) bary_add(BARY_ARGS(z), BARY_ARGS(x), BARY_ARGS(y))
134 #define BARY_SUB(z, x, y) bary_sub(BARY_ARGS(z), BARY_ARGS(x), BARY_ARGS(y))
135 #define BARY_SHORT_MUL(z, x, y) bary_short_mul(BARY_ARGS(z), BARY_ARGS(x), BARY_ARGS(y))
136 #define BARY_DIVMOD(q, r, x, y) bary_divmod(BARY_ARGS(q), BARY_ARGS(r), BARY_ARGS(x), BARY_ARGS(y))
137 #define BARY_ZERO_P(x) bary_zero_p(BARY_ARGS(x))
139 #define BIGNUM_SET_NEGATIVE_SIGN(b) BIGNUM_SET_SIGN(b, 0)
140 #define BIGNUM_SET_POSITIVE_SIGN(b) BIGNUM_SET_SIGN(b, 1)
142 #define bignew(len,sign) bignew_1(rb_cInteger,(len),(sign))
144 #define BDIGITS_ZERO(ptr, n) do { \
145 BDIGIT *bdigitz_zero_ptr = (ptr); \
146 size_t bdigitz_zero_n = (n); \
147 while (bdigitz_zero_n) { \
148 *bdigitz_zero_ptr++ = 0; \
153 #define BARY_TRUNC(ds, n) do { \
154 while (0 < (n) && (ds)[(n)-1] == 0) \
158 #define KARATSUBA_BALANCED(xn, yn) ((yn)/2 < (xn))
159 #define TOOM3_BALANCED(xn, yn) (((yn)+2)/3 * 2 < (xn))
161 #define GMP_MUL_DIGITS 20
162 #define KARATSUBA_MUL_DIGITS 70
163 #define TOOM3_MUL_DIGITS 150
165 #define GMP_DIV_DIGITS 20
166 #define GMP_BIG2STR_DIGITS 20
167 #define GMP_STR2BIG_DIGITS 20
169 # define NAIVE_MUL_DIGITS GMP_MUL_DIGITS
171 # define NAIVE_MUL_DIGITS KARATSUBA_MUL_DIGITS
174 typedef 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);
176 static mulfunc_t bary_mul_toom3_start;
177 static mulfunc_t bary_mul_karatsuba_start;
178 static BDIGIT bigdivrem_single(BDIGIT *qds,
const BDIGIT *xds,
size_t xn, BDIGIT y);
184 static inline VALUE power_cache_get_power(
int base,
int power_level,
size_t *numdigits_ret);
186 #if SIZEOF_BDIGIT <= SIZEOF_INT
187 static int nlz(BDIGIT x) {
return nlz_int((
unsigned int)x) - (SIZEOF_INT-SIZEOF_BDIGIT) * CHAR_BIT; }
188 #elif SIZEOF_BDIGIT <= SIZEOF_LONG
189 static int nlz(BDIGIT x) {
return nlz_long((
unsigned long)x) - (SIZEOF_LONG-SIZEOF_BDIGIT) * CHAR_BIT; }
190 #elif SIZEOF_BDIGIT <= SIZEOF_LONG_LONG
191 static int nlz(BDIGIT x) {
return nlz_long_long((
unsigned LONG_LONG)x) - (SIZEOF_LONG_LONG-SIZEOF_BDIGIT) * CHAR_BIT; }
192 #elif SIZEOF_BDIGIT <= SIZEOF_INT128_T
193 static int nlz(BDIGIT x) {
return nlz_int128((uint128_t)x) - (SIZEOF_INT128_T-SIZEOF_BDIGIT) * CHAR_BIT; }
196 #define U16(a) ((uint16_t)(a))
197 #define U32(a) ((uint32_t)(a))
199 #define U64(a,b) (((uint64_t)(a) << 32) | (b))
201 #ifdef HAVE_UINT128_T
202 #define U128(a,b,c,d) (((uint128_t)U64(a,b) << 64) | U64(c,d))
249 #if SIZEOF_BDIGIT_DBL == 2
250 static const int maxpow16_exp[35] = {
251 15, 10, 7, 6, 6, 5, 5, 5, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3,
252 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
254 static const uint16_t maxpow16_num[35] = {
255 U16(0x00008000), U16(0x0000e6a9), U16(0x00004000), U16(0x00003d09),
256 U16(0x0000b640), U16(0x000041a7), U16(0x00008000), U16(0x0000e6a9),
257 U16(0x00002710), U16(0x00003931), U16(0x00005100), U16(0x00006f91),
258 U16(0x00009610), U16(0x0000c5c1), U16(0x00001000), U16(0x00001331),
259 U16(0x000016c8), U16(0x00001acb), U16(0x00001f40), U16(0x0000242d),
260 U16(0x00002998), U16(0x00002f87), U16(0x00003600), U16(0x00003d09),
261 U16(0x000044a8), U16(0x00004ce3), U16(0x000055c0), U16(0x00005f45),
262 U16(0x00006978), U16(0x0000745f), U16(0x00008000), U16(0x00008c61),
263 U16(0x00009988), U16(0x0000a77b), U16(0x0000b640),
265 #elif SIZEOF_BDIGIT_DBL == 4
266 static const int maxpow32_exp[35] = {
267 31, 20, 15, 13, 12, 11, 10, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7,
268 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
270 static const uint32_t maxpow32_num[35] = {
271 U32(0x80000000), U32(0xcfd41b91), U32(0x40000000), U32(0x48c27395),
272 U32(0x81bf1000), U32(0x75db9c97), U32(0x40000000), U32(0xcfd41b91),
273 U32(0x3b9aca00), U32(0x8c8b6d2b), U32(0x19a10000), U32(0x309f1021),
274 U32(0x57f6c100), U32(0x98c29b81), U32(0x10000000), U32(0x18754571),
275 U32(0x247dbc80), U32(0x3547667b), U32(0x4c4b4000), U32(0x6b5a6e1d),
276 U32(0x94ace180), U32(0xcaf18367), U32(0x0b640000), U32(0x0e8d4a51),
277 U32(0x1269ae40), U32(0x17179149), U32(0x1cb91000), U32(0x23744899),
278 U32(0x2b73a840), U32(0x34e63b41), U32(0x40000000), U32(0x4cfa3cc1),
279 U32(0x5c13d840), U32(0x6d91b519), U32(0x81bf1000),
281 #elif SIZEOF_BDIGIT_DBL == 8 && defined HAVE_UINT64_T
282 static const int maxpow64_exp[35] = {
283 63, 40, 31, 27, 24, 22, 21, 20, 19, 18, 17, 17, 16, 16, 15, 15, 15,
284 15, 14, 14, 14, 14, 13, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12,
287 static const uint64_t maxpow64_num[35] = {
288 U64(0x80000000,0x00000000), U64(0xa8b8b452,0x291fe821),
289 U64(0x40000000,0x00000000), U64(0x6765c793,0xfa10079d),
290 U64(0x41c21cb8,0xe1000000), U64(0x36427987,0x50226111),
291 U64(0x80000000,0x00000000), U64(0xa8b8b452,0x291fe821),
292 U64(0x8ac72304,0x89e80000), U64(0x4d28cb56,0xc33fa539),
293 U64(0x1eca170c,0x00000000), U64(0x780c7372,0x621bd74d),
294 U64(0x1e39a505,0x7d810000), U64(0x5b27ac99,0x3df97701),
295 U64(0x10000000,0x00000000), U64(0x27b95e99,0x7e21d9f1),
296 U64(0x5da0e1e5,0x3c5c8000), U64(0xd2ae3299,0xc1c4aedb),
297 U64(0x16bcc41e,0x90000000), U64(0x2d04b7fd,0xd9c0ef49),
298 U64(0x5658597b,0xcaa24000), U64(0xa0e20737,0x37609371),
299 U64(0x0c29e980,0x00000000), U64(0x14adf4b7,0x320334b9),
300 U64(0x226ed364,0x78bfa000), U64(0x383d9170,0xb85ff80b),
301 U64(0x5a3c23e3,0x9c000000), U64(0x8e651373,0x88122bcd),
302 U64(0xdd41bb36,0xd259e000), U64(0x0aee5720,0xee830681),
303 U64(0x10000000,0x00000000), U64(0x172588ad,0x4f5f0981),
304 U64(0x211e44f7,0xd02c1000), U64(0x2ee56725,0xf06e5c71),
305 U64(0x41c21cb8,0xe1000000),
307 #elif SIZEOF_BDIGIT_DBL == 16 && defined HAVE_UINT128_T
308 static const int maxpow128_exp[35] = {
309 127, 80, 63, 55, 49, 45, 42, 40, 38, 37, 35, 34, 33, 32, 31, 31, 30,
310 30, 29, 29, 28, 28, 27, 27, 27, 26, 26, 26, 26, 25, 25, 25, 25, 24,
313 static const uint128_t maxpow128_num[35] = {
314 U128(0x80000000,0x00000000,0x00000000,0x00000000),
315 U128(0x6f32f1ef,0x8b18a2bc,0x3cea5978,0x9c79d441),
316 U128(0x40000000,0x00000000,0x00000000,0x00000000),
317 U128(0xd0cf4b50,0xcfe20765,0xfff4b4e3,0xf741cf6d),
318 U128(0x6558e2a0,0x921fe069,0x42860000,0x00000000),
319 U128(0x5080c7b7,0xd0e31ba7,0x5911a67d,0xdd3d35e7),
320 U128(0x40000000,0x00000000,0x00000000,0x00000000),
321 U128(0x6f32f1ef,0x8b18a2bc,0x3cea5978,0x9c79d441),
322 U128(0x4b3b4ca8,0x5a86c47a,0x098a2240,0x00000000),
323 U128(0xffd1390a,0x0adc2fb8,0xdabbb817,0x4d95c99b),
324 U128(0x2c6fdb36,0x4c25e6c0,0x00000000,0x00000000),
325 U128(0x384bacd6,0x42c343b4,0xe90c4272,0x13506d29),
326 U128(0x31f5db32,0xa34aced6,0x0bf13a0e,0x00000000),
327 U128(0x20753ada,0xfd1e839f,0x53686d01,0x3143ee01),
328 U128(0x10000000,0x00000000,0x00000000,0x00000000),
329 U128(0x68ca11d6,0xb4f6d1d1,0xfaa82667,0x8073c2f1),
330 U128(0x223e493b,0xb3bb69ff,0xa4b87d6c,0x40000000),
331 U128(0xad62418d,0x14ea8247,0x01c4b488,0x6cc66f59),
332 U128(0x2863c1f5,0xcdae42f9,0x54000000,0x00000000),
333 U128(0xa63fd833,0xb9386b07,0x36039e82,0xbe651b25),
334 U128(0x1d1f7a9c,0xd087a14d,0x28cdf3d5,0x10000000),
335 U128(0x651b5095,0xc2ea8fc1,0xb30e2c57,0x77aaf7e1),
336 U128(0x0ddef20e,0xff760000,0x00000000,0x00000000),
337 U128(0x29c30f10,0x29939b14,0x6664242d,0x97d9f649),
338 U128(0x786a435a,0xe9558b0e,0x6aaf6d63,0xa8000000),
339 U128(0x0c5afe6f,0xf302bcbf,0x94fd9829,0xd87f5079),
340 U128(0x1fce575c,0xe1692706,0x07100000,0x00000000),
341 U128(0x4f34497c,0x8597e144,0x36e91802,0x00528229),
342 U128(0xbf3a8e1d,0x41ef2170,0x7802130d,0x84000000),
343 U128(0x0e7819e1,0x7f1eb0fb,0x6ee4fb89,0x01d9531f),
344 U128(0x20000000,0x00000000,0x00000000,0x00000000),
345 U128(0x4510460d,0xd9e879c0,0x14a82375,0x2f22b321),
346 U128(0x91abce3c,0x4b4117ad,0xe76d35db,0x22000000),
347 U128(0x08973ea3,0x55d75bc2,0x2e42c391,0x727d69e1),
348 U128(0x10e425c5,0x6daffabc,0x35c10000,0x00000000),
353 maxpow_in_bdigit_dbl(
int base,
int *exp_ret)
361 #if SIZEOF_BDIGIT_DBL == 2
362 maxpow = maxpow16_num[base-2];
363 exponent = maxpow16_exp[base-2];
364 #elif SIZEOF_BDIGIT_DBL == 4
365 maxpow = maxpow32_num[base-2];
366 exponent = maxpow32_exp[base-2];
367 #elif SIZEOF_BDIGIT_DBL == 8 && defined HAVE_UINT64_T
368 maxpow = maxpow64_num[base-2];
369 exponent = maxpow64_exp[base-2];
370 #elif SIZEOF_BDIGIT_DBL == 16 && defined HAVE_UINT128_T
371 maxpow = maxpow128_num[base-2];
372 exponent = maxpow128_exp[base-2];
376 while (maxpow <= BDIGIT_DBL_MAX / base) {
387 static inline BDIGIT_DBL
388 bary2bdigitdbl(
const BDIGIT *ds,
size_t n)
393 return ds[0] | BIGUP(ds[1]);
400 bdigitdbl2bary(BDIGIT *ds,
size_t n, BDIGIT_DBL num)
405 ds[1] = (BDIGIT)BIGDN(num);
409 bary_cmp(
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
420 for (i = 0; i < xn; i++)
421 if (xds[xn - i - 1] != yds[yn - i - 1])
425 return xds[xn - i - 1] < yds[yn - i - 1] ? -1 : 1;
429 bary_small_lshift(BDIGIT *zds,
const BDIGIT *xds,
size_t n,
int shift)
435 for (i=0; i<n; i++) {
436 num = num | (BDIGIT_DBL)*xds++ << shift;
444 bary_small_rshift(BDIGIT *zds,
const BDIGIT *xds,
size_t n,
int shift, BDIGIT higher_bdigit)
451 num = BIGUP(higher_bdigit);
452 for (i = 0; i < n; i++) {
453 BDIGIT x = xds[n - i - 1];
454 num = (num | x) >> shift;
455 zds[n - i - 1] = BIGLO(num);
461 bary_zero_p(
const BDIGIT *xds,
size_t xn)
466 if (xds[--xn])
return 0;
472 bary_neg(BDIGIT *ds,
size_t n)
475 for (i = 0; i < n; i++)
476 ds[n - i - 1] = BIGLO(~ds[n - i - 1]);
480 bary_2comp(BDIGIT *ds,
size_t n)
483 for (i = 0; i < n; i++) {
491 ds[i] = BIGLO(~ds[i] + 1);
494 ds[i] = BIGLO(~ds[i]);
500 bary_swap(BDIGIT *ds,
size_t num_bdigits)
503 BDIGIT *p2 = ds + num_bdigits - 1;
504 for (; p1 < p2; p1++, p2--) {
511 #define INTEGER_PACK_WORDORDER_MASK \
512 (INTEGER_PACK_MSWORD_FIRST | \
513 INTEGER_PACK_LSWORD_FIRST)
514 #define INTEGER_PACK_BYTEORDER_MASK \
515 (INTEGER_PACK_MSBYTE_FIRST | \
516 INTEGER_PACK_LSBYTE_FIRST | \
517 INTEGER_PACK_NATIVE_BYTE_ORDER)
520 validate_integer_pack_format(
size_t numwords,
size_t wordsize,
size_t nails,
int flags,
int supported_flags)
522 int wordorder_bits = flags & INTEGER_PACK_WORDORDER_MASK;
523 int byteorder_bits = flags & INTEGER_PACK_BYTEORDER_MASK;
525 if (flags & ~supported_flags) {
528 if (wordorder_bits == 0) {
535 if (byteorder_bits == 0) {
544 if (SSIZE_MAX < wordsize)
546 if (wordsize <= nails / CHAR_BIT)
548 if (SIZE_MAX / wordsize < numwords)
549 rb_raise(
rb_eArgError,
"too big numwords * wordsize: %"PRI_SIZE_PREFIX
"u * %"PRI_SIZE_PREFIX
"u", numwords, wordsize);
553 integer_pack_loop_setup(
554 size_t numwords,
size_t wordsize,
size_t nails,
int flags,
555 size_t *word_num_fullbytes_ret,
556 int *word_num_partialbits_ret,
557 size_t *word_start_ret,
558 ssize_t *word_step_ret,
559 size_t *word_last_ret,
560 size_t *byte_start_ret,
563 int wordorder_bits = flags & INTEGER_PACK_WORDORDER_MASK;
564 int byteorder_bits = flags & INTEGER_PACK_BYTEORDER_MASK;
565 size_t word_num_fullbytes;
566 int word_num_partialbits;
573 word_num_partialbits = CHAR_BIT - (int)(nails % CHAR_BIT);
574 if (word_num_partialbits == CHAR_BIT)
575 word_num_partialbits = 0;
576 word_num_fullbytes = wordsize - (nails / CHAR_BIT);
577 if (word_num_partialbits != 0) {
578 word_num_fullbytes--;
582 word_start = wordsize*(numwords-1);
583 word_step = -(ssize_t)wordsize;
588 word_step = wordsize;
589 word_last = wordsize*(numwords-1);
593 #ifdef WORDS_BIGENDIAN
600 byte_start = wordsize-1;
608 *word_num_partialbits_ret = word_num_partialbits;
609 *word_num_fullbytes_ret = word_num_fullbytes;
610 *word_start_ret = word_start;
611 *word_step_ret = word_step;
612 *word_last_ret = word_last;
613 *byte_start_ret = byte_start;
614 *byte_step_ret = byte_step;
618 integer_pack_fill_dd(BDIGIT **dpp, BDIGIT **dep, BDIGIT_DBL *ddp,
int *numbits_in_dd_p)
620 if (*dpp < *dep && BITSPERDIG <= (
int)
sizeof(*ddp) * CHAR_BIT - *numbits_in_dd_p) {
621 *ddp |= (BDIGIT_DBL)(*(*dpp)++) << *numbits_in_dd_p;
622 *numbits_in_dd_p += BITSPERDIG;
624 else if (*dpp == *dep) {
626 *numbits_in_dd_p = (int)
sizeof(*ddp) * CHAR_BIT;
630 static inline BDIGIT_DBL
631 integer_pack_take_lowbits(
int n, BDIGIT_DBL *ddp,
int *numbits_in_dd_p)
634 ret = (*ddp) & (((BDIGIT_DBL)1 << n) - 1);
636 *numbits_in_dd_p -= n;
640 #if !defined(WORDS_BIGENDIAN)
642 bytes_2comp(
unsigned char *buf,
size_t len)
645 for (i = 0; i <
len; i++) {
646 signed char c = buf[i];
648 unsigned int e = d & 0xFF;
651 for (i = 0; i <
len; i++) {
661 bary_pack(
int sign, BDIGIT *ds,
size_t num_bdigits,
void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
664 unsigned char *buf, *bufend;
667 de = ds + num_bdigits;
669 validate_integer_pack_format(numwords, wordsize, nails, flags,
678 while (dp < de && de[-1] == 0)
686 MEMZERO(words,
unsigned char, numwords * wordsize);
689 if (nails == 0 && numwords == 1) {
690 int need_swap = wordsize != 1 &&
696 *((
unsigned char *)words) = (
unsigned char)(d = dp[0]);
697 return ((1 < de - dp || CLEAR_LOWBITS(d, 8) != 0) ? 2 : 1) * sign;
699 #if defined(HAVE_UINT16_T) && 2 <= SIZEOF_BDIGIT
700 if (wordsize == 2 && (uintptr_t)words %
RUBY_ALIGNOF(uint16_t) == 0) {
701 uint16_t u = (uint16_t)(d = dp[0]);
702 if (need_swap) u = swap16(u);
703 *((uint16_t *)words) = u;
704 return ((1 < de - dp || CLEAR_LOWBITS(d, 16) != 0) ? 2 : 1) * sign;
707 #if defined(HAVE_UINT32_T) && 4 <= SIZEOF_BDIGIT
708 if (wordsize == 4 && (uintptr_t)words %
RUBY_ALIGNOF(uint32_t) == 0) {
709 uint32_t u = (uint32_t)(d = dp[0]);
710 if (need_swap) u = swap32(u);
711 *((uint32_t *)words) = u;
712 return ((1 < de - dp || CLEAR_LOWBITS(d, 32) != 0) ? 2 : 1) * sign;
715 #if defined(HAVE_UINT64_T) && 8 <= SIZEOF_BDIGIT
716 if (wordsize == 8 && (uintptr_t)words %
RUBY_ALIGNOF(uint64_t) == 0) {
717 uint64_t u = (uint64_t)(d = dp[0]);
718 if (need_swap) u = swap64(u);
719 *((uint64_t *)words) = u;
720 return ((1 < de - dp || CLEAR_LOWBITS(d, 64) != 0) ? 2 : 1) * sign;
727 *((
unsigned char *)words) = (
unsigned char)(d = -(BDIGIT_DBL_SIGNED)dp[0]);
728 return (1 < de - dp || FILL_LOWBITS(d, 8) != -1) ? -2 : -1;
730 #if defined(HAVE_UINT16_T) && 2 <= SIZEOF_BDIGIT
731 if (wordsize == 2 && (uintptr_t)words %
RUBY_ALIGNOF(uint16_t) == 0) {
732 uint16_t u = (uint16_t)(d = -(BDIGIT_DBL_SIGNED)dp[0]);
733 if (need_swap) u = swap16(u);
734 *((uint16_t *)words) = u;
735 return (wordsize == SIZEOF_BDIGIT && de - dp == 2 && dp[1] == 1 && dp[0] == 0) ? -1 :
736 (1 < de - dp || FILL_LOWBITS(d, 16) != -1) ? -2 : -1;
739 #if defined(HAVE_UINT32_T) && 4 <= SIZEOF_BDIGIT
740 if (wordsize == 4 && (uintptr_t)words %
RUBY_ALIGNOF(uint32_t) == 0) {
741 uint32_t u = (uint32_t)(d = -(BDIGIT_DBL_SIGNED)dp[0]);
742 if (need_swap) u = swap32(u);
743 *((uint32_t *)words) = u;
744 return (wordsize == SIZEOF_BDIGIT && de - dp == 2 && dp[1] == 1 && dp[0] == 0) ? -1 :
745 (1 < de - dp || FILL_LOWBITS(d, 32) != -1) ? -2 : -1;
748 #if defined(HAVE_UINT64_T) && 8 <= SIZEOF_BDIGIT
749 if (wordsize == 8 && (uintptr_t)words %
RUBY_ALIGNOF(uint64_t) == 0) {
750 uint64_t u = (uint64_t)(d = -(BDIGIT_DBL_SIGNED)dp[0]);
751 if (need_swap) u = swap64(u);
752 *((uint64_t *)words) = u;
753 return (wordsize == SIZEOF_BDIGIT && de - dp == 2 && dp[1] == 1 && dp[0] == 0) ? -1 :
754 (1 < de - dp || FILL_LOWBITS(d, 64) != -1) ? -2 : -1;
759 #if !defined(WORDS_BIGENDIAN)
760 if (nails == 0 && SIZEOF_BDIGIT ==
sizeof(BDIGIT) &&
763 size_t src_size = (de - dp) * SIZEOF_BDIGIT;
764 size_t dst_size = numwords * wordsize;
766 while (0 < src_size && ((
unsigned char *)ds)[src_size-1] == 0)
768 if (src_size <= dst_size) {
769 MEMCPY(words, dp,
char, src_size);
770 MEMZERO((
char*)words + src_size,
char, dst_size - src_size);
773 MEMCPY(words, dp,
char, dst_size);
777 int zero_p = bytes_2comp(words, dst_size);
778 if (zero_p && overflow) {
779 unsigned char *p = (
unsigned char *)dp;
780 if (dst_size == src_size-1 &&
791 if (nails == 0 && SIZEOF_BDIGIT ==
sizeof(BDIGIT) &&
792 wordsize % SIZEOF_BDIGIT == 0 && (uintptr_t)words %
RUBY_ALIGNOF(BDIGIT) == 0) {
793 size_t bdigits_per_word = wordsize / SIZEOF_BDIGIT;
794 size_t src_num_bdigits = de - dp;
795 size_t dst_num_bdigits = numwords * bdigits_per_word;
800 if (src_num_bdigits <= dst_num_bdigits) {
801 MEMCPY(words, dp, BDIGIT, src_num_bdigits);
802 BDIGITS_ZERO((BDIGIT*)words + src_num_bdigits, dst_num_bdigits - src_num_bdigits);
805 MEMCPY(words, dp, BDIGIT, dst_num_bdigits);
809 int zero_p = bary_2comp(words, dst_num_bdigits);
810 if (zero_p && overflow &&
811 dst_num_bdigits == src_num_bdigits-1 &&
812 dp[dst_num_bdigits] == 1)
815 if (msbytefirst_p != HOST_BIGENDIAN_P) {
817 for (i = 0; i < dst_num_bdigits; i++) {
818 BDIGIT d = ((BDIGIT*)words)[i];
819 ((BDIGIT*)words)[i] = swap_bdigit(d);
822 if (mswordfirst_p ? !msbytefirst_p : msbytefirst_p) {
825 for (i = 0; i < numwords; i++) {
826 bary_swap(p, bdigits_per_word);
827 p += bdigits_per_word;
831 bary_swap(words, dst_num_bdigits);
840 bufend = buf + numwords * wordsize;
847 if (de - dp == 1 && dp[0] == 1)
854 memset(buf,
'\0', bufend - buf);
856 else if (dp < de && buf < bufend) {
857 int word_num_partialbits;
858 size_t word_num_fullbytes;
864 size_t word_start, word_last;
865 unsigned char *wordp, *last_wordp;
869 integer_pack_loop_setup(numwords, wordsize, nails, flags,
870 &word_num_fullbytes, &word_num_partialbits,
871 &word_start, &word_step, &word_last, &byte_start, &byte_step);
873 wordp = buf + word_start;
874 last_wordp = buf + word_last;
880 integer_pack_fill_dd(&dp, &de, &dd, &numbits_in_dd)
881 #define TAKE_LOWBITS(n) \
882 integer_pack_take_lowbits(n, &dd, &numbits_in_dd)
885 size_t index_in_word = 0;
886 unsigned char *bytep = wordp + byte_start;
887 while (index_in_word < word_num_fullbytes) {
889 *bytep = TAKE_LOWBITS(CHAR_BIT);
893 if (word_num_partialbits) {
895 *bytep = TAKE_LOWBITS(word_num_partialbits);
899 while (index_in_word < wordsize) {
905 if (wordp == last_wordp)
912 if (dp != de || 1 < dd) {
923 while (dp < de && *dp == 0)
935 int word_num_partialbits;
936 size_t word_num_fullbytes;
942 size_t word_start, word_last;
943 unsigned char *wordp, *last_wordp;
945 unsigned int partialbits_mask;
948 integer_pack_loop_setup(numwords, wordsize, nails, flags,
949 &word_num_fullbytes, &word_num_partialbits,
950 &word_start, &word_step, &word_last, &byte_start, &byte_step);
952 partialbits_mask = (1 << word_num_partialbits) - 1;
955 wordp = buf + word_start;
956 last_wordp = buf + word_last;
960 size_t index_in_word = 0;
961 unsigned char *bytep = wordp + byte_start;
962 while (index_in_word < word_num_fullbytes) {
963 carry += (
unsigned char)~*bytep;
964 *bytep = (
unsigned char)carry;
969 if (word_num_partialbits) {
970 carry += (*bytep & partialbits_mask) ^ partialbits_mask;
971 *bytep = carry & partialbits_mask;
972 carry >>= word_num_partialbits;
977 if (wordp == last_wordp)
990 integer_unpack_num_bdigits_small(
size_t numwords,
size_t wordsize,
size_t nails,
int *nlp_bits_ret)
993 size_t num_bits = (wordsize * CHAR_BIT - nails) * numwords;
994 size_t num_bdigits = roomof(num_bits, BITSPERDIG);
995 *nlp_bits_ret = (int)(num_bdigits * BITSPERDIG - num_bits);
1000 integer_unpack_num_bdigits_generic(
size_t numwords,
size_t wordsize,
size_t nails,
int *nlp_bits_ret)
1007 size_t num_bytes1 = wordsize * numwords;
1010 size_t q1 = numwords / CHAR_BIT;
1011 size_t r1 = numwords % CHAR_BIT;
1014 size_t num_bytes2 = num_bytes1 - nails * q1;
1017 size_t q2 = nails / CHAR_BIT;
1018 size_t r2 = nails % CHAR_BIT;
1021 size_t num_bytes3 = num_bytes2 - q2 * r1;
1024 size_t q3 = num_bytes3 / BITSPERDIG;
1025 size_t r3 = num_bytes3 % BITSPERDIG;
1028 size_t num_digits1 = CHAR_BIT * q3;
1041 if (CHAR_BIT * r3 >= r1 * r2) {
1042 size_t tmp1 = CHAR_BIT * BITSPERDIG - (CHAR_BIT * r3 - r1 * r2);
1043 size_t q4 = tmp1 / BITSPERDIG;
1044 int r4 = (int)(tmp1 % BITSPERDIG);
1045 size_t num_digits2 = num_digits1 + CHAR_BIT - q4;
1050 size_t tmp1 = r1 * r2 - CHAR_BIT * r3;
1051 size_t q4 = tmp1 / BITSPERDIG;
1052 int r4 = (int)(tmp1 % BITSPERDIG);
1053 size_t num_digits2 = num_digits1 - q4;
1060 integer_unpack_num_bdigits(
size_t numwords,
size_t wordsize,
size_t nails,
int *nlp_bits_ret)
1064 if (numwords <= (SIZE_MAX - (BITSPERDIG-1)) / CHAR_BIT / wordsize) {
1065 num_bdigits = integer_unpack_num_bdigits_small(numwords, wordsize, nails, nlp_bits_ret);
1066 if (debug_integer_pack) {
1068 size_t num_bdigits1 = integer_unpack_num_bdigits_generic(numwords, wordsize, nails, &nlp_bits1);
1075 num_bdigits = integer_unpack_num_bdigits_generic(numwords, wordsize, nails, nlp_bits_ret);
1081 integer_unpack_push_bits(
int data,
int numbits, BDIGIT_DBL *ddp,
int *numbits_in_dd_p, BDIGIT **dpp)
1083 (*ddp) |= ((BDIGIT_DBL)data) << (*numbits_in_dd_p);
1084 *numbits_in_dd_p += numbits;
1085 while (BITSPERDIG <= *numbits_in_dd_p) {
1086 *(*dpp)++ = BIGLO(*ddp);
1088 *numbits_in_dd_p -= BITSPERDIG;
1093 integer_unpack_single_bdigit(BDIGIT u,
size_t size,
int flags, BDIGIT *dp)
1098 ((size == SIZEOF_BDIGIT && u == 0) ? -2 : -1) :
1099 ((u >> (size * CHAR_BIT - 1)) ? -1 : 1);
1101 u |= LSHIFTX(BDIGMAX, size * CHAR_BIT);
1111 #ifdef HAVE_BUILTIN___BUILTIN_ASSUME_ALIGNED
1112 #define reinterpret_cast(type, value) (type) \
1113 __builtin_assume_aligned((value), sizeof(*(type)NULL));
1115 #define reinterpret_cast(type, value) (type)value
1119 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)
1122 const unsigned char *buf = words;
1127 de = dp + num_bdigits;
1130 if (nails == 0 && numwords == 1) {
1131 int need_swap = wordsize != 1 &&
1134 if (wordsize == 1) {
1135 return integer_unpack_single_bdigit(*(uint8_t *)buf,
sizeof(uint8_t), flags, dp);
1137 #if defined(HAVE_UINT16_T) && 2 <= SIZEOF_BDIGIT
1138 if (wordsize == 2 && (uintptr_t)words %
RUBY_ALIGNOF(uint16_t) == 0) {
1139 uint16_t u = *reinterpret_cast(
const uint16_t *, buf);
1140 return integer_unpack_single_bdigit(need_swap ? swap16(u) : u,
sizeof(uint16_t), flags, dp);
1143 #if defined(HAVE_UINT32_T) && 4 <= SIZEOF_BDIGIT
1144 if (wordsize == 4 && (uintptr_t)words %
RUBY_ALIGNOF(uint32_t) == 0) {
1145 uint32_t u = *reinterpret_cast(
const uint32_t *, buf);
1146 return integer_unpack_single_bdigit(need_swap ? swap32(u) : u,
sizeof(uint32_t), flags, dp);
1149 #if defined(HAVE_UINT64_T) && 8 <= SIZEOF_BDIGIT
1150 if (wordsize == 8 && (uintptr_t)words %
RUBY_ALIGNOF(uint64_t) == 0) {
1151 uint64_t u = *reinterpret_cast(
const uint64_t *, buf);
1152 return integer_unpack_single_bdigit(need_swap ? swap64(u) : u,
sizeof(uint64_t), flags, dp);
1155 #undef reinterpret_cast
1157 #if !defined(WORDS_BIGENDIAN)
1158 if (nails == 0 && SIZEOF_BDIGIT ==
sizeof(BDIGIT) &&
1161 size_t src_size = numwords * wordsize;
1162 size_t dst_size = num_bdigits * SIZEOF_BDIGIT;
1163 MEMCPY(dp, words,
char, src_size);
1167 memset((
char*)dp + src_size, 0xff, dst_size - src_size);
1168 zero_p = bary_2comp(dp, num_bdigits);
1169 sign = zero_p ? -2 : -1;
1171 else if (buf[src_size-1] >> (CHAR_BIT-1)) {
1172 memset((
char*)dp + src_size, 0xff, dst_size - src_size);
1173 bary_2comp(dp, num_bdigits);
1177 MEMZERO((
char*)dp + src_size,
char, dst_size - src_size);
1182 MEMZERO((
char*)dp + src_size,
char, dst_size - src_size);
1188 if (nails == 0 && SIZEOF_BDIGIT ==
sizeof(BDIGIT) &&
1189 wordsize % SIZEOF_BDIGIT == 0) {
1190 size_t bdigits_per_word = wordsize / SIZEOF_BDIGIT;
1194 MEMCPY(dp, words, BDIGIT, numwords*bdigits_per_word);
1195 if (mswordfirst_p) {
1196 bary_swap(dp, num_bdigits);
1198 if (mswordfirst_p ? !msbytefirst_p : msbytefirst_p) {
1201 for (i = 0; i < numwords; i++) {
1202 bary_swap(p, bdigits_per_word);
1203 p += bdigits_per_word;
1206 if (msbytefirst_p != HOST_BIGENDIAN_P) {
1208 for (p = dp; p < de; p++) {
1210 *p = swap_bdigit(d);
1215 int zero_p = bary_2comp(dp, num_bdigits);
1216 sign = zero_p ? -2 : -1;
1218 else if (BDIGIT_MSB(de[-1])) {
1219 bary_2comp(dp, num_bdigits);
1233 if (num_bdigits != 0) {
1234 int word_num_partialbits;
1235 size_t word_num_fullbytes;
1241 size_t word_start, word_last;
1242 const unsigned char *wordp, *last_wordp;
1246 integer_pack_loop_setup(numwords, wordsize, nails, flags,
1247 &word_num_fullbytes, &word_num_partialbits,
1248 &word_start, &word_step, &word_last, &byte_start, &byte_step);
1250 wordp = buf + word_start;
1251 last_wordp = buf + word_last;
1256 #define PUSH_BITS(data, numbits) \
1257 integer_unpack_push_bits(data, numbits, &dd, &numbits_in_dd, &dp)
1260 size_t index_in_word = 0;
1261 const unsigned char *bytep = wordp + byte_start;
1262 while (index_in_word < word_num_fullbytes) {
1263 PUSH_BITS(*bytep, CHAR_BIT);
1267 if (word_num_partialbits) {
1268 PUSH_BITS(*bytep & ((1 << word_num_partialbits) - 1), word_num_partialbits);
1273 if (wordp == last_wordp)
1292 (bdigits[num_bdigits-1] >> (BITSPERDIG - nlp_bits - 1))) {
1293 bdigits[num_bdigits-1] |= BIGLO(BDIGMAX << (BITSPERDIG - nlp_bits));
1302 sign = bary_zero_p(bdigits, num_bdigits) ? -2 : -1;
1305 if (num_bdigits != 0 && BDIGIT_MSB(bdigits[num_bdigits-1]))
1311 if (sign == -1 && num_bdigits != 0) {
1312 bary_2comp(bdigits, num_bdigits);
1320 bary_unpack(BDIGIT *bdigits,
size_t num_bdigits,
const void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
1322 size_t num_bdigits0;
1326 validate_integer_pack_format(numwords, wordsize, nails, flags,
1337 num_bdigits0 = integer_unpack_num_bdigits(numwords, wordsize, nails, &nlp_bits);
1341 sign = bary_unpack_internal(bdigits, num_bdigits0, words, numwords, wordsize, nails, flags, nlp_bits);
1343 if (num_bdigits0 < num_bdigits) {
1344 BDIGITS_ZERO(bdigits + num_bdigits0, num_bdigits - num_bdigits0);
1346 bdigits[num_bdigits0] = 1;
1352 bary_subb(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn,
int borrow)
1354 BDIGIT_DBL_SIGNED num;
1361 sn = xn < yn ? xn : yn;
1363 num = borrow ? -1 : 0;
1364 for (i = 0; i < sn; i++) {
1365 num += (BDIGIT_DBL_SIGNED)xds[i] - yds[i];
1366 zds[i] = BIGLO(num);
1370 for (; i < xn; i++) {
1371 if (num == 0)
goto num_is_zero;
1373 zds[i] = BIGLO(num);
1378 for (; i < yn; i++) {
1380 zds[i] = BIGLO(num);
1384 if (num == 0)
goto num_is_zero;
1385 for (; i < zn; i++) {
1391 if (xds == zds && xn == zn)
1393 for (; i < xn; i++) {
1396 for (; i < zn; i++) {
1403 bary_sub(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
1405 return bary_subb(zds, zn, xds, xn, yds, yn, 0);
1409 bary_sub_one(BDIGIT *zds,
size_t zn)
1411 return bary_subb(zds, zn, zds, zn, NULL, 0, 1);
1415 bary_addc(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn,
int carry)
1425 tds = xds; xds = yds; yds = tds;
1426 i = xn; xn = yn; yn = i;
1429 num = carry ? 1 : 0;
1430 for (i = 0; i < xn; i++) {
1431 num += (BDIGIT_DBL)xds[i] + yds[i];
1432 zds[i] = BIGLO(num);
1435 for (; i < yn; i++) {
1436 if (num == 0)
goto num_is_zero;
1438 zds[i] = BIGLO(num);
1441 for (; i < zn; i++) {
1442 if (num == 0)
goto num_is_zero;
1443 zds[i] = BIGLO(num);
1449 if (yds == zds && yn == zn)
1451 for (; i < yn; i++) {
1454 for (; i < zn; i++) {
1461 bary_add(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
1463 return bary_addc(zds, zn, xds, xn, yds, yn, 0);
1467 bary_add_one(BDIGIT *ds,
size_t n)
1470 for (i = 0; i < n; i++) {
1471 BDIGIT_DBL n = ds[i];
1481 bary_mul_single(BDIGIT *zds,
size_t zn, BDIGIT x, BDIGIT y)
1487 n = (BDIGIT_DBL)x * y;
1488 bdigitdbl2bary(zds, 2, n);
1489 BDIGITS_ZERO(zds + 2, zn - 2);
1493 bary_muladd_1xN(BDIGIT *zds,
size_t zn, BDIGIT x,
const BDIGIT *yds,
size_t yn)
1505 for (j = 0; j < yn; j++) {
1506 BDIGIT_DBL ee = n + dd * yds[j];
1517 for (; j < zn; j++) {
1527 static BDIGIT_DBL_SIGNED
1528 bigdivrem_mulsub(BDIGIT *zds,
size_t zn, BDIGIT x,
const BDIGIT *yds,
size_t yn)
1532 BDIGIT_DBL_SIGNED num;
1541 BDIGIT_DBL_SIGNED ee;
1542 t2 += (BDIGIT_DBL)yds[i] * x;
1543 ee = num - BIGLO(t2);
1544 num = (BDIGIT_DBL_SIGNED)zds[i] + ee;
1545 if (ee) zds[i] = BIGLO(num);
1549 num -= (BDIGIT_DBL_SIGNED)t2;
1550 num += (BDIGIT_DBL_SIGNED)zds[yn];
1555 bary_mulsub_1xN(BDIGIT *zds,
size_t zn, BDIGIT x,
const BDIGIT *yds,
size_t yn)
1557 BDIGIT_DBL_SIGNED num;
1561 num = bigdivrem_mulsub(zds, zn, x, yds, yn);
1562 zds[yn] = BIGLO(num);
1569 bary_mul_normal(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
1575 BDIGITS_ZERO(zds, zn);
1576 for (i = 0; i < xn; i++) {
1577 bary_muladd_1xN(zds+i, zn-i, xds[i], yds, yn);
1584 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), zn = xn + yn;
1585 VALUE z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
1586 bary_mul_normal(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn);
1597 bary_sq_fast(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn)
1606 BDIGITS_ZERO(zds, zn);
1611 for (i = 0; i < xn-1; i++) {
1612 v = (BDIGIT_DBL)xds[i];
1615 c = (BDIGIT_DBL)zds[i + i] + v * v;
1616 zds[i + i] = BIGLO(c);
1621 for (j = i + 1; j < xn; j++) {
1622 w = (BDIGIT_DBL)xds[j];
1623 c += (BDIGIT_DBL)zds[i + j] + vl * w;
1624 zds[i + j] = BIGLO(c);
1630 c += (BDIGIT_DBL)zds[i + xn];
1631 zds[i + xn] = BIGLO(c);
1634 zds[i + xn + 1] += (BDIGIT)c;
1639 v = (BDIGIT_DBL)xds[i];
1642 c = (BDIGIT_DBL)zds[i + i] + v * v;
1643 zds[i + i] = BIGLO(c);
1646 zds[i + xn] += BIGLO(c);
1651 rb_big_sq_fast(
VALUE x)
1653 size_t xn = BIGNUM_LEN(x), zn = 2 * xn;
1654 VALUE z = bignew(zn, 1);
1655 bary_sq_fast(BDIGITS(z), zn, BDIGITS(x), xn);
1660 static inline size_t
1661 max_size(
size_t a,
size_t b)
1663 return (a > b ? a : b);
1668 bary_mul_balance_with_mulfunc(BDIGIT *
const zds,
const size_t zn,
1669 const BDIGIT *
const xds,
const size_t xn,
1670 const BDIGIT *
const yds,
const size_t yn,
1671 BDIGIT *wds,
size_t wn, mulfunc_t *
const mulfunc)
1678 RUBY_ASSERT(!KARATSUBA_BALANCED(xn, yn) || !TOOM3_BALANCED(xn, yn));
1680 BDIGITS_ZERO(zds, xn);
1689 const size_t r = yn % xn;
1690 if (2*xn + yn + max_size(xn-r, r) > zn) {
1698 const size_t r = (xn > (yn - n) ? (yn - n) : xn);
1699 const size_t tn = (xn + r);
1700 if (2 * (xn + r) <= zn - n) {
1701 BDIGIT *
const tds = zds + n + xn + r;
1702 mulfunc(tds, tn, xds, xn, yds + n, r, wds, wn);
1703 BDIGITS_ZERO(zds + n + xn, r);
1704 bary_add(zds + n, tn,
1709 BDIGIT *
const tds = zds + n;
1716 rb_bug(
"wds is not enough: %" PRIdSIZE
" for %" PRIdSIZE, wn, xn);
1719 MEMCPY(wds, zds + n, BDIGIT, xn);
1720 mulfunc(tds, tn, xds, xn, yds + n, r, wds+xn, wn-xn);
1721 bary_add(zds + n, tn,
1727 BDIGITS_ZERO(zds+xn+yn, zn - (xn+yn));
1736 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), zn = xn + yn;
1737 VALUE z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
1738 bary_mul_balance_with_mulfunc(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, NULL, 0, bary_mul_toom3_start);
1746 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)
1751 int sub_p, borrow, carry1, carry2, carry3;
1757 const BDIGIT *xds0, *xds1, *yds0, *yds1;
1758 BDIGIT *zds0, *zds1, *zds2, *zds3;
1764 sq = xds == yds && xn == yn;
1814 if (bary_sub(zds0, n, xds, n, xds+n, xn-n)) {
1815 bary_2comp(zds0, n);
1823 bary_mul_karatsuba_start(zds1, 2*n, zds0, n, zds0, n, wds, wn);
1826 if (bary_sub(wds, n, yds, n, yds+n, n)) {
1833 bary_mul_karatsuba_start(zds1, 2*n, zds0, n, wds, n, wds+n, wn-n);
1840 borrow = !bary_2comp(zds1, 2*n);
1844 MEMCPY(wds, zds1, BDIGIT, n);
1848 bary_mul_karatsuba_start(zds0, 2*n, xds0, n, yds0, n, wds+n, wn-n);
1852 carry1 = bary_add(wds, n, wds, n, zds0, n);
1853 carry1 = bary_addc(zds2, n, zds2, n, zds1, n, carry1);
1857 carry2 = bary_add(zds1, n, zds1, n, wds, n);
1861 MEMCPY(wds, zds2, BDIGIT, n);
1865 bary_mul_karatsuba_start(zds2, zn-2*n, xds1, xn-n, yds1, n, wds+n, wn-n);
1869 carry3 = bary_add(zds1, n, zds1, n, zds2, n);
1873 carry3 = bary_addc(zds2, n, zds2, n, zds3, (4*n < zn ? n : zn-3*n), carry3);
1877 bary_add(zds2, zn-2*n, zds2, zn-2*n, wds, n);
1882 bary_add_one(zds2, zn-2*n);
1884 if (carry1 + carry3 - borrow < 0)
1885 bary_sub_one(zds3, zn-3*n);
1886 else if (carry1 + carry3 - borrow > 0) {
1887 BDIGIT c = carry1 + carry3 - borrow;
1888 bary_add(zds3, zn-3*n, zds3, zn-3*n, &c, 1);
1903 bary_muladd_1xN(zds+yn, zn-yn, yds[yn], xds, xn);
1904 bary_muladd_1xN(zds+xn, zn-xn, xds[xn], yds, yn+1);
1907 bary_muladd_1xN(zds+yn, zn-yn, yds[yn], xds, xn);
1917 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), zn = xn + yn;
1918 VALUE z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
1919 if (!((xn <= yn && yn < 2) || KARATSUBA_BALANCED(xn, yn)))
1921 bary_mul_karatsuba(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, NULL, 0);
1928 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)
1935 size_t x0n;
const BDIGIT *x0ds;
1936 size_t x1n;
const BDIGIT *x1ds;
1937 size_t x2n;
const BDIGIT *x2ds;
1938 size_t y0n;
const BDIGIT *y0ds;
1939 size_t y1n;
const BDIGIT *y1ds;
1940 size_t y2n;
const BDIGIT *y2ds;
1942 size_t u1n; BDIGIT *u1ds;
int u1p;
1943 size_t u2n; BDIGIT *u2ds;
int u2p;
1944 size_t u3n; BDIGIT *u3ds;
int u3p;
1946 size_t v1n; BDIGIT *v1ds;
int v1p;
1947 size_t v2n; BDIGIT *v2ds;
int v2p;
1948 size_t v3n; BDIGIT *v3ds;
int v3p;
1950 size_t t0n; BDIGIT *t0ds;
int t0p;
1951 size_t t1n; BDIGIT *t1ds;
int t1p;
1952 size_t t2n; BDIGIT *t2ds;
int t2p;
1953 size_t t3n; BDIGIT *t3ds;
int t3p;
1954 size_t t4n; BDIGIT *t4ds;
int t4p;
1956 size_t z0n; BDIGIT *z0ds;
1957 size_t z1n; BDIGIT *z1ds;
int z1p;
1958 size_t z2n; BDIGIT *z2ds;
int z2p;
1959 size_t z3n; BDIGIT *z3ds;
int z3p;
1960 size_t z4n; BDIGIT *z4ds;
1962 size_t zzn; BDIGIT *zzds;
1964 int sq = xds == yds && xn == yn;
1982 wnc += (t1n = 2*n+2);
1983 wnc += (t2n = 2*n+2);
1984 wnc += (t3n = 2*n+2);
1987 wnc += (z1n = 2*n+1);
1988 wnc += (z2n = 2*n+1);
1989 wnc += (z3n = 2*n+1);
1996 u1ds = wds; wds += u1n;
1997 u2ds = wds; wds += u2n;
1998 u3ds = wds; wds += u3n;
2000 v1ds = wds; wds += v1n;
2001 v2ds = wds; wds += v2n;
2002 v3ds = wds; wds += v3n;
2004 t0ds = wds; wds += t0n;
2005 t1ds = wds; wds += t1n;
2006 t2ds = wds; wds += t2n;
2007 t3ds = wds; wds += t3n;
2008 t4ds = wds; wds += t4n;
2010 z1ds = wds; wds += z1n;
2011 z2ds = wds; wds += z2n;
2012 z3ds = wds; wds += z3n;
2078 bary_add(u1ds, u1n, x0ds, x0n, x2ds, x2n);
2082 if (bary_sub(u2ds, u2n, u1ds, u1n, x1ds, x1n)) {
2083 bary_2comp(u2ds, u2n);
2091 bary_add(u1ds, u1n, u1ds, u1n, x1ds, x1n);
2096 bary_add(u3ds, u3n, u2ds, u2n, x2ds, x2n);
2098 else if (bary_sub(u3ds, u3n, x2ds, x2n, u2ds, u2n)) {
2099 bary_2comp(u3ds, u3n);
2102 bary_small_lshift(u3ds, u3ds, u3n, 1);
2104 bary_add(u3ds, u3n, u3ds, u3n, x0ds, x0n);
2106 else if (bary_sub(u3ds, u3n, u3ds, u3n, x0ds, x0n)) {
2107 bary_2comp(u3ds, u3n);
2112 v1n = u1n; v1ds = u1ds; v1p = u1p;
2113 v2n = u2n; v2ds = u2ds; v2p = u2p;
2114 v3n = u3n; v3ds = u3ds; v3p = u3p;
2118 bary_add(v1ds, v1n, y0ds, y0n, y2ds, y2n);
2123 if (bary_sub(v2ds, v2n, v1ds, v1n, y1ds, y1n)) {
2124 bary_2comp(v2ds, v2n);
2129 bary_add(v1ds, v1n, v1ds, v1n, y1ds, y1n);
2134 bary_add(v3ds, v3n, v2ds, v2n, y2ds, y2n);
2136 else if (bary_sub(v3ds, v3n, y2ds, y2n, v2ds, v2n)) {
2137 bary_2comp(v3ds, v3n);
2140 bary_small_lshift(v3ds, v3ds, v3n, 1);
2142 bary_add(v3ds, v3n, v3ds, v3n, y0ds, y0n);
2144 else if (bary_sub(v3ds, v3n, v3ds, v3n, y0ds, y0n)) {
2145 bary_2comp(v3ds, v3n);
2151 bary_mul_toom3_start(t0ds, t0n, x0ds, x0n, y0ds, y0n, wds, wn);
2155 bary_mul_toom3_start(t1ds, t1n, u1ds, u1n, v1ds, v1n, wds, wn);
2161 bary_mul_toom3_start(t2ds, t2n, u2ds, u2n, v2ds, v2n, wds, wn);
2167 bary_mul_toom3_start(t3ds, t3n, u3ds, u3n, v3ds, v3n, wds, wn);
2173 bary_mul_toom3_start(t4ds, t4n, x2ds, x2n, y2ds, y2n, wds, wn);
2181 z0n = t0n; z0ds = t0ds;
2184 z4n = t4n; z4ds = t4ds;
2189 if (bary_sub(z3ds, z3n, t3ds, t3n, t1ds, t1n)) {
2190 bary_2comp(z3ds, z3n);
2196 bary_add(z3ds, z3n, t3ds, t3n, t1ds, t1n);
2198 bigdivrem_single(z3ds, z3ds, z3n, 3);
2203 if (bary_sub(z1ds, z1n, t1ds, t1n, t2ds, t2n)) {
2204 bary_2comp(z1ds, z1n);
2210 bary_add(z1ds, z1n, t1ds, t1n, t2ds, t2n);
2212 bary_small_rshift(z1ds, z1ds, z1n, 1, 0);
2217 if (bary_sub(z2ds, z2n, t2ds, t2n, t0ds, t0n)) {
2218 bary_2comp(z2ds, z2n);
2224 bary_add(z2ds, z2n, t2ds, t2n, t0ds, t0n);
2230 if (bary_sub(z3ds, z3n, z2ds, z2n, z3ds, z3n)) {
2231 bary_2comp(z3ds, z3n);
2237 bary_add(z3ds, z3n, z2ds, z2n, z3ds, z3n);
2239 bary_small_rshift(z3ds, z3ds, z3n, 1, 0);
2241 bary_muladd_1xN(z3ds, z3n, 2, t4ds, t4n);
2244 if (bary_mulsub_1xN(z3ds, z3n, 2, t4ds, t4n)) {
2245 bary_2comp(z3ds, z3n);
2252 bary_add(z2ds, z2n, z2ds, z2n, z1ds, z1n);
2255 if (bary_sub(z2ds, z2n, z2ds, z2n, z1ds, z1n)) {
2256 bary_2comp(z2ds, z2n);
2262 if (bary_sub(z2ds, z2n, z2ds, z2n, t4ds, t4n)) {
2263 bary_2comp(z2ds, z2n);
2268 bary_add(z2ds, z2n, z2ds, z2n, t4ds, t4n);
2273 if (bary_sub(z1ds, z1n, z1ds, z1n, z3ds, z3n)) {
2274 bary_2comp(z1ds, z1n);
2279 bary_add(z1ds, z1n, z1ds, z1n, z3ds, z3n);
2286 MEMCPY(zzds, z0ds, BDIGIT, z0n);
2287 BDIGITS_ZERO(zzds + z0n, 4*n - z0n);
2288 MEMCPY(zzds + 4*n, z4ds, BDIGIT, z4n);
2289 BDIGITS_ZERO(zzds + 4*n + z4n, zzn - (4*n + z4n));
2291 bary_add(zzds + n, zzn - n, zzds + n, zzn - n, z1ds, z1n);
2293 bary_sub(zzds + n, zzn - n, zzds + n, zzn - n, z1ds, z1n);
2295 bary_add(zzds + 2*n, zzn - 2*n, zzds + 2*n, zzn - 2*n, z2ds, z2n);
2297 bary_sub(zzds + 2*n, zzn - 2*n, zzds + 2*n, zzn - 2*n, z2ds, z2n);
2299 bary_add(zzds + 3*n, zzn - 3*n, zzds + 3*n, zzn - 3*n, z3ds, z3n);
2301 bary_sub(zzds + 3*n, zzn - 3*n, zzds + 3*n, zzn - 3*n, z3ds, z3n);
2303 BARY_TRUNC(zzds, zzn);
2304 MEMCPY(zds, zzds, BDIGIT, zzn);
2305 BDIGITS_ZERO(zds + zzn, zn - zzn);
2314 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), zn = xn + yn;
2315 VALUE z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
2316 if (xn > yn || yn < 3 || !TOOM3_BALANCED(xn,yn))
2318 bary_mul_toom3(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, NULL, 0);
2326 bdigits_to_mpz(mpz_t mp,
const BDIGIT *digits,
size_t len)
2328 const size_t nails = (
sizeof(BDIGIT)-SIZEOF_BDIGIT)*CHAR_BIT;
2329 mpz_import(mp,
len, -1,
sizeof(BDIGIT), 0, nails, digits);
2333 bdigits_from_mpz(mpz_t mp, BDIGIT *digits,
size_t *
len)
2335 const size_t nails = (
sizeof(BDIGIT)-SIZEOF_BDIGIT)*CHAR_BIT;
2336 mpz_export(digits,
len, -1,
sizeof(BDIGIT), 0, nails, mp);
2340 bary_mul_gmp(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2350 bdigits_to_mpz(x, xds, xn);
2351 if (xds == yds && xn == yn) {
2355 bdigits_to_mpz(y, yds, yn);
2358 bdigits_from_mpz(z, zds, &count);
2359 BDIGITS_ZERO(zds+count, zn-count);
2368 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), zn = xn + yn;
2369 VALUE z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
2370 bary_mul_gmp(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn);
2378 bary_short_mul(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2382 if (xn == 1 && yn == 1) {
2383 bary_mul_single(zds, zn, xds[0], yds[0]);
2386 bary_mul_normal(zds, zn, xds, xn, yds, yn);
2393 bary_sparse_p(
const BDIGIT *ds,
size_t n)
2397 if ( ds[2 * n / 5]) c++;
2398 if (c <= 1 && ds[ n / 2]) c++;
2399 if (c <= 1 && ds[3 * n / 5]) c++;
2401 return (c <= 1) ? 1 : 0;
2405 bary_mul_precheck(BDIGIT **zdsp,
size_t *znp,
const BDIGIT **xdsp,
size_t *xnp,
const BDIGIT **ydsp,
size_t *ynp)
2409 BDIGIT *zds = *zdsp;
2411 const BDIGIT *xds = *xdsp;
2413 const BDIGIT *yds = *ydsp;
2421 if (xds[xn-1] == 0) {
2437 if (yds[yn-1] == 0) {
2453 BDIGITS_ZERO(zds, nlsz);
2462 tds = xds; xds = yds; yds = tds;
2463 tn = xn; xn = yn; yn = tn;
2469 BDIGITS_ZERO(zds, zn);
2474 MEMCPY(zds, yds, BDIGIT, yn);
2475 BDIGITS_ZERO(zds+yn, zn-yn);
2478 if (POW2_P(xds[0])) {
2479 zds[yn] = bary_small_lshift(zds, yds, yn, bit_length(xds[0])-1);
2480 BDIGITS_ZERO(zds+yn+1, zn-yn-1);
2483 if (yn == 1 && yds[0] == 1) {
2485 BDIGITS_ZERO(zds+1, zn-1);
2488 bary_mul_normal(zds, zn, xds, xn, yds, yn);
2503 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)
2506 if (xn < KARATSUBA_MUL_DIGITS) {
2511 if (bary_sparse_p(xds, xn))
goto normal;
2512 if (bary_sparse_p(yds, yn)) {
2513 bary_short_mul(zds, zn, yds, yn, xds, xn);
2518 if (!KARATSUBA_BALANCED(xn, yn)) {
2519 bary_mul_balance_with_mulfunc(zds, zn, xds, xn, yds, yn, wds, wn, bary_mul_karatsuba_start);
2524 bary_mul_karatsuba(zds, zn, xds, xn, yds, yn, wds, wn);
2528 if (xds == yds && xn == yn) {
2529 bary_sq_fast(zds, zn, xds, xn);
2532 bary_short_mul(zds, zn, xds, xn, yds, yn);
2537 bary_mul_karatsuba_start(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn, BDIGIT *wds,
size_t wn)
2539 if (bary_mul_precheck(&zds, &zn, &xds, &xn, &yds, &yn))
2542 bary_mul_karatsuba_branch(zds, zn, xds, xn, yds, yn, wds, wn);
2546 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)
2548 if (xn < TOOM3_MUL_DIGITS) {
2549 bary_mul_karatsuba_branch(zds, zn, xds, xn, yds, yn, wds, wn);
2553 if (!TOOM3_BALANCED(xn, yn)) {
2554 bary_mul_balance_with_mulfunc(zds, zn, xds, xn, yds, yn, wds, wn, bary_mul_toom3_start);
2558 bary_mul_toom3(zds, zn, xds, xn, yds, yn, wds, wn);
2562 bary_mul_toom3_start(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn, BDIGIT *wds,
size_t wn)
2564 if (bary_mul_precheck(&zds, &zn, &xds, &xn, &yds, &yn))
2567 bary_mul_toom3_branch(zds, zn, xds, xn, yds, yn, wds, wn);
2571 bary_mul(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2574 if (xn < NAIVE_MUL_DIGITS) {
2575 if (xds == yds && xn == yn)
2576 bary_sq_fast(zds, zn, xds, xn);
2578 bary_short_mul(zds, zn, xds, xn, yds, yn);
2583 if (yn < NAIVE_MUL_DIGITS) {
2584 bary_short_mul(zds, zn, yds, yn, xds, xn);
2590 bary_mul_gmp(zds, zn, xds, xn, yds, yn);
2592 bary_mul_toom3_start(zds, zn, xds, xn, yds, yn, NULL, 0);
2599 volatile VALUE stop;
2603 bigdivrem1(
void *
ptr)
2606 size_t yn = bds->yn;
2607 size_t zn = bds->zn;
2608 BDIGIT *yds = bds->yds, *zds = bds->zds;
2609 BDIGIT_DBL_SIGNED num;
2617 if (zds[zn-1] == yds[yn-1]) q = BDIGMAX;
2618 else q = (BDIGIT)((BIGUP(zds[zn-1]) + zds[zn-2])/yds[yn-1]);
2620 num = bigdivrem_mulsub(zds+zn-(yn+1), yn+1,
2625 num = bary_add(zds+zn-(yn+1), yn,
2639 rb_big_stop(
void *
ptr)
2646 bigdivrem_single1(BDIGIT *qds,
const BDIGIT *xds,
size_t xn, BDIGIT x_higher_bdigit, BDIGIT y)
2653 bary_small_rshift(qds, xds, xn, bit_length(y)-1, x_higher_bdigit);
2659 t2 = x_higher_bdigit;
2660 for (i = 0; i < xn; i++) {
2661 t2 = BIGUP(t2) + xds[xn - i - 1];
2662 qds[xn - i - 1] = (BDIGIT)(t2 / y);
2670 bigdivrem_single(BDIGIT *qds,
const BDIGIT *xds,
size_t xn, BDIGIT y)
2672 return bigdivrem_single1(qds, xds, xn, 0, y);
2676 bigdivrem_restoring(BDIGIT *zds,
size_t zn, BDIGIT *yds,
size_t yn)
2685 for (ynzero = 0; !yds[ynzero]; ynzero++);
2687 if (ynzero+1 == yn) {
2689 r = bigdivrem_single1(zds+yn, zds+ynzero, zn-yn, zds[zn-1], yds[ynzero]);
2694 bds.yn = yn - ynzero;
2695 bds.zds = zds + ynzero;
2696 bds.yds = yds + ynzero;
2698 bds.zn = zn - ynzero;
2699 if (bds.zn > 10000 || bds.yn > 10000) {
2704 if (bds.stop ==
Qtrue) {
2715 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)
2722 RUBY_ASSERT(yn < xn || (xn == yn && yds[yn - 1] <= xds[xn - 1]));
2726 zn = xn + BIGDIVREM_EXTRA_WORDS;
2728 shift = nlz(yds[yn-1]);
2731 int alloc_z = !qds || qn < zn;
2732 if (alloc_y && alloc_z) {
2733 yyds =
ALLOCV_N(BDIGIT, tmpyz, yn+zn);
2737 yyds = alloc_y ?
ALLOCV_N(BDIGIT, tmpyz, yn) : rds;
2738 zds = alloc_z ?
ALLOCV_N(BDIGIT, tmpyz, zn) : qds;
2740 zds[xn] = bary_small_lshift(zds, xds, xn, shift);
2741 bary_small_lshift(yyds, yds, yn, shift);
2744 if (qds && zn <= qn)
2748 MEMCPY(zds, xds, BDIGIT, xn);
2752 yyds = (BDIGIT *)yds;
2755 bigdivrem_restoring(zds, zn, yyds, yn);
2759 bary_small_rshift(rds, zds, yn, shift, 0);
2761 MEMCPY(rds, zds, BDIGIT, yn);
2762 BDIGITS_ZERO(rds+yn, rn-yn);
2767 MEMMOVE(qds, zds+yn, BDIGIT, j);
2768 BDIGITS_ZERO(qds+j, qn-j);
2778 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), qn, rn;
2779 BDIGIT *xds = BDIGITS(x), *yds = BDIGITS(y), *qds, *rds;
2782 BARY_TRUNC(yds, yn);
2785 BARY_TRUNC(xds, xn);
2787 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1]))
2790 qn = xn + BIGDIVREM_EXTRA_WORDS;
2791 q = bignew(qn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
2795 r = bignew(rn, BIGNUM_SIGN(x));
2798 bary_divmod_normal(qds, qn, rds, rn, xds, xn, yds, yn);
2811 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)
2816 RUBY_ASSERT(yn < xn || (xn == yn && yds[yn - 1] <= xds[xn - 1]));
2823 if (qds) mpz_init(q);
2824 if (rds) mpz_init(r);
2826 bdigits_to_mpz(x, xds, xn);
2827 bdigits_to_mpz(y, yds, yn);
2830 mpz_fdiv_q(q, x, y);
2833 mpz_fdiv_r(r, x, y);
2836 mpz_fdiv_qr(q, r, x, y);
2843 bdigits_from_mpz(q, qds, &count);
2844 BDIGITS_ZERO(qds+count, qn-count);
2849 bdigits_from_mpz(r, rds, &count);
2850 BDIGITS_ZERO(rds+count, rn-count);
2858 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), qn, rn;
2859 BDIGIT *xds = BDIGITS(x), *yds = BDIGITS(y), *qds, *rds;
2862 BARY_TRUNC(yds, yn);
2865 BARY_TRUNC(xds, xn);
2867 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1]))
2871 q = bignew(qn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
2875 r = bignew(rn, BIGNUM_SIGN(x));
2878 bary_divmod_gmp(qds, qn, rds, rn, xds, xn, yds, yn);
2891 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)
2894 if (GMP_DIV_DIGITS < xn) {
2895 bary_divmod_gmp(qds, qn, rds, rn, xds, xn, yds, yn);
2899 bary_divmod_normal(qds, qn, rds, rn, xds, xn, yds, yn);
2903 bary_divmod(BDIGIT *qds,
size_t qn, BDIGIT *rds,
size_t rn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2908 BARY_TRUNC(yds, yn);
2912 BARY_TRUNC(xds, xn);
2914 BDIGITS_ZERO(qds, qn);
2915 BDIGITS_ZERO(rds, rn);
2919 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1])) {
2920 MEMCPY(rds, xds, BDIGIT, xn);
2921 BDIGITS_ZERO(rds+xn, rn-xn);
2922 BDIGITS_ZERO(qds, qn);
2925 MEMCPY(qds, xds, BDIGIT, xn);
2926 BDIGITS_ZERO(qds+xn, qn-xn);
2927 rds[0] = bigdivrem_single(qds, xds, xn, yds[0]);
2928 BDIGITS_ZERO(rds+1, rn-1);
2930 else if (xn == 2 && yn == 2) {
2931 BDIGIT_DBL x = bary2bdigitdbl(xds, 2);
2932 BDIGIT_DBL y = bary2bdigitdbl(yds, 2);
2933 BDIGIT_DBL q = x / y;
2934 BDIGIT_DBL r = x % y;
2936 qds[1] = BIGLO(BIGDN(q));
2937 BDIGITS_ZERO(qds+2, qn-2);
2939 rds[1] = BIGLO(BIGDN(r));
2940 BDIGITS_ZERO(rds+2, rn-2);
2943 bary_divmod_branch(qds, qn, rds, rn, xds, xn, yds, yn);
2948 #ifndef BIGNUM_DEBUG
2949 # define BIGNUM_DEBUG (0+RUBY_DEBUG)
2955 return bary_zero_p(BDIGITS(x), BIGNUM_LEN(x));
2972 if (l > 0)
return 1;
2973 if (l < 0)
return -1;
2976 if (RB_BIGNUM_TYPE_P(val)) {
2977 if (BIGZEROP(val))
return 0;
2978 if (BIGNUM_SIGN(val))
return 1;
2986 #define BIGNUM_SET_LEN(b,l) \
2987 (BIGNUM_EMBED_P(b) ? \
2988 (void)(RBASIC(b)->flags = \
2989 (RBASIC(b)->flags & ~BIGNUM_EMBED_LEN_MASK) | \
2990 ((l) << BIGNUM_EMBED_LEN_SHIFT)) : \
2991 (void)(RBIGNUM(b)->as.heap.len = (l)))
2994 rb_big_realloc(
VALUE big,
size_t len)
2997 if (BIGNUM_EMBED_P(big)) {
2998 if (BIGNUM_EMBED_LEN_MAX <
len) {
3000 MEMCPY(ds, RBIGNUM(big)->as.ary, BDIGIT, BIGNUM_EMBED_LEN_MAX);
3001 RBIGNUM(big)->as.heap.len = BIGNUM_LEN(big);
3002 RBIGNUM(big)->as.heap.digits = ds;
3007 if (
len <= BIGNUM_EMBED_LEN_MAX) {
3008 ds = RBIGNUM(big)->as.heap.digits;
3010 BIGNUM_SET_LEN(big,
len);
3011 (void)VALGRIND_MAKE_MEM_UNDEFINED((
void*)RBIGNUM(big)->as.ary,
sizeof(RBIGNUM(big)->as.ary));
3013 MEMCPY(RBIGNUM(big)->as.ary, ds, BDIGIT,
len);
3018 if (BIGNUM_LEN(big) == 0) {
3019 RBIGNUM(big)->as.heap.digits =
ALLOC_N(BDIGIT,
len);
3031 rb_big_realloc(big,
len);
3032 BIGNUM_SET_LEN(big,
len);
3036 bignew_1(
VALUE klass,
size_t len,
int sign)
3038 NEWOBJ_OF(big,
struct RBignum, klass,
3041 BIGNUM_SET_SIGN(bigv, sign);
3042 if (
len <= BIGNUM_EMBED_LEN_MAX) {
3044 BIGNUM_SET_LEN(bigv,
len);
3045 (void)VALGRIND_MAKE_MEM_UNDEFINED((
void*)big->as.ary,
sizeof(big->as.ary));
3049 big->as.heap.len =
len;
3058 return bignew(
len, sign != 0);
3064 size_t len = BIGNUM_LEN(x);
3067 MEMCPY(BDIGITS(z), BDIGITS(x), BDIGIT,
len);
3072 big_extend_carry(
VALUE x)
3075 BDIGITS(x)[BIGNUM_LEN(x)-1] = 1;
3082 long i = BIGNUM_LEN(x);
3083 BDIGIT *ds = BDIGITS(x);
3085 if (bary_2comp(ds, i)) {
3086 big_extend_carry(x);
3097 abs2twocomp(
VALUE *xp,
long *n_ret)
3100 long n = BIGNUM_LEN(x);
3101 BDIGIT *ds = BDIGITS(x);
3106 if (n != 0 && BIGNUM_NEGATIVE_P(x)) {
3108 MEMCPY(BDIGITS(z), ds, BDIGIT, n);
3109 bary_2comp(BDIGITS(z), n);
3118 twocomp2abs_bang(
VALUE x,
int hibits)
3120 BIGNUM_SET_SIGN(x, !hibits);
3129 size_t len = BIGNUM_LEN(x);
3130 BDIGIT *ds = BDIGITS(x);
3132 if (
len == 0)
return x;
3133 while (--
len && !ds[
len]);
3134 if (BIGNUM_LEN(x) >
len+1) {
3143 size_t n = BIGNUM_LEN(x);
3144 BDIGIT *ds = BDIGITS(x);
3145 #if SIZEOF_BDIGIT < SIZEOF_LONG
3153 if (n == 0)
return INT2FIX(0);
3155 #if SIZEOF_BDIGIT < SIZEOF_LONG
3156 if (
sizeof(
long)/SIZEOF_BDIGIT < n)
3162 u = (
unsigned long)(BIGUP(u) + ds[i]);
3172 if (BIGNUM_POSITIVE_P(x)) {
3187 if (RB_BIGNUM_TYPE_P(x)) {
3204 BDIGIT *digits = BDIGITS(big);
3206 #if SIZEOF_BDIGIT >= SIZEOF_VALUE
3210 digits[i] = BIGLO(n);
3216 while (--i && !digits[i]) ;
3217 BIGNUM_SET_LEN(big, i+1);
3229 u = 1 + (
VALUE)(-(n + 1));
3237 BIGNUM_SET_NEGATIVE_SIGN(big);
3293 BDIGIT fixbuf[bdigit_roomof(
sizeof(
long))];
3295 int num_leading_zeros;
3304 #if SIZEOF_BDIGIT >= SIZEOF_LONG
3309 for (i = 0; i < numberof(fixbuf); i++) {
3310 fixbuf[i] = BIGLO(v);
3316 de = fixbuf + numberof(fixbuf);
3320 de = dp + BIGNUM_LEN(val);
3322 while (dp < de && de[-1] == 0)
3329 num_leading_zeros = nlz(de[-1]);
3331 *nlz_bits_ret = num_leading_zeros % CHAR_BIT;
3332 return (de - dp) * SIZEOF_BDIGIT - num_leading_zeros / CHAR_BIT;
3336 absint_numwords_small(
size_t numbytes,
int nlz_bits_in_msbyte,
size_t word_numbits,
size_t *nlz_bits_ret)
3338 size_t val_numbits = numbytes * CHAR_BIT - nlz_bits_in_msbyte;
3339 size_t div = val_numbits / word_numbits;
3340 size_t mod = val_numbits % word_numbits;
3343 numwords = mod == 0 ? div : div + 1;
3344 nlz_bits = mod == 0 ? 0 : word_numbits - mod;
3345 *nlz_bits_ret = nlz_bits;
3350 absint_numwords_generic(
size_t numbytes,
int nlz_bits_in_msbyte,
size_t word_numbits,
size_t *nlz_bits_ret)
3352 static const BDIGIT char_bit[1] = { CHAR_BIT };
3353 BDIGIT numbytes_bary[bdigit_roomof(
sizeof(numbytes))];
3354 BDIGIT val_numbits_bary[bdigit_roomof(
sizeof(numbytes) + 1)];
3355 BDIGIT nlz_bits_in_msbyte_bary[1];
3356 BDIGIT word_numbits_bary[bdigit_roomof(
sizeof(word_numbits))];
3357 BDIGIT div_bary[numberof(val_numbits_bary) + BIGDIVREM_EXTRA_WORDS];
3358 BDIGIT mod_bary[numberof(word_numbits_bary)];
3359 BDIGIT one[1] = { 1 };
3365 nlz_bits_in_msbyte_bary[0] = nlz_bits_in_msbyte;
3374 bary_unpack(BARY_ARGS(numbytes_bary), &numbytes, 1,
sizeof(numbytes), 0,
3376 BARY_SHORT_MUL(val_numbits_bary, numbytes_bary, char_bit);
3377 if (nlz_bits_in_msbyte)
3378 BARY_SUB(val_numbits_bary, val_numbits_bary, nlz_bits_in_msbyte_bary);
3379 bary_unpack(BARY_ARGS(word_numbits_bary), &word_numbits, 1,
sizeof(word_numbits), 0,
3381 BARY_DIVMOD(div_bary, mod_bary, val_numbits_bary, word_numbits_bary);
3382 if (BARY_ZERO_P(mod_bary)) {
3386 BARY_ADD(div_bary, div_bary, one);
3387 bary_pack(+1, BARY_ARGS(mod_bary), &mod, 1,
sizeof(mod), 0,
3389 nlz_bits = word_numbits - mod;
3391 sign = bary_pack(+1, BARY_ARGS(div_bary), &numwords, 1,
sizeof(numwords), 0,
3395 #if defined __GNUC__ && (__GNUC__ == 4 && __GNUC_MINOR__ == 4)
3400 *nlz_bits_ret = nlz_bits;
3427 int nlz_bits_in_msbyte;
3429 size_t nlz_bits = 0;
3431 if (word_numbits == 0)
3436 if (numbytes <= SIZE_MAX / CHAR_BIT) {
3437 numwords = absint_numwords_small(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits);
3438 if (debug_integer_pack) {
3439 size_t numwords0, nlz_bits0;
3440 numwords0 = absint_numwords_generic(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits0);
3447 numwords = absint_numwords_generic(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits);
3449 if (numwords == (
size_t)-1)
3453 *nlz_bits_ret = nlz_bits;
3491 BDIGIT fixbuf[bdigit_roomof(
sizeof(
long))];
3501 #if SIZEOF_BDIGIT >= SIZEOF_LONG
3506 for (i = 0; i < numberof(fixbuf); i++) {
3507 fixbuf[i] = BIGLO(v);
3513 de = fixbuf + numberof(fixbuf);
3517 de = dp + BIGNUM_LEN(val);
3519 while (dp < de && de[-1] == 0)
3521 while (dp < de && dp[0] == 0)
3593 BDIGIT fixbuf[bdigit_roomof(
sizeof(
long))];
3606 #if SIZEOF_BDIGIT >= SIZEOF_LONG
3611 for (i = 0; i < numberof(fixbuf); i++) {
3612 fixbuf[i] = BIGLO(v);
3618 num_bdigits = numberof(fixbuf);
3621 sign = BIGNUM_POSITIVE_P(val) ? 1 : -1;
3623 num_bdigits = BIGNUM_LEN(val);
3626 return bary_pack(sign, ds, num_bdigits, words, numwords, wordsize, nails, flags);
3681 BDIGIT fixbuf[2] = { 0, 0 };
3683 validate_integer_pack_format(numwords, wordsize, nails, flags,
3694 num_bdigits = integer_unpack_num_bdigits(numwords, wordsize, nails, &nlp_bits);
3696 if (LONG_MAX-1 < num_bdigits)
3703 val = bignew((
long)num_bdigits, 0);
3706 sign = bary_unpack_internal(ds, num_bdigits, words, numwords, wordsize, nails, flags, nlp_bits);
3710 big_extend_carry(val);
3712 else if (num_bdigits == numberof(fixbuf)) {
3713 val = bignew((
long)num_bdigits+1, 0);
3714 MEMCPY(BDIGITS(val), fixbuf, BDIGIT, num_bdigits);
3715 BDIGITS(val)[num_bdigits++] = 1;
3718 ds[num_bdigits++] = 1;
3723 BDIGIT_DBL u = fixbuf[0] + BIGUP(fixbuf[1]);
3728 if (sign < 0 && BDIGIT_MSB(fixbuf[1]) == 0 &&
3730 return LONG2FIX((
long)-(BDIGIT_DBL_SIGNED)u);
3731 val = bignew((
long)num_bdigits, 0 <= sign);
3732 MEMCPY(BDIGITS(val), fixbuf, BDIGIT, num_bdigits);
3736 bary_zero_p(BDIGITS(val), BIGNUM_LEN(val)))
3738 BIGNUM_SET_SIGN(val, 0 <= sign);
3741 return bigtrunc(val);
3742 return bignorm(val);
3745 #define conv_digit(c) (ruby_digit36_to_number_table[(unsigned char)(c)])
3747 NORETURN(
static inline void invalid_radix(
int base));
3748 NORETURN(
static inline void invalid_integer(
VALUE s));
3751 valid_radix_p(
int base)
3753 return (1 < base && base <= 36);
3757 invalid_radix(
int base)
3763 invalid_integer(
VALUE s)
3769 str2big_scan_digits(
const char *s,
const char *str,
int base,
int badcheck,
size_t *num_digits_p, ssize_t *len_p)
3772 size_t num_digits = 0;
3773 const char *digits_start = str;
3774 const char *digits_end = str;
3775 ssize_t
len = *len_p;
3785 if (badcheck && *str ==
'_')
return FALSE;
3787 while ((c = *str++) != 0) {
3790 if (badcheck)
return FALSE;
3793 nondigit = (char) c;
3795 else if ((c = conv_digit(c)) < 0 || c >= base) {
3803 if (
len > 0 && !--
len)
break;
3805 if (badcheck && nondigit)
return FALSE;
3806 if (badcheck &&
len) {
3808 while (*str &&
ISSPACE(*str)) {
3810 if (
len > 0 && !--
len)
break;
3816 *num_digits_p = num_digits;
3817 *len_p = digits_end - digits_start;
3824 const char *digits_start,
3825 const char *digits_end,
3838 num_bdigits = (num_digits / BITSPERDIG) * bits_per_digit + roomof((num_digits % BITSPERDIG) * bits_per_digit, BITSPERDIG);
3839 z = bignew(num_bdigits, sign);
3843 for (p = digits_end; digits_start < p; p--) {
3844 if ((c = conv_digit(p[-1])) < 0)
3846 dd |= (BDIGIT_DBL)c << numbits;
3847 numbits += bits_per_digit;
3848 if (BITSPERDIG <= numbits) {
3851 numbits -= BITSPERDIG;
3857 RUBY_ASSERT((
size_t)(dp - BDIGITS(z)) == num_bdigits);
3865 const char *digits_start,
3866 const char *digits_end,
3879 z = bignew(num_bdigits, sign);
3881 BDIGITS_ZERO(zds, num_bdigits);
3883 for (p = digits_start; p < digits_end; p++) {
3884 if ((c = conv_digit(*p)) < 0)
3890 num += (BDIGIT_DBL)zds[i]*base;
3891 zds[i++] = BIGLO(num);
3909 const char *digits_start,
3910 const char *digits_end,
3913 int digits_per_bdigits_dbl,
3919 BDIGIT *uds, *vds, *tds;
3921 BDIGIT_DBL current_base;
3923 int power_level = 0;
3930 uds =
ALLOCV_N(BDIGIT, tmpuv, 2*num_bdigits);
3931 vds = uds + num_bdigits;
3933 powerv = power_cache_get_power(base, power_level, NULL);
3938 m = digits_per_bdigits_dbl;
3939 if (num_digits < (
size_t)m)
3940 m = (int)num_digits;
3941 for (p = digits_end; digits_start < p; p--) {
3942 if ((c = conv_digit(p[-1])) < 0)
3944 dd = dd + c * current_base;
3945 current_base *= base;
3949 uds[i++] = BIGLO(dd);
3950 uds[i++] = (BDIGIT)BIGDN(dd);
3952 m = digits_per_bdigits_dbl;
3953 if (num_digits < (
size_t)m)
3954 m = (
int)num_digits;
3959 for (unit = 2; unit < num_bdigits; unit *= 2) {
3960 for (i = 0; i < num_bdigits; i += unit*2) {
3961 if (2*unit <= num_bdigits - i) {
3962 bary_mul(vds+i, unit*2, BDIGITS(powerv), BIGNUM_LEN(powerv), uds+i+unit, unit);
3963 bary_add(vds+i, unit*2, vds+i, unit*2, uds+i, unit);
3965 else if (unit <= num_bdigits - i) {
3966 bary_mul(vds+i, num_bdigits-i, BDIGITS(powerv), BIGNUM_LEN(powerv), uds+i+unit, num_bdigits-(i+unit));
3967 bary_add(vds+i, num_bdigits-i, vds+i, num_bdigits-i, uds+i, unit);
3970 MEMCPY(vds+i, uds+i, BDIGIT, num_bdigits-i);
3974 powerv = power_cache_get_power(base, power_level, NULL);
3979 BARY_TRUNC(uds, num_bdigits);
3980 z = bignew(num_bdigits, sign);
3981 MEMCPY(BDIGITS(z), uds, BDIGIT, num_bdigits);
3993 const char *digits_start,
3994 const char *digits_end,
4007 buf =
ALLOCV_N(
char, tmps, num_digits+1);
4009 for (q = digits_start; q < digits_end; q++) {
4010 if (conv_digit(*q) < 0)
4017 mpz_set_str(mz, buf, base);
4019 z = bignew(zn, sign);
4021 bdigits_from_mpz(mz, BDIGITS(z), &count);
4022 BDIGITS_ZERO(zds+count, zn-count);
4032 static VALUE rb_cstr_parse_inum(
const char *str, ssize_t
len,
char **endp,
int base);
4054 VALUE ret = rb_cstr_parse_inum(str, -1, (badcheck ? NULL : &end), base);
4080 rb_int_parse_cstr(
const char *str, ssize_t
len,
char **endp,
size_t *ndigits,
4081 int base,
int flags)
4083 const char *
const s = str;
4091 const char *digits_start, *digits_end;
4092 size_t num_digits = 0;
4094 const ssize_t len0 =
len;
4095 const int badcheck = !endp;
4097 #define ADV(n) do {\
4098 if (len > 0 && len <= (n)) goto bad; \
4102 #define ASSERT_LEN() do {\
4103 RUBY_ASSERT(len != 0); \
4104 if (len0 >= 0) RUBY_ASSERT(s + len0 == str + len); \
4110 if (
len && (flags & RB_INT_PARSE_SIGN)) {
4113 if (str[0] ==
'+') {
4116 else if (str[0] ==
'-') {
4123 if (str[0] ==
'0' &&
len > 1) {
4145 else if (base < -1) {
4152 else if (
len == 1 || !(flags & RB_INT_PARSE_PREFIX)) {
4155 else if (base == 2) {
4156 if (str[0] ==
'0' && (str[1] ==
'b'||str[1] ==
'B')) {
4160 else if (base == 8) {
4161 if (str[0] ==
'0' && (str[1] ==
'o'||str[1] ==
'O')) {
4165 else if (base == 10) {
4166 if (str[0] ==
'0' && (str[1] ==
'd'||str[1] ==
'D')) {
4170 else if (base == 16) {
4171 if (str[0] ==
'0' && (str[1] ==
'x'||str[1] ==
'X')) {
4175 if (!valid_radix_p(base)) {
4176 invalid_radix(base);
4179 num_digits = str - s;
4180 if (*str ==
'0' &&
len != 1) {
4182 const char *end =
len < 0 ? NULL : str +
len;
4184 while ((c = *++str) ==
'0' ||
4185 ((flags & RB_INT_PARSE_UNDERSCORE) && c ==
'_')) {
4194 if (str == end)
break;
4197 if (end)
len = end - str;
4201 if (c < 0 || c >= base) {
4202 if (!badcheck && num_digits) z =
INT2FIX(0);
4206 if (ndigits) *ndigits = num_digits;
4209 const char *end = &str[num_digits];
4210 if (num_digits > 0 && *end ==
'_' && (flags & RB_INT_PARSE_UNDERSCORE))
4212 if (endp) *endp = (
char *)end;
4213 if (ndigits) *ndigits += num_digits;
4215 if (num_digits == 0)
return Qnil;
4216 while (
len < 0 ? *end : end < str +
len) {
4225 long result = -(long)val;
4231 BIGNUM_SET_SIGN(big, sign);
4232 return bignorm(big);
4238 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4240 if (endp) *endp = (
char *)(str +
len);
4241 if (ndigits) *ndigits += num_digits;
4242 digits_end = digits_start +
len;
4245 z = str2big_poweroftwo(sign, digits_start, digits_end, num_digits,
4246 bit_length(base-1));
4249 int digits_per_bdigits_dbl;
4250 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4251 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4254 if (GMP_STR2BIG_DIGITS < num_bdigits) {
4255 z = str2big_gmp(sign, digits_start, digits_end, num_digits,
4260 if (num_bdigits < KARATSUBA_MUL_DIGITS) {
4261 z = str2big_normal(sign, digits_start, digits_end,
4265 z = str2big_karatsuba(sign, digits_start, digits_end, num_digits,
4266 num_bdigits, digits_per_bdigits_dbl, base);
4273 if (endp) *endp = (
char *)str;
4274 if (ndigits) *ndigits = num_digits;
4279 rb_cstr_parse_inum(
const char *str, ssize_t
len,
char **endp,
int base)
4281 return rb_int_parse_cstr(str,
len, endp, NULL, base,
4282 RB_INT_PARSE_DEFAULT);
4286 rb_str_convert_to_inum(
VALUE str,
int base,
int badcheck,
int raise_exception)
4296 ret = rb_cstr_parse_inum(s,
len, (badcheck ? NULL : &end), base);
4299 if (!raise_exception)
return Qnil;
4300 invalid_integer(str);
4310 return rb_str_convert_to_inum(str, base, badcheck, TRUE);
4314 rb_str2big_poweroftwo(
VALUE arg,
int base,
int badcheck)
4317 const char *s, *str;
4318 const char *digits_start, *digits_end;
4323 if (!valid_radix_p(base) || !POW2_P(base)) {
4324 invalid_radix(base);
4337 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4338 invalid_integer(arg);
4339 digits_end = digits_start +
len;
4341 z = str2big_poweroftwo(positive_p, digits_start, digits_end, num_digits,
4342 bit_length(base-1));
4350 rb_str2big_normal(
VALUE arg,
int base,
int badcheck)
4353 const char *s, *str;
4354 const char *digits_start, *digits_end;
4359 int digits_per_bdigits_dbl;
4362 if (!valid_radix_p(base)) {
4363 invalid_radix(base);
4369 if (
len > 0 && *str ==
'-') {
4376 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4377 invalid_integer(arg);
4378 digits_end = digits_start +
len;
4380 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4381 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4383 z = str2big_normal(positive_p, digits_start, digits_end,
4392 rb_str2big_karatsuba(
VALUE arg,
int base,
int badcheck)
4395 const char *s, *str;
4396 const char *digits_start, *digits_end;
4401 int digits_per_bdigits_dbl;
4404 if (!valid_radix_p(base)) {
4405 invalid_radix(base);
4411 if (
len > 0 && *str ==
'-') {
4418 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4419 invalid_integer(arg);
4420 digits_end = digits_start +
len;
4422 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4423 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4425 z = str2big_karatsuba(positive_p, digits_start, digits_end, num_digits,
4426 num_bdigits, digits_per_bdigits_dbl, base);
4435 rb_str2big_gmp(
VALUE arg,
int base,
int badcheck)
4438 const char *s, *str;
4439 const char *digits_start, *digits_end;
4444 int digits_per_bdigits_dbl;
4447 if (!valid_radix_p(base)) {
4448 invalid_radix(base);
4454 if (
len > 0 && *str ==
'-') {
4461 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4462 invalid_integer(arg);
4463 digits_end = digits_start +
len;
4465 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4466 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4468 z = str2big_gmp(positive_p, digits_start, digits_end, num_digits, num_bdigits, base);
4482 VALUE big = bignew(bdigit_roomof(SIZEOF_LONG_LONG), 1);
4483 BDIGIT *digits = BDIGITS(big);
4485 #if SIZEOF_BDIGIT >= SIZEOF_LONG_LONG
4488 for (i = 0; i < bdigit_roomof(SIZEOF_LONG_LONG); i++) {
4489 digits[i] = BIGLO(n);
4494 i = bdigit_roomof(SIZEOF_LONG_LONG);
4495 while (i-- && !digits[i]) ;
4496 BIGNUM_SET_LEN(big, i+1);
4514 big = rb_ull2big(u);
4516 BIGNUM_SET_NEGATIVE_SIGN(big);
4525 return rb_ull2big(n);
4532 return rb_ll2big(n);
4537 #ifdef HAVE_INT128_T
4539 rb_uint128t2big(uint128_t n)
4542 VALUE big = bignew(bdigit_roomof(SIZEOF_INT128_T), 1);
4543 BDIGIT *digits = BDIGITS(big);
4545 for (i = 0; i < bdigit_roomof(SIZEOF_INT128_T); i++) {
4546 digits[i] = BIGLO(RSHIFT(n ,BITSPERDIG*i));
4549 i = bdigit_roomof(SIZEOF_INT128_T);
4550 while (i-- && !digits[i]) ;
4551 BIGNUM_SET_LEN(big, i+1);
4556 rb_int128t2big(int128_t n)
4563 u = 1 + (uint128_t)(-(n + 1));
4569 big = rb_uint128t2big(u);
4571 BIGNUM_SET_NEGATIVE_SIGN(big);
4590 big_shift3(
VALUE x,
int lshift_p,
size_t shift_numdigits,
int shift_numbits)
4599 if (LONG_MAX < shift_numdigits) {
4603 s1 = shift_numdigits;
4605 if ((
size_t)s1 != shift_numdigits)
goto too_big;
4607 if (LONG_MAX/SIZEOF_BDIGIT <= xn+s1)
goto too_big;
4608 z = bignew(xn+s1+1, BIGNUM_SIGN(x));
4610 BDIGITS_ZERO(zds, s1);
4612 zds[xn+s1] = bary_small_lshift(zds+s1, xds, xn, s2);
4617 if (LONG_MAX < shift_numdigits || (
size_t)BIGNUM_LEN(x) <= shift_numdigits) {
4618 if (BIGNUM_POSITIVE_P(x) ||
4619 bary_zero_p(BDIGITS(x), BIGNUM_LEN(x)))
4624 s1 = shift_numdigits;
4626 hibitsx = abs2twocomp(&x, &xn);
4634 bary_small_rshift(zds, xds+s1, zn, s2, hibitsx != 0 ? BDIGMAX : 0);
4635 twocomp2abs_bang(z, hibitsx != 0);
4646 size_t shift_numdigits;
4657 lshift_p = !lshift_p;
4661 if (1 < sign || CHAR_BIT <= lens[1])
4665 if (1 < sign || CHAR_BIT <= lens[1])
4668 shift_numbits = (int)(lens[0] & (BITSPERDIG-1));
4669 shift_numdigits = (lens[0] >> bit_length(BITSPERDIG-1)) |
4670 (lens[1] << (CHAR_BIT*SIZEOF_SIZE_T - bit_length(BITSPERDIG-1)));
4671 return big_shift3(x, lshift_p, shift_numdigits, shift_numbits);
4675 big_lshift(
VALUE x,
unsigned long shift)
4677 long s1 = shift/BITSPERDIG;
4678 int s2 = (int)(shift%BITSPERDIG);
4679 return big_shift3(x, 1, s1, s2);
4683 big_rshift(
VALUE x,
unsigned long shift)
4685 long s1 = shift/BITSPERDIG;
4686 int s2 = (int)(shift%BITSPERDIG);
4687 return big_shift3(x, 0, s1, s2);
4690 #define MAX_BASE36_POWER_TABLE_ENTRIES (SIZEOF_SIZE_T * CHAR_BIT + 1)
4692 static VALUE base36_power_cache[35][MAX_BASE36_POWER_TABLE_ENTRIES];
4693 static size_t base36_numdigits_cache[35][MAX_BASE36_POWER_TABLE_ENTRIES];
4696 power_cache_init(
void)
4701 power_cache_get_power(
int base,
int power_level,
size_t *numdigits_ret)
4717 if (MAX_BASE36_POWER_TABLE_ENTRIES <= power_level)
4718 rb_bug(
"too big power number requested: maxpow_in_bdigit_dbl(%d)**(2**%d)", base, power_level);
4720 VALUE power = base36_power_cache[base - 2][power_level];
4723 if (power_level == 0) {
4725 BDIGIT_DBL dd = maxpow_in_bdigit_dbl(base, &numdigits0);
4726 power = bignew(2, 1);
4727 bdigitdbl2bary(BDIGITS(power), 2, dd);
4728 numdigits = numdigits0;
4731 power = bigtrunc(bigsq(power_cache_get_power(base, power_level - 1, &numdigits)));
4735 base36_power_cache[base - 2][power_level] = power;
4736 base36_numdigits_cache[base - 2][power_level] = numdigits;
4737 rb_vm_register_global_object(power);
4740 *numdigits_ret = base36_numdigits_cache[base - 2][power_level];
4748 int hbase2_numdigits;
4756 if (LONG_MAX-1 <
len)
4765 big2str_2bdigits(
struct big2str_struct *b2s, BDIGIT *xds,
size_t xn,
size_t taillen)
4769 char buf[SIZEOF_BDIGIT_DBL*CHAR_BIT], *p;
4770 int beginning = !b2s->ptr;
4774 num = bary2bdigitdbl(xds, xn);
4782 BDIGIT_DBL idx = num % b2s->base;
4784 p[--j] = ruby_digitmap[idx];
4786 len =
sizeof(buf) - j;
4787 big2str_alloc(b2s,
len + taillen);
4792 j = b2s->hbase2_numdigits;
4794 BDIGIT_DBL idx = num % b2s->base;
4796 p[--j] = ruby_digitmap[idx];
4798 len = b2s->hbase2_numdigits;
4804 big2str_karatsuba(
struct big2str_struct *b2s, BDIGIT *xds,
size_t xn,
size_t wn,
4805 int power_level,
size_t taillen)
4808 size_t half_numdigits, lower_numdigits;
4809 int lower_power_level;
4834 if (xn == 0 || bary_zero_p(xds, xn)) {
4837 power_cache_get_power(b2s->base, power_level, &
len);
4838 memset(b2s->ptr,
'0',
len);
4844 if (power_level == 0) {
4845 big2str_2bdigits(b2s, xds, xn, taillen);
4849 lower_power_level = power_level-1;
4850 b = power_cache_get_power(b2s->base, lower_power_level, &lower_numdigits);
4854 half_numdigits = lower_numdigits;
4856 while (0 < lower_power_level &&
4858 (xn == bn && bary_cmp(xds, xn, bds, bn) < 0))) {
4859 lower_power_level--;
4860 b = power_cache_get_power(b2s->base, lower_power_level, &lower_numdigits);
4865 if (lower_power_level == 0 &&
4867 (xn == bn && bary_cmp(xds, xn, bds, bn) < 0))) {
4869 len = half_numdigits * 2 - lower_numdigits;
4870 memset(b2s->ptr,
'0',
len);
4873 big2str_2bdigits(b2s, xds, xn, taillen);
4881 if (lower_power_level != power_level-1 && b2s->ptr) {
4882 len = (half_numdigits - lower_numdigits) * 2;
4883 memset(b2s->ptr,
'0',
len);
4887 shift = nlz(bds[bn-1]);
4889 qn = xn + BIGDIVREM_EXTRA_WORDS;
4894 tds = (BDIGIT *)bds;
4902 bary_small_lshift(tds, bds, bn, shift);
4903 xds[xn] = bary_small_lshift(xds, xds, xn, shift);
4906 bigdivrem_restoring(xds, qn, tds, bn);
4915 bary_small_rshift(rds, rds, rn, shift, 0);
4918 BARY_TRUNC(qds, qn);
4920 big2str_karatsuba(b2s, qds, qn, xn+wn - (rn+qn), lower_power_level, lower_numdigits+taillen);
4921 BARY_TRUNC(rds, rn);
4922 big2str_karatsuba(b2s, rds, rn, xn+wn - rn, lower_power_level, taillen);
4927 big2str_base_poweroftwo(
VALUE x,
int base)
4929 int word_numbits = ffs(base) - 1;
4934 if (BIGNUM_NEGATIVE_P(x)) {
4935 if (LONG_MAX-1 < numwords)
4939 *
ptr++ = BIGNUM_POSITIVE_P(x) ?
'+' :
'-';
4942 if (LONG_MAX < numwords)
4949 while (0 < numwords) {
4950 *
ptr = ruby_digitmap[*(
unsigned char *)
ptr];
4958 rb_big2str_poweroftwo(
VALUE x,
int base)
4960 return big2str_base_poweroftwo(x, base);
4964 big2str_generic(
VALUE x,
int base)
4974 BARY_TRUNC(xds, xn);
4980 if (!valid_radix_p(base))
4981 invalid_radix(base);
4983 if (xn >= LONG_MAX/BITSPERDIG) {
4988 power = power_cache_get_power(base, power_level, NULL);
4989 while (power_level < MAX_BASE36_POWER_TABLE_ENTRIES &&
4990 (
size_t)BIGNUM_LEN(power) <= (xn+1)/2) {
4992 power = power_cache_get_power(base, power_level, NULL);
4994 RUBY_ASSERT(power_level != MAX_BASE36_POWER_TABLE_ENTRIES);
4996 if ((
size_t)BIGNUM_LEN(power) <= xn) {
5010 b2s_data.negative = BIGNUM_NEGATIVE_P(x);
5011 b2s_data.base = base;
5012 b2s_data.hbase2 = maxpow_in_bdigit_dbl(base, &b2s_data.hbase2_numdigits);
5014 b2s_data.result =
Qnil;
5015 b2s_data.ptr = NULL;
5017 if (power_level == 0) {
5018 big2str_2bdigits(&b2s_data, xds, xn, 0);
5024 wn = power_level * BIGDIVREM_EXTRA_WORDS + BIGNUM_LEN(power);
5025 wds =
ALLOCV_N(BDIGIT, tmpw, xn + wn);
5026 MEMCPY(wds, xds, BDIGIT, xn);
5027 big2str_karatsuba(&b2s_data, wds, xn, wn, power_level, 0);
5033 *b2s_data.ptr =
'\0';
5037 return b2s_data.result;
5041 rb_big2str_generic(
VALUE x,
int base)
5043 return big2str_generic(x, base);
5048 big2str_gmp(
VALUE x,
int base)
5053 BDIGIT *xds = BDIGITS(x);
5054 size_t xn = BIGNUM_LEN(x);
5057 bdigits_to_mpz(mx, xds, xn);
5059 size = mpz_sizeinbase(mx, base);
5061 if (BIGNUM_NEGATIVE_P(x)) {
5080 rb_big2str_gmp(
VALUE x,
int base)
5082 return big2str_gmp(x, base);
5087 rb_big2str1(
VALUE x,
int base)
5099 BARY_TRUNC(xds, xn);
5105 if (!valid_radix_p(base))
5106 invalid_radix(base);
5108 if (xn >= LONG_MAX/BITSPERDIG) {
5114 return big2str_base_poweroftwo(x, base);
5118 if (GMP_BIG2STR_DIGITS < xn) {
5119 return big2str_gmp(x, base);
5123 return big2str_generic(x, base);
5129 return rb_big2str1(x, base);
5132 static unsigned long
5135 #if SIZEOF_LONG > SIZEOF_BDIGIT
5138 size_t len = BIGNUM_LEN(x);
5144 if (BIGSIZE(x) >
sizeof(
long)) {
5148 #if SIZEOF_LONG <= SIZEOF_BDIGIT
5149 num = (
unsigned long)ds[0];
5152 for (i = 0; i <
len; i++) {
5154 num += (
unsigned long)ds[
len - i - 1];
5163 unsigned long num = big2ulong(x,
"unsigned long");
5165 if (BIGNUM_POSITIVE_P(x)) {
5169 if (num <= 1+(
unsigned long)(-(LONG_MIN+1)))
5170 return -(long)(num-1)-1;
5178 unsigned long num = big2ulong(x,
"long");
5180 if (BIGNUM_POSITIVE_P(x)) {
5181 if (num <= LONG_MAX)
5185 if (num <= 1+(
unsigned long)(-(LONG_MIN+1)))
5186 return -(long)(num-1)-1;
5196 #if SIZEOF_LONG_LONG > SIZEOF_BDIGIT
5199 size_t len = BIGNUM_LEN(x);
5201 BDIGIT *ds = BDIGITS(x);
5205 if (BIGSIZE(x) > SIZEOF_LONG_LONG)
5207 #if SIZEOF_LONG_LONG <= SIZEOF_BDIGIT
5211 for (i = 0; i <
len; i++) {
5213 num += ds[
len - i - 1];
5222 unsigned LONG_LONG num = big2ull(x,
"unsigned long long");
5224 if (BIGNUM_POSITIVE_P(x)) {
5228 if (num <= 1+(
unsigned LONG_LONG)(-(LLONG_MIN+1)))
5237 unsigned LONG_LONG num = big2ull(x,
"long long");
5239 if (BIGNUM_POSITIVE_P(x)) {
5240 if (num <= LLONG_MAX)
5244 if (num <= 1+(
unsigned LONG_LONG)(-(LLONG_MIN+1)))
5259 double u = (d < 0)?-d:d;
5269 u /= (double)(BIGRAD);
5272 z = bignew(i, d>=0);
5273 digits = BDIGITS(z);
5287 return bignorm(dbl2big(d));
5294 long i = (bigtrunc(x), BIGNUM_LEN(x)), lo = 0, bits;
5295 BDIGIT *ds = BDIGITS(x), dl;
5298 bits = i * BITSPERDIG - nlz(ds[i-1]);
5299 if (bits > DBL_MANT_DIG+DBL_MAX_EXP) {
5303 if (bits > DBL_MANT_DIG+1)
5304 lo = (bits -= DBL_MANT_DIG+1) / BITSPERDIG;
5308 d = ds[i] + BIGRAD*d;
5311 if (bits && (dl & ((BDIGIT)1 << (bits %= BITSPERDIG)))) {
5312 int carry = (dl & ~(BDIGMAX << bits)) != 0;
5320 BDIGIT mask = BDIGMAX;
5332 if (lo > INT_MAX / BITSPERDIG)
5334 else if (lo < INT_MIN / BITSPERDIG)
5337 d = ldexp(d, (
int)(lo * BITSPERDIG));
5341 if (BIGNUM_NEGATIVE_P(x)) d = -d;
5348 double d = big2dbl(x);
5370 if (yd > 0.0)
return INT2FIX(-1);
5375 #if SIZEOF_LONG * CHAR_BIT < DBL_MANT_DIG
5403 if (yf == 0.0 || rel !=
INT2FIX(0))
5410 #if SIZEOF_LONG * CHAR_BIT >= DBL_MANT_DIG
5411 COMPILER_WARNING_PUSH
5412 #if __has_warning("-Wimplicit-int-float-conversion")
5413 COMPILER_WARNING_IGNORED(-Wimplicit-
int-
float-conversion)
5415 static const double LONG_MAX_as_double = LONG_MAX;
5416 COMPILER_WARNING_POP
5431 #if SIZEOF_LONG * CHAR_BIT < DBL_MANT_DIG
5433 return RBOOL(xd == yd);
5436 if (yi < LONG_MIN || LONG_MAX_as_double <= yi)
5440 return RBOOL(xn == yn);
5457 if (sx < sy)
return INT2FIX(-1);
5461 else if (RB_BIGNUM_TYPE_P(y)) {
5462 if (BIGNUM_SIGN(x) == BIGNUM_SIGN(y)) {
5463 int cmp = bary_cmp(BDIGITS(x), BIGNUM_LEN(x), BDIGITS(y), BIGNUM_LEN(y));
5464 return INT2FIX(BIGNUM_SIGN(x) ? cmp : -cmp);
5468 return rb_integer_float_cmp(x, y);
5473 return INT2FIX(BIGNUM_SIGN(x) ? 1 : -1);
5493 rel = rb_integer_float_cmp(x, y);
5498 case big_op_gt:
id =
'>';
break;
5499 case big_op_ge:
id = idGE;
break;
5500 case big_op_lt:
id =
'<';
break;
5501 case big_op_le:
id = idLE;
break;
5510 case big_op_gt:
return RBOOL(n > 0);
5511 case big_op_ge:
return RBOOL(n >= 0);
5512 case big_op_lt:
return RBOOL(n < 0);
5513 case big_op_le:
return RBOOL(n <= 0);
5521 return big_op(x, y, big_op_gt);
5527 return big_op(x, y, big_op_ge);
5533 return big_op(x, y, big_op_lt);
5539 return big_op(x, y, big_op_le);
5557 return RBOOL(bignorm(x) == y);
5559 else if (RB_BIGNUM_TYPE_P(y)) {
5562 return rb_integer_float_eq(x, y);
5567 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y))
return Qfalse;
5568 if (BIGNUM_LEN(x) != BIGNUM_LEN(y))
return Qfalse;
5569 return RBOOL(
MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,BIGNUM_LEN(y)) == 0);
5575 if (!RB_BIGNUM_TYPE_P(y))
return Qfalse;
5576 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y))
return Qfalse;
5577 if (BIGNUM_LEN(x) != BIGNUM_LEN(y))
return Qfalse;
5578 return RBOOL(
MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,BIGNUM_LEN(y)) == 0);
5582 rb_big_uminus(
VALUE x)
5592 rb_big_comp(
VALUE x)
5595 BDIGIT *ds = BDIGITS(z);
5596 long n = BIGNUM_LEN(z);
5600 if (BIGNUM_POSITIVE_P(z)) {
5601 if (bary_add_one(ds, n)) {
5602 big_extend_carry(z);
5604 BIGNUM_SET_NEGATIVE_SIGN(z);
5608 if (bary_add_one(ds, n))
5611 BIGNUM_SET_POSITIVE_SIGN(z);
5621 BDIGIT *xds, *yds, *zds;
5626 zn = xn < yn ? yn : xn;
5634 if (bary_sub(zds, zn, xds, xn, yds, yn)) {
5635 bary_2comp(zds, zn);
5636 BIGNUM_SET_NEGATIVE_SIGN(z);
5645 bigsub_int(
VALUE x,
long y0)
5650 BDIGIT_DBL_SIGNED num;
5661 #if SIZEOF_BDIGIT < SIZEOF_LONG
5662 if (zn < bdigit_roomof(SIZEOF_LONG))
5663 zn = bdigit_roomof(SIZEOF_LONG);
5665 z = bignew(zn, BIGNUM_SIGN(x));
5668 #if SIZEOF_BDIGIT >= SIZEOF_LONG
5670 num = (BDIGIT_DBL_SIGNED)xds[0] - y;
5671 if (xn == 1 && num < 0) {
5673 zds[0] = (BDIGIT)-num;
5677 zds[0] = BIGLO(num);
5685 for (i=0; i < xn; i++) {
5686 if (y == 0)
goto y_is_zero_x;
5687 num += (BDIGIT_DBL_SIGNED)xds[i] - BIGLO(y);
5688 zds[i] = BIGLO(num);
5692 for (; i < zn; i++) {
5693 if (y == 0)
goto y_is_zero_z;
5695 zds[i] = BIGLO(num);
5702 for (; i < xn; i++) {
5704 if (num == 0)
goto num_is_zero_x;
5706 zds[i] = BIGLO(num);
5709 #if SIZEOF_BDIGIT < SIZEOF_LONG
5710 for (; i < zn; i++) {
5712 if (num == 0)
goto num_is_zero_z;
5713 zds[i] = BIGLO(num);
5719 for (; i < xn; i++) {
5723 #if SIZEOF_BDIGIT < SIZEOF_LONG
5724 for (; i < zn; i++) {
5742 bigadd_int(
VALUE x,
long y)
5757 #if SIZEOF_BDIGIT < SIZEOF_LONG
5758 if (zn < bdigit_roomof(SIZEOF_LONG))
5759 zn = bdigit_roomof(SIZEOF_LONG);
5763 z = bignew(zn, BIGNUM_SIGN(x));
5766 #if SIZEOF_BDIGIT >= SIZEOF_LONG
5767 num = (BDIGIT_DBL)xds[0] + y;
5768 zds[0] = BIGLO(num);
5776 for (i=0; i < xn; i++) {
5777 if (y == 0)
goto y_is_zero_x;
5778 num += (BDIGIT_DBL)xds[i] + BIGLO(y);
5779 zds[i] = BIGLO(num);
5783 for (; i < zn; i++) {
5784 if (y == 0)
goto y_is_zero_z;
5786 zds[i] = BIGLO(num);
5794 for (;i < xn; i++) {
5796 if (num == 0)
goto num_is_zero_x;
5797 num += (BDIGIT_DBL)xds[i];
5798 zds[i] = BIGLO(num);
5801 for (; i < zn; i++) {
5803 if (num == 0)
goto num_is_zero_z;
5804 zds[i] = BIGLO(num);
5809 for (;i < xn; i++) {
5813 for (; i < zn; i++) {
5830 sign = (sign == BIGNUM_SIGN(y));
5831 if (BIGNUM_SIGN(x) != sign) {
5832 if (sign)
return bigsub(y, x);
5833 return bigsub(x, y);
5836 if (BIGNUM_LEN(x) > BIGNUM_LEN(y)) {
5837 len = BIGNUM_LEN(x) + 1;
5840 len = BIGNUM_LEN(y) + 1;
5842 z = bignew(
len, sign);
5844 bary_add(BDIGITS(z), BIGNUM_LEN(z),
5845 BDIGITS(x), BIGNUM_LEN(x),
5846 BDIGITS(y), BIGNUM_LEN(y));
5858 if ((n > 0) != BIGNUM_SIGN(x)) {
5862 return bigsub_int(x, n);
5867 return bigadd_int(x, n);
5869 else if (RB_BIGNUM_TYPE_P(y)) {
5870 return bignorm(bigadd(x, y, 1));
5887 if ((n > 0) != BIGNUM_SIGN(x)) {
5891 return bigadd_int(x, n);
5896 return bigsub_int(x, n);
5898 else if (RB_BIGNUM_TYPE_P(y)) {
5899 return bignorm(bigadd(x, y, 0));
5924 if (xn < NAIVE_MUL_DIGITS)
5925 bary_sq_fast(zds, zn, xds, xn);
5927 bary_mul(zds, zn, xds, xn, xds, xn);
5938 BDIGIT *xds, *yds, *zds;
5947 z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
5953 bary_mul(zds, zn, xds, xn, yds, yn);
5966 else if (RB_BIGNUM_TYPE_P(y)) {
5975 return bignorm(bigmul0(x, y));
5981 long xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y);
5983 BDIGIT *xds, *yds, *zds;
5991 BARY_TRUNC(yds, yn);
5996 BARY_TRUNC(xds, xn);
5998 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1])) {
6000 if (modp) *modp = x;
6005 z = bignew(xn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6007 dd = bigdivrem_single(zds, xds, xn, dd);
6010 BIGNUM_SET_SIGN(*modp, BIGNUM_SIGN(x));
6012 if (divp) *divp = z;
6015 if (xn == 2 && yn == 2) {
6016 BDIGIT_DBL x0 = bary2bdigitdbl(xds, 2);
6017 BDIGIT_DBL y0 = bary2bdigitdbl(yds, 2);
6018 BDIGIT_DBL q0 = x0 / y0;
6019 BDIGIT_DBL r0 = x0 % y0;
6021 z = bignew(bdigit_roomof(
sizeof(BDIGIT_DBL)), BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6024 zds[1] = BIGLO(BIGDN(q0));
6028 z = bignew(bdigit_roomof(
sizeof(BDIGIT_DBL)), BIGNUM_SIGN(x));
6031 zds[1] = BIGLO(BIGDN(r0));
6038 qn = xn + BIGDIVREM_EXTRA_WORDS;
6039 q = bignew(qn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6049 r = bignew(rn, BIGNUM_SIGN(x));
6057 bary_divmod_branch(qds, qn, rds, rn, xds, xn, yds, yn);
6076 bigdivrem(x, y, divp, &mod);
6077 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y) && !BIGZEROP(mod)) {
6078 if (divp) *divp = bigadd(*divp,
rb_int2big(1), 0);
6079 if (modp) *modp = bigadd(mod, y, 1);
6095 else if (RB_BIGNUM_TYPE_P(y)) {
6100 return rb_flo_div_flo(
DBL2NUM(dx), y);
6106 v = rb_big_divide(x, y,
'/');
6113 bigdivmod(x, y, &z, 0);
6121 return rb_big_divide(x, y,
'/');
6127 return rb_big_divide(x, y, idDiv);
6138 else if (!RB_BIGNUM_TYPE_P(y)) {
6141 bigdivmod(x, y, 0, &z);
6154 else if (!RB_BIGNUM_TYPE_P(y)) {
6157 bigdivrem(x, y, 0, &z);
6170 else if (!RB_BIGNUM_TYPE_P(y)) {
6173 bigdivmod(x, y, &div, &mod);
6179 big_shift(
VALUE x,
long n)
6182 return big_lshift(x, 1+(
unsigned long)(-(n+1)));
6184 return big_rshift(x, (
unsigned long)n);
6188 enum {DBL_BIGDIG = ((DBL_MANT_DIG + BITSPERDIG) / BITSPERDIG)};
6198 ex = l * BITSPERDIG - nlz(BDIGITS(x)[l-1]);
6199 ex -= 2 * DBL_BIGDIG * BITSPERDIG;
6200 if (ex > BITSPERDIG) ex -= BITSPERDIG;
6201 else if (ex > 0) ex = 0;
6202 if (ex) x = big_shift(x, ex);
6204 bigdivrem(x, y, &z, 0);
6206 #if SIZEOF_LONG > SIZEOF_INT
6209 if (l > INT_MAX)
return HUGE_VAL;
6210 if (l < INT_MIN)
return 0.0;
6213 return ldexp(big2dbl(z), (
int)l);
6222 ey = l * BITSPERDIG - nlz(BDIGITS(y)[l-1]);
6223 ey -= DBL_BIGDIG * BITSPERDIG;
6224 if (ey) y = big_shift(y, ey);
6225 return big_fdiv(x, y, ey);
6232 y = dbl2big(ldexp(frexp(
RFLOAT_VALUE(y), &i), DBL_MANT_DIG));
6233 return big_fdiv(x, y, i - DBL_MANT_DIG);
6248 else if (RB_BIGNUM_TYPE_P(y)) {
6249 return big_fdiv_int(x, y);
6256 return big_fdiv_float(x, y);
6268 return DBL2NUM(rb_big_fdiv_double(x, y));
6279 if (y ==
INT2FIX(1))
return x;
6282 if ((BIGNUM_NEGATIVE_P(x) && !BIGZEROP(x))) {
6283 return rb_dbl_complex_new_polar_pi(pow(-
rb_big2dbl(x), d), d);
6286 else if (RB_BIGNUM_TYPE_P(y)) {
6290 rb_warn(
"in a**b, b may be too big");
6307 const size_t BIGLEN_LIMIT = 32*1024*1024;
6309 if (xbits == (
size_t)-1 ||
6310 (xbits > BIGLEN_LIMIT) ||
6311 (xbits * yy > BIGLEN_LIMIT)) {
6312 rb_warn(
"in a**b, b may be too big");
6316 for (mask =
FIXNUM_MAX + 1; mask; mask >>= 1) {
6317 if (z) z = bigsq(z);
6319 z = z ? bigtrunc(bigmul0(z, x)) : x;
6333 bigand_int(
VALUE x,
long xn, BDIGIT hibitsx,
long y)
6341 if (y == 0)
return INT2FIX(0);
6342 if (xn == 0)
return hibitsx ?
LONG2NUM(y) : 0;
6343 hibitsy = 0 <= y ? 0 : BDIGMAX;
6345 #if SIZEOF_BDIGIT >= SIZEOF_LONG
6353 #if SIZEOF_BDIGIT < SIZEOF_LONG
6354 if (hibitsx && zn < bdigit_roomof(SIZEOF_LONG))
6355 zn = bdigit_roomof(SIZEOF_LONG);
6361 #if SIZEOF_BDIGIT >= SIZEOF_LONG
6363 zds[0] = xds[0] & BIGLO(y);
6365 for (i=0; i < xn; i++) {
6366 if (y == 0 || y == -1)
break;
6367 zds[i] = xds[i] & BIGLO(y);
6370 for (; i < zn; i++) {
6371 if (y == 0 || y == -1)
break;
6372 zds[i] = hibitsx & BIGLO(y);
6376 for (;i < xn; i++) {
6377 zds[i] = xds[i] & hibitsy;
6379 for (;i < zn; i++) {
6380 zds[i] = hibitsx & hibitsy;
6382 twocomp2abs_bang(z, hibitsx && hibitsy);
6391 BDIGIT *ds1, *ds2, *zds;
6392 long i, xn, yn, n1, n2;
6393 BDIGIT hibitsx, hibitsy;
6394 BDIGIT hibits1, hibits2;
6403 hibitsx = abs2twocomp(&x, &xn);
6405 return bigand_int(x, xn, hibitsx,
FIX2LONG(y));
6407 hibitsy = abs2twocomp(&y, &yn);
6409 tmpv = x; x = y; y = tmpv;
6410 tmpn = xn; xn = yn; yn = tmpn;
6411 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6426 for (i=0; i<n1; i++) {
6427 zds[i] = ds1[i] & ds2[i];
6430 zds[i] = hibits1 & ds2[i];
6432 twocomp2abs_bang(z, hibits1 && hibits2);
6439 bigor_int(
VALUE x,
long xn, BDIGIT hibitsx,
long y)
6447 if (y == -1)
return INT2FIX(-1);
6449 hibitsy = 0 <= y ? 0 : BDIGMAX;
6453 #if SIZEOF_BDIGIT < SIZEOF_LONG
6454 if (zn < bdigit_roomof(SIZEOF_LONG))
6455 zn = bdigit_roomof(SIZEOF_LONG);
6460 #if SIZEOF_BDIGIT >= SIZEOF_LONG
6462 zds[0] = xds[0] | BIGLO(y);
6464 goto y_is_fixed_point;
6467 for (i=0; i < xn; i++) {
6468 if (y == 0 || y == -1)
goto y_is_fixed_point;
6469 zds[i] = xds[i] | BIGLO(y);
6474 for (; i < zn; i++) {
6475 if (y == 0 || y == -1)
goto y_is_fixed_point;
6485 for (; i < xn; i++) {
6490 for (; i < zn; i++) {
6496 for (; i < zn; i++) {
6501 twocomp2abs_bang(z, hibitsx || hibitsy);
6510 BDIGIT *ds1, *ds2, *zds;
6511 long i, xn, yn, n1, n2;
6512 BDIGIT hibitsx, hibitsy;
6513 BDIGIT hibits1, hibits2;
6522 hibitsx = abs2twocomp(&x, &xn);
6524 return bigor_int(x, xn, hibitsx,
FIX2LONG(y));
6526 hibitsy = abs2twocomp(&y, &yn);
6528 tmpv = x; x = y; y = tmpv;
6529 tmpn = xn; xn = yn; yn = tmpn;
6530 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6545 for (i=0; i<n1; i++) {
6546 zds[i] = ds1[i] | ds2[i];
6549 zds[i] = hibits1 | ds2[i];
6551 twocomp2abs_bang(z, hibits1 || hibits2);
6558 bigxor_int(
VALUE x,
long xn, BDIGIT hibitsx,
long y)
6566 hibitsy = 0 <= y ? 0 : BDIGMAX;
6569 #if SIZEOF_BDIGIT < SIZEOF_LONG
6570 if (zn < bdigit_roomof(SIZEOF_LONG))
6571 zn = bdigit_roomof(SIZEOF_LONG);
6576 #if SIZEOF_BDIGIT >= SIZEOF_LONG
6578 zds[0] = xds[0] ^ BIGLO(y);
6580 for (i = 0; i < xn; i++) {
6581 zds[i] = xds[i] ^ BIGLO(y);
6584 for (; i < zn; i++) {
6585 zds[i] = hibitsx ^ BIGLO(y);
6589 for (; i < xn; i++) {
6590 zds[i] = xds[i] ^ hibitsy;
6592 for (; i < zn; i++) {
6593 zds[i] = hibitsx ^ hibitsy;
6595 twocomp2abs_bang(z, (hibitsx ^ hibitsy) != 0);
6604 BDIGIT *ds1, *ds2, *zds;
6605 long i, xn, yn, n1, n2;
6606 BDIGIT hibitsx, hibitsy;
6607 BDIGIT hibits1, hibits2;
6616 hibitsx = abs2twocomp(&x, &xn);
6618 return bigxor_int(x, xn, hibitsx,
FIX2LONG(y));
6620 hibitsy = abs2twocomp(&y, &yn);
6622 tmpv = x; x = y; y = tmpv;
6623 tmpn = xn; xn = yn; yn = tmpn;
6624 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6636 for (i=0; i<n1; i++) {
6637 zds[i] = ds1[i] ^ ds2[i];
6640 zds[i] = hibitsx ^ ds2[i];
6642 twocomp2abs_bang(z, (hibits1 ^ hibits2) != 0);
6652 size_t shift_numdigits;
6658 unsigned long shift;
6665 shift = 1+(
unsigned long)(-(l+1));
6667 shift_numbits = (int)(shift & (BITSPERDIG-1));
6668 shift_numdigits = shift >> bit_length(BITSPERDIG-1);
6669 return bignorm(big_shift3(x, lshift_p, shift_numdigits, shift_numbits));
6671 else if (RB_BIGNUM_TYPE_P(y)) {
6672 return bignorm(big_shift2(x, 1, y));
6682 size_t shift_numdigits;
6688 unsigned long shift;
6695 shift = 1+(
unsigned long)(-(l+1));
6697 shift_numbits = (int)(shift & (BITSPERDIG-1));
6698 shift_numdigits = shift >> bit_length(BITSPERDIG-1);
6699 return bignorm(big_shift3(x, lshift_p, shift_numdigits, shift_numbits));
6701 else if (RB_BIGNUM_TYPE_P(y)) {
6702 return bignorm(big_shift2(x, 0, y));
6717 if (RB_BIGNUM_TYPE_P(y)) {
6718 if (BIGNUM_NEGATIVE_P(y))
6721 if (BIGSIZE(y) >
sizeof(
size_t)) {
6724 #if SIZEOF_SIZE_T <= SIZEOF_LONG
6725 shift = big2ulong(y,
"long");
6727 shift = big2ull(y,
"long long");
6735 s1 = shift/BITSPERDIG;
6736 s2 = shift%BITSPERDIG;
6737 bit = (BDIGIT)1 << s2;
6739 if (s1 >= BIGNUM_LEN(x))
6743 if (BIGNUM_POSITIVE_P(x))
6745 if (xds[s1] & (bit-1))
6747 for (i = 0; i < s1; i++)
6754 rb_big_hash(
VALUE x)
6758 hash =
rb_memhash(BDIGITS(x),
sizeof(BDIGIT)*BIGNUM_LEN(x)) ^ BIGNUM_SIGN(x);
6793 if (BIGNUM_NEGATIVE_P(x)) {
6795 BIGNUM_SET_POSITIVE_SIGN(x);
6803 return BIGNUM_SIGN(x);
6807 rb_big_size(
VALUE big)
6809 return BIGSIZE(big);
6813 rb_big_size_m(
VALUE big)
6819 rb_big_bit_length(
VALUE big)
6824 static const BDIGIT char_bit[1] = { CHAR_BIT };
6825 BDIGIT numbytes_bary[bdigit_roomof(
sizeof(
size_t))];
6827 BDIGIT result_bary[bdigit_roomof(
sizeof(
size_t)+1)];
6835 if (nlz_bits != CHAR_BIT-1) {
6844 if (numbytes <= SIZE_MAX / CHAR_BIT) {
6845 return SIZET2NUM(numbytes * CHAR_BIT - nlz_bits);
6848 nlz_bary[0] = nlz_bits;
6850 bary_unpack(BARY_ARGS(numbytes_bary), &numbytes, 1,
sizeof(numbytes), 0,
6852 BARY_SHORT_MUL(result_bary, numbytes_bary, char_bit);
6853 BARY_SUB(result_bary, result_bary, nlz_bary);
6860 rb_big_odd_p(
VALUE num)
6862 return RBOOL(BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1);
6866 rb_big_even_p(
VALUE num)
6868 if (BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1) {
6874 unsigned long rb_ulong_isqrt(
unsigned long);
6875 #if SIZEOF_BDIGIT*2 > SIZEOF_LONG
6876 BDIGIT rb_bdigit_dbl_isqrt(BDIGIT_DBL);
6877 # ifdef ULL_TO_DOUBLE
6878 # define BDIGIT_DBL_TO_DOUBLE(n) ULL_TO_DOUBLE(n)
6881 # define rb_bdigit_dbl_isqrt(x) (BDIGIT)rb_ulong_isqrt(x)
6883 #ifndef BDIGIT_DBL_TO_DOUBLE
6884 # define BDIGIT_DBL_TO_DOUBLE(n) (double)(n)
6888 rb_big_isqrt(
VALUE n)
6890 BDIGIT *nds = BDIGITS(n);
6891 size_t len = BIGNUM_LEN(n);
6894 BDIGIT sq = rb_bdigit_dbl_isqrt(bary2bdigitdbl(nds,
len));
6895 #if SIZEOF_BDIGIT > SIZEOF_LONG
6902 size_t shift =
FIX2LONG(rb_big_bit_length(n)) / 4;
6906 x = rb_int_plus(rb_int_lshift(x,
SIZET2NUM(shift - 1)), rb_int_idiv(rb_int_rshift(n,
SIZET2NUM(shift + 1)), x));
6907 VALUE xx = rb_int_mul(x, x);
6908 while (rb_int_gt(xx, n)) {
6909 xx = rb_int_minus(xx, rb_int_minus(rb_int_plus(x, x),
INT2FIX(1)));
6910 x = rb_int_minus(x,
INT2FIX(1));
6918 bary_powm_gmp(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn,
const BDIGIT *mds,
size_t mn)
6926 bdigits_to_mpz(x, xds, xn);
6927 bdigits_to_mpz(y, yds, yn);
6928 bdigits_to_mpz(m, mds, mn);
6929 mpz_powm(z, x, y, m);
6930 bdigits_from_mpz(z, zds, &count);
6931 BDIGITS_ZERO(zds+count, zn-count);
6944 size_t xn, yn, mn, zn;
6958 bary_powm_gmp(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, BDIGITS(m), mn);
6959 if (nega_flg & BIGNUM_POSITIVE_P(z)) {
6971 if (
RTEST(rb_int_odd_p(y))) {
6972 tmp = rb_int_mul(tmp, x);
6973 tmp = rb_int_modulo(tmp, m);
6975 x = rb_int_mul(x, x);
6976 x = rb_int_modulo(x, m);
6978 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
6980 tmp = rb_int_mul(tmp, x);
6981 tmp = rb_int_modulo(tmp, m);
6983 x = rb_int_mul(x, x);
6984 x = rb_int_modulo(x, m);
6987 if (nega_flg && rb_int_positive_p(tmp)) {
6988 tmp = rb_int_minus(tmp, m);
6999 int_pow_tmp1(
VALUE x,
VALUE y,
long mm,
int nega_flg)
7006 if (
RTEST(rb_int_odd_p(y))) {
7007 tmp = (tmp * xx) % mm;
7009 xx = (xx * xx) % mm;
7011 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7013 tmp = (tmp * xx) % mm;
7015 xx = (xx * xx) % mm;
7018 if (nega_flg && tmp) {
7025 int_pow_tmp2(
VALUE x,
VALUE y,
long mm,
int nega_flg)
7033 # define MUL_MODULO(a, b, c) (long)(((DLONG)(a) * (DLONG)(b)) % (c))
7038 # define MUL_MODULO(a, b, c) rb_int_modulo(rb_fix_mul_fix((a), (b)), (c))
7042 if (
RTEST(rb_int_odd_p(y))) {
7043 tmp2 = MUL_MODULO(tmp2, xx, m);
7045 xx = MUL_MODULO(xx, xx, m);
7047 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7049 tmp2 = MUL_MODULO(tmp2, xx, m);
7051 xx = MUL_MODULO(xx, xx, m);
7059 if (nega_flg && tmp) {
7077 rb_int_powm(
int const argc,
VALUE *
const argv,
VALUE const num)
7082 return rb_int_pow(num, argv[0]);
7085 VALUE const a = num;
7086 VALUE const b = argv[0];
7092 if (rb_int_negative_p(b)) {
7096 rb_raise(
rb_eTypeError,
"Integer#pow() 2nd argument not allowed unless all arguments are integers");
7099 if (rb_int_negative_p(m)) {
7100 m = rb_int_uminus(m);
7105 long const half_val = (long)HALF_LONG_MSB;
7108 if (mm == 1)
return INT2FIX(0);
7109 if (mm <= half_val) {
7110 return int_pow_tmp1(rb_int_modulo(a, m), b, mm, nega_flg);
7113 return int_pow_tmp2(rb_int_modulo(a, m), b, mm, nega_flg);
7119 return int_pow_tmp3(rb_int_modulo(a, m), b, m, nega_flg);
#define RUBY_ASSERT(...)
Asserts that the given expression is truthy if and only if RUBY_DEBUG is truthy.
#define RUBY_DEBUG
Define this macro when you want assertions.
#define RUBY_ALIGNOF
Wraps (or simulates) alignof.
void rb_define_method(VALUE klass, const char *name, VALUE(*func)(ANYARGS), int argc)
Defines a method.
#define RB_INTEGER_TYPE_P
Old name of rb_integer_type_p.
#define FL_UNSET_RAW
Old name of RB_FL_UNSET_RAW.
#define REALLOC_N
Old name of RB_REALLOC_N.
#define ISSPACE
Old name of rb_isspace.
#define RFLOAT_VALUE
Old name of rb_float_value.
#define xfree
Old name of ruby_xfree.
#define Qundef
Old name of RUBY_Qundef.
#define INT2FIX
Old name of RB_INT2FIX.
#define NEGFIXABLE
Old name of RB_NEGFIXABLE.
#define T_BIGNUM
Old name of RUBY_T_BIGNUM.
#define OBJ_FREEZE
Old name of RB_OBJ_FREEZE.
#define ULONG2NUM
Old name of RB_ULONG2NUM.
#define UNREACHABLE_RETURN
Old name of RBIMPL_UNREACHABLE_RETURN.
#define CLASS_OF
Old name of rb_class_of.
#define SIZET2NUM
Old name of RB_SIZE2NUM.
#define FIXABLE
Old name of RB_FIXABLE.
#define LONG2FIX
Old name of RB_INT2FIX.
#define FIX2INT
Old name of RB_FIX2INT.
#define FIX2ULONG
Old name of RB_FIX2ULONG.
#define ALLOC_N
Old name of RB_ALLOC_N.
#define NUM2DBL
Old name of rb_num2dbl.
#define LONG2NUM
Old name of RB_LONG2NUM.
#define rb_usascii_str_new2
Old name of rb_usascii_str_new_cstr.
#define ULL2NUM
Old name of RB_ULL2NUM.
#define FIXNUM_MIN
Old name of RUBY_FIXNUM_MIN.
#define Qtrue
Old name of RUBY_Qtrue.
#define ST2FIX
Old name of RB_ST2FIX.
#define FIXNUM_MAX
Old name of RUBY_FIXNUM_MAX.
#define Qnil
Old name of RUBY_Qnil.
#define Qfalse
Old name of RUBY_Qfalse.
#define FIX2LONG
Old name of RB_FIX2LONG.
#define NIL_P
Old name of RB_NIL_P.
#define ALLOCV_N
Old name of RB_ALLOCV_N.
#define FL_WB_PROTECTED
Old name of RUBY_FL_WB_PROTECTED.
#define POSFIXABLE
Old name of RB_POSFIXABLE.
#define DBL2NUM
Old name of rb_float_new.
#define NUM2LONG
Old name of RB_NUM2LONG.
#define FIXNUM_P
Old name of RB_FIXNUM_P.
#define FL_SET_RAW
Old name of RB_FL_SET_RAW.
#define ALLOCV_END
Old name of RB_ALLOCV_END.
void rb_raise(VALUE exc, const char *fmt,...)
Exception entry point.
void rb_bug(const char *fmt,...)
Interpreter panic switch.
VALUE rb_eRangeError
RangeError exception.
VALUE rb_eTypeError
TypeError exception.
void rb_invalid_str(const char *str, const char *type)
Honestly I don't understand the name, but it raises an instance of rb_eArgError.
VALUE rb_eFloatDomainError
FloatDomainError exception.
void rb_warn(const char *fmt,...)
Identical to rb_warning(), except it reports unless $VERBOSE is nil.
VALUE rb_eArgError
ArgumentError exception.
void rb_warning(const char *fmt,...)
Issues a warning.
VALUE rb_Float(VALUE val)
This is the logic behind Kernel#Float.
VALUE rb_cInteger
Module class.
VALUE rb_obj_hide(VALUE obj)
Make the object invisible from Ruby code.
VALUE rb_equal(VALUE lhs, VALUE rhs)
This function is an optimised version of calling #==.
VALUE rb_to_int(VALUE val)
Identical to rb_check_to_int(), except it raises in case of conversion mismatch.
VALUE rb_funcall(VALUE recv, ID mid, int n,...)
Calls a method.
#define RGENGC_WB_PROTECTED_BIGNUM
This is a compile-time flag to enable/disable write barrier for struct RBignum.
VALUE rb_assoc_new(VALUE car, VALUE cdr)
Identical to rb_ary_new_from_values(), except it expects exactly two parameters.
int rb_integer_pack(VALUE val, void *words, size_t numwords, size_t wordsize, size_t nails, int flags)
Exports an integer into a buffer.
VALUE rb_big_lshift(VALUE x, VALUE y)
Performs shift left.
VALUE rb_big_and(VALUE x, VALUE y)
Performs bitwise and of the passed two objects.
VALUE rb_big_or(VALUE x, VALUE y)
Performs bitwise or of the passed two objects.
VALUE rb_big_minus(VALUE x, VALUE y)
Performs subtraction of the passed two objects.
VALUE rb_big_modulo(VALUE x, VALUE y)
Performs modulo of the passed two objects.
VALUE rb_big_new(size_t len, int sign)
Allocates a bignum object.
VALUE rb_big_pow(VALUE x, VALUE y)
Raises x to the powerof y.
int rb_bigzero_p(VALUE x)
Queries if the passed bignum instance is a "bigzero".
#define INTEGER_PACK_MSBYTE_FIRST
Stores/interprets the most significant byte in a word as the first byte in the word.
#define INTEGER_PACK_LSBYTE_FIRST
Stores/interprets the least significant byte in a word as the first byte in the word.
#define INTEGER_PACK_NATIVE_BYTE_ORDER
Means either INTEGER_PACK_MSBYTE_FIRST or INTEGER_PACK_LSBYTE_FIRST, depending on the host processor'...
VALUE rb_big_plus(VALUE x, VALUE y)
Performs addition of the passed two objects.
VALUE rb_str_to_inum(VALUE str, int base, int badcheck)
Identical to rb_cstr2inum(), except it takes Ruby's strings instead of C's.
VALUE rb_big_clone(VALUE num)
Duplicates the given bignum.
size_t rb_absint_size(VALUE val, int *nlz_bits_ret)
Calculates the number of bytes needed to represent the absolute value of the passed integer.
size_t rb_absint_numwords(VALUE val, size_t word_numbits, size_t *nlz_bits_ret)
Calculates the number of words needed represent the absolute value of the passed integer.
int rb_absint_singlebit_p(VALUE val)
Tests abs(val) consists only of a bit or not.
VALUE rb_integer_unpack(const void *words, size_t numwords, size_t wordsize, size_t nails, int flags)
Import an integer from a buffer.
unsigned long rb_big2ulong(VALUE x)
Converts a bignum into C's unsigned long.
VALUE rb_big_idiv(VALUE x, VALUE y)
Performs "integer division".
void rb_big_2comp(VALUE num)
Destructively modify the passed bignum into 2's complement representation.
VALUE rb_big2str(VALUE x, int base)
Generates a place-value representation of the passed integer.
#define INTEGER_PACK_FORCE_BIGNUM
Always generates a bignum object even if the integer can be representable using fixnum scheme (unpack...
#define INTEGER_PACK_BIG_ENDIAN
Big endian combination.
VALUE rb_big_cmp(VALUE lhs, VALUE rhs)
Compares the passed two bignums.
VALUE rb_str2inum(VALUE str, int base)
Identical to rb_str_to_inum(), except the second argument controls the base and badcheck at once.
VALUE rb_dbl2big(double d)
Converts a C's double into a bignum.
VALUE rb_big_mul(VALUE x, VALUE y)
Performs multiplication of the passed two objects.
VALUE rb_big_eql(VALUE lhs, VALUE rhs)
Equality, in terms of eql?.
VALUE rb_cstr2inum(const char *str, int base)
Identical to rb_cstr_to_inum(), except the second argument controls the base and badcheck at once.
#define INTEGER_PACK_2COMP
Uses 2's complement representation.
VALUE rb_big_unpack(unsigned long *buf, long num_longs)
Constructs a (possibly very big) bignum from a series of integers.
#define INTEGER_PACK_NEGATIVE
Interprets the input as a signed negative number (unpack only).
VALUE rb_big_divmod(VALUE x, VALUE y)
Performs "divmod" operation.
VALUE rb_big_xor(VALUE x, VALUE y)
Performs exclusive or of the passed two objects.
#define INTEGER_PACK_MSWORD_FIRST
Stores/interprets the most significant word as the first word.
VALUE rb_big_div(VALUE x, VALUE y)
Performs division of the passed two objects.
VALUE rb_big_norm(VALUE x)
Normalises the passed bignum.
VALUE rb_cstr_to_inum(const char *str, int base, int badcheck)
Parses C's string to convert into a Ruby's integer.
void rb_big_pack(VALUE val, unsigned long *buf, long num_longs)
Converts a bignum into a series of its parts.
VALUE rb_big_rshift(VALUE x, VALUE y)
Performs shift right.
double rb_big2dbl(VALUE x)
Converts a bignum into C's double.
#define INTEGER_PACK_FORCE_GENERIC_IMPLEMENTATION
Uses "generic" implementation (handy on test).
long rb_big2long(VALUE x)
Converts a bignum into C's long.
void rb_big_resize(VALUE big, size_t len)
Destructively resizes the backend storage of the passed bignum.
VALUE rb_big_eq(VALUE lhs, VALUE rhs)
Equality, in terms of ==.
#define INTEGER_PACK_LSWORD_FIRST
Stores/interprets the least significant word as the first word.
int rb_cmpint(VALUE val, VALUE a, VALUE b)
Canonicalises the passed val, which is the return value of a <=> b, into C's {-1, 0,...
void rb_cmperr(VALUE a, VALUE b)
Raises "comparison failed" error.
static int rb_check_arity(int argc, int min, int max)
Ensures that the passed integer is in the passed range.
void rb_num_zerodiv(void)
Just always raises an exception.
VALUE rb_fix2str(VALUE val, int base)
Generates a place-value representation of the given Fixnum, with given radix.
VALUE rb_num_coerce_bit(VALUE lhs, VALUE rhs, ID op)
This one is optimised for bitwise operations, but the API is identical to rb_num_coerce_bin().
VALUE rb_num_coerce_relop(VALUE lhs, VALUE rhs, ID op)
Identical to rb_num_coerce_cmp(), except for return values.
VALUE rb_num_coerce_cmp(VALUE lhs, VALUE rhs, ID op)
Identical to rb_num_coerce_bin(), except for return values.
VALUE rb_num_coerce_bin(VALUE lhs, VALUE rhs, ID op)
Coerced binary operation.
VALUE rb_rational_raw(VALUE num, VALUE den)
Identical to rb_rational_new(), except it skips argument validations.
st_index_t rb_memhash(const void *ptr, long len)
This is a universal hash function.
VALUE rb_usascii_str_new(const char *ptr, long len)
Identical to rb_str_new(), except it generates a string of "US ASCII" encoding.
void rb_str_set_len(VALUE str, long len)
Overwrites the length of the string.
void rb_must_asciicompat(VALUE obj)
Asserts that the given string's encoding is (Ruby's definition of) ASCII compatible.
VALUE rb_str_resize(VALUE str, long len)
Overwrites the length of the string.
void rb_thread_check_ints(void)
Checks for interrupts.
ID rb_intern(const char *name)
Finds or creates a symbol of the given name.
void rb_define_const(VALUE klass, const char *name, VALUE val)
Defines a Ruby level constant under a namespace.
char * ptr
Pointer to the underlying memory region, of at least capa bytes.
int len
Length of the buffer.
#define RB_NOGVL_UBF_ASYNC_SAFE
Passing this flag to rb_nogvl() indicates that the passed UBF is async-signal-safe.
void * rb_nogvl(void *(*func)(void *), void *data1, rb_unblock_function_t *ubf, void *data2, int flags)
Identical to rb_thread_call_without_gvl(), except it additionally takes "flags" that change the behav...
unsigned long ruby_scan_digits(const char *str, ssize_t len, int base, size_t *retlen, int *overflow)
Scans the passed string, assuming the string is a textual representation of an integer.
VALUE rb_sprintf(const char *fmt,...)
Ruby's extended sprintf(3).
VALUE rb_ull2inum(unsigned LONG_LONG num)
Converts a C's unsigned long long into an instance of rb_cInteger.
VALUE rb_ll2inum(LONG_LONG num)
Converts a C's long long into an instance of rb_cInteger.
VALUE rb_int2inum(intptr_t i)
Converts a C's intptr_t into an instance of rb_cInteger.
VALUE rb_uint2big(uintptr_t i)
Converts a C's intptr_t into an instance of rb_cInteger.
VALUE rb_int2big(intptr_t i)
Converts a C's intptr_t into an instance of rb_cInteger.
VALUE rb_uint2inum(uintptr_t i)
Converts a C's uintptr_t into an instance of rb_cInteger.
#define MEMCPY(p1, p2, type, n)
Handy macro to call memcpy.
#define MEMCMP(p1, p2, type, n)
Handy macro to call memcmp.
#define MEMZERO(p, type, n)
Handy macro to erase a region of memory.
#define RB_GC_GUARD(v)
Prevents premature destruction of local objects.
#define MEMMOVE(p1, p2, type, n)
Handy macro to call memmove.
VALUE type(ANYARGS)
ANYARGS-ed function type.
int rb_big_sign(VALUE num)
The "sign" of a bignum.
#define StringValue(v)
Ensures that the parameter object is a String.
#define StringValuePtr(v)
Identical to StringValue, except it returns a char*.
static char * RSTRING_PTR(VALUE str)
Queries the contents pointer of the string.
#define RSTRING_GETMEM(str, ptrvar, lenvar)
Convenient macro to obtain the contents and length at once.
static long RSTRING_LEN(VALUE str)
Queries the length of the string.
#define StringValueCStr(v)
Identical to StringValuePtr, except it additionally checks for the contents for viability as a C stri...
#define RTEST
This is an old name of RB_TEST.
intptr_t SIGNED_VALUE
A signed integer type that has the same width with VALUE.
uintptr_t ID
Type that represents a Ruby identifier such as a variable name.
#define SIZEOF_VALUE
Identical to sizeof(VALUE), except it is a macro that can also be used inside of preprocessor directi...
uintptr_t VALUE
Type that represents a Ruby object.
static bool RB_FLOAT_TYPE_P(VALUE obj)
Queries if the object is an instance of rb_cFloat.
#define RBIMPL_WARNING_IGNORED(flag)
Suppresses a warning.
#define RBIMPL_WARNING_PUSH()
Pushes compiler warning state.
#define RBIMPL_WARNING_POP()
Pops compiler warning state.