[Python-Dev] Memory size overflows
Gerald S. Williams
gsw@agere.com
Thu, 17 Oct 2002 12:06:28 -0400
Armin Rigo wrote:
> We might be running into code bloats thought. If we go for such big
> macros, I believe we should design them so that they run fast in the
> common case and call a helper function otherwise.
Easily done, but first you have to ask yourself if it's
really ever more efficient than this:
#define SAFE_MULTIPLY(dest,src1,src2,on_overflow)\
{\
size_t _x = src1;\
size_t _y = src2;\
size_t _dest = _x * _y;\
\
dest = _dest;\
\
if ((_x | _y) & HI_MASK)\
{\
if ((_dest / _x) != _y)\
{\
on_overflow;\
}\
}\
}
If so, here's a macro/helper version:
#define FULL_BITS (sizeof(size_t) * 8U)
#define TOP_BIT (((size_t)1) << ((FULL_BITS)-1))
#define HALF_BITS (sizeof(size_t) * 4U)
#define MID_BIT (((size_t)1) << ((HALF_BITS)-1))
#define LO_MASK ((((size_t)1) << (HALF_BITS))-1)
#define HI_MASK (~(LO_MASK))
#define SAFE_MULTIPLY(dest,src1,src2,on_overflow)\
{\
size_t _x = src1;\
size_t _y = src2;\
size_t _dest = _x * _y;\
\
dest = _dest;\
\
if ((_x | _y) & HI_MASK)\
{\
if (_safe_multiply_check_for_overflow(_x,_y,_dest))\
{\
on_overflow;\
}\
}\
}
int
_safe_multiply_check_for_overflow(
size_t x,
size_t y,
size_t dest)
{
size_t h;
size_t l;
if (x >= y)
{
h = x;
l = y;
}
else
{
h = y;
l = x;
}
if ((h & HI_MASK) && (l))
{
int hlog;
int llog;
if (l & HI_MASK)
{
hlog = llog = FULL_BITS;
}
else
{
size_t mask;
for ((mask=TOP_BIT),(hlog=FULL_BITS-1);!(mask&h);mask>>=1)
{
--hlog;
}
for ((mask=MID_BIT),(llog=HALF_BITS-1);!(mask&l);mask>>=1)
{
--llog;
}
}
if ((hlog + llog > FULL_BITS - 1) ||
((hlog + llog == FULL_BITS - 1) && !(dest & TOP_BIT)))
{
return 1;
}
}
return 0;
}
Of course there are also the alternatives of using floating point
numbers (assuming the mantissa has as many bits as size_t), or a
double-width intermediate representation, if available.
There are also some other tricks that can be used to optimize this
solution. The time-consuming part is finding out if the sum of the
log2's of the multiplicands (i.e., highest bit positions) is less
than, greater than, or equal to <bits in size_t> - 1. But I said I
was done tweaking for now. :-)
-Jerry