summaryrefslogtreecommitdiff
path: root/system/embdrv/lc3_dec/Common/fft/fft.c
diff options
context:
space:
mode:
Diffstat (limited to 'system/embdrv/lc3_dec/Common/fft/fft.c')
-rw-r--r--system/embdrv/lc3_dec/Common/fft/fft.c677
1 files changed, 0 insertions, 677 deletions
diff --git a/system/embdrv/lc3_dec/Common/fft/fft.c b/system/embdrv/lc3_dec/Common/fft/fft.c
deleted file mode 100644
index d684302938..0000000000
--- a/system/embdrv/lc3_dec/Common/fft/fft.c
+++ /dev/null
@@ -1,677 +0,0 @@
-/******************************************************************************
- *
- * 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];
-}
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-03 16:35:19 +0000