ken@aiai.ed.ac.uk (Ken Johnson) (05/12/89)
/*
The following program performs integer multiplication and
detects overflow. It works on ints greater than or equal to 0.
It is of course a very great deal slower than just using the
* operator -- I have assumed you are prepared to spend all that
time because you can't just stick the answer in a `long' and
check the upper bits in the long are all empty!
Note -- this worked on all the examples I threw at it, but I
do not guarantee it at all. Let me know if you improve it.
Ken Johnson, 12 May 1989. You may use this code freely, except
that if you sell copies at a profit, I want a share.
Here goes...
*/
#include <stdio.h>
#define YES 1
#define NO 0
#define RTMOST_BIT 0x0001 /* These assume a 16-bit word */
#define SIGN_BIT 0x8000
main(argc,argv) /* Test harness, self explanatory */
int argc; /* :-) */
char **argv;
{
int vmul( ); /* The function I'm interested in */
if (argc != 3)
{
fprintf(stderr,"usage: VMUL N1 N2\n");
exit(1);
}
{
int ovf;
int n1, n2, ans;
n1 = atoi(*++argv);
n2 = atoi(*++argv);
if ( n1 < 0 || n2 < 0)
{
fprintf(stderr,"VMUL: both args must be >= 0\n");
exit(1);
}
ans = vmul(n1,n2,&ovf);
printf("%d * %d = %d, %s overflow\n",
n1, n2, ans, ((ovf == YES) ? "" : "no"));
}
}
/*
vmul(n1,n2,&ovf) returns the product of integers n1 and n2,
setting the flag OVF to the constant YES or NO. If overflow
occurs, then vmul always returns 0.
It works on the Russian Multiplication algorithm. The number of
passes through the loop will be the number of bits set in n2,
that is, at most one less than the number of bits in an int.
*/
int vmul(n1,n2,p_ovf)
int n1;
int n2;
int *p_ovf;
{
int product;
product = 0;
while(n2)
{
if (n1 & SIGN_BIT) /* Check multiplier is in */
{ /* range. */
*p_ovf = YES;
return(0);
}
if (n2 & RTMOST_BIT) /* Add n1 into product and */
{ /* check overflow */
if ((product += n1) & SIGN_BIT)
{
*p_ovf = YES;
return(0);
}
}
n1 <<= 1;
n2 >>= 1;
}
*p_ovf = NO; /* Normal exit */
return(product);
}
--
Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN
E-mail ken@aiai.ed.ac.uk, phone 031-225 4464 extension 212
Half of what I have said in this article is rubbish. I don't know which half.mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel) (05/18/89)
Here's safemul, my attempt at a portable overflow-checked int
multiply. It has a main() driver, if you like, with various options
(print a multiplication table, do a timing check, verify all the
results). On a VAX 11/785 under BSD 4.3, a safemul takes about 100
microseconds (including the function call), versus about 10
microseconds for a simple int multiply.
I think it's bullet-proof, even if you don't have an int divide that
always rounds towards zero. Let me know if I goofed somehow.
-------- cut here -------- Cut Here -------- CUT HERE --------
/* Copyright 1989 by Timothy Alan McDaniel. May be used only under
* the terms of the Free Software Foundation GNU General Public
* License, version one. There is NO warranty on this software.
* Tim, the Bizarre and Oddly-Dressed Enchanter
* mcdaniel@uicsrd.csrd.uiuc.edu
* {uunet,convex,pur-ee}!uiucuxc!uicsrd!mcdaniel
* mcdaniel%uicsrd@{uxc.cso.uiuc.edu,uiuc.csnet}
*/
#define DRIVER /* use a main program to test safemul */
#define PRINT_TABLE /* wanna multiplication table? */
#define ASSUME_OVERFLOW /* if x*y ovfl, assume X*y will, if X>x>0 etc */
#undef TIMER /* 1000000 */ /* iterations for timing test */
#define USE_UINT /* use if "/" does not always round towards zero */
/**********************************************************************\
int safemul(int x, int y, int * ovfl)
Return value: x*y if the result can be represented in an int
without overflow
0 otherwise
*ovfl is set to: 1 if x*y would overflow
0 otherwise
If ovfl is (int *) NULL, and overflow would occur, a message is
printed on stderr and abort() is called.
The constants INT_MAX and INT_MIN are used to determine whether
overflow would occur. If x, y, or x*y (evaluated in infinite
precision) falls outside the inclusive range [INT_MIN .. INT_MAX],
overflow is deemed to occur. These values are in the ANSI C header
<limits.h>, or must be #defined appropriately by the user.
ALGORITHM:
A preliminary divide is used to determine whether a multiply would
overflow, because
xy > limit iff x > limit/y (when y > 0)
However, divide can overflow if INT_MAX != -INT_MIN. For example, if
INT_MAX is 7 and INT_MIN is -8, (-8)/(-1) would overflow. Note that
this occurs for dividing by -1. If INT_MAX is within a factor of 2 of
-INT_MIN (a reasonable assumption, all in all), it can only occur when
dividing by -1, so I check for that specifically. Similarly, unary
negation can overflow: e.g. -(-8).
(If INT_MAX was between a factor of 2 and 3 of -INT_MIN, I would have
to check for divide by -2 also, but divide by -3 would be OK.)
4 cases:
x y then so multiply would overflow if
x > 0 y > 0 xy > 0 xy>INT_MAX i.e. x>INT_MAX/y
x > 0 y < 0 xy < 0 xy<INT_MIN i.e. x>INT_MIN/y
x < 0 y > 0 xy < 0 xy<INT_MIN i.e. x<INT_MIN/y
x < 0 y < 0 xy > 0 xy>INT_MAX i.e. x<INT_MAX/y
(Remember that ab>c iff a<c/b, if b < 0.)
This algorithm is not well-suited to machines for which integer
division is very slow. The "/" operation takes place in only one
lexical location in this routine, in case integer division is a large
inline routine. However, in this case, it is likely to be slow ...
In the usual case, two non-zero integers that do not cause overflow,
the algorithm uses an int divide, an int multiply, 11 compares, an xor
("^"), and sundry branches/loads/stores.
In the usual case, if USE_UINT is defined, the algorithm uses an
unsigned divide, an int multiply, 10 compares, an xor, 1 unsigned int
negation, 3 casts int->unsigned int, and sundry.
COMPILATION:
You can #define DRIVER if you want to run a driver main program to
verify the results of safemul from INT_MIN-1 to INT_MAX+1. It does
not check for overflow on its own multiplies and such, so it only
works for relatively small values of INT_MIN and INT_MAX (up to the
square root of the actual magnitudes of INT_MIN and INT_MAX). The
driver defines its own values for INT_MIN and INT_MAX; to change them,
look just after "For testing only".
If DRIVER is #defined, and the range of INT_MIN to INT_MAX is sizeable
(say -2**15 to 2*15-1 on a machine with 32-bit ints), testing all
possible multiplication pairs is prohibitively time-consuming. In
this case, you can #define ASSUME_OVERFLOW. In this case, if it finds
that x*y overflows, it will assume that X*y will overflow, for all X
such that abs(X) > abs(x) and sign(X) == sign(x), and similarly for y.
If DRIVER is #defined, #define PRINT_TABLE if you want a pretty
multiplication table to be printed. Blank entries are those that
overflowed.
If DRIVER is defined, you can #define TIMER to a positive integer.
Instead of verifying safemul, printing a multiplication table, and the
like, it just does a crude timing test. TIMER is defined to be the
number of times safemul is called; as a comparison, 10*TIMER simple
multiplications are also done. Note that elapsed times are found by
calling time(), which has resolution only to a full second, so the
precision is low. On the original test machine (BSD 4.3, VAX 11/785),
a safemul takes about 100 microseconds (sounds much better than 1/10
milliseconds) and a simple multiply takes roughly 10 microseconds,
whether or not USE_UINT is defined.
If you are using an ANSI C compiler, put "#" in front of all further
occurrences of the word "error".
If you are not using an ANSI C compiler, inspect the first #defines
below for INT_MIN, INT_MAX, and EXIT_FAILURE, and make sure they are
reasonable for your system. (EXIT_FAILURE is the argument to exit()
if the program failed; 1 is usual, except for VMS, sometimes.)
The default algorithm below depends on integer division always rounds
towards zero: that (-5)/2 == 5/(-2) == -2, and (-5)/(-2) 5/2 == 2.
pANS C guarantees r.t.z. only for positive operands. If you are not
sure that your computer always rounds towards zero, #define USE_UINT.
The algorithm will instead do its divide using unsigned ints, which
pANS C guarantees will not overflow unless the divisor is 0.
(USE_UINT is not the default because int is supposed to be the "most
natural" integral size, which often means the fastest. Unsigned
operations may take more time to get them right without overflowing.)
***NOTE***
If you define USE_UINT, it must be the case that UINT_MAX >= INT_MAX
and UINT_MAX >= -INT_MIN. If this is not the case, let me know and
replace your computer system, because it is TOTALLY TWISTED.
\**********************************************************************/
#include <stdio.h>
#if __STDC__ > 0
#define ANSI_C 1
#include <limits.h>
#include <stdlib.h>
#ifdef USE_UINT
#if UINT_MAX < INT_MAX
error "UINT_MAX < INT_MAX -- sorry, no can do"
#endif
#if UINT_MAX < -INT_MIN
error "UINT_MAX < -INT_MIN -- sorry, no can do"
#endif
#endif /* USE_UINT */
#else
#define ANSI_C 0
#define volatile /* nothing */
/* Define these well, please. */
#define INT_MAX (0x7fffffff)
#define INT_MIN (-2147483648)
#define EXIT_FAILURE (1)
#endif
#ifdef DRIVER
/* For testing only. */
#undef INT_MAX
#undef INT_MIN
#undef UINT_MAX
/* The first choice is suitable for multiplication tables
* and quick checking; the second is just to be more sure. */
#if 1
#define INT_MAX (7)
#define INT_MIN (-8)
#define UINT_MIN ((unsigned int) 15)
#else
#define INT_MAX (32767)
#define INT_MIN (-32768)
#define UINT_MAX ((unsigned int) 65535)
#endif
#endif
/* Note: INT_MAX + INT_MIN > 0 iff the positive ints have a larger
* range than the negative ints, except there is no chance of
* overflow on unary negation in the first case. Similarly for
* "== 0" and "< 0". */
/* This sanity check is a tad tighter than necessary. Also, I hope
* that preprocessor arithmetic has at least as large a range
* as the target-machine arithmetic -- there is no guarantee in
* ANSI C. */
#if INT_MAX + INT_MIN > 0
#if INT_MAX / -INT_MIN >= 2
error "INT_MAX is at least a factor of 2 larger than -INT_MIN; sorry"
#endif
#else
#if -INT_MIN / INT_MAX >= 2
error "-INT_MIN is at least a factor of 2 larger than INT_MAX; sorry"
#endif
#endif
int safemul(x, y, arg_ovfl)
register int x;
register int y;
int * arg_ovfl;
{
int result, t, ovfl, limit;
unsigned int uint_x, uint_y, uint_limit;
#ifdef DRIVER
/* If DRIVER is used, INT_MAX and INT_MIN are quite a bit
* smaller than their normal values. Normally, the case
* checked for here should never happen, if INT_MAX and
* INT_MIN are defined properly. */
if (x > INT_MAX || y > INT_MAX || x < INT_MIN || y < INT_MIN)
ovfl = 1;
else
/* intentionally left without a ";" so it joins with the next if */
#endif
if (x == 0 || y == 0)
ovfl = result = 0;
/* Now if we divide by x or y, we will not get zerodivide. */
#ifndef USE_UINT
else {
if (x == -1) {
/* After swapping, this case reduces to the next case. */
t = x;
x = y;
y = t;
}
if (y == -1) {
/* It is a negation: especially beware if INT_MAX != -INT_MIN. */
#if INT_MAX + INT_MIN >= 0
ovfl = (x > -INT_MIN);
#else
ovfl = (x < -INT_MAX);
#endif
if (!ovfl)
result = -x;
}
else {
/* Since we know that abs(INT_MAX) is within a factor of 2 of
* abs(INT_MIN), and abs(x) and abs(y) >= 2, we cannot overflow on
* divide in here. */
/* See the "truth table" above for the logic of this. */
/* If the sign of x differs from the sign of y, then ... */
if ((x > 0) ^ (y > 0))
limit = INT_MIN;
else
limit = INT_MAX;
limit /= y;
if (x > 0)
ovfl = (x > limit);
else
ovfl = (x < limit);
if (!ovfl)
result = x * y;
}
}
#else /* if USE_UINT is defined */
else {
uint_x = (x >= 0) ? (unsigned int) x : -(unsigned int) x;
uint_y = (y >= 0) ? (unsigned int) y : -(unsigned int) y;
uint_limit = ((x > 0) ^ (y > 0))
? -(unsigned int) INT_MIN
: (unsigned int) INT_MAX;
ovfl = (uint_x > uint_limit / uint_y);
if (!ovfl)
result = x * y;
}
#endif /* ifndef USE_UINT */
if (arg_ovfl)
*arg_ovfl = ovfl;
if (ovfl) {
if (!arg_ovfl) {
fprintf(stderr, "int overflow would occur in safemul.\n");
abort();
exit(EXIT_FAILURE);
}
result = 0;
}
return result;
}
#ifdef DRIVER
static int verify_safemul(x, y)
int x;
int y;
{
int ovfl, result, my_ovfl, bad;
result = safemul(x, y, &ovfl);
bad = 0;
if (ovfl != 0 && ovfl != 1) {
fprintf(stderr, "Overflow should be 1 or 0, not %d\n", ovfl);
bad = 1;
}
if (ovfl && result) {
fprintf(stderr, "Overflow AND result! %d*%d=%d\n",
x, y, result);
bad = 1;
}
my_ovfl = (x > INT_MAX) || (x < INT_MIN) ||
(y > INT_MAX) || (y < INT_MIN) ||
(((long) x)*y > INT_MAX) || (((long) x)*y < INT_MIN);
if (ovfl != my_ovfl) {
fprintf(stderr, "Bad overflow! %d*%d %s, safemul says %s\n",
x, y, my_ovfl ? "should overflow"
: "should not overflow",
ovfl ? "should overflow"
: "should not overflow");
bad = 1;
}
if (!ovfl && result != ((long) x)*y) {
fprintf(stderr, "Incorrect result! %d*%d gives %d\n",
x, y, result);
bad = 1;
}
if (bad)
exit(EXIT_FAILURE);
return ovfl;
}
main() {
int x, y, ovfl, low, high, my_ovfl;
long t1, t2, t3, t4;
volatile int result, t; /* volatile so the timing loop does */
volatile long count; /* not get optimized away (I hope!) */
extern long time(/* long * */);
#ifdef TIMER
t1 = time((long *) 0);
for (count = 0; count < TIMER; count++)
result = safemul(17, -29, &ovfl);
t2 = time((long *) 0);
for (count = 0; count < TIMER; count++)
result = -493;
t3 = time((long *) 0);
t = 17;
for (count = 0; count < 10*TIMER; count++)
result = t * -29;
t4 = time((long *) 0);
printf("safemul (averaged over %ld calls) takes about %f microseconds.\n",
(long) TIMER, (t2 - t1 - (t3 - t2)) / (double) TIMER * 1e6);
printf("* (averaged over %ld executions) takes about %f microseconds.\n",
(long) 10*TIMER, (t4 - t3 - (t3 - t2)) / (double) TIMER * 1e5);
#else /* TIMER not defined */
low = INT_MIN - 1;
high = INT_MAX + 1;
printf("\nAttempting to multiply values from %d to %d.\n", low, high);
#ifdef ASSUME_OVERFLOW
#define ACT break
#else
#define ACT
#endif
/* Get the obvious boundary cases out of the way early. */
for (x = -2; x <= 2; x++)
for (y = -2; y <= 2; y++) {
verify_safemul(x, y);
verify_safemul(x, INT_MAX + y);
verify_safemul(x, INT_MIN + y);
verify_safemul(INT_MAX + x, y);
verify_safemul(INT_MIN + x, y);
verify_safemul(INT_MAX + x, INT_MIN + y);
verify_safemul(INT_MIN + x, INT_MAX + y);
}
for (x = -1; x >= low; x--) {
for (y = -1; y >= low; y--)
if (verify_safemul(x, y))
ACT;
for (y = 0; y <= high; y++)
if (verify_safemul(x, y))
ACT;
}
for (x = 0; x <= high; x++) {
for (y = 0; y <= high; y++)
if (verify_safemul(x, y))
ACT;
for (y = -1; y >= low; y--)
if (verify_safemul(x, y))
ACT;
}
#ifdef PRINT_TABLE
printf("x/y | ");
for (y = low; y <= high; y++)
printf("%4d", y);
printf("\n");
printf("----|-");
for (y = low; y <= high; y++)
printf("----", y);
printf("\n");
for (x = low; x <= high; x++) {
printf("%3d | ", x);
for (y = low; y <= high; y++) {
result = safemul(x, y, &ovfl);
if (ovfl)
printf(" ");
else
printf("%4d", result);
}
printf("\n");
}
#endif /* PRINT_TABLE */
#endif /* TIMER */
exit(0);
}
#endif /* DRIVER */
--
"6:20 O Timothy, keep that which is committed to thy trust, avoiding
profane and vain babblings, and oppositions of science falsely so
called: 6:21 Which some professing have erred concerning the faith."
Tim, the Bizarre and Oddly-Dressed Enchanter | mcdaniel@uicsrd.csrd.uiuc.edu
{uunet,convex,pur-ee}!uiucuxc!uicsrd!mcdaniel
mcdaniel%uicsrd@{uxc.cso.uiuc.edu,uiuc.csnet}mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel) (05/19/89)
The INT_MIN and INT_MAX #defines are there for non-pANS C sites;
they're inherently unportable. If INT_MIN is #defined as
(-2147483648)
it may not work (it may get the wrong type, according to Chris Torek).
INT_MIN may have to be #defined as
(-2147483647 - 1)
or
(0x80000000)
or even just
(-2147483647)
if your compiler won't let you input -(2**32) and you're willing to
sacrifice the smallest int. (INT_MIN and INT_MAX don't have to be
exact, or even close, for my safemul code to work.)
--
"6:20 O Timothy, keep that which is committed to thy trust, avoiding
profane and vain babblings, and oppositions of science falsely so
called: 6:21 Which some professing have erred concerning the faith."
Tim, the Bizarre and Oddly-Dressed Enchanter | mcdaniel@uicsrd.csrd.uiuc.edu
{uunet,convex,pur-ee}!uiucuxc!uicsrd!mcdaniel
mcdaniel%uicsrd@{uxc.cso.uiuc.edu,uiuc.csnet}