[Python-Dev] Memory size overflows

[Tim Peters]

[Scott Gilbert]
> The following is really ugly (until you put it in a macro), but
> would work:
>
> #define HALF_BITS (sizeof(size_t) * 4U)
> #define LO_MASK ((((size_t)1) << HALF_BITS)-1)
> #define HI_MASK (LO_MASK<<HALF_BITS)
>
>   if (
>       /* Tim's fast path */
>       ((src1 | src2) & HI_MASK) && (
>       /* Ugly slower path */
>       (((src1&LO_MASK) * (src2>>HALF_BITS)) & HI_MASK) |
>       (((src1>>HALF_BITS) * (src2&LO_MASK)) & HI_MASK) |
>       (src1>>HALF_BITS) * (src2>>HALF_BITS))
>   ) {
>      goto overflow;
>   }

I'll repeat that it's hard to do this correctly and quickly (c.f. earlier
comments about the history of Python's subtly buggy attempts).

This kind of approach is viewing src1 and src2 as 2-digit numbers in base X
= 2**HALF_BITS:

    src1 = A*X + B
    src2 = C*X + D

then viewing their product as

highpart:      A*C*X**2 +
               xxxxxxxx
middlepart1:          A*D*X +
                   xxxxxxxx
middlepart2:          B*C*X +
                   xxxxxxxx
lowpart:                    B*D
                       xxxxxxxx
               ----------------
               xxxxxxxxxxxxxxxx
               <danger>< safe >

Your second line checks whether the high half of middlepart2 is 0; your
third line whether the high half of middlepart1 is 0; your last line whether
highpart is 0.  But they can all be 0 and *still* have overflow:  the sum

    low half of middlepart1 +
    low half of middlepart2 +
    high half of lowpart

can carry over into the <danger> zone.  Supposing we were looking at 16-bit
products, here's an example:

        0x01ff *
        0x00ff
        ------
      0000
        00ff
        0000
          fe01
      --------
      0001fd01
         ^ oops

Hint:  before posting something like this, prototype it in Python, and do an
exhaustive check of all possible pairs of multiplicands in an artificially
small base.  Very few buggy algorithms survive that, even for very small
artificial bases.