[Python-Dev] Memory size overflows

[Gerald S. Williams]

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