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]))
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);
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]))
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);
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 VALUE obj = bignew(
len, sign != 0);
3059 memset(BIGNUM_DIGITS(obj), 0,
len *
sizeof(BDIGIT));
3066 size_t len = BIGNUM_LEN(x);
3069 MEMCPY(BDIGITS(z), BDIGITS(x), BDIGIT,
len);
3074big_extend_carry(
VALUE x)
3076 rb_big_resize(x, BIGNUM_LEN(x)+1);
3077 BDIGITS(x)[BIGNUM_LEN(x)-1] = 1;
3084 long i = BIGNUM_LEN(x);
3085 BDIGIT *ds = BDIGITS(x);
3087 if (bary_2comp(ds, i)) {
3088 big_extend_carry(x);
3099abs2twocomp(
VALUE *xp,
long *n_ret)
3102 long n = BIGNUM_LEN(x);
3103 BDIGIT *ds = BDIGITS(x);
3108 if (n != 0 && BIGNUM_NEGATIVE_P(x)) {
3110 MEMCPY(BDIGITS(z), ds, BDIGIT, n);
3111 bary_2comp(BDIGITS(z), n);
3120twocomp2abs_bang(
VALUE x,
int hibits)
3122 BIGNUM_SET_SIGN(x, !hibits);
3131 size_t len = BIGNUM_LEN(x);
3132 BDIGIT *ds = BDIGITS(x);
3134 if (
len == 0)
return x;
3135 while (--
len && !ds[
len]);
3136 if (BIGNUM_LEN(x) >
len+1) {
3137 rb_big_resize(x,
len+1);
3145 size_t n = BIGNUM_LEN(x);
3146 BDIGIT *ds = BDIGITS(x);
3147#if SIZEOF_BDIGIT < SIZEOF_LONG
3155 if (n == 0)
return INT2FIX(0);
3157#if SIZEOF_BDIGIT < SIZEOF_LONG
3158 if (
sizeof(
long)/SIZEOF_BDIGIT < n)
3164 u = (
unsigned long)(BIGUP(u) + ds[i]);
3174 if (BIGNUM_POSITIVE_P(x)) {
3182 rb_big_resize(x, n);
3189 if (RB_BIGNUM_TYPE_P(x)) {
3202rb_uint2big(uintptr_t n)
3206 BDIGIT *digits = BDIGITS(big);
3208#if SIZEOF_BDIGIT >= SIZEOF_VALUE
3212 digits[i] = BIGLO(n);
3218 while (--i && !digits[i]) ;
3219 BIGNUM_SET_LEN(big, i+1);
3224rb_int2big(intptr_t n)
3231 u = 1 + (
VALUE)(-(n + 1));
3237 big = rb_uint2big(u);
3239 BIGNUM_SET_NEGATIVE_SIGN(big);
3245rb_uint2inum(uintptr_t n)
3248 return rb_uint2big(n);
3252rb_int2inum(intptr_t n)
3255 return rb_int2big(n);
3259rb_big_pack(
VALUE val,
unsigned long *buf,
long num_longs)
3261 rb_integer_pack(val, buf, num_longs,
sizeof(
long), 0,
3267rb_big_unpack(
unsigned long *buf,
long num_longs)
3269 return rb_integer_unpack(buf, num_longs,
sizeof(
long), 0,
3291rb_absint_size(
VALUE val,
int *nlz_bits_ret)
3295 BDIGIT fixbuf[bdigit_roomof(
sizeof(
long))];
3297 int num_leading_zeros;
3306#if SIZEOF_BDIGIT >= SIZEOF_LONG
3311 for (i = 0; i < numberof(fixbuf); i++) {
3312 fixbuf[i] = BIGLO(v);
3318 de = fixbuf + numberof(fixbuf);
3322 de = dp + BIGNUM_LEN(val);
3324 while (dp < de && de[-1] == 0)
3331 num_leading_zeros = nlz(de[-1]);
3333 *nlz_bits_ret = num_leading_zeros % CHAR_BIT;
3334 return (de - dp) * SIZEOF_BDIGIT - num_leading_zeros / CHAR_BIT;
3338absint_numwords_small(
size_t numbytes,
int nlz_bits_in_msbyte,
size_t word_numbits,
size_t *nlz_bits_ret)
3340 size_t val_numbits = numbytes * CHAR_BIT - nlz_bits_in_msbyte;
3341 size_t div = val_numbits / word_numbits;
3342 size_t mod = val_numbits % word_numbits;
3345 numwords = mod == 0 ? div : div + 1;
3346 nlz_bits = mod == 0 ? 0 : word_numbits - mod;
3347 *nlz_bits_ret = nlz_bits;
3352absint_numwords_generic(
size_t numbytes,
int nlz_bits_in_msbyte,
size_t word_numbits,
size_t *nlz_bits_ret)
3354 static const BDIGIT char_bit[1] = { CHAR_BIT };
3355 BDIGIT numbytes_bary[bdigit_roomof(
sizeof(numbytes))];
3356 BDIGIT val_numbits_bary[bdigit_roomof(
sizeof(numbytes) + 1)];
3357 BDIGIT nlz_bits_in_msbyte_bary[1];
3358 BDIGIT word_numbits_bary[bdigit_roomof(
sizeof(word_numbits))];
3359 BDIGIT div_bary[numberof(val_numbits_bary) + BIGDIVREM_EXTRA_WORDS];
3360 BDIGIT mod_bary[numberof(word_numbits_bary)];
3361 BDIGIT one[1] = { 1 };
3367 nlz_bits_in_msbyte_bary[0] = nlz_bits_in_msbyte;
3376 bary_unpack(BARY_ARGS(numbytes_bary), &numbytes, 1,
sizeof(numbytes), 0,
3378 BARY_SHORT_MUL(val_numbits_bary, numbytes_bary, char_bit);
3379 if (nlz_bits_in_msbyte)
3380 BARY_SUB(val_numbits_bary, val_numbits_bary, nlz_bits_in_msbyte_bary);
3381 bary_unpack(BARY_ARGS(word_numbits_bary), &word_numbits, 1,
sizeof(word_numbits), 0,
3383 BARY_DIVMOD(div_bary, mod_bary, val_numbits_bary, word_numbits_bary);
3384 if (BARY_ZERO_P(mod_bary)) {
3388 BARY_ADD(div_bary, div_bary, one);
3389 bary_pack(+1, BARY_ARGS(mod_bary), &mod, 1,
sizeof(mod), 0,
3391 nlz_bits = word_numbits - mod;
3393 sign = bary_pack(+1, BARY_ARGS(div_bary), &numwords, 1,
sizeof(numwords), 0,
3397#if defined __GNUC__ && (__GNUC__ == 4 && __GNUC_MINOR__ == 4)
3402 *nlz_bits_ret = nlz_bits;
3426rb_absint_numwords(
VALUE val,
size_t word_numbits,
size_t *nlz_bits_ret)
3429 int nlz_bits_in_msbyte;
3431 size_t nlz_bits = 0;
3433 if (word_numbits == 0)
3436 numbytes = rb_absint_size(val, &nlz_bits_in_msbyte);
3438 if (numbytes <= SIZE_MAX / CHAR_BIT) {
3439 numwords = absint_numwords_small(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits);
3440 if (debug_integer_pack) {
3441 size_t numwords0, nlz_bits0;
3442 numwords0 = absint_numwords_generic(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits0);
3449 numwords = absint_numwords_generic(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits);
3451 if (numwords == (
size_t)-1)
3455 *nlz_bits_ret = nlz_bits;
3493 BDIGIT fixbuf[bdigit_roomof(
sizeof(
long))];
3503#if SIZEOF_BDIGIT >= SIZEOF_LONG
3508 for (i = 0; i < numberof(fixbuf); i++) {
3509 fixbuf[i] = BIGLO(v);
3515 de = fixbuf + numberof(fixbuf);
3519 de = dp + BIGNUM_LEN(val);
3521 while (dp < de && de[-1] == 0)
3523 while (dp < de && dp[0] == 0)
3590rb_integer_pack(
VALUE val,
void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
3595 BDIGIT fixbuf[bdigit_roomof(
sizeof(
long))];
3608#if SIZEOF_BDIGIT >= SIZEOF_LONG
3613 for (i = 0; i < numberof(fixbuf); i++) {
3614 fixbuf[i] = BIGLO(v);
3620 num_bdigits = numberof(fixbuf);
3623 sign = BIGNUM_POSITIVE_P(val) ? 1 : -1;
3625 num_bdigits = BIGNUM_LEN(val);
3628 return bary_pack(sign, ds, num_bdigits, words, numwords, wordsize, nails, flags);
3676rb_integer_unpack(
const void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
3683 BDIGIT fixbuf[2] = { 0, 0 };
3685 validate_integer_pack_format(numwords, wordsize, nails, flags,
3696 num_bdigits = integer_unpack_num_bdigits(numwords, wordsize, nails, &nlp_bits);
3698 if (LONG_MAX-1 < num_bdigits)
3699 rb_raise(rb_eArgError,
"too big to unpack as an integer");
3705 val = bignew((
long)num_bdigits, 0);
3708 sign = bary_unpack_internal(ds, num_bdigits, words, numwords, wordsize, nails, flags, nlp_bits);
3712 big_extend_carry(val);
3714 else if (num_bdigits == numberof(fixbuf)) {
3715 val = bignew((
long)num_bdigits+1, 0);
3716 MEMCPY(BDIGITS(val), fixbuf, BDIGIT, num_bdigits);
3717 BDIGITS(val)[num_bdigits++] = 1;
3720 ds[num_bdigits++] = 1;
3725 BDIGIT_DBL u = fixbuf[0] + BIGUP(fixbuf[1]);
3730 if (sign < 0 && BDIGIT_MSB(fixbuf[1]) == 0 &&
3732 return LONG2FIX((
long)-(BDIGIT_DBL_SIGNED)u);
3733 val = bignew((
long)num_bdigits, 0 <= sign);
3734 MEMCPY(BDIGITS(val), fixbuf, BDIGIT, num_bdigits);
3738 bary_zero_p(BDIGITS(val), BIGNUM_LEN(val)))
3740 BIGNUM_SET_SIGN(val, 0 <= sign);
3743 return bigtrunc(val);
3744 return bignorm(val);
3747#define conv_digit(c) (ruby_digit36_to_number_table[(unsigned char)(c)])
3749NORETURN(
static inline void invalid_radix(
int base));
3750NORETURN(
static inline void invalid_integer(
VALUE s));
3753valid_radix_p(
int base)
3755 return (1 < base && base <= 36);
3759invalid_radix(
int base)
3761 rb_raise(rb_eArgError,
"invalid radix %d", base);
3765invalid_integer(
VALUE s)
3767 rb_raise(rb_eArgError,
"invalid value for Integer(): %+"PRIsVALUE, s);
3771str2big_scan_digits(
const char *s,
const char *str,
int base,
int badcheck,
size_t *num_digits_p, ssize_t *len_p)
3774 size_t num_digits = 0;
3775 const char *digits_start = str;
3776 const char *digits_end = str;
3777 ssize_t
len = *len_p;
3787 if (badcheck && *str ==
'_')
return FALSE;
3789 while ((c = *str++) != 0) {
3792 if (badcheck)
return FALSE;
3795 nondigit = (char) c;
3797 else if ((c = conv_digit(c)) < 0 || c >= base) {
3805 if (
len > 0 && !--
len)
break;
3807 if (badcheck && nondigit)
return FALSE;
3808 if (badcheck &&
len) {
3810 while (*str &&
ISSPACE(*str)) {
3812 if (
len > 0 && !--
len)
break;
3818 *num_digits_p = num_digits;
3819 *len_p = digits_end - digits_start;
3826 const char *digits_start,
3827 const char *digits_end,
3840 num_bdigits = (num_digits / BITSPERDIG) * bits_per_digit + roomof((num_digits % BITSPERDIG) * bits_per_digit, BITSPERDIG);
3841 z = bignew(num_bdigits, sign);
3845 for (p = digits_end; digits_start < p; p--) {
3846 if ((c = conv_digit(p[-1])) < 0)
3848 dd |= (BDIGIT_DBL)c << numbits;
3849 numbits += bits_per_digit;
3850 if (BITSPERDIG <= numbits) {
3853 numbits -= BITSPERDIG;
3859 RUBY_ASSERT((
size_t)(dp - BDIGITS(z)) == num_bdigits);
3867 const char *digits_start,
3868 const char *digits_end,
3881 z = bignew(num_bdigits, sign);
3883 BDIGITS_ZERO(zds, num_bdigits);
3885 for (p = digits_start; p < digits_end; p++) {
3886 if ((c = conv_digit(*p)) < 0)
3892 num += (BDIGIT_DBL)zds[i]*base;
3893 zds[i++] = BIGLO(num);
3911 const char *digits_start,
3912 const char *digits_end,
3915 int digits_per_bdigits_dbl,
3921 BDIGIT *uds, *vds, *tds;
3923 BDIGIT_DBL current_base;
3925 int power_level = 0;
3932 uds =
ALLOCV_N(BDIGIT, tmpuv, 2*num_bdigits);
3933 vds = uds + num_bdigits;
3935 powerv = power_cache_get_power(base, power_level, NULL);
3940 m = digits_per_bdigits_dbl;
3941 if (num_digits < (
size_t)m)
3942 m = (int)num_digits;
3943 for (p = digits_end; digits_start < p; p--) {
3944 if ((c = conv_digit(p[-1])) < 0)
3946 dd = dd + c * current_base;
3947 current_base *= base;
3951 uds[i++] = BIGLO(dd);
3952 uds[i++] = (BDIGIT)BIGDN(dd);
3954 m = digits_per_bdigits_dbl;
3955 if (num_digits < (
size_t)m)
3956 m = (
int)num_digits;
3961 for (unit = 2; unit < num_bdigits; unit *= 2) {
3962 for (i = 0; i < num_bdigits; i += unit*2) {
3963 if (2*unit <= num_bdigits - i) {
3964 bary_mul(vds+i, unit*2, BDIGITS(powerv), BIGNUM_LEN(powerv), uds+i+unit, unit);
3965 bary_add(vds+i, unit*2, vds+i, unit*2, uds+i, unit);
3967 else if (unit <= num_bdigits - i) {
3968 bary_mul(vds+i, num_bdigits-i, BDIGITS(powerv), BIGNUM_LEN(powerv), uds+i+unit, num_bdigits-(i+unit));
3969 bary_add(vds+i, num_bdigits-i, vds+i, num_bdigits-i, uds+i, unit);
3972 MEMCPY(vds+i, uds+i, BDIGIT, num_bdigits-i);
3976 powerv = power_cache_get_power(base, power_level, NULL);
3981 BARY_TRUNC(uds, num_bdigits);
3982 z = bignew(num_bdigits, sign);
3983 MEMCPY(BDIGITS(z), uds, BDIGIT, num_bdigits);
3995 const char *digits_start,
3996 const char *digits_end,
4009 buf =
ALLOCV_N(
char, tmps, num_digits+1);
4011 for (q = digits_start; q < digits_end; q++) {
4012 if (conv_digit(*q) < 0)
4019 mpz_set_str(mz, buf, base);
4021 z = bignew(zn, sign);
4023 bdigits_from_mpz(mz, BDIGITS(z), &count);
4024 BDIGITS_ZERO(zds+count, zn-count);
4034static VALUE rb_cstr_parse_inum(
const char *str, ssize_t
len,
char **endp,
int base);
4053rb_cstr_to_inum(
const char *str,
int base,
int badcheck)
4056 VALUE ret = rb_cstr_parse_inum(str, -1, (badcheck ? NULL : &end), base);
4082rb_int_parse_cstr(
const char *str, ssize_t
len,
char **endp,
size_t *ndigits,
4083 int base,
int flags)
4085 const char *
const s = str;
4093 const char *digits_start, *digits_end;
4094 size_t num_digits = 0;
4096 const ssize_t len0 =
len;
4097 const int badcheck = !endp;
4100 if (len > 0 && len <= (n)) goto bad; \
4104#define ASSERT_LEN() do {\
4105 RUBY_ASSERT(len != 0); \
4106 if (len0 >= 0) RUBY_ASSERT(s + len0 == str + len); \
4112 if (
len && (flags & RB_INT_PARSE_SIGN)) {
4115 if (str[0] ==
'+') {
4118 else if (str[0] ==
'-') {
4125 if (str[0] ==
'0' &&
len > 1) {
4147 else if (base < -1) {
4154 else if (
len == 1 || !(flags & RB_INT_PARSE_PREFIX)) {
4157 else if (base == 2) {
4158 if (str[0] ==
'0' && (str[1] ==
'b'||str[1] ==
'B')) {
4162 else if (base == 8) {
4163 if (str[0] ==
'0' && (str[1] ==
'o'||str[1] ==
'O')) {
4167 else if (base == 10) {
4168 if (str[0] ==
'0' && (str[1] ==
'd'||str[1] ==
'D')) {
4172 else if (base == 16) {
4173 if (str[0] ==
'0' && (str[1] ==
'x'||str[1] ==
'X')) {
4177 if (!valid_radix_p(base)) {
4178 invalid_radix(base);
4181 num_digits = str - s;
4182 if (*str ==
'0' &&
len != 1) {
4184 const char *end =
len < 0 ? NULL : str +
len;
4186 while ((c = *++str) ==
'0' ||
4187 ((flags & RB_INT_PARSE_UNDERSCORE) && c ==
'_')) {
4196 if (str == end)
break;
4199 if (end)
len = end - str;
4203 if (c < 0 || c >= base) {
4204 if (!badcheck && num_digits) z =
INT2FIX(0);
4208 if (ndigits) *ndigits = num_digits;
4209 val = ruby_scan_digits(str,
len, base, &num_digits, &ov);
4211 const char *end = &str[num_digits];
4212 if (num_digits > 0 && *end ==
'_' && (flags & RB_INT_PARSE_UNDERSCORE))
4214 if (endp) *endp = (
char *)end;
4215 if (ndigits) *ndigits += num_digits;
4217 if (num_digits == 0)
return Qnil;
4218 while (
len < 0 ? *end : end < str +
len) {
4227 long result = -(long)val;
4232 VALUE big = rb_uint2big(val);
4233 BIGNUM_SET_SIGN(big, sign);
4234 return bignorm(big);
4240 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4242 if (endp) *endp = (
char *)(str +
len);
4243 if (ndigits) *ndigits += num_digits;
4244 digits_end = digits_start +
len;
4247 z = str2big_poweroftwo(sign, digits_start, digits_end, num_digits,
4248 bit_length(base-1));
4251 int digits_per_bdigits_dbl;
4252 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4253 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4256 if (GMP_STR2BIG_DIGITS < num_bdigits) {
4257 z = str2big_gmp(sign, digits_start, digits_end, num_digits,
4262 if (num_bdigits < KARATSUBA_MUL_DIGITS) {
4263 z = str2big_normal(sign, digits_start, digits_end,
4267 z = str2big_karatsuba(sign, digits_start, digits_end, num_digits,
4268 num_bdigits, digits_per_bdigits_dbl, base);
4275 if (endp) *endp = (
char *)str;
4276 if (ndigits) *ndigits = num_digits;
4281rb_cstr_parse_inum(
const char *str, ssize_t
len,
char **endp,
int base)
4283 return rb_int_parse_cstr(str,
len, endp, NULL, base,
4284 RB_INT_PARSE_DEFAULT);
4288rb_str_convert_to_inum(
VALUE str,
int base,
int badcheck,
int raise_exception)
4298 ret = rb_cstr_parse_inum(s,
len, (badcheck ? NULL : &end), base);
4301 if (!raise_exception)
return Qnil;
4302 invalid_integer(str);
4310rb_str_to_inum(
VALUE str,
int base,
int badcheck)
4312 return rb_str_convert_to_inum(str, base, badcheck, TRUE);
4316rb_str2big_poweroftwo(
VALUE arg,
int base,
int badcheck)
4319 const char *s, *str;
4320 const char *digits_start, *digits_end;
4325 if (!valid_radix_p(base) || !POW2_P(base)) {
4326 invalid_radix(base);
4331 len = RSTRING_LEN(arg);
4339 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4340 invalid_integer(arg);
4341 digits_end = digits_start +
len;
4343 z = str2big_poweroftwo(positive_p, digits_start, digits_end, num_digits,
4344 bit_length(base-1));
4352rb_str2big_normal(
VALUE arg,
int base,
int badcheck)
4355 const char *s, *str;
4356 const char *digits_start, *digits_end;
4361 int digits_per_bdigits_dbl;
4364 if (!valid_radix_p(base)) {
4365 invalid_radix(base);
4370 len = RSTRING_LEN(arg);
4371 if (
len > 0 && *str ==
'-') {
4378 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4379 invalid_integer(arg);
4380 digits_end = digits_start +
len;
4382 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4383 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4385 z = str2big_normal(positive_p, digits_start, digits_end,
4394rb_str2big_karatsuba(
VALUE arg,
int base,
int badcheck)
4397 const char *s, *str;
4398 const char *digits_start, *digits_end;
4403 int digits_per_bdigits_dbl;
4406 if (!valid_radix_p(base)) {
4407 invalid_radix(base);
4412 len = RSTRING_LEN(arg);
4413 if (
len > 0 && *str ==
'-') {
4420 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4421 invalid_integer(arg);
4422 digits_end = digits_start +
len;
4424 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4425 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4427 z = str2big_karatsuba(positive_p, digits_start, digits_end, num_digits,
4428 num_bdigits, digits_per_bdigits_dbl, base);
4437rb_str2big_gmp(
VALUE arg,
int base,
int badcheck)
4440 const char *s, *str;
4441 const char *digits_start, *digits_end;
4446 int digits_per_bdigits_dbl;
4449 if (!valid_radix_p(base)) {
4450 invalid_radix(base);
4455 len = RSTRING_LEN(arg);
4456 if (
len > 0 && *str ==
'-') {
4463 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4464 invalid_integer(arg);
4465 digits_end = digits_start +
len;
4467 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4468 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4470 z = str2big_gmp(positive_p, digits_start, digits_end, num_digits, num_bdigits, base);
4484 VALUE big = bignew(bdigit_roomof(SIZEOF_LONG_LONG), 1);
4485 BDIGIT *digits = BDIGITS(big);
4487#if SIZEOF_BDIGIT >= SIZEOF_LONG_LONG
4490 for (i = 0; i < bdigit_roomof(SIZEOF_LONG_LONG); i++) {
4491 digits[i] = BIGLO(n);
4496 i = bdigit_roomof(SIZEOF_LONG_LONG);
4497 while (i-- && !digits[i]) ;
4498 BIGNUM_SET_LEN(big, i+1);
4516 big = rb_ull2big(u);
4518 BIGNUM_SET_NEGATIVE_SIGN(big);
4527 return rb_ull2big(n);
4534 return rb_ll2big(n);
4541rb_uint128t2big(uint128_t n)
4544 VALUE big = bignew(bdigit_roomof(SIZEOF_INT128_T), 1);
4545 BDIGIT *digits = BDIGITS(big);
4547 for (i = 0; i < bdigit_roomof(SIZEOF_INT128_T); i++) {
4548 digits[i] = BIGLO(RSHIFT(n ,BITSPERDIG*i));
4551 i = bdigit_roomof(SIZEOF_INT128_T);
4552 while (i-- && !digits[i]) ;
4553 BIGNUM_SET_LEN(big, i+1);
4558rb_int128t2big(int128_t n)
4565 u = 1 + (uint128_t)(-(n + 1));
4571 big = rb_uint128t2big(u);
4573 BIGNUM_SET_NEGATIVE_SIGN(big);
4580rb_cstr2inum(
const char *str,
int base)
4582 return rb_cstr_to_inum(str, base, base==0);
4588 return rb_str_to_inum(str, base, base==0);
4592big_shift3(
VALUE x,
int lshift_p,
size_t shift_numdigits,
int shift_numbits)
4601 if (LONG_MAX < shift_numdigits) {
4605 s1 = shift_numdigits;
4607 if ((
size_t)s1 != shift_numdigits)
goto too_big;
4609 if (LONG_MAX/SIZEOF_BDIGIT <= xn+s1)
goto too_big;
4610 z = bignew(xn+s1+1, BIGNUM_SIGN(x));
4612 BDIGITS_ZERO(zds, s1);
4614 zds[xn+s1] = bary_small_lshift(zds+s1, xds, xn, s2);
4619 if (LONG_MAX < shift_numdigits || (
size_t)BIGNUM_LEN(x) <= shift_numdigits) {
4620 if (BIGNUM_POSITIVE_P(x) ||
4621 bary_zero_p(BDIGITS(x), BIGNUM_LEN(x)))
4626 s1 = shift_numdigits;
4628 hibitsx = abs2twocomp(&x, &xn);
4636 bary_small_rshift(zds, xds+s1, zn, s2, hibitsx != 0 ? BDIGMAX : 0);
4637 twocomp2abs_bang(z, hibitsx != 0);
4648 size_t shift_numdigits;
4656 sign = rb_integer_pack(y, lens, numberof(lens),
sizeof(
size_t), 0,
4659 lshift_p = !lshift_p;
4663 if (1 < sign || CHAR_BIT <= lens[1])
4667 if (1 < sign || CHAR_BIT <= lens[1])
4670 shift_numbits = (int)(lens[0] & (BITSPERDIG-1));
4671 shift_numdigits = (lens[0] >> bit_length(BITSPERDIG-1)) |
4672 (lens[1] << (CHAR_BIT*SIZEOF_SIZE_T - bit_length(BITSPERDIG-1)));
4673 return big_shift3(x, lshift_p, shift_numdigits, shift_numbits);
4677big_lshift(
VALUE x,
unsigned long shift)
4679 long s1 = shift/BITSPERDIG;
4680 int s2 = (int)(shift%BITSPERDIG);
4681 return big_shift3(x, 1, s1, s2);
4685big_rshift(
VALUE x,
unsigned long shift)
4687 long s1 = shift/BITSPERDIG;
4688 int s2 = (int)(shift%BITSPERDIG);
4689 return big_shift3(x, 0, s1, s2);
4692#define MAX_BASE36_POWER_TABLE_ENTRIES (SIZEOF_SIZE_T * CHAR_BIT + 1)
4694static VALUE base36_power_cache[35][MAX_BASE36_POWER_TABLE_ENTRIES];
4695static size_t base36_numdigits_cache[35][MAX_BASE36_POWER_TABLE_ENTRIES];
4698power_cache_init(
void)
4703power_cache_get_power(
int base,
int power_level,
size_t *numdigits_ret)
4719 if (MAX_BASE36_POWER_TABLE_ENTRIES <= power_level)
4720 rb_bug(
"too big power number requested: maxpow_in_bdigit_dbl(%d)**(2**%d)", base, power_level);
4722 VALUE power = base36_power_cache[base - 2][power_level];
4725 if (power_level == 0) {
4727 BDIGIT_DBL dd = maxpow_in_bdigit_dbl(base, &numdigits0);
4728 power = bignew(2, 1);
4729 bdigitdbl2bary(BDIGITS(power), 2, dd);
4730 numdigits = numdigits0;
4733 power = bigtrunc(bigsq(power_cache_get_power(base, power_level - 1, &numdigits)));
4737 base36_power_cache[base - 2][power_level] = power;
4738 base36_numdigits_cache[base - 2][power_level] = numdigits;
4739 rb_vm_register_global_object(power);
4742 *numdigits_ret = base36_numdigits_cache[base - 2][power_level];
4750 int hbase2_numdigits;
4758 if (LONG_MAX-1 <
len)
4759 rb_raise(rb_eArgError,
"too big number");
4761 b2s->ptr = RSTRING_PTR(b2s->result);
4767big2str_2bdigits(
struct big2str_struct *b2s, BDIGIT *xds,
size_t xn,
size_t taillen)
4771 char buf[SIZEOF_BDIGIT_DBL*CHAR_BIT], *p;
4772 int beginning = !b2s->ptr;
4776 num = bary2bdigitdbl(xds, xn);
4784 BDIGIT_DBL idx = num % b2s->base;
4786 p[--j] = ruby_digitmap[idx];
4788 len =
sizeof(buf) - j;
4789 big2str_alloc(b2s,
len + taillen);
4794 j = b2s->hbase2_numdigits;
4796 BDIGIT_DBL idx = num % b2s->base;
4798 p[--j] = ruby_digitmap[idx];
4800 len = b2s->hbase2_numdigits;
4806big2str_karatsuba(
struct big2str_struct *b2s, BDIGIT *xds,
size_t xn,
size_t wn,
4807 int power_level,
size_t taillen)
4810 size_t half_numdigits, lower_numdigits;
4811 int lower_power_level;
4836 if (xn == 0 || bary_zero_p(xds, xn)) {
4839 power_cache_get_power(b2s->base, power_level, &
len);
4840 memset(b2s->ptr,
'0',
len);
4846 if (power_level == 0) {
4847 big2str_2bdigits(b2s, xds, xn, taillen);
4851 lower_power_level = power_level-1;
4852 b = power_cache_get_power(b2s->base, lower_power_level, &lower_numdigits);
4856 half_numdigits = lower_numdigits;
4858 while (0 < lower_power_level &&
4860 (xn == bn && bary_cmp(xds, xn, bds, bn) < 0))) {
4861 lower_power_level--;
4862 b = power_cache_get_power(b2s->base, lower_power_level, &lower_numdigits);
4867 if (lower_power_level == 0 &&
4869 (xn == bn && bary_cmp(xds, xn, bds, bn) < 0))) {
4871 len = half_numdigits * 2 - lower_numdigits;
4872 memset(b2s->ptr,
'0',
len);
4875 big2str_2bdigits(b2s, xds, xn, taillen);
4883 if (lower_power_level != power_level-1 && b2s->ptr) {
4884 len = (half_numdigits - lower_numdigits) * 2;
4885 memset(b2s->ptr,
'0',
len);
4889 shift = nlz(bds[bn-1]);
4891 qn = xn + BIGDIVREM_EXTRA_WORDS;
4896 tds = (BDIGIT *)bds;
4904 bary_small_lshift(tds, bds, bn, shift);
4905 xds[xn] = bary_small_lshift(xds, xds, xn, shift);
4908 bigdivrem_restoring(xds, qn, tds, bn);
4917 bary_small_rshift(rds, rds, rn, shift, 0);
4920 BARY_TRUNC(qds, qn);
4922 big2str_karatsuba(b2s, qds, qn, xn+wn - (rn+qn), lower_power_level, lower_numdigits+taillen);
4923 BARY_TRUNC(rds, rn);
4924 big2str_karatsuba(b2s, rds, rn, xn+wn - rn, lower_power_level, taillen);
4929big2str_base_poweroftwo(
VALUE x,
int base)
4931 int word_numbits = ffs(base) - 1;
4935 numwords = rb_absint_numwords(x, word_numbits, NULL);
4936 if (BIGNUM_NEGATIVE_P(x)) {
4937 if (LONG_MAX-1 < numwords)
4938 rb_raise(rb_eArgError,
"too big number");
4940 ptr = RSTRING_PTR(result);
4941 *ptr++ = BIGNUM_POSITIVE_P(x) ?
'+' :
'-';
4944 if (LONG_MAX < numwords)
4945 rb_raise(rb_eArgError,
"too big number");
4947 ptr = RSTRING_PTR(result);
4949 rb_integer_pack(x, ptr, numwords, 1, CHAR_BIT-word_numbits,
4951 while (0 < numwords) {
4952 *ptr = ruby_digitmap[*(
unsigned char *)ptr];
4960rb_big2str_poweroftwo(
VALUE x,
int base)
4962 return big2str_base_poweroftwo(x, base);
4966big2str_generic(
VALUE x,
int base)
4976 BARY_TRUNC(xds, xn);
4982 if (!valid_radix_p(base))
4983 invalid_radix(base);
4985 if (xn >= LONG_MAX/BITSPERDIG) {
4986 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'string'");
4990 power = power_cache_get_power(base, power_level, NULL);
4991 while (power_level < MAX_BASE36_POWER_TABLE_ENTRIES &&
4992 (
size_t)BIGNUM_LEN(power) <= (xn+1)/2) {
4994 power = power_cache_get_power(base, power_level, NULL);
4996 RUBY_ASSERT(power_level != MAX_BASE36_POWER_TABLE_ENTRIES);
4998 if ((
size_t)BIGNUM_LEN(power) <= xn) {
5012 b2s_data.negative = BIGNUM_NEGATIVE_P(x);
5013 b2s_data.base = base;
5014 b2s_data.hbase2 = maxpow_in_bdigit_dbl(base, &b2s_data.hbase2_numdigits);
5016 b2s_data.result =
Qnil;
5017 b2s_data.ptr = NULL;
5019 if (power_level == 0) {
5020 big2str_2bdigits(&b2s_data, xds, xn, 0);
5026 wn = power_level * BIGDIVREM_EXTRA_WORDS + BIGNUM_LEN(power);
5027 wds =
ALLOCV_N(BDIGIT, tmpw, xn + wn);
5028 MEMCPY(wds, xds, BDIGIT, xn);
5029 big2str_karatsuba(&b2s_data, wds, xn, wn, power_level, 0);
5035 *b2s_data.ptr =
'\0';
5036 rb_str_resize(b2s_data.result, (
long)(b2s_data.ptr - RSTRING_PTR(b2s_data.result)));
5039 return b2s_data.result;
5043rb_big2str_generic(
VALUE x,
int base)
5045 return big2str_generic(x, base);
5050big2str_gmp(
VALUE x,
int base)
5055 BDIGIT *xds = BDIGITS(x);
5056 size_t xn = BIGNUM_LEN(x);
5059 bdigits_to_mpz(mx, xds, xn);
5061 size = mpz_sizeinbase(mx, base);
5063 if (BIGNUM_NEGATIVE_P(x)) {
5070 mpz_get_str(RSTRING_PTR(str), base, mx);
5073 if (RSTRING_PTR(str)[RSTRING_LEN(str)-1] ==
'\0') {
5082rb_big2str_gmp(
VALUE x,
int base)
5084 return big2str_gmp(x, base);
5089rb_big2str1(
VALUE x,
int base)
5101 BARY_TRUNC(xds, xn);
5107 if (!valid_radix_p(base))
5108 invalid_radix(base);
5110 if (xn >= LONG_MAX/BITSPERDIG) {
5111 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'string'");
5116 return big2str_base_poweroftwo(x, base);
5120 if (GMP_BIG2STR_DIGITS < xn) {
5121 return big2str_gmp(x, base);
5125 return big2str_generic(x, base);
5131 return rb_big2str1(x, base);
5137#if SIZEOF_LONG > SIZEOF_BDIGIT
5140 size_t len = BIGNUM_LEN(x);
5146 if (BIGSIZE(x) >
sizeof(
long)) {
5150#if SIZEOF_LONG <= SIZEOF_BDIGIT
5151 num = (
unsigned long)ds[0];
5154 for (i = 0; i <
len; i++) {
5156 num += (
unsigned long)ds[
len - i - 1];
5165 unsigned long num = big2ulong(x,
"unsigned long");
5167 if (BIGNUM_POSITIVE_P(x)) {
5171 if (num <= 1+(
unsigned long)(-(LONG_MIN+1)))
5172 return -(long)(num-1)-1;
5174 rb_raise(
rb_eRangeError,
"bignum out of range of unsigned long");
5180 unsigned long num = big2ulong(x,
"long");
5182 if (BIGNUM_POSITIVE_P(x)) {
5183 if (num <= LONG_MAX)
5187 if (num <= 1+(
unsigned long)(-(LONG_MIN+1)))
5188 return -(long)(num-1)-1;
5190 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'long'");
5198#if SIZEOF_LONG_LONG > SIZEOF_BDIGIT
5201 size_t len = BIGNUM_LEN(x);
5203 BDIGIT *ds = BDIGITS(x);
5207 if (BIGSIZE(x) > SIZEOF_LONG_LONG)
5209#if SIZEOF_LONG_LONG <= SIZEOF_BDIGIT
5213 for (i = 0; i <
len; i++) {
5215 num += ds[
len - i - 1];
5224 unsigned LONG_LONG num = big2ull(x,
"unsigned long long");
5226 if (BIGNUM_POSITIVE_P(x)) {
5230 if (num <= 1+(
unsigned LONG_LONG)(-(LLONG_MIN+1)))
5233 rb_raise(
rb_eRangeError,
"bignum out of range of unsigned long long");
5239 unsigned LONG_LONG num = big2ull(x,
"long long");
5241 if (BIGNUM_POSITIVE_P(x)) {
5242 if (num <= LLONG_MAX)
5246 if (num <= 1+(
unsigned LONG_LONG)(-(LLONG_MIN+1)))
5249 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'long long'");
5261 double u = (d < 0)?-d:d;
5271 u /= (double)(BIGRAD);
5274 z = bignew(i, d>=0);
5275 digits = BDIGITS(z);
5289 return bignorm(dbl2big(d));
5296 long i = (bigtrunc(x), BIGNUM_LEN(x)), lo = 0, bits;
5297 BDIGIT *ds = BDIGITS(x), dl;
5300 bits = i * BITSPERDIG - nlz(ds[i-1]);
5301 if (bits > DBL_MANT_DIG+DBL_MAX_EXP) {
5305 if (bits > DBL_MANT_DIG+1)
5306 lo = (bits -= DBL_MANT_DIG+1) / BITSPERDIG;
5310 d = ds[i] + BIGRAD*d;
5313 if (bits && (dl & ((BDIGIT)1 << (bits %= BITSPERDIG)))) {
5314 int carry = (dl & ~(BDIGMAX << bits)) != 0;
5322 BDIGIT mask = BDIGMAX;
5334 if (lo > INT_MAX / BITSPERDIG)
5336 else if (lo < INT_MIN / BITSPERDIG)
5339 d = ldexp(d, (
int)(lo * BITSPERDIG));
5343 if (BIGNUM_NEGATIVE_P(x)) d = -d;
5350 double d = big2dbl(x);
5372 if (yd > 0.0)
return INT2FIX(-1);
5377#if SIZEOF_LONG * CHAR_BIT < DBL_MANT_DIG
5404 rel = rb_big_cmp(x, y);
5405 if (yf == 0.0 || rel !=
INT2FIX(0))
5412#if SIZEOF_LONG * CHAR_BIT >= DBL_MANT_DIG
5413COMPILER_WARNING_PUSH
5414#if __has_warning("-Wimplicit-int-float-conversion")
5415COMPILER_WARNING_IGNORED(-Wimplicit-
int-
float-conversion)
5417static const double LONG_MAX_as_double = LONG_MAX;
5433#if SIZEOF_LONG * CHAR_BIT < DBL_MANT_DIG
5435 return RBOOL(xd == yd);
5438 if (yi < LONG_MIN || LONG_MAX_as_double <= yi)
5442 return RBOOL(xn == yn);
5446 return rb_big_eq(x, y);
5459 if (sx < sy)
return INT2FIX(-1);
5463 else if (RB_BIGNUM_TYPE_P(y)) {
5464 if (BIGNUM_SIGN(x) == BIGNUM_SIGN(y)) {
5465 int cmp = bary_cmp(BDIGITS(x), BIGNUM_LEN(x), BDIGITS(y), BIGNUM_LEN(y));
5466 return INT2FIX(BIGNUM_SIGN(x) ? cmp : -cmp);
5470 return rb_integer_float_cmp(x, y);
5475 return INT2FIX(BIGNUM_SIGN(x) ? 1 : -1);
5492 rel = rb_big_cmp(x, y);
5495 rel = rb_integer_float_cmp(x, y);
5500 case big_op_gt:
id =
'>';
break;
5501 case big_op_ge:
id = idGE;
break;
5502 case big_op_lt:
id =
'<';
break;
5503 case big_op_le:
id = idLE;
break;
5512 case big_op_gt:
return RBOOL(n > 0);
5513 case big_op_ge:
return RBOOL(n >= 0);
5514 case big_op_lt:
return RBOOL(n < 0);
5515 case big_op_le:
return RBOOL(n <= 0);
5523 return big_op(x, y, big_op_gt);
5529 return big_op(x, y, big_op_ge);
5535 return big_op(x, y, big_op_lt);
5541 return big_op(x, y, big_op_le);
5559 return RBOOL(bignorm(x) == y);
5561 else if (RB_BIGNUM_TYPE_P(y)) {
5564 return rb_integer_float_eq(x, y);
5569 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y))
return Qfalse;
5570 if (BIGNUM_LEN(x) != BIGNUM_LEN(y))
return Qfalse;
5571 return RBOOL(
MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,BIGNUM_LEN(y)) == 0);
5577 if (!RB_BIGNUM_TYPE_P(y))
return Qfalse;
5578 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y))
return Qfalse;
5579 if (BIGNUM_LEN(x) != BIGNUM_LEN(y))
return Qfalse;
5580 return RBOOL(
MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,BIGNUM_LEN(y)) == 0);
5584rb_big_uminus(
VALUE x)
5586 VALUE z = rb_big_clone(x);
5596 VALUE z = rb_big_clone(x);
5597 BDIGIT *ds = BDIGITS(z);
5598 long n = BIGNUM_LEN(z);
5602 if (BIGNUM_POSITIVE_P(z)) {
5603 if (bary_add_one(ds, n)) {
5604 big_extend_carry(z);
5606 BIGNUM_SET_NEGATIVE_SIGN(z);
5610 if (bary_add_one(ds, n))
5613 BIGNUM_SET_POSITIVE_SIGN(z);
5623 BDIGIT *xds, *yds, *zds;
5628 zn = xn < yn ? yn : xn;
5636 if (bary_sub(zds, zn, xds, xn, yds, yn)) {
5637 bary_2comp(zds, zn);
5638 BIGNUM_SET_NEGATIVE_SIGN(z);
5647bigsub_int(
VALUE x,
long y0)
5652 BDIGIT_DBL_SIGNED num;
5663#if SIZEOF_BDIGIT < SIZEOF_LONG
5664 if (zn < bdigit_roomof(SIZEOF_LONG))
5665 zn = bdigit_roomof(SIZEOF_LONG);
5667 z = bignew(zn, BIGNUM_SIGN(x));
5670#if SIZEOF_BDIGIT >= SIZEOF_LONG
5672 num = (BDIGIT_DBL_SIGNED)xds[0] - y;
5673 if (xn == 1 && num < 0) {
5675 zds[0] = (BDIGIT)-num;
5679 zds[0] = BIGLO(num);
5687 for (i=0; i < xn; i++) {
5688 if (y == 0)
goto y_is_zero_x;
5689 num += (BDIGIT_DBL_SIGNED)xds[i] - BIGLO(y);
5690 zds[i] = BIGLO(num);
5694 for (; i < zn; i++) {
5695 if (y == 0)
goto y_is_zero_z;
5697 zds[i] = BIGLO(num);
5704 for (; i < xn; i++) {
5706 if (num == 0)
goto num_is_zero_x;
5708 zds[i] = BIGLO(num);
5711#if SIZEOF_BDIGIT < SIZEOF_LONG
5712 for (; i < zn; i++) {
5714 if (num == 0)
goto num_is_zero_z;
5715 zds[i] = BIGLO(num);
5721 for (; i < xn; i++) {
5725#if SIZEOF_BDIGIT < SIZEOF_LONG
5726 for (; i < zn; i++) {
5744bigadd_int(
VALUE x,
long y)
5759#if SIZEOF_BDIGIT < SIZEOF_LONG
5760 if (zn < bdigit_roomof(SIZEOF_LONG))
5761 zn = bdigit_roomof(SIZEOF_LONG);
5765 z = bignew(zn, BIGNUM_SIGN(x));
5768#if SIZEOF_BDIGIT >= SIZEOF_LONG
5769 num = (BDIGIT_DBL)xds[0] + y;
5770 zds[0] = BIGLO(num);
5778 for (i=0; i < xn; i++) {
5779 if (y == 0)
goto y_is_zero_x;
5780 num += (BDIGIT_DBL)xds[i] + BIGLO(y);
5781 zds[i] = BIGLO(num);
5785 for (; i < zn; i++) {
5786 if (y == 0)
goto y_is_zero_z;
5788 zds[i] = BIGLO(num);
5796 for (;i < xn; i++) {
5798 if (num == 0)
goto num_is_zero_x;
5799 num += (BDIGIT_DBL)xds[i];
5800 zds[i] = BIGLO(num);
5803 for (; i < zn; i++) {
5805 if (num == 0)
goto num_is_zero_z;
5806 zds[i] = BIGLO(num);
5811 for (;i < xn; i++) {
5815 for (; i < zn; i++) {
5832 sign = (sign == BIGNUM_SIGN(y));
5833 if (BIGNUM_SIGN(x) != sign) {
5834 if (sign)
return bigsub(y, x);
5835 return bigsub(x, y);
5838 if (BIGNUM_LEN(x) > BIGNUM_LEN(y)) {
5839 len = BIGNUM_LEN(x) + 1;
5842 len = BIGNUM_LEN(y) + 1;
5844 z = bignew(
len, sign);
5846 bary_add(BDIGITS(z), BIGNUM_LEN(z),
5847 BDIGITS(x), BIGNUM_LEN(x),
5848 BDIGITS(y), BIGNUM_LEN(y));
5860 if ((n > 0) != BIGNUM_SIGN(x)) {
5864 return bigsub_int(x, n);
5869 return bigadd_int(x, n);
5871 else if (RB_BIGNUM_TYPE_P(y)) {
5872 return bignorm(bigadd(x, y, 1));
5889 if ((n > 0) != BIGNUM_SIGN(x)) {
5893 return bigadd_int(x, n);
5898 return bigsub_int(x, n);
5900 else if (RB_BIGNUM_TYPE_P(y)) {
5901 return bignorm(bigadd(x, y, 0));
5919 if (MUL_OVERFLOW_LONG_P(2, xn))
5920 rb_raise(rb_eArgError,
"square overflow");
5928 if (xn < NAIVE_MUL_DIGITS)
5929 bary_sq_fast(zds, zn, xds, xn);
5931 bary_mul(zds, zn, xds, xn, xds, xn);
5942 BDIGIT *xds, *yds, *zds;
5949 if (ADD_OVERFLOW_LONG_P(xn, yn))
5950 rb_raise(rb_eArgError,
"multiplication overflow");
5953 z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
5959 bary_mul(zds, zn, xds, xn, yds, yn);
5972 else if (RB_BIGNUM_TYPE_P(y)) {
5981 return bignorm(bigmul0(x, y));
5987 long xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y);
5989 BDIGIT *xds, *yds, *zds;
5997 BARY_TRUNC(yds, yn);
6002 BARY_TRUNC(xds, xn);
6004 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1])) {
6005 if (divp) *divp = rb_int2big(0);
6006 if (modp) *modp = x;
6011 z = bignew(xn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6013 dd = bigdivrem_single(zds, xds, xn, dd);
6015 *modp = rb_uint2big((uintptr_t)dd);
6016 BIGNUM_SET_SIGN(*modp, BIGNUM_SIGN(x));
6018 if (divp) *divp = z;
6021 if (xn == 2 && yn == 2) {
6022 BDIGIT_DBL x0 = bary2bdigitdbl(xds, 2);
6023 BDIGIT_DBL y0 = bary2bdigitdbl(yds, 2);
6024 BDIGIT_DBL q0 = x0 / y0;
6025 BDIGIT_DBL r0 = x0 % y0;
6027 z = bignew(bdigit_roomof(
sizeof(BDIGIT_DBL)), BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6030 zds[1] = BIGLO(BIGDN(q0));
6034 z = bignew(bdigit_roomof(
sizeof(BDIGIT_DBL)), BIGNUM_SIGN(x));
6037 zds[1] = BIGLO(BIGDN(r0));
6044 qn = xn + BIGDIVREM_EXTRA_WORDS;
6045 q = bignew(qn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6055 r = bignew(rn, BIGNUM_SIGN(x));
6063 bary_divmod_branch(qds, qn, rds, rn, xds, xn, yds, yn);
6082 bigdivrem(x, y, divp, &mod);
6083 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y) && !BIGZEROP(mod)) {
6084 if (divp) *divp = bigadd(*divp, rb_int2big(1), 0);
6085 if (modp) *modp = bigadd(mod, y, 1);
6101 else if (RB_BIGNUM_TYPE_P(y)) {
6105 double dx = rb_big2dbl(x);
6106 return rb_flo_div_flo(
DBL2NUM(dx), y);
6112 v = rb_big_divide(x, y,
'/');
6119 bigdivmod(x, y, &z, 0);
6127 return rb_big_divide(x, y,
'/');
6133 return rb_big_divide(x, y, idDiv);
6144 else if (!RB_BIGNUM_TYPE_P(y)) {
6147 bigdivmod(x, y, 0, &z);
6160 else if (!RB_BIGNUM_TYPE_P(y)) {
6163 bigdivrem(x, y, 0, &z);
6176 else if (!RB_BIGNUM_TYPE_P(y)) {
6179 bigdivmod(x, y, &div, &mod);
6185big_shift(
VALUE x,
long n)
6188 return big_lshift(x, 1+(
unsigned long)(-(n+1)));
6190 return big_rshift(x, (
unsigned long)n);
6194enum {DBL_BIGDIG = ((DBL_MANT_DIG + BITSPERDIG) / BITSPERDIG)};
6204 ex = l * BITSPERDIG - nlz(BDIGITS(x)[l-1]);
6205 ex -= 2 * DBL_BIGDIG * BITSPERDIG;
6206 if (ex > BITSPERDIG) ex -= BITSPERDIG;
6207 else if (ex > 0) ex = 0;
6208 if (ex) x = big_shift(x, ex);
6210 bigdivrem(x, y, &z, 0);
6212#if SIZEOF_LONG > SIZEOF_INT
6215 if (l > INT_MAX)
return HUGE_VAL;
6216 if (l < INT_MIN)
return 0.0;
6219 return ldexp(big2dbl(z), (
int)l);
6228 ey = l * BITSPERDIG - nlz(BDIGITS(y)[l-1]);
6229 ey -= DBL_BIGDIG * BITSPERDIG;
6230 if (ey) y = big_shift(y, ey);
6231 return big_fdiv(x, y, ey);
6238 y = dbl2big(ldexp(frexp(
RFLOAT_VALUE(y), &i), DBL_MANT_DIG));
6239 return big_fdiv(x, y, i - DBL_MANT_DIG);
6252 return big_fdiv_int(x, rb_int2big(
FIX2LONG(y)));
6254 else if (RB_BIGNUM_TYPE_P(y)) {
6255 return big_fdiv_int(x, y);
6262 return big_fdiv_float(x, y);
6274 return DBL2NUM(rb_big_fdiv_double(x, y));
6285 if (y ==
INT2FIX(1))
return x;
6288 if ((BIGNUM_NEGATIVE_P(x) && !BIGZEROP(x))) {
6289 return rb_dbl_complex_new_polar_pi(pow(-rb_big2dbl(x), d), d);
6292 else if (RB_BIGNUM_TYPE_P(y)) {
6296 rb_raise(rb_eArgError,
"exponent is too large");
6311 const size_t xbits = rb_absint_numwords(x, 1, NULL);
6312#if SIZEOF_SIZE_T == 4
6313 const size_t BIGLEN_LIMIT = 1ULL << 31;
6315 const size_t BIGLEN_LIMIT = 1ULL << 34;
6318 if (xbits == (
size_t)-1 ||
6319 (xbits > BIGLEN_LIMIT) ||
6320 MUL_OVERFLOW_LONG_P(yy, xbits) ||
6321 (xbits * yy > BIGLEN_LIMIT)) {
6322 rb_raise(rb_eArgError,
"exponent is too large");
6325 for (mask =
FIXNUM_MAX + 1; mask; mask >>= 1) {
6326 if (z) z = bigsq(z);
6328 z = z ? bigtrunc(bigmul0(z, x)) : x;
6338 return DBL2NUM(pow(rb_big2dbl(x), d));
6342bigand_int(
VALUE x,
long xn, BDIGIT hibitsx,
long y)
6350 if (y == 0)
return INT2FIX(0);
6352 hibitsy = 0 <= y ? 0 : BDIGMAX;
6354#if SIZEOF_BDIGIT >= SIZEOF_LONG
6362#if SIZEOF_BDIGIT < SIZEOF_LONG
6363 if (hibitsx && zn < bdigit_roomof(SIZEOF_LONG))
6364 zn = bdigit_roomof(SIZEOF_LONG);
6370#if SIZEOF_BDIGIT >= SIZEOF_LONG
6372 zds[0] = xds[0] & BIGLO(y);
6374 for (i=0; i < xn; i++) {
6375 if (y == 0 || y == -1)
break;
6376 zds[i] = xds[i] & BIGLO(y);
6379 for (; i < zn; i++) {
6380 if (y == 0 || y == -1)
break;
6381 zds[i] = hibitsx & BIGLO(y);
6385 for (;i < xn; i++) {
6386 zds[i] = xds[i] & hibitsy;
6388 for (;i < zn; i++) {
6389 zds[i] = hibitsx & hibitsy;
6391 twocomp2abs_bang(z, hibitsx && hibitsy);
6400 BDIGIT *ds1, *ds2, *zds;
6401 long i, xn, yn, n1, n2;
6402 BDIGIT hibitsx, hibitsy;
6403 BDIGIT hibits1, hibits2;
6412 hibitsx = abs2twocomp(&x, &xn);
6414 return bigand_int(x, xn, hibitsx,
FIX2LONG(y));
6416 hibitsy = abs2twocomp(&y, &yn);
6418 tmpv = x; x = y; y = tmpv;
6419 tmpn = xn; xn = yn; yn = tmpn;
6420 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6435 for (i=0; i<n1; i++) {
6436 zds[i] = ds1[i] & ds2[i];
6439 zds[i] = hibits1 & ds2[i];
6441 twocomp2abs_bang(z, hibits1 && hibits2);
6448bigor_int(
VALUE x,
long xn, BDIGIT hibitsx,
long y)
6456 if (y == -1)
return INT2FIX(-1);
6458 hibitsy = 0 <= y ? 0 : BDIGMAX;
6462#if SIZEOF_BDIGIT < SIZEOF_LONG
6463 if (zn < bdigit_roomof(SIZEOF_LONG))
6464 zn = bdigit_roomof(SIZEOF_LONG);
6469#if SIZEOF_BDIGIT >= SIZEOF_LONG
6471 zds[0] = xds[0] | BIGLO(y);
6473 goto y_is_fixed_point;
6476 for (i=0; i < xn; i++) {
6477 if (y == 0 || y == -1)
goto y_is_fixed_point;
6478 zds[i] = xds[i] | BIGLO(y);
6483 for (; i < zn; i++) {
6484 if (y == 0 || y == -1)
goto y_is_fixed_point;
6494 for (; i < xn; i++) {
6499 for (; i < zn; i++) {
6505 for (; i < zn; i++) {
6510 twocomp2abs_bang(z, hibitsx || hibitsy);
6519 BDIGIT *ds1, *ds2, *zds;
6520 long i, xn, yn, n1, n2;
6521 BDIGIT hibitsx, hibitsy;
6522 BDIGIT hibits1, hibits2;
6531 hibitsx = abs2twocomp(&x, &xn);
6533 return bigor_int(x, xn, hibitsx,
FIX2LONG(y));
6535 hibitsy = abs2twocomp(&y, &yn);
6537 tmpv = x; x = y; y = tmpv;
6538 tmpn = xn; xn = yn; yn = tmpn;
6539 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6554 for (i=0; i<n1; i++) {
6555 zds[i] = ds1[i] | ds2[i];
6558 zds[i] = hibits1 | ds2[i];
6560 twocomp2abs_bang(z, hibits1 || hibits2);
6567bigxor_int(
VALUE x,
long xn, BDIGIT hibitsx,
long y)
6575 hibitsy = 0 <= y ? 0 : BDIGMAX;
6578#if SIZEOF_BDIGIT < SIZEOF_LONG
6579 if (zn < bdigit_roomof(SIZEOF_LONG))
6580 zn = bdigit_roomof(SIZEOF_LONG);
6585#if SIZEOF_BDIGIT >= SIZEOF_LONG
6587 zds[0] = xds[0] ^ BIGLO(y);
6589 for (i = 0; i < xn; i++) {
6590 zds[i] = xds[i] ^ BIGLO(y);
6593 for (; i < zn; i++) {
6594 zds[i] = hibitsx ^ BIGLO(y);
6598 for (; i < xn; i++) {
6599 zds[i] = xds[i] ^ hibitsy;
6601 for (; i < zn; i++) {
6602 zds[i] = hibitsx ^ hibitsy;
6604 twocomp2abs_bang(z, (hibitsx ^ hibitsy) != 0);
6613 BDIGIT *ds1, *ds2, *zds;
6614 long i, xn, yn, n1, n2;
6615 BDIGIT hibitsx, hibitsy;
6616 BDIGIT hibits1, hibits2;
6625 hibitsx = abs2twocomp(&x, &xn);
6627 return bigxor_int(x, xn, hibitsx,
FIX2LONG(y));
6629 hibitsy = abs2twocomp(&y, &yn);
6631 tmpv = x; x = y; y = tmpv;
6632 tmpn = xn; xn = yn; yn = tmpn;
6633 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6645 for (i=0; i<n1; i++) {
6646 zds[i] = ds1[i] ^ ds2[i];
6649 zds[i] = hibitsx ^ ds2[i];
6651 twocomp2abs_bang(z, (hibits1 ^ hibits2) != 0);
6661 size_t shift_numdigits;
6667 unsigned long shift;
6674 shift = 1+(
unsigned long)(-(l+1));
6676 shift_numbits = (int)(shift & (BITSPERDIG-1));
6677 shift_numdigits = shift >> bit_length(BITSPERDIG-1);
6678 return bignorm(big_shift3(x, lshift_p, shift_numdigits, shift_numbits));
6680 else if (RB_BIGNUM_TYPE_P(y)) {
6681 return bignorm(big_shift2(x, 1, y));
6691 size_t shift_numdigits;
6697 unsigned long shift;
6704 shift = 1+(
unsigned long)(-(l+1));
6706 shift_numbits = (int)(shift & (BITSPERDIG-1));
6707 shift_numdigits = shift >> bit_length(BITSPERDIG-1);
6708 return bignorm(big_shift3(x, lshift_p, shift_numdigits, shift_numbits));
6710 else if (RB_BIGNUM_TYPE_P(y)) {
6711 return bignorm(big_shift2(x, 0, y));
6726 if (RB_BIGNUM_TYPE_P(y)) {
6727 if (BIGNUM_NEGATIVE_P(y))
6730 if (BIGSIZE(y) >
sizeof(
size_t)) {
6733#if SIZEOF_SIZE_T <= SIZEOF_LONG
6734 shift = big2ulong(y,
"long");
6736 shift = big2ull(y,
"long long");
6744 s1 = shift/BITSPERDIG;
6745 s2 = shift%BITSPERDIG;
6746 bit = (BDIGIT)1 << s2;
6748 if (s1 >= BIGNUM_LEN(x))
6752 if (BIGNUM_POSITIVE_P(x))
6754 if (xds[s1] & (bit-1))
6756 for (i = 0; i < s1; i++)
6767 size_t copy_begin, xn, shift;
6768 ssize_t begin, length, end;
6769 bool negative_add_one;
6776 shift = begin < 0 ? -begin : 0;
6780 if (length < 0)
return rb_big_rshift(x, beg);
6781 if (length == 0 || end <= 0)
return INT2FIX(0);
6782 if (begin < 0) begin = 0;
6784 if ((
size_t)(end - 1) / BITSPERDIG >= xn) {
6786 end = xn * BITSPERDIG;
6789 if ((
size_t)begin / BITSPERDIG < xn) {
6791 size_t shift_bits, copy_end;
6792 copy_begin = begin / BITSPERDIG;
6793 shift_bits = begin % BITSPERDIG;
6794 copy_end = (end - 1) / BITSPERDIG + 1;
6795 v = bignew(copy_end - copy_begin, 1);
6797 MEMCPY(vds, xds + copy_begin, BDIGIT, copy_end - copy_begin);
6798 negative_add_one = (vds[0] & ((1 << shift_bits) - 1)) == 0;
6800 if (shift_bits) v = rb_int_rshift(v,
SIZET2NUM(shift_bits));
6805 negative_add_one =
false;
6806 copy_begin = begin = end = 0;
6809 if (BIGNUM_NEGATIVE_P(x)) {
6810 size_t mask_size = length - shift;
6812 v = rb_int_xor(v, mask);
6813 for (
size_t i = 0; negative_add_one && i < copy_begin; i++) {
6814 if (xds[i]) negative_add_one =
false;
6816 if (negative_add_one) v = rb_int_plus(v,
INT2FIX(1));
6817 v = rb_int_and(v, mask);
6820 size_t mask_size = (size_t)end - begin;
6822 v = rb_int_and(v, mask);
6825 if (shift) v = rb_int_lshift(v,
SSIZET2NUM(shift));
6834 hash =
rb_memhash(BDIGITS(x),
sizeof(BDIGIT)*BIGNUM_LEN(x)) ^ BIGNUM_SIGN(x);
6869 if (BIGNUM_NEGATIVE_P(x)) {
6870 x = rb_big_clone(x);
6871 BIGNUM_SET_POSITIVE_SIGN(x);
6879 return BIGNUM_SIGN(x);
6883rb_big_size(
VALUE big)
6885 return BIGSIZE(big);
6889rb_big_size_m(
VALUE big)
6895rb_big_bit_length(
VALUE big)
6900 static const BDIGIT char_bit[1] = { CHAR_BIT };
6901 BDIGIT numbytes_bary[bdigit_roomof(
sizeof(
size_t))];
6903 BDIGIT result_bary[bdigit_roomof(
sizeof(
size_t)+1)];
6905 numbytes = rb_absint_size(big, &nlz_bits);
6910 if (BIGNUM_NEGATIVE_P(big) && rb_absint_singlebit_p(big)) {
6911 if (nlz_bits != CHAR_BIT-1) {
6920 if (numbytes <= SIZE_MAX / CHAR_BIT) {
6921 return SIZET2NUM(numbytes * CHAR_BIT - nlz_bits);
6924 nlz_bary[0] = nlz_bits;
6926 bary_unpack(BARY_ARGS(numbytes_bary), &numbytes, 1,
sizeof(numbytes), 0,
6928 BARY_SHORT_MUL(result_bary, numbytes_bary, char_bit);
6929 BARY_SUB(result_bary, result_bary, nlz_bary);
6931 return rb_integer_unpack(result_bary, numberof(result_bary),
sizeof(BDIGIT), 0,
6936rb_big_odd_p(
VALUE num)
6938 return RBOOL(BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1);
6942rb_big_even_p(
VALUE num)
6944 if (BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1) {
6950unsigned long rb_ulong_isqrt(
unsigned long);
6951#if SIZEOF_BDIGIT*2 > SIZEOF_LONG
6952BDIGIT rb_bdigit_dbl_isqrt(BDIGIT_DBL);
6953# ifdef ULL_TO_DOUBLE
6954# define BDIGIT_DBL_TO_DOUBLE(n) ULL_TO_DOUBLE(n)
6957# define rb_bdigit_dbl_isqrt(x) (BDIGIT)rb_ulong_isqrt(x)
6959#ifndef BDIGIT_DBL_TO_DOUBLE
6960# define BDIGIT_DBL_TO_DOUBLE(n) (double)(n)
6964rb_big_isqrt(
VALUE n)
6966 BDIGIT *nds = BDIGITS(n);
6967 size_t len = BIGNUM_LEN(n);
6970 BDIGIT sq = rb_bdigit_dbl_isqrt(bary2bdigitdbl(nds,
len));
6971#if SIZEOF_BDIGIT > SIZEOF_LONG
6978 size_t shift =
FIX2LONG(rb_big_bit_length(n)) / 4;
6982 x = rb_int_plus(rb_int_lshift(x,
SIZET2NUM(shift - 1)), rb_int_idiv(rb_int_rshift(n,
SIZET2NUM(shift + 1)), x));
6983 VALUE xx = rb_int_mul(x, x);
6984 while (rb_int_gt(xx, n)) {
6985 xx = rb_int_minus(xx, rb_int_minus(rb_int_plus(x, x),
INT2FIX(1)));
6986 x = rb_int_minus(x,
INT2FIX(1));
6994bary_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)
7002 bdigits_to_mpz(x, xds, xn);
7003 bdigits_to_mpz(y, yds, yn);
7004 bdigits_to_mpz(m, mds, mn);
7005 mpz_powm(z, x, y, m);
7006 bdigits_from_mpz(z, zds, &count);
7007 BDIGITS_ZERO(zds+count, zn-count);
7020 size_t xn, yn, mn, zn;
7034 bary_powm_gmp(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, BDIGITS(m), mn);
7035 if (nega_flg & BIGNUM_POSITIVE_P(z)) {
7036 z = rb_big_minus(z, m);
7041 return rb_big_norm(z);
7047 if (
RTEST(rb_int_odd_p(y))) {
7048 tmp = rb_int_mul(tmp, x);
7049 tmp = rb_int_modulo(tmp, m);
7051 x = rb_int_mul(x, x);
7052 x = rb_int_modulo(x, m);
7054 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7056 tmp = rb_int_mul(tmp, x);
7057 tmp = rb_int_modulo(tmp, m);
7059 x = rb_int_mul(x, x);
7060 x = rb_int_modulo(x, m);
7063 if (nega_flg && rb_int_positive_p(tmp)) {
7064 tmp = rb_int_minus(tmp, m);
7075int_pow_tmp1(
VALUE x,
VALUE y,
long mm,
int nega_flg)
7082 if (
RTEST(rb_int_odd_p(y))) {
7083 tmp = (tmp * xx) % mm;
7085 xx = (xx * xx) % mm;
7087 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7089 tmp = (tmp * xx) % mm;
7091 xx = (xx * xx) % mm;
7094 if (nega_flg && tmp) {
7101int_pow_tmp2(
VALUE x,
VALUE y,
long mm,
int nega_flg)
7109# define MUL_MODULO(a, b, c) (long)(((DLONG)(a) * (DLONG)(b)) % (c))
7114# define MUL_MODULO(a, b, c) rb_int_modulo(rb_fix_mul_fix((a), (b)), (c))
7118 if (
RTEST(rb_int_odd_p(y))) {
7119 tmp2 = MUL_MODULO(tmp2, xx, m);
7121 xx = MUL_MODULO(xx, xx, m);
7123 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7125 tmp2 = MUL_MODULO(tmp2, xx, m);
7127 xx = MUL_MODULO(xx, xx, m);
7135 if (nega_flg && tmp) {
7153rb_int_powm(
int const argc,
VALUE *
const argv,
VALUE const num)
7158 return rb_int_pow(num, argv[0]);
7161 VALUE const a = num;
7162 VALUE const b = argv[0];
7166 rb_raise(
rb_eTypeError,
"Integer#pow() 2nd argument not allowed unless a 1st argument is integer");
7168 if (rb_int_negative_p(b)) {
7169 rb_raise(
rb_eRangeError,
"Integer#pow() 1st argument cannot be negative when 2nd argument specified");
7172 rb_raise(
rb_eTypeError,
"Integer#pow() 2nd argument not allowed unless all arguments are integers");
7175 if (rb_int_negative_p(m)) {
7176 m = rb_int_uminus(m);
7181 long const half_val = (long)HALF_LONG_MSB;
7184 if (mm == 1)
return INT2FIX(0);
7185 if (mm <= half_val) {
7186 return int_pow_tmp1(rb_int_modulo(a, m), b, mm, nega_flg);
7189 return int_pow_tmp2(rb_int_modulo(a, m), b, mm, nega_flg);
7195 return int_pow_tmp3(rb_int_modulo(a, m), b, m, nega_flg);
7226 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 NUM2SSIZET
Old name of RB_NUM2SSIZE.
#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 SSIZET2NUM
Old name of RB_SSIZE2NUM.
#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.
VALUE rb_assoc_new(VALUE car, VALUE cdr)
Identical to rb_ary_new_from_values(), except it expects exactly two parameters.
#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.