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"
47#include "ruby_assert.h"
58static const bool debug_integer_pack = (
59#ifdef DEBUG_INTEGER_PACK
66const char ruby_digitmap[] =
"0123456789abcdefghijklmnopqrstuvwxyz";
68#ifndef SIZEOF_BDIGIT_DBL
69# if SIZEOF_INT*2 <= SIZEOF_LONG_LONG
70# define SIZEOF_BDIGIT_DBL SIZEOF_LONG_LONG
72# define SIZEOF_BDIGIT_DBL SIZEOF_LONG
76STATIC_ASSERT(sizeof_bdigit_dbl,
sizeof(BDIGIT_DBL) == SIZEOF_BDIGIT_DBL);
77STATIC_ASSERT(sizeof_bdigit_dbl_signed,
sizeof(BDIGIT_DBL_SIGNED) == SIZEOF_BDIGIT_DBL);
78STATIC_ASSERT(sizeof_bdigit, SIZEOF_BDIGIT <=
sizeof(BDIGIT));
79STATIC_ASSERT(sizeof_bdigit_and_dbl, SIZEOF_BDIGIT*2 <= SIZEOF_BDIGIT_DBL);
80STATIC_ASSERT(bdigit_signedness, 0 < (BDIGIT)-1);
81STATIC_ASSERT(bdigit_dbl_signedness, 0 < (BDIGIT_DBL)-1);
82STATIC_ASSERT(bdigit_dbl_signed_signedness, 0 > (BDIGIT_DBL_SIGNED)-1);
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)))
2994big_embed_capa(
VALUE big)
2996 size_t size = rb_gc_obj_slot_size(big) - offsetof(
struct RBignum, as.ary);
2998 size_t capa = size /
sizeof(BDIGIT);
3004big_embed_size(
size_t capa)
3006 size_t size = offsetof(
struct RBignum, as.ary) + (
sizeof(BDIGIT) *
capa);
3007 if (size <
sizeof(
struct RBignum)) {
3008 size =
sizeof(
struct RBignum);
3014big_embeddable_p(
size_t capa)
3016 if (
capa > BIGNUM_EMBED_LEN_MAX) {
3019 return rb_gc_size_allocatable_p(big_embed_size(
capa));
3023rb_big_realloc(
VALUE big,
size_t len)
3026 size_t embed_capa = big_embed_capa(big);
3028 if (BIGNUM_EMBED_P(big)) {
3029 if (embed_capa <
len) {
3031 MEMCPY(ds, RBIGNUM(big)->as.ary, BDIGIT, embed_capa);
3032 RBIGNUM(big)->as.heap.len = BIGNUM_LEN(big);
3033 RBIGNUM(big)->as.heap.digits = ds;
3038 if (
len <= embed_capa) {
3039 ds = RBIGNUM(big)->as.heap.digits;
3041 BIGNUM_SET_LEN(big,
len);
3042 (void)VALGRIND_MAKE_MEM_UNDEFINED((
void*)RBIGNUM(big)->as.ary, embed_capa *
sizeof(BDIGIT));
3044 MEMCPY(RBIGNUM(big)->as.ary, ds, BDIGIT,
len);
3049 if (BIGNUM_LEN(big) == 0) {
3050 RBIGNUM(big)->as.heap.digits =
ALLOC_N(BDIGIT,
len);
3052 else if (BIGNUM_LEN(big) <
len) {
3062 rb_big_realloc(big,
len);
3063 BIGNUM_SET_LEN(big,
len);
3067bignew_1(
VALUE klass,
size_t len,
int sign)
3071 if (big_embeddable_p(
len)) {
3072 size_t size = big_embed_size(
len);
3074 NEWOBJ_OF(big,
struct RBignum, klass,
3078 BIGNUM_SET_SIGN(bigv, sign);
3079 BIGNUM_SET_LEN(bigv,
len);
3080 (void)VALGRIND_MAKE_MEM_UNDEFINED((
void*)big->as.ary,
len *
sizeof(BDIGIT));
3083 NEWOBJ_OF(big,
struct RBignum, klass,
3086 BIGNUM_SET_SIGN(bigv, sign);
3088 big->as.heap.len =
len;
3095rb_big_new(
size_t len,
int sign)
3097 VALUE obj = bignew(
len, sign != 0);
3098 memset(BIGNUM_DIGITS(obj), 0,
len *
sizeof(BDIGIT));
3105 size_t len = BIGNUM_LEN(x);
3108 MEMCPY(BDIGITS(z), BDIGITS(x), BDIGIT,
len);
3113big_extend_carry(
VALUE x)
3115 rb_big_resize(x, BIGNUM_LEN(x)+1);
3116 BDIGITS(x)[BIGNUM_LEN(x)-1] = 1;
3123 long i = BIGNUM_LEN(x);
3124 BDIGIT *ds = BDIGITS(x);
3126 if (bary_2comp(ds, i)) {
3127 big_extend_carry(x);
3138abs2twocomp(
VALUE *xp,
long *n_ret)
3141 long n = BIGNUM_LEN(x);
3142 BDIGIT *ds = BDIGITS(x);
3147 if (n != 0 && BIGNUM_NEGATIVE_P(x)) {
3149 MEMCPY(BDIGITS(z), ds, BDIGIT, n);
3150 bary_2comp(BDIGITS(z), n);
3159twocomp2abs_bang(
VALUE x,
int hibits)
3161 BIGNUM_SET_SIGN(x, !hibits);
3170 size_t len = BIGNUM_LEN(x);
3171 BDIGIT *ds = BDIGITS(x);
3173 if (
len == 0)
return x;
3174 while (--
len && !ds[
len]);
3175 if (BIGNUM_LEN(x) >
len+1) {
3176 rb_big_resize(x,
len+1);
3184 size_t n = BIGNUM_LEN(x);
3185 BDIGIT *ds = BDIGITS(x);
3186#if SIZEOF_BDIGIT < SIZEOF_LONG
3194 if (n == 0)
return INT2FIX(0);
3196#if SIZEOF_BDIGIT < SIZEOF_LONG
3197 if (
sizeof(
long)/SIZEOF_BDIGIT < n)
3203 u = (
unsigned long)(BIGUP(u) + ds[i]);
3213 if (BIGNUM_POSITIVE_P(x)) {
3221 rb_big_resize(x, n);
3228 if (RB_BIGNUM_TYPE_P(x)) {
3241rb_uint2big(uintptr_t n)
3245 BDIGIT *digits = BDIGITS(big);
3247#if SIZEOF_BDIGIT >= SIZEOF_VALUE
3251 digits[i] = BIGLO(n);
3257 while (--i && !digits[i]) ;
3258 BIGNUM_SET_LEN(big, i+1);
3263rb_int2big(intptr_t n)
3270 u = 1 + (
VALUE)(-(n + 1));
3276 big = rb_uint2big(u);
3278 BIGNUM_SET_NEGATIVE_SIGN(big);
3284rb_uint2inum(uintptr_t n)
3287 return rb_uint2big(n);
3291rb_int2inum(intptr_t n)
3294 return rb_int2big(n);
3298rb_big_pack(
VALUE val,
unsigned long *buf,
long num_longs)
3300 rb_integer_pack(val, buf, num_longs,
sizeof(
long), 0,
3306rb_big_unpack(
unsigned long *buf,
long num_longs)
3308 return rb_integer_unpack(buf, num_longs,
sizeof(
long), 0,
3330rb_absint_size(
VALUE val,
int *nlz_bits_ret)
3334 BDIGIT fixbuf[bdigit_roomof(
sizeof(
long))];
3336 int num_leading_zeros;
3345#if SIZEOF_BDIGIT >= SIZEOF_LONG
3350 for (i = 0; i < numberof(fixbuf); i++) {
3351 fixbuf[i] = BIGLO(v);
3357 de = fixbuf + numberof(fixbuf);
3361 de = dp + BIGNUM_LEN(val);
3363 while (dp < de && de[-1] == 0)
3370 num_leading_zeros = nlz(de[-1]);
3372 *nlz_bits_ret = num_leading_zeros % CHAR_BIT;
3373 return (de - dp) * SIZEOF_BDIGIT - num_leading_zeros / CHAR_BIT;
3377absint_numwords_small(
size_t numbytes,
int nlz_bits_in_msbyte,
size_t word_numbits,
size_t *nlz_bits_ret)
3379 size_t val_numbits = numbytes * CHAR_BIT - nlz_bits_in_msbyte;
3380 size_t div = val_numbits / word_numbits;
3381 size_t mod = val_numbits % word_numbits;
3384 numwords = mod == 0 ? div : div + 1;
3385 nlz_bits = mod == 0 ? 0 : word_numbits - mod;
3386 *nlz_bits_ret = nlz_bits;
3391absint_numwords_generic(
size_t numbytes,
int nlz_bits_in_msbyte,
size_t word_numbits,
size_t *nlz_bits_ret)
3393 static const BDIGIT char_bit[1] = { CHAR_BIT };
3394 BDIGIT numbytes_bary[bdigit_roomof(
sizeof(numbytes))];
3395 BDIGIT val_numbits_bary[bdigit_roomof(
sizeof(numbytes) + 1)];
3396 BDIGIT nlz_bits_in_msbyte_bary[1];
3397 BDIGIT word_numbits_bary[bdigit_roomof(
sizeof(word_numbits))];
3398 BDIGIT div_bary[numberof(val_numbits_bary) + BIGDIVREM_EXTRA_WORDS];
3399 BDIGIT mod_bary[numberof(word_numbits_bary)];
3400 BDIGIT one[1] = { 1 };
3406 nlz_bits_in_msbyte_bary[0] = nlz_bits_in_msbyte;
3415 bary_unpack(BARY_ARGS(numbytes_bary), &numbytes, 1,
sizeof(numbytes), 0,
3417 BARY_SHORT_MUL(val_numbits_bary, numbytes_bary, char_bit);
3418 if (nlz_bits_in_msbyte)
3419 BARY_SUB(val_numbits_bary, val_numbits_bary, nlz_bits_in_msbyte_bary);
3420 bary_unpack(BARY_ARGS(word_numbits_bary), &word_numbits, 1,
sizeof(word_numbits), 0,
3422 BARY_DIVMOD(div_bary, mod_bary, val_numbits_bary, word_numbits_bary);
3423 if (BARY_ZERO_P(mod_bary)) {
3427 BARY_ADD(div_bary, div_bary, one);
3428 bary_pack(+1, BARY_ARGS(mod_bary), &mod, 1,
sizeof(mod), 0,
3430 nlz_bits = word_numbits - mod;
3432 sign = bary_pack(+1, BARY_ARGS(div_bary), &numwords, 1,
sizeof(numwords), 0,
3436#if defined __GNUC__ && (__GNUC__ == 4 && __GNUC_MINOR__ == 4)
3441 *nlz_bits_ret = nlz_bits;
3465rb_absint_numwords(
VALUE val,
size_t word_numbits,
size_t *nlz_bits_ret)
3468 int nlz_bits_in_msbyte;
3470 size_t nlz_bits = 0;
3472 if (word_numbits == 0)
3475 numbytes = rb_absint_size(val, &nlz_bits_in_msbyte);
3477 if (numbytes <= SIZE_MAX / CHAR_BIT) {
3478 numwords = absint_numwords_small(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits);
3479 if (debug_integer_pack) {
3480 size_t numwords0, nlz_bits0;
3481 numwords0 = absint_numwords_generic(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits0);
3488 numwords = absint_numwords_generic(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits);
3490 if (numwords == (
size_t)-1)
3494 *nlz_bits_ret = nlz_bits;
3532 BDIGIT fixbuf[bdigit_roomof(
sizeof(
long))];
3542#if SIZEOF_BDIGIT >= SIZEOF_LONG
3547 for (i = 0; i < numberof(fixbuf); i++) {
3548 fixbuf[i] = BIGLO(v);
3554 de = fixbuf + numberof(fixbuf);
3558 de = dp + BIGNUM_LEN(val);
3560 while (dp < de && de[-1] == 0)
3562 while (dp < de && dp[0] == 0)
3629rb_integer_pack(
VALUE val,
void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
3634 BDIGIT fixbuf[bdigit_roomof(
sizeof(
long))];
3647#if SIZEOF_BDIGIT >= SIZEOF_LONG
3652 for (i = 0; i < numberof(fixbuf); i++) {
3653 fixbuf[i] = BIGLO(v);
3659 num_bdigits = numberof(fixbuf);
3662 sign = BIGNUM_POSITIVE_P(val) ? 1 : -1;
3664 num_bdigits = BIGNUM_LEN(val);
3667 return bary_pack(sign, ds, num_bdigits, words, numwords, wordsize, nails, flags);
3715rb_integer_unpack(
const void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
3722 BDIGIT fixbuf[2] = { 0, 0 };
3724 validate_integer_pack_format(numwords, wordsize, nails, flags,
3735 num_bdigits = integer_unpack_num_bdigits(numwords, wordsize, nails, &nlp_bits);
3737 if (LONG_MAX-1 < num_bdigits)
3738 rb_raise(rb_eArgError,
"too big to unpack as an integer");
3744 val = bignew((
long)num_bdigits, 0);
3747 sign = bary_unpack_internal(ds, num_bdigits, words, numwords, wordsize, nails, flags, nlp_bits);
3751 big_extend_carry(val);
3753 else if (num_bdigits == numberof(fixbuf)) {
3754 val = bignew((
long)num_bdigits+1, 0);
3755 MEMCPY(BDIGITS(val), fixbuf, BDIGIT, num_bdigits);
3756 BDIGITS(val)[num_bdigits++] = 1;
3759 ds[num_bdigits++] = 1;
3764 BDIGIT_DBL u = fixbuf[0] + BIGUP(fixbuf[1]);
3769 if (sign < 0 && BDIGIT_MSB(fixbuf[1]) == 0 &&
3771 return LONG2FIX((
long)-(BDIGIT_DBL_SIGNED)u);
3772 val = bignew((
long)num_bdigits, 0 <= sign);
3773 MEMCPY(BDIGITS(val), fixbuf, BDIGIT, num_bdigits);
3777 bary_zero_p(BDIGITS(val), BIGNUM_LEN(val)))
3779 BIGNUM_SET_SIGN(val, 0 <= sign);
3782 return bigtrunc(val);
3783 return bignorm(val);
3786#define conv_digit(c) (ruby_digit36_to_number_table[(unsigned char)(c)])
3788NORETURN(
static inline void invalid_radix(
int base));
3789NORETURN(
static inline void invalid_integer(
VALUE s));
3792valid_radix_p(
int base)
3794 return (1 < base && base <= 36);
3798invalid_radix(
int base)
3800 rb_raise(rb_eArgError,
"invalid radix %d", base);
3804invalid_integer(
VALUE s)
3806 rb_raise(rb_eArgError,
"invalid value for Integer(): %+"PRIsVALUE, s);
3810str2big_scan_digits(
const char *s,
const char *str,
int base,
int badcheck,
size_t *num_digits_p, ssize_t *len_p)
3813 size_t num_digits = 0;
3814 const char *digits_start = str;
3815 const char *digits_end = str;
3816 ssize_t
len = *len_p;
3826 if (badcheck && *str ==
'_')
return FALSE;
3828 while ((c = *str++) != 0) {
3831 if (badcheck)
return FALSE;
3834 nondigit = (char) c;
3836 else if ((c = conv_digit(c)) < 0 || c >= base) {
3844 if (
len > 0 && !--
len)
break;
3846 if (badcheck && nondigit)
return FALSE;
3847 if (badcheck &&
len) {
3849 while (*str &&
ISSPACE(*str)) {
3851 if (
len > 0 && !--
len)
break;
3857 *num_digits_p = num_digits;
3858 *len_p = digits_end - digits_start;
3865 const char *digits_start,
3866 const char *digits_end,
3879 num_bdigits = (num_digits / BITSPERDIG) * bits_per_digit + roomof((num_digits % BITSPERDIG) * bits_per_digit, BITSPERDIG);
3880 z = bignew(num_bdigits, sign);
3884 for (p = digits_end; digits_start < p; p--) {
3885 if ((c = conv_digit(p[-1])) < 0)
3887 dd |= (BDIGIT_DBL)c << numbits;
3888 numbits += bits_per_digit;
3889 if (BITSPERDIG <= numbits) {
3892 numbits -= BITSPERDIG;
3898 RUBY_ASSERT((
size_t)(dp - BDIGITS(z)) == num_bdigits);
3906 const char *digits_start,
3907 const char *digits_end,
3920 z = bignew(num_bdigits, sign);
3922 BDIGITS_ZERO(zds, num_bdigits);
3924 for (p = digits_start; p < digits_end; p++) {
3925 if ((c = conv_digit(*p)) < 0)
3931 num += (BDIGIT_DBL)zds[i]*base;
3932 zds[i++] = BIGLO(num);
3950 const char *digits_start,
3951 const char *digits_end,
3954 int digits_per_bdigits_dbl,
3960 BDIGIT *uds, *vds, *tds;
3962 BDIGIT_DBL current_base;
3964 int power_level = 0;
3971 uds =
ALLOCV_N(BDIGIT, tmpuv, 2*num_bdigits);
3972 vds = uds + num_bdigits;
3974 powerv = power_cache_get_power(base, power_level, NULL);
3979 m = digits_per_bdigits_dbl;
3980 if (num_digits < (
size_t)m)
3981 m = (int)num_digits;
3982 for (p = digits_end; digits_start < p; p--) {
3983 if ((c = conv_digit(p[-1])) < 0)
3985 dd = dd + c * current_base;
3986 current_base *= base;
3990 uds[i++] = BIGLO(dd);
3991 uds[i++] = (BDIGIT)BIGDN(dd);
3993 m = digits_per_bdigits_dbl;
3994 if (num_digits < (
size_t)m)
3995 m = (int)num_digits;
4000 for (unit = 2; unit < num_bdigits; unit *= 2) {
4001 for (i = 0; i < num_bdigits; i += unit*2) {
4002 if (2*unit <= num_bdigits - i) {
4003 bary_mul(vds+i, unit*2, BDIGITS(powerv), BIGNUM_LEN(powerv), uds+i+unit, unit);
4004 bary_add(vds+i, unit*2, vds+i, unit*2, uds+i, unit);
4006 else if (unit <= num_bdigits - i) {
4007 bary_mul(vds+i, num_bdigits-i, BDIGITS(powerv), BIGNUM_LEN(powerv), uds+i+unit, num_bdigits-(i+unit));
4008 bary_add(vds+i, num_bdigits-i, vds+i, num_bdigits-i, uds+i, unit);
4011 MEMCPY(vds+i, uds+i, BDIGIT, num_bdigits-i);
4015 powerv = power_cache_get_power(base, power_level, NULL);
4020 BARY_TRUNC(uds, num_bdigits);
4021 z = bignew(num_bdigits, sign);
4022 MEMCPY(BDIGITS(z), uds, BDIGIT, num_bdigits);
4034 const char *digits_start,
4035 const char *digits_end,
4048 buf =
ALLOCV_N(
char, tmps, num_digits+1);
4050 for (q = digits_start; q < digits_end; q++) {
4051 if (conv_digit(*q) < 0)
4058 mpz_set_str(mz, buf, base);
4060 z = bignew(zn, sign);
4062 bdigits_from_mpz(mz, BDIGITS(z), &count);
4063 BDIGITS_ZERO(zds+count, zn-count);
4073static VALUE rb_cstr_parse_inum(
const char *str, ssize_t
len,
char **endp,
int base);
4092rb_cstr_to_inum(
const char *str,
int base,
int badcheck)
4095 VALUE ret = rb_cstr_parse_inum(str, -1, (badcheck ? NULL : &end), base);
4121rb_int_parse_cstr(
const char *str, ssize_t
len,
char **endp,
size_t *ndigits,
4122 int base,
int flags)
4124 const char *
const s = str;
4132 const char *digits_start, *digits_end;
4133 size_t num_digits = 0;
4135 const ssize_t len0 =
len;
4136 const int badcheck = !endp;
4139 if (len > 0 && len <= (n)) goto bad; \
4143#define ASSERT_LEN() do {\
4144 RUBY_ASSERT(len != 0); \
4145 if (len0 >= 0) RUBY_ASSERT(s + len0 == str + len); \
4151 if (
len && (flags & RB_INT_PARSE_SIGN)) {
4154 if (str[0] ==
'+') {
4157 else if (str[0] ==
'-') {
4164 if (str[0] ==
'0' &&
len > 1) {
4186 else if (base < -1) {
4193 else if (
len == 0 ||
len == 1 || !(flags & RB_INT_PARSE_PREFIX)) {
4196 else if (base == 2) {
4197 if (str[0] ==
'0' && (str[1] ==
'b'||str[1] ==
'B')) {
4201 else if (base == 8) {
4202 if (str[0] ==
'0' && (str[1] ==
'o'||str[1] ==
'O')) {
4206 else if (base == 10) {
4207 if (str[0] ==
'0' && (str[1] ==
'd'||str[1] ==
'D')) {
4211 else if (base == 16) {
4212 if (str[0] ==
'0' && (str[1] ==
'x'||str[1] ==
'X')) {
4216 if (!valid_radix_p(base)) {
4217 invalid_radix(base);
4220 num_digits = str - s;
4221 if (*str ==
'0' &&
len != 1) {
4223 const char *end =
len < 0 ? NULL : str +
len;
4224 while (str != end) {
4225 const char *next = str + 1;
4228 if (next == end || !*next ||
ISSPACE(*next))
4233 else if ((flags & RB_INT_PARSE_UNDERSCORE) && c ==
'_') {
4234 if (++us >= 2 || next == end || !*next ||
ISSPACE(*next))
4242 if (end)
len = end - str;
4246 if (c < 0 || c >= base) {
4247 if (!badcheck && num_digits) z =
INT2FIX(0);
4251 if (ndigits) *ndigits = num_digits;
4252 val = ruby_scan_digits(str,
len, base, &num_digits, &ov);
4254 const char *end = &str[num_digits];
4255 if (num_digits > 0 && *end ==
'_' && (flags & RB_INT_PARSE_UNDERSCORE))
4257 if (endp) *endp = (
char *)end;
4258 if (ndigits) *ndigits += num_digits;
4260 if (num_digits == 0)
return Qnil;
4261 while (
len < 0 ? *end : end < str +
len) {
4270 long result = -(long)val;
4275 VALUE big = rb_uint2big(val);
4276 BIGNUM_SET_SIGN(big, sign);
4277 return bignorm(big);
4283 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4285 if (endp) *endp = (
char *)(str +
len);
4286 if (ndigits) *ndigits += num_digits;
4287 digits_end = digits_start +
len;
4290 z = str2big_poweroftwo(sign, digits_start, digits_end, num_digits,
4291 bit_length(base-1));
4294 int digits_per_bdigits_dbl;
4295 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4296 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4299 if (GMP_STR2BIG_DIGITS < num_bdigits) {
4300 z = str2big_gmp(sign, digits_start, digits_end, num_digits,
4305 if (num_bdigits < KARATSUBA_MUL_DIGITS) {
4306 z = str2big_normal(sign, digits_start, digits_end,
4310 z = str2big_karatsuba(sign, digits_start, digits_end, num_digits,
4311 num_bdigits, digits_per_bdigits_dbl, base);
4318 if (endp) *endp = (
char *)str;
4319 if (ndigits) *ndigits = num_digits;
4324rb_cstr_parse_inum(
const char *str, ssize_t
len,
char **endp,
int base)
4326 return rb_int_parse_cstr(str,
len, endp, NULL, base,
4327 RB_INT_PARSE_DEFAULT);
4331rb_str_convert_to_inum(
VALUE str,
int base,
int badcheck,
int raise_exception)
4341 ret = rb_cstr_parse_inum(s,
len, (badcheck ? NULL : &end), base);
4344 if (!raise_exception)
return Qnil;
4345 invalid_integer(str);
4353rb_str_to_inum(
VALUE str,
int base,
int badcheck)
4355 return rb_str_convert_to_inum(str, base, badcheck, TRUE);
4359rb_str2big_poweroftwo(
VALUE arg,
int base,
int badcheck)
4362 const char *s, *str;
4363 const char *digits_start, *digits_end;
4368 if (!valid_radix_p(base) || !POW2_P(base)) {
4369 invalid_radix(base);
4374 len = RSTRING_LEN(arg);
4382 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4383 invalid_integer(arg);
4384 digits_end = digits_start +
len;
4386 z = str2big_poweroftwo(positive_p, digits_start, digits_end, num_digits,
4387 bit_length(base-1));
4395rb_str2big_normal(
VALUE arg,
int base,
int badcheck)
4398 const char *s, *str;
4399 const char *digits_start, *digits_end;
4404 int digits_per_bdigits_dbl;
4407 if (!valid_radix_p(base)) {
4408 invalid_radix(base);
4413 len = RSTRING_LEN(arg);
4414 if (
len > 0 && *str ==
'-') {
4421 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4422 invalid_integer(arg);
4423 digits_end = digits_start +
len;
4425 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4426 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4428 z = str2big_normal(positive_p, digits_start, digits_end,
4437rb_str2big_karatsuba(
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_karatsuba(positive_p, digits_start, digits_end, num_digits,
4471 num_bdigits, digits_per_bdigits_dbl, base);
4480rb_str2big_gmp(
VALUE arg,
int base,
int badcheck)
4483 const char *s, *str;
4484 const char *digits_start, *digits_end;
4489 int digits_per_bdigits_dbl;
4492 if (!valid_radix_p(base)) {
4493 invalid_radix(base);
4498 len = RSTRING_LEN(arg);
4499 if (
len > 0 && *str ==
'-') {
4506 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4507 invalid_integer(arg);
4508 digits_end = digits_start +
len;
4510 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4511 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4513 z = str2big_gmp(positive_p, digits_start, digits_end, num_digits, num_bdigits, base);
4527 VALUE big = bignew(bdigit_roomof(SIZEOF_LONG_LONG), 1);
4528 BDIGIT *digits = BDIGITS(big);
4530#if SIZEOF_BDIGIT >= SIZEOF_LONG_LONG
4533 for (i = 0; i < bdigit_roomof(SIZEOF_LONG_LONG); i++) {
4534 digits[i] = BIGLO(n);
4539 i = bdigit_roomof(SIZEOF_LONG_LONG);
4540 while (i-- && !digits[i]) ;
4541 BIGNUM_SET_LEN(big, i+1);
4559 big = rb_ull2big(u);
4561 BIGNUM_SET_NEGATIVE_SIGN(big);
4570 return rb_ull2big(n);
4577 return rb_ll2big(n);
4584rb_uint128t2big(uint128_t n)
4587 VALUE big = bignew(bdigit_roomof(SIZEOF_INT128_T), 1);
4588 BDIGIT *digits = BDIGITS(big);
4590 for (i = 0; i < bdigit_roomof(SIZEOF_INT128_T); i++) {
4591 digits[i] = BIGLO(RSHIFT(n ,BITSPERDIG*i));
4594 i = bdigit_roomof(SIZEOF_INT128_T);
4595 while (i-- && !digits[i]) ;
4596 BIGNUM_SET_LEN(big, i+1);
4601rb_int128t2big(int128_t n)
4608 u = 1 + (uint128_t)(-(n + 1));
4614 big = rb_uint128t2big(u);
4616 BIGNUM_SET_NEGATIVE_SIGN(big);
4623rb_cstr2inum(
const char *str,
int base)
4625 return rb_cstr_to_inum(str, base, base==0);
4631 return rb_str_to_inum(str, base, base==0);
4635big_shift3(
VALUE x,
int lshift_p,
size_t shift_numdigits,
int shift_numbits)
4644 if (LONG_MAX < shift_numdigits) {
4648 s1 = shift_numdigits;
4650 if ((
size_t)s1 != shift_numdigits)
goto too_big;
4652 if (LONG_MAX/SIZEOF_BDIGIT <= xn+s1)
goto too_big;
4653 z = bignew(xn+s1+1, BIGNUM_SIGN(x));
4655 BDIGITS_ZERO(zds, s1);
4657 zds[xn+s1] = bary_small_lshift(zds+s1, xds, xn, s2);
4662 if (LONG_MAX < shift_numdigits || (
size_t)BIGNUM_LEN(x) <= shift_numdigits) {
4663 if (BIGNUM_POSITIVE_P(x) ||
4664 bary_zero_p(BDIGITS(x), BIGNUM_LEN(x)))
4669 s1 = shift_numdigits;
4671 hibitsx = abs2twocomp(&x, &xn);
4679 bary_small_rshift(zds, xds+s1, zn, s2, hibitsx != 0 ? BDIGMAX : 0);
4680 twocomp2abs_bang(z, hibitsx != 0);
4691 size_t shift_numdigits;
4699 sign = rb_integer_pack(y, lens, numberof(lens),
sizeof(
size_t), 0,
4702 lshift_p = !lshift_p;
4706 if (1 < sign || CHAR_BIT <= lens[1])
4710 if (1 < sign || CHAR_BIT <= lens[1])
4713 shift_numbits = (int)(lens[0] & (BITSPERDIG-1));
4714 shift_numdigits = (lens[0] >> bit_length(BITSPERDIG-1)) |
4715 (lens[1] << (CHAR_BIT*SIZEOF_SIZE_T - bit_length(BITSPERDIG-1)));
4716 return big_shift3(x, lshift_p, shift_numdigits, shift_numbits);
4720big_lshift(
VALUE x,
unsigned long shift)
4722 long s1 = shift/BITSPERDIG;
4723 int s2 = (int)(shift%BITSPERDIG);
4724 return big_shift3(x, 1, s1, s2);
4728big_rshift(
VALUE x,
unsigned long shift)
4730 long s1 = shift/BITSPERDIG;
4731 int s2 = (int)(shift%BITSPERDIG);
4732 return big_shift3(x, 0, s1, s2);
4735#define MAX_BASE36_POWER_TABLE_ENTRIES (SIZEOF_SIZE_T * CHAR_BIT + 1)
4737static VALUE base36_power_cache[35][MAX_BASE36_POWER_TABLE_ENTRIES];
4738static size_t base36_numdigits_cache[35][MAX_BASE36_POWER_TABLE_ENTRIES];
4741power_cache_init(
void)
4746power_cache_get_power(
int base,
int power_level,
size_t *numdigits_ret)
4762 if (MAX_BASE36_POWER_TABLE_ENTRIES <= power_level)
4763 rb_bug(
"too big power number requested: maxpow_in_bdigit_dbl(%d)**(2**%d)", base, power_level);
4765 VALUE power = rbimpl_atomic_value_load(&base36_power_cache[base - 2][power_level], RBIMPL_ATOMIC_ACQUIRE);
4768 if (power_level == 0) {
4770 BDIGIT_DBL dd = maxpow_in_bdigit_dbl(base, &numdigits0);
4771 power = bignew(2, 1);
4772 bdigitdbl2bary(BDIGITS(power), 2, dd);
4773 numdigits = numdigits0;
4776 power = bigtrunc(bigsq(power_cache_get_power(base, power_level - 1, &numdigits)));
4780 base36_numdigits_cache[base - 2][power_level] = numdigits;
4782 VALUE old = rbimpl_atomic_value_cas(&base36_power_cache[base - 2][power_level], 0, power,
4783 RBIMPL_ATOMIC_RELEASE, RBIMPL_ATOMIC_ACQUIRE);
4788 rb_vm_register_global_object(power);
4792 *numdigits_ret = base36_numdigits_cache[base - 2][power_level];
4800 int hbase2_numdigits;
4808 if (LONG_MAX-1 <
len)
4809 rb_raise(rb_eArgError,
"too big number");
4811 b2s->ptr = RSTRING_PTR(b2s->result);
4817big2str_2bdigits(
struct big2str_struct *b2s, BDIGIT *xds,
size_t xn,
size_t taillen)
4821 char buf[SIZEOF_BDIGIT_DBL*CHAR_BIT], *p;
4822 int beginning = !b2s->ptr;
4826 num = bary2bdigitdbl(xds, xn);
4834 BDIGIT_DBL idx = num % b2s->base;
4836 p[--j] = ruby_digitmap[idx];
4838 len =
sizeof(buf) - j;
4839 big2str_alloc(b2s,
len + taillen);
4844 j = b2s->hbase2_numdigits;
4846 BDIGIT_DBL idx = num % b2s->base;
4848 p[--j] = ruby_digitmap[idx];
4850 len = b2s->hbase2_numdigits;
4856big2str_karatsuba(
struct big2str_struct *b2s, BDIGIT *xds,
size_t xn,
size_t wn,
4857 int power_level,
size_t taillen)
4860 size_t half_numdigits, lower_numdigits;
4861 int lower_power_level;
4886 if (xn == 0 || bary_zero_p(xds, xn)) {
4889 power_cache_get_power(b2s->base, power_level, &
len);
4890 memset(b2s->ptr,
'0',
len);
4896 if (power_level == 0) {
4897 big2str_2bdigits(b2s, xds, xn, taillen);
4901 lower_power_level = power_level-1;
4902 b = power_cache_get_power(b2s->base, lower_power_level, &lower_numdigits);
4906 half_numdigits = lower_numdigits;
4908 while (0 < lower_power_level &&
4910 (xn == bn && bary_cmp(xds, xn, bds, bn) < 0))) {
4911 lower_power_level--;
4912 b = power_cache_get_power(b2s->base, lower_power_level, &lower_numdigits);
4917 if (lower_power_level == 0 &&
4919 (xn == bn && bary_cmp(xds, xn, bds, bn) < 0))) {
4921 len = half_numdigits * 2 - lower_numdigits;
4922 memset(b2s->ptr,
'0',
len);
4925 big2str_2bdigits(b2s, xds, xn, taillen);
4933 if (lower_power_level != power_level-1 && b2s->ptr) {
4934 len = (half_numdigits - lower_numdigits) * 2;
4935 memset(b2s->ptr,
'0',
len);
4939 shift = nlz(bds[bn-1]);
4941 qn = xn + BIGDIVREM_EXTRA_WORDS;
4946 tds = (BDIGIT *)bds;
4954 bary_small_lshift(tds, bds, bn, shift);
4955 xds[xn] = bary_small_lshift(xds, xds, xn, shift);
4958 bigdivrem_restoring(xds, qn, tds, bn);
4967 bary_small_rshift(rds, rds, rn, shift, 0);
4970 BARY_TRUNC(qds, qn);
4972 big2str_karatsuba(b2s, qds, qn, xn+wn - (rn+qn), lower_power_level, lower_numdigits+taillen);
4973 BARY_TRUNC(rds, rn);
4974 big2str_karatsuba(b2s, rds, rn, xn+wn - rn, lower_power_level, taillen);
4979big2str_base_poweroftwo(
VALUE x,
int base)
4981 int word_numbits = ffs(base) - 1;
4985 numwords = rb_absint_numwords(x, word_numbits, NULL);
4986 if (BIGNUM_NEGATIVE_P(x)) {
4987 if (LONG_MAX-1 < numwords)
4988 rb_raise(rb_eArgError,
"too big number");
4990 ptr = RSTRING_PTR(result);
4991 *
ptr++ = BIGNUM_POSITIVE_P(x) ?
'+' :
'-';
4994 if (LONG_MAX < numwords)
4995 rb_raise(rb_eArgError,
"too big number");
4997 ptr = RSTRING_PTR(result);
4999 rb_integer_pack(x,
ptr, numwords, 1, CHAR_BIT-word_numbits,
5001 while (0 < numwords) {
5002 *
ptr = ruby_digitmap[*(
unsigned char *)
ptr];
5010rb_big2str_poweroftwo(
VALUE x,
int base)
5012 return big2str_base_poweroftwo(x, base);
5016big2str_generic(
VALUE x,
int base)
5026 BARY_TRUNC(xds, xn);
5032 if (!valid_radix_p(base))
5033 invalid_radix(base);
5035 if (xn >= LONG_MAX/BITSPERDIG) {
5036 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'string'");
5040 power = power_cache_get_power(base, power_level, NULL);
5041 while (power_level < MAX_BASE36_POWER_TABLE_ENTRIES &&
5042 (
size_t)BIGNUM_LEN(power) <= (xn+1)/2) {
5044 power = power_cache_get_power(base, power_level, NULL);
5046 RUBY_ASSERT(power_level != MAX_BASE36_POWER_TABLE_ENTRIES);
5048 if ((
size_t)BIGNUM_LEN(power) <= xn) {
5062 b2s_data.negative = BIGNUM_NEGATIVE_P(x);
5063 b2s_data.base = base;
5064 b2s_data.hbase2 = maxpow_in_bdigit_dbl(base, &b2s_data.hbase2_numdigits);
5066 b2s_data.result =
Qnil;
5067 b2s_data.ptr = NULL;
5069 if (power_level == 0) {
5070 big2str_2bdigits(&b2s_data, xds, xn, 0);
5076 wn = power_level * BIGDIVREM_EXTRA_WORDS + BIGNUM_LEN(power);
5077 wds =
ALLOCV_N(BDIGIT, tmpw, xn + wn);
5078 MEMCPY(wds, xds, BDIGIT, xn);
5079 big2str_karatsuba(&b2s_data, wds, xn, wn, power_level, 0);
5085 *b2s_data.ptr =
'\0';
5086 rb_str_resize(b2s_data.result, (
long)(b2s_data.ptr - RSTRING_PTR(b2s_data.result)));
5089 return b2s_data.result;
5093rb_big2str_generic(
VALUE x,
int base)
5095 return big2str_generic(x, base);
5100big2str_gmp(
VALUE x,
int base)
5105 BDIGIT *xds = BDIGITS(x);
5106 size_t xn = BIGNUM_LEN(x);
5109 bdigits_to_mpz(mx, xds, xn);
5111 size = mpz_sizeinbase(mx, base);
5113 if (BIGNUM_NEGATIVE_P(x)) {
5120 mpz_get_str(RSTRING_PTR(str), base, mx);
5123 if (RSTRING_PTR(str)[RSTRING_LEN(str)-1] ==
'\0') {
5132rb_big2str_gmp(
VALUE x,
int base)
5134 return big2str_gmp(x, base);
5139rb_big2str1(
VALUE x,
int base)
5151 BARY_TRUNC(xds, xn);
5157 if (!valid_radix_p(base))
5158 invalid_radix(base);
5160 if (xn >= LONG_MAX/BITSPERDIG) {
5161 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'string'");
5166 return big2str_base_poweroftwo(x, base);
5170 if (GMP_BIG2STR_DIGITS < xn) {
5171 return big2str_gmp(x, base);
5175 return big2str_generic(x, base);
5181 return rb_big2str1(x, base);
5187#if SIZEOF_LONG > SIZEOF_BDIGIT
5190 size_t len = BIGNUM_LEN(x);
5196 if (BIGSIZE(x) >
sizeof(
long)) {
5200#if SIZEOF_LONG <= SIZEOF_BDIGIT
5201 num = (
unsigned long)ds[0];
5204 for (i = 0; i <
len; i++) {
5206 num += (
unsigned long)ds[
len - i - 1];
5215 unsigned long num = big2ulong(x,
"unsigned long");
5217 if (BIGNUM_POSITIVE_P(x)) {
5221 if (num <= 1+(
unsigned long)(-(LONG_MIN+1)))
5222 return -(long)(num-1)-1;
5224 rb_raise(
rb_eRangeError,
"bignum out of range of unsigned long");
5230 unsigned long num = big2ulong(x,
"long");
5232 if (BIGNUM_POSITIVE_P(x)) {
5233 if (num <= LONG_MAX)
5237 if (num <= 1+(
unsigned long)(-(LONG_MIN+1)))
5238 return -(long)(num-1)-1;
5240 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'long'");
5248#if SIZEOF_LONG_LONG > SIZEOF_BDIGIT
5251 size_t len = BIGNUM_LEN(x);
5253 BDIGIT *ds = BDIGITS(x);
5257 if (BIGSIZE(x) > SIZEOF_LONG_LONG)
5259#if SIZEOF_LONG_LONG <= SIZEOF_BDIGIT
5263 for (i = 0; i <
len; i++) {
5265 num += ds[
len - i - 1];
5274 unsigned LONG_LONG num = big2ull(x,
"unsigned long long");
5276 if (BIGNUM_POSITIVE_P(x)) {
5280 if (num <= 1+(
unsigned LONG_LONG)(-(LLONG_MIN+1)))
5283 rb_raise(
rb_eRangeError,
"bignum out of range of unsigned long long");
5289 unsigned LONG_LONG num = big2ull(x,
"long long");
5291 if (BIGNUM_POSITIVE_P(x)) {
5292 if (num <= LLONG_MAX)
5296 if (num <= 1+(
unsigned LONG_LONG)(-(LLONG_MIN+1)))
5299 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'long long'");
5311 double u = (d < 0)?-d:d;
5321 u /= (double)(BIGRAD);
5324 z = bignew(i, d>=0);
5325 digits = BDIGITS(z);
5339 return bignorm(dbl2big(d));
5346 long i = (bigtrunc(x), BIGNUM_LEN(x)), lo = 0, bits;
5347 BDIGIT *ds = BDIGITS(x), dl;
5350 bits = i * BITSPERDIG - nlz(ds[i-1]);
5351 if (bits > DBL_MANT_DIG+DBL_MAX_EXP) {
5355 if (bits > DBL_MANT_DIG+1)
5356 lo = (bits -= DBL_MANT_DIG+1) / BITSPERDIG;
5360 d = ds[i] + BIGRAD*d;
5363 if (bits && (dl & ((BDIGIT)1 << (bits %= BITSPERDIG)))) {
5364 int carry = (dl & ~(BDIGMAX << bits)) != 0;
5372 BDIGIT mask = BDIGMAX;
5384 if (lo > INT_MAX / BITSPERDIG)
5386 else if (lo < INT_MIN / BITSPERDIG)
5389 d = ldexp(d, (
int)(lo * BITSPERDIG));
5393 if (BIGNUM_NEGATIVE_P(x)) d = -d;
5400 double d = big2dbl(x);
5422 if (yd > 0.0)
return INT2FIX(-1);
5427#if SIZEOF_LONG * CHAR_BIT < DBL_MANT_DIG
5454 rel = rb_big_cmp(x, y);
5455 if (yf == 0.0 || rel !=
INT2FIX(0))
5462#if SIZEOF_LONG * CHAR_BIT >= DBL_MANT_DIG
5463COMPILER_WARNING_PUSH
5464#if __has_warning("-Wimplicit-int-float-conversion")
5465COMPILER_WARNING_IGNORED(-Wimplicit-
int-
float-conversion)
5467static const double LONG_MAX_as_double = LONG_MAX;
5483#if SIZEOF_LONG * CHAR_BIT < DBL_MANT_DIG
5485 return RBOOL(xd == yd);
5488 if (yi < LONG_MIN || LONG_MAX_as_double <= yi)
5492 return RBOOL(xn == yn);
5496 return rb_big_eq(x, y);
5509 if (sx < sy)
return INT2FIX(-1);
5513 else if (RB_BIGNUM_TYPE_P(y)) {
5514 if (BIGNUM_SIGN(x) == BIGNUM_SIGN(y)) {
5515 int cmp = bary_cmp(BDIGITS(x), BIGNUM_LEN(x), BDIGITS(y), BIGNUM_LEN(y));
5516 return INT2FIX(BIGNUM_SIGN(x) ? cmp : -cmp);
5519 else if (RB_FLOAT_TYPE_P(y)) {
5520 return rb_integer_float_cmp(x, y);
5525 return INT2FIX(BIGNUM_SIGN(x) ? 1 : -1);
5542 rel = rb_big_cmp(x, y);
5544 else if (RB_FLOAT_TYPE_P(y)) {
5545 rel = rb_integer_float_cmp(x, y);
5550 case big_op_gt:
id =
'>';
break;
5551 case big_op_ge:
id = idGE;
break;
5552 case big_op_lt:
id =
'<';
break;
5553 case big_op_le:
id = idLE;
break;
5562 case big_op_gt:
return RBOOL(n > 0);
5563 case big_op_ge:
return RBOOL(n >= 0);
5564 case big_op_lt:
return RBOOL(n < 0);
5565 case big_op_le:
return RBOOL(n <= 0);
5573 return big_op(x, y, big_op_gt);
5579 return big_op(x, y, big_op_ge);
5585 return big_op(x, y, big_op_lt);
5591 return big_op(x, y, big_op_le);
5609 return RBOOL(bignorm(x) == y);
5611 else if (RB_BIGNUM_TYPE_P(y)) {
5613 else if (RB_FLOAT_TYPE_P(y)) {
5614 return rb_integer_float_eq(x, y);
5619 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y))
return Qfalse;
5620 if (BIGNUM_LEN(x) != BIGNUM_LEN(y))
return Qfalse;
5621 return RBOOL(
MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,BIGNUM_LEN(y)) == 0);
5627 if (!RB_BIGNUM_TYPE_P(y))
return Qfalse;
5628 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y))
return Qfalse;
5629 if (BIGNUM_LEN(x) != BIGNUM_LEN(y))
return Qfalse;
5630 return RBOOL(
MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,BIGNUM_LEN(y)) == 0);
5634rb_big_uminus(
VALUE x)
5636 VALUE z = rb_big_clone(x);
5646 VALUE z = rb_big_clone(x);
5647 BDIGIT *ds = BDIGITS(z);
5648 long n = BIGNUM_LEN(z);
5652 if (BIGNUM_POSITIVE_P(z)) {
5653 if (bary_add_one(ds, n)) {
5654 big_extend_carry(z);
5656 BIGNUM_SET_NEGATIVE_SIGN(z);
5660 if (bary_add_one(ds, n))
5663 BIGNUM_SET_POSITIVE_SIGN(z);
5673 BDIGIT *xds, *yds, *zds;
5678 zn = xn < yn ? yn : xn;
5686 if (bary_sub(zds, zn, xds, xn, yds, yn)) {
5687 bary_2comp(zds, zn);
5688 BIGNUM_SET_NEGATIVE_SIGN(z);
5697bigsub_int(
VALUE x,
long y0)
5702 BDIGIT_DBL_SIGNED num;
5713#if SIZEOF_BDIGIT < SIZEOF_LONG
5714 if (zn < bdigit_roomof(SIZEOF_LONG))
5715 zn = bdigit_roomof(SIZEOF_LONG);
5717 z = bignew(zn, BIGNUM_SIGN(x));
5720#if SIZEOF_BDIGIT >= SIZEOF_LONG
5722 num = (BDIGIT_DBL_SIGNED)xds[0] - y;
5723 if (xn == 1 && num < 0) {
5725 zds[0] = (BDIGIT)-num;
5729 zds[0] = BIGLO(num);
5737 for (i=0; i < xn; i++) {
5738 if (y == 0)
goto y_is_zero_x;
5739 num += (BDIGIT_DBL_SIGNED)xds[i] - BIGLO(y);
5740 zds[i] = BIGLO(num);
5744 for (; i < zn; i++) {
5745 if (y == 0)
goto y_is_zero_z;
5747 zds[i] = BIGLO(num);
5754 for (; i < xn; i++) {
5756 if (num == 0)
goto num_is_zero_x;
5758 zds[i] = BIGLO(num);
5761#if SIZEOF_BDIGIT < SIZEOF_LONG
5762 for (; i < zn; i++) {
5764 if (num == 0)
goto num_is_zero_z;
5765 zds[i] = BIGLO(num);
5771 for (; i < xn; i++) {
5775#if SIZEOF_BDIGIT < SIZEOF_LONG
5776 for (; i < zn; i++) {
5794bigadd_int(
VALUE x,
long y)
5809#if SIZEOF_BDIGIT < SIZEOF_LONG
5810 if (zn < bdigit_roomof(SIZEOF_LONG))
5811 zn = bdigit_roomof(SIZEOF_LONG);
5815 z = bignew(zn, BIGNUM_SIGN(x));
5818#if SIZEOF_BDIGIT >= SIZEOF_LONG
5819 num = (BDIGIT_DBL)xds[0] + y;
5820 zds[0] = BIGLO(num);
5828 for (i=0; i < xn; i++) {
5829 if (y == 0)
goto y_is_zero_x;
5830 num += (BDIGIT_DBL)xds[i] + BIGLO(y);
5831 zds[i] = BIGLO(num);
5835 for (; i < zn; i++) {
5836 if (y == 0)
goto y_is_zero_z;
5838 zds[i] = BIGLO(num);
5846 for (;i < xn; i++) {
5848 if (num == 0)
goto num_is_zero_x;
5849 num += (BDIGIT_DBL)xds[i];
5850 zds[i] = BIGLO(num);
5853 for (; i < zn; i++) {
5855 if (num == 0)
goto num_is_zero_z;
5856 zds[i] = BIGLO(num);
5861 for (;i < xn; i++) {
5865 for (; i < zn; i++) {
5882 sign = (sign == BIGNUM_SIGN(y));
5883 if (BIGNUM_SIGN(x) != sign) {
5884 if (sign)
return bigsub(y, x);
5885 return bigsub(x, y);
5888 if (BIGNUM_LEN(x) > BIGNUM_LEN(y)) {
5889 len = BIGNUM_LEN(x) + 1;
5892 len = BIGNUM_LEN(y) + 1;
5894 z = bignew(
len, sign);
5896 bary_add(BDIGITS(z), BIGNUM_LEN(z),
5897 BDIGITS(x), BIGNUM_LEN(x),
5898 BDIGITS(y), BIGNUM_LEN(y));
5910 if ((n > 0) != BIGNUM_SIGN(x)) {
5914 return bigsub_int(x, n);
5919 return bigadd_int(x, n);
5921 else if (RB_BIGNUM_TYPE_P(y)) {
5922 return bignorm(bigadd(x, y, 1));
5924 else if (RB_FLOAT_TYPE_P(y)) {
5939 if ((n > 0) != BIGNUM_SIGN(x)) {
5943 return bigadd_int(x, n);
5948 return bigsub_int(x, n);
5950 else if (RB_BIGNUM_TYPE_P(y)) {
5951 return bignorm(bigadd(x, y, 0));
5953 else if (RB_FLOAT_TYPE_P(y)) {
5969 if (MUL_OVERFLOW_LONG_P(2, xn))
5970 rb_raise(rb_eArgError,
"square overflow");
5978 if (xn < NAIVE_MUL_DIGITS)
5979 bary_sq_fast(zds, zn, xds, xn);
5981 bary_mul(zds, zn, xds, xn, xds, xn);
5992 BDIGIT *xds, *yds, *zds;
5999 if (ADD_OVERFLOW_LONG_P(xn, yn))
6000 rb_raise(rb_eArgError,
"multiplication overflow");
6003 z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6009 bary_mul(zds, zn, xds, xn, yds, yn);
6022 else if (RB_BIGNUM_TYPE_P(y)) {
6024 else if (RB_FLOAT_TYPE_P(y)) {
6031 return bignorm(bigmul0(x, y));
6037 long xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y);
6039 BDIGIT *xds, *yds, *zds;
6047 BARY_TRUNC(yds, yn);
6052 BARY_TRUNC(xds, xn);
6054 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1])) {
6055 if (divp) *divp = rb_int2big(0);
6056 if (modp) *modp = x;
6061 z = bignew(xn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6063 dd = bigdivrem_single(zds, xds, xn, dd);
6065 *modp = rb_uint2big((uintptr_t)dd);
6066 BIGNUM_SET_SIGN(*modp, BIGNUM_SIGN(x));
6068 if (divp) *divp = z;
6071 if (xn == 2 && yn == 2) {
6072 BDIGIT_DBL x0 = bary2bdigitdbl(xds, 2);
6073 BDIGIT_DBL y0 = bary2bdigitdbl(yds, 2);
6074 BDIGIT_DBL q0 = x0 / y0;
6075 BDIGIT_DBL r0 = x0 % y0;
6077 z = bignew(bdigit_roomof(
sizeof(BDIGIT_DBL)), BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6080 zds[1] = BIGLO(BIGDN(q0));
6084 z = bignew(bdigit_roomof(
sizeof(BDIGIT_DBL)), BIGNUM_SIGN(x));
6087 zds[1] = BIGLO(BIGDN(r0));
6094 qn = xn + BIGDIVREM_EXTRA_WORDS;
6095 q = bignew(qn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6105 r = bignew(rn, BIGNUM_SIGN(x));
6113 bary_divmod_branch(qds, qn, rds, rn, xds, xn, yds, yn);
6132 bigdivrem(x, y, divp, &mod);
6133 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y) && !BIGZEROP(mod)) {
6134 if (divp) *divp = bigadd(*divp, rb_int2big(1), 0);
6135 if (modp) *modp = bigadd(mod, y, 1);
6151 else if (RB_BIGNUM_TYPE_P(y)) {
6153 else if (RB_FLOAT_TYPE_P(y)) {
6155 double dx = rb_big2dbl(x);
6156 return rb_flo_div_flo(
DBL2NUM(dx), y);
6162 v = rb_big_divide(x, y,
'/');
6169 bigdivmod(x, y, &z, 0);
6177 return rb_big_divide(x, y,
'/');
6183 return rb_big_divide(x, y, idDiv);
6194 else if (!RB_BIGNUM_TYPE_P(y)) {
6197 bigdivmod(x, y, 0, &z);
6210 else if (!RB_BIGNUM_TYPE_P(y)) {
6213 bigdivrem(x, y, 0, &z);
6226 else if (!RB_BIGNUM_TYPE_P(y)) {
6229 bigdivmod(x, y, &div, &mod);
6235big_shift(
VALUE x,
long n)
6238 return big_lshift(x, 1+(
unsigned long)(-(n+1)));
6240 return big_rshift(x, (
unsigned long)n);
6244enum {DBL_BIGDIG = ((DBL_MANT_DIG + BITSPERDIG) / BITSPERDIG)};
6254 ex = l * BITSPERDIG - nlz(BDIGITS(x)[l-1]);
6255 ex -= 2 * DBL_BIGDIG * BITSPERDIG;
6256 if (ex > BITSPERDIG) ex -= BITSPERDIG;
6257 else if (ex > 0) ex = 0;
6258 if (ex) x = big_shift(x, ex);
6260 bigdivrem(x, y, &z, 0);
6262#if SIZEOF_LONG > SIZEOF_INT
6265 if (l > INT_MAX)
return HUGE_VAL;
6266 if (l < INT_MIN)
return 0.0;
6269 return ldexp(big2dbl(z), (
int)l);
6278 ey = l * BITSPERDIG - nlz(BDIGITS(y)[l-1]);
6279 ey -= DBL_BIGDIG * BITSPERDIG;
6280 if (ey) y = big_shift(y, ey);
6281 return big_fdiv(x, y, ey);
6288 y = dbl2big(ldexp(frexp(
RFLOAT_VALUE(y), &i), DBL_MANT_DIG));
6289 return big_fdiv(x, y, i - DBL_MANT_DIG);
6302 return big_fdiv_int(x, rb_int2big(
FIX2LONG(y)));
6304 else if (RB_BIGNUM_TYPE_P(y)) {
6305 return big_fdiv_int(x, y);
6307 else if (RB_FLOAT_TYPE_P(y)) {
6312 return big_fdiv_float(x, y);
6324 return DBL2NUM(rb_big_fdiv_double(x, y));
6335 if (y ==
INT2FIX(1))
return x;
6336 if (RB_FLOAT_TYPE_P(y)) {
6338 if ((BIGNUM_NEGATIVE_P(x) && !BIGZEROP(x))) {
6339 return rb_dbl_complex_new_polar_pi(pow(-rb_big2dbl(x), d), d);
6342 else if (RB_BIGNUM_TYPE_P(y)) {
6346 rb_raise(rb_eArgError,
"exponent is too large");
6361 const size_t xbits = rb_absint_numwords(x, 1, NULL);
6362#if SIZEOF_SIZE_T == 4
6363 const size_t BIGLEN_LIMIT = 1ULL << 31;
6365 const size_t BIGLEN_LIMIT = 1ULL << 34;
6368 if (xbits == (
size_t)-1 ||
6369 (xbits > BIGLEN_LIMIT) ||
6370 MUL_OVERFLOW_LONG_P(yy, xbits) ||
6371 (xbits * yy > BIGLEN_LIMIT)) {
6372 rb_raise(rb_eArgError,
"exponent is too large");
6375 for (mask =
FIXNUM_MAX + 1; mask; mask >>= 1) {
6376 if (z) z = bigsq(z);
6378 z = z ? bigtrunc(bigmul0(z, x)) : x;
6388 return DBL2NUM(pow(rb_big2dbl(x), d));
6392bigand_int(
VALUE x,
long xn, BDIGIT hibitsx,
long y)
6400 if (y == 0)
return INT2FIX(0);
6402 hibitsy = 0 <= y ? 0 : BDIGMAX;
6404#if SIZEOF_BDIGIT >= SIZEOF_LONG
6412#if SIZEOF_BDIGIT < SIZEOF_LONG
6413 if (hibitsx && zn < bdigit_roomof(SIZEOF_LONG))
6414 zn = bdigit_roomof(SIZEOF_LONG);
6420#if SIZEOF_BDIGIT >= SIZEOF_LONG
6422 zds[0] = xds[0] & BIGLO(y);
6424 for (i=0; i < xn; i++) {
6425 if (y == 0 || y == -1)
break;
6426 zds[i] = xds[i] & BIGLO(y);
6429 for (; i < zn; i++) {
6430 if (y == 0 || y == -1)
break;
6431 zds[i] = hibitsx & BIGLO(y);
6435 for (;i < xn; i++) {
6436 zds[i] = xds[i] & hibitsy;
6438 for (;i < zn; i++) {
6439 zds[i] = hibitsx & hibitsy;
6441 twocomp2abs_bang(z, hibitsx && hibitsy);
6450 BDIGIT *ds1, *ds2, *zds;
6451 long i, xn, yn, n1, n2;
6452 BDIGIT hibitsx, hibitsy;
6453 BDIGIT hibits1, hibits2;
6462 hibitsx = abs2twocomp(&x, &xn);
6464 return bigand_int(x, xn, hibitsx,
FIX2LONG(y));
6466 hibitsy = abs2twocomp(&y, &yn);
6468 tmpv = x; x = y; y = tmpv;
6469 tmpn = xn; xn = yn; yn = tmpn;
6470 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6485 for (i=0; i<n1; i++) {
6486 zds[i] = ds1[i] & ds2[i];
6489 zds[i] = hibits1 & ds2[i];
6491 twocomp2abs_bang(z, hibits1 && hibits2);
6498bigor_int(
VALUE x,
long xn, BDIGIT hibitsx,
long y)
6506 if (y == -1)
return INT2FIX(-1);
6508 hibitsy = 0 <= y ? 0 : BDIGMAX;
6512#if SIZEOF_BDIGIT < SIZEOF_LONG
6513 if (zn < bdigit_roomof(SIZEOF_LONG))
6514 zn = bdigit_roomof(SIZEOF_LONG);
6519#if SIZEOF_BDIGIT >= SIZEOF_LONG
6521 zds[0] = xds[0] | BIGLO(y);
6523 goto y_is_fixed_point;
6526 for (i=0; i < xn; i++) {
6527 if (y == 0 || y == -1)
goto y_is_fixed_point;
6528 zds[i] = xds[i] | BIGLO(y);
6533 for (; i < zn; i++) {
6534 if (y == 0 || y == -1)
goto y_is_fixed_point;
6544 for (; i < xn; i++) {
6549 for (; i < zn; i++) {
6555 for (; i < zn; i++) {
6560 twocomp2abs_bang(z, hibitsx || hibitsy);
6569 BDIGIT *ds1, *ds2, *zds;
6570 long i, xn, yn, n1, n2;
6571 BDIGIT hibitsx, hibitsy;
6572 BDIGIT hibits1, hibits2;
6581 hibitsx = abs2twocomp(&x, &xn);
6583 return bigor_int(x, xn, hibitsx,
FIX2LONG(y));
6585 hibitsy = abs2twocomp(&y, &yn);
6587 tmpv = x; x = y; y = tmpv;
6588 tmpn = xn; xn = yn; yn = tmpn;
6589 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6604 for (i=0; i<n1; i++) {
6605 zds[i] = ds1[i] | ds2[i];
6608 zds[i] = hibits1 | ds2[i];
6610 twocomp2abs_bang(z, hibits1 || hibits2);
6617bigxor_int(
VALUE x,
long xn, BDIGIT hibitsx,
long y)
6625 hibitsy = 0 <= y ? 0 : BDIGMAX;
6628#if SIZEOF_BDIGIT < SIZEOF_LONG
6629 if (zn < bdigit_roomof(SIZEOF_LONG))
6630 zn = bdigit_roomof(SIZEOF_LONG);
6635#if SIZEOF_BDIGIT >= SIZEOF_LONG
6637 zds[0] = xds[0] ^ BIGLO(y);
6639 for (i = 0; i < xn; i++) {
6640 zds[i] = xds[i] ^ BIGLO(y);
6643 for (; i < zn; i++) {
6644 zds[i] = hibitsx ^ BIGLO(y);
6648 for (; i < xn; i++) {
6649 zds[i] = xds[i] ^ hibitsy;
6651 for (; i < zn; i++) {
6652 zds[i] = hibitsx ^ hibitsy;
6654 twocomp2abs_bang(z, (hibitsx ^ hibitsy) != 0);
6663 BDIGIT *ds1, *ds2, *zds;
6664 long i, xn, yn, n1, n2;
6665 BDIGIT hibitsx, hibitsy;
6666 BDIGIT hibits1, hibits2;
6675 hibitsx = abs2twocomp(&x, &xn);
6677 return bigxor_int(x, xn, hibitsx,
FIX2LONG(y));
6679 hibitsy = abs2twocomp(&y, &yn);
6681 tmpv = x; x = y; y = tmpv;
6682 tmpn = xn; xn = yn; yn = tmpn;
6683 tmph = hibitsx; hibitsx = hibitsy; hibitsy = tmph;
6695 for (i=0; i<n1; i++) {
6696 zds[i] = ds1[i] ^ ds2[i];
6699 zds[i] = hibitsx ^ ds2[i];
6701 twocomp2abs_bang(z, (hibits1 ^ hibits2) != 0);
6711 size_t shift_numdigits;
6717 unsigned long shift;
6724 shift = 1+(
unsigned long)(-(l+1));
6726 shift_numbits = (int)(shift & (BITSPERDIG-1));
6727 shift_numdigits = shift >> bit_length(BITSPERDIG-1);
6728 return bignorm(big_shift3(x, lshift_p, shift_numdigits, shift_numbits));
6730 else if (RB_BIGNUM_TYPE_P(y)) {
6731 return bignorm(big_shift2(x, 1, y));
6741 size_t shift_numdigits;
6747 unsigned long shift;
6754 shift = 1+(
unsigned long)(-(l+1));
6756 shift_numbits = (int)(shift & (BITSPERDIG-1));
6757 shift_numdigits = shift >> bit_length(BITSPERDIG-1);
6758 return bignorm(big_shift3(x, lshift_p, shift_numdigits, shift_numbits));
6760 else if (RB_BIGNUM_TYPE_P(y)) {
6761 return bignorm(big_shift2(x, 0, y));
6776 if (RB_BIGNUM_TYPE_P(y)) {
6777 if (BIGNUM_NEGATIVE_P(y))
6780 if (BIGSIZE(y) >
sizeof(
size_t)) {
6783#if SIZEOF_SIZE_T <= SIZEOF_LONG
6784 shift = big2ulong(y,
"long");
6786 shift = big2ull(y,
"long long");
6794 s1 = shift/BITSPERDIG;
6795 s2 = shift%BITSPERDIG;
6796 bit = (BDIGIT)1 << s2;
6798 if (s1 >= BIGNUM_LEN(x))
6802 if (BIGNUM_POSITIVE_P(x))
6804 if (xds[s1] & (bit-1))
6806 for (i = 0; i < s1; i++)
6817 size_t copy_begin, xn, shift;
6818 ssize_t begin, length, end;
6819 bool negative_add_one;
6826 shift = begin < 0 ? -begin : 0;
6830 if (length < 0)
return rb_big_rshift(x, beg);
6831 if (length == 0 || end <= 0)
return INT2FIX(0);
6832 if (begin < 0) begin = 0;
6834 if ((
size_t)(end - 1) / BITSPERDIG >= xn) {
6836 end = xn * BITSPERDIG;
6839 if ((
size_t)begin / BITSPERDIG < xn) {
6841 size_t shift_bits, copy_end;
6842 copy_begin = begin / BITSPERDIG;
6843 shift_bits = begin % BITSPERDIG;
6844 copy_end = (end - 1) / BITSPERDIG + 1;
6845 v = bignew(copy_end - copy_begin, 1);
6847 MEMCPY(vds, xds + copy_begin, BDIGIT, copy_end - copy_begin);
6848 negative_add_one = (vds[0] & ((1 << shift_bits) - 1)) == 0;
6850 if (shift_bits) v = rb_int_rshift(v,
SIZET2NUM(shift_bits));
6855 negative_add_one =
false;
6856 copy_begin = begin = end = 0;
6859 if (BIGNUM_NEGATIVE_P(x)) {
6860 size_t mask_size = length - shift;
6862 v = rb_int_xor(v, mask);
6863 for (
size_t i = 0; negative_add_one && i < copy_begin; i++) {
6864 if (xds[i]) negative_add_one =
false;
6866 if (negative_add_one) v = rb_int_plus(v,
INT2FIX(1));
6867 v = rb_int_and(v, mask);
6870 size_t mask_size = (size_t)end - begin;
6872 v = rb_int_and(v, mask);
6875 if (shift) v = rb_int_lshift(v,
SSIZET2NUM(shift));
6884 hash =
rb_memhash(BDIGITS(x),
sizeof(BDIGIT)*BIGNUM_LEN(x)) ^ BIGNUM_SIGN(x);
6919 if (BIGNUM_NEGATIVE_P(x)) {
6920 x = rb_big_clone(x);
6921 BIGNUM_SET_POSITIVE_SIGN(x);
6929 return BIGNUM_SIGN(x);
6933rb_big_size(
VALUE big)
6935 return BIGSIZE(big);
6939rb_big_size_m(
VALUE big)
6945rb_big_bit_length(
VALUE big)
6950 static const BDIGIT char_bit[1] = { CHAR_BIT };
6951 BDIGIT numbytes_bary[bdigit_roomof(
sizeof(
size_t))];
6953 BDIGIT result_bary[bdigit_roomof(
sizeof(
size_t)+1)];
6955 numbytes = rb_absint_size(big, &nlz_bits);
6960 if (BIGNUM_NEGATIVE_P(big) && rb_absint_singlebit_p(big)) {
6961 if (nlz_bits != CHAR_BIT-1) {
6970 if (numbytes <= SIZE_MAX / CHAR_BIT) {
6971 return SIZET2NUM(numbytes * CHAR_BIT - nlz_bits);
6974 nlz_bary[0] = nlz_bits;
6976 bary_unpack(BARY_ARGS(numbytes_bary), &numbytes, 1,
sizeof(numbytes), 0,
6978 BARY_SHORT_MUL(result_bary, numbytes_bary, char_bit);
6979 BARY_SUB(result_bary, result_bary, nlz_bary);
6981 return rb_integer_unpack(result_bary, numberof(result_bary),
sizeof(BDIGIT), 0,
6986rb_big_odd_p(
VALUE num)
6988 return RBOOL(BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1);
6992rb_big_even_p(
VALUE num)
6994 if (BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1) {
7000unsigned long rb_ulong_isqrt(
unsigned long);
7001#if SIZEOF_BDIGIT*2 > SIZEOF_LONG
7002BDIGIT rb_bdigit_dbl_isqrt(BDIGIT_DBL);
7003# ifdef ULL_TO_DOUBLE
7004# define BDIGIT_DBL_TO_DOUBLE(n) ULL_TO_DOUBLE(n)
7007# define rb_bdigit_dbl_isqrt(x) (BDIGIT)rb_ulong_isqrt(x)
7009#ifndef BDIGIT_DBL_TO_DOUBLE
7010# define BDIGIT_DBL_TO_DOUBLE(n) (double)(n)
7014rb_big_isqrt(
VALUE n)
7016 BDIGIT *nds = BDIGITS(n);
7017 size_t len = BIGNUM_LEN(n);
7020 BDIGIT sq = rb_bdigit_dbl_isqrt(bary2bdigitdbl(nds,
len));
7021#if SIZEOF_BDIGIT > SIZEOF_LONG
7028 size_t shift =
FIX2LONG(rb_big_bit_length(n)) / 4;
7032 x = rb_int_plus(rb_int_lshift(x,
SIZET2NUM(shift - 1)), rb_int_idiv(rb_int_rshift(n,
SIZET2NUM(shift + 1)), x));
7033 VALUE xx = rb_int_mul(x, x);
7034 while (rb_int_gt(xx, n)) {
7035 xx = rb_int_minus(xx, rb_int_minus(rb_int_plus(x, x),
INT2FIX(1)));
7036 x = rb_int_minus(x,
INT2FIX(1));
7044bary_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)
7052 bdigits_to_mpz(x, xds, xn);
7053 bdigits_to_mpz(y, yds, yn);
7054 bdigits_to_mpz(m, mds, mn);
7055 mpz_powm(z, x, y, m);
7056 bdigits_from_mpz(z, zds, &count);
7057 BDIGITS_ZERO(zds+count, zn-count);
7070 size_t xn, yn, mn, zn;
7084 bary_powm_gmp(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, BDIGITS(m), mn);
7085 if (nega_flg && BIGNUM_POSITIVE_P(z) && !BIGZEROP(z)) {
7086 z = rb_big_minus(z, m);
7091 return rb_big_norm(z);
7097 if (
RTEST(rb_int_odd_p(y))) {
7098 tmp = rb_int_mul(tmp, x);
7099 tmp = rb_int_modulo(tmp, m);
7101 x = rb_int_mul(x, x);
7102 x = rb_int_modulo(x, m);
7104 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7106 tmp = rb_int_mul(tmp, x);
7107 tmp = rb_int_modulo(tmp, m);
7109 x = rb_int_mul(x, x);
7110 x = rb_int_modulo(x, m);
7113 if (nega_flg && rb_int_positive_p(tmp) && !rb_int_zero_p(tmp)) {
7114 tmp = rb_int_minus(tmp, m);
7125int_pow_tmp1(
VALUE x,
VALUE y,
long mm,
int nega_flg)
7132 if (
RTEST(rb_int_odd_p(y))) {
7133 tmp = (tmp * xx) % mm;
7135 xx = (xx * xx) % mm;
7137 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7139 tmp = (tmp * xx) % mm;
7141 xx = (xx * xx) % mm;
7144 if (nega_flg && tmp) {
7151int_pow_tmp2(
VALUE x,
VALUE y,
long mm,
int nega_flg)
7159# define MUL_MODULO(a, b, c) (long)(((DLONG)(a) * (DLONG)(b)) % (c))
7164# define MUL_MODULO(a, b, c) rb_int_modulo(rb_fix_mul_fix((a), (b)), (c))
7168 if (
RTEST(rb_int_odd_p(y))) {
7169 tmp2 = MUL_MODULO(tmp2, xx, m);
7171 xx = MUL_MODULO(xx, xx, m);
7173 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7175 tmp2 = MUL_MODULO(tmp2, xx, m);
7177 xx = MUL_MODULO(xx, xx, m);
7185 if (nega_flg && tmp) {
7203rb_int_powm(
int const argc,
VALUE *
const argv,
VALUE const num)
7205 rb_check_arity(argc, 1, 2);
7208 return rb_int_pow(num, argv[0]);
7211 VALUE const a = num;
7212 VALUE const b = argv[0];
7216 rb_raise(
rb_eTypeError,
"Integer#pow() 2nd argument not allowed unless a 1st argument is integer");
7218 if (rb_int_negative_p(b)) {
7219 rb_raise(
rb_eRangeError,
"Integer#pow() 1st argument cannot be negative when 2nd argument specified");
7222 rb_raise(
rb_eTypeError,
"Integer#pow() 2nd argument not allowed unless all arguments are integers");
7225 if (rb_int_zero_p(a) && !rb_int_zero_p(b)) {
7230 if (rb_int_negative_p(m)) {
7231 m = rb_int_uminus(m);
7236 long const half_val = (long)HALF_LONG_MSB;
7239 if (mm == 1)
return INT2FIX(0);
7240 if (mm <= half_val) {
7241 return int_pow_tmp1(rb_int_modulo(a, m), b, mm, nega_flg);
7244 return int_pow_tmp2(rb_int_modulo(a, m), b, mm, nega_flg);
7250 return int_pow_tmp3(rb_int_modulo(a, m), b, m, nega_flg);
7281 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 ISSPACE
@old{rb_isspace}
#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 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.
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 capa
Designed capacity of the buffer.
char * ptr
Pointer to the underlying memory region, of at least capa bytes.
int len
Length of the buffer.
#define RB_NOGVL_UBF_ASYNC_SAFE
Passing this flag to rb_nogvl() indicates that the passed UBF is async-signal-safe.
void * rb_nogvl(void *(*func)(void *), void *data1, rb_unblock_function_t *ubf, void *data2, int flags)
Identical to rb_thread_call_without_gvl(), except it additionally takes "flags" that change the behav...
#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.
#define RBIMPL_WARNING_IGNORED(flag)
Suppresses a warning.
#define RBIMPL_WARNING_PUSH()
Pushes compiler warning state.
#define RBIMPL_WARNING_POP()
Pops compiler warning state.