Bignum fixes

[Chris Shoemaker]

These makes the specs in core/bignum and core/float pass for me.

-chris

Short-log:

Three optimizations and one BUG comment for Bignum#>>.
Fix broken Bignum#>>.
Give Bignums a stable hash code.
Change libtommath to make Bignum#to_s only use lowercase letters.
Fix Bignum.from_float.

Diff-stat:

.../external_libs/libtommath/bn_mp_radix_smap.c | 2 +-
.../external_libs/libtommath/bn_mp_read_radix.c | 2 +-
shotgun/lib/bignum.c | 114 +++++++------------
shotgun/lib/bignum.h | 1 +
shotgun/lib/object.c | 2 +
5 files changed, 47 insertions(+), 74 deletions(-)

[Chris Shoemaker]

Oops. Here are the patches, too. :)

-chris

[Chris Shoemaker]

1) avoid temporary mp_init/mp_clear of temp var when self is positive.
2) remove one duplicated early-exit branch
3) combine two branches into one.

This patch doesn't change any results, but just cleans up the algorithm
to make it easier to see where the bug is.
---
shotgun/lib/bignum.c | 26 +++++++++-----------------
1 files changed, 9 insertions(+), 17 deletions(-)

diff --git a/shotgun/lib/bignum.c b/shotgun/lib/bignum.c
index a928509..ef946ae 100644
--- a/shotgun/lib/bignum.c
+++ b/shotgun/lib/bignum.c
@@ -338,39 +338,31 @@ OBJECT bignum_right_shift(STATE, OBJECT self, OBJECT bits) {
mp_int * a;
mp_int b;

- mp_init(&b);
a = MP(self);

- if (s1 > a->used) {
+ if (s1 >= a->used) {
if (a->sign == MP_ZPOS)
return I2N(0);
else
return I2N(-1);
}

- if (a->sign == MP_NEG) {
- mp_copy(a, &b);
- twos_complement(&b);
- a = &b;
- }
-
- i = a->used;
+ i = a->used;
j = i - s1;

- if (j == 0) {
- if (a->sign == MP_ZPOS)
- return I2N(0);
- else
- return I2N(-1);
- }
-
n->sign = a->sign;
mp_grow(n, j);

if (a->sign == MP_NEG) {
+ mp_init(&b);
+ mp_copy(a, &b);
+ twos_complement(&b);
+ a = &b;
num = ((BDIGIT_DBL)~0) << DIGIT_BIT;
}
while (i--, j--) {
+ // BUG: This algorithm would be correct only if we filled the bits vacated
+ // by the shift with ones.
num = (num | DIGIT(a,i)) >> s2;
DIGIT(n,j) = num & (DIGIT_RADIX-1);
num = ((BDIGIT_DBL)DIGIT(a,i)) << DIGIT_BIT;
@@ -379,9 +371,9 @@ OBJECT bignum_right_shift(STATE, OBJECT self, OBJECT bits) {

if (a->sign == MP_NEG) {
twos_complement(n);
+ mp_clear(&b);
}

- mp_clear(&b);
return bignum_normalize(state, n_obj);
}

--
1.5.3.7.1157.gbf82a

[Chris Shoemaker]

We now correctly simulate a twos-complement representation by
conditionally rounding toward negative infinity. This is simpler
than converting to twos-complement twice, and doesn't require any
tricky filling the shift vacancy with ones.

We short-circuit the case where we're shifting zero bits and
use mp_div_2d() instead of reimplementing the bit-shifting.

Also, drastically simplify bignum_left_shift() by using mp_mul_2d.
---
shotgun/lib/bignum.c | 90 +++++++++++++++----------------------------------
1 files changed, 28 insertions(+), 62 deletions(-)

diff --git a/shotgun/lib/bignum.c b/shotgun/lib/bignum.c
index ef946ae..5f88012 100644
--- a/shotgun/lib/bignum.c
+++ b/shotgun/lib/bignum.c
@@ -295,83 +295,49 @@ OBJECT bignum_neg(STATE, OBJECT self) {
OBJECT bignum_left_shift(STATE, OBJECT self, OBJECT bits) {
NMP;
int shift = FIXNUM_TO_INT(bits);
- int s1 = shift / DIGIT_BIT;
- int s2 = shift % DIGIT_BIT;
- long len, i, j;
-
- mp_int * a;
- BDIGIT_DBL num = 0;
-
- a = MP(self);
- len = a->used;
+ mp_int * a = MP(self);

+ mp_mul_2d(a, shift, n);

n->sign = a->sign;

- mp_grow(n, len + s1 + 1);
-
- for (i=0; i < s1; i++) {
- DIGIT(n,i) = 0;
- n->used += 1;
- }
-
- for (j=0; j < len; j++) {
- num = num | (BDIGIT_DBL)DIGIT(a,j) << s2;
- DIGIT(n,i++) = (num & (DIGIT_RADIX-1));
- num = num >> DIGIT_BIT;
- n->used += 1;
- }
-
- DIGIT(n,i) = (num & (DIGIT_RADIX-1));
- n->used += 1;
-
return bignum_normalize(state, n_obj);

}

OBJECT bignum_right_shift(STATE, OBJECT self, OBJECT bits) {

NMP;
int shift = FIXNUM_TO_INT(bits);
- long s1 = shift / DIGIT_BIT;
- long s2 = shift % DIGIT_BIT;
-
- BDIGIT_DBL num = 0;
- long i, j;
-
- mp_int * a;
- mp_int b;
+ mp_int * a = MP(self);

- a = MP(self);
-
- if (s1 >= a->used) {
+ if ((shift / DIGIT_BIT) >= a->used) {

if (a->sign == MP_ZPOS)
return I2N(0);
else
return I2N(-1);
}

- i = a->used;
- j = i - s1;
-

- n->sign = a->sign;

- mp_grow(n, j);
-

- if (a->sign == MP_NEG) {

- mp_init(&b);

- mp_copy(a, &b);
- twos_complement(&b);
- a = &b;

- num = ((BDIGIT_DBL)~0) << DIGIT_BIT;
- }
- while (i--, j--) {
- // BUG: This algorithm would be correct only if we filled the bits vacated
- // by the shift with ones.
- num = (num | DIGIT(a,i)) >> s2;
- DIGIT(n,j) = num & (DIGIT_RADIX-1);
- num = ((BDIGIT_DBL)DIGIT(a,i)) << DIGIT_BIT;
- n->used += 1;
- }
-

- if (a->sign == MP_NEG) {

- twos_complement(n);
- mp_clear(&b);
+ if (shift == 0) {
+ mp_copy(a, n);
+ } else {
+ int need_floor = (a->sign == MP_NEG) && (DIGIT(a, 0) & 1);
+
+ mp_div_2d(a, shift, n, NULL);
+ n->sign = a->sign;
+ if (need_floor) {
+ /* We sometimes have to simulate the rounding toward negative
+ infinity that would happen if we were using a twos-complement
+ representation. We know we'll never overflow or need to grow,
+ but we may need to back away from zero. (libtommath doesn't
+ seem to have an increment-in-place function.) */
+ long i = 0;
+ BDIGIT_DBL num = 1;
+
+ if (n->used == 0)
+ n->used = 1;
+ while (i < n->used) {
+ num += DIGIT(n,i);
+ DIGIT(n,i++) = num & (DIGIT_RADIX-1);
+ num = num >> DIGIT_BIT;
+ }
+ }

[Chris Shoemaker]

---
shotgun/lib/bignum.c | 12 ++++++++++++
shotgun/lib/bignum.h | 1 +
shotgun/lib/object.c | 2 ++
3 files changed, 15 insertions(+), 0 deletions(-)

diff --git a/shotgun/lib/bignum.c b/shotgun/lib/bignum.c
index 5f88012..0f29d65 100644
--- a/shotgun/lib/bignum.c
+++ b/shotgun/lib/bignum.c
@@ -579,3 +579,15 @@ OBJECT bignum_size(STATE, OBJECT self)
as I'm concerned. */
return I2N(bytes);
}
+
+int bignum_hash_int(OBJECT self)
+{
+ mp_int *a = MP(self);
+
+ /* Apparently, a couple bits of each a->dp[n] aren't actually used,
+ (e.g. when DIGIT_BIT is 60) so this hash is actually including
+ that unused memory. This might only be a problem if calculations
+ are leaving cruft in those unused bits. However, since Bignums
+ are immutable, this shouldn't happen to us. */
+ return string_hash_str((unsigned char *)a->dp, a->used * sizeof(a->dp));
+}
diff --git a/shotgun/lib/bignum.h b/shotgun/lib/bignum.h
index c0157a7..895a56d 100644
--- a/shotgun/lib/bignum.h
+++ b/shotgun/lib/bignum.h
@@ -30,5 +30,6 @@ OBJECT bignum_from_ull(STATE, unsigned long long val);
OBJECT bignum_from_ll(STATE, long long val);
OBJECT bignum_size(STATE, OBJECT self);
int bignum_is_zero(STATE, OBJECT a);
+int bignum_hash_int(OBJECT a);

#endif
diff --git a/shotgun/lib/object.c b/shotgun/lib/object.c
index bfc9827..2c58d82 100644
--- a/shotgun/lib/object.c
+++ b/shotgun/lib/object.c
@@ -118,6 +118,8 @@ unsigned int object_hash_int(STATE, OBJECT self) {
} else {
if(ISA(self, state->global->string)) {
hsh = string_hash_int(state, self);
+ } else if(ISA(self, BASIC_CLASS(bignum))) {
+ hsh = bignum_hash_int(self);
} else {
hsh = object_get_id(state, self);
}
--
1.5.3.7.1157.gbf82a

[Chris Shoemaker]

---

.../external_libs/libtommath/bn_mp_radix_smap.c | 2 +-
.../external_libs/libtommath/bn_mp_read_radix.c | 2 +-

2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/shotgun/external_libs/libtommath/bn_mp_radix_smap.c b/shotgun/external_libs/libtommath/bn_mp_radix_smap.c
index 7d72feb..438700f 100644
--- a/shotgun/external_libs/libtommath/bn_mp_radix_smap.c
+++ b/shotgun/external_libs/libtommath/bn_mp_radix_smap.c
@@ -16,7 +16,7 @@
*/

/* chars used in radix conversions */
-const char *mp_s_rmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
+const char *mp_s_rmap = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ+/";
#endif

/* $Source: /cvs/libtom/libtommath/bn_mp_radix_smap.c,v $ */
diff --git a/shotgun/external_libs/libtommath/bn_mp_read_radix.c b/shotgun/external_libs/libtommath/bn_mp_read_radix.c
index 91c46c2..9320796 100644
--- a/shotgun/external_libs/libtommath/bn_mp_read_radix.c
+++ b/shotgun/external_libs/libtommath/bn_mp_read_radix.c
@@ -48,7 +48,7 @@ int mp_read_radix (mp_int * a, const char *str, int radix)
* this allows numbers like 1AB and 1ab to represent the same value
* [e.g. in hex]
*/
- ch = (char) ((radix < 36) ? toupper (*str) : *str);
+ ch = (char) ((radix < 36) ? tolower (*str) : *str);
for (y = 0; y < 64; y++) {
if (ch == mp_s_rmap[y]) {
break;
--
1.5.3.7.1157.gbf82a

[Chris Shoemaker]

On 64-bit architectures, you can't assume that a mp_digit will fit
inside an int.

This fixes three float specs.
---
shotgun/lib/bignum.c | 4 ++--
1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/shotgun/lib/bignum.c b/shotgun/lib/bignum.c
index 0f29d65..11b33a3 100644
--- a/shotgun/lib/bignum.c
+++ b/shotgun/lib/bignum.c
@@ -534,7 +534,7 @@ OBJECT bignum_from_double(STATE, double d)
NMP;

long i = 0;
- unsigned int c;
+ BDIGIT_DBL c;
double value;

value = (d < 0) ? -d : d;
@@ -557,7 +557,7 @@ OBJECT bignum_from_double(STATE, double d)

while (i--) {
value *= DIGIT_RADIX;
- c = (unsigned int)value;
+ c = (BDIGIT_DBL) value;
value -= c;
DIGIT(n,i) = c;
n->used += 1;
--
1.5.3.7.1157.gbf82a

[Tilman Sauerbeck]

Chris Shoemaker [2007-12-16 16:22]:

> These makes the specs in core/bignum and core/float pass for me.

Thanks, they are all in.

Regards,
Tilman

--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?