lambdaworks_math/
helpers.rs

1#[cfg(feature = "alloc")]
2use crate::field::{element::FieldElement, traits::IsFFTField};
3
4/// Computes the power of two that is equal or greater than n
5pub fn next_power_of_two(n: u64) -> u64 {
6    if n <= 1 {
7        1
8    } else {
9        (u64::MAX >> (n - 1).leading_zeros()) + 1
10    }
11}
12
13/// Pads the trace table with zeros until the length of the columns of the trace
14/// is equal to a power of 2
15/// This is required to ensure that we can use the radix-2 Cooley-Tukey FFT algorithm
16#[cfg(feature = "alloc")]
17pub fn resize_to_next_power_of_two<F: IsFFTField>(
18    trace_colums: &mut [alloc::vec::Vec<FieldElement<F>>],
19) {
20    trace_colums.iter_mut().for_each(|col| {
21        // TODO: Remove this unwrap. This may panic if the usize cant be
22        // casted into a u64.
23        let col_len = col.len().try_into().unwrap();
24        let next_power_of_two_len = next_power_of_two(col_len);
25        col.resize(next_power_of_two_len as usize, FieldElement::<F>::zero())
26    })
27}