#include "ruby.h"

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

static VALUE zero = INT2NUM(0);
static VALUE one = INT2NUM(1);

static VALUE c_mod_pow(VALUE self, VALUE exp, VALUE mod){

  VALUE result = one;
  VALUE base = self;

  VALUE base_square;
  VALUE result_base;

  while( NUM2INT(rb_big_cmp(TO_BIGNUM(exp), zero)) > 0 ){

    if ( rb_num2int(rb_big_and(TO_BIGNUM(exp), one)) ){
     result_base = rb_big_mul(TO_BIGNUM(result), base);
     result = rb_big_modulo(TO_BIGNUM(result_base), mod);
    }

    exp = rb_big_rshift(TO_BIGNUM(exp), one);
    base_square = rb_big_mul(TO_BIGNUM(base), base);
    base = rb_big_modulo(TO_BIGNUM(base_square), mod);
  }

  return result;
}

void Init_mod_pow(){
  rb_define_method(rb_cInteger, "mod_pow", c_mod_pow, 2);
}