summaryrefslogtreecommitdiff
path: root/bignum.c
diff options
context:
space:
mode:
Diffstat (limited to 'bignum.c')
-rw-r--r--bignum.c178
1 files changed, 141 insertions, 37 deletions
diff --git a/bignum.c b/bignum.c
index 2e135caf20..28924b4eb9 100644
--- a/bignum.c
+++ b/bignum.c
@@ -64,6 +64,21 @@ static const bool debug_integer_pack = (
const char ruby_digitmap[] = "0123456789abcdefghijklmnopqrstuvwxyz";
+/* Two-digit decimal lookup table. Offset 2*n holds the ASCII pair for
+ * n in the range 0..99. Used by both rb_fix2str in numeric.c and
+ * big2str_2bdigits below to emit two base-10 digits per iteration. */
+const char ruby_decimal_digit_pairs[201] =
+ "00010203040506070809"
+ "10111213141516171819"
+ "20212223242526272829"
+ "30313233343536373839"
+ "40414243444546474849"
+ "50515253545556575859"
+ "60616263646566676869"
+ "70717273747576777879"
+ "80818283848586878889"
+ "90919293949596979899";
+
#ifndef SIZEOF_BDIGIT_DBL
# if SIZEOF_INT*2 <= SIZEOF_LONG_LONG
# define SIZEOF_BDIGIT_DBL SIZEOF_LONG_LONG
@@ -79,7 +94,6 @@ STATIC_ASSERT(sizeof_bdigit_and_dbl, SIZEOF_BDIGIT*2 <= SIZEOF_BDIGIT_DBL);
STATIC_ASSERT(bdigit_signedness, 0 < (BDIGIT)-1);
STATIC_ASSERT(bdigit_dbl_signedness, 0 < (BDIGIT_DBL)-1);
STATIC_ASSERT(bdigit_dbl_signed_signedness, 0 > (BDIGIT_DBL_SIGNED)-1);
-STATIC_ASSERT(rbignum_embed_len_max, BIGNUM_EMBED_LEN_MAX <= (BIGNUM_EMBED_LEN_MASK >> BIGNUM_EMBED_LEN_SHIFT));
#if SIZEOF_BDIGIT < SIZEOF_LONG
STATIC_ASSERT(sizeof_long_and_sizeof_bdigit, SIZEOF_LONG % SIZEOF_BDIGIT == 0);
@@ -2944,11 +2958,6 @@ bary_divmod(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT *xds, s
}
}
-
-#ifndef BIGNUM_DEBUG
-# define BIGNUM_DEBUG (0+RUBY_DEBUG)
-#endif
-
static int
bigzero_p(VALUE x)
{
@@ -2965,7 +2974,7 @@ int
rb_cmpint(VALUE val, VALUE a, VALUE b)
{
if (NIL_P(val)) {
- rb_cmperr(a, b);
+ rb_cmperr_reason(a, b, "comparator returned nil");
}
if (FIXNUM_P(val)) {
long l = FIX2LONG(val);
@@ -2990,36 +2999,68 @@ rb_cmpint(VALUE val, VALUE a, VALUE b)
((l) << BIGNUM_EMBED_LEN_SHIFT)) : \
(void)(RBIGNUM(b)->as.heap.len = (l)))
+static size_t
+big_embed_capa(VALUE big)
+{
+ size_t size = rb_gc_obj_slot_size(big) - offsetof(struct RBignum, as.ary);
+ RUBY_ASSERT(size % sizeof(BDIGIT) == 0);
+ size_t capa = size / sizeof(BDIGIT);
+ RUBY_ASSERT(capa <= BIGNUM_EMBED_LEN_MAX);
+ return capa;
+}
+
+static size_t
+big_embed_size(size_t capa)
+{
+ size_t size = offsetof(struct RBignum, as.ary) + (sizeof(BDIGIT) * capa);
+ if (size < sizeof(struct RBignum)) {
+ size = sizeof(struct RBignum);
+ }
+ return size;
+}
+
+static bool
+big_embeddable_p(size_t capa)
+{
+ if (capa > BIGNUM_EMBED_LEN_MAX) {
+ return false;
+ }
+ return rb_gc_size_allocatable_p(big_embed_size(capa));
+}
+
static void
rb_big_realloc(VALUE big, size_t len)
{
BDIGIT *ds;
+ size_t embed_capa = big_embed_capa(big);
+
if (BIGNUM_EMBED_P(big)) {
- if (BIGNUM_EMBED_LEN_MAX < len) {
+ if (embed_capa < len) {
ds = ALLOC_N(BDIGIT, len);
- MEMCPY(ds, RBIGNUM(big)->as.ary, BDIGIT, BIGNUM_EMBED_LEN_MAX);
+ MEMCPY(ds, RBIGNUM(big)->as.ary, BDIGIT, embed_capa);
RBIGNUM(big)->as.heap.len = BIGNUM_LEN(big);
RBIGNUM(big)->as.heap.digits = ds;
FL_UNSET_RAW(big, BIGNUM_EMBED_FLAG);
}
}
else {
- if (len <= BIGNUM_EMBED_LEN_MAX) {
+ if (len <= embed_capa) {
ds = RBIGNUM(big)->as.heap.digits;
+ size_t old_len = RBIGNUM(big)->as.heap.len;
FL_SET_RAW(big, BIGNUM_EMBED_FLAG);
BIGNUM_SET_LEN(big, len);
- (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)RBIGNUM(big)->as.ary, sizeof(RBIGNUM(big)->as.ary));
+ (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)RBIGNUM(big)->as.ary, embed_capa * sizeof(BDIGIT));
if (ds) {
MEMCPY(RBIGNUM(big)->as.ary, ds, BDIGIT, len);
- xfree(ds);
+ SIZED_FREE_N(ds, old_len);
}
}
else {
if (BIGNUM_LEN(big) == 0) {
RBIGNUM(big)->as.heap.digits = ALLOC_N(BDIGIT, len);
}
- else {
- REALLOC_N(RBIGNUM(big)->as.heap.digits, BDIGIT, len);
+ else if (BIGNUM_LEN(big) != len) {
+ SIZED_REALLOC_N(RBIGNUM(big)->as.heap.digits, BDIGIT, len, BIGNUM_LEN(big));
}
}
}
@@ -3035,16 +3076,21 @@ rb_big_resize(VALUE big, size_t len)
static VALUE
bignew_1(VALUE klass, size_t len, int sign)
{
- NEWOBJ_OF(big, struct RBignum, klass,
- T_BIGNUM | (RGENGC_WB_PROTECTED_BIGNUM ? FL_WB_PROTECTED : 0), sizeof(struct RBignum), 0);
- VALUE bigv = (VALUE)big;
- BIGNUM_SET_SIGN(bigv, sign);
- if (len <= BIGNUM_EMBED_LEN_MAX) {
- FL_SET_RAW(bigv, BIGNUM_EMBED_FLAG);
+ VALUE bigv;
+
+ if (big_embeddable_p(len)) {
+ size_t size = big_embed_size(len);
+ RUBY_ASSERT(rb_gc_size_allocatable_p(size));
+ NEWOBJ_OF(big, struct RBignum, klass, T_BIGNUM | BIGNUM_EMBED_FLAG, size);
+ bigv = (VALUE)big;
+ BIGNUM_SET_SIGN(bigv, sign);
BIGNUM_SET_LEN(bigv, len);
- (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)big->as.ary, sizeof(big->as.ary));
+ (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)big->as.ary, len * sizeof(BDIGIT));
}
else {
+ NEWOBJ_OF(big, struct RBignum, klass, T_BIGNUM, sizeof(struct RBignum));
+ bigv = (VALUE)big;
+ BIGNUM_SET_SIGN(bigv, sign);
big->as.heap.digits = ALLOC_N(BDIGIT, len);
big->as.heap.len = len;
}
@@ -3055,7 +3101,9 @@ bignew_1(VALUE klass, size_t len, int sign)
VALUE
rb_big_new(size_t len, int sign)
{
- return bignew(len, sign != 0);
+ VALUE obj = bignew(len, sign != 0);
+ memset(BIGNUM_DIGITS(obj), 0, len * sizeof(BDIGIT));
+ return obj;
}
VALUE
@@ -4475,7 +4523,7 @@ rb_str2big_gmp(VALUE arg, int base, int badcheck)
#if HAVE_LONG_LONG
-static VALUE
+VALUE
rb_ull2big(unsigned LONG_LONG n)
{
long i;
@@ -4497,7 +4545,7 @@ rb_ull2big(unsigned LONG_LONG n)
return big;
}
-static VALUE
+VALUE
rb_ll2big(LONG_LONG n)
{
long neg = 0;
@@ -4535,7 +4583,7 @@ rb_ll2inum(LONG_LONG n)
#endif /* HAVE_LONG_LONG */
#ifdef HAVE_INT128_T
-static VALUE
+VALUE
rb_uint128t2big(uint128_t n)
{
long i;
@@ -4778,11 +4826,34 @@ big2str_2bdigits(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t tail
return;
p = buf;
j = sizeof(buf);
- do {
- BDIGIT_DBL idx = num % b2s->base;
- num /= b2s->base;
- p[--j] = ruby_digitmap[idx];
- } while (num);
+ if (b2s->base == 10) {
+ /* Emit two decimal digits per iteration from ruby_decimal_digit_pairs.
+ * See the comment on the table in bignum.c near ruby_digitmap. */
+ while (num >= 100) {
+ BDIGIT_DBL idx = (num % 100) * 2;
+ num /= 100;
+ j -= 2;
+ p[j] = ruby_decimal_digit_pairs[idx];
+ p[j + 1] = ruby_decimal_digit_pairs[idx + 1];
+ }
+ if (num >= 10) {
+ BDIGIT_DBL idx = num * 2;
+ j -= 2;
+ p[j] = ruby_decimal_digit_pairs[idx];
+ p[j + 1] = ruby_decimal_digit_pairs[idx + 1];
+ }
+ else {
+ /* num is 1..9 here (0 was handled above) */
+ p[--j] = (char)('0' + num);
+ }
+ }
+ else {
+ do {
+ BDIGIT_DBL idx = num % b2s->base;
+ num /= b2s->base;
+ p[--j] = ruby_digitmap[idx];
+ } while (num);
+ }
len = sizeof(buf) - j;
big2str_alloc(b2s, len + taillen);
MEMCPY(b2s->ptr, buf + j, char, len);
@@ -4790,11 +4861,39 @@ big2str_2bdigits(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t tail
else {
p = b2s->ptr;
j = b2s->hbase2_numdigits;
- do {
- BDIGIT_DBL idx = num % b2s->base;
- num /= b2s->base;
- p[--j] = ruby_digitmap[idx];
- } while (j);
+ if (b2s->base == 10) {
+ /* Non-beginning chunks must emit EXACTLY hbase2_numdigits,
+ * zero-padded on the left. Consume num in 2-digit groups,
+ * handle the odd trailing digit, then memset remaining
+ * positions with '0'. */
+ while (num >= 100) {
+ BDIGIT_DBL idx = (num % 100) * 2;
+ num /= 100;
+ j -= 2;
+ p[j] = ruby_decimal_digit_pairs[idx];
+ p[j + 1] = ruby_decimal_digit_pairs[idx + 1];
+ }
+ if (num >= 10) {
+ BDIGIT_DBL idx = num * 2;
+ j -= 2;
+ p[j] = ruby_decimal_digit_pairs[idx];
+ p[j + 1] = ruby_decimal_digit_pairs[idx + 1];
+ }
+ else if (num > 0) {
+ p[--j] = (char)('0' + num);
+ }
+ if (j > 0) {
+ memset(p, '0', j);
+ j = 0;
+ }
+ }
+ else {
+ do {
+ BDIGIT_DBL idx = num % b2s->base;
+ num /= b2s->base;
+ p[--j] = ruby_digitmap[idx];
+ } while (j);
+ }
len = b2s->hbase2_numdigits;
}
b2s->ptr += len;
@@ -7030,7 +7129,7 @@ int_pow_tmp3(VALUE x, VALUE y, VALUE m, int nega_flg)
zn = mn;
z = bignew(zn, 1);
bary_powm_gmp(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, BDIGITS(m), mn);
- if (nega_flg & BIGNUM_POSITIVE_P(z)) {
+ if (nega_flg && BIGNUM_POSITIVE_P(z) && !BIGZEROP(z)) {
z = rb_big_minus(z, m);
}
RB_GC_GUARD(x);
@@ -7058,7 +7157,7 @@ int_pow_tmp3(VALUE x, VALUE y, VALUE m, int nega_flg)
x = rb_int_modulo(x, m);
}
- if (nega_flg && rb_int_positive_p(tmp)) {
+ if (nega_flg && rb_int_positive_p(tmp) && !rb_int_zero_p(tmp)) {
tmp = rb_int_minus(tmp, m);
}
return tmp;
@@ -7170,6 +7269,11 @@ rb_int_powm(int const argc, VALUE * const argv, VALUE const num)
rb_raise(rb_eTypeError, "Integer#pow() 2nd argument not allowed unless all arguments are integers");
}
+ if (rb_int_zero_p(a) && !rb_int_zero_p(b)) {
+ /* shortcut; 0**x => 0 except for x == 0 */
+ return INT2FIX(0);
+ }
+
if (rb_int_negative_p(m)) {
m = rb_int_uminus(m);
nega_flg = 1;
generated by cgit v1.2.3 (git 2.25.1) at 2026-06-06 20:51:26 +0000