out-of-bound write

[Vincent Lefevre]

On 2013-12-17 12:40:25 +0100, Torbjorn Granlund wrote:
> Zimmermann Paul <Paul.Zimmermann at inria.fr> writes:
> 
>   it would make sense that mpn_set_str requires that the space
>   allocated at RP contains at least:
>   
>   a = the exact number of limbs needed to store the input number,
>       
>   or b = the number of limbs needed to store the maximal possible
>       input number of base BASE with STRSIZE chars, i.e.,
>       BASE^STRSIZE-1,
>   
>   where of course a <= b.
>   
>   The bug is that in some cases, the required space is even b + 1!
>   
> Almost.  I think a+1 is the required allocation.

It seems that what Paul says is ambiguous (can be interpreted
differently).

>   For example on a 64-bit computer with BASE=3 and STRSIZE=1815 limbs,
>   mpn_set_str might require up to 46 limbs, whereas 3^1815-1 has 45
>   limbs only.
>   
>   As a consequence, it is not possible to know how much space needs
>   to be allocated at RP before calling mpn_set_str.
>   
> First you analyse the allocation requirements, then then you say
> such an analysis is not possible. :-)

I think that Paul means that currently, due to the bug, it is not
possible to know how much space is needed, because GMP may end up
adding leading 0's.

> I don't think trimming the requirements to a or even b will be doable
> without either:
> 
> 1. slowing down the function (by e.g., split up the culprit mpn_mul call
>    into one mpn_mul and one mpn_addmul_1, or
> 2. making a large local allocation for the mpn_mul product.
> 
> To me, documenting a+1 as required allocation seem like the best
> solution.  (We need to read the sources to make sure a+1 is indeed
> correct.)

So, if I understand correctly, you consider that the current
documentation is incorrect and GMP's current behavior is the
expected one.

-- 
Vincent Lefèvre <vincent at vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)