| 77 | } |
| 78 | |
| 79 | std::vector<unsigned int> digit_reverse_indices(unsigned int N, const std::vector<unsigned int> &fft_stages) |
| 80 | { |
| 81 | std::vector<unsigned int> idx_digit_reverse; |
| 82 | |
| 83 | // Early exit in case N and fft stages do not match |
| 84 | const float stages_prod = |
| 85 | std::accumulate(std::begin(fft_stages), std::end(fft_stages), (unsigned int)1, std::multiplies<unsigned int>()); |
| 86 | if (stages_prod != N) |
| 87 | { |
| 88 | return idx_digit_reverse; |
| 89 | } |
| 90 | |
| 91 | // Resize digit reverse vector |
| 92 | idx_digit_reverse.resize(N); |
| 93 | |
| 94 | // Get number of radix stages |
| 95 | unsigned int n_stages = fft_stages.size(); |
| 96 | |
| 97 | // Scan elements |
| 98 | for (unsigned int n = 0; n < N; ++n) |
| 99 | { |
| 100 | unsigned int k = n; |
| 101 | unsigned int Nx = fft_stages[0]; |
| 102 | |
| 103 | // Scan stages |
| 104 | for (unsigned int s = 1; s < n_stages; ++s) |
| 105 | { |
| 106 | // radix of stage i-th |
| 107 | unsigned int Ny = fft_stages[s]; |
| 108 | unsigned int Ni = Ny * Nx; |
| 109 | |
| 110 | // Update k index |
| 111 | k = (k * Ny) % Ni + (k / Nx) % Ny + Ni * (k / Ni); |
| 112 | |
| 113 | // Update Nx |
| 114 | Nx *= Ny; |
| 115 | } |
| 116 | |
| 117 | // K is the index of digit-reverse |
| 118 | idx_digit_reverse[n] = k; |
| 119 | } |
| 120 | |
| 121 | return idx_digit_reverse; |
| 122 | } |
| 123 | } // namespace fft |
| 124 | } // namespace helpers |
| 125 | } // namespace arm_compute |