Hi GMP Team,
I have found a bug in GMP 6.3.0 while experimenting with a generic C build
(--disable-assembly) and attempting to use a lower MUL_TOOM22_THRESHOLD
(value 5). The issue involves `mpn_toom42_mul` crashing with small
unbalanced inputs.
## 1. GMP Version
GMP 6.3.0 (Patched locally to lower MUL_TOOM22_THRESHOLD to 5).
Note: We were experimenting with a generic C build (--disable-assembly) and
attempting to patch gmp-impl.h to use a lower MUL_TOOM22_THRESHOLD (value
5) to enable specific optimizations for small sizes. This bug is exposed by
tuning the threshold, but indicates a logic-check handling in `toom42`
logic for specific geometries.
## 2. Test Program
I have pasted a self-contained reproduction program `reproduce_bug.c`.
```c
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
mp_limb_t mpn_mul (mp_ptr rp, mp_srcptr s1p, mp_size_t un, mp_srcptr s2p,
mp_size_t vn);
int main() {
// Trigger case: 9x5 multiplication
// Requires library built with MUL_TOOM22_THRESHOLD=5 (or lower)
mp_size_t un = 9;
mp_size_t vn = 5;
mp_limb_t *a = malloc(un * sizeof(mp_limb_t));
mp_limb_t *b = malloc(vn * sizeof(mp_limb_t));
mp_limb_t *p = malloc((un + vn) * sizeof(mp_limb_t));
for(int i=0; i<un; i++) a[i] = 1;
for(int i=0; i<vn; i++) b[i] = 1;
printf("Testing 9x5 mul...\n");
mpn_mul(p, a, un, b, vn);
printf("Success\n");
return 0;
}
```
## 3. Description
When `MUL_TOOM22_THRESHOLD` is set to 5, `mpn_mul` dispatches 9x5
multiplication to `mpn_toom42_mul` (since `vn=5 >= THRESHOLD`).
Inside `mpn_toom42_mul`:
- Inputs: `an = 9`, `bn = 5`.
- `n` calculation: `(bn + 1) >> 1` results in `n = 3`.
- `s` calculation: `an - 3 * n` results in `9 - 9 = 0`.
- The code assumes `s > 0` (expecting 4 parts for A) and crashes or asserts
failure.
Running `make check` also results in test failures when the library is
built with this configuration, confirming the issue affects standard tests
as well.
The fix is to handle `s <= 0` by falling back to `mpn_toom32_mul`, which
supports the 3-part split for A.
## 4. Stack Backtrace
```
Program received signal SIGSEGV, Segmentation fault.
0x... in __gmpn_lshift () from .../libgmp.so.10
#0 0x... in __gmpn_lshift ()
#1 0x... in __gmpn_toom42_mul ()
#2 0x... in __gmpn_mul ()
#3 0x... in main () at reproduce_bug.c...
```
(Note: The crash occurs due to invalid scratch/pointer usage, maybe because
geometry assumptions are violated.)
## 5. Build Steps (Reproduction)
To reproduce the issue, build GMP as follows:
1. Configure for generic C build:
`./configure --disable-assembly`
2. Modify `gmp-impl.h` to lower the threshold (before running make):
Change:
`#define MUL_TOOM22_THRESHOLD 30`
to:
`#define MUL_TOOM22_THRESHOLD 5`
(This can be done with sed: `sed -i 's/#define MUL_TOOM22_THRESHOLD
30/#define MUL_TOOM22_THRESHOLD 5/' gmp-impl.h`)
3. Compile the library:
`make`
4. Compile the reproduction program against this library:
`gcc -I. -L.libs reproduce_bug.c -lgmp -o reproduce_bug`
`LD_LIBRARY_PATH=.libs ./reproduce_bug`
## 6. Compiler and System
**Compiler:** gcc 11.4.0 (Ubuntu 11.4.0-1ubuntu1~22.04.2)
**System:** Linux nehalem ... x86_64 GNU/Linux
**Config Guess:** nehalem-pc-linux-gnu
## 7. config.log excerpt
(Not applicable as this is a logic bug exposed by threshold tuning, not a
configure detection failure).
## Suggested Fix
In `mpn/generic/toom42_mul.c`, add a check for `s <= 0`:
```c
s = an - 3 * n;
t = bn - n;
if (s <= 0)
{
mpn_toom32_mul (pp, ap, an, bp, bn, scratch);
return;
}
```
--
Subhrajit
_______________________________________________
gmp-bugs mailing list
[email protected]
https://gmplib.org/mailman/listinfo/gmp-bugs
