fixnum multiplication doesn't use long long

diff --git a/native/factor.h b/native/factor.h
index 0e638d9bcc0493498fd89028f7c34bed1186402a..7615cc3c9b29e81efcdb2972789fe849ba836c02 100644 (file)
--- a/native/factor.h
+++ b/native/factor.h
@@ -30,6 +30,8 @@ typedef unsigned long int CELL;
 #define CELLS ((signed)sizeof(CELL))
 
 #define WORD_SIZE (CELLS*8)
+#define HALF_WORD_SIZE (CELLS*4)
+#define HALF_WORD_MASK (((unsigned long)1<<HALF_WORD_SIZE)-1)
 
 /* must always be 16 bits */
 typedef unsigned short CHAR;

diff --git a/native/fixnum.c b/native/fixnum.c
index ca6a5c0323cd56efe780926e4f6fe8486ab5c268..a395a0b2bab41c585298a0714ede58d4ff72e410 100644 (file)
--- a/native/fixnum.c
+++ b/native/fixnum.c
@@ -48,13 +48,60 @@ CELL subtract_fixnum(FIXNUM x, FIXNUM y)
        return tag_integer(x - y);
 }
 
+/**
+ * Multiply two integers, and trap overflow.
+ * I'm sure a more efficient algorithm exists.
+ */
 CELL multiply_fixnum(FIXNUM x, FIXNUM y)
 {
-       long long result = (long long)x * (long long)y;
-       if(result < FIXNUM_MIN || result > FIXNUM_MAX)
-               return tag_object(s48_long_long_to_bignum(result));
+       bool negp;
+       FIXNUM hx, lx, hy, ly;
+       FIXNUM hprod, lprod, xprod, result;
+
+       if(x < 0)
+       {
+               negp = true;
+               x = -x;
+       }
        else
-               return tag_fixnum(result);
+               negp = false;
+
+       if(y < 0)
+       {
+               negp = !negp;
+               y = -y;
+       }
+
+       hx = x >> HALF_WORD_SIZE;
+       hy = y >> HALF_WORD_SIZE;
+
+       hprod = hx * hy;
+
+       if(hprod != 0)
+               goto bignum;
+
+       lx = x & HALF_WORD_MASK;
+       ly = y & HALF_WORD_MASK;
+
+       lprod = lx * ly;
+
+       if(lprod > FIXNUM_MAX)
+               goto bignum;
+
+       xprod = lx * hy + hx * ly;
+
+       if(xprod > (FIXNUM_MAX >> HALF_WORD_SIZE))
+               goto bignum;
+
+       result = (xprod << HALF_WORD_SIZE) + lprod;
+       if(negp)
+               result = -result;
+       return tag_integer(result);
+
+bignum:        return tag_object(
+               s48_bignum_multiply(
+                       s48_long_to_bignum(x),
+                       s48_long_to_bignum(y)));
 }
 
 CELL divint_fixnum(FIXNUM x, FIXNUM y)