From 63c70c830c79f0b4cfc0f7393662a9cb1169973e Mon Sep 17 00:00:00 2001 From: pcpa Date: Thu, 24 May 2012 15:26:50 -0300 Subject: Correct 64 bit overflow check and bignum code. Signed-off-by: pcpa Signed-off-by: Alan Coopersmith --- lisp/mathimp.c | 35 +++-------------------------------- lisp/mp/mp.c | 12 ++++++------ lisp/mp/mp.h | 2 ++ lisp/mp/mpi.c | 8 ++++---- lisp/read.c | 4 +--- 5 files changed, 16 insertions(+), 45 deletions(-) diff --git a/lisp/mathimp.c b/lisp/mathimp.c index f5c098f..293625b 100644 --- a/lisp/mathimp.c +++ b/lisp/mathimp.c @@ -39,15 +39,6 @@ #define CONST /**/ #endif -/* mask for checking overflow on long operations */ -#ifdef LONG64 -#define FI_MASK 0x4000000000000000L -#define LONGSBITS 63 -#else -#define FI_MASK 0x40000000L -#define LONGSBITS 31 -#endif - #define N_FIXNUM 1 #define N_BIGNUM 2 #define N_FLONUM 3 @@ -2738,7 +2729,7 @@ fi_fi_add_overflow(long op1, long op2) { long op = op1 + op2; - return (op1 > 0 ? op2 > op : op2 < op); + return (op2 >= 0 ? op < op1 : op > op1); } /* @@ -2749,7 +2740,7 @@ fi_fi_sub_overflow(long op1, long op2) { long op = op1 - op2; - return (((op1 < 0) ^ (op2 < 0)) && ((op < 0) ^ (op1 < 0))); + return (op2 >= 0 ? op > op1 : op < op1); } /* @@ -2758,35 +2749,15 @@ fi_fi_sub_overflow(long op1, long op2) static INLINE int fi_fi_mul_overflow(long op1, long op2) { -#ifndef LONG64 - double op = (double)op1 * (double)op2; - - return (op > 2147483647.0 || op < -2147483648.0); -#else - int shift; - long mask; - if (op1 == 0 || op1 == 1 || op2 == 0 || op2 == 1) return (0); - if (op1 == MINSLONG || op2 == MINSLONG) return (1); - if (op1 < 0) op1 = -op1; if (op2 < 0) op2 = -op2; - - for (shift = 0, mask = FI_MASK; shift < LONGSBITS; shift++, mask >>= 1) - if (op1 & mask) - break; - ++shift; - for (mask = FI_MASK; shift < LONGSBITS; shift++, mask >>= 1) - if (op2 & mask) - break; - - return (shift < LONGSBITS); -#endif + return (op1 > MAXSLONG / op2); } diff --git a/lisp/mp/mp.c b/lisp/mp/mp.c index 2afb343..cf24768 100644 --- a/lisp/mp/mp.c +++ b/lisp/mp/mp.c @@ -190,19 +190,19 @@ mp_add(BNS *rop, BNS *op1, BNS *op2, BNI len1, BNI len2) MP_SWAP(op1, op2, len1, len2); /* unroll start of loop */ - value = op1[0] + op2[0]; + value = (BNI)op1[0] + op2[0]; rop[0] = value; carry = value >> BNSBITS; /* add op1 and op2 */ for (size = 1; size < len2; size++) { - value = op1[size] + op2[size] + carry; + value = (BNI)op1[size] + op2[size] + carry; rop[size] = value; carry = value >> BNSBITS; } if (rop != op1) { for (; size < len1; size++) { - value = op1[size] + carry; + value = (BNI)op1[size] + carry; rop[size] = value; carry = value >> BNSBITS; } @@ -210,7 +210,7 @@ mp_add(BNS *rop, BNS *op1, BNS *op2, BNI len1, BNI len2) else { /* if rop == op1, than just adjust carry */ for (; carry && size < len1; size++) { - value = op1[size] + carry; + value = (BNI)op1[size] + carry; rop[size] = value; carry = value >> BNSBITS; } @@ -237,7 +237,7 @@ mp_sub(BNS *rop, BNS *op1, BNS *op2, BNI len1, BNI len2) } /* unroll start of loop */ - svalue = op1[0] - op2[0]; + svalue = (long)op1[0] - op2[0]; rop[0] = svalue; carry = svalue < 0; @@ -257,7 +257,7 @@ mp_sub(BNS *rop, BNS *op1, BNS *op2, BNI len1, BNI len2) else { /* if rop == op1, than just adjust carry */ for (; carry && size < len1; size++) { - svalue = op1[size] - carry; + svalue = (long)op1[size] - carry; rop[size] = svalue; carry = svalue < 0; } diff --git a/lisp/mp/mp.h b/lisp/mp/mp.h index 8bcb127..c5a74f3 100644 --- a/lisp/mp/mp.h +++ b/lisp/mp/mp.h @@ -76,6 +76,7 @@ # define BNI unsigned long # define BNS unsigned int # define MINSLONG 0x8000000000000000UL +# define MAXSLONG 0x7fffffffffffffffUL # define CARRY 0x100000000 # define LMASK 0xffffffff00000000UL # define SMASK 0x00000000ffffffffUL @@ -89,6 +90,7 @@ # define BNI unsigned long # define BNS unsigned short # define MINSLONG 0x80000000UL +# define MAXSLONG 0x7fffffffUL # define CARRY 0x10000 # define LMASK 0xffff0000UL # define SMASK 0x0000ffffUL diff --git a/lisp/mp/mpi.c b/lisp/mp/mpi.c index fabe366..447bd23 100644 --- a/lisp/mp/mpi.c +++ b/lisp/mp/mpi.c @@ -318,7 +318,7 @@ mpi_setstr(mpi *rop, char *str, int base) if (islower(value)) value = toupper(value); value = value > '9' ? value - 'A' + 10 : value - '0'; - value += rop->digs[0] * base; + value += (BNI)rop->digs[0] * base; carry = value >> BNSBITS; rop->digs[0] = (BNS)value; for (i = 1; i < size; i++) { @@ -642,10 +642,10 @@ mpi_divqr(mpi *qrop, mpi *rrop, mpi *num, mpi *den) if (ndigs[npos] == ddigs[dpos]) qest = (BNS)SMASK; else - qest = (BNS)((((BNI)(ndigs[npos]) << 16) + ndigs[npos - 1]) / + qest = (BNS)((((BNI)(ndigs[npos]) << BNSBITS) + ndigs[npos - 1]) / ddigs[dpos]); - while ((value = ((BNI)(ndigs[npos]) << 16) + ndigs[npos - 1] - + while ((value = ((BNI)(ndigs[npos]) << BNSBITS) + ndigs[npos - 1] - qest * (BNI)(ddigs[dpos])) < CARRY && ddigs[dpos - 1] * (BNI)qest > (value << BNSBITS) + ndigs[npos - 2]) @@ -1603,7 +1603,7 @@ mpi_getstr(char *str, mpi *op, int base) /* make copy of op data and adjust digs */ xdigs = mp_malloc(size * sizeof(BNS)); - memcpy(xdigs, op->digs, size * sizeof(unsigned short)); + memcpy(xdigs, op->digs, size * sizeof(BNS)); digs = xdigs + size - 1; /* convert to string */ diff --git a/lisp/read.c b/lisp/read.c index 9c70b64..a49e240 100644 --- a/lisp/read.c +++ b/lisp/read.c @@ -1474,9 +1474,7 @@ LispParseNumber(char *str, int radix, LispObj *read__stream, int read__line) integer = strtol(str, NULL, radix); /* if does not fit in a long */ - if (errno == ERANGE && - ((*str == '-' && integer == LONG_MIN) || - (*str != '-' && integer == LONG_MAX))) { + if (errno == ERANGE) { bignum = LispMalloc(sizeof(mpi)); mpi_init(bignum); mpi_setstr(bignum, str, radix); -- cgit v1.2.3