[Python-Dev] Memory size overflows (original) (raw)

Gerald S. Williams gsw@agere.com
Thu, 17 Oct 2002 10:07:12 -0400

Here's a version of my previous algorithm with the checks added back in to improve overall performance. This one runs about as fast as the divide-and-compare algorithm for my test cases. :-)

OK, I'm done tweaking now...

#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)
{
size_t h;
int hlog;
size_t l;
int llog;
size_t mask;

if (_x >= _y)
{
h = _x;
l = _y;
}
else
{
h = _y;
l = _x;
}

if ((h & HI_MASK) && (l))
{
if (l & HI_MASK)
{
hlog = llog = FULL_BITS;
}
else
{
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)))
{
on_overflow;
}
}
}
}

-Jerry