mini-gmp: mpz_init_set_str fails on leading zeroes
Austyn Krutsinger
akrutsinger at gmail.com
Fri Jul 29 11:23:00 UTC 2016
>
> So I think it's fine to always initialize rn to 1. And then mpz_set_str
> will have to either strip leading zeros in the input to mpn_set_str, or
> normalize the result afterwards.
>
I think the attached patch provides a reasonable solution. The only
function effected is mpn_set_str_other() and since this particular function
is unique to mini-gmp, there is no requirement for trying to maintain
different
implementations
of mpz_set_str() or mpn_mul_1().
Well, more different than they already are anyways.
The attached patch adds a flag to mpn_set_str_other() so its return, it
knows if the number being processed ends up being a zero or if it ends up
being some number greater than zero. As soon as one of the limbs is
calculated to be a number (w > 0) then the z flag is set. This allows the
string number to be converted into an valid mpz_t number, then return the
appropriate size based on the value of the originating string number,
obviously the expected behavior.
The other way to handle leading zero's is, as you mentioned, skip them in
the mpz_set_str() function, however if you set a number to all zero's like
mpz_set_str(r, "000000000000000000000000", 10), then mpn_set_str_other()
will assert an error, assert (j == sn);, because of the mismatch of
expected string length (sn) and calculated string length (j). j will always
be at least 1 because of the line w = sp[j++];. Having mpz_set_str() skip
the leading zeros could probably the fastest method and waste the least CPU
cycles, but would incur other checks elsewhere in the code. I haven't
looked at a solution for the mpz_set_str fix, so I don't know what other
bits of code would need to be changed other than what I've just highlighted.
> Since this is mini-gmp, another option which is fine if it turns
> out to be simpler, is to add an if (!n) return 0; to the start of
> mpn_mul_1, and an appropriate comment somewhere. Then mpn_set_str will
> produce always normalized output, with no changes.
>
In a very roundabout way, it's not as simple as
if (!n) return 0; in mpn_mul_1 or mpn_add_1. This is what I had initially
tried actually, but when you try a string of zeros at least the length of
the base, so 0000000000 for base 10, a function like mpz_out_str() will end
up calling mpn_limb_size_in_base_2() and mpn_limb_size_in_base_2() will
fail because the mp_limb_t u will be null. This comes from the fact that
u->_mp_size is set to 1 before mpz_sizeinbase() is called. The actual value
of up[0] is 4 bytes of zeros, so when mpn_limb_size_in_base_2(up[un-1]) is
called, an error is asserted that up[0] is 0.
size_t
mpz_sizeinbase (const mpz_t u, int base)
{
...
un = GMP_ABS (u->_mp_size);
if (un == 0)
return 1;
up = u->_mp_d;
bits = (un - 1) * GMP_LIMB_BITS + mpn_limb_size_in_base_2 (up[un-1]);
Regards,
Austyn
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0003-Fix-issue-with-mpn_set_str_other-not-properly-handli.patch
Type: application/octet-stream
Size: 1313 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-bugs/attachments/20160729/380d8b8d/attachment.obj>
More information about the gmp-bugs
mailing list