| /****************************************************************************** |
| * |
| * Copyright 2016 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at: |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| * |
| ******************************************************************************/ |
| |
| #include "fft.h" |
| |
| /* ---------------------------------------------------------------------------- |
| * FFT processing |
| * -------------------------------------------------------------------------- */ |
| |
| /** |
| * Tables |
| * |
| * T_N[0..N-1] = |
| * { cos(-2Pi i/N) + j sin(-2Pi i/N), |
| * cos(-2Pi 2i/N) + j sin(-2Pi 2i/N) } , N=15, 45, 90 |
| * |
| * T_N[0..N/2-1] = |
| * cos(-2Pi i/N) + j sin(-2Pi i/N) , N=10, 20, ... |
| */ |
| |
| struct fft_bf2_twiddles { |
| int n2; |
| const struct fft_complex* t; |
| }; |
| struct fft_bf3_twiddles { |
| int n3; |
| const struct fft_complex (*t)[2]; |
| }; |
| |
| static const struct fft_bf2_twiddles twiddles_10 = { |
| .n2 = 10 / 2, |
| .t = (const struct fft_complex[]){ |
| {1.0000000e+00, -0.0000000e+00}, |
| {8.0901699e-01, -5.8778525e-01}, |
| {3.0901699e-01, -9.5105652e-01}, |
| {-3.0901699e-01, -9.5105652e-01}, |
| {-8.0901699e-01, -5.8778525e-01}, |
| }}; |
| |
| static const struct fft_bf2_twiddles twiddles_20 = { |
| .n2 = 20 / 2, |
| .t = (const struct fft_complex[]){ |
| {1.0000000e+00, -0.0000000e+00}, |
| {9.5105652e-01, -3.0901699e-01}, |
| {8.0901699e-01, -5.8778525e-01}, |
| {5.8778525e-01, -8.0901699e-01}, |
| {3.0901699e-01, -9.5105652e-01}, |
| {6.1232340e-17, -1.0000000e+00}, |
| {-3.0901699e-01, -9.5105652e-01}, |
| {-5.8778525e-01, -8.0901699e-01}, |
| {-8.0901699e-01, -5.8778525e-01}, |
| {-9.5105652e-01, -3.0901699e-01}, |
| }}; |
| |
| static const struct fft_bf2_twiddles twiddles_30 = { |
| .n2 = 30 / 2, |
| .t = (const struct fft_complex[]){ |
| {1.0000000e+00, -0.0000000e+00}, |
| {9.7814760e-01, -2.0791169e-01}, |
| {9.1354546e-01, -4.0673664e-01}, |
| {8.0901699e-01, -5.8778525e-01}, |
| {6.6913061e-01, -7.4314483e-01}, |
| {5.0000000e-01, -8.6602540e-01}, |
| {3.0901699e-01, -9.5105652e-01}, |
| {1.0452846e-01, -9.9452190e-01}, |
| {-1.0452846e-01, -9.9452190e-01}, |
| {-3.0901699e-01, -9.5105652e-01}, |
| {-5.0000000e-01, -8.6602540e-01}, |
| {-6.6913061e-01, -7.4314483e-01}, |
| {-8.0901699e-01, -5.8778525e-01}, |
| {-9.1354546e-01, -4.0673664e-01}, |
| {-9.7814760e-01, -2.0791169e-01}, |
| }}; |
| |
| static const struct fft_bf2_twiddles twiddles_40 = { |
| .n2 = 40 / 2, |
| .t = (const struct fft_complex[]){ |
| {1.0000000e+00, -0.0000000e+00}, {9.8768834e-01, -1.5643447e-01}, |
| {9.5105652e-01, -3.0901699e-01}, {8.9100652e-01, -4.5399050e-01}, |
| {8.0901699e-01, -5.8778525e-01}, {7.0710678e-01, -7.0710678e-01}, |
| {5.8778525e-01, -8.0901699e-01}, {4.5399050e-01, -8.9100652e-01}, |
| {3.0901699e-01, -9.5105652e-01}, {1.5643447e-01, -9.8768834e-01}, |
| {6.1232340e-17, -1.0000000e+00}, {-1.5643447e-01, -9.8768834e-01}, |
| {-3.0901699e-01, -9.5105652e-01}, {-4.5399050e-01, -8.9100652e-01}, |
| {-5.8778525e-01, -8.0901699e-01}, {-7.0710678e-01, -7.0710678e-01}, |
| {-8.0901699e-01, -5.8778525e-01}, {-8.9100652e-01, -4.5399050e-01}, |
| {-9.5105652e-01, -3.0901699e-01}, {-9.8768834e-01, -1.5643447e-01}, |
| }}; |
| |
| static const struct fft_bf2_twiddles twiddles_60 = { |
| .n2 = 60 / 2, |
| .t = (const struct fft_complex[]){ |
| {1.0000000e+00, -0.0000000e+00}, {9.9452190e-01, -1.0452846e-01}, |
| {9.7814760e-01, -2.0791169e-01}, {9.5105652e-01, -3.0901699e-01}, |
| {9.1354546e-01, -4.0673664e-01}, {8.6602540e-01, -5.0000000e-01}, |
| {8.0901699e-01, -5.8778525e-01}, {7.4314483e-01, -6.6913061e-01}, |
| {6.6913061e-01, -7.4314483e-01}, {5.8778525e-01, -8.0901699e-01}, |
| {5.0000000e-01, -8.6602540e-01}, {4.0673664e-01, -9.1354546e-01}, |
| {3.0901699e-01, -9.5105652e-01}, {2.0791169e-01, -9.7814760e-01}, |
| {1.0452846e-01, -9.9452190e-01}, {2.8327694e-16, -1.0000000e+00}, |
| {-1.0452846e-01, -9.9452190e-01}, {-2.0791169e-01, -9.7814760e-01}, |
| {-3.0901699e-01, -9.5105652e-01}, {-4.0673664e-01, -9.1354546e-01}, |
| {-5.0000000e-01, -8.6602540e-01}, {-5.8778525e-01, -8.0901699e-01}, |
| {-6.6913061e-01, -7.4314483e-01}, {-7.4314483e-01, -6.6913061e-01}, |
| {-8.0901699e-01, -5.8778525e-01}, {-8.6602540e-01, -5.0000000e-01}, |
| {-9.1354546e-01, -4.0673664e-01}, {-9.5105652e-01, -3.0901699e-01}, |
| {-9.7814760e-01, -2.0791169e-01}, {-9.9452190e-01, -1.0452846e-01}, |
| }}; |
| |
| static const struct fft_bf2_twiddles twiddles_80 = { |
| .n2 = 80 / 2, |
| .t = (const struct fft_complex[]){ |
| {1.0000000e+00, -0.0000000e+00}, {9.9691733e-01, -7.8459096e-02}, |
| {9.8768834e-01, -1.5643447e-01}, {9.7236992e-01, -2.3344536e-01}, |
| {9.5105652e-01, -3.0901699e-01}, {9.2387953e-01, -3.8268343e-01}, |
| {8.9100652e-01, -4.5399050e-01}, {8.5264016e-01, -5.2249856e-01}, |
| {8.0901699e-01, -5.8778525e-01}, {7.6040597e-01, -6.4944805e-01}, |
| {7.0710678e-01, -7.0710678e-01}, {6.4944805e-01, -7.6040597e-01}, |
| {5.8778525e-01, -8.0901699e-01}, {5.2249856e-01, -8.5264016e-01}, |
| {4.5399050e-01, -8.9100652e-01}, {3.8268343e-01, -9.2387953e-01}, |
| {3.0901699e-01, -9.5105652e-01}, {2.3344536e-01, -9.7236992e-01}, |
| {1.5643447e-01, -9.8768834e-01}, {7.8459096e-02, -9.9691733e-01}, |
| {6.1232340e-17, -1.0000000e+00}, {-7.8459096e-02, -9.9691733e-01}, |
| {-1.5643447e-01, -9.8768834e-01}, {-2.3344536e-01, -9.7236992e-01}, |
| {-3.0901699e-01, -9.5105652e-01}, {-3.8268343e-01, -9.2387953e-01}, |
| {-4.5399050e-01, -8.9100652e-01}, {-5.2249856e-01, -8.5264016e-01}, |
| {-5.8778525e-01, -8.0901699e-01}, {-6.4944805e-01, -7.6040597e-01}, |
| {-7.0710678e-01, -7.0710678e-01}, {-7.6040597e-01, -6.4944805e-01}, |
| {-8.0901699e-01, -5.8778525e-01}, {-8.5264016e-01, -5.2249856e-01}, |
| {-8.9100652e-01, -4.5399050e-01}, {-9.2387953e-01, -3.8268343e-01}, |
| {-9.5105652e-01, -3.0901699e-01}, {-9.7236992e-01, -2.3344536e-01}, |
| {-9.8768834e-01, -1.5643447e-01}, {-9.9691733e-01, -7.8459096e-02}, |
| }}; |
| |
| static const struct fft_bf2_twiddles twiddles_90 = { |
| .n2 = 90 / 2, |
| .t = (const struct fft_complex[]){ |
| {1.0000000e+00, -0.0000000e+00}, {9.9756405e-01, -6.9756474e-02}, |
| {9.9026807e-01, -1.3917310e-01}, {9.7814760e-01, -2.0791169e-01}, |
| {9.6126170e-01, -2.7563736e-01}, {9.3969262e-01, -3.4202014e-01}, |
| {9.1354546e-01, -4.0673664e-01}, {8.8294759e-01, -4.6947156e-01}, |
| {8.4804810e-01, -5.2991926e-01}, {8.0901699e-01, -5.8778525e-01}, |
| {7.6604444e-01, -6.4278761e-01}, {7.1933980e-01, -6.9465837e-01}, |
| {6.6913061e-01, -7.4314483e-01}, {6.1566148e-01, -7.8801075e-01}, |
| {5.5919290e-01, -8.2903757e-01}, {5.0000000e-01, -8.6602540e-01}, |
| {4.3837115e-01, -8.9879405e-01}, {3.7460659e-01, -9.2718385e-01}, |
| {3.0901699e-01, -9.5105652e-01}, {2.4192190e-01, -9.7029573e-01}, |
| {1.7364818e-01, -9.8480775e-01}, {1.0452846e-01, -9.9452190e-01}, |
| {3.4899497e-02, -9.9939083e-01}, {-3.4899497e-02, -9.9939083e-01}, |
| {-1.0452846e-01, -9.9452190e-01}, {-1.7364818e-01, -9.8480775e-01}, |
| {-2.4192190e-01, -9.7029573e-01}, {-3.0901699e-01, -9.5105652e-01}, |
| {-3.7460659e-01, -9.2718385e-01}, {-4.3837115e-01, -8.9879405e-01}, |
| {-5.0000000e-01, -8.6602540e-01}, {-5.5919290e-01, -8.2903757e-01}, |
| {-6.1566148e-01, -7.8801075e-01}, {-6.6913061e-01, -7.4314483e-01}, |
| {-7.1933980e-01, -6.9465837e-01}, {-7.6604444e-01, -6.4278761e-01}, |
| {-8.0901699e-01, -5.8778525e-01}, {-8.4804810e-01, -5.2991926e-01}, |
| {-8.8294759e-01, -4.6947156e-01}, {-9.1354546e-01, -4.0673664e-01}, |
| {-9.3969262e-01, -3.4202014e-01}, {-9.6126170e-01, -2.7563736e-01}, |
| {-9.7814760e-01, -2.0791169e-01}, {-9.9026807e-01, -1.3917310e-01}, |
| {-9.9756405e-01, -6.9756474e-02}, |
| }}; |
| |
| static const struct fft_bf2_twiddles twiddles_120 = { |
| .n2 = 120 / 2, |
| .t = (const struct fft_complex[]){ |
| {1.0000000e+00, -0.0000000e+00}, {9.9862953e-01, -5.2335956e-02}, |
| {9.9452190e-01, -1.0452846e-01}, {9.8768834e-01, -1.5643447e-01}, |
| {9.7814760e-01, -2.0791169e-01}, {9.6592583e-01, -2.5881905e-01}, |
| {9.5105652e-01, -3.0901699e-01}, {9.3358043e-01, -3.5836795e-01}, |
| {9.1354546e-01, -4.0673664e-01}, {8.9100652e-01, -4.5399050e-01}, |
| {8.6602540e-01, -5.0000000e-01}, {8.3867057e-01, -5.4463904e-01}, |
| {8.0901699e-01, -5.8778525e-01}, {7.7714596e-01, -6.2932039e-01}, |
| {7.4314483e-01, -6.6913061e-01}, {7.0710678e-01, -7.0710678e-01}, |
| {6.6913061e-01, -7.4314483e-01}, {6.2932039e-01, -7.7714596e-01}, |
| {5.8778525e-01, -8.0901699e-01}, {5.4463904e-01, -8.3867057e-01}, |
| {5.0000000e-01, -8.6602540e-01}, {4.5399050e-01, -8.9100652e-01}, |
| {4.0673664e-01, -9.1354546e-01}, {3.5836795e-01, -9.3358043e-01}, |
| {3.0901699e-01, -9.5105652e-01}, {2.5881905e-01, -9.6592583e-01}, |
| {2.0791169e-01, -9.7814760e-01}, {1.5643447e-01, -9.8768834e-01}, |
| {1.0452846e-01, -9.9452190e-01}, {5.2335956e-02, -9.9862953e-01}, |
| {2.8327694e-16, -1.0000000e+00}, {-5.2335956e-02, -9.9862953e-01}, |
| {-1.0452846e-01, -9.9452190e-01}, {-1.5643447e-01, -9.8768834e-01}, |
| {-2.0791169e-01, -9.7814760e-01}, {-2.5881905e-01, -9.6592583e-01}, |
| {-3.0901699e-01, -9.5105652e-01}, {-3.5836795e-01, -9.3358043e-01}, |
| {-4.0673664e-01, -9.1354546e-01}, {-4.5399050e-01, -8.9100652e-01}, |
| {-5.0000000e-01, -8.6602540e-01}, {-5.4463904e-01, -8.3867057e-01}, |
| {-5.8778525e-01, -8.0901699e-01}, {-6.2932039e-01, -7.7714596e-01}, |
| {-6.6913061e-01, -7.4314483e-01}, {-7.0710678e-01, -7.0710678e-01}, |
| {-7.4314483e-01, -6.6913061e-01}, {-7.7714596e-01, -6.2932039e-01}, |
| {-8.0901699e-01, -5.8778525e-01}, {-8.3867057e-01, -5.4463904e-01}, |
| {-8.6602540e-01, -5.0000000e-01}, {-8.9100652e-01, -4.5399050e-01}, |
| {-9.1354546e-01, -4.0673664e-01}, {-9.3358043e-01, -3.5836795e-01}, |
| {-9.5105652e-01, -3.0901699e-01}, {-9.6592583e-01, -2.5881905e-01}, |
| {-9.7814760e-01, -2.0791169e-01}, {-9.8768834e-01, -1.5643447e-01}, |
| {-9.9452190e-01, -1.0452846e-01}, {-9.9862953e-01, -5.2335956e-02}, |
| }}; |
| |
| static const struct fft_bf2_twiddles twiddles_160 = { |
| .n2 = 160 / 2, |
| .t = (const struct fft_complex[]){ |
| {1.0000000e+00, -0.0000000e+00}, {9.9922904e-01, -3.9259816e-02}, |
| {9.9691733e-01, -7.8459096e-02}, {9.9306846e-01, -1.1753740e-01}, |
| {9.8768834e-01, -1.5643447e-01}, {9.8078528e-01, -1.9509032e-01}, |
| {9.7236992e-01, -2.3344536e-01}, {9.6245524e-01, -2.7144045e-01}, |
| {9.5105652e-01, -3.0901699e-01}, {9.3819134e-01, -3.4611706e-01}, |
| {9.2387953e-01, -3.8268343e-01}, {9.0814317e-01, -4.1865974e-01}, |
| {8.9100652e-01, -4.5399050e-01}, {8.7249601e-01, -4.8862124e-01}, |
| {8.5264016e-01, -5.2249856e-01}, {8.3146961e-01, -5.5557023e-01}, |
| {8.0901699e-01, -5.8778525e-01}, {7.8531693e-01, -6.1909395e-01}, |
| {7.6040597e-01, -6.4944805e-01}, {7.3432251e-01, -6.7880075e-01}, |
| {7.0710678e-01, -7.0710678e-01}, {6.7880075e-01, -7.3432251e-01}, |
| {6.4944805e-01, -7.6040597e-01}, {6.1909395e-01, -7.8531693e-01}, |
| {5.8778525e-01, -8.0901699e-01}, {5.5557023e-01, -8.3146961e-01}, |
| {5.2249856e-01, -8.5264016e-01}, {4.8862124e-01, -8.7249601e-01}, |
| {4.5399050e-01, -8.9100652e-01}, {4.1865974e-01, -9.0814317e-01}, |
| {3.8268343e-01, -9.2387953e-01}, {3.4611706e-01, -9.3819134e-01}, |
| {3.0901699e-01, -9.5105652e-01}, {2.7144045e-01, -9.6245524e-01}, |
| {2.3344536e-01, -9.7236992e-01}, {1.9509032e-01, -9.8078528e-01}, |
| {1.5643447e-01, -9.8768834e-01}, {1.1753740e-01, -9.9306846e-01}, |
| {7.8459096e-02, -9.9691733e-01}, {3.9259816e-02, -9.9922904e-01}, |
| {6.1232340e-17, -1.0000000e+00}, {-3.9259816e-02, -9.9922904e-01}, |
| {-7.8459096e-02, -9.9691733e-01}, {-1.1753740e-01, -9.9306846e-01}, |
| {-1.5643447e-01, -9.8768834e-01}, {-1.9509032e-01, -9.8078528e-01}, |
| {-2.3344536e-01, -9.7236992e-01}, {-2.7144045e-01, -9.6245524e-01}, |
| {-3.0901699e-01, -9.5105652e-01}, {-3.4611706e-01, -9.3819134e-01}, |
| {-3.8268343e-01, -9.2387953e-01}, {-4.1865974e-01, -9.0814317e-01}, |
| {-4.5399050e-01, -8.9100652e-01}, {-4.8862124e-01, -8.7249601e-01}, |
| {-5.2249856e-01, -8.5264016e-01}, {-5.5557023e-01, -8.3146961e-01}, |
| {-5.8778525e-01, -8.0901699e-01}, {-6.1909395e-01, -7.8531693e-01}, |
| {-6.4944805e-01, -7.6040597e-01}, {-6.7880075e-01, -7.3432251e-01}, |
| {-7.0710678e-01, -7.0710678e-01}, {-7.3432251e-01, -6.7880075e-01}, |
| {-7.6040597e-01, -6.4944805e-01}, {-7.8531693e-01, -6.1909395e-01}, |
| {-8.0901699e-01, -5.8778525e-01}, {-8.3146961e-01, -5.5557023e-01}, |
| {-8.5264016e-01, -5.2249856e-01}, {-8.7249601e-01, -4.8862124e-01}, |
| {-8.9100652e-01, -4.5399050e-01}, {-9.0814317e-01, -4.1865974e-01}, |
| {-9.2387953e-01, -3.8268343e-01}, {-9.3819134e-01, -3.4611706e-01}, |
| {-9.5105652e-01, -3.0901699e-01}, {-9.6245524e-01, -2.7144045e-01}, |
| {-9.7236992e-01, -2.3344536e-01}, {-9.8078528e-01, -1.9509032e-01}, |
| {-9.8768834e-01, -1.5643447e-01}, {-9.9306846e-01, -1.1753740e-01}, |
| {-9.9691733e-01, -7.8459096e-02}, {-9.9922904e-01, -3.9259816e-02}, |
| }}; |
| |
| static const struct fft_bf2_twiddles twiddles_180 = { |
| .n2 = 180 / 2, |
| .t = (const struct fft_complex[]){ |
| {1.0000000e+00, -0.0000000e+00}, {9.9939083e-01, -3.4899497e-02}, |
| {9.9756405e-01, -6.9756474e-02}, {9.9452190e-01, -1.0452846e-01}, |
| {9.9026807e-01, -1.3917310e-01}, {9.8480775e-01, -1.7364818e-01}, |
| {9.7814760e-01, -2.0791169e-01}, {9.7029573e-01, -2.4192190e-01}, |
| {9.6126170e-01, -2.7563736e-01}, {9.5105652e-01, -3.0901699e-01}, |
| {9.3969262e-01, -3.4202014e-01}, {9.2718385e-01, -3.7460659e-01}, |
| {9.1354546e-01, -4.0673664e-01}, {8.9879405e-01, -4.3837115e-01}, |
| {8.8294759e-01, -4.6947156e-01}, {8.6602540e-01, -5.0000000e-01}, |
| {8.4804810e-01, -5.2991926e-01}, {8.2903757e-01, -5.5919290e-01}, |
| {8.0901699e-01, -5.8778525e-01}, {7.8801075e-01, -6.1566148e-01}, |
| {7.6604444e-01, -6.4278761e-01}, {7.4314483e-01, -6.6913061e-01}, |
| {7.1933980e-01, -6.9465837e-01}, {6.9465837e-01, -7.1933980e-01}, |
| {6.6913061e-01, -7.4314483e-01}, {6.4278761e-01, -7.6604444e-01}, |
| {6.1566148e-01, -7.8801075e-01}, {5.8778525e-01, -8.0901699e-01}, |
| {5.5919290e-01, -8.2903757e-01}, {5.2991926e-01, -8.4804810e-01}, |
| {5.0000000e-01, -8.6602540e-01}, {4.6947156e-01, -8.8294759e-01}, |
| {4.3837115e-01, -8.9879405e-01}, {4.0673664e-01, -9.1354546e-01}, |
| {3.7460659e-01, -9.2718385e-01}, {3.4202014e-01, -9.3969262e-01}, |
| {3.0901699e-01, -9.5105652e-01}, {2.7563736e-01, -9.6126170e-01}, |
| {2.4192190e-01, -9.7029573e-01}, {2.0791169e-01, -9.7814760e-01}, |
| {1.7364818e-01, -9.8480775e-01}, {1.3917310e-01, -9.9026807e-01}, |
| {1.0452846e-01, -9.9452190e-01}, {6.9756474e-02, -9.9756405e-01}, |
| {3.4899497e-02, -9.9939083e-01}, {6.1232340e-17, -1.0000000e+00}, |
| {-3.4899497e-02, -9.9939083e-01}, {-6.9756474e-02, -9.9756405e-01}, |
| {-1.0452846e-01, -9.9452190e-01}, {-1.3917310e-01, -9.9026807e-01}, |
| {-1.7364818e-01, -9.8480775e-01}, {-2.0791169e-01, -9.7814760e-01}, |
| {-2.4192190e-01, -9.7029573e-01}, {-2.7563736e-01, -9.6126170e-01}, |
| {-3.0901699e-01, -9.5105652e-01}, {-3.4202014e-01, -9.3969262e-01}, |
| {-3.7460659e-01, -9.2718385e-01}, {-4.0673664e-01, -9.1354546e-01}, |
| {-4.3837115e-01, -8.9879405e-01}, {-4.6947156e-01, -8.8294759e-01}, |
| {-5.0000000e-01, -8.6602540e-01}, {-5.2991926e-01, -8.4804810e-01}, |
| {-5.5919290e-01, -8.2903757e-01}, {-5.8778525e-01, -8.0901699e-01}, |
| {-6.1566148e-01, -7.8801075e-01}, {-6.4278761e-01, -7.6604444e-01}, |
| {-6.6913061e-01, -7.4314483e-01}, {-6.9465837e-01, -7.1933980e-01}, |
| {-7.1933980e-01, -6.9465837e-01}, {-7.4314483e-01, -6.6913061e-01}, |
| {-7.6604444e-01, -6.4278761e-01}, {-7.8801075e-01, -6.1566148e-01}, |
| {-8.0901699e-01, -5.8778525e-01}, {-8.2903757e-01, -5.5919290e-01}, |
| {-8.4804810e-01, -5.2991926e-01}, {-8.6602540e-01, -5.0000000e-01}, |
| {-8.8294759e-01, -4.6947156e-01}, {-8.9879405e-01, -4.3837115e-01}, |
| {-9.1354546e-01, -4.0673664e-01}, {-9.2718385e-01, -3.7460659e-01}, |
| {-9.3969262e-01, -3.4202014e-01}, {-9.5105652e-01, -3.0901699e-01}, |
| {-9.6126170e-01, -2.7563736e-01}, {-9.7029573e-01, -2.4192190e-01}, |
| {-9.7814760e-01, -2.0791169e-01}, {-9.8480775e-01, -1.7364818e-01}, |
| {-9.9026807e-01, -1.3917310e-01}, {-9.9452190e-01, -1.0452846e-01}, |
| {-9.9756405e-01, -6.9756474e-02}, {-9.9939083e-01, -3.4899497e-02}, |
| }}; |
| |
| static const struct fft_bf2_twiddles twiddles_240 = { |
| .n2 = 240 / 2, |
| .t = (const struct fft_complex[]){ |
| {1.0000000e+00, -0.0000000e+00}, {9.9965732e-01, -2.6176948e-02}, |
| {9.9862953e-01, -5.2335956e-02}, {9.9691733e-01, -7.8459096e-02}, |
| {9.9452190e-01, -1.0452846e-01}, {9.9144486e-01, -1.3052619e-01}, |
| {9.8768834e-01, -1.5643447e-01}, {9.8325491e-01, -1.8223553e-01}, |
| {9.7814760e-01, -2.0791169e-01}, {9.7236992e-01, -2.3344536e-01}, |
| {9.6592583e-01, -2.5881905e-01}, {9.5881973e-01, -2.8401534e-01}, |
| {9.5105652e-01, -3.0901699e-01}, {9.4264149e-01, -3.3380686e-01}, |
| {9.3358043e-01, -3.5836795e-01}, {9.2387953e-01, -3.8268343e-01}, |
| {9.1354546e-01, -4.0673664e-01}, {9.0258528e-01, -4.3051110e-01}, |
| {8.9100652e-01, -4.5399050e-01}, {8.7881711e-01, -4.7715876e-01}, |
| {8.6602540e-01, -5.0000000e-01}, {8.5264016e-01, -5.2249856e-01}, |
| {8.3867057e-01, -5.4463904e-01}, {8.2412619e-01, -5.6640624e-01}, |
| {8.0901699e-01, -5.8778525e-01}, {7.9335334e-01, -6.0876143e-01}, |
| {7.7714596e-01, -6.2932039e-01}, {7.6040597e-01, -6.4944805e-01}, |
| {7.4314483e-01, -6.6913061e-01}, {7.2537437e-01, -6.8835458e-01}, |
| {7.0710678e-01, -7.0710678e-01}, {6.8835458e-01, -7.2537437e-01}, |
| {6.6913061e-01, -7.4314483e-01}, {6.4944805e-01, -7.6040597e-01}, |
| {6.2932039e-01, -7.7714596e-01}, {6.0876143e-01, -7.9335334e-01}, |
| {5.8778525e-01, -8.0901699e-01}, {5.6640624e-01, -8.2412619e-01}, |
| {5.4463904e-01, -8.3867057e-01}, {5.2249856e-01, -8.5264016e-01}, |
| {5.0000000e-01, -8.6602540e-01}, {4.7715876e-01, -8.7881711e-01}, |
| {4.5399050e-01, -8.9100652e-01}, {4.3051110e-01, -9.0258528e-01}, |
| {4.0673664e-01, -9.1354546e-01}, {3.8268343e-01, -9.2387953e-01}, |
| {3.5836795e-01, -9.3358043e-01}, {3.3380686e-01, -9.4264149e-01}, |
| {3.0901699e-01, -9.5105652e-01}, {2.8401534e-01, -9.5881973e-01}, |
| {2.5881905e-01, -9.6592583e-01}, {2.3344536e-01, -9.7236992e-01}, |
| {2.0791169e-01, -9.7814760e-01}, {1.8223553e-01, -9.8325491e-01}, |
| {1.5643447e-01, -9.8768834e-01}, {1.3052619e-01, -9.9144486e-01}, |
| {1.0452846e-01, -9.9452190e-01}, {7.8459096e-02, -9.9691733e-01}, |
| {5.2335956e-02, -9.9862953e-01}, {2.6176948e-02, -9.9965732e-01}, |
| {2.8327694e-16, -1.0000000e+00}, {-2.6176948e-02, -9.9965732e-01}, |
| {-5.2335956e-02, -9.9862953e-01}, {-7.8459096e-02, -9.9691733e-01}, |
| {-1.0452846e-01, -9.9452190e-01}, {-1.3052619e-01, -9.9144486e-01}, |
| {-1.5643447e-01, -9.8768834e-01}, {-1.8223553e-01, -9.8325491e-01}, |
| {-2.0791169e-01, -9.7814760e-01}, {-2.3344536e-01, -9.7236992e-01}, |
| {-2.5881905e-01, -9.6592583e-01}, {-2.8401534e-01, -9.5881973e-01}, |
| {-3.0901699e-01, -9.5105652e-01}, {-3.3380686e-01, -9.4264149e-01}, |
| {-3.5836795e-01, -9.3358043e-01}, {-3.8268343e-01, -9.2387953e-01}, |
| {-4.0673664e-01, -9.1354546e-01}, {-4.3051110e-01, -9.0258528e-01}, |
| {-4.5399050e-01, -8.9100652e-01}, {-4.7715876e-01, -8.7881711e-01}, |
| {-5.0000000e-01, -8.6602540e-01}, {-5.2249856e-01, -8.5264016e-01}, |
| {-5.4463904e-01, -8.3867057e-01}, {-5.6640624e-01, -8.2412619e-01}, |
| {-5.8778525e-01, -8.0901699e-01}, {-6.0876143e-01, -7.9335334e-01}, |
| {-6.2932039e-01, -7.7714596e-01}, {-6.4944805e-01, -7.6040597e-01}, |
| {-6.6913061e-01, -7.4314483e-01}, {-6.8835458e-01, -7.2537437e-01}, |
| {-7.0710678e-01, -7.0710678e-01}, {-7.2537437e-01, -6.8835458e-01}, |
| {-7.4314483e-01, -6.6913061e-01}, {-7.6040597e-01, -6.4944805e-01}, |
| {-7.7714596e-01, -6.2932039e-01}, {-7.9335334e-01, -6.0876143e-01}, |
| {-8.0901699e-01, -5.8778525e-01}, {-8.2412619e-01, -5.6640624e-01}, |
| {-8.3867057e-01, -5.4463904e-01}, {-8.5264016e-01, -5.2249856e-01}, |
| {-8.6602540e-01, -5.0000000e-01}, {-8.7881711e-01, -4.7715876e-01}, |
| {-8.9100652e-01, -4.5399050e-01}, {-9.0258528e-01, -4.3051110e-01}, |
| {-9.1354546e-01, -4.0673664e-01}, {-9.2387953e-01, -3.8268343e-01}, |
| {-9.3358043e-01, -3.5836795e-01}, {-9.4264149e-01, -3.3380686e-01}, |
| {-9.5105652e-01, -3.0901699e-01}, {-9.5881973e-01, -2.8401534e-01}, |
| {-9.6592583e-01, -2.5881905e-01}, {-9.7236992e-01, -2.3344536e-01}, |
| {-9.7814760e-01, -2.0791169e-01}, {-9.8325491e-01, -1.8223553e-01}, |
| {-9.8768834e-01, -1.5643447e-01}, {-9.9144486e-01, -1.3052619e-01}, |
| {-9.9452190e-01, -1.0452846e-01}, {-9.9691733e-01, -7.8459096e-02}, |
| {-9.9862953e-01, -5.2335956e-02}, {-9.9965732e-01, -2.6176948e-02}, |
| }}; |
| |
| static const struct fft_bf3_twiddles twiddles_15 = { |
| .n3 = 15 / 3, |
| .t = (const struct fft_complex[][2]){ |
| {{1.0000000e+0, -0.0000000e+0}, {1.0000000e+0, -0.0000000e+0}}, |
| {{9.1354546e-1, -4.0673664e-1}, {6.6913061e-1, -7.4314483e-1}}, |
| {{6.6913061e-1, -7.4314483e-1}, {-1.0452846e-1, -9.9452190e-1}}, |
| {{3.0901699e-1, -9.5105652e-1}, {-8.0901699e-1, -5.8778525e-1}}, |
| {{-1.0452846e-1, -9.9452190e-1}, {-9.7814760e-1, 2.0791169e-1}}, |
| {{-5.0000000e-1, -8.6602540e-1}, {-5.0000000e-1, 8.6602540e-1}}, |
| {{-8.0901699e-1, -5.8778525e-1}, {3.0901699e-1, 9.5105652e-1}}, |
| {{-9.7814760e-1, -2.0791169e-1}, {9.1354546e-1, 4.0673664e-1}}, |
| {{-9.7814760e-1, 2.0791169e-1}, {9.1354546e-1, -4.0673664e-1}}, |
| {{-8.0901699e-1, 5.8778525e-1}, {3.0901699e-1, -9.5105652e-1}}, |
| {{-5.0000000e-1, 8.6602540e-1}, {-5.0000000e-1, -8.6602540e-1}}, |
| {{-1.0452846e-1, 9.9452190e-1}, {-9.7814760e-1, -2.0791169e-1}}, |
| {{3.0901699e-1, 9.5105652e-1}, {-8.0901699e-1, 5.8778525e-1}}, |
| {{6.6913061e-1, 7.4314483e-1}, {-1.0452846e-1, 9.9452190e-1}}, |
| {{9.1354546e-1, 4.0673664e-1}, {6.6913061e-1, 7.4314483e-1}}, |
| }}; |
| |
| static const struct fft_bf3_twiddles twiddles_45 = { |
| .n3 = 45 / 3, |
| .t = (const struct fft_complex[][2]){ |
| {{1.0000000e+0, -0.0000000e+0}, {1.0000000e+0, -0.0000000e+0}}, |
| {{9.9026807e-1, -1.3917310e-1}, {9.6126170e-1, -2.7563736e-1}}, |
| {{9.6126170e-1, -2.7563736e-1}, {8.4804810e-1, -5.2991926e-1}}, |
| {{9.1354546e-1, -4.0673664e-1}, {6.6913061e-1, -7.4314483e-1}}, |
| {{8.4804810e-1, -5.2991926e-1}, {4.3837115e-1, -8.9879405e-1}}, |
| {{7.6604444e-1, -6.4278761e-1}, {1.7364818e-1, -9.8480775e-1}}, |
| {{6.6913061e-1, -7.4314483e-1}, {-1.0452846e-1, -9.9452190e-1}}, |
| {{5.5919290e-1, -8.2903757e-1}, {-3.7460659e-1, -9.2718385e-1}}, |
| {{4.3837115e-1, -8.9879405e-1}, {-6.1566148e-1, -7.8801075e-1}}, |
| {{3.0901699e-1, -9.5105652e-1}, {-8.0901699e-1, -5.8778525e-1}}, |
| {{1.7364818e-1, -9.8480775e-1}, {-9.3969262e-1, -3.4202014e-1}}, |
| {{3.4899497e-2, -9.9939083e-1}, {-9.9756405e-1, -6.9756474e-2}}, |
| {{-1.0452846e-1, -9.9452190e-1}, {-9.7814760e-1, 2.0791169e-1}}, |
| {{-2.4192190e-1, -9.7029573e-1}, {-8.8294759e-1, 4.6947156e-1}}, |
| {{-3.7460659e-1, -9.2718385e-1}, {-7.1933980e-1, 6.9465837e-1}}, |
| {{-5.0000000e-1, -8.6602540e-1}, {-5.0000000e-1, 8.6602540e-1}}, |
| {{-6.1566148e-1, -7.8801075e-1}, {-2.4192190e-1, 9.7029573e-1}}, |
| {{-7.1933980e-1, -6.9465837e-1}, {3.4899497e-2, 9.9939083e-1}}, |
| {{-8.0901699e-1, -5.8778525e-1}, {3.0901699e-1, 9.5105652e-1}}, |
| {{-8.8294759e-1, -4.6947156e-1}, {5.5919290e-1, 8.2903757e-1}}, |
| {{-9.3969262e-1, -3.4202014e-1}, {7.6604444e-1, 6.4278761e-1}}, |
| {{-9.7814760e-1, -2.0791169e-1}, {9.1354546e-1, 4.0673664e-1}}, |
| {{-9.9756405e-1, -6.9756474e-2}, {9.9026807e-1, 1.3917310e-1}}, |
| {{-9.9756405e-1, 6.9756474e-2}, {9.9026807e-1, -1.3917310e-1}}, |
| {{-9.7814760e-1, 2.0791169e-1}, {9.1354546e-1, -4.0673664e-1}}, |
| {{-9.3969262e-1, 3.4202014e-1}, {7.6604444e-1, -6.4278761e-1}}, |
| {{-8.8294759e-1, 4.6947156e-1}, {5.5919290e-1, -8.2903757e-1}}, |
| {{-8.0901699e-1, 5.8778525e-1}, {3.0901699e-1, -9.5105652e-1}}, |
| {{-7.1933980e-1, 6.9465837e-1}, {3.4899497e-2, -9.9939083e-1}}, |
| {{-6.1566148e-1, 7.8801075e-1}, {-2.4192190e-1, -9.7029573e-1}}, |
| {{-5.0000000e-1, 8.6602540e-1}, {-5.0000000e-1, -8.6602540e-1}}, |
| {{-3.7460659e-1, 9.2718385e-1}, {-7.1933980e-1, -6.9465837e-1}}, |
| {{-2.4192190e-1, 9.7029573e-1}, {-8.8294759e-1, -4.6947156e-1}}, |
| {{-1.0452846e-1, 9.9452190e-1}, {-9.7814760e-1, -2.0791169e-1}}, |
| {{3.4899497e-2, 9.9939083e-1}, {-9.9756405e-1, 6.9756474e-2}}, |
| {{1.7364818e-1, 9.8480775e-1}, {-9.3969262e-1, 3.4202014e-1}}, |
| {{3.0901699e-1, 9.5105652e-1}, {-8.0901699e-1, 5.8778525e-1}}, |
| {{4.3837115e-1, 8.9879405e-1}, {-6.1566148e-1, 7.8801075e-1}}, |
| {{5.5919290e-1, 8.2903757e-1}, {-3.7460659e-1, 9.2718385e-1}}, |
| {{6.6913061e-1, 7.4314483e-1}, {-1.0452846e-1, 9.9452190e-1}}, |
| {{7.6604444e-1, 6.4278761e-1}, {1.7364818e-1, 9.8480775e-1}}, |
| {{8.4804810e-1, 5.2991926e-1}, {4.3837115e-1, 8.9879405e-1}}, |
| {{9.1354546e-1, 4.0673664e-1}, {6.6913061e-1, 7.4314483e-1}}, |
| {{9.6126170e-1, 2.7563736e-1}, {8.4804810e-1, 5.2991926e-1}}, |
| {{9.9026807e-1, 1.3917310e-1}, {9.6126170e-1, 2.7563736e-1}}, |
| }}; |
| |
| /** |
| * FFT 5 Points template |
| * s Sign -1: Forward 1: Inverse |
| * x, y Input and output coefficients, of size 5xn |
| * n Number of interleaved transform to perform |
| */ |
| static inline void xfft_5(const float s, const struct fft_complex* x, |
| struct fft_complex* y, int n) { |
| static const float cos1 = 0.3090169944; /* cos(-2Pi 1/5) */ |
| static const float cos2 = -0.8090169944; /* cos(-2Pi 2/5) */ |
| |
| static const float sin1 = -0.9510565163; /* sin(-2Pi 1/5) */ |
| static const float sin2 = -0.5877852523; /* sin(-2Pi 2/5) */ |
| |
| for (int i = 0; i < n; i++, x++, y += 5) { |
| struct fft_complex s14 = {x[1 * n].re + x[4 * n].re, |
| x[1 * n].im + x[4 * n].im}; |
| struct fft_complex d14 = {x[1 * n].re - x[4 * n].re, |
| x[1 * n].im - x[4 * n].im}; |
| |
| struct fft_complex s23 = {x[2 * n].re + x[3 * n].re, |
| x[2 * n].im + x[3 * n].im}; |
| struct fft_complex d23 = {x[2 * n].re - x[3 * n].re, |
| x[2 * n].im - x[3 * n].im}; |
| |
| y[0].re = x[0].re + s14.re + s23.re; |
| y[0].im = x[0].im + s14.im + s23.im; |
| |
| y[1].re = x[0].re + s14.re * cos1 + s * d14.im * sin1 + s23.re * cos2 + |
| s * d23.im * sin2; |
| |
| y[1].im = x[0].im + s14.im * cos1 - s * d14.re * sin1 + s23.im * cos2 - |
| s * d23.re * sin2; |
| |
| y[2].re = x[0].re + s14.re * cos2 + s * d14.im * sin2 + s23.re * cos1 - |
| s * d23.im * sin1; |
| |
| y[2].im = x[0].im + s14.im * cos2 - s * d14.re * sin2 + s23.im * cos1 + |
| s * d23.re * sin1; |
| |
| y[3].re = x[0].re + s14.re * cos2 - s * d14.im * sin2 + s23.re * cos1 + |
| s * d23.im * sin1; |
| |
| y[3].im = x[0].im + s14.im * cos2 + s * d14.re * sin2 + s23.im * cos1 - |
| s * d23.re * sin1; |
| |
| y[4].re = x[0].re + s14.re * cos1 - s * d14.im * sin1 + s23.re * cos2 - |
| s * d23.im * sin2; |
| |
| y[4].im = x[0].im + s14.im * cos1 + s * d14.re * sin1 + s23.im * cos2 + |
| s * d23.re * sin2; |
| } |
| } |
| |
| /** |
| * FFT Butterfly 3 Points template |
| * s Sign -1: Forward 1: Inverse |
| * x, y Input and output coefficients |
| * twiddles Twiddles factors, determine size of transform |
| * n Number of interleaved transforms |
| */ |
| static inline void xfft_bf3(const float s, |
| const struct fft_bf3_twiddles* twiddles, |
| const struct fft_complex* x, struct fft_complex* y, |
| int n) { |
| int n3 = twiddles->n3; |
| const struct fft_complex(*w0)[2] = twiddles->t; |
| const struct fft_complex(*w1)[2] = w0 + n3, (*w2)[2] = w1 + n3; |
| |
| const struct fft_complex *x0 = x, *x1 = x0 + n * n3, *x2 = x1 + n * n3; |
| struct fft_complex *y0 = y, *y1 = y0 + n3, *y2 = y1 + n3; |
| |
| for (int i = 0; i < n; i++, y0 += 3 * n3, y1 += 3 * n3, y2 += 3 * n3) { |
| for (int j = 0; j < n3; j++, x0++, x1++, x2++) { |
| y0[j].re = x0->re + x1->re * w0[j][0].re + s * x1->im * w0[j][0].im + |
| x2->re * w0[j][1].re + s * x2->im * w0[j][1].im; |
| |
| y0[j].im = x0->im + x1->im * w0[j][0].re - s * x1->re * w0[j][0].im + |
| x2->im * w0[j][1].re - s * x2->re * w0[j][1].im; |
| |
| y1[j].re = x0->re + x1->re * w1[j][0].re + s * x1->im * w1[j][0].im + |
| x2->re * w1[j][1].re + s * x2->im * w1[j][1].im; |
| |
| y1[j].im = x0->im + x1->im * w1[j][0].re - s * x1->re * w1[j][0].im + |
| x2->im * w1[j][1].re - s * x2->re * w1[j][1].im; |
| |
| y2[j].re = x0->re + x1->re * w2[j][0].re + s * x1->im * w2[j][0].im + |
| x2->re * w2[j][1].re + s * x2->im * w2[j][1].im; |
| |
| y2[j].im = x0->im + x1->im * w2[j][0].re - s * x1->re * w2[j][0].im + |
| x2->im * w2[j][1].re - s * x2->re * w2[j][1].im; |
| } |
| } |
| } |
| |
| /** |
| * FFT Butterfly 2 Points template |
| * s Sign -1: Forward 1: Inverse |
| * twiddles Twiddles factors, determine size of transform |
| * x, y Input and output coefficients |
| * n Number of interleaved transforms |
| */ |
| static inline void xfft_bf2(const float s, |
| const struct fft_bf2_twiddles* twiddles, |
| const struct fft_complex* x, struct fft_complex* y, |
| int n) { |
| int n2 = twiddles->n2; |
| const struct fft_complex* w = twiddles->t; |
| |
| const struct fft_complex *x0 = x, *x1 = x0 + n * n2; |
| struct fft_complex *y0 = y, *y1 = y0 + n2; |
| |
| for (int i = 0; i < n; i++, y0 += 2 * n2, y1 += 2 * n2) { |
| for (int j = 0; j < n2; j++, x0++, x1++) { |
| y0[j].re = x0->re + x1->re * w[j].re + s * x1->im * w[j].im; |
| y0[j].im = x0->im + x1->im * w[j].re - s * x1->re * w[j].im; |
| |
| y1[j].re = x0->re - x1->re * w[j].re - s * x1->im * w[j].im; |
| y1[j].im = x0->im - x1->im * w[j].re + s * x1->re * w[j].im; |
| } |
| } |
| } |
| |
| /** |
| * Forward FFT 5 Points |
| * x, y Input and output coefficients, of size 5xn |
| * n Number of interleaved transform to perform |
| */ |
| static void ffft_5(const struct fft_complex* x, struct fft_complex* y, int n) { |
| xfft_5(-1, x, y, n); |
| } |
| |
| /** |
| * Inverse FFT 5 Points |
| * x, y Input and output coefficients, of size 5xn |
| * n Number of interleaved transform to perform |
| */ |
| static void ifft_5(const struct fft_complex* x, struct fft_complex* y, int n) { |
| xfft_5(1, x, y, n); |
| } |
| |
| /** |
| * Forward FFT Butterfly 3 Points |
| * twiddles Twiddles factors, determine size of transform |
| * x, y Input and output coefficients |
| * n Number of interleaved transforms |
| */ |
| static void ffft_bf3(const struct fft_bf3_twiddles* twiddles, |
| const struct fft_complex* x, struct fft_complex* y, |
| int n) { |
| xfft_bf3(-1, twiddles, x, y, n); |
| } |
| |
| /** |
| * Inverse FFT Butterfly 3 Points |
| * twiddles Twiddles factors, determine size of transform |
| * x, y Input and output coefficients |
| * n Number of interleaved transforms |
| */ |
| static void ifft_bf3(const struct fft_bf3_twiddles* twiddles, |
| const struct fft_complex* x, struct fft_complex* y, |
| int n) { |
| xfft_bf3(1, twiddles, x, y, n); |
| } |
| |
| /** |
| * Forward FFT Butterfly 2 Points |
| * twiddles Twiddles factors, determine size of transform |
| * x, y Input and output coefficients |
| * n Number of interleaved transforms |
| */ |
| static void ffft_bf2(const struct fft_bf2_twiddles* twiddles, |
| const struct fft_complex* x, struct fft_complex* y, |
| int n) { |
| xfft_bf2(-1, twiddles, x, y, n); |
| } |
| |
| /** |
| * InverseIFFT Butterfly 2 Points |
| * twiddles Twiddles factors, determine size of transform |
| * x, y Input and output coefficients |
| * n Number of interleaved transforms |
| */ |
| static void ifft_bf2(const struct fft_bf2_twiddles* twiddles, |
| const struct fft_complex* x, struct fft_complex* y, |
| int n) { |
| xfft_bf2(1, twiddles, x, y, n); |
| } |
| |
| /** |
| * Perform FFT |
| * inverse True on inverse transform else forward |
| * x, y0, y1 Input, and 2 scratch buffers of size `n` |
| * n Number of points 30, 40, 60, 80, 90, 120, 160, 180, 240 |
| * return The buffer `y0` or `y1` that hold the result |
| * |
| * Input `x` can be the same as the `y0` second scratch buffer |
| */ |
| struct fft_complex* fft(bool inverse, const struct fft_complex* x, int n, |
| struct fft_complex* y0, struct fft_complex* y1) { |
| static const struct fft_bf3_twiddles* twiddles_bf3[] = {&twiddles_15, |
| &twiddles_45}; |
| |
| static const struct fft_bf2_twiddles* twiddles_bf2[][3] = { |
| {&twiddles_10, &twiddles_30, &twiddles_90}, |
| {&twiddles_20, &twiddles_60, &twiddles_180}, |
| {&twiddles_40, &twiddles_120}, |
| {&twiddles_80, &twiddles_240}, |
| {&twiddles_160}}; |
| |
| struct fft_complex* y[2] = {y1, y0}; |
| int i2, i3, is = 0; |
| |
| /* The number of points `n` can be decomposed as : |
| * |
| * n = 5^1 * 3^n3 * 2^n2 |
| * |
| * for n = 40, 80, 160 n3 = 0, n2 = [3..5] |
| * n = 30, 60, 120, 240 n3 = 1, n2 = [1..4] |
| * n = 90, 180 n3 = 2, n2 = [1..2] |
| * |
| * Note that the expression `n & (n-1) == 0` is equivalent |
| * to the check that `n` is a power of 2. */ |
| |
| (inverse ? ifft_5 : ffft_5)(x, y[is], n /= 5); |
| |
| for (i3 = 0; n & (n - 1); i3++, is ^= 1) |
| (inverse ? ifft_bf3 : ffft_bf3)(twiddles_bf3[i3], y[is], y[is ^ 1], n /= 3); |
| |
| for (i2 = 0; n > 1; i2++, is ^= 1) |
| (inverse ? ifft_bf2 : ffft_bf2)(twiddles_bf2[i2][i3], y[is], y[is ^ 1], |
| n >>= 1); |
| |
| return y[is]; |
| } |
