1 /* ScummVM - Graphic Adventure Engine 2 * 3 * ScummVM is the legal property of its developers, whose names 4 * are too numerous to list here. Please refer to the COPYRIGHT 5 * file distributed with this source distribution. 6 * 7 * This program is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU General Public License 9 * as published by the Free Software Foundation; either version 2 10 * of the License, or (at your option) any later version. 11 * 12 * This program is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with this program; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 20 * 21 */ 22 23 // Based on eos' (I)FFT code which is in turn 24 // based upon the (I)FFT code in FFmpeg 25 // Copyright (c) 2008 Loren Merritt 26 // Copyright (c) 2002 Fabrice Bellard 27 // Partly based on libdjbfft by D. J. Bernstein 28 29 #ifndef COMMON_FFT_H 30 #define COMMON_FFT_H 31 32 #include "common/scummsys.h" 33 #include "common/math.h" 34 35 namespace Common { 36 37 /** 38 * @defgroup common_fft Fast Fourier Transform (FFT) 39 * @ingroup common 40 * 41 * @brief API for the FFT algorithm. 42 * 43 * @{ 44 */ 45 46 class CosineTable; 47 48 /** 49 * (Inverse) Fast Fourier Transform. 50 * 51 * Used in engines: 52 * - SCUMM 53 */ 54 class FFT { 55 public: 56 FFT(int bits, int inverse); 57 ~FFT(); 58 59 const uint16 *getRevTab() const; 60 61 /** Perform the permutation needed BEFORE calling calc(). */ 62 void permute(Complex *z); 63 64 /** Perform a complex FFT. 65 * 66 * The input data must be permuted before. 67 * No 1.0/sqrt(n) normalization is done. 68 */ 69 void calc(Complex *z); 70 71 private: 72 int _bits; 73 int _inverse; 74 75 uint16 *_revTab; 76 77 Complex *_expTab; 78 Complex *_tmpBuf; 79 80 int _splitRadix; 81 82 static int splitRadixPermutation(int i, int n, int inverse); 83 84 CosineTable *_cosTables[13]; 85 86 void fft4(Complex *z); 87 void fft8(Complex *z); 88 void fft16(Complex *z); 89 void fft(int n, int logn, Complex *z); 90 }; 91 92 /** @} */ 93 94 } // End of namespace Common 95 96 #endif // COMMON_FFT_H 97