1 /* Copyright (C) 2005-2006 Jean-Marc Valin
2 File: fftwrap.c
3
4 Wrapper for various FFTs
5
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions
8 are met:
9
10 - Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
12
13 - Redistributions in binary form must reproduce the above copyright
14 notice, this list of conditions and the following disclaimer in the
15 documentation and/or other materials provided with the distribution.
16
17 - Neither the name of the Xiph.org Foundation nor the names of its
18 contributors may be used to endorse or promote products derived from
19 this software without specific prior written permission.
20
21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR
25 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32
33 */
34
35 #ifdef HAVE_CONFIG_H
36 #include "config.h"
37 #endif
38
39 /*#define USE_SMALLFT*/
40 #define USE_KISS_FFT
41
42
43 #include "arch.h"
44 #include "os_support.h"
45
46 #define MAX_FFT_SIZE 2048
47
48 #ifdef FIXED_POINT
maximize_range(spx_word16_t * in,spx_word16_t * out,spx_word16_t bound,int len)49 static int maximize_range(spx_word16_t *in, spx_word16_t *out, spx_word16_t bound, int len)
50 {
51 int i, shift;
52 spx_word16_t max_val = 0;
53 for (i=0;i<len;i++)
54 {
55 if (in[i]>max_val)
56 max_val = in[i];
57 if (-in[i]>max_val)
58 max_val = -in[i];
59 }
60 shift=0;
61 while (max_val <= (bound>>1) && max_val != 0)
62 {
63 max_val <<= 1;
64 shift++;
65 }
66 for (i=0;i<len;i++)
67 {
68 out[i] = SHL16(in[i], shift);
69 }
70 return shift;
71 }
72
renorm_range(spx_word16_t * in,spx_word16_t * out,int shift,int len)73 static void renorm_range(spx_word16_t *in, spx_word16_t *out, int shift, int len)
74 {
75 int i;
76 for (i=0;i<len;i++)
77 {
78 out[i] = PSHR16(in[i], shift);
79 }
80 }
81 #endif
82
83 #ifdef USE_SMALLFT
84
85 #include "smallft.h"
86 #include <math.h>
87
spx_fft_init(int size)88 void *spx_fft_init(int size)
89 {
90 struct drft_lookup *table;
91 table = speex_alloc(sizeof(struct drft_lookup));
92 spx_drft_init((struct drft_lookup *)table, size);
93 return (void*)table;
94 }
95
spx_fft_destroy(void * table)96 void spx_fft_destroy(void *table)
97 {
98 spx_drft_clear(table);
99 speex_free(table);
100 }
101
spx_fft(void * table,float * in,float * out)102 void spx_fft(void *table, float *in, float *out)
103 {
104 if (in==out)
105 {
106 int i;
107 float scale = 1./((struct drft_lookup *)table)->n;
108 speex_warning("FFT should not be done in-place");
109 for (i=0;i<((struct drft_lookup *)table)->n;i++)
110 out[i] = scale*in[i];
111 } else {
112 int i;
113 float scale = 1./((struct drft_lookup *)table)->n;
114 for (i=0;i<((struct drft_lookup *)table)->n;i++)
115 out[i] = scale*in[i];
116 }
117 spx_drft_forward((struct drft_lookup *)table, out);
118 }
119
spx_ifft(void * table,float * in,float * out)120 void spx_ifft(void *table, float *in, float *out)
121 {
122 if (in==out)
123 {
124 speex_warning("FFT should not be done in-place");
125 } else {
126 int i;
127 for (i=0;i<((struct drft_lookup *)table)->n;i++)
128 out[i] = in[i];
129 }
130 spx_drft_backward((struct drft_lookup *)table, out);
131 }
132
133 #elif defined(USE_KISS_FFT)
134
135 #include "kiss_fftr.h"
136 #include "kiss_fft.h"
137
138 struct kiss_config {
139 kiss_fftr_cfg forward;
140 kiss_fftr_cfg backward;
141 int N;
142 };
143
spx_fft_init(int size)144 void *spx_fft_init(int size)
145 {
146 struct kiss_config *table;
147 table = (struct kiss_config*)speex_alloc(sizeof(struct kiss_config));
148 table->forward = kiss_fftr_alloc(size,0,NULL,NULL);
149 table->backward = kiss_fftr_alloc(size,1,NULL,NULL);
150 table->N = size;
151 return table;
152 }
153
spx_fft_destroy(void * table)154 void spx_fft_destroy(void *table)
155 {
156 struct kiss_config *t = (struct kiss_config *)table;
157 kiss_fftr_free(t->forward);
158 kiss_fftr_free(t->backward);
159 speex_free(table);
160 }
161
162 #ifdef FIXED_POINT
163
spx_fft(void * table,spx_word16_t * in,spx_word16_t * out)164 void spx_fft(void *table, spx_word16_t *in, spx_word16_t *out)
165 {
166 int shift;
167 struct kiss_config *t = (struct kiss_config *)table;
168 shift = maximize_range(in, in, 32000, t->N);
169 kiss_fftr2(t->forward, in, out);
170 renorm_range(in, in, shift, t->N);
171 renorm_range(out, out, shift, t->N);
172 }
173
174 #else
175
spx_fft(void * table,spx_word16_t * in,spx_word16_t * out)176 void spx_fft(void *table, spx_word16_t *in, spx_word16_t *out)
177 {
178 int i;
179 float scale;
180 struct kiss_config *t = (struct kiss_config *)table;
181 scale = 1./t->N;
182 kiss_fftr2(t->forward, in, out);
183 for (i=0;i<t->N;i++)
184 out[i] *= scale;
185 }
186 #endif
187
spx_ifft(void * table,spx_word16_t * in,spx_word16_t * out)188 void spx_ifft(void *table, spx_word16_t *in, spx_word16_t *out)
189 {
190 struct kiss_config *t = (struct kiss_config *)table;
191 kiss_fftri2(t->backward, in, out);
192 }
193
194
195 #else
196
197 #error No other FFT implemented
198
199 #endif
200
201
202 #ifdef FIXED_POINT
203 /*#include "smallft.h"*/
204
205
spx_fft_float(void * table,float * in,float * out)206 void spx_fft_float(void *table, float *in, float *out)
207 {
208 int i;
209 #ifdef USE_SMALLFT
210 int N = ((struct drft_lookup *)table)->n;
211 #elif defined(USE_KISS_FFT)
212 int N = ((struct kiss_config *)table)->N;
213 #else
214 #endif
215 #ifdef VAR_ARRAYS
216 spx_word16_t _in[N];
217 spx_word16_t _out[N];
218 #else
219 spx_word16_t _in[MAX_FFT_SIZE];
220 spx_word16_t _out[MAX_FFT_SIZE];
221 #endif
222 for (i=0;i<N;i++)
223 _in[i] = (int)floor(.5+in[i]);
224 spx_fft(table, _in, _out);
225 for (i=0;i<N;i++)
226 out[i] = _out[i];
227 #if 0
228 if (!fixed_point)
229 {
230 float scale;
231 struct drft_lookup t;
232 spx_drft_init(&t, ((struct kiss_config *)table)->N);
233 scale = 1./((struct kiss_config *)table)->N;
234 for (i=0;i<((struct kiss_config *)table)->N;i++)
235 out[i] = scale*in[i];
236 spx_drft_forward(&t, out);
237 spx_drft_clear(&t);
238 }
239 #endif
240 }
241
spx_ifft_float(void * table,float * in,float * out)242 void spx_ifft_float(void *table, float *in, float *out)
243 {
244 int i;
245 #ifdef USE_SMALLFT
246 int N = ((struct drft_lookup *)table)->n;
247 #elif defined(USE_KISS_FFT)
248 int N = ((struct kiss_config *)table)->N;
249 #else
250 #endif
251 #ifdef VAR_ARRAYS
252 spx_word16_t _in[N];
253 spx_word16_t _out[N];
254 #else
255 spx_word16_t _in[MAX_FFT_SIZE];
256 spx_word16_t _out[MAX_FFT_SIZE];
257 #endif
258 for (i=0;i<N;i++)
259 _in[i] = (int)floor(.5+in[i]);
260 spx_ifft(table, _in, _out);
261 for (i=0;i<N;i++)
262 out[i] = _out[i];
263 #if 0
264 if (!fixed_point)
265 {
266 int i;
267 struct drft_lookup t;
268 spx_drft_init(&t, ((struct kiss_config *)table)->N);
269 for (i=0;i<((struct kiss_config *)table)->N;i++)
270 out[i] = in[i];
271 spx_drft_backward(&t, out);
272 spx_drft_clear(&t);
273 }
274 #endif
275 }
276
277 #else
278
spx_fft_float(void * table,float * in,float * out)279 void spx_fft_float(void *table, float *in, float *out)
280 {
281 spx_fft(table, in, out);
282 }
spx_ifft_float(void * table,float * in,float * out)283 void spx_ifft_float(void *table, float *in, float *out)
284 {
285 spx_ifft(table, in, out);
286 }
287
288 #endif
289