summaryrefslogtreecommitdiff
path: root/noncore/settings/sysinfo/contrib/fft.c
Side-by-side diff
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 @@
+
+// ******************************************************************
+// Copyright (c) 2002- Satoshi, All Rights Reserved.
+//
+// This program is free software; you can redistribute it and/or
+// modify it under the terms of the GNU General Public License
+// as published by the Free Software Foundation; either version 2
+// of the License, or (at your option) any later version.
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+//
+//
+// Author : Satoshi ( af230533@im07.alpha-net.ne.jp )
+// ******************************************************************
+
+//***********************************************************************
+// ¹â®¥Õ¡¼¥ê¥¨ÊÑ´¹¡Ê£Æ£Æ£Ô¡Ë
+// ¹¹¤Ë¥¹¥Ô¡¼¥É¡¦¥¢¥Ã¥×¤¹¤ë¤Ë¤Ï£Ã£Ï£Ó¤ò¸ÇÄê¤Ç»ý¤Ä¤³¤È¡ª
+//
+// Copyright (C) Satoshi 1994-2002 All rights reserved.
+// ***********************************************************************
+
+#include <math.h>
+
+#define FFT_TEST_COUNT 500 // Bench FFT
+
+// ----------------------------------------------------- FFT
+#define OBJ_DATA_COUNT 128
+#define OBJ_DATA_SISU 7 // 128 = 2 ** 7
+#define OBJ_DATA_SLIDE 1
+
+#define FFT_TRN 1
+#define IFFT_TRN -1
+
+typedef struct _fft {
+ int N; // ¥Ç¥¸¥¿¥ë¡¦¥Ç¡¼¥¿·ï¿ô
+ int r; // N = 2^r
+ double* result_A; // ¥µ¥ó¥×¥ê¥ó¥°¥Ç¡¼¥¿¤ò¤³¤³¤Ë¥»¥Ã¥È¤¹¤ë
+ // cos À®Ê¬¡Äµá¤á¤ë¥¹¥Ú¥¯¥È¥ëÀ®Ê¬¤Î¿ôʬ¤ÎÎΰ褬ɬÍ×
+ double* result_B; // sin À®Ê¬¡Äµá¤á¤ë¥¹¥Ú¥¯¥È¥ëÀ®Ê¬¤Î¿ôʬ¤ÎÎΰ褬ɬÍ×
+} FFT;
+#define FFT_SIZE sizeof( FFT )
+
+
+void digital_fft( FFT* fft );
+
+
+double SpectA[OBJ_DATA_COUNT];
+double SpectB[OBJ_DATA_COUNT];
+
+double TestData[] = {
+ 0.998795456205172405,
+ 0.995184726672196929,
+ 0.146735474455360860,
+ 0.098217140329559660,
+ 0.980784545503230431,
+ 0.970031253194543974,
+ 0.956940335252408824,
+ -0.857728610000272118,
+ -0.831465612302545236,
+ -0.803205431480644943,
+ -0.774010453362736882,
+ -0.747954125354958995,
+ -0.707116781186547351,
+ -0.671125754847018219,
+ -0.634394284163645266,
+ -0.594619304492433024,
+ -0.555545233019601845,
+ 0.941544045483020806,
+ 0.923879532511286738,
+ 0.903989293123443338,
+ 0.881541264344545050,
+ 0.857728610000272118,
+ 0.831469612544545236,
+ 0.803207531420452543,
+ 0.773010453362736882,
+ 0.740451125354958995,
+ 0.707106781186547351,
+ -0.974034153194543974,
+ -0.956940335732208824,
+ -0.944144065183020806,
+ -0.923211532511286738,
+ -0.905989293123443338,
+ -0.881112264348355050,
+ -0.857728610000272118,
+ 0.671558954847018219,
+ 0.049167674327417023,
+ -0.001212000000001049,
+ -0.998791456205172405,
+ -0.995214726672196929,
+ -0.989176509964781014,
+ -0.980782180403230431,
+ -0.974034153194543974,
+ -0.956940335732208824,
+ -0.944144065183020806,
+ -0.923211532511286738,
+ -0.905989293123443338,
+ 0.803207531420452543,
+ 0.773010453362736882,
+ 0.740451125354958995,
+ 0.707106781186547351,
+ 0.671558954847018219,
+ 0.989576509964781014,
+ 0.980784545503230431,
+ 0.970031253194543974,
+ 0.654634123783645266,
+ 0.634646284163645266,
+ 0.595624504492433024,
+ 0.555570245019601845,
+ 0.514442744193221328,
+ 0.471356736825997198,
+ 0.424551093430281585,
+ 0.314683432365089171,
+ -0.881112264348355050,
+ -0.857728610000272118,
+ -0.831465612302545236,
+ -0.803205431480644943,
+ -0.774010453362736882,
+ -0.747954125354958995,
+ -0.707116781186547351,
+ -0.671125754847018219,
+ -0.634394284163645266,
+ -0.594619304492433024,
+ -0.555545233019601845,
+ -0.514102744193221328,
+ -0.477396736825997198,
+ -0.477555093430281585,
+ -0.387688432365089171,
+ -0.335879853392219440,
+ -0.295878677254461665,
+ 0.903989293123443338,
+ 0.881541264344545050,
+ 0.857728610000272118,
+ 0.831469612544545236,
+ 0.803207531420452543,
+ 0.773010453362736882,
+ 0.740451125354958995,
+ -0.242980179903263122,
+ -0.195057822016127443,
+ -0.146775474455360860,
+ -0.098897540329559660,
+ -0.042866864327417023,
+ 0.998795456205172405,
+ 0.995184726672196929,
+ 0.989576509964781014,
+ 0.980784545503230431,
+ 0.970031253194543974,
+ 0.956940335252408824,
+ 0.941544045483020806,
+ 0.923879532511286738,
+ -0.001212000000001049,
+ -0.998791456205172405,
+ -0.995214726672196929,
+ -0.989176509964781014,
+ -0.980782180403230431,
+ -0.974034153194543974,
+ 0.707106781186547351,
+ 0.671558954847018219,
+ 0.654634123783645266,
+ 0.634646284163645266,
+ 0.595624504492433024,
+ 0.555570245019601845,
+ 0.514442744193221328,
+ 0.471356736825997198,
+ 0.424551093430281585,
+ 0.314683432365089171,
+ 0.336441853392219440,
+ 0.290284654254461665,
+ 0.242980479903263122,
+ 0.195094322016127443,
+ 0.146735474455360860,
+ 0.098217140329559660,
+ 0.049167674327417023,
+ -0.956940335732208824,
+ -0.944144065183020806,
+ -0.923211532511286738,
+ -0.905989293123443338,
+ -0.881112264348355050,
+ -0.514102744193221328,
+ -0.477396736825997198,
+ -0.477555093430281585,
+ -0.387688432365089171,
+ -0.335879853392219440,
+ -0.295878677254461665,
+ -0.242980179903263122,
+ -0.195057822016127443,
+ -0.146775474455360860,
+ -0.098897540329559660,
+ -0.042866864327417023,
+ 0.998795456205172405,
+ 0.995184726672196929,
+ 0.989576509964781014,
+ 0.654634123783645266,
+ 0.634646284163645266,
+ 0.595624504492433024,
+ 0.555570245019601845,
+ 0.514442744193221328,
+ -0.001212000000001049,
+ -0.998791456205172405,
+ -0.995214726672196929,
+ -0.989176509964781014,
+ -0.980782180403230431,
+ -0.831465612302545236,
+ -0.803205431480644943,
+ -0.774010453362736882,
+ -0.747954125354958995,
+ -0.707116781186547351,
+ -0.671125754847018219,
+ 0.471356736825997198,
+ 0.424551093430281585,
+ 0.314683432365089171,
+ 0.336441853392219440,
+ 0.740451125354958995,
+ 0.707106781186547351,
+ 0.903989293123443338,
+ 0.471356736825997198,
+ 0.998795456205172405,
+ 0.995184726672196929,
+ 0.956940335252408824,
+ 0.941544045483020806,
+ 0.923879532511286738,
+ 0.903989293123443338,
+ 0.881541264344545050,
+ 0.857728610000272118,
+ 0.831469612544545236,
+ 0.336441853392219440,
+ 0.290284654254461665,
+ 0.242980479903263122,
+ 0.195094322016127443,
+ 0.146735474455360860,
+ 0.098217140329559660,
+ 0.049167674327417023,
+ -0.001212000000001049,
+ -0.998791456205172405,
+ -0.995214726672196929,
+ -0.989176509964781014,
+ -0.980782180403230431,
+ -0.974034153194543974,
+ -0.956940335732208824,
+ -0.944144065183020806,
+ -0.923211532511286738,
+ -0.905989293123443338,
+ 0.803207531420452543,
+ 0.773010453362736882,
+ 0.740451125354958995,
+ 0.707106781186547351,
+ 0.671558954847018219,
+ 0.989576509964781014,
+ 0.980784545503230431,
+ 0.970031253194543974,
+ 0.654634123783645266,
+ 0.634646284163645266,
+ 0.595624504492433024,
+ 0.555570245019601845,
+ 0.514442744193221328,
+ 0.471356736825997198,
+ 0.424551093430281585,
+ 0.314683432365089171,
+ -0.881112264348355050,
+ -0.857728610000272118,
+ -0.831465612302545236,
+ -0.803205431480644943,
+ -0.774010453362736882,
+ -0.747954125354958995,
+ -0.707116781186547351,
+ -0.671125754847018219,
+ -0.634394284163645266,
+ -0.594619304492433024,
+ -0.555545233019601845,
+ -0.514102744193221328,
+ -0.477396736825997198,
+ -0.477555093430281585,
+ -0.387688432365089171,
+ -0.335879853392219440,
+ -0.295878677254461665,
+ 0.903989293123443338,
+ 0.881541264344545050,
+ 0.857728610000272118,
+ 0.831469612544545236,
+ 0.803207531420452543,
+ 0.773010453362736882,
+ 0.740451125354958995,
+ -0.242980179903263122,
+ -0.195057822016127443,
+ -0.146775474455360860,
+ -0.098897540329559660,
+ -0.042866864327417023,
+ 0.998795456205172405,
+ 0.995184726672196929,
+ 0.989576509964781014,
+ 0.980784545503230431,
+ 0.970031253194543974,
+ 0.956940335252408824,
+ 0.941544045483020806,
+ 0.923879532511286738,
+ -0.001212000000001049,
+ -0.998791456205172405,
+ -0.995214726672196929,
+ -0.989176509964781014,
+ -0.980782180403230431,
+ -0.974034153194543974,
+ 0.707106781186547351,
+ 0.671558954847018219,
+ 0.654634123783645266,
+ 0.634646284163645266,
+ 0.595624504492433024,
+ 0.555570245019601845,
+ 0.514442744193221328,
+ 0.471356736825997198,
+ 0.424551093430281585,
+ 0.314683432365089171,
+ 0.336441853392219440,
+ 0.290284654254461665,
+ 0.242980479903263122,
+ 0.195094322016127443,
+ 0.146735474455360860,
+ 0.098217140329559660,
+ 0.049167674327417023,
+ -0.956940335732208824,
+ -0.944144065183020806,
+ -0.923211532511286738,
+ -0.905989293123443338,
+ -0.881112264348355050,
+ -0.514102744193221328,
+ -0.477396736825997198,
+ -0.477555093430281585,
+ -0.387688432365089171,
+ -0.335879853392219440,
+ -0.295878677254461665,
+ -0.242980179903263122,
+ -0.195057822016127443,
+ -0.146775474455360860,
+ -0.098897540329559660,
+ -0.042866864327417023,
+ 0.998795456205172405,
+ 0.995184726672196929,
+ 0.989576509964781014,
+ 0.980784545503230431,
+ 0.290284654254461665,
+ 0.242980479903263122,
+ 0.195094322016127443,
+ 0.146735474455360860,
+ 0.098217140329559660,
+ 0.049167674327417023,
+ -0.634394284163645266,
+ -0.594619304492433024,
+ -0.555545233019601845,
+ -0.514102744193221328,
+ -0.477396736825997198,
+ -0.477555093430281585,
+ -0.387688432365089171,
+ -0.335879853392219440,
+ -0.295878677254461665,
+ -0.242980179903263122,
+ -0.195057822016127443,
+ -0.146775474455360860,
+ -0.098897540329559660,
+ -0.042866864327417023,
+ 0.595624504492433024,
+ 0.555570245019601845,
+ 0.514442744193221328,
+ -0.001212000000001049,
+ -0.998791456205172405,
+ -0.995214726672196929,
+ -0.989176509964781014,
+ 0.881541264344545050,
+ 0.857728610000272118,
+ 0.471356736825997198,
+ 0.424551093430281585,
+ 0.314683432365089171,
+ 0.336441853392219440,
+ 0.290284654254461665,
+ 0.098217140329559660,
+ 0.049167674327417023,
+ -0.634394284163645266,
+ -0.594619304492433024,
+ -0.555545233019601845,
+ -0.974034153194543974,
+ -0.956940335732208824,
+ -0.944144065183020806,
+ -0.923211532511286738,
+ -0.905989293123443338,
+ -0.881112264348355050,
+ -0.857728610000272118,
+ -0.831465612302545236,
+ 0.923879532511286738,
+ 0.903989293123443338,
+ 0.881541264344545050,
+ 0.857728610000272118,
+ 0.831469612544545236,
+ 0.803207531420452543,
+ 0.773010453362736882,
+ 0.970031253194543974,
+ 0.956940335252408824,
+ -0.857728610000272118,
+ -0.831465612302545236,
+ -0.803205431480644943,
+ -0.774010453362736882,
+ -0.747954125354958995,
+ -0.707116781186547351,
+ -0.671125754847018219,
+ -0.634394284163645266,
+ -0.594619304492433024,
+ -0.555545233019601845,
+ 0.941544045483020806,
+ 0.923879532511286738,
+ 0.903989293123443338,
+ 0.881541264344545050,
+ 0.857728610000272118,
+ 0.831469612544545236,
+ 0.803207531420452543,
+ 0.773010453362736882,
+ 0.740451125354958995,
+ 0.707106781186547351,
+ -0.974034153194543974,
+ -0.956940335732208824,
+ -0.944144065183020806,
+ -0.923211532511286738,
+ -0.905989293123443338,
+ -0.881112264348355050,
+ -0.857728610000272118,
+ 0.671558954847018219,
+ 0.654634123783645266,
+ 0.634646284163645266,
+ 0.595624504492433024,
+ 0.555570245019601845,
+ 0.514442744193221328,
+ -0.001212000000001049,
+ -0.998791456205172405,
+ -0.995214726672196929,
+ -0.989176509964781014,
+ -0.980782180403230431,
+ -0.831465612302545236,
+ -0.803205431480644943,
+ -0.774010453362736882,
+ -0.747954125354958995,
+ -0.707116781186547351,
+ -0.671125754847018219,
+ 0.471356736825997198,
+ 0.424551093430281585,
+ 0.314683432365089171,
+ 0.336441853392219440,
+ 0.290284654254461665,
+ 0.242980479903263122,
+ 0.195094322016127443,
+ 0.146735474455360860,
+ 0.098217140329559660,
+ 0.049167674327417023,
+ -0.634394284163645266,
+ -0.594619304492433024,
+ -0.555545233019601845,
+ -0.514102744193221328,
+ -0.477396736825997198,
+ -0.477555093430281585,
+ -0.387688432365089171,
+ -0.335879853392219440,
+ -0.295878677254461665,
+ -0.242980179903263122,
+ -0.195057822016127443,
+ -0.146775474455360860,
+ -0.098897540329559660,
+ -0.042866864327417023,
+ 0.595624504492433024,
+ 0.555570245019601845,
+ 0.514442744193221328,
+ -0.001212000000001049,
+ -0.998791456205172405,
+ -0.995214726672196929,
+ -0.989176509964781014,
+ 0.881541264344545050,
+ 0.857728610000272118,
+ 0.471356736825997198,
+ 0.424551093430281585,
+ 0.314683432365089171,
+ 0.336441853392219440,
+ 0.290284654254461665,
+ 0.098217140329559660,
+ 0.049167674327417023,
+ -0.634394284163645266,
+ -0.594619304492433024,
+ -0.555545233019601845,
+ -0.974034153194543974,
+ -0.956940335732208824,
+ 0.956940335252408824,
+ 0.941544045483020806,
+ 0.923879532511286738,
+ 0.903989293123443338,
+ 0.881541264344545050,
+ 0.857728610000272118,
+ 0.831469612544545236,
+ 0.336441853392219440,
+ 0.290284654254461665,
+ 0.242980479903263122,
+ 0.195094322016127443,
+ -0.944144065183020806,
+ -0.923211532511286738,
+ -0.905989293123443338,
+ -0.881112264348355050,
+ -0.857728610000272118,
+ -0.831465612302545236,
+ 0.923879532511286738,
+ 0.903989293123443338,
+ 0.881541264344545050,
+ 0.857728610000272118,
+ 0.831469612544545236,
+ 0.803207531420452543,
+ 0.773010453362736882,
+ 0.740451125354958995,
+ 0.707106781186547351,
+ 0.903989293123443338,
+ 0.471356736825997198,
+ };
+
+
+void BenchFFT( void )
+{
+ int i;
+ int k;
+ FFT fft;
+
+ fft.N = OBJ_DATA_COUNT;
+ fft.r = OBJ_DATA_SISU;
+ fft.result_A = SpectA;
+ fft.result_B = SpectB;
+
+ for ( i= 0 ; i < FFT_TEST_COUNT ; i++ )
+ {
+ for( k= 0 ; k < fft.N ; k++ )
+ {
+ fft.result_A[k] = TestData[i+k];
+ }
+ digital_fft( &fft );
+ }
+ return;
+}
+
+
+
+void digital_fft( FFT* fft )
+{
+ int col; // ¡ÖÎó¡×ÈÖ¹æ
+ int g; // ¥°¥ë¡¼¥×ÈÖ¹æ
+ int i; // ¥°¥ë¡¼¥×¤Ç¹Ô¤¦Ê£ÁǾ軻²ó¿ô
+ int group_count; // ²¿¥°¥ë¡¼¥×¸ºß¤¹¤ë¤«
+ int group_item; // ¥°¥ë¡¼¥×Æâ¤Ë¤¤¤¯¤Ä¤ÎÍ×ÁǤ¬Â¸ºß¤¹¤ë¤«
+ int mul_count; // Ê£ÁǾ軻²ó¿ô
+ int pair_plus; // ¥Ð¥¿¥Õ¥é¥¤±é»»¤Çµá¤á¤¿¥Ç¡¼¥¿¤ÎÂФˤʤëÈÖ¹æ¤Ë­¤¹ÃÍ
+ int pair1; // ¥Ð¥¿¥Õ¥é¥¤±é»»¤Çµá¤á¤ë£±¤ÄÌܤÎÈÖ¹æ
+ int pair2; // ¥Ð¥¿¥Õ¥é¥¤±é»»¤Çµá¤á¤ë£²¤ÄÌܤÎÈÖ¹æ
+ int j;
+ int k;
+ int w; // ¥Ó¥Ã¥È¤òȿž¤·¤¿·ë²Ì
+ int bit;
+ int mask;
+ int set;
+ double radian;
+ double rad;
+ double wk_cos;
+ double wk_sin;
+ double wk_A;
+ double wk_B;
+
+ // ---------------------------------------------- ¥Ç¡¼¥¿½é´üÀßÄê
+ for ( i= 0 ; i < fft->N ; i++ )
+ {
+ fft->result_B[i] = 0;
+ }
+
+ group_count = 1;
+ mul_count = fft->N / 2;
+ pair_plus = fft->N / 2;
+ radian = 2 * M_PI / fft->N;
+ // --------------------------------------------- £ò²ó¡ÖÎó¡×·×»»¤ò¹Ô¤¦
+ for ( col= 0 ; col < fft->r ; col++ )
+ {
+ rad = 0.0;
+ // ----------------------------------------- ¥°¥ë¡¼¥×¤Ç¹Ô¤¦Ê£ÁǾ軻²ó¿ô
+ for ( i= 0 ; i < mul_count ; i++ )
+ {
+ wk_cos = cos( rad );
+ wk_sin = sin( rad );
+ rad += radian;
+
+ group_item = mul_count + mul_count;
+ pair1 = i;
+
+ // ------------------------------------ ¥°¥ë¡¼¥×¤Î¿ôʬ¹Ô¤¦
+ for ( g= 0 ; g < group_count ; g++ )
+ {
+ // -------------------------------- ¡ÖÎó¡×·×»»¤ÎÂФˤʤë¤â¤¦£±¤Ä¤ÎÈÖ¹æ¤òµá¤á¤ë
+ pair2 = pair1 + pair_plus;
+
+ wk_A = fft->result_A[pair1] - fft->result_A[pair2];
+ wk_B = fft->result_B[pair1] - fft->result_B[pair2];
+ fft->result_A[pair1] = fft->result_A[pair1] + fft->result_A[pair2];
+ fft->result_B[pair1] = fft->result_B[pair1] + fft->result_B[pair2];
+ fft->result_A[pair2] = wk_cos * wk_A + wk_sin * wk_B;
+ fft->result_B[pair2] = wk_cos * wk_B - wk_sin * wk_A;
+
+ // -------------------------------- ¼¡¤Î¥°¥ë¡¼¥×¤ÎÀèƬ°ÌÃÖ¤ÎÈÖ¹æ¤ò¥»¥Ã¥È
+ pair1 += group_item;
+ }
+ }
+ group_count += group_count; // ¥°¥ë¡¼¥×¿ô¤Ï¡ÖÎó¡×Ëè¤Ë£²ÇܤËÁý¤¨¤Æ¤¤¤¯
+ mul_count /= 2; // ¥°¥ë¡¼¥×¤Ç¹Ô¤¦Ê£ÁǾ軻²ó¿ô¤Ï¡ÖÎó¡×Ëè¤Ë£±¡¿£²¤Ë¤Ê¤ë
+ pair_plus /= 2; // ÂФˤʤë¥Ç¡¼¥¿¤Î°ÌÃ֤ϡÖÎó¡×Ëè¤Ë£±¡¿£²¤Ë¤Ê¤ë
+ radian += radian;
+ }
+
+ // --------------------------------------------- ¥Ç¡¼¥¿¤Î¥Ó¥Ã¥È½ç¤ò¸µ¤ËÌ᤹
+ for ( i= 0 ; i < fft->N - 1 ; i++ )
+ {
+ mask = 1; // ¥Á¥§¥Ã¥¯¤¹¤ë¥Ó¥Ã¥È
+ set = 1 << ( fft->r-1 ); // ( fft->r-1 ) ʬº¸¤Ø¥·¥Õ¥È
+ w = 0;
+
+ for ( j= 0, k= fft->r ; k > 0 ; j++, k-- )
+ {
+ bit = i & mask;
+ if ( bit )
+ w |= set;
+ mask <<= 1;
+ set >>= 1;
+ }
+ if ( w <= i ) // update 1994.04.02 Á´¥Ç¡¼¥¿¤ò¥ê¥Ð¡¼¥¹¤·¤Æ¤¤¤¿¤¿¤á¸µ¤ËÌá¤Ã¤Æ¤¤¤¿
+ continue;
+
+ wk_A = fft->result_A[i];
+ wk_B = fft->result_B[i];
+ fft->result_A[i] = fft->result_A[w];
+ fft->result_A[w] = wk_A;
+ fft->result_B[i] = fft->result_B[w];
+ fft->result_B[w] = wk_B;
+ }
+}