Rader's Algorithm causes overflow on 32-bit systems (WebAssembly)

[LukasWuethrich]

Description:
I have a signal with 3,600,032 values and I am computing its FFT. On a 64-bit system, this works perfectly, but on a 32-bit system, it causes an overflow. I am using rustfft in WebAssembly, and currently only 32-bit is available.

The problem is related to the size of usize. As soon as I decrease or increase my vector by a single element, it works fine again, but I assume that Rader's algorithm is no longer being used in that case.

Steps to Reproduce:

demo.zip

Set Rust override: rustup override set 1.85
Add 32-bit Linux target: rustup target add i686-unknown-linux-gnu
Run the demo with backtrace enabled: RUST_BACKTRACE=1 cargo run --target i686-unknown-linux-gnu

Error:

thread 'main' panicked at /home/dev/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/rustfft-6.4.0/src/algorithm/raders_algorithm.rs:94:29: attempt to multiply with overflow
stack backtrace:
0: rust_begin_unwind
1: core::panicking::panic_fmt
2: core::panicking::panic_const::panic_const_mul_overflow
3: rustfft::algorithm::raders_algorithm::RadersAlgorithm<T>::new
4: rustfft::plan::FftPlannerScalar<T>::build_new_fft
5: rustfft::plan::FftPlannerScalar<T>::build_fft
...
note: Some details are omitted, run with RUST_BACKTRACE=full for a verbose backtrace.

Screenshots / Logs / Demo:
I have prepared a minimal demo that reproduces the issue, which can be attached here.

Environment:
Operating System: 32-bit Linux (i686)
Rust Version: 1.85
rustfft Version: 6.4.0
WebAssembly target: yes

Additional Information:

• The overflow seems to be caused by the size of usize on 32-bit systems.
• Changing the vector length by one element avoids the overflow, likely bypassing Rader's algorithm.

[HEnquist]

An easy solution would be to use u64 instead of usize for the calculation on line 94 of raders.

[LukasWuethrich]

I had the same thought. However, I'm not sure if changing line 94 alone is sufficient, or if other variables also need to be updated.

I have now extended my demo project so that I can work locally with a checkout of RustFFT. Since I can now also debug, I noticed that Rader’s algorithm is only used in the 32-bit environment. Otherwise, a different algorithm is used.

btw: I'm not very familiar with Rust and only know the basics

[HEnquist]

I noticed that Rader’s algorithm is only used in the 32-bit environment. Otherwise, a different algorithm is used.

This is really surprising! The choice of algorithm should only depend on the fft length. Are you sure? 3,600,032 contains a large prime in its factorization so it must use either Raders or Bluesteins, but if it uses Raders in a 32-bit build it really should do the same on 64.

[LukasWuethrich]

@HEnquist Thanks a lot for your support!

This is really surprising! The choice of algorithm should only depend on the fft length. Are you sure?

I tried it again and realized that on 64-bit I am using the AVX planner, while on 32-bit I am using the Scalar planner. For my tests, I modified the code so that it always uses the Scalar planner (regardless of 32-bit or 64-bit), and in that case the Radars algorithm is always used. I had previously overlooked the effect of the planner.

I also tried modifying line 94 of raders so that it uses u64 instead of usize, but I couldn’t get it to work. Either I get errors because the data types don’t match anymore, or I end up having to cast so much that no runtime error occurs, but then the FFT result is still wrong.
Do you have any tip or maybe a code snippet on how this could be done?

[HEnquist]

I was thinking something like this: #164
Can you try this branch with your demo?

[HEnquist]

I made another branch containing only the new test I added, but without the u64 fix. Looks good, the test reproduces the panic you on a 32-bit build, see https://github.com/HEnquist/RustFFT/actions/runs/17345950011/job/49245950279?pr=10#logs

[LukasWuethrich]

I was thinking something like this: #164
Can you try this branch with your demo?

Thanks for branch! Unfortunately, I have a second error in raders on line 277.

thread 'main' panicked at /home/dev/git/rust/demo/RustFFT/src/algorithm/raders_algorithm.rs:277:28:
attempt to multiply with overflow

I tried to solve the error in a similar way to your approach, but I couldn't find a solution. The data type StrengthReducedUsize is also used, and unfortunately I'm overwhelmed by that.

Should I make my demo project available to you somehow?

[HEnquist]

Ok, so it's not enough to construct the FFT in the test, it also needs to process something. I updated the PR, can you try again?

[LukasWuethrich]

Now it works! The result looks good

Very, very grateful for this PR! Many thanks @HEnquist

What happens next? Is there a release process?

[HEnquist]

Great! Now we wait for @ejmahler to review my PR :)

[ejmahler]

Thanks for reporting, and thanks to @HEnquist for making a PR. I should have time tonight to review.

[ejmahler]

I tried it again and realized that on 64-bit I am using the AVX planner, while on 32-bit I am using the Scalar planner. For my tests, I modified the code so that it always uses the Scalar planner (regardless of 32-bit or 64-bit), and in that case the Radars algorithm is always used. I had previously overlooked the effect of the planner.

You didn't mention this, but an I correct in guessing that for your 64 bit test, you switched from the webassembly toolchain to intel? I'm assuming that's what happened here and that's why it was selecting different planners but I just want to make sure.

[LukasWuethrich]

You didn't mention this, but an I correct in guessing that for your 64 bit test, you switched from the webassembly toolchain to intel? I'm assuming that's what happened here and that's why it was selecting different planners but I just want to make sure.

yes, that's is true. That happened more by chance, because I wanted to eliminate the complexity of WebAssembly. At the beginning, I had trouble narrowing down the bug and wanted to rule out the possibility that the error was occurring during data transfer to WASM. Locally, I had a 64-bit system, of course, and it was only then that I realized WASM is only 32-bit.

[ejmahler]

Fixed in release 6.4.1. Thanks for reporting, and thanks to @HEnquist for the PR.