[Python-Dev] Memory size overflows

[Gerald S. Williams]

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