Compute Library
 20.11
fft.cpp
Go to the documentation of this file.
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  */
25 
26 #include <numeric>
27 
28 namespace arm_compute
29 {
30 namespace helpers
31 {
32 namespace fft
33 {
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 
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
std::vector< unsigned int > decompose_stages(unsigned int N, const std::set< unsigned int > &supported_factors)
Decompose a given 1D input size using the provided supported factors.
Definition: fft.cpp:34
std::vector< unsigned int > digit_reverse_indices(unsigned int N, const std::vector< unsigned int > &fft_stages)
Calculate digit reverse index vector given fft size and the decomposed stages.
Definition: fft.cpp:79
unsigned int N
Copyright (c) 2017-2020 Arm Limited.
__kernel void accumulate(__global uchar *input_ptr, uint input_stride_x, uint input_step_x, uint input_stride_y, uint input_step_y, uint input_offset_first_element_in_bytes, __global uchar *accu_ptr, uint accu_stride_x, uint accu_step_x, uint accu_stride_y, uint accu_step_y, uint accu_offset_first_element_in_bytes)
This function accumulates an input image into output image.
Definition: accumulate.cl:41