out-of-bound write

Torbjorn Granlund tg at gmplib.org
Tue Dec 17 11:40:25 UTC 2013

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.

  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 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

Please encrypt, key id 0xC8601622

More information about the gmp-bugs mailing list