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

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 - 1. But I said I was done tweaking for now. :-)

-Jerry