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"
48#include "ruby_assert.h"
60static const bool debug_integer_pack = (
61#ifdef DEBUG_INTEGER_PACK
73RBIMPL_ATTR_NONSTRING_ARRAY() const
char ruby_decimal_digit_pairs[100][2] = {
74 "00",
"01",
"02",
"03",
"04",
"05",
"06",
"07",
"08",
"09",
75 "10",
"11",
"12",
"13",
"14",
"15",
"16",
"17",
"18",
"19",
76 "20",
"21",
"22",
"23",
"24",
"25",
"26",
"27",
"28",
"29",
77 "30",
"31",
"32",
"33",
"34",
"35",
"36",
"37",
"38",
"39",
78 "40",
"41",
"42",
"43",
"44",
"45",
"46",
"47",
"48",
"49",
79 "50",
"51",
"52",
"53",
"54",
"55",
"56",
"57",
"58",
"59",
80 "60",
"61",
"62",
"63",
"64",
"65",
"66",
"67",
"68",
"69",
81 "70",
"71",
"72",
"73",
"74",
"75",
"76",
"77",
"78",
"79",
82 "80",
"81",
"82",
"83",
"84",
"85",
"86",
"87",
"88",
"89",
83 "90",
"91",
"92",
"93",
"94",
"95",
"96",
"97",
"98",
"99",
86#ifndef SIZEOF_BDIGIT_DBL
87# if SIZEOF_INT*2 <= SIZEOF_LONG_LONG
88# define SIZEOF_BDIGIT_DBL SIZEOF_LONG_LONG
90# define SIZEOF_BDIGIT_DBL SIZEOF_LONG
94STATIC_ASSERT(sizeof_bdigit_dbl,
sizeof(BDIGIT_DBL) == SIZEOF_BDIGIT_DBL);
95STATIC_ASSERT(sizeof_bdigit_dbl_signed,
sizeof(BDIGIT_DBL_SIGNED) == SIZEOF_BDIGIT_DBL);
96STATIC_ASSERT(sizeof_bdigit, SIZEOF_BDIGIT <=
sizeof(BDIGIT));
97STATIC_ASSERT(sizeof_bdigit_and_dbl, SIZEOF_BDIGIT*2 <= SIZEOF_BDIGIT_DBL);
98STATIC_ASSERT(bdigit_signedness, 0 < (BDIGIT)-1);
99STATIC_ASSERT(bdigit_dbl_signedness, 0 < (BDIGIT_DBL)-1);
100STATIC_ASSERT(bdigit_dbl_signed_signedness, 0 > (BDIGIT_DBL_SIGNED)-1);
102#if SIZEOF_BDIGIT < SIZEOF_LONG
103STATIC_ASSERT(sizeof_long_and_sizeof_bdigit, SIZEOF_LONG % SIZEOF_BDIGIT == 0);
105STATIC_ASSERT(sizeof_long_and_sizeof_bdigit, SIZEOF_BDIGIT % SIZEOF_LONG == 0);
108#ifdef WORDS_BIGENDIAN
109# define HOST_BIGENDIAN_P 1
111# define HOST_BIGENDIAN_P 0
114#define LSHIFTABLE(d, n) ((n) < sizeof(d) * CHAR_BIT)
115#define LSHIFTX(d, n) (!LSHIFTABLE(d, n) ? 0 : ((d) << (!LSHIFTABLE(d, n) ? 0 : (n))))
116#define CLEAR_LOWBITS(d, numbits) ((d) & LSHIFTX(~((d)*0), (numbits)))
117#define FILL_LOWBITS(d, numbits) ((d) | (LSHIFTX(((d)*0+1), (numbits))-1))
118#define POW2_P(x) (((x)&((x)-1))==0)
120#define BDIGITS(x) (BIGNUM_DIGITS(x))
121#define BITSPERDIG (SIZEOF_BDIGIT*CHAR_BIT)
122#define BIGRAD ((BDIGIT_DBL)1 << BITSPERDIG)
123#define BIGRAD_HALF ((BDIGIT)(BIGRAD >> 1))
124#define BDIGIT_MSB(d) (((d) & BIGRAD_HALF) != 0)
125#define BIGUP(x) LSHIFTX(((x) + (BDIGIT_DBL)0), BITSPERDIG)
126#define BIGDN(x) RSHIFT((x),BITSPERDIG)
127#define BIGLO(x) ((BDIGIT)((x) & BDIGMAX))
128#define BDIGMAX ((BDIGIT)(BIGRAD-1))
129#define BDIGIT_DBL_MAX (~(BDIGIT_DBL)0)
131#if SIZEOF_BDIGIT == 2
132# define swap_bdigit(x) swap16(x)
133#elif SIZEOF_BDIGIT == 4
134# define swap_bdigit(x) swap32(x)
135#elif SIZEOF_BDIGIT == 8
136# define swap_bdigit(x) swap64(x)
139#define BIGZEROP(x) (BIGNUM_LEN(x) == 0 || \
140 (BDIGITS(x)[0] == 0 && \
141 (BIGNUM_LEN(x) == 1 || bigzero_p(x))))
142#define BIGSIZE(x) (BIGNUM_LEN(x) == 0 ? (size_t)0 : \
143 BDIGITS(x)[BIGNUM_LEN(x)-1] ? \
144 (size_t)(BIGNUM_LEN(x)*SIZEOF_BDIGIT - nlz(BDIGITS(x)[BIGNUM_LEN(x)-1])/CHAR_BIT) : \
145 rb_absint_size(x, NULL))
147#define BIGDIVREM_EXTRA_WORDS 1
148#define bdigit_roomof(n) roomof(n, SIZEOF_BDIGIT)
149#define BARY_ARGS(ary) ary, numberof(ary)
151#define BARY_ADD(z, x, y) bary_add(BARY_ARGS(z), BARY_ARGS(x), BARY_ARGS(y))
152#define BARY_SUB(z, x, y) bary_sub(BARY_ARGS(z), BARY_ARGS(x), BARY_ARGS(y))
153#define BARY_SHORT_MUL(z, x, y) bary_short_mul(BARY_ARGS(z), BARY_ARGS(x), BARY_ARGS(y))
154#define BARY_DIVMOD(q, r, x, y) bary_divmod(BARY_ARGS(q), BARY_ARGS(r), BARY_ARGS(x), BARY_ARGS(y))
155#define BARY_ZERO_P(x) bary_zero_p(BARY_ARGS(x))
157#define BIGNUM_SET_NEGATIVE_SIGN(b) BIGNUM_SET_SIGN(b, 0)
158#define BIGNUM_SET_POSITIVE_SIGN(b) BIGNUM_SET_SIGN(b, 1)
160#define bignew(len,sign) bignew_1(rb_cInteger,(len),(sign))
162#define BDIGITS_ZERO(ptr, n) do { \
163 BDIGIT *bdigitz_zero_ptr = (ptr); \
164 size_t bdigitz_zero_n = (n); \
165 while (bdigitz_zero_n) { \
166 *bdigitz_zero_ptr++ = 0; \
171#define BARY_TRUNC(ds, n) do { \
172 while (0 < (n) && (ds)[(n)-1] == 0) \
176#define KARATSUBA_BALANCED(xn, yn) ((yn)/2 < (xn))
177#define TOOM3_BALANCED(xn, yn) (((yn)+2)/3 * 2 < (xn))
179#define GMP_MUL_DIGITS 20
180#define KARATSUBA_MUL_DIGITS 70
181#define TOOM3_MUL_DIGITS 150
183#define GMP_DIV_DIGITS 20
184#define GMP_BIG2STR_DIGITS 20
185#define GMP_STR2BIG_DIGITS 20
187# define NAIVE_MUL_DIGITS GMP_MUL_DIGITS
189# define NAIVE_MUL_DIGITS KARATSUBA_MUL_DIGITS
192typedef 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);
194static mulfunc_t bary_mul_toom3_start;
195static mulfunc_t bary_mul_karatsuba_start;
196static BDIGIT bigdivrem_single(BDIGIT *qds,
const BDIGIT *xds,
size_t xn, BDIGIT y);
202static inline VALUE power_cache_get_power(
int base,
int power_level,
size_t *numdigits_ret);
204#if SIZEOF_BDIGIT <= SIZEOF_INT
205static int nlz(BDIGIT x) {
return nlz_int((
unsigned int)x) - (SIZEOF_INT-SIZEOF_BDIGIT) * CHAR_BIT; }
206#elif SIZEOF_BDIGIT <= SIZEOF_LONG
207static int nlz(BDIGIT x) {
return nlz_long((
unsigned long)x) - (SIZEOF_LONG-SIZEOF_BDIGIT) * CHAR_BIT; }
208#elif SIZEOF_BDIGIT <= SIZEOF_LONG_LONG
209static int nlz(BDIGIT x) {
return nlz_long_long((
unsigned LONG_LONG)x) - (SIZEOF_LONG_LONG-SIZEOF_BDIGIT) * CHAR_BIT; }
210#elif SIZEOF_BDIGIT <= SIZEOF_INT128_T
211static int nlz(BDIGIT x) {
return nlz_int128((uint128_t)x) - (SIZEOF_INT128_T-SIZEOF_BDIGIT) * CHAR_BIT; }
214#define U16(a) ((uint16_t)(a))
215#define U32(a) ((uint32_t)(a))
217#define U64(a,b) (((uint64_t)(a) << 32) | (b))
220#define U128(a,b,c,d) (((uint128_t)U64(a,b) << 64) | U64(c,d))
267#if SIZEOF_BDIGIT_DBL == 2
268static const int maxpow16_exp[35] = {
269 15, 10, 7, 6, 6, 5, 5, 5, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3,
270 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
272static const uint16_t maxpow16_num[35] = {
273 U16(0x00008000), U16(0x0000e6a9), U16(0x00004000), U16(0x00003d09),
274 U16(0x0000b640), U16(0x000041a7), U16(0x00008000), U16(0x0000e6a9),
275 U16(0x00002710), U16(0x00003931), U16(0x00005100), U16(0x00006f91),
276 U16(0x00009610), U16(0x0000c5c1), U16(0x00001000), U16(0x00001331),
277 U16(0x000016c8), U16(0x00001acb), U16(0x00001f40), U16(0x0000242d),
278 U16(0x00002998), U16(0x00002f87), U16(0x00003600), U16(0x00003d09),
279 U16(0x000044a8), U16(0x00004ce3), U16(0x000055c0), U16(0x00005f45),
280 U16(0x00006978), U16(0x0000745f), U16(0x00008000), U16(0x00008c61),
281 U16(0x00009988), U16(0x0000a77b), U16(0x0000b640),
283#elif SIZEOF_BDIGIT_DBL == 4
284static const int maxpow32_exp[35] = {
285 31, 20, 15, 13, 12, 11, 10, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7,
286 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
288static const uint32_t maxpow32_num[35] = {
289 U32(0x80000000), U32(0xcfd41b91), U32(0x40000000), U32(0x48c27395),
290 U32(0x81bf1000), U32(0x75db9c97), U32(0x40000000), U32(0xcfd41b91),
291 U32(0x3b9aca00), U32(0x8c8b6d2b), U32(0x19a10000), U32(0x309f1021),
292 U32(0x57f6c100), U32(0x98c29b81), U32(0x10000000), U32(0x18754571),
293 U32(0x247dbc80), U32(0x3547667b), U32(0x4c4b4000), U32(0x6b5a6e1d),
294 U32(0x94ace180), U32(0xcaf18367), U32(0x0b640000), U32(0x0e8d4a51),
295 U32(0x1269ae40), U32(0x17179149), U32(0x1cb91000), U32(0x23744899),
296 U32(0x2b73a840), U32(0x34e63b41), U32(0x40000000), U32(0x4cfa3cc1),
297 U32(0x5c13d840), U32(0x6d91b519), U32(0x81bf1000),
299#elif SIZEOF_BDIGIT_DBL == 8 && defined HAVE_UINT64_T
300static const int maxpow64_exp[35] = {
301 63, 40, 31, 27, 24, 22, 21, 20, 19, 18, 17, 17, 16, 16, 15, 15, 15,
302 15, 14, 14, 14, 14, 13, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12,
305static const uint64_t maxpow64_num[35] = {
306 U64(0x80000000,0x00000000), U64(0xa8b8b452,0x291fe821),
307 U64(0x40000000,0x00000000), U64(0x6765c793,0xfa10079d),
308 U64(0x41c21cb8,0xe1000000), U64(0x36427987,0x50226111),
309 U64(0x80000000,0x00000000), U64(0xa8b8b452,0x291fe821),
310 U64(0x8ac72304,0x89e80000), U64(0x4d28cb56,0xc33fa539),
311 U64(0x1eca170c,0x00000000), U64(0x780c7372,0x621bd74d),
312 U64(0x1e39a505,0x7d810000), U64(0x5b27ac99,0x3df97701),
313 U64(0x10000000,0x00000000), U64(0x27b95e99,0x7e21d9f1),
314 U64(0x5da0e1e5,0x3c5c8000), U64(0xd2ae3299,0xc1c4aedb),
315 U64(0x16bcc41e,0x90000000), U64(0x2d04b7fd,0xd9c0ef49),
316 U64(0x5658597b,0xcaa24000), U64(0xa0e20737,0x37609371),
317 U64(0x0c29e980,0x00000000), U64(0x14adf4b7,0x320334b9),
318 U64(0x226ed364,0x78bfa000), U64(0x383d9170,0xb85ff80b),
319 U64(0x5a3c23e3,0x9c000000), U64(0x8e651373,0x88122bcd),
320 U64(0xdd41bb36,0xd259e000), U64(0x0aee5720,0xee830681),
321 U64(0x10000000,0x00000000), U64(0x172588ad,0x4f5f0981),
322 U64(0x211e44f7,0xd02c1000), U64(0x2ee56725,0xf06e5c71),
323 U64(0x41c21cb8,0xe1000000),
325#elif SIZEOF_BDIGIT_DBL == 16 && defined HAVE_UINT128_T
326static const int maxpow128_exp[35] = {
327 127, 80, 63, 55, 49, 45, 42, 40, 38, 37, 35, 34, 33, 32, 31, 31, 30,
328 30, 29, 29, 28, 28, 27, 27, 27, 26, 26, 26, 26, 25, 25, 25, 25, 24,
331static const uint128_t maxpow128_num[35] = {
332 U128(0x80000000,0x00000000,0x00000000,0x00000000),
333 U128(0x6f32f1ef,0x8b18a2bc,0x3cea5978,0x9c79d441),
334 U128(0x40000000,0x00000000,0x00000000,0x00000000),
335 U128(0xd0cf4b50,0xcfe20765,0xfff4b4e3,0xf741cf6d),
336 U128(0x6558e2a0,0x921fe069,0x42860000,0x00000000),
337 U128(0x5080c7b7,0xd0e31ba7,0x5911a67d,0xdd3d35e7),
338 U128(0x40000000,0x00000000,0x00000000,0x00000000),
339 U128(0x6f32f1ef,0x8b18a2bc,0x3cea5978,0x9c79d441),
340 U128(0x4b3b4ca8,0x5a86c47a,0x098a2240,0x00000000),
341 U128(0xffd1390a,0x0adc2fb8,0xdabbb817,0x4d95c99b),
342 U128(0x2c6fdb36,0x4c25e6c0,0x00000000,0x00000000),
343 U128(0x384bacd6,0x42c343b4,0xe90c4272,0x13506d29),
344 U128(0x31f5db32,0xa34aced6,0x0bf13a0e,0x00000000),
345 U128(0x20753ada,0xfd1e839f,0x53686d01,0x3143ee01),
346 U128(0x10000000,0x00000000,0x00000000,0x00000000),
347 U128(0x68ca11d6,0xb4f6d1d1,0xfaa82667,0x8073c2f1),
348 U128(0x223e493b,0xb3bb69ff,0xa4b87d6c,0x40000000),
349 U128(0xad62418d,0x14ea8247,0x01c4b488,0x6cc66f59),
350 U128(0x2863c1f5,0xcdae42f9,0x54000000,0x00000000),
351 U128(0xa63fd833,0xb9386b07,0x36039e82,0xbe651b25),
352 U128(0x1d1f7a9c,0xd087a14d,0x28cdf3d5,0x10000000),
353 U128(0x651b5095,0xc2ea8fc1,0xb30e2c57,0x77aaf7e1),
354 U128(0x0ddef20e,0xff760000,0x00000000,0x00000000),
355 U128(0x29c30f10,0x29939b14,0x6664242d,0x97d9f649),
356 U128(0x786a435a,0xe9558b0e,0x6aaf6d63,0xa8000000),
357 U128(0x0c5afe6f,0xf302bcbf,0x94fd9829,0xd87f5079),
358 U128(0x1fce575c,0xe1692706,0x07100000,0x00000000),
359 U128(0x4f34497c,0x8597e144,0x36e91802,0x00528229),
360 U128(0xbf3a8e1d,0x41ef2170,0x7802130d,0x84000000),
361 U128(0x0e7819e1,0x7f1eb0fb,0x6ee4fb89,0x01d9531f),
362 U128(0x20000000,0x00000000,0x00000000,0x00000000),
363 U128(0x4510460d,0xd9e879c0,0x14a82375,0x2f22b321),
364 U128(0x91abce3c,0x4b4117ad,0xe76d35db,0x22000000),
365 U128(0x08973ea3,0x55d75bc2,0x2e42c391,0x727d69e1),
366 U128(0x10e425c5,0x6daffabc,0x35c10000,0x00000000),
371maxpow_in_bdigit_dbl(
int base,
int *exp_ret)
379#if SIZEOF_BDIGIT_DBL == 2
380 maxpow = maxpow16_num[base-2];
381 exponent = maxpow16_exp[base-2];
382#elif SIZEOF_BDIGIT_DBL == 4
383 maxpow = maxpow32_num[base-2];
384 exponent = maxpow32_exp[base-2];
385#elif SIZEOF_BDIGIT_DBL == 8 && defined HAVE_UINT64_T
386 maxpow = maxpow64_num[base-2];
387 exponent = maxpow64_exp[base-2];
388#elif SIZEOF_BDIGIT_DBL == 16 && defined HAVE_UINT128_T
389 maxpow = maxpow128_num[base-2];
390 exponent = maxpow128_exp[base-2];
394 while (maxpow <= BDIGIT_DBL_MAX / base) {
405static inline BDIGIT_DBL
406bary2bdigitdbl(
const BDIGIT *ds,
size_t n)
411 return ds[0] | BIGUP(ds[1]);
418bdigitdbl2bary(BDIGIT *ds,
size_t n, BDIGIT_DBL num)
423 ds[1] = (BDIGIT)BIGDN(num);
427bary_cmp(
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
438 for (i = 0; i < xn; i++)
439 if (xds[xn - i - 1] != yds[yn - i - 1])
443 return xds[xn - i - 1] < yds[yn - i - 1] ? -1 : 1;
447bary_small_lshift(BDIGIT *zds,
const BDIGIT *xds,
size_t n,
int shift)
453 for (i=0; i<n; i++) {
454 num = num | (BDIGIT_DBL)*xds++ << shift;
462bary_small_rshift(BDIGIT *zds,
const BDIGIT *xds,
size_t n,
int shift, BDIGIT higher_bdigit)
469 num = BIGUP(higher_bdigit);
470 for (i = 0; i < n; i++) {
471 BDIGIT x = xds[n - i - 1];
472 num = (num | x) >> shift;
473 zds[n - i - 1] = BIGLO(num);
479bary_zero_p(
const BDIGIT *xds,
size_t xn)
484 if (xds[--xn])
return 0;
490bary_neg(BDIGIT *ds,
size_t n)
493 for (i = 0; i < n; i++)
494 ds[n - i - 1] = BIGLO(~ds[n - i - 1]);
498bary_2comp(BDIGIT *ds,
size_t n)
501 for (i = 0; i < n; i++) {
509 ds[i] = BIGLO(~ds[i] + 1);
512 ds[i] = BIGLO(~ds[i]);
518bary_swap(BDIGIT *ds,
size_t num_bdigits)
521 BDIGIT *p2 = ds + num_bdigits - 1;
522 for (; p1 < p2; p1++, p2--) {
529#define INTEGER_PACK_WORDORDER_MASK \
530 (INTEGER_PACK_MSWORD_FIRST | \
531 INTEGER_PACK_LSWORD_FIRST)
532#define INTEGER_PACK_BYTEORDER_MASK \
533 (INTEGER_PACK_MSBYTE_FIRST | \
534 INTEGER_PACK_LSBYTE_FIRST | \
535 INTEGER_PACK_NATIVE_BYTE_ORDER)
538validate_integer_pack_format(
size_t numwords,
size_t wordsize,
size_t nails,
int flags,
int supported_flags)
540 int wordorder_bits = flags & INTEGER_PACK_WORDORDER_MASK;
541 int byteorder_bits = flags & INTEGER_PACK_BYTEORDER_MASK;
543 if (flags & ~supported_flags) {
544 rb_raise(rb_eArgError,
"unsupported flags specified");
546 if (wordorder_bits == 0) {
548 rb_raise(rb_eArgError,
"word order not specified");
552 rb_raise(rb_eArgError,
"unexpected word order");
553 if (byteorder_bits == 0) {
554 rb_raise(rb_eArgError,
"byte order not specified");
559 rb_raise(rb_eArgError,
"unexpected byte order");
561 rb_raise(rb_eArgError,
"invalid wordsize: %"PRI_SIZE_PREFIX
"u", wordsize);
562 if (SSIZE_MAX < wordsize)
563 rb_raise(rb_eArgError,
"too big wordsize: %"PRI_SIZE_PREFIX
"u", wordsize);
564 if (wordsize <= nails / CHAR_BIT)
565 rb_raise(rb_eArgError,
"too big nails: %"PRI_SIZE_PREFIX
"u", nails);
566 if (SIZE_MAX / wordsize < numwords)
567 rb_raise(rb_eArgError,
"too big numwords * wordsize: %"PRI_SIZE_PREFIX
"u * %"PRI_SIZE_PREFIX
"u", numwords, wordsize);
571integer_pack_loop_setup(
572 size_t numwords,
size_t wordsize,
size_t nails,
int flags,
573 size_t *word_num_fullbytes_ret,
574 int *word_num_partialbits_ret,
575 size_t *word_start_ret,
576 ssize_t *word_step_ret,
577 size_t *word_last_ret,
578 size_t *byte_start_ret,
581 int wordorder_bits = flags & INTEGER_PACK_WORDORDER_MASK;
582 int byteorder_bits = flags & INTEGER_PACK_BYTEORDER_MASK;
583 size_t word_num_fullbytes;
584 int word_num_partialbits;
591 word_num_partialbits = CHAR_BIT - (int)(nails % CHAR_BIT);
592 if (word_num_partialbits == CHAR_BIT)
593 word_num_partialbits = 0;
594 word_num_fullbytes = wordsize - (nails / CHAR_BIT);
595 if (word_num_partialbits != 0) {
596 word_num_fullbytes--;
600 word_start = wordsize*(numwords-1);
601 word_step = -(ssize_t)wordsize;
606 word_step = wordsize;
607 word_last = wordsize*(numwords-1);
611#ifdef WORDS_BIGENDIAN
618 byte_start = wordsize-1;
626 *word_num_partialbits_ret = word_num_partialbits;
627 *word_num_fullbytes_ret = word_num_fullbytes;
628 *word_start_ret = word_start;
629 *word_step_ret = word_step;
630 *word_last_ret = word_last;
631 *byte_start_ret = byte_start;
632 *byte_step_ret = byte_step;
636integer_pack_fill_dd(BDIGIT **dpp, BDIGIT **dep, BDIGIT_DBL *ddp,
int *numbits_in_dd_p)
638 if (*dpp < *dep && BITSPERDIG <= (
int)
sizeof(*ddp) * CHAR_BIT - *numbits_in_dd_p) {
639 *ddp |= (BDIGIT_DBL)(*(*dpp)++) << *numbits_in_dd_p;
640 *numbits_in_dd_p += BITSPERDIG;
642 else if (*dpp == *dep) {
644 *numbits_in_dd_p = (int)
sizeof(*ddp) * CHAR_BIT;
648static inline BDIGIT_DBL
649integer_pack_take_lowbits(
int n, BDIGIT_DBL *ddp,
int *numbits_in_dd_p)
652 ret = (*ddp) & (((BDIGIT_DBL)1 << n) - 1);
654 *numbits_in_dd_p -= n;
658#if !defined(WORDS_BIGENDIAN)
660bytes_2comp(
unsigned char *buf,
size_t len)
663 for (i = 0; i <
len; i++) {
664 signed char c = buf[i];
666 unsigned int e = d & 0xFF;
669 for (i = 0; i <
len; i++) {
679bary_pack(
int sign, BDIGIT *ds,
size_t num_bdigits,
void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
682 unsigned char *buf, *bufend;
685 de = ds + num_bdigits;
687 validate_integer_pack_format(numwords, wordsize, nails, flags,
696 while (dp < de && de[-1] == 0)
704 MEMZERO(words,
unsigned char, numwords * wordsize);
707 if (nails == 0 && numwords == 1) {
708 int need_swap = wordsize != 1 &&
714 *((
unsigned char *)words) = (
unsigned char)(d = dp[0]);
715 return ((1 < de - dp || CLEAR_LOWBITS(d, 8) != 0) ? 2 : 1) * sign;
717#if defined(HAVE_UINT16_T) && 2 <= SIZEOF_BDIGIT
718 if (wordsize == 2 && (uintptr_t)words %
RUBY_ALIGNOF(uint16_t) == 0) {
719 uint16_t u = (uint16_t)(d = dp[0]);
720 if (need_swap) u = swap16(u);
721 *((uint16_t *)words) = u;
722 return ((1 < de - dp || CLEAR_LOWBITS(d, 16) != 0) ? 2 : 1) * sign;
725#if defined(HAVE_UINT32_T) && 4 <= SIZEOF_BDIGIT
726 if (wordsize == 4 && (uintptr_t)words %
RUBY_ALIGNOF(uint32_t) == 0) {
727 uint32_t u = (uint32_t)(d = dp[0]);
728 if (need_swap) u = swap32(u);
729 *((uint32_t *)words) = u;
730 return ((1 < de - dp || CLEAR_LOWBITS(d, 32) != 0) ? 2 : 1) * sign;
733#if defined(HAVE_UINT64_T) && 8 <= SIZEOF_BDIGIT
734 if (wordsize == 8 && (uintptr_t)words %
RUBY_ALIGNOF(uint64_t) == 0) {
735 uint64_t u = (uint64_t)(d = dp[0]);
736 if (need_swap) u = swap64(u);
737 *((uint64_t *)words) = u;
738 return ((1 < de - dp || CLEAR_LOWBITS(d, 64) != 0) ? 2 : 1) * sign;
745 *((
unsigned char *)words) = (
unsigned char)(d = -(BDIGIT_DBL_SIGNED)dp[0]);
746 return (1 < de - dp || FILL_LOWBITS(d, 8) != -1) ? -2 : -1;
748#if defined(HAVE_UINT16_T) && 2 <= SIZEOF_BDIGIT
749 if (wordsize == 2 && (uintptr_t)words %
RUBY_ALIGNOF(uint16_t) == 0) {
750 uint16_t u = (uint16_t)(d = -(BDIGIT_DBL_SIGNED)dp[0]);
751 if (need_swap) u = swap16(u);
752 *((uint16_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, 16) != -1) ? -2 : -1;
757#if defined(HAVE_UINT32_T) && 4 <= SIZEOF_BDIGIT
758 if (wordsize == 4 && (uintptr_t)words %
RUBY_ALIGNOF(uint32_t) == 0) {
759 uint32_t u = (uint32_t)(d = -(BDIGIT_DBL_SIGNED)dp[0]);
760 if (need_swap) u = swap32(u);
761 *((uint32_t *)words) = u;
762 return (wordsize == SIZEOF_BDIGIT && de - dp == 2 && dp[1] == 1 && dp[0] == 0) ? -1 :
763 (1 < de - dp || FILL_LOWBITS(d, 32) != -1) ? -2 : -1;
766#if defined(HAVE_UINT64_T) && 8 <= SIZEOF_BDIGIT
767 if (wordsize == 8 && (uintptr_t)words %
RUBY_ALIGNOF(uint64_t) == 0) {
768 uint64_t u = (uint64_t)(d = -(BDIGIT_DBL_SIGNED)dp[0]);
769 if (need_swap) u = swap64(u);
770 *((uint64_t *)words) = u;
771 return (wordsize == SIZEOF_BDIGIT && de - dp == 2 && dp[1] == 1 && dp[0] == 0) ? -1 :
772 (1 < de - dp || FILL_LOWBITS(d, 64) != -1) ? -2 : -1;
777#if !defined(WORDS_BIGENDIAN)
778 if (nails == 0 && SIZEOF_BDIGIT ==
sizeof(BDIGIT) &&
781 size_t src_size = (de - dp) * SIZEOF_BDIGIT;
782 size_t dst_size = numwords * wordsize;
784 while (0 < src_size && ((
unsigned char *)ds)[src_size-1] == 0)
786 if (src_size <= dst_size) {
787 MEMCPY(words, dp,
char, src_size);
788 MEMZERO((
char*)words + src_size,
char, dst_size - src_size);
791 MEMCPY(words, dp,
char, dst_size);
795 int zero_p = bytes_2comp(words, dst_size);
796 if (zero_p && overflow) {
797 unsigned char *p = (
unsigned char *)dp;
798 if (dst_size == src_size-1 &&
809 if (nails == 0 && SIZEOF_BDIGIT ==
sizeof(BDIGIT) &&
810 wordsize % SIZEOF_BDIGIT == 0 && (uintptr_t)words %
RUBY_ALIGNOF(BDIGIT) == 0) {
811 size_t bdigits_per_word = wordsize / SIZEOF_BDIGIT;
812 size_t src_num_bdigits = de - dp;
813 size_t dst_num_bdigits = numwords * bdigits_per_word;
818 if (src_num_bdigits <= dst_num_bdigits) {
819 MEMCPY(words, dp, BDIGIT, src_num_bdigits);
820 BDIGITS_ZERO((BDIGIT*)words + src_num_bdigits, dst_num_bdigits - src_num_bdigits);
823 MEMCPY(words, dp, BDIGIT, dst_num_bdigits);
827 int zero_p = bary_2comp(words, dst_num_bdigits);
828 if (zero_p && overflow &&
829 dst_num_bdigits == src_num_bdigits-1 &&
830 dp[dst_num_bdigits] == 1)
833 if (msbytefirst_p != HOST_BIGENDIAN_P) {
835 for (i = 0; i < dst_num_bdigits; i++) {
836 BDIGIT d = ((BDIGIT*)words)[i];
837 ((BDIGIT*)words)[i] = swap_bdigit(d);
840 if (mswordfirst_p ? !msbytefirst_p : msbytefirst_p) {
843 for (i = 0; i < numwords; i++) {
844 bary_swap(p, bdigits_per_word);
845 p += bdigits_per_word;
849 bary_swap(words, dst_num_bdigits);
858 bufend = buf + numwords * wordsize;
865 if (de - dp == 1 && dp[0] == 1)
872 memset(buf,
'\0', bufend - buf);
874 else if (dp < de && buf < bufend) {
875 int word_num_partialbits;
876 size_t word_num_fullbytes;
882 size_t word_start, word_last;
883 unsigned char *wordp, *last_wordp;
887 integer_pack_loop_setup(numwords, wordsize, nails, flags,
888 &word_num_fullbytes, &word_num_partialbits,
889 &word_start, &word_step, &word_last, &byte_start, &byte_step);
891 wordp = buf + word_start;
892 last_wordp = buf + word_last;
898 integer_pack_fill_dd(&dp, &de, &dd, &numbits_in_dd)
899#define TAKE_LOWBITS(n) \
900 integer_pack_take_lowbits(n, &dd, &numbits_in_dd)
903 size_t index_in_word = 0;
904 unsigned char *bytep = wordp + byte_start;
905 while (index_in_word < word_num_fullbytes) {
907 *bytep = TAKE_LOWBITS(CHAR_BIT);
911 if (word_num_partialbits) {
913 *bytep = TAKE_LOWBITS(word_num_partialbits);
917 while (index_in_word < wordsize) {
923 if (wordp == last_wordp)
930 if (dp != de || 1 < dd) {
941 while (dp < de && *dp == 0)
953 int word_num_partialbits;
954 size_t word_num_fullbytes;
960 size_t word_start, word_last;
961 unsigned char *wordp, *last_wordp;
963 unsigned int partialbits_mask;
966 integer_pack_loop_setup(numwords, wordsize, nails, flags,
967 &word_num_fullbytes, &word_num_partialbits,
968 &word_start, &word_step, &word_last, &byte_start, &byte_step);
970 partialbits_mask = (1 << word_num_partialbits) - 1;
973 wordp = buf + word_start;
974 last_wordp = buf + word_last;
978 size_t index_in_word = 0;
979 unsigned char *bytep = wordp + byte_start;
980 while (index_in_word < word_num_fullbytes) {
981 carry += (
unsigned char)~*bytep;
982 *bytep = (
unsigned char)carry;
987 if (word_num_partialbits) {
988 carry += (*bytep & partialbits_mask) ^ partialbits_mask;
989 *bytep = carry & partialbits_mask;
990 carry >>= word_num_partialbits;
995 if (wordp == last_wordp)
1008integer_unpack_num_bdigits_small(
size_t numwords,
size_t wordsize,
size_t nails,
int *nlp_bits_ret)
1011 size_t num_bits = (wordsize * CHAR_BIT - nails) * numwords;
1012 size_t num_bdigits = roomof(num_bits, BITSPERDIG);
1013 *nlp_bits_ret = (int)(num_bdigits * BITSPERDIG - num_bits);
1018integer_unpack_num_bdigits_generic(
size_t numwords,
size_t wordsize,
size_t nails,
int *nlp_bits_ret)
1025 size_t num_bytes1 = wordsize * numwords;
1028 size_t q1 = numwords / CHAR_BIT;
1029 size_t r1 = numwords % CHAR_BIT;
1032 size_t num_bytes2 = num_bytes1 - nails * q1;
1035 size_t q2 = nails / CHAR_BIT;
1036 size_t r2 = nails % CHAR_BIT;
1039 size_t num_bytes3 = num_bytes2 - q2 * r1;
1042 size_t q3 = num_bytes3 / BITSPERDIG;
1043 size_t r3 = num_bytes3 % BITSPERDIG;
1046 size_t num_digits1 = CHAR_BIT * q3;
1059 if (CHAR_BIT * r3 >= r1 * r2) {
1060 size_t tmp1 = CHAR_BIT * BITSPERDIG - (CHAR_BIT * r3 - r1 * r2);
1061 size_t q4 = tmp1 / BITSPERDIG;
1062 int r4 = (int)(tmp1 % BITSPERDIG);
1063 size_t num_digits2 = num_digits1 + CHAR_BIT - q4;
1068 size_t tmp1 = r1 * r2 - CHAR_BIT * r3;
1069 size_t q4 = tmp1 / BITSPERDIG;
1070 int r4 = (int)(tmp1 % BITSPERDIG);
1071 size_t num_digits2 = num_digits1 - q4;
1078integer_unpack_num_bdigits(
size_t numwords,
size_t wordsize,
size_t nails,
int *nlp_bits_ret)
1082 if (numwords <= (SIZE_MAX - (BITSPERDIG-1)) / CHAR_BIT / wordsize) {
1083 num_bdigits = integer_unpack_num_bdigits_small(numwords, wordsize, nails, nlp_bits_ret);
1084 if (debug_integer_pack) {
1086 size_t num_bdigits1 = integer_unpack_num_bdigits_generic(numwords, wordsize, nails, &nlp_bits1);
1093 num_bdigits = integer_unpack_num_bdigits_generic(numwords, wordsize, nails, nlp_bits_ret);
1099integer_unpack_push_bits(
int data,
int numbits, BDIGIT_DBL *ddp,
int *numbits_in_dd_p, BDIGIT **dpp)
1101 (*ddp) |= ((BDIGIT_DBL)data) << (*numbits_in_dd_p);
1102 *numbits_in_dd_p += numbits;
1103 while (BITSPERDIG <= *numbits_in_dd_p) {
1104 *(*dpp)++ = BIGLO(*ddp);
1106 *numbits_in_dd_p -= BITSPERDIG;
1111integer_unpack_single_bdigit(BDIGIT u,
size_t size,
int flags, BDIGIT *dp)
1116 ((size == SIZEOF_BDIGIT && u == 0) ? -2 : -1) :
1117 ((u >> (size * CHAR_BIT - 1)) ? -1 : 1);
1119 u |= LSHIFTX(BDIGMAX, size * CHAR_BIT);
1129#ifdef HAVE_BUILTIN___BUILTIN_ASSUME_ALIGNED
1130#define reinterpret_cast(type, value) (type) \
1131 __builtin_assume_aligned((value), sizeof(*(type)NULL));
1133#define reinterpret_cast(type, value) (type)value
1137bary_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)
1140 const unsigned char *buf = words;
1145 de = dp + num_bdigits;
1148 if (nails == 0 && numwords == 1) {
1149 int need_swap = wordsize != 1 &&
1152 if (wordsize == 1) {
1153 return integer_unpack_single_bdigit(*(uint8_t *)buf,
sizeof(uint8_t), flags, dp);
1155#if defined(HAVE_UINT16_T) && 2 <= SIZEOF_BDIGIT
1156 if (wordsize == 2 && (uintptr_t)words %
RUBY_ALIGNOF(uint16_t) == 0) {
1157 uint16_t u = *reinterpret_cast(
const uint16_t *, buf);
1158 return integer_unpack_single_bdigit(need_swap ? swap16(u) : u,
sizeof(uint16_t), flags, dp);
1161#if defined(HAVE_UINT32_T) && 4 <= SIZEOF_BDIGIT
1162 if (wordsize == 4 && (uintptr_t)words %
RUBY_ALIGNOF(uint32_t) == 0) {
1163 uint32_t u = *reinterpret_cast(
const uint32_t *, buf);
1164 return integer_unpack_single_bdigit(need_swap ? swap32(u) : u,
sizeof(uint32_t), flags, dp);
1167#if defined(HAVE_UINT64_T) && 8 <= SIZEOF_BDIGIT
1168 if (wordsize == 8 && (uintptr_t)words %
RUBY_ALIGNOF(uint64_t) == 0) {
1169 uint64_t u = *reinterpret_cast(
const uint64_t *, buf);
1170 return integer_unpack_single_bdigit(need_swap ? swap64(u) : u,
sizeof(uint64_t), flags, dp);
1173#undef reinterpret_cast
1175#if !defined(WORDS_BIGENDIAN)
1176 if (nails == 0 && SIZEOF_BDIGIT ==
sizeof(BDIGIT) &&
1179 size_t src_size = numwords * wordsize;
1180 size_t dst_size = num_bdigits * SIZEOF_BDIGIT;
1181 MEMCPY(dp, words,
char, src_size);
1185 memset((
char*)dp + src_size, 0xff, dst_size - src_size);
1186 zero_p = bary_2comp(dp, num_bdigits);
1187 sign = zero_p ? -2 : -1;
1189 else if (buf[src_size-1] >> (CHAR_BIT-1)) {
1190 memset((
char*)dp + src_size, 0xff, dst_size - src_size);
1191 bary_2comp(dp, num_bdigits);
1195 MEMZERO((
char*)dp + src_size,
char, dst_size - src_size);
1200 MEMZERO((
char*)dp + src_size,
char, dst_size - src_size);
1206 if (nails == 0 && SIZEOF_BDIGIT ==
sizeof(BDIGIT) &&
1207 wordsize % SIZEOF_BDIGIT == 0) {
1208 size_t bdigits_per_word = wordsize / SIZEOF_BDIGIT;
1212 MEMCPY(dp, words, BDIGIT, numwords*bdigits_per_word);
1213 if (mswordfirst_p) {
1214 bary_swap(dp, num_bdigits);
1216 if (mswordfirst_p ? !msbytefirst_p : msbytefirst_p) {
1219 for (i = 0; i < numwords; i++) {
1220 bary_swap(p, bdigits_per_word);
1221 p += bdigits_per_word;
1224 if (msbytefirst_p != HOST_BIGENDIAN_P) {
1226 for (p = dp; p < de; p++) {
1228 *p = swap_bdigit(d);
1233 int zero_p = bary_2comp(dp, num_bdigits);
1234 sign = zero_p ? -2 : -1;
1236 else if (BDIGIT_MSB(de[-1])) {
1237 bary_2comp(dp, num_bdigits);
1251 if (num_bdigits != 0) {
1252 int word_num_partialbits;
1253 size_t word_num_fullbytes;
1259 size_t word_start, word_last;
1260 const unsigned char *wordp, *last_wordp;
1264 integer_pack_loop_setup(numwords, wordsize, nails, flags,
1265 &word_num_fullbytes, &word_num_partialbits,
1266 &word_start, &word_step, &word_last, &byte_start, &byte_step);
1268 wordp = buf + word_start;
1269 last_wordp = buf + word_last;
1274#define PUSH_BITS(data, numbits) \
1275 integer_unpack_push_bits(data, numbits, &dd, &numbits_in_dd, &dp)
1278 size_t index_in_word = 0;
1279 const unsigned char *bytep = wordp + byte_start;
1280 while (index_in_word < word_num_fullbytes) {
1281 PUSH_BITS(*bytep, CHAR_BIT);
1285 if (word_num_partialbits) {
1286 PUSH_BITS(*bytep & ((1 << word_num_partialbits) - 1), word_num_partialbits);
1291 if (wordp == last_wordp)
1310 (bdigits[num_bdigits-1] >> (BITSPERDIG - nlp_bits - 1))) {
1311 bdigits[num_bdigits-1] |= BIGLO(BDIGMAX << (BITSPERDIG - nlp_bits));
1320 sign = bary_zero_p(bdigits, num_bdigits) ? -2 : -1;
1323 if (num_bdigits != 0 && BDIGIT_MSB(bdigits[num_bdigits-1]))
1329 if (sign == -1 && num_bdigits != 0) {
1330 bary_2comp(bdigits, num_bdigits);
1338bary_unpack(BDIGIT *bdigits,
size_t num_bdigits,
const void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
1340 size_t num_bdigits0;
1344 validate_integer_pack_format(numwords, wordsize, nails, flags,
1355 num_bdigits0 = integer_unpack_num_bdigits(numwords, wordsize, nails, &nlp_bits);
1359 sign = bary_unpack_internal(bdigits, num_bdigits0, words, numwords, wordsize, nails, flags, nlp_bits);
1361 if (num_bdigits0 < num_bdigits) {
1362 BDIGITS_ZERO(bdigits + num_bdigits0, num_bdigits - num_bdigits0);
1364 bdigits[num_bdigits0] = 1;
1370bary_subb(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn,
int borrow)
1372 BDIGIT_DBL_SIGNED num;
1379 sn = xn < yn ? xn : yn;
1381 num = borrow ? -1 : 0;
1382 for (i = 0; i < sn; i++) {
1383 num += (BDIGIT_DBL_SIGNED)xds[i] - yds[i];
1384 zds[i] = BIGLO(num);
1388 for (; i < xn; i++) {
1389 if (num == 0)
goto num_is_zero;
1391 zds[i] = BIGLO(num);
1396 for (; i < yn; i++) {
1398 zds[i] = BIGLO(num);
1402 if (num == 0)
goto num_is_zero;
1403 for (; i < zn; i++) {
1409 if (xds == zds && xn == zn)
1411 for (; i < xn; i++) {
1414 for (; i < zn; i++) {
1421bary_sub(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
1423 return bary_subb(zds, zn, xds, xn, yds, yn, 0);
1427bary_sub_one(BDIGIT *zds,
size_t zn)
1429 return bary_subb(zds, zn, zds, zn, NULL, 0, 1);
1433bary_addc(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn,
int carry)
1443 tds = xds; xds = yds; yds = tds;
1444 i = xn; xn = yn; yn = i;
1447 num = carry ? 1 : 0;
1448 for (i = 0; i < xn; i++) {
1449 num += (BDIGIT_DBL)xds[i] + yds[i];
1450 zds[i] = BIGLO(num);
1453 for (; i < yn; i++) {
1454 if (num == 0)
goto num_is_zero;
1456 zds[i] = BIGLO(num);
1459 for (; i < zn; i++) {
1460 if (num == 0)
goto num_is_zero;
1461 zds[i] = BIGLO(num);
1467 if (yds == zds && yn == zn)
1469 for (; i < yn; i++) {
1472 for (; i < zn; i++) {
1479bary_add(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
1481 return bary_addc(zds, zn, xds, xn, yds, yn, 0);
1485bary_add_one(BDIGIT *ds,
size_t n)
1488 for (i = 0; i < n; i++) {
1489 BDIGIT_DBL n = ds[i];
1499bary_mul_single(BDIGIT *zds,
size_t zn, BDIGIT x, BDIGIT y)
1505 n = (BDIGIT_DBL)x * y;
1506 bdigitdbl2bary(zds, 2, n);
1507 BDIGITS_ZERO(zds + 2, zn - 2);
1511bary_muladd_1xN(BDIGIT *zds,
size_t zn, BDIGIT x,
const BDIGIT *yds,
size_t yn)
1523 for (j = 0; j < yn; j++) {
1524 BDIGIT_DBL ee = n + dd * yds[j];
1535 for (; j < zn; j++) {
1545static BDIGIT_DBL_SIGNED
1546bigdivrem_mulsub(BDIGIT *zds,
size_t zn, BDIGIT x,
const BDIGIT *yds,
size_t yn)
1550 BDIGIT_DBL_SIGNED num;
1559 BDIGIT_DBL_SIGNED ee;
1560 t2 += (BDIGIT_DBL)yds[i] * x;
1561 ee = num - BIGLO(t2);
1562 num = (BDIGIT_DBL_SIGNED)zds[i] + ee;
1563 if (ee) zds[i] = BIGLO(num);
1567 num -= (BDIGIT_DBL_SIGNED)t2;
1568 num += (BDIGIT_DBL_SIGNED)zds[yn];
1573bary_mulsub_1xN(BDIGIT *zds,
size_t zn, BDIGIT x,
const BDIGIT *yds,
size_t yn)
1575 BDIGIT_DBL_SIGNED num;
1579 num = bigdivrem_mulsub(zds, zn, x, yds, yn);
1580 zds[yn] = BIGLO(num);
1587bary_mul_normal(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
1593 BDIGITS_ZERO(zds, zn);
1594 for (i = 0; i < xn; i++) {
1595 bary_muladd_1xN(zds+i, zn-i, xds[i], yds, yn);
1602 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), zn = xn + yn;
1603 VALUE z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
1604 bary_mul_normal(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn);
1615bary_sq_fast(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn)
1624 BDIGITS_ZERO(zds, zn);
1629 for (i = 0; i < xn-1; i++) {
1630 v = (BDIGIT_DBL)xds[i];
1633 c = (BDIGIT_DBL)zds[i + i] + v * v;
1634 zds[i + i] = BIGLO(c);
1639 for (j = i + 1; j < xn; j++) {
1640 w = (BDIGIT_DBL)xds[j];
1641 c += (BDIGIT_DBL)zds[i + j] + vl * w;
1642 zds[i + j] = BIGLO(c);
1648 c += (BDIGIT_DBL)zds[i + xn];
1649 zds[i + xn] = BIGLO(c);
1652 zds[i + xn + 1] += (BDIGIT)c;
1657 v = (BDIGIT_DBL)xds[i];
1660 c = (BDIGIT_DBL)zds[i + i] + v * v;
1661 zds[i + i] = BIGLO(c);
1664 zds[i + xn] += BIGLO(c);
1669rb_big_sq_fast(
VALUE x)
1671 size_t xn = BIGNUM_LEN(x), zn = 2 * xn;
1672 VALUE z = bignew(zn, 1);
1673 bary_sq_fast(BDIGITS(z), zn, BDIGITS(x), xn);
1679max_size(
size_t a,
size_t b)
1681 return (a > b ? a : b);
1686bary_mul_balance_with_mulfunc(BDIGIT *
const zds,
const size_t zn,
1687 const BDIGIT *
const xds,
const size_t xn,
1688 const BDIGIT *
const yds,
const size_t yn,
1689 BDIGIT *wds,
size_t wn, mulfunc_t *
const mulfunc)
1696 RUBY_ASSERT(!KARATSUBA_BALANCED(xn, yn) || !TOOM3_BALANCED(xn, yn));
1698 BDIGITS_ZERO(zds, xn);
1707 const size_t r = yn % xn;
1708 if (2*xn + yn + max_size(xn-r, r) > zn) {
1716 const size_t r = (xn > (yn - n) ? (yn - n) : xn);
1717 const size_t tn = (xn + r);
1718 if (2 * (xn + r) <= zn - n) {
1719 BDIGIT *
const tds = zds + n + xn + r;
1720 mulfunc(tds, tn, xds, xn, yds + n, r, wds, wn);
1721 BDIGITS_ZERO(zds + n + xn, r);
1722 bary_add(zds + n, tn,
1727 BDIGIT *
const tds = zds + n;
1734 rb_bug(
"wds is not enough: %" PRIdSIZE
" for %" PRIdSIZE, wn, xn);
1737 MEMCPY(wds, zds + n, BDIGIT, xn);
1738 mulfunc(tds, tn, xds, xn, yds + n, r, wds+xn, wn-xn);
1739 bary_add(zds + n, tn,
1745 BDIGITS_ZERO(zds+xn+yn, zn - (xn+yn));
1754 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), zn = xn + yn;
1755 VALUE z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
1756 bary_mul_balance_with_mulfunc(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, NULL, 0, bary_mul_toom3_start);
1764bary_mul_karatsuba(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn, BDIGIT *wds,
size_t wn)
1769 int sub_p, borrow, carry1, carry2, carry3;
1775 const BDIGIT *xds0, *xds1, *yds0, *yds1;
1776 BDIGIT *zds0, *zds1, *zds2, *zds3;
1782 sq = xds == yds && xn == yn;
1832 if (bary_sub(zds0, n, xds, n, xds+n, xn-n)) {
1833 bary_2comp(zds0, n);
1841 bary_mul_karatsuba_start(zds1, 2*n, zds0, n, zds0, n, wds, wn);
1844 if (bary_sub(wds, n, yds, n, yds+n, n)) {
1851 bary_mul_karatsuba_start(zds1, 2*n, zds0, n, wds, n, wds+n, wn-n);
1858 borrow = !bary_2comp(zds1, 2*n);
1862 MEMCPY(wds, zds1, BDIGIT, n);
1866 bary_mul_karatsuba_start(zds0, 2*n, xds0, n, yds0, n, wds+n, wn-n);
1870 carry1 = bary_add(wds, n, wds, n, zds0, n);
1871 carry1 = bary_addc(zds2, n, zds2, n, zds1, n, carry1);
1875 carry2 = bary_add(zds1, n, zds1, n, wds, n);
1879 MEMCPY(wds, zds2, BDIGIT, n);
1883 bary_mul_karatsuba_start(zds2, zn-2*n, xds1, xn-n, yds1, n, wds+n, wn-n);
1887 carry3 = bary_add(zds1, n, zds1, n, zds2, n);
1891 carry3 = bary_addc(zds2, n, zds2, n, zds3, (4*n < zn ? n : zn-3*n), carry3);
1895 bary_add(zds2, zn-2*n, zds2, zn-2*n, wds, n);
1900 bary_add_one(zds2, zn-2*n);
1902 if (carry1 + carry3 - borrow < 0)
1903 bary_sub_one(zds3, zn-3*n);
1904 else if (carry1 + carry3 - borrow > 0) {
1905 BDIGIT c = carry1 + carry3 - borrow;
1906 bary_add(zds3, zn-3*n, zds3, zn-3*n, &c, 1);
1921 bary_muladd_1xN(zds+yn, zn-yn, yds[yn], xds, xn);
1922 bary_muladd_1xN(zds+xn, zn-xn, xds[xn], yds, yn+1);
1925 bary_muladd_1xN(zds+yn, zn-yn, yds[yn], xds, xn);
1935 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), zn = xn + yn;
1936 VALUE z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
1937 if (!((xn <= yn && yn < 2) || KARATSUBA_BALANCED(xn, yn)))
1938 rb_raise(rb_eArgError,
"unexpected bignum length for karatsuba");
1939 bary_mul_karatsuba(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, NULL, 0);
1946bary_mul_toom3(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn, BDIGIT *wds,
size_t wn)
1953 size_t x0n;
const BDIGIT *x0ds;
1954 size_t x1n;
const BDIGIT *x1ds;
1955 size_t x2n;
const BDIGIT *x2ds;
1956 size_t y0n;
const BDIGIT *y0ds;
1957 size_t y1n;
const BDIGIT *y1ds;
1958 size_t y2n;
const BDIGIT *y2ds;
1960 size_t u1n; BDIGIT *u1ds;
int u1p;
1961 size_t u2n; BDIGIT *u2ds;
int u2p;
1962 size_t u3n; BDIGIT *u3ds;
int u3p;
1964 size_t v1n; BDIGIT *v1ds;
int v1p;
1965 size_t v2n; BDIGIT *v2ds;
int v2p;
1966 size_t v3n; BDIGIT *v3ds;
int v3p;
1968 size_t t0n; BDIGIT *t0ds;
int t0p;
1969 size_t t1n; BDIGIT *t1ds;
int t1p;
1970 size_t t2n; BDIGIT *t2ds;
int t2p;
1971 size_t t3n; BDIGIT *t3ds;
int t3p;
1972 size_t t4n; BDIGIT *t4ds;
int t4p;
1974 size_t z0n; BDIGIT *z0ds;
1975 size_t z1n; BDIGIT *z1ds;
int z1p;
1976 size_t z2n; BDIGIT *z2ds;
int z2p;
1977 size_t z3n; BDIGIT *z3ds;
int z3p;
1978 size_t z4n; BDIGIT *z4ds;
1980 size_t zzn; BDIGIT *zzds;
1982 int sq = xds == yds && xn == yn;
2000 wnc += (t1n = 2*n+2);
2001 wnc += (t2n = 2*n+2);
2002 wnc += (t3n = 2*n+2);
2005 wnc += (z1n = 2*n+1);
2006 wnc += (z2n = 2*n+1);
2007 wnc += (z3n = 2*n+1);
2014 u1ds = wds; wds += u1n;
2015 u2ds = wds; wds += u2n;
2016 u3ds = wds; wds += u3n;
2018 v1ds = wds; wds += v1n;
2019 v2ds = wds; wds += v2n;
2020 v3ds = wds; wds += v3n;
2022 t0ds = wds; wds += t0n;
2023 t1ds = wds; wds += t1n;
2024 t2ds = wds; wds += t2n;
2025 t3ds = wds; wds += t3n;
2026 t4ds = wds; wds += t4n;
2028 z1ds = wds; wds += z1n;
2029 z2ds = wds; wds += z2n;
2030 z3ds = wds; wds += z3n;
2096 bary_add(u1ds, u1n, x0ds, x0n, x2ds, x2n);
2100 if (bary_sub(u2ds, u2n, u1ds, u1n, x1ds, x1n)) {
2101 bary_2comp(u2ds, u2n);
2109 bary_add(u1ds, u1n, u1ds, u1n, x1ds, x1n);
2114 bary_add(u3ds, u3n, u2ds, u2n, x2ds, x2n);
2116 else if (bary_sub(u3ds, u3n, x2ds, x2n, u2ds, u2n)) {
2117 bary_2comp(u3ds, u3n);
2120 bary_small_lshift(u3ds, u3ds, u3n, 1);
2122 bary_add(u3ds, u3n, u3ds, u3n, x0ds, x0n);
2124 else if (bary_sub(u3ds, u3n, u3ds, u3n, x0ds, x0n)) {
2125 bary_2comp(u3ds, u3n);
2130 v1n = u1n; v1ds = u1ds; v1p = u1p;
2131 v2n = u2n; v2ds = u2ds; v2p = u2p;
2132 v3n = u3n; v3ds = u3ds; v3p = u3p;
2136 bary_add(v1ds, v1n, y0ds, y0n, y2ds, y2n);
2141 if (bary_sub(v2ds, v2n, v1ds, v1n, y1ds, y1n)) {
2142 bary_2comp(v2ds, v2n);
2147 bary_add(v1ds, v1n, v1ds, v1n, y1ds, y1n);
2152 bary_add(v3ds, v3n, v2ds, v2n, y2ds, y2n);
2154 else if (bary_sub(v3ds, v3n, y2ds, y2n, v2ds, v2n)) {
2155 bary_2comp(v3ds, v3n);
2158 bary_small_lshift(v3ds, v3ds, v3n, 1);
2160 bary_add(v3ds, v3n, v3ds, v3n, y0ds, y0n);
2162 else if (bary_sub(v3ds, v3n, v3ds, v3n, y0ds, y0n)) {
2163 bary_2comp(v3ds, v3n);
2169 bary_mul_toom3_start(t0ds, t0n, x0ds, x0n, y0ds, y0n, wds, wn);
2173 bary_mul_toom3_start(t1ds, t1n, u1ds, u1n, v1ds, v1n, wds, wn);
2179 bary_mul_toom3_start(t2ds, t2n, u2ds, u2n, v2ds, v2n, wds, wn);
2185 bary_mul_toom3_start(t3ds, t3n, u3ds, u3n, v3ds, v3n, wds, wn);
2191 bary_mul_toom3_start(t4ds, t4n, x2ds, x2n, y2ds, y2n, wds, wn);
2199 z0n = t0n; z0ds = t0ds;
2202 z4n = t4n; z4ds = t4ds;
2207 if (bary_sub(z3ds, z3n, t3ds, t3n, t1ds, t1n)) {
2208 bary_2comp(z3ds, z3n);
2214 bary_add(z3ds, z3n, t3ds, t3n, t1ds, t1n);
2216 bigdivrem_single(z3ds, z3ds, z3n, 3);
2221 if (bary_sub(z1ds, z1n, t1ds, t1n, t2ds, t2n)) {
2222 bary_2comp(z1ds, z1n);
2228 bary_add(z1ds, z1n, t1ds, t1n, t2ds, t2n);
2230 bary_small_rshift(z1ds, z1ds, z1n, 1, 0);
2235 if (bary_sub(z2ds, z2n, t2ds, t2n, t0ds, t0n)) {
2236 bary_2comp(z2ds, z2n);
2242 bary_add(z2ds, z2n, t2ds, t2n, t0ds, t0n);
2248 if (bary_sub(z3ds, z3n, z2ds, z2n, z3ds, z3n)) {
2249 bary_2comp(z3ds, z3n);
2255 bary_add(z3ds, z3n, z2ds, z2n, z3ds, z3n);
2257 bary_small_rshift(z3ds, z3ds, z3n, 1, 0);
2259 bary_muladd_1xN(z3ds, z3n, 2, t4ds, t4n);
2262 if (bary_mulsub_1xN(z3ds, z3n, 2, t4ds, t4n)) {
2263 bary_2comp(z3ds, z3n);
2270 bary_add(z2ds, z2n, z2ds, z2n, z1ds, z1n);
2273 if (bary_sub(z2ds, z2n, z2ds, z2n, z1ds, z1n)) {
2274 bary_2comp(z2ds, z2n);
2280 if (bary_sub(z2ds, z2n, z2ds, z2n, t4ds, t4n)) {
2281 bary_2comp(z2ds, z2n);
2286 bary_add(z2ds, z2n, z2ds, z2n, t4ds, t4n);
2291 if (bary_sub(z1ds, z1n, z1ds, z1n, z3ds, z3n)) {
2292 bary_2comp(z1ds, z1n);
2297 bary_add(z1ds, z1n, z1ds, z1n, z3ds, z3n);
2304 MEMCPY(zzds, z0ds, BDIGIT, z0n);
2305 BDIGITS_ZERO(zzds + z0n, 4*n - z0n);
2306 MEMCPY(zzds + 4*n, z4ds, BDIGIT, z4n);
2307 BDIGITS_ZERO(zzds + 4*n + z4n, zzn - (4*n + z4n));
2309 bary_add(zzds + n, zzn - n, zzds + n, zzn - n, z1ds, z1n);
2311 bary_sub(zzds + n, zzn - n, zzds + n, zzn - n, z1ds, z1n);
2313 bary_add(zzds + 2*n, zzn - 2*n, zzds + 2*n, zzn - 2*n, z2ds, z2n);
2315 bary_sub(zzds + 2*n, zzn - 2*n, zzds + 2*n, zzn - 2*n, z2ds, z2n);
2317 bary_add(zzds + 3*n, zzn - 3*n, zzds + 3*n, zzn - 3*n, z3ds, z3n);
2319 bary_sub(zzds + 3*n, zzn - 3*n, zzds + 3*n, zzn - 3*n, z3ds, z3n);
2321 BARY_TRUNC(zzds, zzn);
2322 MEMCPY(zds, zzds, BDIGIT, zzn);
2323 BDIGITS_ZERO(zds + zzn, zn - zzn);
2332 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), zn = xn + yn;
2333 VALUE z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
2334 if (xn > yn || yn < 3 || !TOOM3_BALANCED(xn,yn))
2335 rb_raise(rb_eArgError,
"unexpected bignum length for toom3");
2336 bary_mul_toom3(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, NULL, 0);
2344bdigits_to_mpz(mpz_t mp,
const BDIGIT *digits,
size_t len)
2346 const size_t nails = (
sizeof(BDIGIT)-SIZEOF_BDIGIT)*CHAR_BIT;
2347 mpz_import(mp,
len, -1,
sizeof(BDIGIT), 0, nails, digits);
2351bdigits_from_mpz(mpz_t mp, BDIGIT *digits,
size_t *
len)
2353 const size_t nails = (
sizeof(BDIGIT)-SIZEOF_BDIGIT)*CHAR_BIT;
2354 mpz_export(digits,
len, -1,
sizeof(BDIGIT), 0, nails, mp);
2358bary_mul_gmp(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2368 bdigits_to_mpz(x, xds, xn);
2369 if (xds == yds && xn == yn) {
2373 bdigits_to_mpz(y, yds, yn);
2376 bdigits_from_mpz(z, zds, &count);
2377 BDIGITS_ZERO(zds+count, zn-count);
2386 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), zn = xn + yn;
2387 VALUE z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
2388 bary_mul_gmp(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn);
2396bary_short_mul(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2400 if (xn == 1 && yn == 1) {
2401 bary_mul_single(zds, zn, xds[0], yds[0]);
2404 bary_mul_normal(zds, zn, xds, xn, yds, yn);
2411bary_sparse_p(
const BDIGIT *ds,
size_t n)
2415 if ( ds[2 * n / 5]) c++;
2416 if (c <= 1 && ds[ n / 2]) c++;
2417 if (c <= 1 && ds[3 * n / 5]) c++;
2419 return (c <= 1) ? 1 : 0;
2423bary_mul_precheck(BDIGIT **zdsp,
size_t *znp,
const BDIGIT **xdsp,
size_t *xnp,
const BDIGIT **ydsp,
size_t *ynp)
2427 BDIGIT *zds = *zdsp;
2429 const BDIGIT *xds = *xdsp;
2431 const BDIGIT *yds = *ydsp;
2439 if (xds[xn-1] == 0) {
2455 if (yds[yn-1] == 0) {
2471 BDIGITS_ZERO(zds, nlsz);
2480 tds = xds; xds = yds; yds = tds;
2481 tn = xn; xn = yn; yn = tn;
2487 BDIGITS_ZERO(zds, zn);
2492 MEMCPY(zds, yds, BDIGIT, yn);
2493 BDIGITS_ZERO(zds+yn, zn-yn);
2496 if (POW2_P(xds[0])) {
2497 zds[yn] = bary_small_lshift(zds, yds, yn, bit_length(xds[0])-1);
2498 BDIGITS_ZERO(zds+yn+1, zn-yn-1);
2501 if (yn == 1 && yds[0] == 1) {
2503 BDIGITS_ZERO(zds+1, zn-1);
2506 bary_mul_normal(zds, zn, xds, xn, yds, yn);
2521bary_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)
2524 if (xn < KARATSUBA_MUL_DIGITS) {
2529 if (bary_sparse_p(xds, xn))
goto normal;
2530 if (bary_sparse_p(yds, yn)) {
2531 bary_short_mul(zds, zn, yds, yn, xds, xn);
2536 if (!KARATSUBA_BALANCED(xn, yn)) {
2537 bary_mul_balance_with_mulfunc(zds, zn, xds, xn, yds, yn, wds, wn, bary_mul_karatsuba_start);
2542 bary_mul_karatsuba(zds, zn, xds, xn, yds, yn, wds, wn);
2546 if (xds == yds && xn == yn) {
2547 bary_sq_fast(zds, zn, xds, xn);
2550 bary_short_mul(zds, zn, xds, xn, yds, yn);
2555bary_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)
2557 if (bary_mul_precheck(&zds, &zn, &xds, &xn, &yds, &yn))
2560 bary_mul_karatsuba_branch(zds, zn, xds, xn, yds, yn, wds, wn);
2564bary_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)
2566 if (xn < TOOM3_MUL_DIGITS) {
2567 bary_mul_karatsuba_branch(zds, zn, xds, xn, yds, yn, wds, wn);
2571 if (!TOOM3_BALANCED(xn, yn)) {
2572 bary_mul_balance_with_mulfunc(zds, zn, xds, xn, yds, yn, wds, wn, bary_mul_toom3_start);
2576 bary_mul_toom3(zds, zn, xds, xn, yds, yn, wds, wn);
2580bary_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)
2582 if (bary_mul_precheck(&zds, &zn, &xds, &xn, &yds, &yn))
2585 bary_mul_toom3_branch(zds, zn, xds, xn, yds, yn, wds, wn);
2589bary_mul(BDIGIT *zds,
size_t zn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2592 if (xn < NAIVE_MUL_DIGITS) {
2593 if (xds == yds && xn == yn)
2594 bary_sq_fast(zds, zn, xds, xn);
2596 bary_short_mul(zds, zn, xds, xn, yds, yn);
2601 if (yn < NAIVE_MUL_DIGITS) {
2602 bary_short_mul(zds, zn, yds, yn, xds, xn);
2608 bary_mul_gmp(zds, zn, xds, xn, yds, yn);
2610 bary_mul_toom3_start(zds, zn, xds, xn, yds, yn, NULL, 0);
2617 volatile VALUE stop;
2621bigdivrem1(
void *ptr)
2624 size_t yn = bds->yn;
2625 size_t zn = bds->zn;
2626 BDIGIT *yds = bds->yds, *zds = bds->zds;
2627 BDIGIT_DBL_SIGNED num;
2635 if (zds[zn-1] == yds[yn-1]) q = BDIGMAX;
2636 else q = (BDIGIT)((BIGUP(zds[zn-1]) + zds[zn-2])/yds[yn-1]);
2638 num = bigdivrem_mulsub(zds+zn-(yn+1), yn+1,
2643 num = bary_add(zds+zn-(yn+1), yn,
2657rb_big_stop(
void *ptr)
2664bigdivrem_single1(BDIGIT *qds,
const BDIGIT *xds,
size_t xn, BDIGIT x_higher_bdigit, BDIGIT y)
2671 bary_small_rshift(qds, xds, xn, bit_length(y)-1, x_higher_bdigit);
2677 t2 = x_higher_bdigit;
2678 for (i = 0; i < xn; i++) {
2679 t2 = BIGUP(t2) + xds[xn - i - 1];
2680 qds[xn - i - 1] = (BDIGIT)(t2 / y);
2688bigdivrem_single(BDIGIT *qds,
const BDIGIT *xds,
size_t xn, BDIGIT y)
2690 return bigdivrem_single1(qds, xds, xn, 0, y);
2694bigdivrem_restoring(BDIGIT *zds,
size_t zn, BDIGIT *yds,
size_t yn)
2703 for (ynzero = 0; !yds[ynzero]; ynzero++);
2705 if (ynzero+1 == yn) {
2707 r = bigdivrem_single1(zds+yn, zds+ynzero, zn-yn, zds[zn-1], yds[ynzero]);
2712 bds.yn = yn - ynzero;
2713 bds.zds = zds + ynzero;
2714 bds.yds = yds + ynzero;
2716 bds.zn = zn - ynzero;
2717 if (bds.zn > 10000 || bds.yn > 10000) {
2722 if (bds.stop ==
Qtrue) {
2733bary_divmod_normal(BDIGIT *qds,
size_t qn, BDIGIT *rds,
size_t rn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2740 RUBY_ASSERT(yn < xn || (xn == yn && yds[yn - 1] <= xds[xn - 1]));
2744 zn = xn + BIGDIVREM_EXTRA_WORDS;
2746 shift = nlz(yds[yn-1]);
2749 int alloc_z = !qds || qn < zn;
2750 if (alloc_y && alloc_z) {
2751 yyds =
ALLOCV_N(BDIGIT, tmpyz, yn+zn);
2755 yyds = alloc_y ?
ALLOCV_N(BDIGIT, tmpyz, yn) : rds;
2756 zds = alloc_z ?
ALLOCV_N(BDIGIT, tmpyz, zn) : qds;
2758 zds[xn] = bary_small_lshift(zds, xds, xn, shift);
2759 bary_small_lshift(yyds, yds, yn, shift);
2762 if (qds && zn <= qn)
2766 MEMCPY(zds, xds, BDIGIT, xn);
2770 yyds = (BDIGIT *)yds;
2773 bigdivrem_restoring(zds, zn, yyds, yn);
2777 bary_small_rshift(rds, zds, yn, shift, 0);
2779 MEMCPY(rds, zds, BDIGIT, yn);
2780 BDIGITS_ZERO(rds+yn, rn-yn);
2785 MEMMOVE(qds, zds+yn, BDIGIT, j);
2786 BDIGITS_ZERO(qds+j, qn-j);
2796 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), qn, rn;
2797 BDIGIT *xds = BDIGITS(x), *yds = BDIGITS(y), *qds, *rds;
2800 BARY_TRUNC(yds, yn);
2803 BARY_TRUNC(xds, xn);
2805 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1]))
2808 qn = xn + BIGDIVREM_EXTRA_WORDS;
2809 q = bignew(qn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
2813 r = bignew(rn, BIGNUM_SIGN(x));
2816 bary_divmod_normal(qds, qn, rds, rn, xds, xn, yds, yn);
2829bary_divmod_gmp(BDIGIT *qds,
size_t qn, BDIGIT *rds,
size_t rn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2834 RUBY_ASSERT(yn < xn || (xn == yn && yds[yn - 1] <= xds[xn - 1]));
2841 if (qds) mpz_init(q);
2842 if (rds) mpz_init(r);
2844 bdigits_to_mpz(x, xds, xn);
2845 bdigits_to_mpz(y, yds, yn);
2848 mpz_fdiv_q(q, x, y);
2851 mpz_fdiv_r(r, x, y);
2854 mpz_fdiv_qr(q, r, x, y);
2861 bdigits_from_mpz(q, qds, &count);
2862 BDIGITS_ZERO(qds+count, qn-count);
2867 bdigits_from_mpz(r, rds, &count);
2868 BDIGITS_ZERO(rds+count, rn-count);
2876 size_t xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y), qn, rn;
2877 BDIGIT *xds = BDIGITS(x), *yds = BDIGITS(y), *qds, *rds;
2880 BARY_TRUNC(yds, yn);
2883 BARY_TRUNC(xds, xn);
2885 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1]))
2889 q = bignew(qn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
2893 r = bignew(rn, BIGNUM_SIGN(x));
2896 bary_divmod_gmp(qds, qn, rds, rn, xds, xn, yds, yn);
2909bary_divmod_branch(BDIGIT *qds,
size_t qn, BDIGIT *rds,
size_t rn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2912 if (GMP_DIV_DIGITS < xn) {
2913 bary_divmod_gmp(qds, qn, rds, rn, xds, xn, yds, yn);
2917 bary_divmod_normal(qds, qn, rds, rn, xds, xn, yds, yn);
2921bary_divmod(BDIGIT *qds,
size_t qn, BDIGIT *rds,
size_t rn,
const BDIGIT *xds,
size_t xn,
const BDIGIT *yds,
size_t yn)
2926 BARY_TRUNC(yds, yn);
2930 BARY_TRUNC(xds, xn);
2932 BDIGITS_ZERO(qds, qn);
2933 BDIGITS_ZERO(rds, rn);
2937 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1])) {
2938 MEMCPY(rds, xds, BDIGIT, xn);
2939 BDIGITS_ZERO(rds+xn, rn-xn);
2940 BDIGITS_ZERO(qds, qn);
2943 MEMCPY(qds, xds, BDIGIT, xn);
2944 BDIGITS_ZERO(qds+xn, qn-xn);
2945 rds[0] = bigdivrem_single(qds, xds, xn, yds[0]);
2946 BDIGITS_ZERO(rds+1, rn-1);
2948 else if (xn == 2 && yn == 2) {
2949 BDIGIT_DBL x = bary2bdigitdbl(xds, 2);
2950 BDIGIT_DBL y = bary2bdigitdbl(yds, 2);
2951 BDIGIT_DBL q = x / y;
2952 BDIGIT_DBL r = x % y;
2954 qds[1] = BIGLO(BIGDN(q));
2955 BDIGITS_ZERO(qds+2, qn-2);
2957 rds[1] = BIGLO(BIGDN(r));
2958 BDIGITS_ZERO(rds+2, rn-2);
2961 bary_divmod_branch(qds, qn, rds, rn, xds, xn, yds, yn);
2968 return bary_zero_p(BDIGITS(x), BIGNUM_LEN(x));
2981 rb_cmperr_reason(a, b,
"comparator returned nil");
2985 if (l > 0)
return 1;
2986 if (l < 0)
return -1;
2989 if (RB_BIGNUM_TYPE_P(val)) {
2990 if (BIGZEROP(val))
return 0;
2991 if (BIGNUM_SIGN(val))
return 1;
2999#define BIGNUM_SET_LEN(b,l) \
3000 (BIGNUM_EMBED_P(b) ? \
3001 (void)(RBASIC(b)->flags = \
3002 (RBASIC(b)->flags & ~BIGNUM_EMBED_LEN_MASK) | \
3003 ((l) << BIGNUM_EMBED_LEN_SHIFT)) : \
3004 (void)(RBIGNUM(b)->as.heap.len = (l)))
3007big_embed_capa(
VALUE big)
3009 size_t size = rb_obj_shape_slot_size(big) - offsetof(
struct RBignum, as.ary);
3011 size_t capa = size /
sizeof(BDIGIT);
3017big_embed_size(
size_t capa)
3019 size_t size = offsetof(
struct RBignum, as.ary) + (
sizeof(BDIGIT) *
capa);
3020 if (size <
sizeof(
struct RBignum)) {
3021 size =
sizeof(
struct RBignum);
3027big_embeddable_p(
size_t capa)
3029 if (
capa > BIGNUM_EMBED_LEN_MAX) {
3032 return rb_gc_size_allocatable_p(big_embed_size(
capa));
3036rb_big_realloc(
VALUE big,
size_t len)
3039 size_t embed_capa = big_embed_capa(big);
3041 if (BIGNUM_EMBED_P(big)) {
3042 if (embed_capa <
len) {
3044 MEMCPY(ds, RBIGNUM(big)->as.ary, BDIGIT, embed_capa);
3045 RBIGNUM(big)->as.heap.len = BIGNUM_LEN(big);
3046 RBIGNUM(big)->as.heap.digits = ds;
3051 if (
len <= embed_capa) {
3052 ds = RBIGNUM(big)->as.heap.digits;
3053 size_t old_len = RBIGNUM(big)->as.heap.len;
3055 BIGNUM_SET_LEN(big,
len);
3056 (void)VALGRIND_MAKE_MEM_UNDEFINED((
void*)RBIGNUM(big)->as.ary, embed_capa *
sizeof(BDIGIT));
3058 MEMCPY(RBIGNUM(big)->as.ary, ds, BDIGIT,
len);
3059 SIZED_FREE_N(ds, old_len);
3063 if (BIGNUM_LEN(big) == 0) {
3064 RBIGNUM(big)->as.heap.digits =
ALLOC_N(BDIGIT,
len);
3066 else if (BIGNUM_LEN(big) !=
len) {
3067 SIZED_REALLOC_N(RBIGNUM(big)->as.heap.digits, BDIGIT,
len, BIGNUM_LEN(big));
3076 rb_big_realloc(big,
len);
3077 BIGNUM_SET_LEN(big,
len);
3081bignew_1(
VALUE klass,
size_t len,
int sign)
3085 if (big_embeddable_p(
len)) {
3086 size_t size = big_embed_size(
len);
3088 NEWOBJ_OF(big,
struct RBignum, klass,
T_BIGNUM | BIGNUM_EMBED_FLAG, size);
3090 BIGNUM_SET_SIGN(bigv, sign);
3091 BIGNUM_SET_LEN(bigv,
len);
3092 (void)VALGRIND_MAKE_MEM_UNDEFINED((
void*)big->as.ary,
len *
sizeof(BDIGIT));
3097 BIGNUM_SET_SIGN(bigv, sign);
3099 big->as.heap.len =
len;
3106rb_big_new(
size_t len,
int sign)
3108 VALUE obj = bignew(
len, sign != 0);
3109 memset(BIGNUM_DIGITS(obj), 0,
len *
sizeof(BDIGIT));
3116 size_t len = BIGNUM_LEN(x);
3119 MEMCPY(BDIGITS(z), BDIGITS(x), BDIGIT,
len);
3124big_extend_carry(
VALUE x)
3126 rb_big_resize(x, BIGNUM_LEN(x)+1);
3127 BDIGITS(x)[BIGNUM_LEN(x)-1] = 1;
3134 long i = BIGNUM_LEN(x);
3135 BDIGIT *ds = BDIGITS(x);
3137 if (bary_2comp(ds, i)) {
3138 big_extend_carry(x);
3149abs2twocomp(
VALUE *xp,
long *n_ret)
3152 long n = BIGNUM_LEN(x);
3153 BDIGIT *ds = BDIGITS(x);
3158 if (n != 0 && BIGNUM_NEGATIVE_P(x)) {
3160 MEMCPY(BDIGITS(z), ds, BDIGIT, n);
3161 bary_2comp(BDIGITS(z), n);
3170twocomp2abs_bang(
VALUE x,
int hibits)
3172 BIGNUM_SET_SIGN(x, !hibits);
3181 size_t len = BIGNUM_LEN(x);
3182 BDIGIT *ds = BDIGITS(x);
3184 if (
len == 0)
return x;
3185 while (--
len && !ds[
len]);
3186 if (BIGNUM_LEN(x) >
len+1) {
3187 rb_big_resize(x,
len+1);
3195 size_t n = BIGNUM_LEN(x);
3196 BDIGIT *ds = BDIGITS(x);
3197#if SIZEOF_BDIGIT < SIZEOF_LONG
3205 if (n == 0)
return INT2FIX(0);
3207#if SIZEOF_BDIGIT < SIZEOF_LONG
3208 if (
sizeof(
long)/SIZEOF_BDIGIT < n)
3214 u = (
unsigned long)(BIGUP(u) + ds[i]);
3224 if (BIGNUM_POSITIVE_P(x)) {
3232 rb_big_resize(x, n);
3239 if (RB_BIGNUM_TYPE_P(x)) {
3252rb_uint2big(uintptr_t n)
3256 BDIGIT *digits = BDIGITS(big);
3258#if SIZEOF_BDIGIT >= SIZEOF_VALUE
3262 digits[i] = BIGLO(n);
3268 while (--i && !digits[i]) ;
3269 BIGNUM_SET_LEN(big, i+1);
3274rb_int2big(intptr_t n)
3281 u = 1 + (
VALUE)(-(n + 1));
3287 big = rb_uint2big(u);
3289 BIGNUM_SET_NEGATIVE_SIGN(big);
3295rb_uint2inum(uintptr_t n)
3298 return rb_uint2big(n);
3302rb_int2inum(intptr_t n)
3305 return rb_int2big(n);
3309rb_big_pack(
VALUE val,
unsigned long *buf,
long num_longs)
3311 rb_integer_pack(val, buf, num_longs,
sizeof(
long), 0,
3317rb_big_unpack(
unsigned long *buf,
long num_longs)
3319 return rb_integer_unpack(buf, num_longs,
sizeof(
long), 0,
3341rb_absint_size(
VALUE val,
int *nlz_bits_ret)
3345 BDIGIT fixbuf[bdigit_roomof(
sizeof(
long))];
3347 int num_leading_zeros;
3356#if SIZEOF_BDIGIT >= SIZEOF_LONG
3361 for (i = 0; i < numberof(fixbuf); i++) {
3362 fixbuf[i] = BIGLO(v);
3368 de = fixbuf + numberof(fixbuf);
3372 de = dp + BIGNUM_LEN(val);
3374 while (dp < de && de[-1] == 0)
3381 num_leading_zeros = nlz(de[-1]);
3383 *nlz_bits_ret = num_leading_zeros % CHAR_BIT;
3384 return (de - dp) * SIZEOF_BDIGIT - num_leading_zeros / CHAR_BIT;
3388absint_numwords_small(
size_t numbytes,
int nlz_bits_in_msbyte,
size_t word_numbits,
size_t *nlz_bits_ret)
3390 size_t val_numbits = numbytes * CHAR_BIT - nlz_bits_in_msbyte;
3391 size_t div = val_numbits / word_numbits;
3392 size_t mod = val_numbits % word_numbits;
3395 numwords = mod == 0 ? div : div + 1;
3396 nlz_bits = mod == 0 ? 0 : word_numbits - mod;
3397 *nlz_bits_ret = nlz_bits;
3402absint_numwords_generic(
size_t numbytes,
int nlz_bits_in_msbyte,
size_t word_numbits,
size_t *nlz_bits_ret)
3404 static const BDIGIT char_bit[1] = { CHAR_BIT };
3405 BDIGIT numbytes_bary[bdigit_roomof(
sizeof(numbytes))];
3406 BDIGIT val_numbits_bary[bdigit_roomof(
sizeof(numbytes) + 1)];
3407 BDIGIT nlz_bits_in_msbyte_bary[1];
3408 BDIGIT word_numbits_bary[bdigit_roomof(
sizeof(word_numbits))];
3409 BDIGIT div_bary[numberof(val_numbits_bary) + BIGDIVREM_EXTRA_WORDS];
3410 BDIGIT mod_bary[numberof(word_numbits_bary)];
3411 BDIGIT one[1] = { 1 };
3417 nlz_bits_in_msbyte_bary[0] = nlz_bits_in_msbyte;
3426 bary_unpack(BARY_ARGS(numbytes_bary), &numbytes, 1,
sizeof(numbytes), 0,
3428 BARY_SHORT_MUL(val_numbits_bary, numbytes_bary, char_bit);
3429 if (nlz_bits_in_msbyte)
3430 BARY_SUB(val_numbits_bary, val_numbits_bary, nlz_bits_in_msbyte_bary);
3431 bary_unpack(BARY_ARGS(word_numbits_bary), &word_numbits, 1,
sizeof(word_numbits), 0,
3433 BARY_DIVMOD(div_bary, mod_bary, val_numbits_bary, word_numbits_bary);
3434 if (BARY_ZERO_P(mod_bary)) {
3438 BARY_ADD(div_bary, div_bary, one);
3439 bary_pack(+1, BARY_ARGS(mod_bary), &mod, 1,
sizeof(mod), 0,
3441 nlz_bits = word_numbits - mod;
3443 sign = bary_pack(+1, BARY_ARGS(div_bary), &numwords, 1,
sizeof(numwords), 0,
3449 *nlz_bits_ret = nlz_bits;
3473rb_absint_numwords(
VALUE val,
size_t word_numbits,
size_t *nlz_bits_ret)
3476 int nlz_bits_in_msbyte;
3478 size_t nlz_bits = 0;
3480 if (word_numbits == 0)
3483 numbytes = rb_absint_size(val, &nlz_bits_in_msbyte);
3485 if (numbytes <= SIZE_MAX / CHAR_BIT) {
3486 numwords = absint_numwords_small(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits);
3487 if (debug_integer_pack) {
3488 size_t numwords0, nlz_bits0;
3489 numwords0 = absint_numwords_generic(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits0);
3496 numwords = absint_numwords_generic(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits);
3498 if (numwords == (
size_t)-1)
3502 *nlz_bits_ret = nlz_bits;
3540 BDIGIT fixbuf[bdigit_roomof(
sizeof(
long))];
3550#if SIZEOF_BDIGIT >= SIZEOF_LONG
3555 for (i = 0; i < numberof(fixbuf); i++) {
3556 fixbuf[i] = BIGLO(v);
3562 de = fixbuf + numberof(fixbuf);
3566 de = dp + BIGNUM_LEN(val);
3568 while (dp < de && de[-1] == 0)
3570 while (dp < de && dp[0] == 0)
3637rb_integer_pack(
VALUE val,
void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
3642 BDIGIT fixbuf[bdigit_roomof(
sizeof(
long))];
3655#if SIZEOF_BDIGIT >= SIZEOF_LONG
3660 for (i = 0; i < numberof(fixbuf); i++) {
3661 fixbuf[i] = BIGLO(v);
3667 num_bdigits = numberof(fixbuf);
3670 sign = BIGNUM_POSITIVE_P(val) ? 1 : -1;
3672 num_bdigits = BIGNUM_LEN(val);
3675 return bary_pack(sign, ds, num_bdigits, words, numwords, wordsize, nails, flags);
3723rb_integer_unpack(
const void *words,
size_t numwords,
size_t wordsize,
size_t nails,
int flags)
3730 BDIGIT fixbuf[2] = { 0, 0 };
3732 validate_integer_pack_format(numwords, wordsize, nails, flags,
3743 num_bdigits = integer_unpack_num_bdigits(numwords, wordsize, nails, &nlp_bits);
3745 if (LONG_MAX-1 < num_bdigits)
3746 rb_raise(rb_eArgError,
"too big to unpack as an integer");
3752 val = bignew((
long)num_bdigits, 0);
3755 sign = bary_unpack_internal(ds, num_bdigits, words, numwords, wordsize, nails, flags, nlp_bits);
3759 big_extend_carry(val);
3761 else if (num_bdigits == numberof(fixbuf)) {
3762 val = bignew((
long)num_bdigits+1, 0);
3763 MEMCPY(BDIGITS(val), fixbuf, BDIGIT, num_bdigits);
3764 BDIGITS(val)[num_bdigits++] = 1;
3767 ds[num_bdigits++] = 1;
3772 BDIGIT_DBL u = fixbuf[0] + BIGUP(fixbuf[1]);
3777 if (sign < 0 && BDIGIT_MSB(fixbuf[1]) == 0 &&
3779 return LONG2FIX((
long)-(BDIGIT_DBL_SIGNED)u);
3780 val = bignew((
long)num_bdigits, 0 <= sign);
3781 MEMCPY(BDIGITS(val), fixbuf, BDIGIT, num_bdigits);
3785 bary_zero_p(BDIGITS(val), BIGNUM_LEN(val)))
3787 BIGNUM_SET_SIGN(val, 0 <= sign);
3790 return bigtrunc(val);
3791 return bignorm(val);
3794#define conv_digit(c) (ruby_digit36_to_number_table[(unsigned char)(c)])
3796NORETURN(
static inline void invalid_radix(
int base));
3797NORETURN(
static inline void invalid_integer(
VALUE s));
3800valid_radix_p(
int base)
3802 return (1 < base && base <= 36);
3806invalid_radix(
int base)
3808 rb_raise(rb_eArgError,
"invalid radix %d", base);
3812invalid_integer(
VALUE s)
3814 rb_raise(rb_eArgError,
"invalid value for Integer(): %+"PRIsVALUE, s);
3818str2big_scan_digits(
const char *s,
const char *str,
int base,
int badcheck,
size_t *num_digits_p, ssize_t *len_p)
3821 size_t num_digits = 0;
3822 const char *digits_start = str;
3823 const char *digits_end = str;
3824 ssize_t
len = *len_p;
3834 if (badcheck && *str ==
'_')
return FALSE;
3836 while ((c = *str++) != 0) {
3839 if (badcheck)
return FALSE;
3842 nondigit = (char) c;
3844 else if ((c = conv_digit(c)) < 0 || c >= base) {
3852 if (
len > 0 && !--
len)
break;
3854 if (badcheck && nondigit)
return FALSE;
3855 if (badcheck &&
len) {
3857 while (*str &&
ISSPACE(*str)) {
3859 if (
len > 0 && !--
len)
break;
3865 *num_digits_p = num_digits;
3866 *len_p = digits_end - digits_start;
3873 const char *digits_start,
3874 const char *digits_end,
3887 num_bdigits = (num_digits / BITSPERDIG) * bits_per_digit + roomof((num_digits % BITSPERDIG) * bits_per_digit, BITSPERDIG);
3888 z = bignew(num_bdigits, sign);
3892 for (p = digits_end; digits_start < p; p--) {
3893 if ((c = conv_digit(p[-1])) < 0)
3895 dd |= (BDIGIT_DBL)c << numbits;
3896 numbits += bits_per_digit;
3897 if (BITSPERDIG <= numbits) {
3900 numbits -= BITSPERDIG;
3906 RUBY_ASSERT((
size_t)(dp - BDIGITS(z)) == num_bdigits);
3914 const char *digits_start,
3915 const char *digits_end,
3928 z = bignew(num_bdigits, sign);
3930 BDIGITS_ZERO(zds, num_bdigits);
3932 for (p = digits_start; p < digits_end; p++) {
3933 if ((c = conv_digit(*p)) < 0)
3939 num += (BDIGIT_DBL)zds[i]*base;
3940 zds[i++] = BIGLO(num);
3958 const char *digits_start,
3959 const char *digits_end,
3962 int digits_per_bdigits_dbl,
3968 BDIGIT *uds, *vds, *tds;
3970 BDIGIT_DBL current_base;
3972 int power_level = 0;
3979 uds =
ALLOCV_N(BDIGIT, tmpuv, 2*num_bdigits);
3980 vds = uds + num_bdigits;
3982 powerv = power_cache_get_power(base, power_level, NULL);
3987 m = digits_per_bdigits_dbl;
3988 if (num_digits < (
size_t)m)
3989 m = (int)num_digits;
3990 for (p = digits_end; digits_start < p; p--) {
3991 if ((c = conv_digit(p[-1])) < 0)
3993 dd = dd + c * current_base;
3994 current_base *= base;
3998 uds[i++] = BIGLO(dd);
3999 uds[i++] = (BDIGIT)BIGDN(dd);
4001 m = digits_per_bdigits_dbl;
4002 if (num_digits < (
size_t)m)
4003 m = (int)num_digits;
4008 for (unit = 2; unit < num_bdigits; unit *= 2) {
4009 for (i = 0; i < num_bdigits; i += unit*2) {
4010 if (2*unit <= num_bdigits - i) {
4011 bary_mul(vds+i, unit*2, BDIGITS(powerv), BIGNUM_LEN(powerv), uds+i+unit, unit);
4012 bary_add(vds+i, unit*2, vds+i, unit*2, uds+i, unit);
4014 else if (unit <= num_bdigits - i) {
4015 bary_mul(vds+i, num_bdigits-i, BDIGITS(powerv), BIGNUM_LEN(powerv), uds+i+unit, num_bdigits-(i+unit));
4016 bary_add(vds+i, num_bdigits-i, vds+i, num_bdigits-i, uds+i, unit);
4019 MEMCPY(vds+i, uds+i, BDIGIT, num_bdigits-i);
4023 powerv = power_cache_get_power(base, power_level, NULL);
4028 BARY_TRUNC(uds, num_bdigits);
4029 z = bignew(num_bdigits, sign);
4030 MEMCPY(BDIGITS(z), uds, BDIGIT, num_bdigits);
4042 const char *digits_start,
4043 const char *digits_end,
4056 buf =
ALLOCV_N(
char, tmps, num_digits+1);
4058 for (q = digits_start; q < digits_end; q++) {
4059 if (conv_digit(*q) < 0)
4066 mpz_set_str(mz, buf, base);
4068 z = bignew(zn, sign);
4070 bdigits_from_mpz(mz, BDIGITS(z), &count);
4071 BDIGITS_ZERO(zds+count, zn-count);
4081static VALUE rb_cstr_parse_inum(
const char *str, ssize_t
len,
char **endp,
int base);
4100rb_cstr_to_inum(
const char *str,
int base,
int badcheck)
4103 VALUE ret = rb_cstr_parse_inum(str, -1, (badcheck ? NULL : &end), base);
4129rb_int_parse_cstr(
const char *str, ssize_t
len,
char **endp,
size_t *ndigits,
4130 int base,
int flags)
4132 const char *
const s = str;
4140 const char *digits_start, *digits_end;
4141 size_t num_digits = 0;
4143 const ssize_t len0 =
len;
4144 const int badcheck = !endp;
4147 if (len > 0 && len <= (n)) goto bad; \
4151#define ASSERT_LEN() do {\
4152 RUBY_ASSERT(len != 0); \
4153 if (len0 >= 0) RUBY_ASSERT(s + len0 == str + len); \
4162 if (str[0] ==
'+') {
4165 else if (str[0] ==
'-') {
4172 if (str[0] ==
'0' &&
len > 1) {
4194 else if (base < -1) {
4204 else if (base == 2) {
4205 if (str[0] ==
'0' && (str[1] ==
'b'||str[1] ==
'B')) {
4209 else if (base == 8) {
4210 if (str[0] ==
'0' && (str[1] ==
'o'||str[1] ==
'O')) {
4214 else if (base == 10) {
4215 if (str[0] ==
'0' && (str[1] ==
'd'||str[1] ==
'D')) {
4219 else if (base == 16) {
4220 if (str[0] ==
'0' && (str[1] ==
'x'||str[1] ==
'X')) {
4224 if (!valid_radix_p(base)) {
4225 invalid_radix(base);
4228 num_digits = str - s;
4229 if (*str ==
'0' &&
len != 1) {
4231 const char *end =
len < 0 ? NULL : str +
len;
4232 while (str != end) {
4233 const char *next = str + 1;
4236 if (next == end || !*next ||
ISSPACE(*next))
4242 if (++us >= 2 || next == end || !*next ||
ISSPACE(*next))
4250 if (end)
len = end - str;
4254 if (c < 0 || c >= base) {
4255 if (!badcheck && num_digits) z =
INT2FIX(0);
4259 if (ndigits) *ndigits = num_digits;
4260 val = ruby_scan_digits(str,
len, base, &num_digits, &ov);
4262 const char *end = &str[num_digits];
4265 if (endp) *endp = (
char *)end;
4266 if (ndigits) *ndigits += num_digits;
4268 if (num_digits == 0)
return Qnil;
4269 while (
len < 0 ? *end : end < str +
len) {
4278 long result = -(long)val;
4283 VALUE big = rb_uint2big(val);
4284 BIGNUM_SET_SIGN(big, sign);
4285 return bignorm(big);
4291 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4293 if (endp) *endp = (
char *)(str +
len);
4294 if (ndigits) *ndigits += num_digits;
4295 digits_end = digits_start +
len;
4298 z = str2big_poweroftwo(sign, digits_start, digits_end, num_digits,
4299 bit_length(base-1));
4302 int digits_per_bdigits_dbl;
4303 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4304 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4307 if (GMP_STR2BIG_DIGITS < num_bdigits) {
4308 z = str2big_gmp(sign, digits_start, digits_end, num_digits,
4313 if (num_bdigits < KARATSUBA_MUL_DIGITS) {
4314 z = str2big_normal(sign, digits_start, digits_end,
4318 z = str2big_karatsuba(sign, digits_start, digits_end, num_digits,
4319 num_bdigits, digits_per_bdigits_dbl, base);
4326 if (endp) *endp = (
char *)str;
4327 if (ndigits) *ndigits = num_digits;
4332rb_cstr_parse_inum(
const char *str, ssize_t
len,
char **endp,
int base)
4334 return rb_int_parse_cstr(str,
len, endp, NULL, base,
4339rb_str_convert_to_inum(
VALUE str,
int base,
int badcheck,
int raise_exception)
4349 ret = rb_cstr_parse_inum(s,
len, (badcheck ? NULL : &end), base);
4352 if (!raise_exception)
return Qnil;
4353 invalid_integer(str);
4361rb_str_to_inum(
VALUE str,
int base,
int badcheck)
4363 return rb_str_convert_to_inum(str, base, badcheck, TRUE);
4367rb_str2big_poweroftwo(
VALUE arg,
int base,
int badcheck)
4370 const char *s, *str;
4371 const char *digits_start, *digits_end;
4376 if (!valid_radix_p(base) || !POW2_P(base)) {
4377 invalid_radix(base);
4382 len = RSTRING_LEN(arg);
4390 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4391 invalid_integer(arg);
4392 digits_end = digits_start +
len;
4394 z = str2big_poweroftwo(positive_p, digits_start, digits_end, num_digits,
4395 bit_length(base-1));
4403rb_str2big_normal(
VALUE arg,
int base,
int badcheck)
4406 const char *s, *str;
4407 const char *digits_start, *digits_end;
4412 int digits_per_bdigits_dbl;
4415 if (!valid_radix_p(base)) {
4416 invalid_radix(base);
4421 len = RSTRING_LEN(arg);
4422 if (
len > 0 && *str ==
'-') {
4429 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4430 invalid_integer(arg);
4431 digits_end = digits_start +
len;
4433 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4434 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4436 z = str2big_normal(positive_p, digits_start, digits_end,
4445rb_str2big_karatsuba(
VALUE arg,
int base,
int badcheck)
4448 const char *s, *str;
4449 const char *digits_start, *digits_end;
4454 int digits_per_bdigits_dbl;
4457 if (!valid_radix_p(base)) {
4458 invalid_radix(base);
4463 len = RSTRING_LEN(arg);
4464 if (
len > 0 && *str ==
'-') {
4471 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4472 invalid_integer(arg);
4473 digits_end = digits_start +
len;
4475 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4476 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4478 z = str2big_karatsuba(positive_p, digits_start, digits_end, num_digits,
4479 num_bdigits, digits_per_bdigits_dbl, base);
4488rb_str2big_gmp(
VALUE arg,
int base,
int badcheck)
4491 const char *s, *str;
4492 const char *digits_start, *digits_end;
4497 int digits_per_bdigits_dbl;
4500 if (!valid_radix_p(base)) {
4501 invalid_radix(base);
4506 len = RSTRING_LEN(arg);
4507 if (
len > 0 && *str ==
'-') {
4514 if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &
len))
4515 invalid_integer(arg);
4516 digits_end = digits_start +
len;
4518 maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl);
4519 num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2;
4521 z = str2big_gmp(positive_p, digits_start, digits_end, num_digits, num_bdigits, base);
4535 VALUE big = bignew(bdigit_roomof(SIZEOF_LONG_LONG), 1);
4536 BDIGIT *digits = BDIGITS(big);
4538#if SIZEOF_BDIGIT >= SIZEOF_LONG_LONG
4541 for (i = 0; i < bdigit_roomof(SIZEOF_LONG_LONG); i++) {
4542 digits[i] = BIGLO(n);
4547 i = bdigit_roomof(SIZEOF_LONG_LONG);
4548 while (i-- && !digits[i]) ;
4549 BIGNUM_SET_LEN(big, i+1);
4567 big = rb_ull2big(u);
4569 BIGNUM_SET_NEGATIVE_SIGN(big);
4578 return rb_ull2big(n);
4585 return rb_ll2big(n);
4592rb_uint128t2big(uint128_t n)
4595 VALUE big = bignew(bdigit_roomof(SIZEOF_INT128_T), 1);
4596 BDIGIT *digits = BDIGITS(big);
4598 for (i = 0; i < bdigit_roomof(SIZEOF_INT128_T); i++) {
4599 digits[i] = BIGLO(RSHIFT(n ,BITSPERDIG*i));
4602 i = bdigit_roomof(SIZEOF_INT128_T);
4603 while (i-- && !digits[i]) ;
4604 BIGNUM_SET_LEN(big, i+1);
4609rb_int128t2big(int128_t n)
4616 u = 1 + (uint128_t)(-(n + 1));
4622 big = rb_uint128t2big(u);
4624 BIGNUM_SET_NEGATIVE_SIGN(big);
4631rb_cstr2inum(
const char *str,
int base)
4633 return rb_cstr_to_inum(str, base, base==0);
4639 return rb_str_to_inum(str, base, base==0);
4643big_shift3(
VALUE x,
int lshift_p,
size_t shift_numdigits,
int shift_numbits)
4652 if (LONG_MAX < shift_numdigits) {
4656 s1 = shift_numdigits;
4658 if ((
size_t)s1 != shift_numdigits)
goto too_big;
4660 if (LONG_MAX/SIZEOF_BDIGIT <= xn+s1)
goto too_big;
4661 z = bignew(xn+s1+1, BIGNUM_SIGN(x));
4663 BDIGITS_ZERO(zds, s1);
4665 zds[xn+s1] = bary_small_lshift(zds+s1, xds, xn, s2);
4670 if (LONG_MAX < shift_numdigits || (
size_t)BIGNUM_LEN(x) <= shift_numdigits) {
4671 if (BIGNUM_POSITIVE_P(x) ||
4672 bary_zero_p(BDIGITS(x), BIGNUM_LEN(x)))
4677 s1 = shift_numdigits;
4679 hibitsx = abs2twocomp(&x, &xn);
4687 bary_small_rshift(zds, xds+s1, zn, s2, hibitsx != 0 ? BDIGMAX : 0);
4688 twocomp2abs_bang(z, hibitsx != 0);
4699 size_t shift_numdigits;
4707 sign = rb_integer_pack(y, lens, numberof(lens),
sizeof(
size_t), 0,
4710 lshift_p = !lshift_p;
4714 if (1 < sign || CHAR_BIT <= lens[1])
4718 if (1 < sign || CHAR_BIT <= lens[1])
4721 shift_numbits = (int)(lens[0] & (BITSPERDIG-1));
4722 shift_numdigits = (lens[0] >> bit_length(BITSPERDIG-1)) |
4723 (lens[1] << (CHAR_BIT*SIZEOF_SIZE_T - bit_length(BITSPERDIG-1)));
4724 return big_shift3(x, lshift_p, shift_numdigits, shift_numbits);
4728big_lshift(
VALUE x,
unsigned long shift)
4730 long s1 = shift/BITSPERDIG;
4731 int s2 = (int)(shift%BITSPERDIG);
4732 return big_shift3(x, 1, s1, s2);
4736big_rshift(
VALUE x,
unsigned long shift)
4738 long s1 = shift/BITSPERDIG;
4739 int s2 = (int)(shift%BITSPERDIG);
4740 return big_shift3(x, 0, s1, s2);
4743#define MAX_BASE36_POWER_TABLE_ENTRIES (SIZEOF_SIZE_T * CHAR_BIT + 1)
4745static VALUE base36_power_cache[35][MAX_BASE36_POWER_TABLE_ENTRIES];
4746static size_t base36_numdigits_cache[35][MAX_BASE36_POWER_TABLE_ENTRIES];
4749power_cache_init(
void)
4754power_cache_get_power(
int base,
int power_level,
size_t *numdigits_ret)
4770 if (MAX_BASE36_POWER_TABLE_ENTRIES <= power_level)
4771 rb_bug(
"too big power number requested: maxpow_in_bdigit_dbl(%d)**(2**%d)", base, power_level);
4773 VALUE power = rbimpl_atomic_value_load(&base36_power_cache[base - 2][power_level], RBIMPL_ATOMIC_ACQUIRE);
4776 if (power_level == 0) {
4778 BDIGIT_DBL dd = maxpow_in_bdigit_dbl(base, &numdigits0);
4779 power = bignew(2, 1);
4780 bdigitdbl2bary(BDIGITS(power), 2, dd);
4781 numdigits = numdigits0;
4784 power = bigtrunc(bigsq(power_cache_get_power(base, power_level - 1, &numdigits)));
4788 base36_numdigits_cache[base - 2][power_level] = numdigits;
4790 VALUE old = rbimpl_atomic_value_cas(&base36_power_cache[base - 2][power_level], 0, power,
4791 RBIMPL_ATOMIC_RELEASE, RBIMPL_ATOMIC_ACQUIRE);
4796 rb_vm_register_global_object(power);
4800 *numdigits_ret = base36_numdigits_cache[base - 2][power_level];
4808 int hbase2_numdigits;
4817 rb_raise(rb_eArgError,
"too big number");
4819 b2s->ptr = RSTRING_PTR(b2s->result);
4825big2str_2bdigits(
struct big2str_struct *b2s, BDIGIT *xds,
size_t xn,
size_t taillen)
4829 int beginning = !b2s->ptr;
4833 num = bary2bdigitdbl(xds, xn);
4836 char buf[SIZEOF_BDIGIT_DBL*CHAR_BIT], *p = buf;
4840 j -= ruby_convert_to_digits(&p[j], num, b2s->base);
4841 len =
sizeof(buf) - j;
4842 big2str_alloc(b2s,
len + taillen);
4847 j = b2s->hbase2_numdigits;
4848 j -= ruby_convert_to_digits(&p[j], num, b2s->base);
4855 len = b2s->hbase2_numdigits;
4861big2str_karatsuba(
struct big2str_struct *b2s, BDIGIT *xds,
size_t xn,
size_t wn,
4862 int power_level,
size_t taillen)
4865 size_t half_numdigits, lower_numdigits;
4866 int lower_power_level;
4891 if (xn == 0 || bary_zero_p(xds, xn)) {
4894 power_cache_get_power(b2s->base, power_level, &
len);
4895 memset(b2s->ptr,
'0',
len);
4901 if (power_level == 0) {
4902 big2str_2bdigits(b2s, xds, xn, taillen);
4906 lower_power_level = power_level-1;
4907 b = power_cache_get_power(b2s->base, lower_power_level, &lower_numdigits);
4911 half_numdigits = lower_numdigits;
4913 while (0 < lower_power_level &&
4915 (xn == bn && bary_cmp(xds, xn, bds, bn) < 0))) {
4916 lower_power_level--;
4917 b = power_cache_get_power(b2s->base, lower_power_level, &lower_numdigits);
4922 if (lower_power_level == 0 &&
4924 (xn == bn && bary_cmp(xds, xn, bds, bn) < 0))) {
4926 len = half_numdigits * 2 - lower_numdigits;
4927 memset(b2s->ptr,
'0',
len);
4930 big2str_2bdigits(b2s, xds, xn, taillen);
4938 if (lower_power_level != power_level-1 && b2s->ptr) {
4939 len = (half_numdigits - lower_numdigits) * 2;
4940 memset(b2s->ptr,
'0',
len);
4944 shift = nlz(bds[bn-1]);
4946 qn = xn + BIGDIVREM_EXTRA_WORDS;
4951 tds = (BDIGIT *)bds;
4959 bary_small_lshift(tds, bds, bn, shift);
4960 xds[xn] = bary_small_lshift(xds, xds, xn, shift);
4963 bigdivrem_restoring(xds, qn, tds, bn);
4972 bary_small_rshift(rds, rds, rn, shift, 0);
4975 BARY_TRUNC(qds, qn);
4977 big2str_karatsuba(b2s, qds, qn, xn+wn - (rn+qn), lower_power_level, lower_numdigits+taillen);
4978 BARY_TRUNC(rds, rn);
4979 big2str_karatsuba(b2s, rds, rn, xn+wn - rn, lower_power_level, taillen);
4984big2str_base_poweroftwo(
VALUE x,
int base)
4986 int word_numbits = ffs(base) - 1;
4990 numwords = rb_absint_numwords(x, word_numbits, NULL);
4991 if (BIGNUM_NEGATIVE_P(x)) {
4992 if (LONG_MAX-1 < numwords)
4993 rb_raise(rb_eArgError,
"too big number");
4995 ptr = RSTRING_PTR(result);
4996 *ptr++ = BIGNUM_POSITIVE_P(x) ?
'+' :
'-';
4999 if (LONG_MAX < numwords)
5000 rb_raise(rb_eArgError,
"too big number");
5002 ptr = RSTRING_PTR(result);
5004 rb_integer_pack(x, ptr, numwords, 1, CHAR_BIT-word_numbits,
5006 while (0 < numwords) {
5007 *ptr = ruby_digitmap[(
unsigned char)*ptr];
5015rb_big2str_poweroftwo(
VALUE x,
int base)
5017 return big2str_base_poweroftwo(x, base);
5021big2str_generic(
VALUE x,
int base)
5031 BARY_TRUNC(xds, xn);
5037 if (!valid_radix_p(base))
5038 invalid_radix(base);
5040 if (xn >= LONG_MAX/BITSPERDIG) {
5041 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'string'");
5045 power = power_cache_get_power(base, power_level, NULL);
5046 while (power_level < MAX_BASE36_POWER_TABLE_ENTRIES &&
5047 (
size_t)BIGNUM_LEN(power) <= (xn+1)/2) {
5049 power = power_cache_get_power(base, power_level, NULL);
5051 RUBY_ASSERT(power_level != MAX_BASE36_POWER_TABLE_ENTRIES);
5053 if ((
size_t)BIGNUM_LEN(power) <= xn) {
5067 b2s_data.negative = BIGNUM_NEGATIVE_P(x);
5068 b2s_data.base = (
unsigned int)base;
5069 b2s_data.hbase2 = maxpow_in_bdigit_dbl(base, &b2s_data.hbase2_numdigits);
5071 b2s_data.result =
Qnil;
5072 b2s_data.ptr = NULL;
5074 if (power_level == 0) {
5075 big2str_2bdigits(&b2s_data, xds, xn, 0);
5081 wn = power_level * BIGDIVREM_EXTRA_WORDS + BIGNUM_LEN(power);
5082 wds =
ALLOCV_N(BDIGIT, tmpw, xn + wn);
5083 MEMCPY(wds, xds, BDIGIT, xn);
5084 big2str_karatsuba(&b2s_data, wds, xn, wn, power_level, 0);
5090 *b2s_data.ptr =
'\0';
5091 rb_str_resize(b2s_data.result, (
rb_len_t)(b2s_data.ptr - RSTRING_PTR(b2s_data.result)));
5094 return b2s_data.result;
5098rb_big2str_generic(
VALUE x,
int base)
5100 return big2str_generic(x, base);
5105big2str_gmp(
VALUE x,
int base)
5110 BDIGIT *xds = BDIGITS(x);
5111 size_t xn = BIGNUM_LEN(x);
5114 bdigits_to_mpz(mx, xds, xn);
5116 size = mpz_sizeinbase(mx, base);
5118 if (BIGNUM_NEGATIVE_P(x)) {
5125 mpz_get_str(RSTRING_PTR(str), base, mx);
5128 if (RSTRING_PTR(str)[RSTRING_LEN(str)-1] ==
'\0') {
5137rb_big2str_gmp(
VALUE x,
int base)
5139 return big2str_gmp(x, base);
5144rb_big2str1(
VALUE x,
int base)
5156 BARY_TRUNC(xds, xn);
5162 if (!valid_radix_p(base))
5163 invalid_radix(base);
5165 if (xn >= LONG_MAX/BITSPERDIG) {
5166 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'string'");
5171 return big2str_base_poweroftwo(x, base);
5175 if (GMP_BIG2STR_DIGITS < xn) {
5176 return big2str_gmp(x, base);
5180 return big2str_generic(x, base);
5186 return rb_big2str1(x, base);
5192#if SIZEOF_LONG > SIZEOF_BDIGIT
5195 size_t len = BIGNUM_LEN(x);
5201 if (BIGSIZE(x) >
sizeof(
long)) {
5205#if SIZEOF_LONG <= SIZEOF_BDIGIT
5206 num = (
unsigned long)ds[0];
5209 for (i = 0; i <
len; i++) {
5211 num += (
unsigned long)ds[
len - i - 1];
5220 unsigned long num = big2ulong(x,
"unsigned long");
5222 if (BIGNUM_POSITIVE_P(x)) {
5226 if (num <= 1+(
unsigned long)(-(LONG_MIN+1)))
5227 return -(long)(num-1)-1;
5229 rb_raise(
rb_eRangeError,
"bignum out of range of unsigned long");
5235 unsigned long num = big2ulong(x,
"long");
5237 if (BIGNUM_POSITIVE_P(x)) {
5238 if (num <= LONG_MAX)
5242 if (num <= 1+(
unsigned long)(-(LONG_MIN+1)))
5243 return -(long)(num-1)-1;
5245 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'long'");
5253#if SIZEOF_LONG_LONG > SIZEOF_BDIGIT
5256 size_t len = BIGNUM_LEN(x);
5258 BDIGIT *ds = BDIGITS(x);
5262 if (BIGSIZE(x) > SIZEOF_LONG_LONG)
5264#if SIZEOF_LONG_LONG <= SIZEOF_BDIGIT
5268 for (i = 0; i <
len; i++) {
5270 num += ds[
len - i - 1];
5279 unsigned LONG_LONG num = big2ull(x,
"unsigned long long");
5281 if (BIGNUM_POSITIVE_P(x)) {
5285 if (num <= 1+(
unsigned LONG_LONG)(-(LLONG_MIN+1)))
5288 rb_raise(
rb_eRangeError,
"bignum out of range of unsigned long long");
5294 unsigned LONG_LONG num = big2ull(x,
"long long");
5296 if (BIGNUM_POSITIVE_P(x)) {
5297 if (num <= LLONG_MAX)
5301 if (num <= 1+(
unsigned LONG_LONG)(-(LLONG_MIN+1)))
5304 rb_raise(
rb_eRangeError,
"bignum too big to convert into 'long long'");
5316 double u = (d < 0)?-d:d;
5326 u /= (double)(BIGRAD);
5329 z = bignew(i, d>=0);
5330 digits = BDIGITS(z);
5344 return bignorm(dbl2big(d));
5351 long i = (bigtrunc(x), BIGNUM_LEN(x)), lo = 0, bits;
5352 BDIGIT *ds = BDIGITS(x), dl;
5355 bits = i * BITSPERDIG - nlz(ds[i-1]);
5356 if (bits > DBL_MANT_DIG+DBL_MAX_EXP) {
5360 if (bits > DBL_MANT_DIG+1)
5361 lo = (bits -= DBL_MANT_DIG+1) / BITSPERDIG;
5365 d = ds[i] + BIGRAD*d;
5368 if (bits && (dl & ((BDIGIT)1 << (bits %= BITSPERDIG)))) {
5369 int carry = (dl & ~(BDIGMAX << bits)) != 0;
5377 BDIGIT mask = BDIGMAX;
5389 if (lo > INT_MAX / BITSPERDIG)
5391 else if (lo < INT_MIN / BITSPERDIG)
5394 d = ldexp(d, (
int)(lo * BITSPERDIG));
5398 if (BIGNUM_NEGATIVE_P(x)) d = -d;
5405 double d = big2dbl(x);
5427 if (yd > 0.0)
return INT2FIX(-1);
5432#if SIZEOF_LONG * CHAR_BIT < DBL_MANT_DIG
5459 rel = rb_big_cmp(x, y);
5460 if (yf == 0.0 || rel !=
INT2FIX(0))
5467#if SIZEOF_LONG * CHAR_BIT >= DBL_MANT_DIG
5468COMPILER_WARNING_PUSH
5469#if __has_warning("-Wimplicit-int-float-conversion")
5470COMPILER_WARNING_IGNORED(-Wimplicit-
int-
float-conversion)
5472static const double LONG_MAX_as_double = LONG_MAX;
5488#if SIZEOF_LONG * CHAR_BIT < DBL_MANT_DIG
5490 return RBOOL(xd == yd);
5493 if (yi < LONG_MIN || LONG_MAX_as_double <= yi)
5497 return RBOOL(xn == yn);
5501 return rb_big_eq(x, y);
5514 if (sx < sy)
return INT2FIX(-1);
5518 else if (RB_BIGNUM_TYPE_P(y)) {
5519 if (BIGNUM_SIGN(x) == BIGNUM_SIGN(y)) {
5520 int cmp = bary_cmp(BDIGITS(x), BIGNUM_LEN(x), BDIGITS(y), BIGNUM_LEN(y));
5521 return INT2FIX(BIGNUM_SIGN(x) ? cmp : -cmp);
5525 return rb_integer_float_cmp(x, y);
5530 return INT2FIX(BIGNUM_SIGN(x) ? 1 : -1);
5547 rel = rb_big_cmp(x, y);
5550 rel = rb_integer_float_cmp(x, y);
5555 case big_op_gt:
id =
'>';
break;
5556 case big_op_ge:
id = idGE;
break;
5557 case big_op_lt:
id =
'<';
break;
5558 case big_op_le:
id = idLE;
break;
5567 case big_op_gt:
return RBOOL(n > 0);
5568 case big_op_ge:
return RBOOL(n >= 0);
5569 case big_op_lt:
return RBOOL(n < 0);
5570 case big_op_le:
return RBOOL(n <= 0);
5578 return big_op(x, y, big_op_gt);
5584 return big_op(x, y, big_op_ge);
5590 return big_op(x, y, big_op_lt);
5596 return big_op(x, y, big_op_le);
5614 return RBOOL(bignorm(x) == y);
5616 else if (RB_BIGNUM_TYPE_P(y)) {
5619 return rb_integer_float_eq(x, y);
5622 return rb_equal(y, x);
5624 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y))
return Qfalse;
5625 if (BIGNUM_LEN(x) != BIGNUM_LEN(y))
return Qfalse;
5626 return RBOOL(
MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,BIGNUM_LEN(y)) == 0);
5632 if (!RB_BIGNUM_TYPE_P(y))
return Qfalse;
5633 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y))
return Qfalse;
5634 if (BIGNUM_LEN(x) != BIGNUM_LEN(y))
return Qfalse;
5635 return RBOOL(
MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,BIGNUM_LEN(y)) == 0);
5639rb_big_uminus(
VALUE x)
5641 VALUE z = rb_big_clone(x);
5651 VALUE z = rb_big_clone(x);
5652 BDIGIT *ds = BDIGITS(z);
5653 long n = BIGNUM_LEN(z);
5657 if (BIGNUM_POSITIVE_P(z)) {
5658 if (bary_add_one(ds, n)) {
5659 big_extend_carry(z);
5661 BIGNUM_SET_NEGATIVE_SIGN(z);
5665 if (bary_add_one(ds, n))
5668 BIGNUM_SET_POSITIVE_SIGN(z);
5678 BDIGIT *xds, *yds, *zds;
5683 zn = xn < yn ? yn : xn;
5691 if (bary_sub(zds, zn, xds, xn, yds, yn)) {
5692 bary_2comp(zds, zn);
5693 BIGNUM_SET_NEGATIVE_SIGN(z);
5702bigsub_int(
VALUE x,
long y0)
5707 BDIGIT_DBL_SIGNED num;
5718#if SIZEOF_BDIGIT < SIZEOF_LONG
5719 if (zn < bdigit_roomof(SIZEOF_LONG))
5720 zn = bdigit_roomof(SIZEOF_LONG);
5722 z = bignew(zn, BIGNUM_SIGN(x));
5725#if SIZEOF_BDIGIT >= SIZEOF_LONG
5727 num = (BDIGIT_DBL_SIGNED)xds[0] - y;
5728 if (xn == 1 && num < 0) {
5730 zds[0] = (BDIGIT)-num;
5734 zds[0] = BIGLO(num);
5742 for (i=0; i < xn; i++) {
5743 if (y == 0)
goto y_is_zero_x;
5744 num += (BDIGIT_DBL_SIGNED)xds[i] - BIGLO(y);
5745 zds[i] = BIGLO(num);
5749 for (; i < zn; i++) {
5750 if (y == 0)
goto y_is_zero_z;
5752 zds[i] = BIGLO(num);
5759 for (; i < xn; i++) {
5761 if (num == 0)
goto num_is_zero_x;
5763 zds[i] = BIGLO(num);
5766#if SIZEOF_BDIGIT < SIZEOF_LONG
5767 for (; i < zn; i++) {
5769 if (num == 0)
goto num_is_zero_z;
5770 zds[i] = BIGLO(num);
5776 for (; i < xn; i++) {
5780#if SIZEOF_BDIGIT < SIZEOF_LONG
5781 for (; i < zn; i++) {
5799bigadd_int(
VALUE x,
long y)
5814#if SIZEOF_BDIGIT < SIZEOF_LONG
5815 if (zn < bdigit_roomof(SIZEOF_LONG))
5816 zn = bdigit_roomof(SIZEOF_LONG);
5820 z = bignew(zn, BIGNUM_SIGN(x));
5823#if SIZEOF_BDIGIT >= SIZEOF_LONG
5824 num = (BDIGIT_DBL)xds[0] + y;
5825 zds[0] = BIGLO(num);
5833 for (i=0; i < xn; i++) {
5834 if (y == 0)
goto y_is_zero_x;
5835 num += (BDIGIT_DBL)xds[i] + BIGLO(y);
5836 zds[i] = BIGLO(num);
5840 for (; i < zn; i++) {
5841 if (y == 0)
goto y_is_zero_z;
5843 zds[i] = BIGLO(num);
5851 for (;i < xn; i++) {
5853 if (num == 0)
goto num_is_zero_x;
5854 num += (BDIGIT_DBL)xds[i];
5855 zds[i] = BIGLO(num);
5858 for (; i < zn; i++) {
5860 if (num == 0)
goto num_is_zero_z;
5861 zds[i] = BIGLO(num);
5866 for (;i < xn; i++) {
5870 for (; i < zn; i++) {
5887 sign = (sign == BIGNUM_SIGN(y));
5888 if (BIGNUM_SIGN(x) != sign) {
5889 if (sign)
return bigsub(y, x);
5890 return bigsub(x, y);
5893 if (BIGNUM_LEN(x) > BIGNUM_LEN(y)) {
5894 len = BIGNUM_LEN(x) + 1;
5897 len = BIGNUM_LEN(y) + 1;
5899 z = bignew(
len, sign);
5901 bary_add(BDIGITS(z), BIGNUM_LEN(z),
5902 BDIGITS(x), BIGNUM_LEN(x),
5903 BDIGITS(y), BIGNUM_LEN(y));
5915 if ((n > 0) != BIGNUM_SIGN(x)) {
5919 return bigsub_int(x, n);
5924 return bigadd_int(x, n);
5926 else if (RB_BIGNUM_TYPE_P(y)) {
5927 return bignorm(bigadd(x, y, 1));
5944 if ((n > 0) != BIGNUM_SIGN(x)) {
5948 return bigadd_int(x, n);
5953 return bigsub_int(x, n);
5955 else if (RB_BIGNUM_TYPE_P(y)) {
5956 return bignorm(bigadd(x, y, 0));
5974 if (MUL_OVERFLOW_LONG_P(2, xn))
5975 rb_raise(rb_eArgError,
"square overflow");
5983 if (xn < NAIVE_MUL_DIGITS)
5984 bary_sq_fast(zds, zn, xds, xn);
5986 bary_mul(zds, zn, xds, xn, xds, xn);
5997 BDIGIT *xds, *yds, *zds;
6004 if (ADD_OVERFLOW_LONG_P(xn, yn))
6005 rb_raise(rb_eArgError,
"multiplication overflow");
6008 z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6014 bary_mul(zds, zn, xds, xn, yds, yn);
6027 else if (RB_BIGNUM_TYPE_P(y)) {
6036 return bignorm(bigmul0(x, y));
6042 long xn = BIGNUM_LEN(x), yn = BIGNUM_LEN(y);
6044 BDIGIT *xds, *yds, *zds;
6052 BARY_TRUNC(yds, yn);
6057 BARY_TRUNC(xds, xn);
6059 if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1])) {
6060 if (divp) *divp = rb_int2big(0);
6061 if (modp) *modp = x;
6066 z = bignew(xn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6068 dd = bigdivrem_single(zds, xds, xn, dd);
6070 *modp = rb_uint2big((uintptr_t)dd);
6071 BIGNUM_SET_SIGN(*modp, BIGNUM_SIGN(x));
6073 if (divp) *divp = z;
6076 if (xn == 2 && yn == 2) {
6077 BDIGIT_DBL x0 = bary2bdigitdbl(xds, 2);
6078 BDIGIT_DBL y0 = bary2bdigitdbl(yds, 2);
6079 BDIGIT_DBL q0 = x0 / y0;
6080 BDIGIT_DBL r0 = x0 % y0;
6082 z = bignew(bdigit_roomof(
sizeof(BDIGIT_DBL)), BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6085 zds[1] = BIGLO(BIGDN(q0));
6089 z = bignew(bdigit_roomof(
sizeof(BDIGIT_DBL)), BIGNUM_SIGN(x));
6092 zds[1] = BIGLO(BIGDN(r0));
6099 qn = xn + BIGDIVREM_EXTRA_WORDS;
6100 q = bignew(qn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y));
6110 r = bignew(rn, BIGNUM_SIGN(x));
6118 bary_divmod_branch(qds, qn, rds, rn, xds, xn, yds, yn);
6137 bigdivrem(x, y, divp, &mod);
6138 if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y) && !BIGZEROP(mod)) {
6139 if (divp) *divp = bigadd(*divp, rb_int2big(1), 0);
6140 if (modp) *modp = bigadd(mod, y, 1);
6156 else if (RB_BIGNUM_TYPE_P(y)) {
6160 double dx = rb_big2dbl(x);
6161 return rb_flo_div_flo(
DBL2NUM(dx), y);
6167 v = rb_big_divide(x, y,
'/');
6174 bigdivmod(x, y, &z, 0);
6182 return rb_big_divide(x, y,
'/');
6188 return rb_big_divide(x, y, idDiv);
6199 else if (!RB_BIGNUM_TYPE_P(y)) {
6202 bigdivmod(x, y, 0, &z);
6215 else if (!RB_BIGNUM_TYPE_P(y)) {
6218 bigdivrem(x, y, 0, &z);
6231 else if (!RB_BIGNUM_TYPE_P(y)) {
6234 bigdivmod(x, y, &div, &mod);
6240big_shift(
VALUE x,
long n)
6243 return big_lshift(x, 1+(
unsigned long)(-(n+1)));
6245 return big_rshift(x, (
unsigned long)n);
6249enum {DBL_BIGDIG = ((DBL_MANT_DIG + BITSPERDIG) / BITSPERDIG)};
6259 ex = l * BITSPERDIG - nlz(BDIGITS(x)[l-1]);
6260 ex -= 2 * DBL_BIGDIG * BITSPERDIG;
6261 if (ex > BITSPERDIG) ex -= BITSPERDIG;
6262 else if (ex > 0) ex = 0;
6263 if (ex) x = big_shift(x, ex);
6265 bigdivrem(x, y, &z, 0);
6267#if SIZEOF_LONG > SIZEOF_INT
6270 if (l > INT_MAX)
return HUGE_VAL;
6271 if (l < INT_MIN)
return 0.0;
6274 return ldexp(big2dbl(z), (
int)l);
6283 ey = l * BITSPERDIG - nlz(BDIGITS(y)[l-1]);
6284 ey -= DBL_BIGDIG * BITSPERDIG;
6285 if (ey) y = big_shift(y, ey);
6286 return big_fdiv(x, y, ey);
6293 y = dbl2big(ldexp(frexp(
RFLOAT_VALUE(y), &i), DBL_MANT_DIG));
6294 return big_fdiv(x, y, i - DBL_MANT_DIG);
6307 return big_fdiv_int(x, rb_int2big(
FIX2LONG(y)));
6309 else if (RB_BIGNUM_TYPE_P(y)) {
6310 return big_fdiv_int(x, y);
6317 return big_fdiv_float(x, y);
6335 if (y ==
INT2FIX(1))
return x;
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] & (((BDIGIT)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_bit_count(
VALUE big)
6988 if (BIGNUM_NEGATIVE_P(big))
6989 rb_raise(rb_eArgError,
"bit_count is undefined for negative integers");
6991 BDIGIT *ds = BDIGITS(big);
6992 size_t n = BIGNUM_LEN(big);
6996 count += rb_popcount64((uint64_t)ds[n]);
7003rb_big_odd_p(
VALUE num)
7005 return RBOOL(BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1);
7009rb_big_even_p(
VALUE num)
7011 if (BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1) {
7017unsigned long rb_ulong_isqrt(
unsigned long);
7018#if SIZEOF_BDIGIT*2 > SIZEOF_LONG
7019BDIGIT rb_bdigit_dbl_isqrt(BDIGIT_DBL);
7020# ifdef ULL_TO_DOUBLE
7021# define BDIGIT_DBL_TO_DOUBLE(n) ULL_TO_DOUBLE(n)
7024# define rb_bdigit_dbl_isqrt(x) (BDIGIT)rb_ulong_isqrt(x)
7026#ifndef BDIGIT_DBL_TO_DOUBLE
7027# define BDIGIT_DBL_TO_DOUBLE(n) (double)(n)
7031rb_big_isqrt(
VALUE n)
7033 BDIGIT *nds = BDIGITS(n);
7034 size_t len = BIGNUM_LEN(n);
7037 BDIGIT sq = rb_bdigit_dbl_isqrt(bary2bdigitdbl(nds,
len));
7038#if SIZEOF_BDIGIT > SIZEOF_LONG
7045 size_t shift =
FIX2LONG(rb_big_bit_length(n)) / 4;
7049 x = rb_int_plus(rb_int_lshift(x,
SIZET2NUM(shift - 1)), rb_int_idiv(rb_int_rshift(n,
SIZET2NUM(shift + 1)), x));
7050 VALUE xx = rb_int_mul(x, x);
7051 while (rb_int_gt(xx, n)) {
7052 xx = rb_int_minus(xx, rb_int_minus(rb_int_plus(x, x),
INT2FIX(1)));
7053 x = rb_int_minus(x,
INT2FIX(1));
7061bary_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)
7069 bdigits_to_mpz(x, xds, xn);
7070 bdigits_to_mpz(y, yds, yn);
7071 bdigits_to_mpz(m, mds, mn);
7072 mpz_powm(z, x, y, m);
7073 bdigits_from_mpz(z, zds, &count);
7074 BDIGITS_ZERO(zds+count, zn-count);
7087 size_t xn, yn, mn, zn;
7101 bary_powm_gmp(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, BDIGITS(m), mn);
7102 if (nega_flg && BIGNUM_POSITIVE_P(z) && !BIGZEROP(z)) {
7103 z = rb_big_minus(z, m);
7108 return rb_big_norm(z);
7114 if (
RTEST(rb_int_odd_p(y))) {
7115 tmp = rb_int_mul(tmp, x);
7116 tmp = rb_int_modulo(tmp, m);
7118 x = rb_int_mul(x, x);
7119 x = rb_int_modulo(x, m);
7121 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7123 tmp = rb_int_mul(tmp, x);
7124 tmp = rb_int_modulo(tmp, m);
7126 x = rb_int_mul(x, x);
7127 x = rb_int_modulo(x, m);
7130 if (nega_flg && rb_int_positive_p(tmp) && !rb_int_zero_p(tmp)) {
7131 tmp = rb_int_minus(tmp, m);
7142int_pow_tmp1(
VALUE x,
VALUE y,
long mm,
int nega_flg)
7149 if (
RTEST(rb_int_odd_p(y))) {
7150 tmp = (tmp * xx) % mm;
7152 xx = (xx * xx) % mm;
7154 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7156 tmp = (tmp * xx) % mm;
7158 xx = (xx * xx) % mm;
7161 if (nega_flg && tmp) {
7168int_pow_tmp2(
VALUE x,
VALUE y,
long mm,
int nega_flg)
7176# define MUL_MODULO(a, b, c) (long)(((DLONG)(a) * (DLONG)(b)) % (c))
7181# define MUL_MODULO(a, b, c) rb_int_modulo(rb_fix_mul_fix((a), (b)), (c))
7185 if (
RTEST(rb_int_odd_p(y))) {
7186 tmp2 = MUL_MODULO(tmp2, xx, m);
7188 xx = MUL_MODULO(xx, xx, m);
7190 for (yy =
FIX2LONG(y); yy; yy >>= 1L) {
7192 tmp2 = MUL_MODULO(tmp2, xx, m);
7194 xx = MUL_MODULO(xx, xx, m);
7202 if (nega_flg && tmp) {
7220rb_int_powm(
int const argc,
VALUE *
const argv,
VALUE const num)
7225 return rb_int_pow(num, argv[0]);
7228 VALUE const a = num;
7229 VALUE const b = argv[0];
7233 rb_raise(
rb_eTypeError,
"Integer#pow() 2nd argument not allowed unless a 1st argument is integer");
7235 if (rb_int_negative_p(b)) {
7236 rb_raise(
rb_eRangeError,
"Integer#pow() 1st argument cannot be negative when 2nd argument specified");
7239 rb_raise(
rb_eTypeError,
"Integer#pow() 2nd argument not allowed unless all arguments are integers");
7242 if (rb_int_zero_p(a) && !rb_int_zero_p(b)) {
7247 if (rb_int_negative_p(m)) {
7248 m = rb_int_uminus(m);
7253 long const half_val = (long)HALF_LONG_MSB;
7256 if (mm == 1)
return INT2FIX(0);
7257 if (mm <= half_val) {
7258 return int_pow_tmp1(rb_int_modulo(a, m), b, mm, nega_flg);
7261 return int_pow_tmp2(rb_int_modulo(a, m), b, mm, nega_flg);
7267 return int_pow_tmp3(rb_int_modulo(a, m), b, m, nega_flg);
7298 rb_define_const(
rb_cInteger,
"GMP_VERSION", rb_sprintf(
"GMP %s", gmp_version));
#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 NUM2SSIZET
Old name of RB_NUM2SSIZE.
#define RFLOAT_VALUE
Old name of rb_float_value.
#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 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_to_int(VALUE val)
Identical to rb_check_to_int(), except it raises in case of conversion mismatch.
#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.
VALUE rb_funcall(VALUE recv, ID mid, int n,...)
Calls a method.
VALUE rb_assoc_new(VALUE car, VALUE cdr)
Identical to rb_ary_new_from_values(), except it expects exactly two parameters.
#define RB_INT_PARSE_UNDERSCORE
Allows underscores between digits.
#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 RB_INT_PARSE_SIGN
Allows a leading sign (+ or -).
#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 RB_INT_PARSE_DEFAULT
Default flags (all features enabled).
#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 RB_INT_PARSE_PREFIX
Allows a base prefix (0x, 0b, 0o, 0d).
#define INTEGER_PACK_LSWORD_FIRST
Stores/interprets the least significant word as the first word.
static int rb_check_arity(int argc, int min, int max)
Ensures that the passed integer is in the passed range.
void rb_num_zerodiv(void)
Just always raises an exception.
VALUE rb_fix2str(VALUE val, int base)
Generates a place-value representation of the given Fixnum, with given radix.
VALUE rb_num_coerce_bit(VALUE lhs, VALUE rhs, ID op)
This one is optimised for bitwise operations, but the API is identical to rb_num_coerce_bin().
VALUE rb_num_coerce_relop(VALUE lhs, VALUE rhs, ID op)
Identical to rb_num_coerce_cmp(), except for return values.
VALUE rb_num_coerce_cmp(VALUE lhs, VALUE rhs, ID op)
Identical to rb_num_coerce_bin(), except for return values.
VALUE rb_num_coerce_bin(VALUE lhs, VALUE rhs, ID op)
Coerced binary operation.
VALUE rb_rational_raw(VALUE num, VALUE den)
Identical to rb_rational_new(), except it skips argument validations.
#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, rb_len_t len)
Overwrites the length of the string.
st_index_t rb_memhash(const void *ptr, rb_len_t len)
This is a universal hash function.
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.
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.
Defines RBIMPL_ATTR_NONSTRING.
#define RBIMPL_ATTR_NONSTRING()
Wraps (or simulates) __attribute__((nonstring)).
#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.
long rb_len_t
A signed integer type for lengths and indices of objects such as String and Array.
#define RB_LEN_MAX
Maximum possible value that a rb_len_t can take.
intptr_t SIGNED_VALUE
A signed integer type that has the same width with VALUE.
uintptr_t ID
Type that represents a Ruby identifier such as a variable name.
#define SIZEOF_VALUE
Identical to sizeof(VALUE), except it is a macro that can also be used inside of preprocessor directi...
uintptr_t VALUE
Type that represents a Ruby object.
static bool RB_FLOAT_TYPE_P(VALUE obj)
Queries if the object is an instance of rb_cFloat.
#define RBIMPL_WARNING_IGNORED(flag)
Suppresses a warning.
#define RBIMPL_WARNING_PUSH()
Pushes compiler warning state.
#define RBIMPL_WARNING_POP()
Pops compiler warning state.