diff options
author | Georgios Pinitas <georgios.pinitas@arm.com> | 2019-03-18 20:07:37 +0000 |
---|---|---|
committer | Georgios Pinitas <georgios.pinitas@arm.com> | 2019-03-29 10:46:38 +0000 |
commit | 0bc784982f183d9d50be31adb867e84c237d9fc3 (patch) | |
tree | 0c6f7092d409acfcf204c0b537be01524b776e6b /src/core/utils/helpers | |
parent | 47d39dc615d1dee2482bc84699802165a9778ac8 (diff) | |
download | ComputeLibrary-0bc784982f183d9d50be31adb867e84c237d9fc3.tar.gz |
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>
Diffstat (limited to 'src/core/utils/helpers')
-rw-r--r-- | src/core/utils/helpers/fft.cpp | 124 |
1 files changed, 124 insertions, 0 deletions
diff --git a/src/core/utils/helpers/fft.cpp b/src/core/utils/helpers/fft.cpp new file mode 100644 index 0000000000..7ff2fdf62b --- /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 |