mpn_mul_fft type overflow issue

[Mark Sofroniou]

On 09/18/2013 05:27 AM, Torbjorn Granlund wrote:
> Hello Mark!
>
> I cannot say that we were unaware of these type probems in mul_fft.c.
> Since I have no machine where to test changes, I have postponed fixing
> these problems.
>
> I am glad you have had a chance to clean this up.
Hi Torbjorn, thanks for the quick reply.
> Some questions, though:
>
> * How did you test the original code/modified code?  Did you test it
>    systematically, say with a modified tests/mpz/t-mul, or did you just
>    run into a problem frm an application?
It's a long story. We (me and David Librik) first noticed it in the Windows
64 bit version of Mathematica more than a year ago (don't remember exactly
when I'd have to check). At that time we thought it was an issue with the
Windows long long type and GMP's use of long and we didn't really have a
machine to fully test it on.

This June I was verifying a huge Factorial computation in a Linux-x86-64
development version of Mathematica (using gmp 5.1.2) and got this
allocation error.

At that point I realised it was nothing to do with Windows so set about
tracking where this went wrong in GMP and creating standalone code
to test and run.
> * How much of non-multiply GMP code have you tested for these huge
>    operands?  I don't expect many type problems elsewhere, but to say
>    there are zero problem would probably be over-optimistic.
I have only tried mpn_mul, mpn_add and mpn_subtract. I had to make
a special application to use a public machine with 1000GB of memory to
test them since these issues only show up with allocations > 2^37
and I only had access to a machine with 384GB at work.
> We will look at your patch soon.  You seem to change "unsigned long"
> used for sizes into mp_limb_t.  That's a curious change.  I'd say that
> we should typically use mp_size_t for sizes, while mp_limb_t should be
> used for numerical data.  Alternatively, size_t can be used for the
> former needs.
>
Thanks. I wasn't completely sure what the right type was in all cases.
Most of the changes are to use mp_size_t instead of int - these are
the important ones. There are a couple (related to the variables K2 and K3)
that change unsigned int to mp_limb_t. I also changed mpn_mul_fft_lcm
to mp_limb_t and that doesn't look exactly right - size_t doesn't
look right there - maybe a bit counter type (not sure what you
use for that other than int)?

One of the reasons for sending this for discussion was that I wanted
to know if you are amenable to these sorts of changes and whether
it is worth me investing more time on them. I think that it would be
nice to not have plain C uses of int/long and unsigned int/long internally
in the mpn functions and to replace them with scalable types.

There are things like:

   int sqr = (n == m && nl == ml);

that would maybe be clearer as a boolean type.

Regards, Mark