mini-gmp: mpz_init_set_str fails on leading zeroes
Austyn Krutsinger
akrutsinger at gmail.com
Fri Jul 22 16:09:40 UTC 2016
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
>>
>>
>
More information about the gmp-bugs
mailing list