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"
57static const bool debug_integer_pack = (
58#ifdef DEBUG_INTEGER_PACK
65const 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
75STATIC_ASSERT(sizeof_bdigit_dbl,
sizeof(BDIGIT_DBL) == SIZEOF_BDIGIT_DBL);
76STATIC_ASSERT(sizeof_bdigit_dbl_signed,
sizeof(BDIGIT_DBL_SIGNED) == SIZEOF_BDIGIT_DBL);
77STATIC_ASSERT(sizeof_bdigit, SIZEOF_BDIGIT <=
sizeof(BDIGIT));
78STATIC_ASSERT(sizeof_bdigit_and_dbl, SIZEOF_BDIGIT*2 <= SIZEOF_BDIGIT_DBL);
79STATIC_ASSERT(bdigit_signedness, 0 < (BDIGIT)-1);
80STATIC_ASSERT(bdigit_dbl_signedness, 0 < (BDIGIT_DBL)-1);
81STATIC_ASSERT(bdigit_dbl_signed_signedness, 0 > (BDIGIT_DBL_SIGNED)-1);
82STATIC_ASSERT(rbignum_embed_len_max, BIGNUM_EMBED_LEN_MAX <= (BIGNUM_EMBED_LEN_MASK >> BIGNUM_EMBED_LEN_SHIFT));
84#if SIZEOF_BDIGIT < SIZEOF_LONG
85STATIC_ASSERT(sizeof_long_and_sizeof_bdigit, SIZEOF_LONG % SIZEOF_BDIGIT == 0);
87STATIC_ASSERT(sizeof_long_and_sizeof_bdigit, SIZEOF_BDIGIT % SIZEOF_LONG == 0);
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
174typedef 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);
176static mulfunc_t bary_mul_toom3_start;
177static mulfunc_t bary_mul_karatsuba_start;
178static BDIGIT bigdivrem_single(BDIGIT *qds,
const BDIGIT *xds,
size_t xn, BDIGIT y);
184static inline VALUE power_cache_get_power(
int base,
int power_level,
size_t *numdigits_ret);
186#if SIZEOF_BDIGIT <= SIZEOF_INT
187static int nlz(BDIGIT x) {
return nlz_int((
unsigned int)x) - (SIZEOF_INT-SIZEOF_BDIGIT) * CHAR_BIT; }
188#elif SIZEOF_BDIGIT <= SIZEOF_LONG
189static int nlz(BDIGIT x) {
return nlz_long((
unsigned long)x) - (SIZEOF_LONG-SIZEOF_BDIGIT) * CHAR_BIT; }
190#elif SIZEOF_BDIGIT <= SIZEOF_LONG_LONG
191static 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
193static 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))
202#define U128(a,b,c,d) (((uint128_t)U64(a,b) << 64) | U64(c,d))
249#if SIZEOF_BDIGIT_DBL == 2
250static 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,
254static 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
266static 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,
270static 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
282static 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,
287static 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
308static 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,
313static 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),
353maxpow_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) {
387static inline BDIGIT_DBL
388bary2bdigitdbl(
const BDIGIT *ds,
size_t n)
393 return ds[0] | BIGUP(ds[1]);
400bdigitdbl2bary(BDIGIT *ds,
size_t n, BDIGIT_DBL num)
405 ds[1] = (BDIGIT)BIGDN(num);
409bary_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;
429bary_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;
444bary_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);
461bary_zero_p(
const BDIGIT *xds,
size_t xn)
466 if (xds[--xn])
return 0;
472bary_neg(BDIGIT *ds,
size_t n)
475 for (i = 0; i < n; i++)
476 ds[n - i - 1] = BIGLO(~ds[n - i - 1]);
480bary_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]);
500bary_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)
520validate_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) {
526 rb_raise(rb_eArgError,
"unsupported flags specified");
528 if (wordorder_bits == 0) {
530 rb_raise(rb_eArgError,
"word order not specified");
534 rb_raise(rb_eArgError,
"unexpected word order");
535 if (byteorder_bits == 0) {
536 rb_raise(rb_eArgError,
"byte order not specified");
541 rb_raise(rb_eArgError,
"unexpected byte order");
543 rb_raise(rb_eArgError,
"invalid wordsize: %"PRI_SIZE_PREFIX
"u", wordsize);
544 if (SSIZE_MAX < wordsize)
545 rb_raise(rb_eArgError,
"too big wordsize: %"PRI_SIZE_PREFIX
"u", wordsize);
546 if (wordsize <= nails / CHAR_BIT)
547 rb_raise(rb_eArgError,
"too big nails: %"PRI_SIZE_PREFIX
"u", nails);
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);
553integer_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;
618integer_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;
630static inline BDIGIT_DBL
631integer_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)
642bytes_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++) {
661bary_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)
990integer_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);
1000integer_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;
1060integer_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);
1081integer_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;
1093integer_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
1119bary_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);
1320bary_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;
1352bary_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++) {
1403bary_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);
1409bary_sub_one(BDIGIT *zds,
size_t zn)
1411 return bary_subb(zds, zn, zds, zn, NULL, 0, 1);
1415bary_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++) {
1461bary_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);
1467bary_add_one(BDIGIT *ds,
size_t n)
1470 for (i = 0; i < n; i++) {
1471 BDIGIT_DBL n = ds[i];
1481bary_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);
1493bary_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++) {
1527static BDIGIT_DBL_SIGNED
1528bigdivrem_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];
1555bary_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);
1569bary_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);
1597bary_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);
1651rb_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);
1661max_size(
size_t a,
size_t b)
1663 return (a > b ? a : b);
1668bary_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);
1746bary_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)))
1920 rb_raise(rb_eArgError,
"unexpected bignum length for karatsuba");
1921 bary_mul_karatsuba(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, NULL, 0);
1928bary_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))
2317 rb_raise(rb_eArgError,
"unexpected bignum length for toom3");
2318 bary_mul_toom3(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, NULL, 0);
2326bdigits_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);
2333bdigits_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);
2340bary_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);
2378bary_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);
2393bary_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;
2405bary_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);
2503bary_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);
2537bary_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);
2546bary_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);
2562bary_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);
2571bary_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;
2603bigdivrem1(
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,
2639rb_big_stop(
void *ptr)
2646bigdivrem_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);
2670bigdivrem_single(BDIGIT *qds,
const BDIGIT *xds,
size_t xn, BDIGIT y)
2672 return bigdivrem_single1(qds, xds, xn, 0, y);
2676bigdivrem_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) {
2715bary_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]))
2788 return rb_assoc_new(
LONG2FIX(0), x);
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);
2806 return rb_assoc_new(q, r);
2811bary_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]))
2868 return rb_assoc_new(
LONG2FIX(0), x);
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);
2886 return rb_assoc_new(q, r);
2891bary_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);
2903bary_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);
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)))
2994rb_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);
3036bignew_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;
3056rb_big_new(
size_t len,
int sign)
3058 return bignew(
len, sign != 0);
3064 size_t len = BIGNUM_LEN(x);
3067 MEMCPY(BDIGITS(z), BDIGITS(x), BDIGIT,
len);
3072big_extend_carry(
VALUE x)
3074 rb_big_resize(x, BIGNUM_LEN(x)+1);
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);
3097abs2twocomp(
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);
3118twocomp2abs_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) {
3135 rb_big_resize(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)) {
3180 rb_big_resize(x, n);
3187 if (RB_BIGNUM_TYPE_P(x)) {
3200rb_uint2big(uintptr_t n)
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);
3222rb_int2big(intptr_t n)
3229 u = 1 + (
VALUE)(-(n + 1));
3235 big = rb_uint2big(u);
3237 BIGNUM_SET_NEGATIVE_SIGN(big);
3243rb_uint2inum(uintptr_t n)
3246 return rb_uint2big(n);
3250rb_int2inum(intptr_t n)
3253 return rb_int2big(n);
3257rb_big_pack(
VALUE val,
unsigned long *buf,
long num_longs)
3259 rb_integer_pack(val, buf, num_longs,
sizeof(
long), 0,
3265rb_big_unpack(
unsigned long *buf,
long num_longs)
3267 return rb_integer_unpack(buf, num_longs,
sizeof(
long), 0,
3289rb_absint_size(
VALUE val,
int *nlz_bits_ret)
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;
3336absint_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;
3350absint_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;
3424rb_absint_numwords(
VALUE val,
size_t word_numbits,
size_t *nlz_bits_ret)
3427 int nlz_bits_in_msbyte;
3429 size_t nlz_bits = 0;
3431 if (word_numbits == 0)
3434 numbytes = rb_absint_size(val, &nlz_bits_in_msbyte);
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)
3588rb_integer_pack(
VALUE val,
void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
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);
3674rb_integer_unpack(
const void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int 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)
3697 rb_raise(rb_eArgError,
"too big to unpack as an integer");
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)])
3747NORETURN(
static inline void invalid_radix(
int base));
3748NORETURN(
static inline void invalid_integer(
VALUE s));
3751valid_radix_p(
int base)
3753 return (1 < base && base <= 36);
3757invalid_radix(
int base)
3759 rb_raise(rb_eArgError,
"invalid radix %d", base);
3763invalid_integer(
VALUE s)
3765 rb_raise(rb_eArgError,
"invalid value for Integer(): %+"PRIsVALUE, s);
3769str2big_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);
4032static VALUE rb_cstr_parse_inum(
const char *str, ssize_t
len,
char **endp,
int base);
4051rb_cstr_to_inum(
const char *str,
int base,
int badcheck)
4054 VALUE ret = rb_cstr_parse_inum(str, -1, (badcheck ? NULL : &end), base);
4080rb_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;
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;
4207 val = ruby_scan_digits(str,
len, base, &num_digits, &ov);
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;
4230 VALUE big = rb_uint2big(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;
4279rb_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);
4286rb_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);
4308rb_str_to_inum(
VALUE str,
int base,
int badcheck)
4310 return rb_str_convert_to_inum(str, base, badcheck, TRUE);
4314rb_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);
4329 len = RSTRING_LEN(arg);
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));
4350rb_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);
4368 len = RSTRING_LEN(arg);
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,
4392rb_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);
4410 len = RSTRING_LEN(arg);
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);
4435rb_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);
4453 len = RSTRING_LEN(arg);
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);
4539rb_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);
4556rb_int128t2big(int128_t n)
4563 u = 1 + (uint128_t)(-(n + 1));
4569 big = rb_uint128t2big(u);
4571 BIGNUM_SET_NEGATIVE_SIGN(big);
4578rb_cstr2inum(
const char *str,
int base)
4580 return rb_cstr_to_inum(str, base, base==0);
4586 return rb_str_to_inum(str, base, base==0);
4590big_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;
4654 sign = rb_integer_pack(y, lens, numberof(lens),
sizeof(
size_t), 0,
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);
4675big_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);
4683big_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)
4692static VALUE base36_power_cache[35][MAX_BASE36_POWER_TABLE_ENTRIES];
4693static size_t base36_numdigits_cache[35][MAX_BASE36_POWER_TABLE_ENTRIES];
4696power_cache_init(
void)
4701power_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)
4757 rb_raise(rb_eArgError,
"too big number");
4759 b2s->ptr = RSTRING_PTR(b2s->result);
4765big2str_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;
4804big2str_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);
4927big2str_base_poweroftwo(
VALUE x,
int base)
4929 int word_numbits = ffs(base) - 1;
4933 numwords = rb_absint_numwords(x, word_numbits, NULL);
4934 if (BIGNUM_NEGATIVE_P(x)) {
4935 if (LONG_MAX-1 < numwords)
4936 rb_raise(rb_eArgError,
"too big number");
4938 ptr = RSTRING_PTR(result);
4939 *ptr++ = BIGNUM_POSITIVE_P(x) ?
'+' :
'-';
4942 if (LONG_MAX < numwords)
4943 rb_raise(rb_eArgError,
"too big number");
4945 ptr = RSTRING_PTR(result);
4947 rb_integer_pack(x, ptr, numwords, 1, CHAR_BIT-word_numbits,
4949 while (0 < numwords) {
4950 *ptr = ruby_digitmap[*(
unsigned char *)ptr];
4958rb_big2str_poweroftwo(
VALUE x,
int base)
4960 return big2str_base_poweroftwo(x, base);
4964big2str_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) {
4984 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'string'");
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';
5034 rb_str_resize(b2s_data.result, (
long)(b2s_data.ptr - RSTRING_PTR(b2s_data.result)));
5037 return b2s_data.result;
5041rb_big2str_generic(
VALUE x,
int base)
5043 return big2str_generic(x, base);
5048big2str_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)) {
5068 mpz_get_str(RSTRING_PTR(str), base, mx);
5071 if (RSTRING_PTR(str)[RSTRING_LEN(str)-1] ==
'\0') {
5080rb_big2str_gmp(
VALUE x,
int base)
5082 return big2str_gmp(x, base);
5087rb_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) {
5109 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'string'");
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);
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;
5172 rb_raise(
rb_eRangeError,
"bignum out of range of unsigned long");
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;
5188 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'long'");
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)))
5231 rb_raise(
rb_eRangeError,
"bignum out of range of unsigned long long");
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)))
5247 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'long long'");
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
5402 rel = rb_big_cmp(x, y);
5403 if (yf == 0.0 || rel !=
INT2FIX(0))
5410#if SIZEOF_LONG * CHAR_BIT >= DBL_MANT_DIG
5411COMPILER_WARNING_PUSH
5412#if __has_warning("-Wimplicit-int-float-conversion")
5413COMPILER_WARNING_IGNORED(-Wimplicit-
int-
float-conversion)
5415static const double LONG_MAX_as_double = LONG_MAX;
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);
5444 return rb_big_eq(x, y);
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);
5490 rel = rb_big_cmp(x, y);
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);
5582rb_big_uminus(
VALUE x)
5584 VALUE z = rb_big_clone(x);
5594 VALUE z = rb_big_clone(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);
5645bigsub_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++) {
5742bigadd_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));
5917 if (MUL_OVERFLOW_LONG_P(2, xn))
5918 rb_raise(rb_eArgError,
"square overflow");
5926 if (xn < NAIVE_MUL_DIGITS)
5927 bary_sq_fast(zds, zn, xds, xn);
5929 bary_mul(zds, zn, xds, xn, xds, xn);
5940 BDIGIT *xds, *yds, *zds;
5947 if (ADD_OVERFLOW_LONG_P(xn, yn))
5948 rb_raise(rb_eArgError,
"multiplication overflow");
5951 z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
5957 bary_mul(zds, zn, xds, xn, yds, yn);
5970 else if (RB_BIGNUM_TYPE_P(y)) {
5979 return bignorm(bigmul0(x, y));
5985 long xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y);
5987 BDIGIT *xds, *yds, *zds;
5995 BARY_TRUNC(yds, yn);
6000 BARY_TRUNC(xds, xn);
6002 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1])) {
6003 if (divp) *divp = rb_int2big(0);
6004 if (modp) *modp = x;
6009 z = bignew(xn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6011 dd = bigdivrem_single(zds, xds, xn, dd);
6013 *modp = rb_uint2big((uintptr_t)dd);
6014 BIGNUM_SET_SIGN(*modp, BIGNUM_SIGN(x));
6016 if (divp) *divp = z;
6019 if (xn == 2 && yn == 2) {
6020 BDIGIT_DBL x0 = bary2bdigitdbl(xds, 2);
6021 BDIGIT_DBL y0 = bary2bdigitdbl(yds, 2);
6022 BDIGIT_DBL q0 = x0 / y0;
6023 BDIGIT_DBL r0 = x0 % y0;
6025 z = bignew(bdigit_roomof(
sizeof(BDIGIT_DBL)), BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6028 zds[1] = BIGLO(BIGDN(q0));
6032 z = bignew(bdigit_roomof(
sizeof(BDIGIT_DBL)), BIGNUM_SIGN(x));
6035 zds[1] = BIGLO(BIGDN(r0));
6042 qn = xn + BIGDIVREM_EXTRA_WORDS;
6043 q = bignew(qn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6053 r = bignew(rn, BIGNUM_SIGN(x));
6061 bary_divmod_branch(qds, qn, rds, rn, xds, xn, yds, yn);
6080 bigdivrem(x, y, divp, &mod);
6081 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y) && !BIGZEROP(mod)) {
6082 if (divp) *divp = bigadd(*divp, rb_int2big(1), 0);
6083 if (modp) *modp = bigadd(mod, y, 1);
6099 else if (RB_BIGNUM_TYPE_P(y)) {
6103 double dx = rb_big2dbl(x);
6104 return rb_flo_div_flo(
DBL2NUM(dx), y);
6110 v = rb_big_divide(x, y,
'/');
6117 bigdivmod(x, y, &z, 0);
6125 return rb_big_divide(x, y,
'/');
6131 return rb_big_divide(x, y, idDiv);
6142 else if (!RB_BIGNUM_TYPE_P(y)) {
6145 bigdivmod(x, y, 0, &z);
6158 else if (!RB_BIGNUM_TYPE_P(y)) {
6161 bigdivrem(x, y, 0, &z);
6174 else if (!RB_BIGNUM_TYPE_P(y)) {
6177 bigdivmod(x, y, &div, &mod);
6179 return rb_assoc_new(bignorm(div), bignorm(mod));
6183big_shift(
VALUE x,
long n)
6186 return big_lshift(x, 1+(
unsigned long)(-(n+1)));
6188 return big_rshift(x, (
unsigned long)n);
6192enum {DBL_BIGDIG = ((DBL_MANT_DIG + BITSPERDIG) / BITSPERDIG)};
6202 ex = l * BITSPERDIG - nlz(BDIGITS(x)[l-1]);
6203 ex -= 2 * DBL_BIGDIG * BITSPERDIG;
6204 if (ex > BITSPERDIG) ex -= BITSPERDIG;
6205 else if (ex > 0) ex = 0;
6206 if (ex) x = big_shift(x, ex);
6208 bigdivrem(x, y, &z, 0);
6210#if SIZEOF_LONG > SIZEOF_INT
6213 if (l > INT_MAX)
return HUGE_VAL;
6214 if (l < INT_MIN)
return 0.0;
6217 return ldexp(big2dbl(z), (
int)l);
6226 ey = l * BITSPERDIG - nlz(BDIGITS(y)[l-1]);
6227 ey -= DBL_BIGDIG * BITSPERDIG;
6228 if (ey) y = big_shift(y, ey);
6229 return big_fdiv(x, y, ey);
6236 y = dbl2big(ldexp(frexp(
RFLOAT_VALUE(y), &i), DBL_MANT_DIG));
6237 return big_fdiv(x, y, i - DBL_MANT_DIG);
6250 return big_fdiv_int(x, rb_int2big(
FIX2LONG(y)));
6252 else if (RB_BIGNUM_TYPE_P(y)) {
6253 return big_fdiv_int(x, y);
6260 return big_fdiv_float(x, y);
6272 return DBL2NUM(rb_big_fdiv_double(x, y));
6283 if (y ==
INT2FIX(1))
return x;
6286 if ((BIGNUM_NEGATIVE_P(x) && !BIGZEROP(x))) {
6287 return rb_dbl_complex_new_polar_pi(pow(-rb_big2dbl(x), d), d);
6290 else if (RB_BIGNUM_TYPE_P(y)) {
6294 rb_raise(rb_eArgError,
"exponent is too large");
6309 const size_t xbits = rb_absint_numwords(x, 1, NULL);
6310#if SIZEOF_SIZE_T == 4
6311 const size_t BIGLEN_LIMIT = 1ULL << 31;
6313 const size_t BIGLEN_LIMIT = 1ULL << 34;
6316 if (xbits == (
size_t)-1 ||
6317 (xbits > BIGLEN_LIMIT) ||
6318 MUL_OVERFLOW_LONG_P(yy, xbits) ||
6319 (xbits * yy > BIGLEN_LIMIT)) {
6320 rb_raise(rb_eArgError,
"exponent is too large");
6323 for (mask =
FIXNUM_MAX + 1; mask; mask >>= 1) {
6324 if (z) z = bigsq(z);
6326 z = z ? bigtrunc(bigmul0(z, x)) : x;
6336 return DBL2NUM(pow(rb_big2dbl(x), d));
6340bigand_int(
VALUE x,
long xn, BDIGIT hibitsx,
long y)
6348 if (y == 0)
return INT2FIX(0);
6349 if (xn == 0)
return hibitsx ?
LONG2NUM(y) : 0;
6350 hibitsy = 0 <= y ? 0 : BDIGMAX;
6352#if SIZEOF_BDIGIT >= SIZEOF_LONG
6360#if SIZEOF_BDIGIT < SIZEOF_LONG
6361 if (hibitsx && zn < bdigit_roomof(SIZEOF_LONG))
6362 zn = bdigit_roomof(SIZEOF_LONG);
6368#if SIZEOF_BDIGIT >= SIZEOF_LONG
6370 zds[0] = xds[0] & BIGLO(y);
6372 for (i=0; i < xn; i++) {
6373 if (y == 0 || y == -1)
break;
6374 zds[i] = xds[i] & BIGLO(y);
6377 for (; i < zn; i++) {
6378 if (y == 0 || y == -1)
break;
6379 zds[i] = hibitsx & BIGLO(y);
6383 for (;i < xn; i++) {
6384 zds[i] = xds[i] & hibitsy;
6386 for (;i < zn; i++) {
6387 zds[i] = hibitsx & hibitsy;
6389 twocomp2abs_bang(z, hibitsx && hibitsy);
6398 BDIGIT *ds1, *ds2, *zds;
6399 long i, xn, yn, n1, n2;
6400 BDIGIT hibitsx, hibitsy;
6401 BDIGIT hibits1, hibits2;
6410 hibitsx = abs2twocomp(&x, &xn);
6412 return bigand_int(x, xn, hibitsx,
FIX2LONG(y));
6414 hibitsy = abs2twocomp(&y, &yn);
6416 tmpv = x; x = y; y = tmpv;
6417 tmpn = xn; xn = yn; yn = tmpn;
6418 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6433 for (i=0; i<n1; i++) {
6434 zds[i] = ds1[i] & ds2[i];
6437 zds[i] = hibits1 & ds2[i];
6439 twocomp2abs_bang(z, hibits1 && hibits2);
6446bigor_int(
VALUE x,
long xn, BDIGIT hibitsx,
long y)
6454 if (y == -1)
return INT2FIX(-1);
6456 hibitsy = 0 <= y ? 0 : BDIGMAX;
6460#if SIZEOF_BDIGIT < SIZEOF_LONG
6461 if (zn < bdigit_roomof(SIZEOF_LONG))
6462 zn = bdigit_roomof(SIZEOF_LONG);
6467#if SIZEOF_BDIGIT >= SIZEOF_LONG
6469 zds[0] = xds[0] | BIGLO(y);
6471 goto y_is_fixed_point;
6474 for (i=0; i < xn; i++) {
6475 if (y == 0 || y == -1)
goto y_is_fixed_point;
6476 zds[i] = xds[i] | BIGLO(y);
6481 for (; i < zn; i++) {
6482 if (y == 0 || y == -1)
goto y_is_fixed_point;
6492 for (; i < xn; i++) {
6497 for (; i < zn; i++) {
6503 for (; i < zn; i++) {
6508 twocomp2abs_bang(z, hibitsx || hibitsy);
6517 BDIGIT *ds1, *ds2, *zds;
6518 long i, xn, yn, n1, n2;
6519 BDIGIT hibitsx, hibitsy;
6520 BDIGIT hibits1, hibits2;
6529 hibitsx = abs2twocomp(&x, &xn);
6531 return bigor_int(x, xn, hibitsx,
FIX2LONG(y));
6533 hibitsy = abs2twocomp(&y, &yn);
6535 tmpv = x; x = y; y = tmpv;
6536 tmpn = xn; xn = yn; yn = tmpn;
6537 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6552 for (i=0; i<n1; i++) {
6553 zds[i] = ds1[i] | ds2[i];
6556 zds[i] = hibits1 | ds2[i];
6558 twocomp2abs_bang(z, hibits1 || hibits2);
6565bigxor_int(
VALUE x,
long xn, BDIGIT hibitsx,
long y)
6573 hibitsy = 0 <= y ? 0 : BDIGMAX;
6576#if SIZEOF_BDIGIT < SIZEOF_LONG
6577 if (zn < bdigit_roomof(SIZEOF_LONG))
6578 zn = bdigit_roomof(SIZEOF_LONG);
6583#if SIZEOF_BDIGIT >= SIZEOF_LONG
6585 zds[0] = xds[0] ^ BIGLO(y);
6587 for (i = 0; i < xn; i++) {
6588 zds[i] = xds[i] ^ BIGLO(y);
6591 for (; i < zn; i++) {
6592 zds[i] = hibitsx ^ BIGLO(y);
6596 for (; i < xn; i++) {
6597 zds[i] = xds[i] ^ hibitsy;
6599 for (; i < zn; i++) {
6600 zds[i] = hibitsx ^ hibitsy;
6602 twocomp2abs_bang(z, (hibitsx ^ hibitsy) != 0);
6611 BDIGIT *ds1, *ds2, *zds;
6612 long i, xn, yn, n1, n2;
6613 BDIGIT hibitsx, hibitsy;
6614 BDIGIT hibits1, hibits2;
6623 hibitsx = abs2twocomp(&x, &xn);
6625 return bigxor_int(x, xn, hibitsx,
FIX2LONG(y));
6627 hibitsy = abs2twocomp(&y, &yn);
6629 tmpv = x; x = y; y = tmpv;
6630 tmpn = xn; xn = yn; yn = tmpn;
6631 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6643 for (i=0; i<n1; i++) {
6644 zds[i] = ds1[i] ^ ds2[i];
6647 zds[i] = hibitsx ^ ds2[i];
6649 twocomp2abs_bang(z, (hibits1 ^ hibits2) != 0);
6659 size_t shift_numdigits;
6665 unsigned long shift;
6672 shift = 1+(
unsigned long)(-(l+1));
6674 shift_numbits = (int)(shift & (BITSPERDIG-1));
6675 shift_numdigits = shift >> bit_length(BITSPERDIG-1);
6676 return bignorm(big_shift3(x, lshift_p, shift_numdigits, shift_numbits));
6678 else if (RB_BIGNUM_TYPE_P(y)) {
6679 return bignorm(big_shift2(x, 1, y));
6689 size_t shift_numdigits;
6695 unsigned long shift;
6702 shift = 1+(
unsigned long)(-(l+1));
6704 shift_numbits = (int)(shift & (BITSPERDIG-1));
6705 shift_numdigits = shift >> bit_length(BITSPERDIG-1);
6706 return bignorm(big_shift3(x, lshift_p, shift_numdigits, shift_numbits));
6708 else if (RB_BIGNUM_TYPE_P(y)) {
6709 return bignorm(big_shift2(x, 0, y));
6724 if (RB_BIGNUM_TYPE_P(y)) {
6725 if (BIGNUM_NEGATIVE_P(y))
6728 if (BIGSIZE(y) >
sizeof(
size_t)) {
6731#if SIZEOF_SIZE_T <= SIZEOF_LONG
6732 shift = big2ulong(y,
"long");
6734 shift = big2ull(y,
"long long");
6742 s1 = shift/BITSPERDIG;
6743 s2 = shift%BITSPERDIG;
6744 bit = (BDIGIT)1 << s2;
6746 if (s1 >= BIGNUM_LEN(x))
6750 if (BIGNUM_POSITIVE_P(x))
6752 if (xds[s1] & (bit-1))
6754 for (i = 0; i < s1; i++)
6765 hash =
rb_memhash(BDIGITS(x),
sizeof(BDIGIT)*BIGNUM_LEN(x)) ^ BIGNUM_SIGN(x);
6788 return rb_assoc_new(y, x);
6793 return rb_assoc_new(y, x);
6800 if (BIGNUM_NEGATIVE_P(x)) {
6801 x = rb_big_clone(x);
6802 BIGNUM_SET_POSITIVE_SIGN(x);
6810 return BIGNUM_SIGN(x);
6814rb_big_size(
VALUE big)
6816 return BIGSIZE(big);
6820rb_big_size_m(
VALUE big)
6826rb_big_bit_length(
VALUE big)
6831 static const BDIGIT char_bit[1] = { CHAR_BIT };
6832 BDIGIT numbytes_bary[bdigit_roomof(
sizeof(
size_t))];
6834 BDIGIT result_bary[bdigit_roomof(
sizeof(
size_t)+1)];
6836 numbytes = rb_absint_size(big, &nlz_bits);
6841 if (BIGNUM_NEGATIVE_P(big) && rb_absint_singlebit_p(big)) {
6842 if (nlz_bits != CHAR_BIT-1) {
6851 if (numbytes <= SIZE_MAX / CHAR_BIT) {
6852 return SIZET2NUM(numbytes * CHAR_BIT - nlz_bits);
6855 nlz_bary[0] = nlz_bits;
6857 bary_unpack(BARY_ARGS(numbytes_bary), &numbytes, 1,
sizeof(numbytes), 0,
6859 BARY_SHORT_MUL(result_bary, numbytes_bary, char_bit);
6860 BARY_SUB(result_bary, result_bary, nlz_bary);
6862 return rb_integer_unpack(result_bary, numberof(result_bary),
sizeof(BDIGIT), 0,
6867rb_big_odd_p(
VALUE num)
6869 return RBOOL(BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1);
6873rb_big_even_p(
VALUE num)
6875 if (BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1) {
6881unsigned long rb_ulong_isqrt(
unsigned long);
6882#if SIZEOF_BDIGIT*2 > SIZEOF_LONG
6883BDIGIT rb_bdigit_dbl_isqrt(BDIGIT_DBL);
6884# ifdef ULL_TO_DOUBLE
6885# define BDIGIT_DBL_TO_DOUBLE(n) ULL_TO_DOUBLE(n)
6888# define rb_bdigit_dbl_isqrt(x) (BDIGIT)rb_ulong_isqrt(x)
6890#ifndef BDIGIT_DBL_TO_DOUBLE
6891# define BDIGIT_DBL_TO_DOUBLE(n) (double)(n)
6895rb_big_isqrt(
VALUE n)
6897 BDIGIT *nds = BDIGITS(n);
6898 size_t len = BIGNUM_LEN(n);
6901 BDIGIT sq = rb_bdigit_dbl_isqrt(bary2bdigitdbl(nds,
len));
6902#if SIZEOF_BDIGIT > SIZEOF_LONG
6909 size_t shift =
FIX2LONG(rb_big_bit_length(n)) / 4;
6913 x = rb_int_plus(rb_int_lshift(x,
SIZET2NUM(shift - 1)), rb_int_idiv(rb_int_rshift(n,
SIZET2NUM(shift + 1)), x));
6914 VALUE xx = rb_int_mul(x, x);
6915 while (rb_int_gt(xx, n)) {
6916 xx = rb_int_minus(xx, rb_int_minus(rb_int_plus(x, x),
INT2FIX(1)));
6917 x = rb_int_minus(x,
INT2FIX(1));
6925bary_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)
6933 bdigits_to_mpz(x, xds, xn);
6934 bdigits_to_mpz(y, yds, yn);
6935 bdigits_to_mpz(m, mds, mn);
6936 mpz_powm(z, x, y, m);
6937 bdigits_from_mpz(z, zds, &count);
6938 BDIGITS_ZERO(zds+count, zn-count);
6951 size_t xn, yn, mn, zn;
6965 bary_powm_gmp(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, BDIGITS(m), mn);
6966 if (nega_flg & BIGNUM_POSITIVE_P(z)) {
6967 z = rb_big_minus(z, m);
6972 return rb_big_norm(z);
6978 if (
RTEST(rb_int_odd_p(y))) {
6979 tmp = rb_int_mul(tmp, x);
6980 tmp = rb_int_modulo(tmp, m);
6982 x = rb_int_mul(x, x);
6983 x = rb_int_modulo(x, m);
6985 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
6987 tmp = rb_int_mul(tmp, x);
6988 tmp = rb_int_modulo(tmp, m);
6990 x = rb_int_mul(x, x);
6991 x = rb_int_modulo(x, m);
6994 if (nega_flg && rb_int_positive_p(tmp)) {
6995 tmp = rb_int_minus(tmp, m);
7006int_pow_tmp1(
VALUE x,
VALUE y,
long mm,
int nega_flg)
7013 if (
RTEST(rb_int_odd_p(y))) {
7014 tmp = (tmp * xx) % mm;
7016 xx = (xx * xx) % mm;
7018 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7020 tmp = (tmp * xx) % mm;
7022 xx = (xx * xx) % mm;
7025 if (nega_flg && tmp) {
7032int_pow_tmp2(
VALUE x,
VALUE y,
long mm,
int nega_flg)
7040# define MUL_MODULO(a, b, c) (long)(((DLONG)(a) * (DLONG)(b)) % (c))
7045# define MUL_MODULO(a, b, c) rb_int_modulo(rb_fix_mul_fix((a), (b)), (c))
7049 if (
RTEST(rb_int_odd_p(y))) {
7050 tmp2 = MUL_MODULO(tmp2, xx, m);
7052 xx = MUL_MODULO(xx, xx, m);
7054 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7056 tmp2 = MUL_MODULO(tmp2, xx, m);
7058 xx = MUL_MODULO(xx, xx, m);
7066 if (nega_flg && tmp) {
7084rb_int_powm(
int const argc,
VALUE *
const argv,
VALUE const num)
7089 return rb_int_pow(num, argv[0]);
7092 VALUE const a = num;
7093 VALUE const b = argv[0];
7097 rb_raise(
rb_eTypeError,
"Integer#pow() 2nd argument not allowed unless a 1st argument is integer");
7099 if (rb_int_negative_p(b)) {
7100 rb_raise(
rb_eRangeError,
"Integer#pow() 1st argument cannot be negative when 2nd argument specified");
7103 rb_raise(
rb_eTypeError,
"Integer#pow() 2nd argument not allowed unless all arguments are integers");
7106 if (rb_int_negative_p(m)) {
7107 m = rb_int_uminus(m);
7112 long const half_val = (long)HALF_LONG_MSB;
7115 if (mm == 1)
return INT2FIX(0);
7116 if (mm <= half_val) {
7117 return int_pow_tmp1(rb_int_modulo(a, m), b, mm, nega_flg);
7120 return int_pow_tmp2(rb_int_modulo(a, m), b, mm, nega_flg);
7126 return int_pow_tmp3(rb_int_modulo(a, m), b, m, nega_flg);
7157 rb_define_const(
rb_cInteger,
"GMP_VERSION", rb_sprintf(
"GMP %s", gmp_version));
#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.
#define rb_define_method(klass, mid, func, arity)
Defines klass#mid.
#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.
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_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.
#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'...
#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.
#define INTEGER_PACK_2COMP
Uses 2's complement representation.
#define INTEGER_PACK_NEGATIVE
Interprets the input as a signed negative number (unpack only).
#define INTEGER_PACK_MSWORD_FIRST
Stores/interprets the most significant word as the first word.
#define INTEGER_PACK_FORCE_GENERIC_IMPLEMENTATION
Uses "generic" implementation (handy on test).
#define INTEGER_PACK_LSWORD_FIRST
Stores/interprets the least significant word as the first word.
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.
#define rb_usascii_str_new(str, 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.
void rb_thread_check_ints(void)
Checks for interrupts.
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...
#define RB_NOGVL_OFFLOAD_SAFE
Passing this flag to rb_nogvl() indicates that the passed function is safe to offload to a background...
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.
#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.
#define StringValue(v)
Ensures that the parameter object is a String.
#define StringValuePtr(v)
Identical to StringValue, except it returns a char*.
#define RSTRING_GETMEM(str, ptrvar, lenvar)
Convenient macro to obtain the contents and length at once.
#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.