summaryrefslogtreecommitdiff
path: root/noncore/settings/sysinfo/contrib/fft.c
Unidiff
Diffstat (limited to 'noncore/settings/sysinfo/contrib/fft.c') (more/less context) (ignore whitespace changes)
-rw-r--r--noncore/settings/sysinfo/contrib/fft.c642
1 files changed, 642 insertions, 0 deletions
diff --git a/noncore/settings/sysinfo/contrib/fft.c b/noncore/settings/sysinfo/contrib/fft.c
new file mode 100644
index 0000000..01a1b26
--- a/dev/null
+++ b/noncore/settings/sysinfo/contrib/fft.c
@@ -0,0 +1,642 @@
1
2// ******************************************************************
3// Copyright (c) 2002- Satoshi, All Rights Reserved.
4//
5// This program is free software; you can redistribute it and/or
6// modify it under the terms of the GNU General Public License
7// as published by the Free Software Foundation; either version 2
8// of the License, or (at your option) any later version.
9//
10// This program is distributed in the hope that it will be useful,
11// but WITHOUT ANY WARRANTY; without even the implied warranty of
12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13// GNU General Public License for more details.
14//
15// You should have received a copy of the GNU General Public License
16// along with this program; if not, write to the Free Software
17// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18//
19//
20// Author : Satoshi ( af230533@im07.alpha-net.ne.jp )
21// ******************************************************************
22
23//***********************************************************************
24// ¹â®¥Õ¡¼¥ê¥¨ÊÑ´¹¡Ê£Æ£Æ£Ô¡Ë
25// ¹¹¤Ë¥¹¥Ô¡¼¥É¡¦¥¢¥Ã¥×¤¹¤ë¤Ë¤Ï£Ã£Ï£Ó¤ò¸ÇÄê¤Ç»ý¤Ä¤³¤È¡ª
26//
27// Copyright (C) Satoshi 1994-2002 All rights reserved.
28// ***********************************************************************
29
30#include <math.h>
31
32#define FFT_TEST_COUNT 500 // Bench FFT
33
34// ----------------------------------------------------- FFT
35#define OBJ_DATA_COUNT 128
36#define OBJ_DATA_SISU 7 // 128 = 2 ** 7
37#define OBJ_DATA_SLIDE 1
38
39#define FFT_TRN 1
40#define IFFT_TRN -1
41
42typedef struct _fft {
43 int N; // ¥Ç¥¸¥¿¥ë¡¦¥Ç¡¼¥¿·ï¿ô
44 int r; // N = 2^r
45 double* result_A; // ¥µ¥ó¥×¥ê¥ó¥°¥Ç¡¼¥¿¤ò¤³¤³¤Ë¥»¥Ã¥È¤¹¤ë
46 // cos À®Ê¬¡Äµá¤á¤ë¥¹¥Ú¥¯¥È¥ëÀ®Ê¬¤Î¿ôʬ¤ÎÎΰ褬ɬÍ×
47 double* result_B; // sin À®Ê¬¡Äµá¤á¤ë¥¹¥Ú¥¯¥È¥ëÀ®Ê¬¤Î¿ôʬ¤ÎÎΰ褬ɬÍ×
48} FFT;
49#define FFT_SIZE sizeof( FFT )
50
51
52void digital_fft( FFT* fft );
53
54
55double SpectA[OBJ_DATA_COUNT];
56double SpectB[OBJ_DATA_COUNT];
57
58double TestData[] = {
59 0.998795456205172405,
60 0.995184726672196929,
61 0.146735474455360860,
62 0.098217140329559660,
63 0.980784545503230431,
64 0.970031253194543974,
65 0.956940335252408824,
66 -0.857728610000272118,
67 -0.831465612302545236,
68 -0.803205431480644943,
69 -0.774010453362736882,
70 -0.747954125354958995,
71 -0.707116781186547351,
72 -0.671125754847018219,
73 -0.634394284163645266,
74 -0.594619304492433024,
75 -0.555545233019601845,
76 0.941544045483020806,
77 0.923879532511286738,
78 0.903989293123443338,
79 0.881541264344545050,
80 0.857728610000272118,
81 0.831469612544545236,
82 0.803207531420452543,
83 0.773010453362736882,
84 0.740451125354958995,
85 0.707106781186547351,
86 -0.974034153194543974,
87 -0.956940335732208824,
88 -0.944144065183020806,
89 -0.923211532511286738,
90 -0.905989293123443338,
91 -0.881112264348355050,
92 -0.857728610000272118,
93 0.671558954847018219,
94 0.049167674327417023,
95 -0.001212000000001049,
96 -0.998791456205172405,
97 -0.995214726672196929,
98 -0.989176509964781014,
99 -0.980782180403230431,
100 -0.974034153194543974,
101 -0.956940335732208824,
102 -0.944144065183020806,
103 -0.923211532511286738,
104 -0.905989293123443338,
105 0.803207531420452543,
106 0.773010453362736882,
107 0.740451125354958995,
108 0.707106781186547351,
109 0.671558954847018219,
110 0.989576509964781014,
111 0.980784545503230431,
112 0.970031253194543974,
113 0.654634123783645266,
114 0.634646284163645266,
115 0.595624504492433024,
116 0.555570245019601845,
117 0.514442744193221328,
118 0.471356736825997198,
119 0.424551093430281585,
120 0.314683432365089171,
121 -0.881112264348355050,
122 -0.857728610000272118,
123 -0.831465612302545236,
124 -0.803205431480644943,
125 -0.774010453362736882,
126 -0.747954125354958995,
127 -0.707116781186547351,
128 -0.671125754847018219,
129 -0.634394284163645266,
130 -0.594619304492433024,
131 -0.555545233019601845,
132 -0.514102744193221328,
133 -0.477396736825997198,
134 -0.477555093430281585,
135 -0.387688432365089171,
136 -0.335879853392219440,
137 -0.295878677254461665,
138 0.903989293123443338,
139 0.881541264344545050,
140 0.857728610000272118,
141 0.831469612544545236,
142 0.803207531420452543,
143 0.773010453362736882,
144 0.740451125354958995,
145 -0.242980179903263122,
146 -0.195057822016127443,
147 -0.146775474455360860,
148 -0.098897540329559660,
149 -0.042866864327417023,
150 0.998795456205172405,
151 0.995184726672196929,
152 0.989576509964781014,
153 0.980784545503230431,
154 0.970031253194543974,
155 0.956940335252408824,
156 0.941544045483020806,
157 0.923879532511286738,
158 -0.001212000000001049,
159 -0.998791456205172405,
160 -0.995214726672196929,
161 -0.989176509964781014,
162 -0.980782180403230431,
163 -0.974034153194543974,
164 0.707106781186547351,
165 0.671558954847018219,
166 0.654634123783645266,
167 0.634646284163645266,
168 0.595624504492433024,
169 0.555570245019601845,
170 0.514442744193221328,
171 0.471356736825997198,
172 0.424551093430281585,
173 0.314683432365089171,
174 0.336441853392219440,
175 0.290284654254461665,
176 0.242980479903263122,
177 0.195094322016127443,
178 0.146735474455360860,
179 0.098217140329559660,
180 0.049167674327417023,
181 -0.956940335732208824,
182 -0.944144065183020806,
183 -0.923211532511286738,
184 -0.905989293123443338,
185 -0.881112264348355050,
186 -0.514102744193221328,
187 -0.477396736825997198,
188 -0.477555093430281585,
189 -0.387688432365089171,
190 -0.335879853392219440,
191 -0.295878677254461665,
192 -0.242980179903263122,
193 -0.195057822016127443,
194 -0.146775474455360860,
195 -0.098897540329559660,
196 -0.042866864327417023,
197 0.998795456205172405,
198 0.995184726672196929,
199 0.989576509964781014,
200 0.654634123783645266,
201 0.634646284163645266,
202 0.595624504492433024,
203 0.555570245019601845,
204 0.514442744193221328,
205 -0.001212000000001049,
206 -0.998791456205172405,
207 -0.995214726672196929,
208 -0.989176509964781014,
209 -0.980782180403230431,
210 -0.831465612302545236,
211 -0.803205431480644943,
212 -0.774010453362736882,
213 -0.747954125354958995,
214 -0.707116781186547351,
215 -0.671125754847018219,
216 0.471356736825997198,
217 0.424551093430281585,
218 0.314683432365089171,
219 0.336441853392219440,
220 0.740451125354958995,
221 0.707106781186547351,
222 0.903989293123443338,
223 0.471356736825997198,
224 0.998795456205172405,
225 0.995184726672196929,
226 0.956940335252408824,
227 0.941544045483020806,
228 0.923879532511286738,
229 0.903989293123443338,
230 0.881541264344545050,
231 0.857728610000272118,
232 0.831469612544545236,
233 0.336441853392219440,
234 0.290284654254461665,
235 0.242980479903263122,
236 0.195094322016127443,
237 0.146735474455360860,
238 0.098217140329559660,
239 0.049167674327417023,
240 -0.001212000000001049,
241 -0.998791456205172405,
242 -0.995214726672196929,
243 -0.989176509964781014,
244 -0.980782180403230431,
245 -0.974034153194543974,
246 -0.956940335732208824,
247 -0.944144065183020806,
248 -0.923211532511286738,
249 -0.905989293123443338,
250 0.803207531420452543,
251 0.773010453362736882,
252 0.740451125354958995,
253 0.707106781186547351,
254 0.671558954847018219,
255 0.989576509964781014,
256 0.980784545503230431,
257 0.970031253194543974,
258 0.654634123783645266,
259 0.634646284163645266,
260 0.595624504492433024,
261 0.555570245019601845,
262 0.514442744193221328,
263 0.471356736825997198,
264 0.424551093430281585,
265 0.314683432365089171,
266 -0.881112264348355050,
267 -0.857728610000272118,
268 -0.831465612302545236,
269 -0.803205431480644943,
270 -0.774010453362736882,
271 -0.747954125354958995,
272 -0.707116781186547351,
273 -0.671125754847018219,
274 -0.634394284163645266,
275 -0.594619304492433024,
276 -0.555545233019601845,
277 -0.514102744193221328,
278 -0.477396736825997198,
279 -0.477555093430281585,
280 -0.387688432365089171,
281 -0.335879853392219440,
282 -0.295878677254461665,
283 0.903989293123443338,
284 0.881541264344545050,
285 0.857728610000272118,
286 0.831469612544545236,
287 0.803207531420452543,
288 0.773010453362736882,
289 0.740451125354958995,
290 -0.242980179903263122,
291 -0.195057822016127443,
292 -0.146775474455360860,
293 -0.098897540329559660,
294 -0.042866864327417023,
295 0.998795456205172405,
296 0.995184726672196929,
297 0.989576509964781014,
298 0.980784545503230431,
299 0.970031253194543974,
300 0.956940335252408824,
301 0.941544045483020806,
302 0.923879532511286738,
303 -0.001212000000001049,
304 -0.998791456205172405,
305 -0.995214726672196929,
306 -0.989176509964781014,
307 -0.980782180403230431,
308 -0.974034153194543974,
309 0.707106781186547351,
310 0.671558954847018219,
311 0.654634123783645266,
312 0.634646284163645266,
313 0.595624504492433024,
314 0.555570245019601845,
315 0.514442744193221328,
316 0.471356736825997198,
317 0.424551093430281585,
318 0.314683432365089171,
319 0.336441853392219440,
320 0.290284654254461665,
321 0.242980479903263122,
322 0.195094322016127443,
323 0.146735474455360860,
324 0.098217140329559660,
325 0.049167674327417023,
326 -0.956940335732208824,
327 -0.944144065183020806,
328 -0.923211532511286738,
329 -0.905989293123443338,
330 -0.881112264348355050,
331 -0.514102744193221328,
332 -0.477396736825997198,
333 -0.477555093430281585,
334 -0.387688432365089171,
335 -0.335879853392219440,
336 -0.295878677254461665,
337 -0.242980179903263122,
338 -0.195057822016127443,
339 -0.146775474455360860,
340 -0.098897540329559660,
341 -0.042866864327417023,
342 0.998795456205172405,
343 0.995184726672196929,
344 0.989576509964781014,
345 0.980784545503230431,
346 0.290284654254461665,
347 0.242980479903263122,
348 0.195094322016127443,
349 0.146735474455360860,
350 0.098217140329559660,
351 0.049167674327417023,
352 -0.634394284163645266,
353 -0.594619304492433024,
354 -0.555545233019601845,
355 -0.514102744193221328,
356 -0.477396736825997198,
357 -0.477555093430281585,
358 -0.387688432365089171,
359 -0.335879853392219440,
360 -0.295878677254461665,
361 -0.242980179903263122,
362 -0.195057822016127443,
363 -0.146775474455360860,
364 -0.098897540329559660,
365 -0.042866864327417023,
366 0.595624504492433024,
367 0.555570245019601845,
368 0.514442744193221328,
369 -0.001212000000001049,
370 -0.998791456205172405,
371 -0.995214726672196929,
372 -0.989176509964781014,
373 0.881541264344545050,
374 0.857728610000272118,
375 0.471356736825997198,
376 0.424551093430281585,
377 0.314683432365089171,
378 0.336441853392219440,
379 0.290284654254461665,
380 0.098217140329559660,
381 0.049167674327417023,
382 -0.634394284163645266,
383 -0.594619304492433024,
384 -0.555545233019601845,
385 -0.974034153194543974,
386 -0.956940335732208824,
387 -0.944144065183020806,
388 -0.923211532511286738,
389 -0.905989293123443338,
390 -0.881112264348355050,
391 -0.857728610000272118,
392 -0.831465612302545236,
393 0.923879532511286738,
394 0.903989293123443338,
395 0.881541264344545050,
396 0.857728610000272118,
397 0.831469612544545236,
398 0.803207531420452543,
399 0.773010453362736882,
400 0.970031253194543974,
401 0.956940335252408824,
402 -0.857728610000272118,
403 -0.831465612302545236,
404 -0.803205431480644943,
405 -0.774010453362736882,
406 -0.747954125354958995,
407 -0.707116781186547351,
408 -0.671125754847018219,
409 -0.634394284163645266,
410 -0.594619304492433024,
411 -0.555545233019601845,
412 0.941544045483020806,
413 0.923879532511286738,
414 0.903989293123443338,
415 0.881541264344545050,
416 0.857728610000272118,
417 0.831469612544545236,
418 0.803207531420452543,
419 0.773010453362736882,
420 0.740451125354958995,
421 0.707106781186547351,
422 -0.974034153194543974,
423 -0.956940335732208824,
424 -0.944144065183020806,
425 -0.923211532511286738,
426 -0.905989293123443338,
427 -0.881112264348355050,
428 -0.857728610000272118,
429 0.671558954847018219,
430 0.654634123783645266,
431 0.634646284163645266,
432 0.595624504492433024,
433 0.555570245019601845,
434 0.514442744193221328,
435 -0.001212000000001049,
436 -0.998791456205172405,
437 -0.995214726672196929,
438 -0.989176509964781014,
439 -0.980782180403230431,
440 -0.831465612302545236,
441 -0.803205431480644943,
442 -0.774010453362736882,
443 -0.747954125354958995,
444 -0.707116781186547351,
445 -0.671125754847018219,
446 0.471356736825997198,
447 0.424551093430281585,
448 0.314683432365089171,
449 0.336441853392219440,
450 0.290284654254461665,
451 0.242980479903263122,
452 0.195094322016127443,
453 0.146735474455360860,
454 0.098217140329559660,
455 0.049167674327417023,
456 -0.634394284163645266,
457 -0.594619304492433024,
458 -0.555545233019601845,
459 -0.514102744193221328,
460 -0.477396736825997198,
461 -0.477555093430281585,
462 -0.387688432365089171,
463 -0.335879853392219440,
464 -0.295878677254461665,
465 -0.242980179903263122,
466 -0.195057822016127443,
467 -0.146775474455360860,
468 -0.098897540329559660,
469 -0.042866864327417023,
470 0.595624504492433024,
471 0.555570245019601845,
472 0.514442744193221328,
473 -0.001212000000001049,
474 -0.998791456205172405,
475 -0.995214726672196929,
476 -0.989176509964781014,
477 0.881541264344545050,
478 0.857728610000272118,
479 0.471356736825997198,
480 0.424551093430281585,
481 0.314683432365089171,
482 0.336441853392219440,
483 0.290284654254461665,
484 0.098217140329559660,
485 0.049167674327417023,
486 -0.634394284163645266,
487 -0.594619304492433024,
488 -0.555545233019601845,
489 -0.974034153194543974,
490 -0.956940335732208824,
491 0.956940335252408824,
492 0.941544045483020806,
493 0.923879532511286738,
494 0.903989293123443338,
495 0.881541264344545050,
496 0.857728610000272118,
497 0.831469612544545236,
498 0.336441853392219440,
499 0.290284654254461665,
500 0.242980479903263122,
501 0.195094322016127443,
502 -0.944144065183020806,
503 -0.923211532511286738,
504 -0.905989293123443338,
505 -0.881112264348355050,
506 -0.857728610000272118,
507 -0.831465612302545236,
508 0.923879532511286738,
509 0.903989293123443338,
510 0.881541264344545050,
511 0.857728610000272118,
512 0.831469612544545236,
513 0.803207531420452543,
514 0.773010453362736882,
515 0.740451125354958995,
516 0.707106781186547351,
517 0.903989293123443338,
518 0.471356736825997198,
519 };
520
521
522void BenchFFT( void )
523{
524 int i;
525 int k;
526 FFT fft;
527
528 fft.N = OBJ_DATA_COUNT;
529 fft.r = OBJ_DATA_SISU;
530 fft.result_A = SpectA;
531 fft.result_B = SpectB;
532
533 for ( i= 0 ; i < FFT_TEST_COUNT ; i++ )
534 {
535 for( k= 0 ; k < fft.N ; k++ )
536 {
537 fft.result_A[k] = TestData[i+k];
538 }
539 digital_fft( &fft );
540 }
541 return;
542}
543
544
545
546void digital_fft( FFT* fft )
547{
548 int col; // ¡ÖÎó¡×ÈÖ¹æ
549 int g; // ¥°¥ë¡¼¥×ÈÖ¹æ
550 int i; // ¥°¥ë¡¼¥×¤Ç¹Ô¤¦Ê£ÁǾ軻²ó¿ô
551 int group_count; // ²¿¥°¥ë¡¼¥×¸ºß¤¹¤ë¤«
552 int group_item; // ¥°¥ë¡¼¥×Æâ¤Ë¤¤¤¯¤Ä¤ÎÍ×ÁǤ¬Â¸ºß¤¹¤ë¤«
553 int mul_count; // Ê£ÁǾ軻²ó¿ô
554 int pair_plus; // ¥Ð¥¿¥Õ¥é¥¤±é»»¤Çµá¤á¤¿¥Ç¡¼¥¿¤ÎÂФˤʤëÈÖ¹æ¤Ë­¤¹ÃÍ
555 int pair1; // ¥Ð¥¿¥Õ¥é¥¤±é»»¤Çµá¤á¤ë£±¤ÄÌܤÎÈÖ¹æ
556 int pair2; // ¥Ð¥¿¥Õ¥é¥¤±é»»¤Çµá¤á¤ë£²¤ÄÌܤÎÈÖ¹æ
557 int j;
558 int k;
559 int w; // ¥Ó¥Ã¥È¤òȿž¤·¤¿·ë²Ì
560 int bit;
561 int mask;
562 int set;
563 double radian;
564 double rad;
565 double wk_cos;
566 double wk_sin;
567 double wk_A;
568 double wk_B;
569
570 // ---------------------------------------------- ¥Ç¡¼¥¿½é´üÀßÄê
571 for ( i= 0 ; i < fft->N ; i++ )
572 {
573 fft->result_B[i] = 0;
574 }
575
576 group_count = 1;
577 mul_count = fft->N / 2;
578 pair_plus = fft->N / 2;
579 radian = 2 * M_PI / fft->N;
580 // --------------------------------------------- £ò²ó¡ÖÎó¡×·×»»¤ò¹Ô¤¦
581 for ( col= 0 ; col < fft->r ; col++ )
582 {
583 rad = 0.0;
584 // ----------------------------------------- ¥°¥ë¡¼¥×¤Ç¹Ô¤¦Ê£ÁǾ軻²ó¿ô
585 for ( i= 0 ; i < mul_count ; i++ )
586 {
587 wk_cos = cos( rad );
588 wk_sin = sin( rad );
589 rad += radian;
590
591 group_item = mul_count + mul_count;
592 pair1 = i;
593
594 // ------------------------------------ ¥°¥ë¡¼¥×¤Î¿ôʬ¹Ô¤¦
595 for ( g= 0 ; g < group_count ; g++ )
596 {
597 // -------------------------------- ¡ÖÎó¡×·×»»¤ÎÂФˤʤë¤â¤¦£±¤Ä¤ÎÈÖ¹æ¤òµá¤á¤ë
598 pair2 = pair1 + pair_plus;
599
600 wk_A = fft->result_A[pair1] - fft->result_A[pair2];
601 wk_B = fft->result_B[pair1] - fft->result_B[pair2];
602 fft->result_A[pair1] = fft->result_A[pair1] + fft->result_A[pair2];
603 fft->result_B[pair1] = fft->result_B[pair1] + fft->result_B[pair2];
604 fft->result_A[pair2] = wk_cos * wk_A + wk_sin * wk_B;
605 fft->result_B[pair2] = wk_cos * wk_B - wk_sin * wk_A;
606
607 // -------------------------------- ¼¡¤Î¥°¥ë¡¼¥×¤ÎÀèƬ°ÌÃÖ¤ÎÈÖ¹æ¤ò¥»¥Ã¥È
608 pair1 += group_item;
609 }
610 }
611 group_count += group_count; // ¥°¥ë¡¼¥×¿ô¤Ï¡ÖÎó¡×Ëè¤Ë£²ÇܤËÁý¤¨¤Æ¤¤¤¯
612 mul_count /= 2; // ¥°¥ë¡¼¥×¤Ç¹Ô¤¦Ê£ÁǾ軻²ó¿ô¤Ï¡ÖÎó¡×Ëè¤Ë£±¡¿£²¤Ë¤Ê¤ë
613 pair_plus /= 2; // ÂФˤʤë¥Ç¡¼¥¿¤Î°ÌÃ֤ϡÖÎó¡×Ëè¤Ë£±¡¿£²¤Ë¤Ê¤ë
614 radian += radian;
615 }
616
617 // --------------------------------------------- ¥Ç¡¼¥¿¤Î¥Ó¥Ã¥È½ç¤ò¸µ¤ËÌ᤹
618 for ( i= 0 ; i < fft->N - 1 ; i++ )
619 {
620 mask = 1; // ¥Á¥§¥Ã¥¯¤¹¤ë¥Ó¥Ã¥È
621 set = 1 << ( fft->r-1 ); // ( fft->r-1 ) ʬº¸¤Ø¥·¥Õ¥È
622 w = 0;
623
624 for ( j= 0, k= fft->r ; k > 0 ; j++, k-- )
625 {
626 bit = i & mask;
627 if ( bit )
628 w |= set;
629 mask <<= 1;
630 set >>= 1;
631 }
632 if ( w <= i ) // update 1994.04.02 Á´¥Ç¡¼¥¿¤ò¥ê¥Ð¡¼¥¹¤·¤Æ¤¤¤¿¤¿¤á¸µ¤ËÌá¤Ã¤Æ¤¤¤¿
633 continue;
634
635 wk_A = fft->result_A[i];
636 wk_B = fft->result_B[i];
637 fft->result_A[i] = fft->result_A[w];
638 fft->result_A[w] = wk_A;
639 fft->result_B[i] = fft->result_B[w];
640 fft->result_B[w] = wk_B;
641 }
642}