1 /*
2 * Copyright (c) 2019-2020 Arm Limited.
3 *
4 * SPDX-License-Identifier: MIT
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to
8 * deal in the Software without restriction, including without limitation the
9 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10 * sell copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24 #include "src/core/utils/helpers/fft.h"
25
26 #include <numeric>
27
28 namespace arm_compute
29 {
30 namespace helpers
31 {
32 namespace fft
33 {
decompose_stages(unsigned int N,const std::set<unsigned int> & supported_factors)34 std::vector<unsigned int> decompose_stages(unsigned int N, const std::set<unsigned int> &supported_factors)
35 {
36 std::vector<unsigned int> stages;
37 unsigned int res = N;
38
39 // Early exit if no supported factors are provided
40 if(supported_factors.empty())
41 {
42 return stages;
43 }
44
45 // Create reverse iterator (Start decomposing from the larger supported factors)
46 auto rfactor_it = supported_factors.rbegin();
47
48 // Decomposition step
49 while(res != 0)
50 {
51 const unsigned int factor = *rfactor_it;
52 if(0 == (res % factor) && res >= factor)
53 {
54 stages.push_back(factor);
55 res /= factor;
56 }
57 else
58 {
59 ++rfactor_it;
60 if(rfactor_it == supported_factors.rend())
61 {
62 if(res > 1)
63 {
64 // Couldn't decompose with given factors
65 stages.clear();
66 return stages;
67 }
68 else
69 {
70 res = 0;
71 }
72 }
73 }
74 }
75
76 return stages;
77 }
78
digit_reverse_indices(unsigned int N,const std::vector<unsigned int> & fft_stages)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 = std::accumulate(std::begin(fft_stages), std::end(fft_stages), 1, std::multiplies<unsigned int>());
85 if(stages_prod != N)
86 {
87 return idx_digit_reverse;
88 }
89
90 // Resize digit reverse vector
91 idx_digit_reverse.resize(N);
92
93 // Get number of radix stages
94 unsigned int n_stages = fft_stages.size();
95
96 // Scan elements
97 for(unsigned int n = 0; n < N; ++n)
98 {
99 unsigned int k = n;
100 unsigned int Nx = fft_stages[0];
101
102 // Scan stages
103 for(unsigned int s = 1; s < n_stages; ++s)
104 {
105 // radix of stage i-th
106 unsigned int Ny = fft_stages[s];
107 unsigned int Ni = Ny * Nx;
108
109 // Update k index
110 k = (k * Ny) % Ni + (k / Nx) % Ny + Ni * (k / Ni);
111
112 // Update Nx
113 Nx *= Ny;
114 }
115
116 // K is the index of digit-reverse
117 idx_digit_reverse[n] = k;
118 }
119
120 return idx_digit_reverse;
121 }
122 } // namespace fft
123 } // namespace helpers
124 } // namespace arm_compute
125