Ruby native C big integer segfault

Question

I'm working on a Ruby native C method: power mod. Here's what I got:

#define TO_BIGNUM(x) (FIXNUM_P(x) ? rb_int2big(FIX2LONG(x)) : x)
#define CONST2BIGNUM(x) (TO_BIGNUM(INT2NUM(x)))

VALUE method_big_power_mod(VALUE self, VALUE base, VALUE exp, VALUE mod){
  VALUE res = TO_BIGNUM(INT2NUM(1));

  base = TO_BIGNUM(base);
  exp = TO_BIGNUM(exp);
  mod = TO_BIGNUM(mod);

  while (rb_big_cmp(exp, CONST2BIGNUM(0))) {
    if (rb_big_modulo(exp, CONST2BIGNUM(2))) {
      VALUE mul = rb_big_mul(res, base);
      res = rb_big_modulo(mul, mod);
    }
    base = rb_big_modulo(rb_big_pow(base, CONST2BIGNUM(2)), mod);
    exp = rb_big_div(exp, CONST2BIGNUM(2));
  }

  return res;
}

It segfaults every time. I isolated the problem to rb_big_modulo calls. gdb stacktrace says that it crashes in the bigdivrem method after calling rb_big_modulo. I tried to look through the source of bignum.c, but I can't figure out what's causing the crash. Am I doing something wrong?

Answer 1

There are two problems that are causing the segfault:

1 - The functions rb_big_* sometimes doesn't return a Bignum object, but when you call then the first arg must be a Bignum object. For example:

if (rb_big_modulo(exp, CONST2BIGNUM(2))) {
  VALUE mul = rb_big_mul(res, base); // This maybe return a Fixnum 
  res = rb_big_modulo(mul, mod); // This will cause a segfault :(
}

2 - The function rb_big_pow when you call it with both args Bignum, it will warn you and will return a Float object where you can't convert easily to a Bignum object. So, you should replace the line where you call it by:

VALUE x = TO_BIGNUM(rb_big_pow(base, INT2NUM(2))); // Power by a Fixnum instead a Bignum
base = TO_BIGNUM(rb_big_modulo(x , mod));

The final implementation will be:

#define TO_BIGNUM(x) (FIXNUM_P(x) ? rb_int2big(FIX2LONG(x)) : x)
#define CONST2BIGNUM(x) (TO_BIGNUM(INT2NUM(x)))

VALUE method_big_power_mod(VALUE self, VALUE base, VALUE exp, VALUE mod){
  VALUE res = TO_BIGNUM(INT2NUM(1));

  base = TO_BIGNUM(base);
  exp = TO_BIGNUM(exp);
  mod = TO_BIGNUM(mod);

  while (rb_big_cmp(exp, CONST2BIGNUM(0))) {
    if (rb_big_modulo(exp, CONST2BIGNUM(2))) {
      VALUE mul = TO_BIGNUM(rb_big_mul(res, base));
      res = TO_BIGNUM(rb_big_modulo(mul, mod));
    }
    VALUE x = TO_BIGNUM(rb_big_pow(base, INT2NUM(2)));

    base = TO_BIGNUM(rb_big_modulo(x , mod));
    exp = TO_BIGNUM(rb_big_div(exp, CONST2BIGNUM(2)));
  }

  return res;
}

I don't know the performance impact with all these conversions. Maybe, you should test when it is a Fixnum or a Bignumand calculate it using the proper function or benchmark both approaches.

When I ran it, I went thought an infinite loop, but I don't know if I call it with the correct values.