Il 2020-09-13 11:38 t...@gmplib.org ha scritto:
Marco Bodrato <bodr...@mail.dm.unipi.it> writes:
With ABI=64 I get:
16777216 ^ 768614336404564651 = 256
With ABI=32 I get:
16777216 ^ 178956971 = 256
Not a signal, nor an abort, simply an incorrect result :-)
That's undesirable.
I thought we cought overflows also in this difficult a^b case by
(indirectly means of allocation errors).
Yet another...
$ cat provo.c
#include <stdio.h>
#include "gmp.h"
int
main ()
{
unsigned long b, e;
mpz_t p;
mpz_t bz;
mpz_init (p);
mpz_init (bz);
b = 24 * GMP_NUMB_BITS;
mpz_setbit (bz, b);
e = ~0UL / 24 + 1;
mpz_pow_ui (p, bz, e);
gmp_printf ("(2 ^ %lu) ^ %lu = %Zd\n", b, e, p);
mpz_clear (bz);
mpz_clear (p);
}
$ gcc provo.c -lgmp -o provo&& ./provo
(2 ^ 1536) ^ 768614336404564651 =
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
And here is a possible patch (for the 6.2 branch):
$ hg diff mpz
diff -r e1fd9db13b47 mpz/n_pow_ui.c
--- a/mpz/n_pow_ui.c Tue Dec 22 23:49:51 2020 +0100
+++ b/mpz/n_pow_ui.c Sat Jun 12 15:24:36 2021 +0200
@@ -206,11 +206,33 @@
/* Strip low zero limbs from b. */
rtwos_limbs = 0;
+#if 1
for (blimb = *bp; blimb == 0; blimb = *++bp)
{
rtwos_limbs += e;
+ if (UNLIKELY (rtwos_limbs < e))
+ {
+ fprintf (stderr, "gmp: overflow in mpz type\n");
+ abort ();
+ }
bsize--; ASSERT (bsize >= 1);
}
+#else
+ blimb = *bp;
+ if (blimb == 0)
+ {
+ do
+ ++rtwos_limbs;
+ while ((blimb = *++bp) == 0);
+ bsize -= rtwos_limbs; ASSERT (bsize >= 1);
+ umul_ppmm (ovfl, rtwos_limbs, e, rtwos_limbs);
+ if (ovfl)
+ {
+ fprintf (stderr, "gmp: overflow in mpz type\n");
+ abort ();
+ }
+ }
+#endif
TRACE (printf ("trailing zero rtwos_limbs=%ld\n", rtwos_limbs));
/* Strip low zero bits from b. */
As you can see, I tried two different patches. One adds a (well
predicted?) branch in the (on average O(1)) loop. The other uses a
multiplication.
But we should probably consider to add a piece of code, at the beginning
of the function, estimating the total size of the result, to avoid so
many spurious checks...
Ĝis,
m
_______________________________________________
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
