Skip to content

Commit

Permalink
WIP: Fix range of Fixnum. Closes #3636.
Browse files Browse the repository at this point in the history
  • Loading branch information
@brixen
brixen committed Apr 24, 2016
1 parent 751335c commit 76fe600
Show file tree
Hide file tree
Showing 8 changed files with 147 additions and 71 deletions.
27 changes: 20 additions & 7 deletions machine/builtin/bignum.cpp
View file
Expand Up @@ -277,12 +277,19 @@ namespace rubinius {
}

Integer* Bignum::from(STATE, mp_int *num) {
if((size_t)mp_count_bits(num) <= FIXNUM_WIDTH) {
mp_clamp(num);

size_t bits = mp_count_bits(num);
bool neg = num->sign == MP_NEG;

if((neg && bits <= FIXNUM_MIN_WIDTH) || (!neg && bits <= FIXNUM_MAX_WIDTH)) {
unsigned long val = mp_get_long(num);
return num->sign == MP_NEG ? Fixnum::from(-val) : Fixnum::from(val);

return neg ? Fixnum::from(-val) : Fixnum::from(val);
} else {
Bignum* n_obj = Bignum::create(state);
mp_copy(XST, num, n_obj->mp_val());

return n_obj;
}
}
Expand Down Expand Up @@ -343,13 +350,19 @@ namespace rubinius {
}

Integer* Bignum::normalize(STATE, Bignum* b) {
mp_clamp(b->mp_val());
mp_int* num = b->mp_val();

mp_clamp(num);

if((size_t)mp_count_bits(b->mp_val()) <= FIXNUM_WIDTH) {
native_int val;
val = (native_int)b->to_native();
return Fixnum::from(val);
size_t bits = mp_count_bits(num);
bool neg = num->sign == MP_NEG;

if((neg && bits < FIXNUM_MIN_WIDTH) || (!neg && bits < FIXNUM_MAX_WIDTH)) {
unsigned long val = mp_get_long(num);

return neg ? Fixnum::from(-val) : Fixnum::from(val);
}

return b;
}

Expand Down
40 changes: 27 additions & 13 deletions machine/builtin/fixnum.cpp
View file
Expand Up @@ -321,14 +321,19 @@ namespace rubinius {
}

Integer* Fixnum::left_shift(STATE, Fixnum* bits) {
native_int self = to_native();
native_int shift = bits->to_native();

if(shift < 0) {
return right_shift(state, Fixnum::from(-shift));
}
shift = -shift;

native_int self = to_native();
if(shift >= (native_int)FIXNUM_WIDTH) {
return Bignum::from(state, self)->left_shift(state, bits);
if(shift <= FIXNUM_MAX) {
return right_shift(state, Fixnum::from(shift));
} else {
return Bignum::from(state, self)->right_shift(state, Bignum::from(state, shift));
}

return right_shift(state, Fixnum::from(-shift));
}

native_int answer = self << shift;
Expand All @@ -346,19 +351,26 @@ namespace rubinius {
}

Integer* Fixnum::right_shift(STATE, Fixnum* bits) {
native_int self = to_native();
native_int shift = bits->to_native();

if(shift < 0) {
return left_shift(state, Fixnum::from(-shift));
shift = -shift;

if(shift <= FIXNUM_MAX) {
return left_shift(state, Fixnum::from(shift));
} else {
return Bignum::from(state, self)->left_shift(state, Bignum::from(state, shift));
}
}

// boundary case. Don't overflow the bits back to their original
// value like C does, just say it's 0.
if(shift > (native_int)FIXNUM_WIDTH) {
if(to_native() >= 0) return Fixnum::from(0);
if(self > 0 && shift > FIXNUM_MAX_WIDTH) {
return Fixnum::from(0);
} else if(self < 0 && shift > FIXNUM_MIN_WIDTH) {
return Fixnum::from(-1);
}

return Fixnum::from(to_native() >> shift);
return Fixnum::from(self >> shift);
}

Integer* Fixnum::size(STATE) {
Expand Down Expand Up @@ -416,8 +428,10 @@ namespace rubinius {
static const char digitmap[] = "0123456789abcdefghijklmnopqrstuvwxyz";

String* Fixnum::to_s(STATE, Fixnum* base) {
// Base 2 fixnum with a minus sign and null byte is the maximum length
char buf[FIXNUM_WIDTH + 2];
/* The bit width of the smallest Fixnum plus the minus sign and null byte
* is the maximum length.
*/
char buf[FIXNUM_MIN_WIDTH + 2];
char *b = buf + sizeof(buf);
native_int j, k, m;

Expand Down
8 changes: 6 additions & 2 deletions machine/capi/integer.cpp
View file
Expand Up @@ -19,7 +19,11 @@ extern "C" {
size_t size = 0;

if(RB_TYPE_P(value, T_FIXNUM)) {
size = FIXNUM_WIDTH;
if(value > 0) {
size = FIXNUM_MAX_WIDTH;
} else {
size = FIXNUM_MIN_WIDTH;
}
} else if(RB_TYPE_P(value, T_BIGNUM)) {
Bignum* big = c_as<Bignum>(env->get_object(value));
size = big->size(env->state())->to_native();
Expand Down Expand Up @@ -57,7 +61,7 @@ extern "C" {

if(v == 0) return 0;

if((numbytes >= FIXNUM_WIDTH / 8) &&
if((numbytes >= FIXNUM_MIN_WIDTH / 8) &&
((flags & INTEGER_PACK_NATIVE_BYTE_ORDER) ||
#ifdef RBX_LITTLE_ENDIAN
((flags & INTEGER_PACK_LSWORD_FIRST) &&
Expand Down
8 changes: 5 additions & 3 deletions machine/include/capi/capi_oop.h
View file
Expand Up @@ -98,8 +98,10 @@

#define CAPI_TAG_FIXNUM(v) ((VALUE)(((VALUE)(v) << TAG_FIXNUM_SHIFT) | TAG_FIXNUM))

#define FIXNUM_WIDTH ((8 * sizeof(native_int)) - TAG_FIXNUM_SHIFT - 1)
#define FIXNUM_MAX (((native_int)1 << FIXNUM_WIDTH) - 1)
#define FIXNUM_MIN (-(FIXNUM_MAX))
#define FIXNUM_MAX_WIDTH ((8 * sizeof(native_int)) - TAG_FIXNUM_SHIFT - 1)
#define FIXNUM_MIN_WIDTH (FIXNUM_MAX_WIDTH + 1)

#define FIXNUM_MAX (((native_int)1 << FIXNUM_MAX_WIDTH) - 1)
#define FIXNUM_MIN (-(FIXNUM_MAX) - 1)

#endif
4 changes: 2 additions & 2 deletions machine/jit/llvm/inline_primitive.cpp
View file
Expand Up @@ -921,7 +921,7 @@ namespace rubinius {
Value* recv_int = ops.fixnum_strip(recv);
Value* shift_int = ops.fixnum_strip(shift);

Value* small_shift = ops.b().CreateICmpSLT(shift_int, ops.clong(FIXNUM_WIDTH), "small_shift");
Value* small_shift = ops.b().CreateICmpSLT(shift_int, ops.clong(FIXNUM_MAX_WIDTH), "small_shift");
ops.create_conditional_branch(left_shift, send, small_shift);

ops.set_block(left_shift);
Expand Down Expand Up @@ -980,7 +980,7 @@ namespace rubinius {
Value* recv_int = ops.fixnum_strip(recv);
Value* shift_int = ops.fixnum_strip(shift);

Value* small_shift = ops.b().CreateICmpSLT(shift_int, ops.clong(FIXNUM_WIDTH), "small_shift");
Value* small_shift = ops.b().CreateICmpSLT(shift_int, ops.clong(FIXNUM_MAX_WIDTH), "small_shift");
ops.create_conditional_branch(right_shift, zero, small_shift);

ops.set_block(right_shift);
Expand Down
4 changes: 2 additions & 2 deletions machine/jit/llvm/operations.hpp
View file
Expand Up @@ -1350,7 +1350,7 @@ namespace rubinius {
* should be the default fixnum mask for a positive number
*/
Value* fix_mask = ConstantInt::get(ctx_->IntPtrTy,
(1UL << (FIXNUM_WIDTH + 1)) | TAG_FIXNUM_MASK);
(1UL << (FIXNUM_MAX_WIDTH + 1)) | TAG_FIXNUM_MASK);
Value* fix_tag = ConstantInt::get(ctx_->IntPtrTy, TAG_FIXNUM);

Value* lint = cast_int(val);
Expand Down Expand Up @@ -1378,7 +1378,7 @@ namespace rubinius {
* should be the default fixnum mask for a positive number
*/
Value* fix_mask = ConstantInt::get(ctx_->IntPtrTy,
(1UL << (FIXNUM_WIDTH + 1)) | TAG_FIXNUM_MASK);
(1UL << (FIXNUM_MAX_WIDTH + 1)) | TAG_FIXNUM_MASK);
Value* fix_tag = ConstantInt::get(ctx_->IntPtrTy, TAG_FIXNUM);

Value* lint = cast_int(val);
Expand Down
16 changes: 5 additions & 11 deletions machine/oop.hpp
View file
Expand Up @@ -58,17 +58,11 @@ namespace rubinius {
#define __FIXNUM_P__(v) (((intptr_t)(v) & TAG_FIXNUM_MASK) == TAG_FIXNUM)
#define __SYMBOL_P__(v) (((intptr_t)(v) & TAG_SYMBOL_MASK) == TAG_SYMBOL)

/* How many bits of data are available in fixnum, not including the sign. */
#define FIXNUM_WIDTH ((8 * sizeof(native_int)) - TAG_FIXNUM_SHIFT - 1)
#define FIXNUM_MAX (((native_int)1 << FIXNUM_WIDTH) - 1)

/* This would naturally be (-(FIXNUM_MAX) - 1) considering the range of bits
* and how twos-complement works. However, the libtommath library used by
* Bignum does not store negative numbers in twos-complement. Consequently,
* this value of FIXNUM_MIN allows for checking that a value is in the Fixnum
* range merely by checking a count of the bits used to represent the number.
*/
#define FIXNUM_MIN (-(FIXNUM_MAX))
#define FIXNUM_MAX_WIDTH ((8 * sizeof(native_int)) - TAG_FIXNUM_SHIFT - 1)
#define FIXNUM_MIN_WIDTH (FIXNUM_MAX_WIDTH + 1)

#define FIXNUM_MAX (((native_int)1 << FIXNUM_MAX_WIDTH) - 1)
#define FIXNUM_MIN (-(FIXNUM_MAX) - 1)

/* Standard Rubinius Representation
*
Expand Down
111 changes: 80 additions & 31 deletions machine/test/test_bignum.hpp
View file
Expand Up @@ -633,60 +633,109 @@ class TestBignum : public CxxTest::TestSuite, public VMTest {
check_float(f, Float::create(state, -880872.999999925));
}

void test_left_shift() {
void test_positive_left_shift_positive() {
Bignum* one = Bignum::from(state, 1);

Fixnum* max_width = Fixnum::from(FIXNUM_MAX_WIDTH);
Integer* fix = one->left_shift(state, max_width);

TS_ASSERT(kind_of<Fixnum>(fix));
TS_ASSERT_EQUALS(1L << (FIXNUM_MAX_WIDTH), fix->to_native());

Integer* max_plus1 = one->left_shift(state, max_width+1);

TS_ASSERT(kind_of<Bignum>(max_plus1));
TS_ASSERT_EQUALS(FIXNUM_MAX + 1, max_plus1->to_native());
}

void test_positive_left_shift_negative() {
Bignum* max_plus1 = Bignum::from(state, FIXNUM_MAX+1);
Fixnum* neg_one = Fixnum::from(-1);

Integer* val = max_plus1->left_shift(state, neg_one);

TS_ASSERT(kind_of<Fixnum>(val));
TS_ASSERT_EQUALS(1L << (FIXNUM_MAX_WIDTH), val->to_native());
}

void test_negative_left_shift_positive() {
Bignum* neg_one = Bignum::from(state, -1);
Fixnum* min_width = Fixnum::from(FIXNUM_MIN_WIDTH);

Fixnum* width_minus1 = Fixnum::from(FIXNUM_WIDTH-1);
Fixnum* width = Fixnum::from(FIXNUM_WIDTH);
Integer* val = neg_one->left_shift(state, min_width);

Integer* fix = one->left_shift(state, width_minus1);
TS_ASSERT(kind_of<Fixnum>(val));
TS_ASSERT_EQUALS((0UL - 1L) << (FIXNUM_MIN_WIDTH), val->to_native());

TS_ASSERT(kind_of<Fixnum>(fix));
TS_ASSERT_EQUALS(1L << (FIXNUM_WIDTH-1), fix->to_native());
val = neg_one->left_shift(state, min_width+1);

fix = neg_one->left_shift(state, width_minus1);
TS_ASSERT(kind_of<Bignum>(val));
TS_ASSERT_EQUALS(FIXNUM_MIN-1, val->to_native());
}

TS_ASSERT(kind_of<Fixnum>(fix));
TS_ASSERT_EQUALS((0UL - 1L) << (FIXNUM_WIDTH-1), fix->to_native());
void test_negative_left_shift_negative() {
Fixnum* neg_one = Fixnum::from(-1);
Bignum* min_minus1 = Bignum::from(state, FIXNUM_MIN-1);

Integer* max_plus1 = one->left_shift(state, width);
Integer* val = min_minus1->left_shift(state, neg_one);

TS_ASSERT(kind_of<Bignum>(max_plus1));
TS_ASSERT_EQUALS(FIXNUM_MAX + 1, max_plus1->to_native());
TS_ASSERT(kind_of<Fixnum>(val));
TS_ASSERT_EQUALS((0UL - 1L) << (FIXNUM_MIN_WIDTH), val->to_native());
}

void test_positive_right_shift_positive() {
Fixnum* one = Fixnum::from(1);

Integer* min_minus1 = neg_one->left_shift(state, width);
Bignum* max_plus1 = Bignum::from(state, FIXNUM_MAX+1);
Integer* val = max_plus1->right_shift(state, one);

TS_ASSERT(kind_of<Bignum>(min_minus1));
TS_ASSERT_EQUALS(FIXNUM_MIN - 1, min_minus1->to_native());
TS_ASSERT(kind_of<Fixnum>(val));
TS_ASSERT_EQUALS(1L << (FIXNUM_MAX_WIDTH), val->to_native());
}

void test_right_shift() {
void test_positive_right_shift_negative() {
Fixnum* neg_one = Fixnum::from(-1);

Bignum* big = Bignum::from(state, 1L << FIXNUM_MAX_WIDTH);
Integer* val = big->right_shift(state, neg_one);

TS_ASSERT(kind_of<Bignum>(val));
TS_ASSERT_EQUALS(FIXNUM_MAX+1, val->to_native());

Bignum* one = Bignum::from(state, 1);
Bignum* neg_one = Bignum::from(state, -1);
Fixnum* neg_max_width = Fixnum::from(FIXNUM_MAX_WIDTH);

Fixnum* neg_width_minus1 = Fixnum::from(-(FIXNUM_WIDTH-1));
Fixnum* neg_width = Fixnum::from(-FIXNUM_WIDTH);
val = one->right_shift(state, neg_max_width);

Integer* fix = one->right_shift(state, neg_width_minus1);
TS_ASSERT(kind_of<Fixnum>(val));
TS_ASSERT_EQUALS(1L << FIXNUM_MAX_WIDTH, val->to_native());
}

TS_ASSERT(kind_of<Fixnum>(fix));
TS_ASSERT_EQUALS(1L << (FIXNUM_WIDTH-1), fix->to_native());
void test_negative_right_shift_positive() {
Bignum* min_minus1 = Bignum::from(state, FIXNUM_MIN-1);
Fixnum* one = Fixnum::from(1);

fix = neg_one->right_shift(state, neg_width_minus1);
Integer* val = min_minus1->right_shift(state, one);

TS_ASSERT(kind_of<Fixnum>(fix));
TS_ASSERT_EQUALS((0UL - 1L) << (FIXNUM_WIDTH-1), fix->to_native());
TS_ASSERT(kind_of<Fixnum>(val));
TS_ASSERT_EQUALS((0UL - 1L) << FIXNUM_MIN_WIDTH, val->to_native());
}

Integer* max_plus1 = one->right_shift(state, neg_width);
void test_negative_right_shift_negative() {
Bignum* neg_one = Bignum::from(state, -1);
Fixnum* neg_min_width = Fixnum::from(-FIXNUM_MIN_WIDTH);

TS_ASSERT(kind_of<Bignum>(max_plus1));
TS_ASSERT_EQUALS(FIXNUM_MAX + 1, max_plus1->to_native());
Integer* val = neg_one->right_shift(state, neg_min_width);

Integer* min_minus1 = neg_one->right_shift(state, neg_width);
TS_ASSERT(kind_of<Fixnum>(val));
TS_ASSERT_EQUALS((0UL - 1L) << FIXNUM_MIN_WIDTH, val->to_native());

TS_ASSERT(kind_of<Bignum>(min_minus1));
TS_ASSERT_EQUALS(FIXNUM_MIN - 1, min_minus1->to_native());
Fixnum* neg_min_width_plus1 = Fixnum::from(-(FIXNUM_MIN_WIDTH+1));

val = neg_one->right_shift(state, neg_min_width_plus1);

TS_ASSERT(kind_of<Bignum>(val));
TS_ASSERT_EQUALS(FIXNUM_MIN-1, val->to_native());
}

void test_pow() {
Expand Down

0 comments on commit 76fe600

Please sign in to comment.