Compute Library
 20.11
arm_compute::helpers::fft Namespace Reference

Functions

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. More...
 
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. More...
 

Function Documentation

◆ decompose_stages()

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.

Parameters
[in]NInput size to be decomposed.
[in]supported_factorsSupported factors that can be used for decomposition.
Returns
A vector with the stages of the decomposition. Will be empty if decomposition failed.

Definition at line 34 of file fft.cpp.

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 }
unsigned int N

References N.

Referenced by NEFFT1D::configure(), CLFFT1D::configure(), NEFFT1D::validate(), and CLFFT1D::validate().

◆ digit_reverse_indices()

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.

Parameters
NInput size to calculate digit reverse for
fft_stagesA vector with the FFT decomposed stages
Returns
A vector with the digit reverse indices. Will be empty if it failed.

Definition at line 79 of file fft.cpp.

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 }
unsigned int N
__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

References accumulate(), and N.

Referenced by NEFFT1D::configure(), and CLFFT1D::configure().