mul_fft, cleaning up some details of the code

Marco Bodrato bodrato at
Sun Mar 6 11:14:49 CET 2022


I looked into the code published by Samuel Vivien.
I realised that in mul_fft there are a lot of _add_1 and _sub_1. At 
least some of them can be easily replaced by _INCR_U or _DECR_U...

Specifically I'd focus into a suspicious piece of code, shared by both 
our current code and Vivien's.

The function mpn_mul_fft_decompose has a branch "if (dif > Kl)", that
ends with the following lines:

	  if (cy >= 0)
	    cy = mpn_add_1 (tmp, tmp, Kl, cy);
	    cy = mpn_sub_1 (tmp, tmp, Kl, -cy);

Can those lines be correct? Can the value in cy be used after this code 
both if it contains the carry or if it contains the borrow of the 
operation on tmp?

I believe this is an error, I'd change the last line into
	cy = 1 - mpn_sub_1 (tmp, tmp, Kl, -cy - 1);
and I propose the attached patch changing this and some other _1 

This is not really needed to solve a bug.
The comment before the mpn_mul_fft_decompose function says "We must have 
nl <= 2*K*l", this means that we should never have ((dif = nl - Kl) > 
Kl), and the code in that branch should never be used.
According to the coverage analisys, the code is not explored by the 
The "bug" is never triggered.

Maybe the branch could be used if someone re-enables mpn_mul_fft_full 
and uses it for very unbalanced (more than 4x1) operands?

-------------- next part --------------
A non-text attachment was scrubbed...
Name: mul_fft.diff
Type: text/x-diff
Size: 4103 bytes
Desc: not available
URL: <>

More information about the gmp-devel mailing list