1/*
2 *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
3 *
4 *  Use of this source code is governed by a BSD-style license
5 *  that can be found in the LICENSE file in the root of the source
6 *  tree. An additional intellectual property rights grant can be found
7 *  in the file PATENTS.  All contributing project authors may
8 *  be found in the AUTHORS file in the root of the source tree.
9 */
10
11
12/*
13 * This file contains the function WebRtcSpl_ComplexFFT().
14 * The description header can be found in signal_processing_library.h
15 *
16 */
17
18#include "webrtc/common_audio/signal_processing/complex_fft_tables.h"
19#include "webrtc/common_audio/signal_processing/include/signal_processing_library.h"
20
21#define CFFTSFT 14
22#define CFFTRND 1
23#define CFFTRND2 16384
24
25#define CIFFTSFT 14
26#define CIFFTRND 1
27
28
29int WebRtcSpl_ComplexFFT(int16_t frfi[], int stages, int mode)
30{
31    int i, j, l, k, istep, n, m;
32    int16_t wr, wi;
33    int32_t tr32, ti32, qr32, qi32;
34
35    /* The 1024-value is a constant given from the size of kSinTable1024[],
36     * and should not be changed depending on the input parameter 'stages'
37     */
38    n = 1 << stages;
39    if (n > 1024)
40        return -1;
41
42    l = 1;
43    k = 10 - 1; /* Constant for given kSinTable1024[]. Do not change
44         depending on the input parameter 'stages' */
45
46    if (mode == 0)
47    {
48        // mode==0: Low-complexity and Low-accuracy mode
49        while (l < n)
50        {
51            istep = l << 1;
52
53            for (m = 0; m < l; ++m)
54            {
55                j = m << k;
56
57                /* The 256-value is a constant given as 1/4 of the size of
58                 * kSinTable1024[], and should not be changed depending on the input
59                 * parameter 'stages'. It will result in 0 <= j < N_SINE_WAVE/2
60                 */
61                wr = kSinTable1024[j + 256];
62                wi = -kSinTable1024[j];
63
64                for (i = m; i < n; i += istep)
65                {
66                    j = i + l;
67
68                    tr32 = WEBRTC_SPL_RSHIFT_W32((WEBRTC_SPL_MUL_16_16(wr, frfi[2 * j])
69                            - WEBRTC_SPL_MUL_16_16(wi, frfi[2 * j + 1])), 15);
70
71                    ti32 = WEBRTC_SPL_RSHIFT_W32((WEBRTC_SPL_MUL_16_16(wr, frfi[2 * j + 1])
72                            + WEBRTC_SPL_MUL_16_16(wi, frfi[2 * j])), 15);
73
74                    qr32 = (int32_t)frfi[2 * i];
75                    qi32 = (int32_t)frfi[2 * i + 1];
76                    frfi[2 * j] = (int16_t)WEBRTC_SPL_RSHIFT_W32(qr32 - tr32, 1);
77                    frfi[2 * j + 1] = (int16_t)WEBRTC_SPL_RSHIFT_W32(qi32 - ti32, 1);
78                    frfi[2 * i] = (int16_t)WEBRTC_SPL_RSHIFT_W32(qr32 + tr32, 1);
79                    frfi[2 * i + 1] = (int16_t)WEBRTC_SPL_RSHIFT_W32(qi32 + ti32, 1);
80                }
81            }
82
83            --k;
84            l = istep;
85
86        }
87
88    } else
89    {
90        // mode==1: High-complexity and High-accuracy mode
91        while (l < n)
92        {
93            istep = l << 1;
94
95            for (m = 0; m < l; ++m)
96            {
97                j = m << k;
98
99                /* The 256-value is a constant given as 1/4 of the size of
100                 * kSinTable1024[], and should not be changed depending on the input
101                 * parameter 'stages'. It will result in 0 <= j < N_SINE_WAVE/2
102                 */
103                wr = kSinTable1024[j + 256];
104                wi = -kSinTable1024[j];
105
106#ifdef WEBRTC_ARCH_ARM_V7
107                int32_t wri = 0;
108                __asm __volatile("pkhbt %0, %1, %2, lsl #16" : "=r"(wri) :
109                    "r"((int32_t)wr), "r"((int32_t)wi));
110#endif
111
112                for (i = m; i < n; i += istep)
113                {
114                    j = i + l;
115
116#ifdef WEBRTC_ARCH_ARM_V7
117                    register int32_t frfi_r;
118                    __asm __volatile(
119                        "pkhbt %[frfi_r], %[frfi_even], %[frfi_odd],"
120                        " lsl #16\n\t"
121                        "smlsd %[tr32], %[wri], %[frfi_r], %[cfftrnd]\n\t"
122                        "smladx %[ti32], %[wri], %[frfi_r], %[cfftrnd]\n\t"
123                        :[frfi_r]"=&r"(frfi_r),
124                         [tr32]"=&r"(tr32),
125                         [ti32]"=r"(ti32)
126                        :[frfi_even]"r"((int32_t)frfi[2*j]),
127                         [frfi_odd]"r"((int32_t)frfi[2*j +1]),
128                         [wri]"r"(wri),
129                         [cfftrnd]"r"(CFFTRND));
130#else
131                    tr32 = WEBRTC_SPL_MUL_16_16(wr, frfi[2 * j])
132                            - WEBRTC_SPL_MUL_16_16(wi, frfi[2 * j + 1]) + CFFTRND;
133
134                    ti32 = WEBRTC_SPL_MUL_16_16(wr, frfi[2 * j + 1])
135                            + WEBRTC_SPL_MUL_16_16(wi, frfi[2 * j]) + CFFTRND;
136#endif
137
138                    tr32 = WEBRTC_SPL_RSHIFT_W32(tr32, 15 - CFFTSFT);
139                    ti32 = WEBRTC_SPL_RSHIFT_W32(ti32, 15 - CFFTSFT);
140
141                    qr32 = ((int32_t)frfi[2 * i]) << CFFTSFT;
142                    qi32 = ((int32_t)frfi[2 * i + 1]) << CFFTSFT;
143
144                    frfi[2 * j] = (int16_t)WEBRTC_SPL_RSHIFT_W32(
145                            (qr32 - tr32 + CFFTRND2), 1 + CFFTSFT);
146                    frfi[2 * j + 1] = (int16_t)WEBRTC_SPL_RSHIFT_W32(
147                            (qi32 - ti32 + CFFTRND2), 1 + CFFTSFT);
148                    frfi[2 * i] = (int16_t)WEBRTC_SPL_RSHIFT_W32(
149                            (qr32 + tr32 + CFFTRND2), 1 + CFFTSFT);
150                    frfi[2 * i + 1] = (int16_t)WEBRTC_SPL_RSHIFT_W32(
151                            (qi32 + ti32 + CFFTRND2), 1 + CFFTSFT);
152                }
153            }
154
155            --k;
156            l = istep;
157        }
158    }
159    return 0;
160}
161
162int WebRtcSpl_ComplexIFFT(int16_t frfi[], int stages, int mode)
163{
164    int i, j, l, k, istep, n, m, scale, shift;
165    int16_t wr, wi;
166    int32_t tr32, ti32, qr32, qi32;
167    int32_t tmp32, round2;
168
169    /* The 1024-value is a constant given from the size of kSinTable1024[],
170     * and should not be changed depending on the input parameter 'stages'
171     */
172    n = 1 << stages;
173    if (n > 1024)
174        return -1;
175
176    scale = 0;
177
178    l = 1;
179    k = 10 - 1; /* Constant for given kSinTable1024[]. Do not change
180         depending on the input parameter 'stages' */
181
182    while (l < n)
183    {
184        // variable scaling, depending upon data
185        shift = 0;
186        round2 = 8192;
187
188        tmp32 = (int32_t)WebRtcSpl_MaxAbsValueW16(frfi, 2 * n);
189        if (tmp32 > 13573)
190        {
191            shift++;
192            scale++;
193            round2 <<= 1;
194        }
195        if (tmp32 > 27146)
196        {
197            shift++;
198            scale++;
199            round2 <<= 1;
200        }
201
202        istep = l << 1;
203
204        if (mode == 0)
205        {
206            // mode==0: Low-complexity and Low-accuracy mode
207            for (m = 0; m < l; ++m)
208            {
209                j = m << k;
210
211                /* The 256-value is a constant given as 1/4 of the size of
212                 * kSinTable1024[], and should not be changed depending on the input
213                 * parameter 'stages'. It will result in 0 <= j < N_SINE_WAVE/2
214                 */
215                wr = kSinTable1024[j + 256];
216                wi = kSinTable1024[j];
217
218                for (i = m; i < n; i += istep)
219                {
220                    j = i + l;
221
222                    tr32 = WEBRTC_SPL_RSHIFT_W32((WEBRTC_SPL_MUL_16_16_RSFT(wr, frfi[2 * j], 0)
223                            - WEBRTC_SPL_MUL_16_16_RSFT(wi, frfi[2 * j + 1], 0)), 15);
224
225                    ti32 = WEBRTC_SPL_RSHIFT_W32(
226                            (WEBRTC_SPL_MUL_16_16_RSFT(wr, frfi[2 * j + 1], 0)
227                                    + WEBRTC_SPL_MUL_16_16_RSFT(wi,frfi[2*j],0)), 15);
228
229                    qr32 = (int32_t)frfi[2 * i];
230                    qi32 = (int32_t)frfi[2 * i + 1];
231                    frfi[2 * j] = (int16_t)WEBRTC_SPL_RSHIFT_W32(qr32 - tr32, shift);
232                    frfi[2 * j + 1] = (int16_t)WEBRTC_SPL_RSHIFT_W32(qi32 - ti32, shift);
233                    frfi[2 * i] = (int16_t)WEBRTC_SPL_RSHIFT_W32(qr32 + tr32, shift);
234                    frfi[2 * i + 1] = (int16_t)WEBRTC_SPL_RSHIFT_W32(qi32 + ti32, shift);
235                }
236            }
237        } else
238        {
239            // mode==1: High-complexity and High-accuracy mode
240
241            for (m = 0; m < l; ++m)
242            {
243                j = m << k;
244
245                /* The 256-value is a constant given as 1/4 of the size of
246                 * kSinTable1024[], and should not be changed depending on the input
247                 * parameter 'stages'. It will result in 0 <= j < N_SINE_WAVE/2
248                 */
249                wr = kSinTable1024[j + 256];
250                wi = kSinTable1024[j];
251
252#ifdef WEBRTC_ARCH_ARM_V7
253                int32_t wri = 0;
254                __asm __volatile("pkhbt %0, %1, %2, lsl #16" : "=r"(wri) :
255                    "r"((int32_t)wr), "r"((int32_t)wi));
256#endif
257
258                for (i = m; i < n; i += istep)
259                {
260                    j = i + l;
261
262#ifdef WEBRTC_ARCH_ARM_V7
263                    register int32_t frfi_r;
264                    __asm __volatile(
265                      "pkhbt %[frfi_r], %[frfi_even], %[frfi_odd], lsl #16\n\t"
266                      "smlsd %[tr32], %[wri], %[frfi_r], %[cifftrnd]\n\t"
267                      "smladx %[ti32], %[wri], %[frfi_r], %[cifftrnd]\n\t"
268                      :[frfi_r]"=&r"(frfi_r),
269                       [tr32]"=&r"(tr32),
270                       [ti32]"=r"(ti32)
271                      :[frfi_even]"r"((int32_t)frfi[2*j]),
272                       [frfi_odd]"r"((int32_t)frfi[2*j +1]),
273                       [wri]"r"(wri),
274                       [cifftrnd]"r"(CIFFTRND)
275                    );
276#else
277
278                    tr32 = WEBRTC_SPL_MUL_16_16(wr, frfi[2 * j])
279                            - WEBRTC_SPL_MUL_16_16(wi, frfi[2 * j + 1]) + CIFFTRND;
280
281                    ti32 = WEBRTC_SPL_MUL_16_16(wr, frfi[2 * j + 1])
282                            + WEBRTC_SPL_MUL_16_16(wi, frfi[2 * j]) + CIFFTRND;
283#endif
284                    tr32 = WEBRTC_SPL_RSHIFT_W32(tr32, 15 - CIFFTSFT);
285                    ti32 = WEBRTC_SPL_RSHIFT_W32(ti32, 15 - CIFFTSFT);
286
287                    qr32 = ((int32_t)frfi[2 * i]) << CIFFTSFT;
288                    qi32 = ((int32_t)frfi[2 * i + 1]) << CIFFTSFT;
289
290                    frfi[2 * j] = (int16_t)WEBRTC_SPL_RSHIFT_W32((qr32 - tr32+round2),
291                                                                       shift+CIFFTSFT);
292                    frfi[2 * j + 1] = (int16_t)WEBRTC_SPL_RSHIFT_W32(
293                            (qi32 - ti32 + round2), shift + CIFFTSFT);
294                    frfi[2 * i] = (int16_t)WEBRTC_SPL_RSHIFT_W32((qr32 + tr32 + round2),
295                                                                       shift + CIFFTSFT);
296                    frfi[2 * i + 1] = (int16_t)WEBRTC_SPL_RSHIFT_W32(
297                            (qi32 + ti32 + round2), shift + CIFFTSFT);
298                }
299            }
300
301        }
302        --k;
303        l = istep;
304    }
305    return scale;
306}
307