Antwort: Re: Re: mini-gmp: mpz_init_set_str fails on leading zeroes

[Axel Miller]

Works for me.
Regards,
Axel


Von:    Austyn Krutsinger <akrutsinger at gmail.com>
An:     Axel Miller <axel.miller at ppi.de>
Kopie:  gmp-bugs at gmplib.org, Torbjörn Granlund <tg at gmplib.org>
Datum:  22.07.2016 18:10
Betreff:        Re: Re: mini-gmp: mpz_init_set_str fails on leading zeroes



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> wrote: 
Austyn Krutsinger <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