[Python-Dev] Memory size overflows

[Tim Peters]

[Guido]
> ...
> I currently use something like this as the overflow test in a few places:
>
>   if (src1 && destination / src1 != src2)
>
> but as Tim points out the division can kill us unless src1 is a
> constant...  How would you spell this without doing a division?

Armin answered that in the case there's an efficient "unsigned long long"
type at least twice the width of the inputs.  Then you just do the product
in the fat precision and see whether any of the upper-half bits are set.

As a pragmatic matter, 2/5ths of that trick can work "most of the time":

#define YOWZA (sizeof(size_t) * 4U)

    if ((src1 | src2} >> YOWZA)
        hard to tell
    else
        overflow is impossible

would get out quick in *most* non-overflow cases.  The fast path there
succeeds if and only if both inputs are at most "half full".  For example,
in

    string * int

it's rare that len(string) >= 64K or int >= 64K.

For what to do in the other half, see the history of subtly buggy attempts
to detect overflow quickly in Python's int * int code.  Without a
double-width type to fall back on, I think it's impossible to do this both
correctly and quickly.

BTW, if we know we're not interested in anything other than 32-bit products,

    double _prod = (double)src1 * (double)src2;
    if (_prod < 4294967296.0) /* 2**32 */
        result = (size_t)_prod;
    else
        overflow;

does the trick reliably on all platforms I know of -- although not all
Python platforms support floating-point efficiently!

It's a good puzzle <wink>.