Skip to content

Commit 76fe600

Browse files
brixenbrixen
committedApr 24, 2016
WIP: Fix range of Fixnum. Closes #3636.
·
v5.0v3.91
1 parent 751335c commit 76fe600

File tree

8 files changed

+147
-71
lines changed

8 files changed

+147
-71
lines changed
 

‎machine/builtin/bignum.cpp

+20-7
Original file line numberDiff line numberDiff line change
@@ -277,12 +277,19 @@ namespace rubinius {
277277
}
278278

279279
Integer* Bignum::from(STATE, mp_int *num) {
280-
if((size_t)mp_count_bits(num) <= FIXNUM_WIDTH) {
280+
mp_clamp(num);
281+
282+
size_t bits = mp_count_bits(num);
283+
bool neg = num->sign == MP_NEG;
284+
285+
if((neg && bits <= FIXNUM_MIN_WIDTH) || (!neg && bits <= FIXNUM_MAX_WIDTH)) {
281286
unsigned long val = mp_get_long(num);
282-
return num->sign == MP_NEG ? Fixnum::from(-val) : Fixnum::from(val);
287+
288+
return neg ? Fixnum::from(-val) : Fixnum::from(val);
283289
} else {
284290
Bignum* n_obj = Bignum::create(state);
285291
mp_copy(XST, num, n_obj->mp_val());
292+
286293
return n_obj;
287294
}
288295
}
@@ -343,13 +350,19 @@ namespace rubinius {
343350
}
344351

345352
Integer* Bignum::normalize(STATE, Bignum* b) {
346-
mp_clamp(b->mp_val());
353+
mp_int* num = b->mp_val();
354+
355+
mp_clamp(num);
347356

348-
if((size_t)mp_count_bits(b->mp_val()) <= FIXNUM_WIDTH) {
349-
native_int val;
350-
val = (native_int)b->to_native();
351-
return Fixnum::from(val);
357+
size_t bits = mp_count_bits(num);
358+
bool neg = num->sign == MP_NEG;
359+
360+
if((neg && bits < FIXNUM_MIN_WIDTH) || (!neg && bits < FIXNUM_MAX_WIDTH)) {
361+
unsigned long val = mp_get_long(num);
362+
363+
return neg ? Fixnum::from(-val) : Fixnum::from(val);
352364
}
365+
353366
return b;
354367
}
355368

‎machine/builtin/fixnum.cpp

+27-13
Original file line numberDiff line numberDiff line change
@@ -321,14 +321,19 @@ namespace rubinius {
321321
}
322322

323323
Integer* Fixnum::left_shift(STATE, Fixnum* bits) {
324+
native_int self = to_native();
324325
native_int shift = bits->to_native();
326+
325327
if(shift < 0) {
326-
return right_shift(state, Fixnum::from(-shift));
327-
}
328+
shift = -shift;
328329

329-
native_int self = to_native();
330-
if(shift >= (native_int)FIXNUM_WIDTH) {
331-
return Bignum::from(state, self)->left_shift(state, bits);
330+
if(shift <= FIXNUM_MAX) {
331+
return right_shift(state, Fixnum::from(shift));
332+
} else {
333+
return Bignum::from(state, self)->right_shift(state, Bignum::from(state, shift));
334+
}
335+
336+
return right_shift(state, Fixnum::from(-shift));
332337
}
333338

334339
native_int answer = self << shift;
@@ -346,19 +351,26 @@ namespace rubinius {
346351
}
347352

348353
Integer* Fixnum::right_shift(STATE, Fixnum* bits) {
354+
native_int self = to_native();
349355
native_int shift = bits->to_native();
356+
350357
if(shift < 0) {
351-
return left_shift(state, Fixnum::from(-shift));
358+
shift = -shift;
359+
360+
if(shift <= FIXNUM_MAX) {
361+
return left_shift(state, Fixnum::from(shift));
362+
} else {
363+
return Bignum::from(state, self)->left_shift(state, Bignum::from(state, shift));
364+
}
352365
}
353366

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

361-
return Fixnum::from(to_native() >> shift);
373+
return Fixnum::from(self >> shift);
362374
}
363375

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

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

‎machine/capi/integer.cpp

+6-2
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,11 @@ extern "C" {
1919
size_t size = 0;
2020

2121
if(RB_TYPE_P(value, T_FIXNUM)) {
22-
size = FIXNUM_WIDTH;
22+
if(value > 0) {
23+
size = FIXNUM_MAX_WIDTH;
24+
} else {
25+
size = FIXNUM_MIN_WIDTH;
26+
}
2327
} else if(RB_TYPE_P(value, T_BIGNUM)) {
2428
Bignum* big = c_as<Bignum>(env->get_object(value));
2529
size = big->size(env->state())->to_native();
@@ -57,7 +61,7 @@ extern "C" {
5761

5862
if(v == 0) return 0;
5963

60-
if((numbytes >= FIXNUM_WIDTH / 8) &&
64+
if((numbytes >= FIXNUM_MIN_WIDTH / 8) &&
6165
((flags & INTEGER_PACK_NATIVE_BYTE_ORDER) ||
6266
#ifdef RBX_LITTLE_ENDIAN
6367
((flags & INTEGER_PACK_LSWORD_FIRST) &&

‎machine/include/capi/capi_oop.h

+5-3
Original file line numberDiff line numberDiff line change
@@ -98,8 +98,10 @@
9898

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

101-
#define FIXNUM_WIDTH ((8 * sizeof(native_int)) - TAG_FIXNUM_SHIFT - 1)
102-
#define FIXNUM_MAX (((native_int)1 << FIXNUM_WIDTH) - 1)
103-
#define FIXNUM_MIN (-(FIXNUM_MAX))
101+
#define FIXNUM_MAX_WIDTH ((8 * sizeof(native_int)) - TAG_FIXNUM_SHIFT - 1)
102+
#define FIXNUM_MIN_WIDTH (FIXNUM_MAX_WIDTH + 1)
103+
104+
#define FIXNUM_MAX (((native_int)1 << FIXNUM_MAX_WIDTH) - 1)
105+
#define FIXNUM_MIN (-(FIXNUM_MAX) - 1)
104106

105107
#endif

‎machine/jit/llvm/inline_primitive.cpp

+2-2
Original file line numberDiff line numberDiff line change
@@ -921,7 +921,7 @@ namespace rubinius {
921921
Value* recv_int = ops.fixnum_strip(recv);
922922
Value* shift_int = ops.fixnum_strip(shift);
923923

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

927927
ops.set_block(left_shift);
@@ -980,7 +980,7 @@ namespace rubinius {
980980
Value* recv_int = ops.fixnum_strip(recv);
981981
Value* shift_int = ops.fixnum_strip(shift);
982982

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

986986
ops.set_block(right_shift);

‎machine/jit/llvm/operations.hpp

+2-2
Original file line numberDiff line numberDiff line change
@@ -1350,7 +1350,7 @@ namespace rubinius {
13501350
* should be the default fixnum mask for a positive number
13511351
*/
13521352
Value* fix_mask = ConstantInt::get(ctx_->IntPtrTy,
1353-
(1UL << (FIXNUM_WIDTH + 1)) | TAG_FIXNUM_MASK);
1353+
(1UL << (FIXNUM_MAX_WIDTH + 1)) | TAG_FIXNUM_MASK);
13541354
Value* fix_tag = ConstantInt::get(ctx_->IntPtrTy, TAG_FIXNUM);
13551355

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

13841384
Value* lint = cast_int(val);

‎machine/oop.hpp

+5-11
Original file line numberDiff line numberDiff line change
@@ -58,17 +58,11 @@ namespace rubinius {
5858
#define __FIXNUM_P__(v) (((intptr_t)(v) & TAG_FIXNUM_MASK) == TAG_FIXNUM)
5959
#define __SYMBOL_P__(v) (((intptr_t)(v) & TAG_SYMBOL_MASK) == TAG_SYMBOL)
6060

61-
/* How many bits of data are available in fixnum, not including the sign. */
62-
#define FIXNUM_WIDTH ((8 * sizeof(native_int)) - TAG_FIXNUM_SHIFT - 1)
63-
#define FIXNUM_MAX (((native_int)1 << FIXNUM_WIDTH) - 1)
64-
65-
/* This would naturally be (-(FIXNUM_MAX) - 1) considering the range of bits
66-
* and how twos-complement works. However, the libtommath library used by
67-
* Bignum does not store negative numbers in twos-complement. Consequently,
68-
* this value of FIXNUM_MIN allows for checking that a value is in the Fixnum
69-
* range merely by checking a count of the bits used to represent the number.
70-
*/
71-
#define FIXNUM_MIN (-(FIXNUM_MAX))
61+
#define FIXNUM_MAX_WIDTH ((8 * sizeof(native_int)) - TAG_FIXNUM_SHIFT - 1)
62+
#define FIXNUM_MIN_WIDTH (FIXNUM_MAX_WIDTH + 1)
63+
64+
#define FIXNUM_MAX (((native_int)1 << FIXNUM_MAX_WIDTH) - 1)
65+
#define FIXNUM_MIN (-(FIXNUM_MAX) - 1)
7266

7367
/* Standard Rubinius Representation
7468
*

‎machine/test/test_bignum.hpp

+80-31
Original file line numberDiff line numberDiff line change
@@ -633,60 +633,109 @@ class TestBignum : public CxxTest::TestSuite, public VMTest {
633633
check_float(f, Float::create(state, -880872.999999925));
634634
}
635635

636-
void test_left_shift() {
636+
void test_positive_left_shift_positive() {
637637
Bignum* one = Bignum::from(state, 1);
638+
639+
Fixnum* max_width = Fixnum::from(FIXNUM_MAX_WIDTH);
640+
Integer* fix = one->left_shift(state, max_width);
641+
642+
TS_ASSERT(kind_of<Fixnum>(fix));
643+
TS_ASSERT_EQUALS(1L << (FIXNUM_MAX_WIDTH), fix->to_native());
644+
645+
Integer* max_plus1 = one->left_shift(state, max_width+1);
646+
647+
TS_ASSERT(kind_of<Bignum>(max_plus1));
648+
TS_ASSERT_EQUALS(FIXNUM_MAX + 1, max_plus1->to_native());
649+
}
650+
651+
void test_positive_left_shift_negative() {
652+
Bignum* max_plus1 = Bignum::from(state, FIXNUM_MAX+1);
653+
Fixnum* neg_one = Fixnum::from(-1);
654+
655+
Integer* val = max_plus1->left_shift(state, neg_one);
656+
657+
TS_ASSERT(kind_of<Fixnum>(val));
658+
TS_ASSERT_EQUALS(1L << (FIXNUM_MAX_WIDTH), val->to_native());
659+
}
660+
661+
void test_negative_left_shift_positive() {
638662
Bignum* neg_one = Bignum::from(state, -1);
663+
Fixnum* min_width = Fixnum::from(FIXNUM_MIN_WIDTH);
639664

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

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

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

648-
fix = neg_one->left_shift(state, width_minus1);
672+
TS_ASSERT(kind_of<Bignum>(val));
673+
TS_ASSERT_EQUALS(FIXNUM_MIN-1, val->to_native());
674+
}
649675

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

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

655-
TS_ASSERT(kind_of<Bignum>(max_plus1));
656-
TS_ASSERT_EQUALS(FIXNUM_MAX + 1, max_plus1->to_native());
682+
TS_ASSERT(kind_of<Fixnum>(val));
683+
TS_ASSERT_EQUALS((0UL - 1L) << (FIXNUM_MIN_WIDTH), val->to_native());
684+
}
685+
686+
void test_positive_right_shift_positive() {
687+
Fixnum* one = Fixnum::from(1);
657688

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

660-
TS_ASSERT(kind_of<Bignum>(min_minus1));
661-
TS_ASSERT_EQUALS(FIXNUM_MIN - 1, min_minus1->to_native());
692+
TS_ASSERT(kind_of<Fixnum>(val));
693+
TS_ASSERT_EQUALS(1L << (FIXNUM_MAX_WIDTH), val->to_native());
662694
}
663695

664-
void test_right_shift() {
696+
void test_positive_right_shift_negative() {
697+
Fixnum* neg_one = Fixnum::from(-1);
698+
699+
Bignum* big = Bignum::from(state, 1L << FIXNUM_MAX_WIDTH);
700+
Integer* val = big->right_shift(state, neg_one);
701+
702+
TS_ASSERT(kind_of<Bignum>(val));
703+
TS_ASSERT_EQUALS(FIXNUM_MAX+1, val->to_native());
704+
665705
Bignum* one = Bignum::from(state, 1);
666-
Bignum* neg_one = Bignum::from(state, -1);
706+
Fixnum* neg_max_width = Fixnum::from(FIXNUM_MAX_WIDTH);
667707

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

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

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

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

678-
TS_ASSERT(kind_of<Fixnum>(fix));
679-
TS_ASSERT_EQUALS((0UL - 1L) << (FIXNUM_WIDTH-1), fix->to_native());
720+
TS_ASSERT(kind_of<Fixnum>(val));
721+
TS_ASSERT_EQUALS((0UL - 1L) << FIXNUM_MIN_WIDTH, val->to_native());
722+
}
680723

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

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

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

688-
TS_ASSERT(kind_of<Bignum>(min_minus1));
689-
TS_ASSERT_EQUALS(FIXNUM_MIN - 1, min_minus1->to_native());
733+
Fixnum* neg_min_width_plus1 = Fixnum::from(-(FIXNUM_MIN_WIDTH+1));
734+
735+
val = neg_one->right_shift(state, neg_min_width_plus1);
736+
737+
TS_ASSERT(kind_of<Bignum>(val));
738+
TS_ASSERT_EQUALS(FIXNUM_MIN-1, val->to_native());
690739
}
691740

692741
void test_pow() {

0 commit comments

Comments
 (0)
Please sign in to comment.