mini-gmp: mpz_init_set_str fails on leading zeroes

[Austyn Krutsinger]

I think I've got a workable solution for everybody's review. I added a 'z'
flag. If none of the calculated limbs are great than 0, then we know the
entire number is zero and we return zero. Otherwise, we treat the
calculated number as any other and return the size.


static mp_size_t
mpn_set_str_other (mp_ptr rp, const unsigned char *sp, size_t sn,
  mp_limb_t b, const struct mpn_base_info *info)
{
  mp_size_t rn;
  mp_limb_t w;
  unsigned k;
  size_t j;
  mp_size_t z;

  k = 1 + (sn - 1) % info->exp;

  j = 0;
  w = sp[j++];
  while (--k != 0)
    w = w * b + sp[j++];

  rp[0] = w;

  z = (w > 0);
  for (rn = 1; j < sn;)
    {
      mp_limb_t cy;

      w = sp[j++];
      for (k = 1; k < info->exp; k++)
   w = w * b + sp[j++];

      if (w > 0)
        z = 1;

      cy = mpn_mul_1 (rp, rp, rn, info->bb);
      cy += mpn_add_1 (rp, rp, rn, w);
      if (cy > 0)
   rp[rn++] = cy;
    }
  assert (j == sn);

  return z == 0 ? z : rn;
}

Regards,
Austyn

On Fri, Jul 22, 2016 at 12:02 AM, Austyn Krutsinger <akrutsinger at gmail.com>
wrote:

> On Thu, Jul 21, 2016 at 5:46 PM, Axel Miller <axel.miller at ppi.de> wrote:
>
>> Wouldn't that break mpz_sgn(v)
>> if i use mpz_set_str(v, "00000000000000000000000000000000000000000000",
>> 10) ?
>>
>
> ​
> I'm not too sure about what will happen with mpz_sgn. mpz_sizeinbase has a
> problem handling all
> ​zeros as you have above. I presume
> mpn_get_str_bits
> ​ would also fail because it too calls
> mpn_limb_size_in_base_2
> ​(up[0]) in this specific case.​
> ​
>
> 3980  size_t
> 3981   mpz_sizeinbase (const mpz_t u, int base)
> 3982   {
>            /*snip*/
> 3996
> 3997     up = u->_mp_d;
> 3998
> 3999     bits = (un - 1) * GMP_LIMB_BITS + mpn_limb_size_in_base_2 (
> up[un-1]);
> 4000     switch (base)
> 4001       {
>
> mpn_limb_size_in_base_2 fails because it expects u to be greater than
> zero.
>
> 1147   static mp_bitcnt_t
> 1148   mpn_limb_size_in_base_2 (mp_limb_t u)
> 1149   {
> 1150     unsigned shift;
> 1151
> 1152     assert (u > 0);
> 1153     gmp_clz (shift, u);
> 1154     return GMP_LIMB_BITS - shift;
> 1155   }
>
> I don't really have any ideas right now on a solution either.
>
> Regards,
> Austyn
>
>
>
>> mpn_set_str_other would then return a value greater than zero for v, even
>> if the value is zero.
>> Thus v->_mp_size would be greater than zero:
>>
>> 4179       rn = mpn_set_str_other (rp, dp, sn, base, &info);
>> 4180     }
>> 4181   assert (rn <= alloc);
>> 4182   gmp_free (dp);
>> 4183
>> 4184   r->_mp_size = sign ? - rn : rn;
>>
>> As a consequence, mpz_sgn(v) would return 1.
>>
>> Kind regards
>> Axel
>>
>>
>>
>> Von:        Austyn Krutsinger <akrutsinger at gmail.com>
>> An:        Torbjörn Granlund <tg at gmplib.org>
>> Kopie:        Axel Miller <axel.miller at ppi.de>, gmp-bugs at gmplib.org
>> Datum:        21.07.2016 10:53
>> Betreff:        Re: mini-gmp: mpz_init_set_str fails on leading zeroes
>> ------------------------------
>>
>>
>>
>>
>> On Thu, Jul 21, 2016 at 1:43 AM, Torbjörn Granlund <*tg at gmplib.org*
>> <tg at gmplib.org>> wrote:
>> Austyn Krutsinger <*akrutsinger at gmail.com* <akrutsinger at gmail.com>>
>> writes:
>>
>>   My initial though was to just skip the leading zero's in the mpz_set_str
>>   function by something like this:
>>
>>     while (isspace( (unsigned char) *sp) || (*sp == '0'))
>>       sp++;
>>
>>   Only problems is that this doesn't work for negative numbers that still
>>   have a bunch of leading zeros;
>>
>> I think we should not accept strings like 00000-0000017.
>>
>> Absolutely agree with you, kind of a silly proposal in retrospect.
>>
>> We can fix this in the mpn_set_str_other function by changing the
>> comparison in line 1321. If we accept that w can be > or = to 0, then there
>> is no issue if the number has leading zeros. So line 1321 in
>> mpn_set_str_other becomes:
>>
>> 1321   for (rn = (w >= 0); j < sn;)
>> 1322     {
>> 1323       mp_limb_t cy;
>> 1324
>> 1325       w = sp[j++];
>> 1326       for (k = 1; k < info->exp; k++)
>> 1327     w = w * b + sp[j++];
>> 1328
>> 1329       cy = mpn_mul_1 (rp, rp, rn, info->bb);
>> 1330       cy += mpn_add_1 (rp, rp, rn, w);
>> 1331       if (cy > 0)
>> 1332     rp[rn++] = cy;
>> 1333     }
>> 1334   assert (j == sn);
>> 1321   for (rn = (w > 0); j < sn;)
>>
>> Regards,
>> Austyn
>>
>>
>