[Python-Dev] Memory size overflows

[Gerald S. Williams]

I felt obliged to post a working copy of SAFE_MULTIPLY. On
my platform, it's slower than simply dividing by one of the
multiplicands and comparing to the other, but it does get
the job done without division. This is what I started out
to write before my brain short-circuited.

Here's a simplified Python representation of the algorithm:

def check(x,y,m):
    xrem, xlog = math.frexp(x)
    yrem, ylog = math.frexp(y)

    if xlog + ylog == m + 1:
	return (xrem * yrem >= 0.5)
    else:
	return xlog + ylog > m + 1


And here it is in C:

#define FULL_BITS (sizeof(size_t) * 8U)
#define TOP_BIT (((size_t)1) << ((FULL_BITS)-1))
#define HALF_BITS (sizeof(size_t) * 4U)

#define SAFE_MULTIPLY(dest,src1,src2,on_overflow)\
    {\
        size_t _x = src1;\
        size_t _y = src2;\
        size_t _dest = _x * _y;\
        size_t h;\
        int    hlog;\
        size_t l;\
        int    llog;\
        size_t mask;\
        \
        dest = _dest;\
        \
        if (_x >= _y)\
        {\
            h = _x;\
            l = _y;\
        }\
        else\
        {\
            h = _y;\
            l = _x;\
        }\
        \
        if (l)\
        {\
            for ((mask=TOP_BIT),(hlog=FULL_BITS-1); !(mask & h); mask >>= 1)\
            {\
                --hlog;\
            }\
            if (hlog >= HALF_BITS)\
            {\
                for (llog = hlog; !(mask & l); mask >>= 1)\
                {\
                    --llog;\
                }\
                if (((hlog + llog) > (FULL_BITS - 1)) ||\
                    (((hlog + llog) == (FULL_BITS - 1)) &&\
                     (((h >> 1) * l + ((h & 1) ? (l >> 1) : 0)) >= TOP_BIT)))\
                {\
                    on_overflow;\
                }\
            }\
        }\
    }

-Jerry