COMPMID-1958: Implements 1D FFT in OpenCL.
Forward complex FFT implementation.
Change-Id: Ia0ba8740072e5adb06f8ead462a47abc8b5dd125
Signed-off-by: Georgios Pinitas <georgios.pinitas@arm.com>
Reviewed-on: https://review.mlplatform.org/c/904
Reviewed-by: Gian Marco Iodice <gianmarco.iodice@arm.com>
Tested-by: Arm Jenkins <bsgcomp@arm.com>
Comments-Addressed: Arm Jenkins <bsgcomp@arm.com>
diff --git a/src/core/utils/helpers/fft.cpp b/src/core/utils/helpers/fft.cpp
new file mode 100644
index 0000000..7ff2fdf
--- /dev/null
+++ b/src/core/utils/helpers/fft.cpp
@@ -0,0 +1,124 @@
+/*
+ * Copyright (c) 2019 ARM Limited.
+ *
+ * SPDX-License-Identifier: MIT
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to
+ * deal in the Software without restriction, including without limitation the
+ * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+#include "arm_compute/core/utils/helpers/fft.h"
+
+#include <numeric>
+
+namespace arm_compute
+{
+namespace helpers
+{
+namespace fft
+{
+std::vector<unsigned int> decompose_stages(unsigned int N, const std::set<unsigned int> &supported_factors)
+{
+ std::vector<unsigned int> stages;
+ unsigned int res = N;
+
+ // Early exit if no supported factors are provided
+ if(supported_factors.empty())
+ {
+ return stages;
+ }
+
+ // Create reverse iterator (Start decomposing from the larger supported factors)
+ auto rfactor_it = supported_factors.rbegin();
+
+ // Decomposition step
+ while(res != 0)
+ {
+ const unsigned int factor = *rfactor_it;
+ if(0 == (res % factor) && res >= factor)
+ {
+ stages.push_back(factor);
+ res /= factor;
+ }
+ else
+ {
+ ++rfactor_it;
+ if(rfactor_it == supported_factors.rend())
+ {
+ if(res > 1)
+ {
+ // Couldn't decompose with given factors
+ stages.clear();
+ return stages;
+ }
+ else
+ {
+ res = 0;
+ }
+ }
+ }
+ }
+
+ return stages;
+}
+
+std::vector<unsigned int> digit_reverse_indices(unsigned int N, const std::vector<unsigned int> &fft_stages)
+{
+ std::vector<unsigned int> idx_digit_reverse;
+
+ // Early exit in case N and fft stages do not match
+ const float stages_prod = std::accumulate(std::begin(fft_stages), std::end(fft_stages), 1, std::multiplies<unsigned int>());
+ if(stages_prod != N)
+ {
+ return idx_digit_reverse;
+ }
+
+ // Resize digit reverse vector
+ idx_digit_reverse.resize(N);
+
+ // Get number of radix stages
+ unsigned int n_stages = fft_stages.size();
+
+ // Scan elements
+ for(unsigned int n = 0; n < N; ++n)
+ {
+ unsigned int k = n;
+ unsigned int Nx = fft_stages[0];
+
+ // Scan stages
+ for(unsigned int s = 1; s < n_stages; ++s)
+ {
+ // radix of stage i-th
+ unsigned int Ny = fft_stages[s];
+ unsigned int Ni = Ny * Nx;
+
+ // Update k index
+ k = (k * Ny) % Ni + (k / Nx) % Ny + Ni * (k / Ni);
+
+ // Update Nx
+ Nx *= Ny;
+ }
+
+ // K is the index of digit-reverse
+ idx_digit_reverse[n] = k;
+ }
+
+ return idx_digit_reverse;
+}
+} // namespace fft
+} // namespace helpers
+} // namespace arm_compute