diff options
author | Gareth Stockwell <ext-gareth.stockwell@nokia.com> | 2010-04-29 16:30:16 (GMT) |
---|---|---|
committer | Gareth Stockwell <ext-gareth.stockwell@nokia.com> | 2010-05-05 09:24:01 (GMT) |
commit | e9dda3cabdcfdeb5d659b94640410b486ad58921 (patch) | |
tree | 169f3f6651c09d1775983c271df169be78d524d4 /demos/spectrum/fftreal | |
parent | 6c8acf656a9293db2fdbad569bb1fa3a83975462 (diff) | |
download | Qt-e9dda3cabdcfdeb5d659b94640410b486ad58921.zip Qt-e9dda3cabdcfdeb5d659b94640410b486ad58921.tar.gz Qt-e9dda3cabdcfdeb5d659b94640410b486ad58921.tar.bz2 |
Add spectrum analyzer demo app
This application is a demo which uses the QtMultimedia APIs to
capture and play back PCM audio. While either recording or playback
is ongoing, the application performs real-time level and frequency
spectrum analysis.
Reviewed-by: Alessandro Portale
Diffstat (limited to 'demos/spectrum/fftreal')
55 files changed, 8296 insertions, 0 deletions
diff --git a/demos/spectrum/fftreal/Array.h b/demos/spectrum/fftreal/Array.h new file mode 100644 index 0000000..a08e3cf --- /dev/null +++ b/demos/spectrum/fftreal/Array.h @@ -0,0 +1,97 @@ +/***************************************************************************** + + Array.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (Array_HEADER_INCLUDED) +#define Array_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class T, long LEN> +class Array +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + typedef T DataType; + + Array (); + + inline const DataType & + operator [] (long pos) const; + inline DataType & + operator [] (long pos); + + static inline long + size (); + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + DataType _data_arr [LEN]; + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + Array (const Array &other); + Array & operator = (const Array &other); + bool operator == (const Array &other); + bool operator != (const Array &other); + +}; // class Array + + + +#include "Array.hpp" + + + +#endif // Array_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/Array.hpp b/demos/spectrum/fftreal/Array.hpp new file mode 100644 index 0000000..8300077 --- /dev/null +++ b/demos/spectrum/fftreal/Array.hpp @@ -0,0 +1,98 @@ +/***************************************************************************** + + Array.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (Array_CURRENT_CODEHEADER) + #error Recursive inclusion of Array code header. +#endif +#define Array_CURRENT_CODEHEADER + +#if ! defined (Array_CODEHEADER_INCLUDED) +#define Array_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include <cassert> + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class T, long LEN> +Array <T, LEN>::Array () +{ + // Nothing +} + + + +template <class T, long LEN> +const typename Array <T, LEN>::DataType & Array <T, LEN>::operator [] (long pos) const +{ + assert (pos >= 0); + assert (pos < LEN); + + return (_data_arr [pos]); +} + + + +template <class T, long LEN> +typename Array <T, LEN>::DataType & Array <T, LEN>::operator [] (long pos) +{ + assert (pos >= 0); + assert (pos < LEN); + + return (_data_arr [pos]); +} + + + +template <class T, long LEN> +long Array <T, LEN>::size () +{ + return (LEN); +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +#endif // Array_CODEHEADER_INCLUDED + +#undef Array_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/DynArray.h b/demos/spectrum/fftreal/DynArray.h new file mode 100644 index 0000000..8041a0c --- /dev/null +++ b/demos/spectrum/fftreal/DynArray.h @@ -0,0 +1,100 @@ +/***************************************************************************** + + DynArray.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (DynArray_HEADER_INCLUDED) +#define DynArray_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class T> +class DynArray +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + typedef T DataType; + + DynArray (); + explicit DynArray (long size); + ~DynArray (); + + inline long size () const; + inline void resize (long size); + + inline const DataType & + operator [] (long pos) const; + inline DataType & + operator [] (long pos); + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + DataType * _data_ptr; + long _len; + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + DynArray (const DynArray &other); + DynArray & operator = (const DynArray &other); + bool operator == (const DynArray &other); + bool operator != (const DynArray &other); + +}; // class DynArray + + + +#include "DynArray.hpp" + + + +#endif // DynArray_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/DynArray.hpp b/demos/spectrum/fftreal/DynArray.hpp new file mode 100644 index 0000000..e62b10f --- /dev/null +++ b/demos/spectrum/fftreal/DynArray.hpp @@ -0,0 +1,143 @@ +/***************************************************************************** + + DynArray.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (DynArray_CURRENT_CODEHEADER) + #error Recursive inclusion of DynArray code header. +#endif +#define DynArray_CURRENT_CODEHEADER + +#if ! defined (DynArray_CODEHEADER_INCLUDED) +#define DynArray_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include <cassert> + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class T> +DynArray <T>::DynArray () +: _data_ptr (0) +, _len (0) +{ + // Nothing +} + + + +template <class T> +DynArray <T>::DynArray (long size) +: _data_ptr (0) +, _len (0) +{ + assert (size >= 0); + if (size > 0) + { + _data_ptr = new DataType [size]; + _len = size; + } +} + + + +template <class T> +DynArray <T>::~DynArray () +{ + delete [] _data_ptr; + _data_ptr = 0; + _len = 0; +} + + + +template <class T> +long DynArray <T>::size () const +{ + return (_len); +} + + + +template <class T> +void DynArray <T>::resize (long size) +{ + assert (size >= 0); + if (size > 0) + { + DataType * old_data_ptr = _data_ptr; + DataType * tmp_data_ptr = new DataType [size]; + + _data_ptr = tmp_data_ptr; + _len = size; + + delete [] old_data_ptr; + } +} + + + +template <class T> +const typename DynArray <T>::DataType & DynArray <T>::operator [] (long pos) const +{ + assert (pos >= 0); + assert (pos < _len); + + return (_data_ptr [pos]); +} + + + +template <class T> +typename DynArray <T>::DataType & DynArray <T>::operator [] (long pos) +{ + assert (pos >= 0); + assert (pos < _len); + + return (_data_ptr [pos]); +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +#endif // DynArray_CODEHEADER_INCLUDED + +#undef DynArray_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTReal.dsp b/demos/spectrum/fftreal/FFTReal.dsp new file mode 100644 index 0000000..fe970db --- /dev/null +++ b/demos/spectrum/fftreal/FFTReal.dsp @@ -0,0 +1,273 @@ +# Microsoft Developer Studio Project File - Name="FFTReal" - Package Owner=<4> +# Microsoft Developer Studio Generated Build File, Format Version 6.00 +# ** DO NOT EDIT ** + +# TARGTYPE "Win32 (x86) Console Application" 0x0103 + +CFG=FFTReal - Win32 Debug +!MESSAGE This is not a valid makefile. To build this project using NMAKE, +!MESSAGE use the Export Makefile command and run +!MESSAGE +!MESSAGE NMAKE /f "FFTReal.mak". +!MESSAGE +!MESSAGE You can specify a configuration when running NMAKE +!MESSAGE by defining the macro CFG on the command line. For example: +!MESSAGE +!MESSAGE NMAKE /f "FFTReal.mak" CFG="FFTReal - Win32 Debug" +!MESSAGE +!MESSAGE Possible choices for configuration are: +!MESSAGE +!MESSAGE "FFTReal - Win32 Release" (based on "Win32 (x86) Console Application") +!MESSAGE "FFTReal - Win32 Debug" (based on "Win32 (x86) Console Application") +!MESSAGE + +# Begin Project +# PROP AllowPerConfigDependencies 0 +# PROP Scc_ProjName "" +# PROP Scc_LocalPath "" +CPP=cl.exe +RSC=rc.exe + +!IF "$(CFG)" == "FFTReal - Win32 Release" + +# PROP BASE Use_MFC 0 +# PROP BASE Use_Debug_Libraries 0 +# PROP BASE Output_Dir "Release" +# PROP BASE Intermediate_Dir "Release" +# PROP BASE Target_Dir "" +# PROP Use_MFC 0 +# PROP Use_Debug_Libraries 0 +# PROP Output_Dir "Release" +# PROP Intermediate_Dir "Release" +# PROP Target_Dir "" +# ADD BASE CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /c +# ADD CPP /nologo /W3 /GR /GX /O2 /Ob2 /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /c +# ADD BASE RSC /l 0x40c /d "NDEBUG" +# ADD RSC /l 0x40c /d "NDEBUG" +BSC32=bscmake.exe +# ADD BASE BSC32 /nologo +# ADD BSC32 /nologo +LINK32=link.exe +# ADD BASE LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /machine:I386 +# ADD LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /machine:I386 + +!ELSEIF "$(CFG)" == "FFTReal - Win32 Debug" + +# PROP BASE Use_MFC 0 +# PROP BASE Use_Debug_Libraries 1 +# PROP BASE Output_Dir "Debug" +# PROP BASE Intermediate_Dir "Debug" +# PROP BASE Target_Dir "" +# PROP Use_MFC 0 +# PROP Use_Debug_Libraries 1 +# PROP Output_Dir "Debug" +# PROP Intermediate_Dir "Debug" +# PROP Ignore_Export_Lib 0 +# PROP Target_Dir "" +# ADD BASE CPP /nologo /W3 /Gm /GX /Zi /Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /c +# ADD CPP /nologo /G6 /MTd /W3 /Gm /GR /GX /Zi /Od /Gf /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /FR /YX /FD /c +# ADD BASE RSC /l 0x40c /d "_DEBUG" +# ADD RSC /l 0x40c /d "_DEBUG" +BSC32=bscmake.exe +# ADD BASE BSC32 /nologo +# ADD BSC32 /nologo +LINK32=link.exe +# ADD BASE LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /debug /machine:I386 /pdbtype:sept +# ADD LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /debug /machine:I386 /pdbtype:sept + +!ENDIF + +# Begin Target + +# Name "FFTReal - Win32 Release" +# Name "FFTReal - Win32 Debug" +# Begin Group "Library" + +# PROP Default_Filter "" +# Begin Source File + +SOURCE=.\Array.h +# End Source File +# Begin Source File + +SOURCE=.\Array.hpp +# End Source File +# Begin Source File + +SOURCE=.\def.h +# End Source File +# Begin Source File + +SOURCE=.\DynArray.h +# End Source File +# Begin Source File + +SOURCE=.\DynArray.hpp +# End Source File +# Begin Source File + +SOURCE=.\FFTReal.h +# End Source File +# Begin Source File + +SOURCE=.\FFTReal.hpp +# End Source File +# Begin Source File + +SOURCE=.\FFTRealFixLen.h +# End Source File +# Begin Source File + +SOURCE=.\FFTRealFixLen.hpp +# End Source File +# Begin Source File + +SOURCE=.\FFTRealFixLenParam.h +# End Source File +# Begin Source File + +SOURCE=.\FFTRealPassDirect.h +# End Source File +# Begin Source File + +SOURCE=.\FFTRealPassDirect.hpp +# End Source File +# Begin Source File + +SOURCE=.\FFTRealPassInverse.h +# End Source File +# Begin Source File + +SOURCE=.\FFTRealPassInverse.hpp +# End Source File +# Begin Source File + +SOURCE=.\FFTRealSelect.h +# End Source File +# Begin Source File + +SOURCE=.\FFTRealSelect.hpp +# End Source File +# Begin Source File + +SOURCE=.\FFTRealUseTrigo.h +# End Source File +# Begin Source File + +SOURCE=.\FFTRealUseTrigo.hpp +# End Source File +# Begin Source File + +SOURCE=.\OscSinCos.h +# End Source File +# Begin Source File + +SOURCE=.\OscSinCos.hpp +# End Source File +# End Group +# Begin Group "Test" + +# PROP Default_Filter "" +# Begin Group "stopwatch" + +# PROP Default_Filter "" +# Begin Source File + +SOURCE=.\stopwatch\ClockCycleCounter.cpp +# End Source File +# Begin Source File + +SOURCE=.\stopwatch\ClockCycleCounter.h +# End Source File +# Begin Source File + +SOURCE=.\stopwatch\ClockCycleCounter.hpp +# End Source File +# Begin Source File + +SOURCE=.\stopwatch\def.h +# End Source File +# Begin Source File + +SOURCE=.\stopwatch\fnc.h +# End Source File +# Begin Source File + +SOURCE=.\stopwatch\fnc.hpp +# End Source File +# Begin Source File + +SOURCE=.\stopwatch\Int64.h +# End Source File +# Begin Source File + +SOURCE=.\stopwatch\StopWatch.cpp +# End Source File +# Begin Source File + +SOURCE=.\stopwatch\StopWatch.h +# End Source File +# Begin Source File + +SOURCE=.\stopwatch\StopWatch.hpp +# End Source File +# End Group +# Begin Source File + +SOURCE=.\test.cpp +# End Source File +# Begin Source File + +SOURCE=.\test_fnc.h +# End Source File +# Begin Source File + +SOURCE=.\test_fnc.hpp +# End Source File +# Begin Source File + +SOURCE=.\test_settings.h +# End Source File +# Begin Source File + +SOURCE=.\TestAccuracy.h +# End Source File +# Begin Source File + +SOURCE=.\TestAccuracy.hpp +# End Source File +# Begin Source File + +SOURCE=.\TestHelperFixLen.h +# End Source File +# Begin Source File + +SOURCE=.\TestHelperFixLen.hpp +# End Source File +# Begin Source File + +SOURCE=.\TestHelperNormal.h +# End Source File +# Begin Source File + +SOURCE=.\TestHelperNormal.hpp +# End Source File +# Begin Source File + +SOURCE=.\TestSpeed.h +# End Source File +# Begin Source File + +SOURCE=.\TestSpeed.hpp +# End Source File +# Begin Source File + +SOURCE=.\TestWhiteNoiseGen.h +# End Source File +# Begin Source File + +SOURCE=.\TestWhiteNoiseGen.hpp +# End Source File +# End Group +# End Target +# End Project diff --git a/demos/spectrum/fftreal/FFTReal.dsw b/demos/spectrum/fftreal/FFTReal.dsw new file mode 100644 index 0000000..076b0ae --- /dev/null +++ b/demos/spectrum/fftreal/FFTReal.dsw @@ -0,0 +1,29 @@ +Microsoft Developer Studio Workspace File, Format Version 6.00 +# WARNING: DO NOT EDIT OR DELETE THIS WORKSPACE FILE! + +############################################################################### + +Project: "FFTReal"=.\FFTReal.dsp - Package Owner=<4> + +Package=<5> +{{{ +}}} + +Package=<4> +{{{ +}}} + +############################################################################### + +Global: + +Package=<5> +{{{ +}}} + +Package=<3> +{{{ +}}} + +############################################################################### + diff --git a/demos/spectrum/fftreal/FFTReal.h b/demos/spectrum/fftreal/FFTReal.h new file mode 100644 index 0000000..9fb2725 --- /dev/null +++ b/demos/spectrum/fftreal/FFTReal.h @@ -0,0 +1,142 @@ +/***************************************************************************** + + FFTReal.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (FFTReal_HEADER_INCLUDED) +#define FFTReal_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "def.h" +#include "DynArray.h" +#include "OscSinCos.h" + + + +template <class DT> +class FFTReal +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + enum { MAX_BIT_DEPTH = 30 }; // So length can be represented as long int + + typedef DT DataType; + + explicit FFTReal (long length); + virtual ~FFTReal () {} + + long get_length () const; + void do_fft (DataType f [], const DataType x []) const; + void do_ifft (const DataType f [], DataType x []) const; + void rescale (DataType x []) const; + DataType * use_buffer () const; + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + // Over this bit depth, we use direct calculation for sin/cos + enum { TRIGO_BD_LIMIT = 12 }; + + typedef OscSinCos <DataType> OscType; + + void init_br_lut (); + void init_trigo_lut (); + void init_trigo_osc (); + + FORCEINLINE const long * + get_br_ptr () const; + FORCEINLINE const DataType * + get_trigo_ptr (int level) const; + FORCEINLINE long + get_trigo_level_index (int level) const; + + inline void compute_fft_general (DataType f [], const DataType x []) const; + inline void compute_direct_pass_1_2 (DataType df [], const DataType x []) const; + inline void compute_direct_pass_3 (DataType df [], const DataType sf []) const; + inline void compute_direct_pass_n (DataType df [], const DataType sf [], int pass) const; + inline void compute_direct_pass_n_lut (DataType df [], const DataType sf [], int pass) const; + inline void compute_direct_pass_n_osc (DataType df [], const DataType sf [], int pass) const; + + inline void compute_ifft_general (const DataType f [], DataType x []) const; + inline void compute_inverse_pass_n (DataType df [], const DataType sf [], int pass) const; + inline void compute_inverse_pass_n_osc (DataType df [], const DataType sf [], int pass) const; + inline void compute_inverse_pass_n_lut (DataType df [], const DataType sf [], int pass) const; + inline void compute_inverse_pass_3 (DataType df [], const DataType sf []) const; + inline void compute_inverse_pass_1_2 (DataType x [], const DataType sf []) const; + + const long _length; + const int _nbr_bits; + DynArray <long> + _br_lut; + DynArray <DataType> + _trigo_lut; + mutable DynArray <DataType> + _buffer; + mutable DynArray <OscType> + _trigo_osc; + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + FFTReal (); + FFTReal (const FFTReal &other); + FFTReal & operator = (const FFTReal &other); + bool operator == (const FFTReal &other); + bool operator != (const FFTReal &other); + +}; // class FFTReal + + + +#include "FFTReal.hpp" + + + +#endif // FFTReal_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTReal.hpp b/demos/spectrum/fftreal/FFTReal.hpp new file mode 100644 index 0000000..335d771 --- /dev/null +++ b/demos/spectrum/fftreal/FFTReal.hpp @@ -0,0 +1,916 @@ +/***************************************************************************** + + FFTReal.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (FFTReal_CURRENT_CODEHEADER) + #error Recursive inclusion of FFTReal code header. +#endif +#define FFTReal_CURRENT_CODEHEADER + +#if ! defined (FFTReal_CODEHEADER_INCLUDED) +#define FFTReal_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include <cassert> +#include <cmath> + + + +static inline bool FFTReal_is_pow2 (long x) +{ + assert (x > 0); + + return ((x & -x) == x); +} + + + +static inline int FFTReal_get_next_pow2 (long x) +{ + --x; + + int p = 0; + while ((x & ~0xFFFFL) != 0) + { + p += 16; + x >>= 16; + } + while ((x & ~0xFL) != 0) + { + p += 4; + x >>= 4; + } + while (x > 0) + { + ++p; + x >>= 1; + } + + return (p); +} + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/* +============================================================================== +Name: ctor +Input parameters: + - length: length of the array on which we want to do a FFT. Range: power of + 2 only, > 0. +Throws: std::bad_alloc +============================================================================== +*/ + +template <class DT> +FFTReal <DT>::FFTReal (long length) +: _length (length) +, _nbr_bits (FFTReal_get_next_pow2 (length)) +, _br_lut () +, _trigo_lut () +, _buffer (length) +, _trigo_osc () +{ + assert (FFTReal_is_pow2 (length)); + assert (_nbr_bits <= MAX_BIT_DEPTH); + + init_br_lut (); + init_trigo_lut (); + init_trigo_osc (); +} + + + +/* +============================================================================== +Name: get_length +Description: + Returns the number of points processed by this FFT object. +Returns: The number of points, power of 2, > 0. +Throws: Nothing +============================================================================== +*/ + +template <class DT> +long FFTReal <DT>::get_length () const +{ + return (_length); +} + + + +/* +============================================================================== +Name: do_fft +Description: + Compute the FFT of the array. +Input parameters: + - x: pointer on the source array (time). +Output parameters: + - f: pointer on the destination array (frequencies). + f [0...length(x)/2] = real values, + f [length(x)/2+1...length(x)-1] = negative imaginary values of + coefficents 1...length(x)/2-1. +Throws: Nothing +============================================================================== +*/ + +template <class DT> +void FFTReal <DT>::do_fft (DataType f [], const DataType x []) const +{ + assert (f != 0); + assert (f != use_buffer ()); + assert (x != 0); + assert (x != use_buffer ()); + assert (x != f); + + // General case + if (_nbr_bits > 2) + { + compute_fft_general (f, x); + } + + // 4-point FFT + else if (_nbr_bits == 2) + { + f [1] = x [0] - x [2]; + f [3] = x [1] - x [3]; + + const DataType b_0 = x [0] + x [2]; + const DataType b_2 = x [1] + x [3]; + + f [0] = b_0 + b_2; + f [2] = b_0 - b_2; + } + + // 2-point FFT + else if (_nbr_bits == 1) + { + f [0] = x [0] + x [1]; + f [1] = x [0] - x [1]; + } + + // 1-point FFT + else + { + f [0] = x [0]; + } +} + + + +/* +============================================================================== +Name: do_ifft +Description: + Compute the inverse FFT of the array. Note that data must be post-scaled: + IFFT (FFT (x)) = x * length (x). +Input parameters: + - f: pointer on the source array (frequencies). + f [0...length(x)/2] = real values + f [length(x)/2+1...length(x)-1] = negative imaginary values of + coefficents 1...length(x)/2-1. +Output parameters: + - x: pointer on the destination array (time). +Throws: Nothing +============================================================================== +*/ + +template <class DT> +void FFTReal <DT>::do_ifft (const DataType f [], DataType x []) const +{ + assert (f != 0); + assert (f != use_buffer ()); + assert (x != 0); + assert (x != use_buffer ()); + assert (x != f); + + // General case + if (_nbr_bits > 2) + { + compute_ifft_general (f, x); + } + + // 4-point IFFT + else if (_nbr_bits == 2) + { + const DataType b_0 = f [0] + f [2]; + const DataType b_2 = f [0] - f [2]; + + x [0] = b_0 + f [1] * 2; + x [2] = b_0 - f [1] * 2; + x [1] = b_2 + f [3] * 2; + x [3] = b_2 - f [3] * 2; + } + + // 2-point IFFT + else if (_nbr_bits == 1) + { + x [0] = f [0] + f [1]; + x [1] = f [0] - f [1]; + } + + // 1-point IFFT + else + { + x [0] = f [0]; + } +} + + + +/* +============================================================================== +Name: rescale +Description: + Scale an array by divide each element by its length. This function should + be called after FFT + IFFT. +Input parameters: + - x: pointer on array to rescale (time or frequency). +Throws: Nothing +============================================================================== +*/ + +template <class DT> +void FFTReal <DT>::rescale (DataType x []) const +{ + const DataType mul = DataType (1.0 / _length); + + if (_length < 4) + { + long i = _length - 1; + do + { + x [i] *= mul; + --i; + } + while (i >= 0); + } + + else + { + assert ((_length & 3) == 0); + + // Could be optimized with SIMD instruction sets (needs alignment check) + long i = _length - 4; + do + { + x [i + 0] *= mul; + x [i + 1] *= mul; + x [i + 2] *= mul; + x [i + 3] *= mul; + i -= 4; + } + while (i >= 0); + } +} + + + +/* +============================================================================== +Name: use_buffer +Description: + Access the internal buffer, whose length is the FFT one. + Buffer content will be erased at each do_fft() / do_ifft() call! + This buffer cannot be used as: + - source for FFT or IFFT done with this object + - destination for FFT or IFFT done with this object +Returns: + Buffer start address +Throws: Nothing +============================================================================== +*/ + +template <class DT> +typename FFTReal <DT>::DataType * FFTReal <DT>::use_buffer () const +{ + return (&_buffer [0]); +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class DT> +void FFTReal <DT>::init_br_lut () +{ + const long length = 1L << _nbr_bits; + _br_lut.resize (length); + + _br_lut [0] = 0; + long br_index = 0; + for (long cnt = 1; cnt < length; ++cnt) + { + // ++br_index (bit reversed) + long bit = length >> 1; + while (((br_index ^= bit) & bit) == 0) + { + bit >>= 1; + } + + _br_lut [cnt] = br_index; + } +} + + + +template <class DT> +void FFTReal <DT>::init_trigo_lut () +{ + using namespace std; + + if (_nbr_bits > 3) + { + const long total_len = (1L << (_nbr_bits - 1)) - 4; + _trigo_lut.resize (total_len); + + for (int level = 3; level < _nbr_bits; ++level) + { + const long level_len = 1L << (level - 1); + DataType * const level_ptr = + &_trigo_lut [get_trigo_level_index (level)]; + const double mul = PI / (level_len << 1); + + for (long i = 0; i < level_len; ++ i) + { + level_ptr [i] = static_cast <DataType> (cos (i * mul)); + } + } + } +} + + + +template <class DT> +void FFTReal <DT>::init_trigo_osc () +{ + const int nbr_osc = _nbr_bits - TRIGO_BD_LIMIT; + if (nbr_osc > 0) + { + _trigo_osc.resize (nbr_osc); + + for (int osc_cnt = 0; osc_cnt < nbr_osc; ++osc_cnt) + { + OscType & osc = _trigo_osc [osc_cnt]; + + const long len = 1L << (TRIGO_BD_LIMIT + osc_cnt); + const double mul = (0.5 * PI) / len; + osc.set_step (mul); + } + } +} + + + +template <class DT> +const long * FFTReal <DT>::get_br_ptr () const +{ + return (&_br_lut [0]); +} + + + +template <class DT> +const typename FFTReal <DT>::DataType * FFTReal <DT>::get_trigo_ptr (int level) const +{ + assert (level >= 3); + + return (&_trigo_lut [get_trigo_level_index (level)]); +} + + + +template <class DT> +long FFTReal <DT>::get_trigo_level_index (int level) const +{ + assert (level >= 3); + + return ((1L << (level - 1)) - 4); +} + + + +// Transform in several passes +template <class DT> +void FFTReal <DT>::compute_fft_general (DataType f [], const DataType x []) const +{ + assert (f != 0); + assert (f != use_buffer ()); + assert (x != 0); + assert (x != use_buffer ()); + assert (x != f); + + DataType * sf; + DataType * df; + + if ((_nbr_bits & 1) != 0) + { + df = use_buffer (); + sf = f; + } + else + { + df = f; + sf = use_buffer (); + } + + compute_direct_pass_1_2 (df, x); + compute_direct_pass_3 (sf, df); + + for (int pass = 3; pass < _nbr_bits; ++ pass) + { + compute_direct_pass_n (df, sf, pass); + + DataType * const temp_ptr = df; + df = sf; + sf = temp_ptr; + } +} + + + +template <class DT> +void FFTReal <DT>::compute_direct_pass_1_2 (DataType df [], const DataType x []) const +{ + assert (df != 0); + assert (x != 0); + assert (df != x); + + const long * const bit_rev_lut_ptr = get_br_ptr (); + long coef_index = 0; + do + { + const long rev_index_0 = bit_rev_lut_ptr [coef_index]; + const long rev_index_1 = bit_rev_lut_ptr [coef_index + 1]; + const long rev_index_2 = bit_rev_lut_ptr [coef_index + 2]; + const long rev_index_3 = bit_rev_lut_ptr [coef_index + 3]; + + DataType * const df2 = df + coef_index; + df2 [1] = x [rev_index_0] - x [rev_index_1]; + df2 [3] = x [rev_index_2] - x [rev_index_3]; + + const DataType sf_0 = x [rev_index_0] + x [rev_index_1]; + const DataType sf_2 = x [rev_index_2] + x [rev_index_3]; + + df2 [0] = sf_0 + sf_2; + df2 [2] = sf_0 - sf_2; + + coef_index += 4; + } + while (coef_index < _length); +} + + + +template <class DT> +void FFTReal <DT>::compute_direct_pass_3 (DataType df [], const DataType sf []) const +{ + assert (df != 0); + assert (sf != 0); + assert (df != sf); + + const DataType sqrt2_2 = DataType (SQRT2 * 0.5); + long coef_index = 0; + do + { + DataType v; + + df [coef_index] = sf [coef_index] + sf [coef_index + 4]; + df [coef_index + 4] = sf [coef_index] - sf [coef_index + 4]; + df [coef_index + 2] = sf [coef_index + 2]; + df [coef_index + 6] = sf [coef_index + 6]; + + v = (sf [coef_index + 5] - sf [coef_index + 7]) * sqrt2_2; + df [coef_index + 1] = sf [coef_index + 1] + v; + df [coef_index + 3] = sf [coef_index + 1] - v; + + v = (sf [coef_index + 5] + sf [coef_index + 7]) * sqrt2_2; + df [coef_index + 5] = v + sf [coef_index + 3]; + df [coef_index + 7] = v - sf [coef_index + 3]; + + coef_index += 8; + } + while (coef_index < _length); +} + + + +template <class DT> +void FFTReal <DT>::compute_direct_pass_n (DataType df [], const DataType sf [], int pass) const +{ + assert (df != 0); + assert (sf != 0); + assert (df != sf); + assert (pass >= 3); + assert (pass < _nbr_bits); + + if (pass <= TRIGO_BD_LIMIT) + { + compute_direct_pass_n_lut (df, sf, pass); + } + else + { + compute_direct_pass_n_osc (df, sf, pass); + } +} + + + +template <class DT> +void FFTReal <DT>::compute_direct_pass_n_lut (DataType df [], const DataType sf [], int pass) const +{ + assert (df != 0); + assert (sf != 0); + assert (df != sf); + assert (pass >= 3); + assert (pass < _nbr_bits); + + const long nbr_coef = 1 << pass; + const long h_nbr_coef = nbr_coef >> 1; + const long d_nbr_coef = nbr_coef << 1; + long coef_index = 0; + const DataType * const cos_ptr = get_trigo_ptr (pass); + do + { + const DataType * const sf1r = sf + coef_index; + const DataType * const sf2r = sf1r + nbr_coef; + DataType * const dfr = df + coef_index; + DataType * const dfi = dfr + nbr_coef; + + // Extreme coefficients are always real + dfr [0] = sf1r [0] + sf2r [0]; + dfi [0] = sf1r [0] - sf2r [0]; // dfr [nbr_coef] = + dfr [h_nbr_coef] = sf1r [h_nbr_coef]; + dfi [h_nbr_coef] = sf2r [h_nbr_coef]; + + // Others are conjugate complex numbers + const DataType * const sf1i = sf1r + h_nbr_coef; + const DataType * const sf2i = sf1i + nbr_coef; + for (long i = 1; i < h_nbr_coef; ++ i) + { + const DataType c = cos_ptr [i]; // cos (i*PI/nbr_coef); + const DataType s = cos_ptr [h_nbr_coef - i]; // sin (i*PI/nbr_coef); + DataType v; + + v = sf2r [i] * c - sf2i [i] * s; + dfr [i] = sf1r [i] + v; + dfi [-i] = sf1r [i] - v; // dfr [nbr_coef - i] = + + v = sf2r [i] * s + sf2i [i] * c; + dfi [i] = v + sf1i [i]; + dfi [nbr_coef - i] = v - sf1i [i]; + } + + coef_index += d_nbr_coef; + } + while (coef_index < _length); +} + + + +template <class DT> +void FFTReal <DT>::compute_direct_pass_n_osc (DataType df [], const DataType sf [], int pass) const +{ + assert (df != 0); + assert (sf != 0); + assert (df != sf); + assert (pass > TRIGO_BD_LIMIT); + assert (pass < _nbr_bits); + + const long nbr_coef = 1 << pass; + const long h_nbr_coef = nbr_coef >> 1; + const long d_nbr_coef = nbr_coef << 1; + long coef_index = 0; + OscType & osc = _trigo_osc [pass - (TRIGO_BD_LIMIT + 1)]; + do + { + const DataType * const sf1r = sf + coef_index; + const DataType * const sf2r = sf1r + nbr_coef; + DataType * const dfr = df + coef_index; + DataType * const dfi = dfr + nbr_coef; + + osc.clear_buffers (); + + // Extreme coefficients are always real + dfr [0] = sf1r [0] + sf2r [0]; + dfi [0] = sf1r [0] - sf2r [0]; // dfr [nbr_coef] = + dfr [h_nbr_coef] = sf1r [h_nbr_coef]; + dfi [h_nbr_coef] = sf2r [h_nbr_coef]; + + // Others are conjugate complex numbers + const DataType * const sf1i = sf1r + h_nbr_coef; + const DataType * const sf2i = sf1i + nbr_coef; + for (long i = 1; i < h_nbr_coef; ++ i) + { + osc.step (); + const DataType c = osc.get_cos (); + const DataType s = osc.get_sin (); + DataType v; + + v = sf2r [i] * c - sf2i [i] * s; + dfr [i] = sf1r [i] + v; + dfi [-i] = sf1r [i] - v; // dfr [nbr_coef - i] = + + v = sf2r [i] * s + sf2i [i] * c; + dfi [i] = v + sf1i [i]; + dfi [nbr_coef - i] = v - sf1i [i]; + } + + coef_index += d_nbr_coef; + } + while (coef_index < _length); +} + + + +// Transform in several pass +template <class DT> +void FFTReal <DT>::compute_ifft_general (const DataType f [], DataType x []) const +{ + assert (f != 0); + assert (f != use_buffer ()); + assert (x != 0); + assert (x != use_buffer ()); + assert (x != f); + + DataType * sf = const_cast <DataType *> (f); + DataType * df; + DataType * df_temp; + + if (_nbr_bits & 1) + { + df = use_buffer (); + df_temp = x; + } + else + { + df = x; + df_temp = use_buffer (); + } + + for (int pass = _nbr_bits - 1; pass >= 3; -- pass) + { + compute_inverse_pass_n (df, sf, pass); + + if (pass < _nbr_bits - 1) + { + DataType * const temp_ptr = df; + df = sf; + sf = temp_ptr; + } + else + { + sf = df; + df = df_temp; + } + } + + compute_inverse_pass_3 (df, sf); + compute_inverse_pass_1_2 (x, df); +} + + + +template <class DT> +void FFTReal <DT>::compute_inverse_pass_n (DataType df [], const DataType sf [], int pass) const +{ + assert (df != 0); + assert (sf != 0); + assert (df != sf); + assert (pass >= 3); + assert (pass < _nbr_bits); + + if (pass <= TRIGO_BD_LIMIT) + { + compute_inverse_pass_n_lut (df, sf, pass); + } + else + { + compute_inverse_pass_n_osc (df, sf, pass); + } +} + + + +template <class DT> +void FFTReal <DT>::compute_inverse_pass_n_lut (DataType df [], const DataType sf [], int pass) const +{ + assert (df != 0); + assert (sf != 0); + assert (df != sf); + assert (pass >= 3); + assert (pass < _nbr_bits); + + const long nbr_coef = 1 << pass; + const long h_nbr_coef = nbr_coef >> 1; + const long d_nbr_coef = nbr_coef << 1; + long coef_index = 0; + const DataType * const cos_ptr = get_trigo_ptr (pass); + do + { + const DataType * const sfr = sf + coef_index; + const DataType * const sfi = sfr + nbr_coef; + DataType * const df1r = df + coef_index; + DataType * const df2r = df1r + nbr_coef; + + // Extreme coefficients are always real + df1r [0] = sfr [0] + sfi [0]; // + sfr [nbr_coef] + df2r [0] = sfr [0] - sfi [0]; // - sfr [nbr_coef] + df1r [h_nbr_coef] = sfr [h_nbr_coef] * 2; + df2r [h_nbr_coef] = sfi [h_nbr_coef] * 2; + + // Others are conjugate complex numbers + DataType * const df1i = df1r + h_nbr_coef; + DataType * const df2i = df1i + nbr_coef; + for (long i = 1; i < h_nbr_coef; ++ i) + { + df1r [i] = sfr [i] + sfi [-i]; // + sfr [nbr_coef - i] + df1i [i] = sfi [i] - sfi [nbr_coef - i]; + + const DataType c = cos_ptr [i]; // cos (i*PI/nbr_coef); + const DataType s = cos_ptr [h_nbr_coef - i]; // sin (i*PI/nbr_coef); + const DataType vr = sfr [i] - sfi [-i]; // - sfr [nbr_coef - i] + const DataType vi = sfi [i] + sfi [nbr_coef - i]; + + df2r [i] = vr * c + vi * s; + df2i [i] = vi * c - vr * s; + } + + coef_index += d_nbr_coef; + } + while (coef_index < _length); +} + + + +template <class DT> +void FFTReal <DT>::compute_inverse_pass_n_osc (DataType df [], const DataType sf [], int pass) const +{ + assert (df != 0); + assert (sf != 0); + assert (df != sf); + assert (pass > TRIGO_BD_LIMIT); + assert (pass < _nbr_bits); + + const long nbr_coef = 1 << pass; + const long h_nbr_coef = nbr_coef >> 1; + const long d_nbr_coef = nbr_coef << 1; + long coef_index = 0; + OscType & osc = _trigo_osc [pass - (TRIGO_BD_LIMIT + 1)]; + do + { + const DataType * const sfr = sf + coef_index; + const DataType * const sfi = sfr + nbr_coef; + DataType * const df1r = df + coef_index; + DataType * const df2r = df1r + nbr_coef; + + osc.clear_buffers (); + + // Extreme coefficients are always real + df1r [0] = sfr [0] + sfi [0]; // + sfr [nbr_coef] + df2r [0] = sfr [0] - sfi [0]; // - sfr [nbr_coef] + df1r [h_nbr_coef] = sfr [h_nbr_coef] * 2; + df2r [h_nbr_coef] = sfi [h_nbr_coef] * 2; + + // Others are conjugate complex numbers + DataType * const df1i = df1r + h_nbr_coef; + DataType * const df2i = df1i + nbr_coef; + for (long i = 1; i < h_nbr_coef; ++ i) + { + df1r [i] = sfr [i] + sfi [-i]; // + sfr [nbr_coef - i] + df1i [i] = sfi [i] - sfi [nbr_coef - i]; + + osc.step (); + const DataType c = osc.get_cos (); + const DataType s = osc.get_sin (); + const DataType vr = sfr [i] - sfi [-i]; // - sfr [nbr_coef - i] + const DataType vi = sfi [i] + sfi [nbr_coef - i]; + + df2r [i] = vr * c + vi * s; + df2i [i] = vi * c - vr * s; + } + + coef_index += d_nbr_coef; + } + while (coef_index < _length); +} + + + +template <class DT> +void FFTReal <DT>::compute_inverse_pass_3 (DataType df [], const DataType sf []) const +{ + assert (df != 0); + assert (sf != 0); + assert (df != sf); + + const DataType sqrt2_2 = DataType (SQRT2 * 0.5); + long coef_index = 0; + do + { + df [coef_index] = sf [coef_index] + sf [coef_index + 4]; + df [coef_index + 4] = sf [coef_index] - sf [coef_index + 4]; + df [coef_index + 2] = sf [coef_index + 2] * 2; + df [coef_index + 6] = sf [coef_index + 6] * 2; + + df [coef_index + 1] = sf [coef_index + 1] + sf [coef_index + 3]; + df [coef_index + 3] = sf [coef_index + 5] - sf [coef_index + 7]; + + const DataType vr = sf [coef_index + 1] - sf [coef_index + 3]; + const DataType vi = sf [coef_index + 5] + sf [coef_index + 7]; + + df [coef_index + 5] = (vr + vi) * sqrt2_2; + df [coef_index + 7] = (vi - vr) * sqrt2_2; + + coef_index += 8; + } + while (coef_index < _length); +} + + + +template <class DT> +void FFTReal <DT>::compute_inverse_pass_1_2 (DataType x [], const DataType sf []) const +{ + assert (x != 0); + assert (sf != 0); + assert (x != sf); + + const long * bit_rev_lut_ptr = get_br_ptr (); + const DataType * sf2 = sf; + long coef_index = 0; + do + { + { + const DataType b_0 = sf2 [0] + sf2 [2]; + const DataType b_2 = sf2 [0] - sf2 [2]; + const DataType b_1 = sf2 [1] * 2; + const DataType b_3 = sf2 [3] * 2; + + x [bit_rev_lut_ptr [0]] = b_0 + b_1; + x [bit_rev_lut_ptr [1]] = b_0 - b_1; + x [bit_rev_lut_ptr [2]] = b_2 + b_3; + x [bit_rev_lut_ptr [3]] = b_2 - b_3; + } + { + const DataType b_0 = sf2 [4] + sf2 [6]; + const DataType b_2 = sf2 [4] - sf2 [6]; + const DataType b_1 = sf2 [5] * 2; + const DataType b_3 = sf2 [7] * 2; + + x [bit_rev_lut_ptr [4]] = b_0 + b_1; + x [bit_rev_lut_ptr [5]] = b_0 - b_1; + x [bit_rev_lut_ptr [6]] = b_2 + b_3; + x [bit_rev_lut_ptr [7]] = b_2 - b_3; + } + + sf2 += 8; + coef_index += 8; + bit_rev_lut_ptr += 8; + } + while (coef_index < _length); +} + + + +#endif // FFTReal_CODEHEADER_INCLUDED + +#undef FFTReal_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTRealFixLen.h b/demos/spectrum/fftreal/FFTRealFixLen.h new file mode 100644 index 0000000..0b80266 --- /dev/null +++ b/demos/spectrum/fftreal/FFTRealFixLen.h @@ -0,0 +1,130 @@ +/***************************************************************************** + + FFTRealFixLen.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (FFTRealFixLen_HEADER_INCLUDED) +#define FFTRealFixLen_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "Array.h" +#include "DynArray.h" +#include "FFTRealFixLenParam.h" +#include "OscSinCos.h" + + + +template <int LL2> +class FFTRealFixLen +{ + typedef int CompileTimeCheck1 [(LL2 >= 0) ? 1 : -1]; + typedef int CompileTimeCheck2 [(LL2 <= 30) ? 1 : -1]; + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + typedef FFTRealFixLenParam::DataType DataType; + typedef OscSinCos <DataType> OscType; + + enum { FFT_LEN_L2 = LL2 }; + enum { FFT_LEN = 1 << FFT_LEN_L2 }; + + FFTRealFixLen (); + + inline long get_length () const; + void do_fft (DataType f [], const DataType x []); + void do_ifft (const DataType f [], DataType x []); + void rescale (DataType x []) const; + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + enum { TRIGO_BD_LIMIT = FFTRealFixLenParam::TRIGO_BD_LIMIT }; + + enum { BR_ARR_SIZE_L2 = ((FFT_LEN_L2 - 3) < 0) ? 0 : (FFT_LEN_L2 - 2) }; + enum { BR_ARR_SIZE = 1 << BR_ARR_SIZE_L2 }; + + enum { TRIGO_BD = ((FFT_LEN_L2 - TRIGO_BD_LIMIT) < 0) + ? (int)FFT_LEN_L2 + : (int)TRIGO_BD_LIMIT }; + enum { TRIGO_TABLE_ARR_SIZE_L2 = (LL2 < 4) ? 0 : (TRIGO_BD - 2) }; + enum { TRIGO_TABLE_ARR_SIZE = 1 << TRIGO_TABLE_ARR_SIZE_L2 }; + + enum { NBR_TRIGO_OSC = FFT_LEN_L2 - TRIGO_BD }; + enum { TRIGO_OSC_ARR_SIZE = (NBR_TRIGO_OSC > 0) ? NBR_TRIGO_OSC : 1 }; + + void build_br_lut (); + void build_trigo_lut (); + void build_trigo_osc (); + + DynArray <DataType> + _buffer; + DynArray <long> + _br_data; + DynArray <DataType> + _trigo_data; + Array <OscType, TRIGO_OSC_ARR_SIZE> + _trigo_osc; + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + FFTRealFixLen (const FFTRealFixLen &other); + FFTRealFixLen& operator = (const FFTRealFixLen &other); + bool operator == (const FFTRealFixLen &other); + bool operator != (const FFTRealFixLen &other); + +}; // class FFTRealFixLen + + + +#include "FFTRealFixLen.hpp" + + + +#endif // FFTRealFixLen_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTRealFixLen.hpp b/demos/spectrum/fftreal/FFTRealFixLen.hpp new file mode 100644 index 0000000..6defb00 --- /dev/null +++ b/demos/spectrum/fftreal/FFTRealFixLen.hpp @@ -0,0 +1,322 @@ +/***************************************************************************** + + FFTRealFixLen.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (FFTRealFixLen_CURRENT_CODEHEADER) + #error Recursive inclusion of FFTRealFixLen code header. +#endif +#define FFTRealFixLen_CURRENT_CODEHEADER + +#if ! defined (FFTRealFixLen_CODEHEADER_INCLUDED) +#define FFTRealFixLen_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "def.h" +#include "FFTRealPassDirect.h" +#include "FFTRealPassInverse.h" +#include "FFTRealSelect.h" + +#include <cassert> +#include <cmath> + +namespace std { } + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <int LL2> +FFTRealFixLen <LL2>::FFTRealFixLen () +: _buffer (FFT_LEN) +, _br_data (BR_ARR_SIZE) +, _trigo_data (TRIGO_TABLE_ARR_SIZE) +, _trigo_osc () +{ + build_br_lut (); + build_trigo_lut (); + build_trigo_osc (); +} + + + +template <int LL2> +long FFTRealFixLen <LL2>::get_length () const +{ + return (FFT_LEN); +} + + + +// General case +template <int LL2> +void FFTRealFixLen <LL2>::do_fft (DataType f [], const DataType x []) +{ + assert (f != 0); + assert (x != 0); + assert (x != f); + assert (FFT_LEN_L2 >= 3); + + // Do the transform in several passes + const DataType * cos_ptr = &_trigo_data [0]; + const long * br_ptr = &_br_data [0]; + + FFTRealPassDirect <FFT_LEN_L2 - 1>::process ( + FFT_LEN, + f, + &_buffer [0], + x, + cos_ptr, + TRIGO_TABLE_ARR_SIZE, + br_ptr, + &_trigo_osc [0] + ); +} + +// 4-point FFT +template <> +void FFTRealFixLen <2>::do_fft (DataType f [], const DataType x []) +{ + assert (f != 0); + assert (x != 0); + assert (x != f); + + f [1] = x [0] - x [2]; + f [3] = x [1] - x [3]; + + const DataType b_0 = x [0] + x [2]; + const DataType b_2 = x [1] + x [3]; + + f [0] = b_0 + b_2; + f [2] = b_0 - b_2; +} + +// 2-point FFT +template <> +void FFTRealFixLen <1>::do_fft (DataType f [], const DataType x []) +{ + assert (f != 0); + assert (x != 0); + assert (x != f); + + f [0] = x [0] + x [1]; + f [1] = x [0] - x [1]; +} + +// 1-point FFT +template <> +void FFTRealFixLen <0>::do_fft (DataType f [], const DataType x []) +{ + assert (f != 0); + assert (x != 0); + + f [0] = x [0]; +} + + + +// General case +template <int LL2> +void FFTRealFixLen <LL2>::do_ifft (const DataType f [], DataType x []) +{ + assert (f != 0); + assert (x != 0); + assert (x != f); + assert (FFT_LEN_L2 >= 3); + + // Do the transform in several passes + DataType * s_ptr = + FFTRealSelect <FFT_LEN_L2 & 1>::sel_bin (&_buffer [0], x); + DataType * d_ptr = + FFTRealSelect <FFT_LEN_L2 & 1>::sel_bin (x, &_buffer [0]); + const DataType * cos_ptr = &_trigo_data [0]; + const long * br_ptr = &_br_data [0]; + + FFTRealPassInverse <FFT_LEN_L2 - 1>::process ( + FFT_LEN, + d_ptr, + s_ptr, + f, + cos_ptr, + TRIGO_TABLE_ARR_SIZE, + br_ptr, + &_trigo_osc [0] + ); +} + +// 4-point IFFT +template <> +void FFTRealFixLen <2>::do_ifft (const DataType f [], DataType x []) +{ + assert (f != 0); + assert (x != 0); + assert (x != f); + + const DataType b_0 = f [0] + f [2]; + const DataType b_2 = f [0] - f [2]; + + x [0] = b_0 + f [1] * 2; + x [2] = b_0 - f [1] * 2; + x [1] = b_2 + f [3] * 2; + x [3] = b_2 - f [3] * 2; +} + +// 2-point IFFT +template <> +void FFTRealFixLen <1>::do_ifft (const DataType f [], DataType x []) +{ + assert (f != 0); + assert (x != 0); + assert (x != f); + + x [0] = f [0] + f [1]; + x [1] = f [0] - f [1]; +} + +// 1-point IFFT +template <> +void FFTRealFixLen <0>::do_ifft (const DataType f [], DataType x []) +{ + assert (f != 0); + assert (x != 0); + assert (x != f); + + x [0] = f [0]; +} + + + + +template <int LL2> +void FFTRealFixLen <LL2>::rescale (DataType x []) const +{ + assert (x != 0); + + const DataType mul = DataType (1.0 / FFT_LEN); + + if (FFT_LEN < 4) + { + long i = FFT_LEN - 1; + do + { + x [i] *= mul; + --i; + } + while (i >= 0); + } + + else + { + assert ((FFT_LEN & 3) == 0); + + // Could be optimized with SIMD instruction sets (needs alignment check) + long i = FFT_LEN - 4; + do + { + x [i + 0] *= mul; + x [i + 1] *= mul; + x [i + 2] *= mul; + x [i + 3] *= mul; + i -= 4; + } + while (i >= 0); + } +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <int LL2> +void FFTRealFixLen <LL2>::build_br_lut () +{ + _br_data [0] = 0; + for (long cnt = 1; cnt < BR_ARR_SIZE; ++cnt) + { + long index = cnt << 2; + long br_index = 0; + + int bit_cnt = FFT_LEN_L2; + do + { + br_index <<= 1; + br_index += (index & 1); + index >>= 1; + + -- bit_cnt; + } + while (bit_cnt > 0); + + _br_data [cnt] = br_index; + } +} + + + +template <int LL2> +void FFTRealFixLen <LL2>::build_trigo_lut () +{ + const double mul = (0.5 * PI) / TRIGO_TABLE_ARR_SIZE; + for (long i = 0; i < TRIGO_TABLE_ARR_SIZE; ++ i) + { + using namespace std; + + _trigo_data [i] = DataType (cos (i * mul)); + } +} + + + +template <int LL2> +void FFTRealFixLen <LL2>::build_trigo_osc () +{ + for (int i = 0; i < NBR_TRIGO_OSC; ++i) + { + OscType & osc = _trigo_osc [i]; + + const long len = static_cast <long> (TRIGO_TABLE_ARR_SIZE) << (i + 1); + const double mul = (0.5 * PI) / len; + osc.set_step (mul); + } +} + + + +#endif // FFTRealFixLen_CODEHEADER_INCLUDED + +#undef FFTRealFixLen_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTRealFixLenParam.h b/demos/spectrum/fftreal/FFTRealFixLenParam.h new file mode 100644 index 0000000..163c083 --- /dev/null +++ b/demos/spectrum/fftreal/FFTRealFixLenParam.h @@ -0,0 +1,93 @@ +/***************************************************************************** + + FFTRealFixLenParam.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (FFTRealFixLenParam_HEADER_INCLUDED) +#define FFTRealFixLenParam_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +class FFTRealFixLenParam +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + // Over this bit depth, we use direct calculation for sin/cos + enum { TRIGO_BD_LIMIT = 12 }; + + typedef float DataType; + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + +#if 0 // To avoid GCC warning: + // All member functions in class 'FFTRealFixLenParam' are private + FFTRealFixLenParam (); + ~FFTRealFixLenParam (); + FFTRealFixLenParam (const FFTRealFixLenParam &other); + FFTRealFixLenParam & + operator = (const FFTRealFixLenParam &other); + bool operator == (const FFTRealFixLenParam &other); + bool operator != (const FFTRealFixLenParam &other); +#endif + +}; // class FFTRealFixLenParam + + + +//#include "FFTRealFixLenParam.hpp" + + + +#endif // FFTRealFixLenParam_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTRealPassDirect.h b/demos/spectrum/fftreal/FFTRealPassDirect.h new file mode 100644 index 0000000..7d19c02 --- /dev/null +++ b/demos/spectrum/fftreal/FFTRealPassDirect.h @@ -0,0 +1,96 @@ +/***************************************************************************** + + FFTRealPassDirect.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (FFTRealPassDirect_HEADER_INCLUDED) +#define FFTRealPassDirect_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "def.h" +#include "FFTRealFixLenParam.h" +#include "OscSinCos.h" + + + +template <int PASS> +class FFTRealPassDirect +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + typedef FFTRealFixLenParam::DataType DataType; + typedef OscSinCos <DataType> OscType; + + FORCEINLINE static void + process (long len, DataType dest_ptr [], DataType src_ptr [], const DataType x_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []); + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + FFTRealPassDirect (); + ~FFTRealPassDirect (); + FFTRealPassDirect (const FFTRealPassDirect &other); + FFTRealPassDirect & + operator = (const FFTRealPassDirect &other); + bool operator == (const FFTRealPassDirect &other); + bool operator != (const FFTRealPassDirect &other); + +}; // class FFTRealPassDirect + + + +#include "FFTRealPassDirect.hpp" + + + +#endif // FFTRealPassDirect_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTRealPassDirect.hpp b/demos/spectrum/fftreal/FFTRealPassDirect.hpp new file mode 100644 index 0000000..db9d568 --- /dev/null +++ b/demos/spectrum/fftreal/FFTRealPassDirect.hpp @@ -0,0 +1,204 @@ +/***************************************************************************** + + FFTRealPassDirect.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (FFTRealPassDirect_CURRENT_CODEHEADER) + #error Recursive inclusion of FFTRealPassDirect code header. +#endif +#define FFTRealPassDirect_CURRENT_CODEHEADER + +#if ! defined (FFTRealPassDirect_CODEHEADER_INCLUDED) +#define FFTRealPassDirect_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "FFTRealUseTrigo.h" + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <> +void FFTRealPassDirect <1>::process (long len, DataType dest_ptr [], DataType src_ptr [], const DataType x_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []) +{ + // First and second pass at once + const long qlen = len >> 2; + + long coef_index = 0; + do + { + // To do: unroll the loop (2x). + const long ri_0 = br_ptr [coef_index >> 2]; + const long ri_1 = ri_0 + 2 * qlen; // bit_rev_lut_ptr [coef_index + 1]; + const long ri_2 = ri_0 + 1 * qlen; // bit_rev_lut_ptr [coef_index + 2]; + const long ri_3 = ri_0 + 3 * qlen; // bit_rev_lut_ptr [coef_index + 3]; + + DataType * const df2 = dest_ptr + coef_index; + df2 [1] = x_ptr [ri_0] - x_ptr [ri_1]; + df2 [3] = x_ptr [ri_2] - x_ptr [ri_3]; + + const DataType sf_0 = x_ptr [ri_0] + x_ptr [ri_1]; + const DataType sf_2 = x_ptr [ri_2] + x_ptr [ri_3]; + + df2 [0] = sf_0 + sf_2; + df2 [2] = sf_0 - sf_2; + + coef_index += 4; + } + while (coef_index < len); +} + +template <> +void FFTRealPassDirect <2>::process (long len, DataType dest_ptr [], DataType src_ptr [], const DataType x_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []) +{ + // Executes "previous" passes first. Inverts source and destination buffers + FFTRealPassDirect <1>::process ( + len, + src_ptr, + dest_ptr, + x_ptr, + cos_ptr, + cos_len, + br_ptr, + osc_list + ); + + // Third pass + const DataType sqrt2_2 = DataType (SQRT2 * 0.5); + + long coef_index = 0; + do + { + dest_ptr [coef_index ] = src_ptr [coef_index] + src_ptr [coef_index + 4]; + dest_ptr [coef_index + 4] = src_ptr [coef_index] - src_ptr [coef_index + 4]; + dest_ptr [coef_index + 2] = src_ptr [coef_index + 2]; + dest_ptr [coef_index + 6] = src_ptr [coef_index + 6]; + + DataType v; + + v = (src_ptr [coef_index + 5] - src_ptr [coef_index + 7]) * sqrt2_2; + dest_ptr [coef_index + 1] = src_ptr [coef_index + 1] + v; + dest_ptr [coef_index + 3] = src_ptr [coef_index + 1] - v; + + v = (src_ptr [coef_index + 5] + src_ptr [coef_index + 7]) * sqrt2_2; + dest_ptr [coef_index + 5] = v + src_ptr [coef_index + 3]; + dest_ptr [coef_index + 7] = v - src_ptr [coef_index + 3]; + + coef_index += 8; + } + while (coef_index < len); +} + +template <int PASS> +void FFTRealPassDirect <PASS>::process (long len, DataType dest_ptr [], DataType src_ptr [], const DataType x_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []) +{ + // Executes "previous" passes first. Inverts source and destination buffers + FFTRealPassDirect <PASS - 1>::process ( + len, + src_ptr, + dest_ptr, + x_ptr, + cos_ptr, + cos_len, + br_ptr, + osc_list + ); + + const long dist = 1L << (PASS - 1); + const long c1_r = 0; + const long c1_i = dist; + const long c2_r = dist * 2; + const long c2_i = dist * 3; + const long cend = dist * 4; + const long table_step = cos_len >> (PASS - 1); + + enum { TRIGO_OSC = PASS - FFTRealFixLenParam::TRIGO_BD_LIMIT }; + enum { TRIGO_DIRECT = (TRIGO_OSC >= 0) ? 1 : 0 }; + + long coef_index = 0; + do + { + const DataType * const sf = src_ptr + coef_index; + DataType * const df = dest_ptr + coef_index; + + // Extreme coefficients are always real + df [c1_r] = sf [c1_r] + sf [c2_r]; + df [c2_r] = sf [c1_r] - sf [c2_r]; + df [c1_i] = sf [c1_i]; + df [c2_i] = sf [c2_i]; + + FFTRealUseTrigo <TRIGO_DIRECT>::prepare (osc_list [TRIGO_OSC]); + + // Others are conjugate complex numbers + for (long i = 1; i < dist; ++ i) + { + DataType c; + DataType s; + FFTRealUseTrigo <TRIGO_DIRECT>::iterate ( + osc_list [TRIGO_OSC], + c, + s, + cos_ptr, + i * table_step, + (dist - i) * table_step + ); + + const DataType sf_r_i = sf [c1_r + i]; + const DataType sf_i_i = sf [c1_i + i]; + + const DataType v1 = sf [c2_r + i] * c - sf [c2_i + i] * s; + df [c1_r + i] = sf_r_i + v1; + df [c2_r - i] = sf_r_i - v1; + + const DataType v2 = sf [c2_r + i] * s + sf [c2_i + i] * c; + df [c2_r + i] = v2 + sf_i_i; + df [cend - i] = v2 - sf_i_i; + } + + coef_index += cend; + } + while (coef_index < len); +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +#endif // FFTRealPassDirect_CODEHEADER_INCLUDED + +#undef FFTRealPassDirect_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTRealPassInverse.h b/demos/spectrum/fftreal/FFTRealPassInverse.h new file mode 100644 index 0000000..2de8952 --- /dev/null +++ b/demos/spectrum/fftreal/FFTRealPassInverse.h @@ -0,0 +1,101 @@ +/***************************************************************************** + + FFTRealPassInverse.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (FFTRealPassInverse_HEADER_INCLUDED) +#define FFTRealPassInverse_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "def.h" +#include "FFTRealFixLenParam.h" +#include "OscSinCos.h" + + + + +template <int PASS> +class FFTRealPassInverse +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + typedef FFTRealFixLenParam::DataType DataType; + typedef OscSinCos <DataType> OscType; + + FORCEINLINE static void + process (long len, DataType dest_ptr [], DataType src_ptr [], const DataType f_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []); + FORCEINLINE static void + process_rec (long len, DataType dest_ptr [], DataType src_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []); + FORCEINLINE static void + process_internal (long len, DataType dest_ptr [], const DataType src_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []); + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + FFTRealPassInverse (); + ~FFTRealPassInverse (); + FFTRealPassInverse (const FFTRealPassInverse &other); + FFTRealPassInverse & + operator = (const FFTRealPassInverse &other); + bool operator == (const FFTRealPassInverse &other); + bool operator != (const FFTRealPassInverse &other); + +}; // class FFTRealPassInverse + + + +#include "FFTRealPassInverse.hpp" + + + +#endif // FFTRealPassInverse_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTRealPassInverse.hpp b/demos/spectrum/fftreal/FFTRealPassInverse.hpp new file mode 100644 index 0000000..5737546 --- /dev/null +++ b/demos/spectrum/fftreal/FFTRealPassInverse.hpp @@ -0,0 +1,229 @@ +/***************************************************************************** + + FFTRealPassInverse.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (FFTRealPassInverse_CURRENT_CODEHEADER) + #error Recursive inclusion of FFTRealPassInverse code header. +#endif +#define FFTRealPassInverse_CURRENT_CODEHEADER + +#if ! defined (FFTRealPassInverse_CODEHEADER_INCLUDED) +#define FFTRealPassInverse_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "FFTRealUseTrigo.h" + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <int PASS> +void FFTRealPassInverse <PASS>::process (long len, DataType dest_ptr [], DataType src_ptr [], const DataType f_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []) +{ + process_internal ( + len, + dest_ptr, + f_ptr, + cos_ptr, + cos_len, + br_ptr, + osc_list + ); + FFTRealPassInverse <PASS - 1>::process_rec ( + len, + src_ptr, + dest_ptr, + cos_ptr, + cos_len, + br_ptr, + osc_list + ); +} + + + +template <int PASS> +void FFTRealPassInverse <PASS>::process_rec (long len, DataType dest_ptr [], DataType src_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []) +{ + process_internal ( + len, + dest_ptr, + src_ptr, + cos_ptr, + cos_len, + br_ptr, + osc_list + ); + FFTRealPassInverse <PASS - 1>::process_rec ( + len, + src_ptr, + dest_ptr, + cos_ptr, + cos_len, + br_ptr, + osc_list + ); +} + +template <> +void FFTRealPassInverse <0>::process_rec (long len, DataType dest_ptr [], DataType src_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []) +{ + // Stops recursion +} + + + +template <int PASS> +void FFTRealPassInverse <PASS>::process_internal (long len, DataType dest_ptr [], const DataType src_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []) +{ + const long dist = 1L << (PASS - 1); + const long c1_r = 0; + const long c1_i = dist; + const long c2_r = dist * 2; + const long c2_i = dist * 3; + const long cend = dist * 4; + const long table_step = cos_len >> (PASS - 1); + + enum { TRIGO_OSC = PASS - FFTRealFixLenParam::TRIGO_BD_LIMIT }; + enum { TRIGO_DIRECT = (TRIGO_OSC >= 0) ? 1 : 0 }; + + long coef_index = 0; + do + { + const DataType * const sf = src_ptr + coef_index; + DataType * const df = dest_ptr + coef_index; + + // Extreme coefficients are always real + df [c1_r] = sf [c1_r] + sf [c2_r]; + df [c2_r] = sf [c1_r] - sf [c2_r]; + df [c1_i] = sf [c1_i] * 2; + df [c2_i] = sf [c2_i] * 2; + + FFTRealUseTrigo <TRIGO_DIRECT>::prepare (osc_list [TRIGO_OSC]); + + // Others are conjugate complex numbers + for (long i = 1; i < dist; ++ i) + { + df [c1_r + i] = sf [c1_r + i] + sf [c2_r - i]; + df [c1_i + i] = sf [c2_r + i] - sf [cend - i]; + + DataType c; + DataType s; + FFTRealUseTrigo <TRIGO_DIRECT>::iterate ( + osc_list [TRIGO_OSC], + c, + s, + cos_ptr, + i * table_step, + (dist - i) * table_step + ); + + const DataType vr = sf [c1_r + i] - sf [c2_r - i]; + const DataType vi = sf [c2_r + i] + sf [cend - i]; + + df [c2_r + i] = vr * c + vi * s; + df [c2_i + i] = vi * c - vr * s; + } + + coef_index += cend; + } + while (coef_index < len); +} + +template <> +void FFTRealPassInverse <2>::process_internal (long len, DataType dest_ptr [], const DataType src_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []) +{ + // Antepenultimate pass + const DataType sqrt2_2 = DataType (SQRT2 * 0.5); + + long coef_index = 0; + do + { + dest_ptr [coef_index ] = src_ptr [coef_index] + src_ptr [coef_index + 4]; + dest_ptr [coef_index + 4] = src_ptr [coef_index] - src_ptr [coef_index + 4]; + dest_ptr [coef_index + 2] = src_ptr [coef_index + 2] * 2; + dest_ptr [coef_index + 6] = src_ptr [coef_index + 6] * 2; + + dest_ptr [coef_index + 1] = src_ptr [coef_index + 1] + src_ptr [coef_index + 3]; + dest_ptr [coef_index + 3] = src_ptr [coef_index + 5] - src_ptr [coef_index + 7]; + + const DataType vr = src_ptr [coef_index + 1] - src_ptr [coef_index + 3]; + const DataType vi = src_ptr [coef_index + 5] + src_ptr [coef_index + 7]; + + dest_ptr [coef_index + 5] = (vr + vi) * sqrt2_2; + dest_ptr [coef_index + 7] = (vi - vr) * sqrt2_2; + + coef_index += 8; + } + while (coef_index < len); +} + +template <> +void FFTRealPassInverse <1>::process_internal (long len, DataType dest_ptr [], const DataType src_ptr [], const DataType cos_ptr [], long cos_len, const long br_ptr [], OscType osc_list []) +{ + // Penultimate and last pass at once + const long qlen = len >> 2; + + long coef_index = 0; + do + { + const long ri_0 = br_ptr [coef_index >> 2]; + + const DataType b_0 = src_ptr [coef_index ] + src_ptr [coef_index + 2]; + const DataType b_2 = src_ptr [coef_index ] - src_ptr [coef_index + 2]; + const DataType b_1 = src_ptr [coef_index + 1] * 2; + const DataType b_3 = src_ptr [coef_index + 3] * 2; + + dest_ptr [ri_0 ] = b_0 + b_1; + dest_ptr [ri_0 + 2 * qlen] = b_0 - b_1; + dest_ptr [ri_0 + 1 * qlen] = b_2 + b_3; + dest_ptr [ri_0 + 3 * qlen] = b_2 - b_3; + + coef_index += 4; + } + while (coef_index < len); +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +#endif // FFTRealPassInverse_CODEHEADER_INCLUDED + +#undef FFTRealPassInverse_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTRealSelect.h b/demos/spectrum/fftreal/FFTRealSelect.h new file mode 100644 index 0000000..bd722d4 --- /dev/null +++ b/demos/spectrum/fftreal/FFTRealSelect.h @@ -0,0 +1,77 @@ +/***************************************************************************** + + FFTRealSelect.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (FFTRealSelect_HEADER_INCLUDED) +#define FFTRealSelect_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "def.h" + + + +template <int P> +class FFTRealSelect +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + FORCEINLINE static float * + sel_bin (float *e_ptr, float *o_ptr); + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + FFTRealSelect (); + ~FFTRealSelect (); + FFTRealSelect (const FFTRealSelect &other); + FFTRealSelect& operator = (const FFTRealSelect &other); + bool operator == (const FFTRealSelect &other); + bool operator != (const FFTRealSelect &other); + +}; // class FFTRealSelect + + + +#include "FFTRealSelect.hpp" + + + +#endif // FFTRealSelect_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTRealSelect.hpp b/demos/spectrum/fftreal/FFTRealSelect.hpp new file mode 100644 index 0000000..9ddf586 --- /dev/null +++ b/demos/spectrum/fftreal/FFTRealSelect.hpp @@ -0,0 +1,62 @@ +/***************************************************************************** + + FFTRealSelect.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (FFTRealSelect_CURRENT_CODEHEADER) + #error Recursive inclusion of FFTRealSelect code header. +#endif +#define FFTRealSelect_CURRENT_CODEHEADER + +#if ! defined (FFTRealSelect_CODEHEADER_INCLUDED) +#define FFTRealSelect_CODEHEADER_INCLUDED + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <int P> +float * FFTRealSelect <P>::sel_bin (float *e_ptr, float *o_ptr) +{ + return (o_ptr); +} + + + +template <> +float * FFTRealSelect <0>::sel_bin (float *e_ptr, float *o_ptr) +{ + return (e_ptr); +} + + + +#endif // FFTRealSelect_CODEHEADER_INCLUDED + +#undef FFTRealSelect_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTRealUseTrigo.h b/demos/spectrum/fftreal/FFTRealUseTrigo.h new file mode 100644 index 0000000..c4368ee --- /dev/null +++ b/demos/spectrum/fftreal/FFTRealUseTrigo.h @@ -0,0 +1,101 @@ +/***************************************************************************** + + FFTRealUseTrigo.h + Copyright (c) 2005 Laurent de Soras + +Template parameters: + - ALGO: algorithm choice. 0 = table, other = oscillator + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (FFTRealUseTrigo_HEADER_INCLUDED) +#define FFTRealUseTrigo_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "def.h" +#include "FFTRealFixLenParam.h" +#include "OscSinCos.h" + + + +template <int ALGO> +class FFTRealUseTrigo +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + typedef FFTRealFixLenParam::DataType DataType; + typedef OscSinCos <DataType> OscType; + + FORCEINLINE static void + prepare (OscType &osc); + FORCEINLINE static void + iterate (OscType &osc, DataType &c, DataType &s, const DataType cos_ptr [], long index_c, long index_s); + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + FFTRealUseTrigo (); + ~FFTRealUseTrigo (); + FFTRealUseTrigo (const FFTRealUseTrigo &other); + FFTRealUseTrigo & + operator = (const FFTRealUseTrigo &other); + bool operator == (const FFTRealUseTrigo &other); + bool operator != (const FFTRealUseTrigo &other); + +}; // class FFTRealUseTrigo + + + +#include "FFTRealUseTrigo.hpp" + + + +#endif // FFTRealUseTrigo_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/FFTRealUseTrigo.hpp b/demos/spectrum/fftreal/FFTRealUseTrigo.hpp new file mode 100644 index 0000000..aa968b8 --- /dev/null +++ b/demos/spectrum/fftreal/FFTRealUseTrigo.hpp @@ -0,0 +1,91 @@ +/***************************************************************************** + + FFTRealUseTrigo.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (FFTRealUseTrigo_CURRENT_CODEHEADER) + #error Recursive inclusion of FFTRealUseTrigo code header. +#endif +#define FFTRealUseTrigo_CURRENT_CODEHEADER + +#if ! defined (FFTRealUseTrigo_CODEHEADER_INCLUDED) +#define FFTRealUseTrigo_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "OscSinCos.h" + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <int ALGO> +void FFTRealUseTrigo <ALGO>::prepare (OscType &osc) +{ + osc.clear_buffers (); +} + +template <> +void FFTRealUseTrigo <0>::prepare (OscType &osc) +{ + // Nothing +} + + + +template <int ALGO> +void FFTRealUseTrigo <ALGO>::iterate (OscType &osc, DataType &c, DataType &s, const DataType cos_ptr [], long index_c, long index_s) +{ + osc.step (); + c = osc.get_cos (); + s = osc.get_sin (); +} + +template <> +void FFTRealUseTrigo <0>::iterate (OscType &osc, DataType &c, DataType &s, const DataType cos_ptr [], long index_c, long index_s) +{ + c = cos_ptr [index_c]; + s = cos_ptr [index_s]; +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +#endif // FFTRealUseTrigo_CODEHEADER_INCLUDED + +#undef FFTRealUseTrigo_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/OscSinCos.h b/demos/spectrum/fftreal/OscSinCos.h new file mode 100644 index 0000000..775fc14 --- /dev/null +++ b/demos/spectrum/fftreal/OscSinCos.h @@ -0,0 +1,106 @@ +/***************************************************************************** + + OscSinCos.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (OscSinCos_HEADER_INCLUDED) +#define OscSinCos_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "def.h" + + + +template <class T> +class OscSinCos +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + typedef T DataType; + + OscSinCos (); + + FORCEINLINE void + set_step (double angle_rad); + + FORCEINLINE DataType + get_cos () const; + FORCEINLINE DataType + get_sin () const; + FORCEINLINE void + step (); + FORCEINLINE void + clear_buffers (); + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + DataType _pos_cos; // Current phase expressed with sin and cos. [-1 ; 1] + DataType _pos_sin; // - + DataType _step_cos; // Phase increment per step, [-1 ; 1] + DataType _step_sin; // - + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + OscSinCos (const OscSinCos &other); + OscSinCos & operator = (const OscSinCos &other); + bool operator == (const OscSinCos &other); + bool operator != (const OscSinCos &other); + +}; // class OscSinCos + + + +#include "OscSinCos.hpp" + + + +#endif // OscSinCos_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/OscSinCos.hpp b/demos/spectrum/fftreal/OscSinCos.hpp new file mode 100644 index 0000000..749aef0 --- /dev/null +++ b/demos/spectrum/fftreal/OscSinCos.hpp @@ -0,0 +1,122 @@ +/***************************************************************************** + + OscSinCos.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (OscSinCos_CURRENT_CODEHEADER) + #error Recursive inclusion of OscSinCos code header. +#endif +#define OscSinCos_CURRENT_CODEHEADER + +#if ! defined (OscSinCos_CODEHEADER_INCLUDED) +#define OscSinCos_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include <cmath> + +namespace std { } + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class T> +OscSinCos <T>::OscSinCos () +: _pos_cos (1) +, _pos_sin (0) +, _step_cos (1) +, _step_sin (0) +{ + // Nothing +} + + + +template <class T> +void OscSinCos <T>::set_step (double angle_rad) +{ + using namespace std; + + _step_cos = static_cast <DataType> (cos (angle_rad)); + _step_sin = static_cast <DataType> (sin (angle_rad)); +} + + + +template <class T> +typename OscSinCos <T>::DataType OscSinCos <T>::get_cos () const +{ + return (_pos_cos); +} + + + +template <class T> +typename OscSinCos <T>::DataType OscSinCos <T>::get_sin () const +{ + return (_pos_sin); +} + + + +template <class T> +void OscSinCos <T>::step () +{ + const DataType old_cos = _pos_cos; + const DataType old_sin = _pos_sin; + + _pos_cos = old_cos * _step_cos - old_sin * _step_sin; + _pos_sin = old_cos * _step_sin + old_sin * _step_cos; +} + + + +template <class T> +void OscSinCos <T>::clear_buffers () +{ + _pos_cos = static_cast <DataType> (1); + _pos_sin = static_cast <DataType> (0); +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +#endif // OscSinCos_CODEHEADER_INCLUDED + +#undef OscSinCos_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/TestAccuracy.h b/demos/spectrum/fftreal/TestAccuracy.h new file mode 100644 index 0000000..4b07a6b --- /dev/null +++ b/demos/spectrum/fftreal/TestAccuracy.h @@ -0,0 +1,105 @@ +/***************************************************************************** + + TestAccuracy.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (TestAccuracy_HEADER_INCLUDED) +#define TestAccuracy_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class FO> +class TestAccuracy +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + typedef typename FO::DataType DataType; + typedef long double BigFloat; // To get maximum accuracy during intermediate calculations + + static int perform_test_single_object (FO &fft); + static int perform_test_d (FO &fft, const char *class_name_0); + static int perform_test_i (FO &fft, const char *class_name_0); + static int perform_test_di (FO &fft, const char *class_name_0); + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + enum { NBR_ACC_TESTS = 10 * 1000 * 1000 }; + enum { MAX_NBR_TESTS = 10000 }; + + static void compute_tf (DataType s [], const DataType x [], long length); + static void compute_itf (DataType x [], const DataType s [], long length); + static int compare_vect_display (const DataType x_ptr [], const DataType y_ptr [], long len, BigFloat &max_err_rel); + static BigFloat + compute_power (const DataType x_ptr [], long len); + static BigFloat + compute_power (const DataType x_ptr [], const DataType y_ptr [], long len); + static void compare_vect (const DataType x_ptr [], const DataType y_ptr [], BigFloat &power, long &max_err_pos, long len); + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + TestAccuracy (); + ~TestAccuracy (); + TestAccuracy (const TestAccuracy &other); + TestAccuracy & operator = (const TestAccuracy &other); + bool operator == (const TestAccuracy &other); + bool operator != (const TestAccuracy &other); + +}; // class TestAccuracy + + + +#include "TestAccuracy.hpp" + + + +#endif // TestAccuracy_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/TestAccuracy.hpp b/demos/spectrum/fftreal/TestAccuracy.hpp new file mode 100644 index 0000000..5c794f7 --- /dev/null +++ b/demos/spectrum/fftreal/TestAccuracy.hpp @@ -0,0 +1,472 @@ +/***************************************************************************** + + TestAccuracy.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (TestAccuracy_CURRENT_CODEHEADER) + #error Recursive inclusion of TestAccuracy code header. +#endif +#define TestAccuracy_CURRENT_CODEHEADER + +#if ! defined (TestAccuracy_CODEHEADER_INCLUDED) +#define TestAccuracy_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "def.h" +#include "test_fnc.h" +#include "TestWhiteNoiseGen.h" + +#include <typeinfo> +#include <vector> + +#include <cmath> +#include <cstdio> + + + +static const double TestAccuracy_LN10 = 2.3025850929940456840179914546844; + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class FO> +int TestAccuracy <FO>::perform_test_single_object (FO &fft) +{ + assert (&fft != 0); + + using namespace std; + + int ret_val = 0; + + const std::type_info & ti = typeid (fft); + const char * class_name_0 = ti.name (); + + if (ret_val == 0) + { + ret_val = perform_test_d (fft, class_name_0); + } + if (ret_val == 0) + { + ret_val = perform_test_i (fft, class_name_0); + } + if (ret_val == 0) + { + ret_val = perform_test_di (fft, class_name_0); + } + + if (ret_val == 0) + { + printf ("\n"); + } + + return (ret_val); +} + + + +template <class FO> +int TestAccuracy <FO>::perform_test_d (FO &fft, const char *class_name_0) +{ + assert (&fft != 0); + assert (class_name_0 != 0); + + using namespace std; + + int ret_val = 0; + const long len = fft.get_length (); + const long nbr_tests = limit ( + NBR_ACC_TESTS / len / len, + 1L, + static_cast <long> (MAX_NBR_TESTS) + ); + + printf ("Testing %s::do_fft () [%ld samples]... ", class_name_0, len); + fflush (stdout); + TestWhiteNoiseGen <DataType> noise; + std::vector <DataType> x (len); + std::vector <DataType> s1 (len); + std::vector <DataType> s2 (len); + BigFloat err_avg = 0; + + for (long test = 0; test < nbr_tests && ret_val == 0; ++ test) + { + noise.generate (&x [0], len); + fft.do_fft (&s1 [0], &x [0]); + compute_tf (&s2 [0], &x [0], len); + + BigFloat max_err; + compare_vect_display (&s1 [0], &s2 [0], len, max_err); + err_avg += max_err; + } + err_avg /= NBR_ACC_TESTS; + + printf ("done.\n"); + printf ( + "Average maximum error: %.6f %% (%f dB)\n", + static_cast <double> (err_avg * 100), + static_cast <double> ((20 / TestAccuracy_LN10) * log (err_avg)) + ); + + return (ret_val); +} + + + +template <class FO> +int TestAccuracy <FO>::perform_test_i (FO &fft, const char *class_name_0) +{ + assert (&fft != 0); + assert (class_name_0 != 0); + + using namespace std; + + int ret_val = 0; + const long len = fft.get_length (); + const long nbr_tests = limit ( + NBR_ACC_TESTS / len / len, + 10L, + static_cast <long> (MAX_NBR_TESTS) + ); + + printf ("Testing %s::do_ifft () [%ld samples]... ", class_name_0, len); + fflush (stdout); + TestWhiteNoiseGen <DataType> noise; + std::vector <DataType> s (len); + std::vector <DataType> x1 (len); + std::vector <DataType> x2 (len); + BigFloat err_avg = 0; + + for (long test = 0; test < nbr_tests && ret_val == 0; ++ test) + { + noise.generate (&s [0], len); + fft.do_ifft (&s [0], &x1 [0]); + compute_itf (&x2 [0], &s [0], len); + + BigFloat max_err; + compare_vect_display (&x1 [0], &x2 [0], len, max_err); + err_avg += max_err; + } + err_avg /= NBR_ACC_TESTS; + + printf ("done.\n"); + printf ( + "Average maximum error: %.6f %% (%f dB)\n", + static_cast <double> (err_avg * 100), + static_cast <double> ((20 / TestAccuracy_LN10) * log (err_avg)) + ); + + return (ret_val); +} + + + +template <class FO> +int TestAccuracy <FO>::perform_test_di (FO &fft, const char *class_name_0) +{ + assert (&fft != 0); + assert (class_name_0 != 0); + + using namespace std; + + int ret_val = 0; + const long len = fft.get_length (); + const long nbr_tests = limit ( + NBR_ACC_TESTS / len / len, + 1L, + static_cast <long> (MAX_NBR_TESTS) + ); + + printf ( + "Testing %s::do_fft () / do_ifft () / rescale () [%ld samples]... ", + class_name_0, + len + ); + fflush (stdout); + TestWhiteNoiseGen <DataType> noise; + std::vector <DataType> x (len); + std::vector <DataType> s (len); + std::vector <DataType> y (len); + BigFloat err_avg = 0; + + for (long test = 0; test < nbr_tests && ret_val == 0; ++ test) + { + noise.generate (&x [0], len); + fft.do_fft (&s [0], &x [0]); + fft.do_ifft (&s [0], &y [0]); + fft.rescale (&y [0]); + + BigFloat max_err; + compare_vect_display (&x [0], &y [0], len, max_err); + err_avg += max_err; + } + err_avg /= NBR_ACC_TESTS; + + printf ("done.\n"); + printf ( + "Average maximum error: %.6f %% (%f dB)\n", + static_cast <double> (err_avg * 100), + static_cast <double> ((20 / TestAccuracy_LN10) * log (err_avg)) + ); + + return (ret_val); +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +// Positive transform +template <class FO> +void TestAccuracy <FO>::compute_tf (DataType s [], const DataType x [], long length) +{ + assert (s != 0); + assert (x != 0); + assert (length >= 2); + assert ((length & 1) == 0); + + const long nbr_bins = length >> 1; + + // DC and Nyquist + BigFloat dc = 0; + BigFloat ny = 0; + for (long pos = 0; pos < length; pos += 2) + { + const BigFloat even = x [pos ]; + const BigFloat odd = x [pos + 1]; + dc += even + odd; + ny += even - odd; + } + s [0 ] = static_cast <DataType> (dc); + s [nbr_bins] = static_cast <DataType> (ny); + + // Regular bins + for (long bin = 1; bin < nbr_bins; ++ bin) + { + BigFloat sum_r = 0; + BigFloat sum_i = 0; + + const BigFloat m = bin * static_cast <BigFloat> (2 * PI) / length; + + for (long pos = 0; pos < length; ++pos) + { + using namespace std; + + const BigFloat phase = pos * m; + const BigFloat e_r = cos (phase); + const BigFloat e_i = sin (phase); + + sum_r += x [pos] * e_r; + sum_i += x [pos] * e_i; + } + + s [ bin] = static_cast <DataType> (sum_r); + s [nbr_bins + bin] = static_cast <DataType> (sum_i); + } +} + + + +// Negative transform +template <class FO> +void TestAccuracy <FO>::compute_itf (DataType x [], const DataType s [], long length) +{ + assert (s != 0); + assert (x != 0); + assert (length >= 2); + assert ((length & 1) == 0); + + const long nbr_bins = length >> 1; + + // DC and Nyquist + BigFloat dc = s [0 ]; + BigFloat ny = s [nbr_bins]; + + // Regular bins + for (long pos = 0; pos < length; ++pos) + { + BigFloat sum = dc + ny * (1 - 2 * (pos & 1)); + + const BigFloat m = pos * static_cast <BigFloat> (-2 * PI) / length; + + for (long bin = 1; bin < nbr_bins; ++ bin) + { + using namespace std; + + const BigFloat phase = bin * m; + const BigFloat e_r = cos (phase); + const BigFloat e_i = sin (phase); + + sum += 2 * ( e_r * s [bin ] + - e_i * s [bin + nbr_bins]); + } + + x [pos] = static_cast <DataType> (sum); + } +} + + + +template <class FO> +int TestAccuracy <FO>::compare_vect_display (const DataType x_ptr [], const DataType y_ptr [], long len, BigFloat &max_err_rel) +{ + assert (x_ptr != 0); + assert (y_ptr != 0); + assert (len > 0); + assert (&max_err_rel != 0); + + using namespace std; + + int ret_val = 0; + + BigFloat power = compute_power (&x_ptr [0], &y_ptr [0], len); + BigFloat power_dif; + long max_err_pos; + compare_vect (&x_ptr [0], &y_ptr [0], power_dif, max_err_pos, len); + + if (power == 0) + { + power = power_dif; + } + const BigFloat power_err_rel = power_dif / power; + + BigFloat max_err = 0; + max_err_rel = 0; + if (max_err_pos >= 0) + { + max_err = y_ptr [max_err_pos] - x_ptr [max_err_pos]; + max_err_rel = 2 * fabs (max_err) / ( fabs (y_ptr [max_err_pos]) + + fabs (x_ptr [max_err_pos])); + } + + if (power_err_rel > 0.001) + { + printf ("Power error : %f (%.6f %%)\n", + static_cast <double> (power_err_rel), + static_cast <double> (power_err_rel * 100) + ); + if (max_err_pos >= 0) + { + printf ( + "Maximum error: %f - %f = %f (%f)\n", + static_cast <double> (y_ptr [max_err_pos]), + static_cast <double> (x_ptr [max_err_pos]), + static_cast <double> (max_err), + static_cast <double> (max_err_pos) + ); + } + } + + return (ret_val); +} + + + +template <class FO> +typename TestAccuracy <FO>::BigFloat TestAccuracy <FO>::compute_power (const DataType x_ptr [], long len) +{ + assert (x_ptr != 0); + assert (len > 0); + + BigFloat power = 0; + for (long pos = 0; pos < len; ++pos) + { + const BigFloat val = x_ptr [pos]; + + power += val * val; + } + + using namespace std; + + power = sqrt (power) / len; + + return (power); +} + + + +template <class FO> +typename TestAccuracy <FO>::BigFloat TestAccuracy <FO>::compute_power (const DataType x_ptr [], const DataType y_ptr [], long len) +{ + assert (x_ptr != 0); + assert (y_ptr != 0); + assert (len > 0); + + return ((compute_power (x_ptr, len) + compute_power (y_ptr, len)) * 0.5); +} + + + +template <class FO> +void TestAccuracy <FO>::compare_vect (const DataType x_ptr [], const DataType y_ptr [], BigFloat &power, long &max_err_pos, long len) +{ + assert (x_ptr != 0); + assert (y_ptr != 0); + assert (len > 0); + assert (&power != 0); + assert (&max_err_pos != 0); + + power = 0; + BigFloat max_dif2 = 0; + max_err_pos = -1; + + for (long pos = 0; pos < len; ++pos) + { + const BigFloat x = x_ptr [pos]; + const BigFloat y = y_ptr [pos]; + const BigFloat dif = y - x; + const BigFloat dif2 = dif * dif; + + power += dif2; + if (dif2 > max_dif2) + { + max_err_pos = pos; + max_dif2 = dif2; + } + } + + using namespace std; + + power = sqrt (power) / len; +} + + + +#endif // TestAccuracy_CODEHEADER_INCLUDED + +#undef TestAccuracy_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/TestHelperFixLen.h b/demos/spectrum/fftreal/TestHelperFixLen.h new file mode 100644 index 0000000..ecff96d --- /dev/null +++ b/demos/spectrum/fftreal/TestHelperFixLen.h @@ -0,0 +1,93 @@ +/***************************************************************************** + + TestHelperFixLen.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (TestHelperFixLen_HEADER_INCLUDED) +#define TestHelperFixLen_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "FFTRealFixLen.h" + + + +template <int L> +class TestHelperFixLen +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + typedef FFTRealFixLen <L> FftType; + + static void perform_test_accuracy (int &ret_val); + static void perform_test_speed (int &ret_val); + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + TestHelperFixLen (); + ~TestHelperFixLen (); + TestHelperFixLen (const TestHelperFixLen &other); + TestHelperFixLen & + operator = (const TestHelperFixLen &other); + bool operator == (const TestHelperFixLen &other); + bool operator != (const TestHelperFixLen &other); + +}; // class TestHelperFixLen + + + +#include "TestHelperFixLen.hpp" + + + +#endif // TestHelperFixLen_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/TestHelperFixLen.hpp b/demos/spectrum/fftreal/TestHelperFixLen.hpp new file mode 100644 index 0000000..25048b9 --- /dev/null +++ b/demos/spectrum/fftreal/TestHelperFixLen.hpp @@ -0,0 +1,93 @@ +/***************************************************************************** + + TestHelperFixLen.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (TestHelperFixLen_CURRENT_CODEHEADER) + #error Recursive inclusion of TestHelperFixLen code header. +#endif +#define TestHelperFixLen_CURRENT_CODEHEADER + +#if ! defined (TestHelperFixLen_CODEHEADER_INCLUDED) +#define TestHelperFixLen_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "test_settings.h" + +#include "TestAccuracy.h" +#if defined (test_settings_SPEED_TEST_ENABLED) + #include "TestSpeed.h" +#endif + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <int L> +void TestHelperFixLen <L>::perform_test_accuracy (int &ret_val) +{ + if (ret_val == 0) + { + FftType fft; + ret_val = TestAccuracy <FftType>::perform_test_single_object (fft); + } +} + + + +template <int L> +void TestHelperFixLen <L>::perform_test_speed (int &ret_val) +{ +#if defined (test_settings_SPEED_TEST_ENABLED) + + if (ret_val == 0) + { + FftType fft; + ret_val = TestSpeed <FftType>::perform_test_single_object (fft); + } + +#endif +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +#endif // TestHelperFixLen_CODEHEADER_INCLUDED + +#undef TestHelperFixLen_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/TestHelperNormal.h b/demos/spectrum/fftreal/TestHelperNormal.h new file mode 100644 index 0000000..a7bff5c --- /dev/null +++ b/demos/spectrum/fftreal/TestHelperNormal.h @@ -0,0 +1,94 @@ +/***************************************************************************** + + TestHelperNormal.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (TestHelperNormal_HEADER_INCLUDED) +#define TestHelperNormal_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "FFTReal.h" + + + +template <class DT> +class TestHelperNormal +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + typedef DT DataType; + typedef FFTReal <DataType> FftType; + + static void perform_test_accuracy (int &ret_val); + static void perform_test_speed (int &ret_val); + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + TestHelperNormal (); + ~TestHelperNormal (); + TestHelperNormal (const TestHelperNormal &other); + TestHelperNormal & + operator = (const TestHelperNormal &other); + bool operator == (const TestHelperNormal &other); + bool operator != (const TestHelperNormal &other); + +}; // class TestHelperNormal + + + +#include "TestHelperNormal.hpp" + + + +#endif // TestHelperNormal_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/TestHelperNormal.hpp b/demos/spectrum/fftreal/TestHelperNormal.hpp new file mode 100644 index 0000000..e037696 --- /dev/null +++ b/demos/spectrum/fftreal/TestHelperNormal.hpp @@ -0,0 +1,99 @@ +/***************************************************************************** + + TestHelperNormal.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (TestHelperNormal_CURRENT_CODEHEADER) + #error Recursive inclusion of TestHelperNormal code header. +#endif +#define TestHelperNormal_CURRENT_CODEHEADER + +#if ! defined (TestHelperNormal_CODEHEADER_INCLUDED) +#define TestHelperNormal_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "test_settings.h" + +#include "TestAccuracy.h" +#if defined (test_settings_SPEED_TEST_ENABLED) + #include "TestSpeed.h" +#endif + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class DT> +void TestHelperNormal <DT>::perform_test_accuracy (int &ret_val) +{ + const int len_arr [] = { 1, 2, 3, 4, 7, 8, 10, 12 }; + const int nbr_len = sizeof (len_arr) / sizeof (len_arr [0]); + for (int k = 0; k < nbr_len && ret_val == 0; ++k) + { + const long len = 1L << (len_arr [k]); + FftType fft (len); + ret_val = TestAccuracy <FftType>::perform_test_single_object (fft); + } +} + + + +template <class DT> +void TestHelperNormal <DT>::perform_test_speed (int &ret_val) +{ +#if defined (test_settings_SPEED_TEST_ENABLED) + + const int len_arr [] = { 1, 2, 3, 4, 7, 8, 10, 12, 14, 16, 18, 20, 22 }; + const int nbr_len = sizeof (len_arr) / sizeof (len_arr [0]); + for (int k = 0; k < nbr_len && ret_val == 0; ++k) + { + const long len = 1L << (len_arr [k]); + FftType fft (len); + ret_val = TestSpeed <FftType>::perform_test_single_object (fft); + } + +#endif +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +#endif // TestHelperNormal_CODEHEADER_INCLUDED + +#undef TestHelperNormal_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/TestSpeed.h b/demos/spectrum/fftreal/TestSpeed.h new file mode 100644 index 0000000..2295781 --- /dev/null +++ b/demos/spectrum/fftreal/TestSpeed.h @@ -0,0 +1,95 @@ +/***************************************************************************** + + TestSpeed.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (TestSpeed_HEADER_INCLUDED) +#define TestSpeed_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class FO> +class TestSpeed +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + typedef typename FO::DataType DataType; + + static int perform_test_single_object (FO &fft); + static int perform_test_d (FO &fft, const char *class_name_0); + static int perform_test_i (FO &fft, const char *class_name_0); + static int perform_test_di (FO &fft, const char *class_name_0); + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + enum { NBR_SPD_TESTS = 10 * 1000 * 1000 }; + enum { MAX_NBR_TESTS = 10000 }; + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + TestSpeed (); + ~TestSpeed (); + TestSpeed (const TestSpeed &other); + TestSpeed & operator = (const TestSpeed &other); + bool operator == (const TestSpeed &other); + bool operator != (const TestSpeed &other); + +}; // class TestSpeed + + + +#include "TestSpeed.hpp" + + + +#endif // TestSpeed_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/TestSpeed.hpp b/demos/spectrum/fftreal/TestSpeed.hpp new file mode 100644 index 0000000..e716b2a --- /dev/null +++ b/demos/spectrum/fftreal/TestSpeed.hpp @@ -0,0 +1,223 @@ +/***************************************************************************** + + TestSpeed.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (TestSpeed_CURRENT_CODEHEADER) + #error Recursive inclusion of TestSpeed code header. +#endif +#define TestSpeed_CURRENT_CODEHEADER + +#if ! defined (TestSpeed_CODEHEADER_INCLUDED) +#define TestSpeed_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "test_fnc.h" +#include "stopwatch/StopWatch.h" +#include "TestWhiteNoiseGen.h" + +#include <typeinfo> + +#include <cstdio> + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class FO> +int TestSpeed <FO>::perform_test_single_object (FO &fft) +{ + assert (&fft != 0); + + int ret_val = 0; + + const std::type_info & ti = typeid (fft); + const char * class_name_0 = ti.name (); + + if (ret_val == 0) + { + perform_test_d (fft, class_name_0); + } + if (ret_val == 0) + { + perform_test_i (fft, class_name_0); + } + if (ret_val == 0) + { + perform_test_di (fft, class_name_0); + } + + if (ret_val == 0) + { + printf ("\n"); + } + + return (ret_val); +} + + + +template <class FO> +int TestSpeed <FO>::perform_test_d (FO &fft, const char *class_name_0) +{ + assert (&fft != 0); + assert (class_name_0 != 0); + + const long len = fft.get_length (); + const long nbr_tests = limit ( + static_cast <long> (NBR_SPD_TESTS / len / len), + 1L, + static_cast <long> (MAX_NBR_TESTS) + ); + + TestWhiteNoiseGen <DataType> noise; + std::vector <DataType> x (len, 0); + std::vector <DataType> s (len); + noise.generate (&x [0], len); + + printf ( + "%s::do_fft () speed test [%ld samples]... ", + class_name_0, + len + ); + fflush (stdout); + + stopwatch::StopWatch chrono; + chrono.start (); + for (long test = 0; test < nbr_tests; ++ test) + { + fft.do_fft (&s [0], &x [0]); + chrono.stop_lap (); + } + + printf ("%.1f clocks/sample\n", chrono.get_time_best_lap (len)); + + return (0); +} + + + +template <class FO> +int TestSpeed <FO>::perform_test_i (FO &fft, const char *class_name_0) +{ + assert (&fft != 0); + assert (class_name_0 != 0); + + const long len = fft.get_length (); + const long nbr_tests = limit ( + static_cast <long> (NBR_SPD_TESTS / len / len), + 1L, + static_cast <long> (MAX_NBR_TESTS) + ); + + TestWhiteNoiseGen <DataType> noise; + std::vector <DataType> x (len); + std::vector <DataType> s (len, 0); + noise.generate (&s [0], len); + + printf ( + "%s::do_ifft () speed test [%ld samples]... ", + class_name_0, + len + ); + fflush (stdout); + + stopwatch::StopWatch chrono; + chrono.start (); + for (long test = 0; test < nbr_tests; ++ test) + { + fft.do_ifft (&s [0], &x [0]); + chrono.stop_lap (); + } + + printf ("%.1f clocks/sample\n", chrono.get_time_best_lap (len)); + + return (0); +} + + + +template <class FO> +int TestSpeed <FO>::perform_test_di (FO &fft, const char *class_name_0) +{ + assert (&fft != 0); + assert (class_name_0 != 0); + + const long len = fft.get_length (); + const long nbr_tests = limit ( + static_cast <long> (NBR_SPD_TESTS / len / len), + 1L, + static_cast <long> (MAX_NBR_TESTS) + ); + + TestWhiteNoiseGen <DataType> noise; + std::vector <DataType> x (len, 0); + std::vector <DataType> s (len); + std::vector <DataType> y (len); + noise.generate (&x [0], len); + + printf ( + "%s::do_fft () / do_ifft () / rescale () speed test [%ld samples]... ", + class_name_0, + len + ); + fflush (stdout); + + stopwatch::StopWatch chrono; + + chrono.start (); + for (long test = 0; test < nbr_tests; ++ test) + { + fft.do_fft (&s [0], &x [0]); + fft.do_ifft (&s [0], &y [0]); + fft.rescale (&y [0]); + chrono.stop_lap (); + } + + printf ("%.1f clocks/sample\n", chrono.get_time_best_lap (len)); + + return (0); +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +#endif // TestSpeed_CODEHEADER_INCLUDED + +#undef TestSpeed_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/TestWhiteNoiseGen.h b/demos/spectrum/fftreal/TestWhiteNoiseGen.h new file mode 100644 index 0000000..d815f8e --- /dev/null +++ b/demos/spectrum/fftreal/TestWhiteNoiseGen.h @@ -0,0 +1,95 @@ +/***************************************************************************** + + TestWhiteNoiseGen.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (TestWhiteNoiseGen_HEADER_INCLUDED) +#define TestWhiteNoiseGen_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class DT> +class TestWhiteNoiseGen +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + typedef DT DataType; + + TestWhiteNoiseGen (); + virtual ~TestWhiteNoiseGen () {} + + void generate (DataType data_ptr [], long len); + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + typedef unsigned long StateType; + + StateType _rand_state; + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + TestWhiteNoiseGen (const TestWhiteNoiseGen &other); + TestWhiteNoiseGen & + operator = (const TestWhiteNoiseGen &other); + bool operator == (const TestWhiteNoiseGen &other); + bool operator != (const TestWhiteNoiseGen &other); + +}; // class TestWhiteNoiseGen + + + +#include "TestWhiteNoiseGen.hpp" + + + +#endif // TestWhiteNoiseGen_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/TestWhiteNoiseGen.hpp b/demos/spectrum/fftreal/TestWhiteNoiseGen.hpp new file mode 100644 index 0000000..13b7eb3 --- /dev/null +++ b/demos/spectrum/fftreal/TestWhiteNoiseGen.hpp @@ -0,0 +1,91 @@ +/***************************************************************************** + + TestWhiteNoiseGen.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (TestWhiteNoiseGen_CURRENT_CODEHEADER) + #error Recursive inclusion of TestWhiteNoiseGen code header. +#endif +#define TestWhiteNoiseGen_CURRENT_CODEHEADER + +#if ! defined (TestWhiteNoiseGen_CODEHEADER_INCLUDED) +#define TestWhiteNoiseGen_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class DT> +TestWhiteNoiseGen <DT>::TestWhiteNoiseGen () +: _rand_state (0) +{ + _rand_state = reinterpret_cast <StateType> (this); +} + + + +template <class DT> +void TestWhiteNoiseGen <DT>::generate (DataType data_ptr [], long len) +{ + assert (data_ptr != 0); + assert (len > 0); + + const DataType one = static_cast <DataType> (1); + const DataType mul = one / static_cast <DataType> (0x80000000UL); + + long pos = 0; + do + { + const DataType x = static_cast <DataType> (_rand_state & 0xFFFFFFFFUL); + data_ptr [pos] = x * mul - one; + + _rand_state = _rand_state * 1234567UL + 890123UL; + + ++ pos; + } + while (pos < len); +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +#endif // TestWhiteNoiseGen_CODEHEADER_INCLUDED + +#undef TestWhiteNoiseGen_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/bwins/fftrealu.def b/demos/spectrum/fftreal/bwins/fftrealu.def new file mode 100644 index 0000000..7a79397 --- /dev/null +++ b/demos/spectrum/fftreal/bwins/fftrealu.def @@ -0,0 +1,5 @@ +EXPORTS + ??0FFTRealWrapper@@QAE@XZ @ 1 NONAME ; FFTRealWrapper::FFTRealWrapper(void) + ??1FFTRealWrapper@@QAE@XZ @ 2 NONAME ; FFTRealWrapper::~FFTRealWrapper(void) + ?calculateFFT@FFTRealWrapper@@QAEXQAMQBM@Z @ 3 NONAME ; void FFTRealWrapper::calculateFFT(float * const, float const * const) + diff --git a/demos/spectrum/fftreal/def.h b/demos/spectrum/fftreal/def.h new file mode 100644 index 0000000..99c545f --- /dev/null +++ b/demos/spectrum/fftreal/def.h @@ -0,0 +1,60 @@ +/***************************************************************************** + + def.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (def_HEADER_INCLUDED) +#define def_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + + +const double PI = 3.1415926535897932384626433832795; +const double SQRT2 = 1.41421356237309514547462185873883; + +#if defined (_MSC_VER) + + #define FORCEINLINE __forceinline + +#else + + #define FORCEINLINE inline + +#endif + + + +#endif // def_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/eabi/fftrealu.def b/demos/spectrum/fftreal/eabi/fftrealu.def new file mode 100644 index 0000000..f95a441 --- /dev/null +++ b/demos/spectrum/fftreal/eabi/fftrealu.def @@ -0,0 +1,7 @@ +EXPORTS + _ZN14FFTRealWrapper12calculateFFTEPfPKf @ 1 NONAME + _ZN14FFTRealWrapperC1Ev @ 2 NONAME + _ZN14FFTRealWrapperC2Ev @ 3 NONAME + _ZN14FFTRealWrapperD1Ev @ 4 NONAME + _ZN14FFTRealWrapperD2Ev @ 5 NONAME + diff --git a/demos/spectrum/fftreal/fftreal.pas b/demos/spectrum/fftreal/fftreal.pas new file mode 100644 index 0000000..ea63754 --- /dev/null +++ b/demos/spectrum/fftreal/fftreal.pas @@ -0,0 +1,661 @@ +(***************************************************************************** + + DIGITAL SIGNAL PROCESSING TOOLS + Version 1.03, 2001/06/15 + (c) 1999 - Laurent de Soras + + FFTReal.h + Fourier transformation of real number arrays. + Portable ISO C++ + +------------------------------------------------------------------------------ + + LEGAL + + Source code may be freely used for any purpose, including commercial + applications. Programs must display in their "About" dialog-box (or + documentation) a text telling they use these routines by Laurent de Soras. + Modified source code can be distributed, but modifications must be clearly + indicated. + + CONTACT + + Laurent de Soras + 92 avenue Albert 1er + 92500 Rueil-Malmaison + France + + ldesoras@club-internet.fr + +------------------------------------------------------------------------------ + + Translation to ObjectPascal by : + Frederic Vanmol + frederic@axiworld.be + +*****************************************************************************) + + +unit + FFTReal; + +interface + +uses + Windows; + +(* Change this typedef to use a different floating point type in your FFTs + (i.e. float, double or long double). *) +type + pflt_t = ^flt_t; + flt_t = single; + + pflt_array = ^flt_array; + flt_array = array[0..0] of flt_t; + + plongarray = ^longarray; + longarray = array[0..0] of longint; + +const + sizeof_flt : longint = SizeOf(flt_t); + + + +type + // Bit reversed look-up table nested class + TBitReversedLUT = class + private + _ptr : plongint; + public + constructor Create(const nbr_bits: integer); + destructor Destroy; override; + function get_ptr: plongint; + end; + + // Trigonometric look-up table nested class + TTrigoLUT = class + private + _ptr : pflt_t; + public + constructor Create(const nbr_bits: integer); + destructor Destroy; override; + function get_ptr(const level: integer): pflt_t; + end; + + TFFTReal = class + private + _bit_rev_lut : TBitReversedLUT; + _trigo_lut : TTrigoLUT; + _sqrt2_2 : flt_t; + _length : longint; + _nbr_bits : integer; + _buffer_ptr : pflt_t; + public + constructor Create(const length: longint); + destructor Destroy; override; + + procedure do_fft(f: pflt_array; const x: pflt_array); + procedure do_ifft(const f: pflt_array; x: pflt_array); + procedure rescale(x: pflt_array); + end; + + + + + + + +implementation + +uses + Math; + +{ TBitReversedLUT } + +constructor TBitReversedLUT.Create(const nbr_bits: integer); +var + length : longint; + cnt : longint; + br_index : longint; + bit : longint; +begin + inherited Create; + + length := 1 shl nbr_bits; + GetMem(_ptr, length*SizeOf(longint)); + + br_index := 0; + plongarray(_ptr)^[0] := 0; + for cnt := 1 to length-1 do + begin + // ++br_index (bit reversed) + bit := length shr 1; + br_index := br_index xor bit; + while br_index and bit = 0 do + begin + bit := bit shr 1; + br_index := br_index xor bit; + end; + + plongarray(_ptr)^[cnt] := br_index; + end; +end; + +destructor TBitReversedLUT.Destroy; +begin + FreeMem(_ptr); + _ptr := nil; + inherited; +end; + +function TBitReversedLUT.get_ptr: plongint; +begin + Result := _ptr; +end; + +{ TTrigLUT } + +constructor TTrigoLUT.Create(const nbr_bits: integer); +var + total_len : longint; + PI : double; + level : integer; + level_len : longint; + level_ptr : pflt_array; + mul : double; + i : longint; +begin + inherited Create; + + _ptr := nil; + + if (nbr_bits > 3) then + begin + total_len := (1 shl (nbr_bits - 1)) - 4; + GetMem(_ptr, total_len * sizeof_flt); + + PI := ArcTan(1) * 4; + for level := 3 to nbr_bits-1 do + begin + level_len := 1 shl (level - 1); + level_ptr := pointer(get_ptr(level)); + mul := PI / (level_len shl 1); + + for i := 0 to level_len-1 do + level_ptr^[i] := cos(i * mul); + end; + end; +end; + +destructor TTrigoLUT.Destroy; +begin + FreeMem(_ptr); + _ptr := nil; + inherited; +end; + +function TTrigoLUT.get_ptr(const level: integer): pflt_t; +var + tempp : pflt_t; +begin + tempp := _ptr; + inc(tempp, (1 shl (level-1)) - 4); + Result := tempp; +end; + +{ TFFTReal } + +constructor TFFTReal.Create(const length: longint); +begin + inherited Create; + + _length := length; + _nbr_bits := Floor(Ln(length) / Ln(2) + 0.5); + _bit_rev_lut := TBitReversedLUT.Create(Floor(Ln(length) / Ln(2) + 0.5)); + _trigo_lut := TTrigoLUT.Create(Floor(Ln(length) / Ln(2) + 0.05)); + _sqrt2_2 := Sqrt(2) * 0.5; + + _buffer_ptr := nil; + if _nbr_bits > 2 then + GetMem(_buffer_ptr, _length * sizeof_flt); +end; + +destructor TFFTReal.Destroy; +begin + if _buffer_ptr <> nil then + begin + FreeMem(_buffer_ptr); + _buffer_ptr := nil; + end; + + _bit_rev_lut.Free; + _bit_rev_lut := nil; + _trigo_lut.Free; + _trigo_lut := nil; + + inherited; +end; + +(*==========================================================================*/ +/* Name: do_fft */ +/* Description: Compute the FFT of the array. */ +/* Input parameters: */ +/* - x: pointer on the source array (time). */ +/* Output parameters: */ +/* - f: pointer on the destination array (frequencies). */ +/* f [0...length(x)/2] = real values, */ +/* f [length(x)/2+1...length(x)-1] = imaginary values of */ +/* coefficents 1...length(x)/2-1. */ +/*==========================================================================*) +procedure TFFTReal.do_fft(f: pflt_array; const x: pflt_array); +var + sf, df : pflt_array; + pass : integer; + nbr_coef : longint; + h_nbr_coef : longint; + d_nbr_coef : longint; + coef_index : longint; + bit_rev_lut_ptr : plongarray; + rev_index_0 : longint; + rev_index_1 : longint; + rev_index_2 : longint; + rev_index_3 : longint; + df2 : pflt_array; + n1, n2, n3 : integer; + sf_0, sf_2 : flt_t; + sqrt2_2 : flt_t; + v : flt_t; + cos_ptr : pflt_array; + i : longint; + sf1r, sf2r : pflt_array; + dfr, dfi : pflt_array; + sf1i, sf2i : pflt_array; + c, s : flt_t; + temp_ptr : pflt_array; + b_0, b_2 : flt_t; +begin + n1 := 1; + n2 := 2; + n3 := 3; + + (*______________________________________________ + * + * General case + *______________________________________________ + *) + + if _nbr_bits > 2 then + begin + if _nbr_bits and 1 <> 0 then + begin + df := pointer(_buffer_ptr); + sf := f; + end + else + begin + df := f; + sf := pointer(_buffer_ptr); + end; + + // + // Do the transformation in several passes + // + + // First and second pass at once + bit_rev_lut_ptr := pointer(_bit_rev_lut.get_ptr); + coef_index := 0; + + repeat + rev_index_0 := bit_rev_lut_ptr^[coef_index]; + rev_index_1 := bit_rev_lut_ptr^[coef_index + 1]; + rev_index_2 := bit_rev_lut_ptr^[coef_index + 2]; + rev_index_3 := bit_rev_lut_ptr^[coef_index + 3]; + + df2 := pointer(longint(df) + (coef_index*sizeof_flt)); + df2^[n1] := x^[rev_index_0] - x^[rev_index_1]; + df2^[n3] := x^[rev_index_2] - x^[rev_index_3]; + + sf_0 := x^[rev_index_0] + x^[rev_index_1]; + sf_2 := x^[rev_index_2] + x^[rev_index_3]; + + df2^[0] := sf_0 + sf_2; + df2^[n2] := sf_0 - sf_2; + + inc(coef_index, 4); + until (coef_index >= _length); + + + // Third pass + coef_index := 0; + sqrt2_2 := _sqrt2_2; + + repeat + sf^[coef_index] := df^[coef_index] + df^[coef_index + 4]; + sf^[coef_index + 4] := df^[coef_index] - df^[coef_index + 4]; + sf^[coef_index + 2] := df^[coef_index + 2]; + sf^[coef_index + 6] := df^[coef_index + 6]; + + v := (df [coef_index + 5] - df^[coef_index + 7]) * sqrt2_2; + sf^[coef_index + 1] := df^[coef_index + 1] + v; + sf^[coef_index + 3] := df^[coef_index + 1] - v; + + v := (df^[coef_index + 5] + df^[coef_index + 7]) * sqrt2_2; + sf [coef_index + 5] := v + df^[coef_index + 3]; + sf [coef_index + 7] := v - df^[coef_index + 3]; + + inc(coef_index, 8); + until (coef_index >= _length); + + + // Next pass + for pass := 3 to _nbr_bits-1 do + begin + coef_index := 0; + nbr_coef := 1 shl pass; + h_nbr_coef := nbr_coef shr 1; + d_nbr_coef := nbr_coef shl 1; + + cos_ptr := pointer(_trigo_lut.get_ptr(pass)); + repeat + sf1r := pointer(longint(sf) + (coef_index * sizeof_flt)); + sf2r := pointer(longint(sf1r) + (nbr_coef * sizeof_flt)); + dfr := pointer(longint(df) + (coef_index * sizeof_flt)); + dfi := pointer(longint(dfr) + (nbr_coef * sizeof_flt)); + + // Extreme coefficients are always real + dfr^[0] := sf1r^[0] + sf2r^[0]; + dfi^[0] := sf1r^[0] - sf2r^[0]; // dfr [nbr_coef] = + dfr^[h_nbr_coef] := sf1r^[h_nbr_coef]; + dfi^[h_nbr_coef] := sf2r^[h_nbr_coef]; + + // Others are conjugate complex numbers + sf1i := pointer(longint(sf1r) + (h_nbr_coef * sizeof_flt)); + sf2i := pointer(longint(sf1i) + (nbr_coef * sizeof_flt)); + + for i := 1 to h_nbr_coef-1 do + begin + c := cos_ptr^[i]; // cos (i*PI/nbr_coef); + s := cos_ptr^[h_nbr_coef - i]; // sin (i*PI/nbr_coef); + + v := sf2r^[i] * c - sf2i^[i] * s; + dfr^[i] := sf1r^[i] + v; + dfi^[-i] := sf1r^[i] - v; // dfr [nbr_coef - i] = + + v := sf2r^[i] * s + sf2i^[i] * c; + dfi^[i] := v + sf1i^[i]; + dfi^[nbr_coef - i] := v - sf1i^[i]; + end; + + inc(coef_index, d_nbr_coef); + until (coef_index >= _length); + + // Prepare to the next pass + temp_ptr := df; + df := sf; + sf := temp_ptr; + end; + end + + (*______________________________________________ + * + * Special cases + *______________________________________________ + *) + + // 4-point FFT + else if _nbr_bits = 2 then + begin + f^[n1] := x^[0] - x^[n2]; + f^[n3] := x^[n1] - x^[n3]; + + b_0 := x^[0] + x^[n2]; + b_2 := x^[n1] + x^[n3]; + + f^[0] := b_0 + b_2; + f^[n2] := b_0 - b_2; + end + + // 2-point FFT + else if _nbr_bits = 1 then + begin + f^[0] := x^[0] + x^[n1]; + f^[n1] := x^[0] - x^[n1]; + end + + // 1-point FFT + else + f^[0] := x^[0]; +end; + + +(*==========================================================================*/ +/* Name: do_ifft */ +/* Description: Compute the inverse FFT of the array. Notice that */ +/* IFFT (FFT (x)) = x * length (x). Data must be */ +/* post-scaled. */ +/* Input parameters: */ +/* - f: pointer on the source array (frequencies). */ +/* f [0...length(x)/2] = real values, */ +/* f [length(x)/2+1...length(x)-1] = imaginary values of */ +/* coefficents 1...length(x)/2-1. */ +/* Output parameters: */ +/* - x: pointer on the destination array (time). */ +/*==========================================================================*) +procedure TFFTReal.do_ifft(const f: pflt_array; x: pflt_array); +var + n1, n2, n3 : integer; + n4, n5, n6, n7 : integer; + sf, df, df_temp : pflt_array; + pass : integer; + nbr_coef : longint; + h_nbr_coef : longint; + d_nbr_coef : longint; + coef_index : longint; + cos_ptr : pflt_array; + i : longint; + sfr, sfi : pflt_array; + df1r, df2r : pflt_array; + df1i, df2i : pflt_array; + c, s, vr, vi : flt_t; + temp_ptr : pflt_array; + sqrt2_2 : flt_t; + bit_rev_lut_ptr : plongarray; + sf2 : pflt_array; + b_0, b_1, b_2, b_3 : flt_t; +begin + n1 := 1; + n2 := 2; + n3 := 3; + n4 := 4; + n5 := 5; + n6 := 6; + n7 := 7; + + (*______________________________________________ + * + * General case + *______________________________________________ + *) + + if _nbr_bits > 2 then + begin + sf := f; + + if _nbr_bits and 1 <> 0 then + begin + df := pointer(_buffer_ptr); + df_temp := x; + end + else + begin + df := x; + df_temp := pointer(_buffer_ptr); + end; + + // Do the transformation in several pass + + // First pass + for pass := _nbr_bits-1 downto 3 do + begin + coef_index := 0; + nbr_coef := 1 shl pass; + h_nbr_coef := nbr_coef shr 1; + d_nbr_coef := nbr_coef shl 1; + + cos_ptr := pointer(_trigo_lut.get_ptr(pass)); + + repeat + sfr := pointer(longint(sf) + (coef_index*sizeof_flt)); + sfi := pointer(longint(sfr) + (nbr_coef*sizeof_flt)); + df1r := pointer(longint(df) + (coef_index*sizeof_flt)); + df2r := pointer(longint(df1r) + (nbr_coef*sizeof_flt)); + + // Extreme coefficients are always real + df1r^[0] := sfr^[0] + sfi^[0]; // + sfr [nbr_coef] + df2r^[0] := sfr^[0] - sfi^[0]; // - sfr [nbr_coef] + df1r^[h_nbr_coef] := sfr^[h_nbr_coef] * 2; + df2r^[h_nbr_coef] := sfi^[h_nbr_coef] * 2; + + // Others are conjugate complex numbers + df1i := pointer(longint(df1r) + (h_nbr_coef*sizeof_flt)); + df2i := pointer(longint(df1i) + (nbr_coef*sizeof_flt)); + + for i := 1 to h_nbr_coef-1 do + begin + df1r^[i] := sfr^[i] + sfi^[-i]; // + sfr [nbr_coef - i] + df1i^[i] := sfi^[i] - sfi^[nbr_coef - i]; + + c := cos_ptr^[i]; // cos (i*PI/nbr_coef); + s := cos_ptr^[h_nbr_coef - i]; // sin (i*PI/nbr_coef); + vr := sfr^[i] - sfi^[-i]; // - sfr [nbr_coef - i] + vi := sfi^[i] + sfi^[nbr_coef - i]; + + df2r^[i] := vr * c + vi * s; + df2i^[i] := vi * c - vr * s; + end; + + inc(coef_index, d_nbr_coef); + until (coef_index >= _length); + + + // Prepare to the next pass + if (pass < _nbr_bits - 1) then + begin + temp_ptr := df; + df := sf; + sf := temp_ptr; + end + else + begin + sf := df; + df := df_temp; + end + end; + + // Antepenultimate pass + sqrt2_2 := _sqrt2_2; + coef_index := 0; + + repeat + df^[coef_index] := sf^[coef_index] + sf^[coef_index + 4]; + df^[coef_index + 4] := sf^[coef_index] - sf^[coef_index + 4]; + df^[coef_index + 2] := sf^[coef_index + 2] * 2; + df^[coef_index + 6] := sf^[coef_index + 6] * 2; + + df^[coef_index + 1] := sf^[coef_index + 1] + sf^[coef_index + 3]; + df^[coef_index + 3] := sf^[coef_index + 5] - sf^[coef_index + 7]; + + vr := sf^[coef_index + 1] - sf^[coef_index + 3]; + vi := sf^[coef_index + 5] + sf^[coef_index + 7]; + + df^[coef_index + 5] := (vr + vi) * sqrt2_2; + df^[coef_index + 7] := (vi - vr) * sqrt2_2; + + inc(coef_index, 8); + until (coef_index >= _length); + + + // Penultimate and last pass at once + coef_index := 0; + bit_rev_lut_ptr := pointer(_bit_rev_lut.get_ptr); + sf2 := df; + + repeat + b_0 := sf2^[0] + sf2^[n2]; + b_2 := sf2^[0] - sf2^[n2]; + b_1 := sf2^[n1] * 2; + b_3 := sf2^[n3] * 2; + + x^[bit_rev_lut_ptr^[0]] := b_0 + b_1; + x^[bit_rev_lut_ptr^[n1]] := b_0 - b_1; + x^[bit_rev_lut_ptr^[n2]] := b_2 + b_3; + x^[bit_rev_lut_ptr^[n3]] := b_2 - b_3; + + b_0 := sf2^[n4] + sf2^[n6]; + b_2 := sf2^[n4] - sf2^[n6]; + b_1 := sf2^[n5] * 2; + b_3 := sf2^[n7] * 2; + + x^[bit_rev_lut_ptr^[n4]] := b_0 + b_1; + x^[bit_rev_lut_ptr^[n5]] := b_0 - b_1; + x^[bit_rev_lut_ptr^[n6]] := b_2 + b_3; + x^[bit_rev_lut_ptr^[n7]] := b_2 - b_3; + + inc(sf2, 8); + inc(coef_index, 8); + inc(bit_rev_lut_ptr, 8); + until (coef_index >= _length); + end + + (*______________________________________________ + * + * Special cases + *______________________________________________ + *) + + // 4-point IFFT + else if _nbr_bits = 2 then + begin + b_0 := f^[0] + f [n2]; + b_2 := f^[0] - f [n2]; + + x^[0] := b_0 + f [n1] * 2; + x^[n2] := b_0 - f [n1] * 2; + x^[n1] := b_2 + f [n3] * 2; + x^[n3] := b_2 - f [n3] * 2; + end + + // 2-point IFFT + else if _nbr_bits = 1 then + begin + x^[0] := f^[0] + f^[n1]; + x^[n1] := f^[0] - f^[n1]; + end + + // 1-point IFFT + else + x^[0] := f^[0]; +end; + +(*==========================================================================*/ +/* Name: rescale */ +/* Description: Scale an array by divide each element by its length. */ +/* This function should be called after FFT + IFFT. */ +/* Input/Output parameters: */ +/* - x: pointer on array to rescale (time or frequency). */ +/*==========================================================================*) +procedure TFFTReal.rescale(x: pflt_array); +var + mul : flt_t; + i : longint; +begin + mul := 1.0 / _length; + i := _length - 1; + + repeat + x^[i] := x^[i] * mul; + dec(i); + until (i < 0); +end; + +end. diff --git a/demos/spectrum/fftreal/fftreal.pro b/demos/spectrum/fftreal/fftreal.pro new file mode 100644 index 0000000..786a962 --- /dev/null +++ b/demos/spectrum/fftreal/fftreal.pro @@ -0,0 +1,41 @@ +TEMPLATE = lib +TARGET = fftreal + +# FFTReal +HEADERS += Array.h \ + Array.hpp \ + DynArray.h \ + DynArray.hpp \ + FFTRealFixLen.h \ + FFTRealFixLen.hpp \ + FFTRealFixLenParam.h \ + FFTRealPassDirect.h \ + FFTRealPassDirect.hpp \ + FFTRealPassInverse.h \ + FFTRealPassInverse.hpp \ + FFTRealSelect.h \ + FFTRealSelect.hpp \ + FFTRealUseTrigo.h \ + FFTRealUseTrigo.hpp \ + OscSinCos.h \ + OscSinCos.hpp \ + def.h + +# Wrapper used to export the required instantiation of the FFTRealFixLen template +HEADERS += fftreal_wrapper.h +SOURCES += fftreal_wrapper.cpp + +DEFINES += FFTREAL_LIBRARY + +symbian { + # Provide unique ID for the generated binary, required by Symbian OS + TARGET.UID3 = 0xA000E3FB +} else { + macx { + CONFIG += lib_bundle + } else { + DESTDIR = ../bin + } +} + + diff --git a/demos/spectrum/fftreal/fftreal_wrapper.cpp b/demos/spectrum/fftreal/fftreal_wrapper.cpp new file mode 100644 index 0000000..50ab36d --- /dev/null +++ b/demos/spectrum/fftreal/fftreal_wrapper.cpp @@ -0,0 +1,54 @@ +/*************************************************************************** +** +** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the examples of the Qt Toolkit. +** +** This program is free software: you can redistribute it and/or modify +** it under the terms of the GNU Lesser General Public License as +** published by the Free Software Foundation, either version 2.1. 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, see +** <http://www.gnu.org/licenses/>. +** +***************************************************************************/ + +#include "fftreal_wrapper.h" + +// FFTReal code generates quite a lot of 'unused parameter' compiler warnings, +// which we suppress here in order to get a clean build output. +#if defined Q_CC_MSVC +# pragma warning(disable:4100) +#elif defined Q_CC_GNU +# pragma GCC diagnostic ignored "-Wunused-parameter" +#elif defined Q_CC_MWERKS +# pragma warning off (10182) +#endif + +#include "FFTRealFixLen.h" + +class FFTRealWrapperPrivate { +public: + FFTRealFixLen<FFTLengthPowerOfTwo> m_fft; +}; + + +FFTRealWrapper::FFTRealWrapper() + : m_private(new FFTRealWrapperPrivate) +{ + +} + +FFTRealWrapper::~FFTRealWrapper() +{ + delete m_private; +} + +void FFTRealWrapper::calculateFFT(DataType in[], const DataType out[]) +{ + m_private->m_fft.do_fft(in, out); +} diff --git a/demos/spectrum/fftreal/fftreal_wrapper.h b/demos/spectrum/fftreal/fftreal_wrapper.h new file mode 100644 index 0000000..48d614e --- /dev/null +++ b/demos/spectrum/fftreal/fftreal_wrapper.h @@ -0,0 +1,63 @@ +/*************************************************************************** +** +** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the examples of the Qt Toolkit. +** +** This program is free software: you can redistribute it and/or modify +** it under the terms of the GNU Lesser General Public License as +** published by the Free Software Foundation, either version 2.1. 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, see +** <http://www.gnu.org/licenses/>. +** +***************************************************************************/ + +#ifndef FFTREAL_WRAPPER_H +#define FFTREAL_WRAPPER_H + +#include <QtCore/QtGlobal> + +#if defined(FFTREAL_LIBRARY) +# define FFTREAL_EXPORT Q_DECL_EXPORT +#else +# define FFTREAL_EXPORT Q_DECL_IMPORT +#endif + +class FFTRealWrapperPrivate; + +// Each pass of the FFT processes 2^X samples, where X is the +// number below. +static const int FFTLengthPowerOfTwo = 12; + +/** + * Wrapper around the FFTRealFixLen template provided by the FFTReal + * library + * + * This class instantiates a single instance of FFTRealFixLen, using + * FFTLengthPowerOfTwo as the template parameter. It then exposes + * FFTRealFixLen<FFTLengthPowerOfTwo>::do_fft via the calculateFFT + * function, thereby allowing an application to dynamically link + * against the FFTReal implementation. + * + * See http://ldesoras.free.fr/prod.html + */ +class FFTREAL_EXPORT FFTRealWrapper +{ +public: + FFTRealWrapper(); + ~FFTRealWrapper(); + + typedef float DataType; + void calculateFFT(DataType in[], const DataType out[]); + +private: + FFTRealWrapperPrivate* m_private; +}; + +#endif // FFTREAL_WRAPPER_H + diff --git a/demos/spectrum/fftreal/license.txt b/demos/spectrum/fftreal/license.txt new file mode 100644 index 0000000..918fe68 --- /dev/null +++ b/demos/spectrum/fftreal/license.txt @@ -0,0 +1,459 @@ + GNU LESSER GENERAL PUBLIC LICENSE + Version 2.1, February 1999 + + Copyright (C) 1991, 1999 Free Software Foundation, Inc. + 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + +[This is the first released version of the Lesser GPL. It also counts + as the successor of the GNU Library Public License, version 2, hence + the version number 2.1.] + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +Licenses are intended to guarantee your freedom to share and change +free software--to make sure the software is free for all its users. + + This license, the Lesser General Public License, applies to some +specially designated software packages--typically libraries--of the +Free Software Foundation and other authors who decide to use it. You +can use it too, but we suggest you first think carefully about whether +this license or the ordinary General Public License is the better +strategy to use in any particular case, based on the explanations below. + + When we speak of free software, we are referring to freedom of use, +not price. Our General Public Licenses are designed to make sure that +you have the freedom to distribute copies of free software (and charge +for this service if you wish); that you receive source code or can get +it if you want it; that you can change the software and use pieces of +it in new free programs; and that you are informed that you can do +these things. + + To protect your rights, we need to make restrictions that forbid +distributors to deny you these rights or to ask you to surrender these +rights. These restrictions translate to certain responsibilities for +you if you distribute copies of the library or if you modify it. + + For example, if you distribute copies of the library, whether gratis +or for a fee, you must give the recipients all the rights that we gave +you. You must make sure that they, too, receive or can get the source +code. If you link other code with the library, you must provide +complete object files to the recipients, so that they can relink them +with the library after making changes to the library and recompiling +it. And you must show them these terms so they know their rights. + + We protect your rights with a two-step method: (1) we copyright the +library, and (2) we offer you this license, which gives you legal +permission to copy, distribute and/or modify the library. + + To protect each distributor, we want to make it very clear that +there is no warranty for the free library. Also, if the library is +modified by someone else and passed on, the recipients should know +that what they have is not the original version, so that the original +author's reputation will not be affected by problems that might be +introduced by others. + + Finally, software patents pose a constant threat to the existence of +any free program. We wish to make sure that a company cannot +effectively restrict the users of a free program by obtaining a +restrictive license from a patent holder. Therefore, we insist that +any patent license obtained for a version of the library must be +consistent with the full freedom of use specified in this license. + + Most GNU software, including some libraries, is covered by the +ordinary GNU General Public License. This license, the GNU Lesser +General Public License, applies to certain designated libraries, and +is quite different from the ordinary General Public License. We use +this license for certain libraries in order to permit linking those +libraries into non-free programs. + + When a program is linked with a library, whether statically or using +a shared library, the combination of the two is legally speaking a +combined work, a derivative of the original library. The ordinary +General Public License therefore permits such linking only if the +entire combination fits its criteria of freedom. The Lesser General +Public License permits more lax criteria for linking other code with +the library. + + We call this license the "Lesser" General Public License because it +does Less to protect the user's freedom than the ordinary General +Public License. It also provides other free software developers Less +of an advantage over competing non-free programs. These disadvantages +are the reason we use the ordinary General Public License for many +libraries. However, the Lesser license provides advantages in certain +special circumstances. + + For example, on rare occasions, there may be a special need to +encourage the widest possible use of a certain library, so that it becomes +a de-facto standard. To achieve this, non-free programs must be +allowed to use the library. A more frequent case is that a free +library does the same job as widely used non-free libraries. In this +case, there is little to gain by limiting the free library to free +software only, so we use the Lesser General Public License. + + In other cases, permission to use a particular library in non-free +programs enables a greater number of people to use a large body of +free software. For example, permission to use the GNU C Library in +non-free programs enables many more people to use the whole GNU +operating system, as well as its variant, the GNU/Linux operating +system. + + Although the Lesser General Public License is Less protective of the +users' freedom, it does ensure that the user of a program that is +linked with the Library has the freedom and the wherewithal to run +that program using a modified version of the Library. + + The precise terms and conditions for copying, distribution and +modification follow. Pay close attention to the difference between a +"work based on the library" and a "work that uses the library". The +former contains code derived from the library, whereas the latter must +be combined with the library in order to run. + + GNU LESSER GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License Agreement applies to any software library or other +program which contains a notice placed by the copyright holder or +other authorized party saying it may be distributed under the terms of +this Lesser General Public License (also called "this License"). +Each licensee is addressed as "you". + + A "library" means a collection of software functions and/or data +prepared so as to be conveniently linked with application programs +(which use some of those functions and data) to form executables. + + The "Library", below, refers to any such software library or work +which has been distributed under these terms. A "work based on the +Library" means either the Library or any derivative work under +copyright law: that is to say, a work containing the Library or a +portion of it, either verbatim or with modifications and/or translated +straightforwardly into another language. (Hereinafter, translation is +included without limitation in the term "modification".) + + "Source code" for a work means the preferred form of the work for +making modifications to it. For a library, complete source code means +all the source code for all modules it contains, plus any associated +interface definition files, plus the scripts used to control compilation +and installation of the library. + + Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running a program using the Library is not restricted, and output from +such a program is covered only if its contents constitute a work based +on the Library (independent of the use of the Library in a tool for +writing it). Whether that is true depends on what the Library does +and what the program that uses the Library does. + + 1. You may copy and distribute verbatim copies of the Library's +complete source code as you receive it, in any medium, provided that +you conspicuously and appropriately publish on each copy an +appropriate copyright notice and disclaimer of warranty; keep intact +all the notices that refer to this License and to the absence of any +warranty; and distribute a copy of this License along with the +Library. + + You may charge a fee for the physical act of transferring a copy, +and you may at your option offer warranty protection in exchange for a +fee. + + 2. You may modify your copy or copies of the Library or any portion +of it, thus forming a work based on the Library, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) The modified work must itself be a software library. + + b) You must cause the files modified to carry prominent notices + stating that you changed the files and the date of any change. + + c) You must cause the whole of the work to be licensed at no + charge to all third parties under the terms of this License. + + d) If a facility in the modified Library refers to a function or a + table of data to be supplied by an application program that uses + the facility, other than as an argument passed when the facility + is invoked, then you must make a good faith effort to ensure that, + in the event an application does not supply such function or + table, the facility still operates, and performs whatever part of + its purpose remains meaningful. + + (For example, a function in a library to compute square roots has + a purpose that is entirely well-defined independent of the + application. Therefore, Subsection 2d requires that any + application-supplied function or table used by this function must + be optional: if the application does not supply it, the square + root function must still compute square roots.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Library, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Library, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote +it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Library. + +In addition, mere aggregation of another work not based on the Library +with the Library (or with a work based on the Library) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may opt to apply the terms of the ordinary GNU General Public +License instead of this License to a given copy of the Library. To do +this, you must alter all the notices that refer to this License, so +that they refer to the ordinary GNU General Public License, version 2, +instead of to this License. (If a newer version than version 2 of the +ordinary GNU General Public License has appeared, then you can specify +that version instead if you wish.) Do not make any other change in +these notices. + + Once this change is made in a given copy, it is irreversible for +that copy, so the ordinary GNU General Public License applies to all +subsequent copies and derivative works made from that copy. + + This option is useful when you wish to copy part of the code of +the Library into a program that is not a library. + + 4. You may copy and distribute the Library (or a portion or +derivative of it, under Section 2) in object code or executable form +under the terms of Sections 1 and 2 above provided that you accompany +it with the complete corresponding machine-readable source code, which +must be distributed under the terms of Sections 1 and 2 above on a +medium customarily used for software interchange. + + If distribution of object code is made by offering access to copy +from a designated place, then offering equivalent access to copy the +source code from the same place satisfies the requirement to +distribute the source code, even though third parties are not +compelled to copy the source along with the object code. + + 5. A program that contains no derivative of any portion of the +Library, but is designed to work with the Library by being compiled or +linked with it, is called a "work that uses the Library". Such a +work, in isolation, is not a derivative work of the Library, and +therefore falls outside the scope of this License. + + However, linking a "work that uses the Library" with the Library +creates an executable that is a derivative of the Library (because it +contains portions of the Library), rather than a "work that uses the +library". The executable is therefore covered by this License. +Section 6 states terms for distribution of such executables. + + When a "work that uses the Library" uses material from a header file +that is part of the Library, the object code for the work may be a +derivative work of the Library even though the source code is not. +Whether this is true is especially significant if the work can be +linked without the Library, or if the work is itself a library. The +threshold for this to be true is not precisely defined by law. + + If such an object file uses only numerical parameters, data +structure layouts and accessors, and small macros and small inline +functions (ten lines or less in length), then the use of the object +file is unrestricted, regardless of whether it is legally a derivative +work. (Executables containing this object code plus portions of the +Library will still fall under Section 6.) + + Otherwise, if the work is a derivative of the Library, you may +distribute the object code for the work under the terms of Section 6. +Any executables containing that work also fall under Section 6, +whether or not they are linked directly with the Library itself. + + 6. As an exception to the Sections above, you may also combine or +link a "work that uses the Library" with the Library to produce a +work containing portions of the Library, and distribute that work +under terms of your choice, provided that the terms permit +modification of the work for the customer's own use and reverse +engineering for debugging such modifications. + + You must give prominent notice with each copy of the work that the +Library is used in it and that the Library and its use are covered by +this License. You must supply a copy of this License. If the work +during execution displays copyright notices, you must include the +copyright notice for the Library among them, as well as a reference +directing the user to the copy of this License. Also, you must do one +of these things: + + a) Accompany the work with the complete corresponding + machine-readable source code for the Library including whatever + changes were used in the work (which must be distributed under + Sections 1 and 2 above); and, if the work is an executable linked + with the Library, with the complete machine-readable "work that + uses the Library", as object code and/or source code, so that the + user can modify the Library and then relink to produce a modified + executable containing the modified Library. (It is understood + that the user who changes the contents of definitions files in the + Library will not necessarily be able to recompile the application + to use the modified definitions.) + + b) Use a suitable shared library mechanism for linking with the + Library. A suitable mechanism is one that (1) uses at run time a + copy of the library already present on the user's computer system, + rather than copying library functions into the executable, and (2) + will operate properly with a modified version of the library, if + the user installs one, as long as the modified version is + interface-compatible with the version that the work was made with. + + c) Accompany the work with a written offer, valid for at + least three years, to give the same user the materials + specified in Subsection 6a, above, for a charge no more + than the cost of performing this distribution. + + d) If distribution of the work is made by offering access to copy + from a designated place, offer equivalent access to copy the above + specified materials from the same place. + + e) Verify that the user has already received a copy of these + materials or that you have already sent this user a copy. + + For an executable, the required form of the "work that uses the +Library" must include any data and utility programs needed for +reproducing the executable from it. However, as a special exception, +the materials to be distributed need not include anything that is +normally distributed (in either source or binary form) with the major +components (compiler, kernel, and so on) of the operating system on +which the executable runs, unless that component itself accompanies +the executable. + + It may happen that this requirement contradicts the license +restrictions of other proprietary libraries that do not normally +accompany the operating system. Such a contradiction means you cannot +use both them and the Library together in an executable that you +distribute. + + 7. You may place library facilities that are a work based on the +Library side-by-side in a single library together with other library +facilities not covered by this License, and distribute such a combined +library, provided that the separate distribution of the work based on +the Library and of the other library facilities is otherwise +permitted, and provided that you do these two things: + + a) Accompany the combined library with a copy of the same work + based on the Library, uncombined with any other library + facilities. This must be distributed under the terms of the + Sections above. + + b) Give prominent notice with the combined library of the fact + that part of it is a work based on the Library, and explaining + where to find the accompanying uncombined form of the same work. + + 8. You may not copy, modify, sublicense, link with, or distribute +the Library except as expressly provided under this License. Any +attempt otherwise to copy, modify, sublicense, link with, or +distribute the Library is void, and will automatically terminate your +rights under this License. However, parties who have received copies, +or rights, from you under this License will not have their licenses +terminated so long as such parties remain in full compliance. + + 9. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Library or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Library (or any work based on the +Library), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Library or works based on it. + + 10. Each time you redistribute the Library (or any work based on the +Library), the recipient automatically receives a license from the +original licensor to copy, distribute, link with or modify the Library +subject to these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties with +this License. + + 11. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Library at all. For example, if a patent +license would not permit royalty-free redistribution of the Library by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Library. + +If any portion of this section is held invalid or unenforceable under any +particular circumstance, the balance of the section is intended to apply, +and the section as a whole is intended to apply in other circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 12. If the distribution and/or use of the Library is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Library under this License may add +an explicit geographical distribution limitation excluding those countries, +so that distribution is permitted only in or among countries not thus +excluded. In such case, this License incorporates the limitation as if +written in the body of this License. + + 13. The Free Software Foundation may publish revised and/or new +versions of the Lesser General Public License from time to time. +Such new versions will be similar in spirit to the present version, +but may differ in detail to address new problems or concerns. + +Each version is given a distinguishing version number. If the Library +specifies a version number of this License which applies to it and +"any later version", you have the option of following the terms and +conditions either of that version or of any later version published by +the Free Software Foundation. If the Library does not specify a +license version number, you may choose any version ever published by +the Free Software Foundation. + + 14. If you wish to incorporate parts of the Library into other free +programs whose distribution conditions are incompatible with these, +write to the author to ask for permission. For software which is +copyrighted by the Free Software Foundation, write to the Free +Software Foundation; we sometimes make exceptions for this. Our +decision will be guided by the two goals of preserving the free status +of all derivatives of our free software and of promoting the sharing +and reuse of software generally. + + NO WARRANTY + + 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO +WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. +EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR +OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY +KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE +LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME +THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN +WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY +AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU +FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR +CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE +LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING +RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A +FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF +SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH +DAMAGES. + + END OF TERMS AND CONDITIONS + diff --git a/demos/spectrum/fftreal/readme.txt b/demos/spectrum/fftreal/readme.txt new file mode 100644 index 0000000..0c5ce16 --- /dev/null +++ b/demos/spectrum/fftreal/readme.txt @@ -0,0 +1,242 @@ +============================================================================== + + FFTReal + Version 2.00, 2005/10/18 + + Fourier transformation (FFT, IFFT) library specialised for real data + Portable ISO C++ + + (c) Laurent de Soras <laurent.de.soras@club-internet.fr> + Object Pascal port (c) Frederic Vanmol <frederic@fruityloops.com> + +============================================================================== + + + +1. Legal +-------- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Check the file license.txt to get full information about the license. + + + +2. Content +---------- + +FFTReal is a library to compute Discrete Fourier Transforms (DFT) with the +FFT algorithm (Fast Fourier Transform) on arrays of real numbers. It can +also compute the inverse transform. + +You should find in this package a lot of files ; some of them are of interest: +- readme.txt: you are reading it +- FFTReal.h: FFT, length fixed at run-time +- FFTRealFixLen.h: FFT, length fixed at compile-time +- FFTReal.pas: Pascal implementation (working but not up-to-date) +- stopwatch directory + + + +3. Using FFTReal +---------------- + +Important - if you were using older versions of FFTReal (up to 1.03), some +things have changed. FFTReal is now a template. Therefore use FFTReal<float> +or FFTReal<double> in your code depending on the application datatype. The +flt_t typedef has been removed. + +You have two ways to use FFTReal. In the first way, the FFT has its length +fixed at run-time, when the object is instanciated. It means that you have +not to know the length when you write the code. This is the usual way of +proceeding. + + +3.1 FFTReal - Length fixed at run-time +-------------------------------------- + +Just instanciate one time a FFTReal object. Specify the data type you want +as template parameter (only floating point: float, double, long double or +custom type). The constructor precompute a lot of things, so it may be a bit +long. The parameter is the number of points used for the next FFTs. It must +be a power of 2: + + #include "FFTReal.h" + ... + long len = 1024; + ... + FFTReal <float> fft_object (len); // 1024-point FFT object constructed. + +Then you can use this object to compute as many FFTs and IFFTs as you want. +They will be computed very quickly because a lot of work has been done in the +object construction. + + float x [1024]; + float f [1024]; + + ... + fft_object.do_fft (f, x); // x (real) --FFT---> f (complex) + ... + fft_object.do_ifft (f, x); // f (complex) --IFFT--> x (real) + fft_object.rescale (x); // Post-scaling should be done after FFT+IFFT + ... + +x [] and f [] are floating point number arrays. x [] is the real number +sequence which we want to compute the FFT. f [] is the result, in the +"frequency" domain. f has the same number of elements as x [], but f [] +elements are complex numbers. The routine uses some FFT properties to +optimize memory and to reduce calculations: the transformaton of a real +number sequence is a conjugate complex number sequence: F [k] = F [-k]*. + + +3.2 FFTRealFixLen - Length fixed at compile-time +------------------------------------------------ + +This class is significantly faster than the previous one, giving a speed +gain between 50 and 100 %. The template parameter is the base-2 logarithm of +the FFT length. The datatype is float; it can be changed by modifying the +DataType typedef in FFTRealFixLenParam.h. As FFTReal class, it supports +only floating-point types or equivalent. + +To instanciate the object, just proceed as below: + + #include "FFTRealFixLen.h" + ... + FFTRealFixLen <10> fft_object; // 1024-point (2^10) FFT object constructed. + +Use is similar as the one of FFTReal. + + +3.3 Data organisation +--------------------- + +Mathematically speaking, the formulas below show what does FFTReal: + +do_fft() : f(k) = sum (p = 0, N-1, x(p) * exp (+j*2*pi*k*p/N)) +do_ifft(): x(k) = sum (p = 0, N-1, f(p) * exp (-j*2*pi*k*p/N)) + +Where j is the square root of -1. The formulas differ only by the sign of +the exponential. When the sign is positive, the transform is called positive. +Common formulas for Fourier transform are negative for the direct tranform and +positive for the inverse one. + +However in these formulas, f is an array of complex numbers and doesn't +correspound exactly to the f[] array taken as function parameter. The +following table shows how the f[] sequence is mapped onto the usable FFT +coefficients (called bins): + + FFTReal output | Positive FFT equiv. | Negative FFT equiv. + ---------------+-----------------------+----------------------- + f [0] | Real (bin 0) | Real (bin 0) + f [...] | Real (bin ...) | Real (bin ...) + f [length/2] | Real (bin length/2) | Real (bin length/2) + f [length/2+1] | Imag (bin 1) | -Imag (bin 1) + f [...] | Imag (bin ...) | -Imag (bin ...) + f [length-1] | Imag (bin length/2-1) | -Imag (bin length/2-1) + +And FFT bins are distributed in f [] as above: + + | | Positive FFT | Negative FFT + Bin | Real part | imaginary part | imaginary part + ------------+----------------+-----------------+--------------- + 0 | f [0] | 0 | 0 + 1 | f [1] | f [length/2+1] | -f [length/2+1] + ... | f [...], | f [...] | -f [...] + length/2-1 | f [length/2-1] | f [length-1] | -f [length-1] + length/2 | f [length/2] | 0 | 0 + length/2+1 | f [length/2-1] | -f [length-1] | f [length-1] + ... | f [...] | -f [...] | f [...] + length-1 | f [1] | -f [length/2+1] | f [length/2+1] + +f [] coefficients have the same layout for FFT and IFFT functions. You may +notice that scaling must be done if you want to retrieve x after FFT and IFFT. +Actually, IFFT (FFT (x)) = x * length(x). This is a not a problem because +most of the applications don't care about absolute values. Thus, the operation +requires less calculation. If you want to use the FFT and IFFT to transform a +signal, you have to apply post- (or pre-) processing yourself. Multiplying +or dividing floating point numbers by a power of 2 doesn't generate extra +computation noise. + + + +4. Compilation and testing +-------------------------- + +Drop the following files into your project or makefile: + +Array.* +def.h +DynArray.* +FFTReal*.cpp +FFTReal*.h* +OscSinCos.* + +Other files are for testing purpose only, do not include them if you just need +to use the library ; they are not needed to use FFTReal in your own programs. + +FFTReal may be compiled in two versions: release and debug. Debug version +has checks that could slow down the code. Define NDEBUG to set the Release +mode. For example, the command line to compile the test bench on GCC would +look like: + +Debug mode: +g++ -Wall -o fftreal_debug.exe *.cpp stopwatch/*.cpp + +Release mode: +g++ -Wall -o fftreal_release.exe -DNDEBUG -O3 *.cpp stopwatch/*.cpp + +It may be tricky to compile the test bench because the speed tests use the +stopwatch sub-library, which is not that cross-platform. If you encounter +any problem that you cannot easily fix while compiling it, edit the file +test_settings.h and un-define the speed test macro. Remove the stopwatch +directory from your source file list, too. + +If it's not done by default, you should activate the exception handling +of your compiler to get the class memory-leak-safe. Thus, when a memory +allocation fails (in the constructor), an exception is thrown and the entire +object is safely destructed. It reduces the permanent error checking overhead +in the client code. Also, the test bench requires Run-Time Type Information +(RTTI) to be enabled in order to display the names of the tested classes - +sometimes mangled, depending on the compiler. + +The test bench may take a long time to compile, especially in Release mode, +because a lot of recursive templates are instanciated. + + + +5. History +---------- + +v2.00 (2005.10.18) +- Turned FFTReal class into template (data type as parameter) +- Added FFTRealFixLen +- Trigonometric tables are size-limited in order to preserve cache memory; +over a given size, sin/cos functions are computed on the fly. +- Better test bench for accuracy and speed + +v1.03 (2001.06.15) +- Thanks to Frederic Vanmol for the Pascal port (works with Delphi). +- Documentation improvement + +v1.02 (2001.03.25) +- sqrt() is now precomputed when the object FFTReal is constructed, resulting +in speed impovement for small size FFT. + +v1.01 (2000) +- Small modifications, I don't remember what. + +v1.00 (1999.08.14) +- First version released + diff --git a/demos/spectrum/fftreal/stopwatch/ClockCycleCounter.cpp b/demos/spectrum/fftreal/stopwatch/ClockCycleCounter.cpp new file mode 100644 index 0000000..fe1d424 --- /dev/null +++ b/demos/spectrum/fftreal/stopwatch/ClockCycleCounter.cpp @@ -0,0 +1,285 @@ +/***************************************************************************** + + ClockCycleCounter.cpp + Copyright (c) 2003 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (_MSC_VER) + #pragma warning (1 : 4130) // "'operator' : logical operation on address of string constant" + #pragma warning (1 : 4223) // "nonstandard extension used : non-lvalue array converted to pointer" + #pragma warning (1 : 4705) // "statement has no effect" + #pragma warning (1 : 4706) // "assignment within conditional expression" + #pragma warning (4 : 4786) // "identifier was truncated to '255' characters in the debug information" + #pragma warning (4 : 4800) // "forcing value to bool 'true' or 'false' (performance warning)" + #pragma warning (4 : 4355) // "'this' : used in base member initializer list" +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "ClockCycleCounter.h" + +#include <cassert> + + + +namespace stopwatch +{ + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/* +============================================================================== +Name: ctor +Description: + The first object constructed initialise global data. This first + construction may be a bit slow. +Throws: Nothing +============================================================================== +*/ + +ClockCycleCounter::ClockCycleCounter () +: _start_time (0) +, _state (0) +, _best_score (-1) +{ + if (! _init_flag) + { + // Should be executed in this order + compute_clk_mul (); + compute_measure_time_total (); + compute_measure_time_lap (); + + // Restores object state + _start_time = 0; + _state = 0; + _best_score = -1; + + _init_flag = true; + } +} + + + +/* +============================================================================== +Name: get_time_total +Description: + Gives the time elapsed between the latest stop_lap() and start() calls. +Returns: + The duration, in clock cycles. +Throws: Nothing +============================================================================== +*/ + +Int64 ClockCycleCounter::get_time_total () const +{ + const Int64 duration = _state - _start_time; + assert (duration >= 0); + + const Int64 t = max ( + duration - _measure_time_total, + static_cast <Int64> (0) + ); + + return (t * _clk_mul); +} + + + +/* +============================================================================== +Name: get_time_best_lap +Description: + Gives the smallest time between two consecutive stop_lap() or between + the stop_lap() and start(). The value is reset by a call to start(). + Call this function only after a stop_lap(). + The time is amputed from the duration of the stop_lap() call itself. +Returns: + The smallest duration, in clock cycles. +Throws: Nothing +============================================================================== +*/ + +Int64 ClockCycleCounter::get_time_best_lap () const +{ + assert (_best_score >= 0); + + const Int64 t1 = max ( + _best_score - _measure_time_lap, + static_cast <Int64> (0) + ); + const Int64 t = min (t1, get_time_total ()); + + return (t * _clk_mul); +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +#if defined (__MACOS__) + +static inline double stopwatch_ClockCycleCounter_get_time_s () +{ + const Nanoseconds ns = AbsoluteToNanoseconds (UpTime ()); + + return (ns.hi * 4294967296e-9 + ns.lo * 1e-9); +} + +#endif // __MACOS__ + + + +/* +============================================================================== +Name: compute_clk_mul +Description: + This function, only for PowerPC/MacOS computers, computes the multiplier + required to deduce clock cycles from the internal counter. +Throws: Nothing +============================================================================== +*/ + +void ClockCycleCounter::compute_clk_mul () +{ + assert (! _init_flag); + +#if defined (__MACOS__) + + long clk_speed_mhz = CurrentProcessorSpeed (); + const Int64 clk_speed = + static_cast <Int64> (clk_speed_mhz) * (1000L*1000L); + + const double start_time_s = stopwatch_ClockCycleCounter_get_time_s (); + start (); + + const double duration = 0.01; // Seconds + while (stopwatch_ClockCycleCounter_get_time_s () - start_time_s < duration) + { + continue; + } + + const double stop_time_s = stopwatch_ClockCycleCounter_get_time_s (); + stop (); + + const double diff_time_s = stop_time_s - start_time_s; + const double nbr_cycles = diff_time_s * static_cast <double> (clk_speed); + + const Int64 diff_time_c = _state - _start_time; + const double clk_mul = nbr_cycles / static_cast <double> (diff_time_c); + + _clk_mul = round_int (clk_mul); + +#endif // __MACOS__ +} + + + +void ClockCycleCounter::compute_measure_time_total () +{ + start (); + spend_time (); + + Int64 best_result = 0x7FFFFFFFL; // Should be enough + long nbr_tests = 100; + for (long cnt = 0; cnt < nbr_tests; ++cnt) + { + start (); + stop_lap (); + const Int64 duration = _state - _start_time; + best_result = min (best_result, duration); + } + + _measure_time_total = best_result; +} + + + +/* +============================================================================== +Name: compute_measure_time_lap +Description: + Computes the duration of one stop_lap() call and store it. It will be used + later to get the real duration of the measured operation (by substracting + the measurement duration). +Throws: Nothing +============================================================================== +*/ + +void ClockCycleCounter::compute_measure_time_lap () +{ + start (); + spend_time (); + + long nbr_tests = 10; + for (long cnt = 0; cnt < nbr_tests; ++cnt) + { + stop_lap (); + stop_lap (); + stop_lap (); + stop_lap (); + } + + _measure_time_lap = _best_score; +} + + + +void ClockCycleCounter::spend_time () +{ + const Int64 nbr_clocks = 500; // Number of clock cycles to spend + + const Int64 start = read_clock_counter (); + Int64 current; + + do + { + current = read_clock_counter (); + } + while ((current - start) * _clk_mul < nbr_clocks); +} + + + +Int64 ClockCycleCounter::_measure_time_total = 0; +Int64 ClockCycleCounter::_measure_time_lap = 0; +int ClockCycleCounter::_clk_mul = 1; +bool ClockCycleCounter::_init_flag = false; + + +} // namespace stopwatch + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/stopwatch/ClockCycleCounter.h b/demos/spectrum/fftreal/stopwatch/ClockCycleCounter.h new file mode 100644 index 0000000..ba7a99a --- /dev/null +++ b/demos/spectrum/fftreal/stopwatch/ClockCycleCounter.h @@ -0,0 +1,124 @@ +/***************************************************************************** + + ClockCycleCounter.h + Copyright (c) 2003 Laurent de Soras + +Instrumentation class, for accurate time interval measurement. You may have +to modify the implementation to adapt it to your system and/or compiler. + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (stopwatch_ClockCycleCounter_HEADER_INCLUDED) +#define stopwatch_ClockCycleCounter_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "def.h" +#include "Int64.h" + + + +namespace stopwatch +{ + + + +class ClockCycleCounter +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + ClockCycleCounter (); + + stopwatch_FORCEINLINE void + start (); + stopwatch_FORCEINLINE void + stop_lap (); + Int64 get_time_total () const; + Int64 get_time_best_lap () const; + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + void compute_clk_mul (); + void compute_measure_time_total (); + void compute_measure_time_lap (); + + static void spend_time (); + static stopwatch_FORCEINLINE Int64 + read_clock_counter (); + + Int64 _start_time; + Int64 _state; + Int64 _best_score; + + static Int64 _measure_time_total; + static Int64 _measure_time_lap; + static int _clk_mul; + static bool _init_flag; + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + ClockCycleCounter (const ClockCycleCounter &other); + ClockCycleCounter & + operator = (const ClockCycleCounter &other); + bool operator == (const ClockCycleCounter &other); + bool operator != (const ClockCycleCounter &other); + +}; // class ClockCycleCounter + + + +} // namespace stopwatch + + + +#include "ClockCycleCounter.hpp" + + + +#endif // stopwatch_ClockCycleCounter_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/stopwatch/ClockCycleCounter.hpp b/demos/spectrum/fftreal/stopwatch/ClockCycleCounter.hpp new file mode 100644 index 0000000..fbd511e --- /dev/null +++ b/demos/spectrum/fftreal/stopwatch/ClockCycleCounter.hpp @@ -0,0 +1,150 @@ +/***************************************************************************** + + ClockCycleCounter.hpp + Copyright (c) 2003 Laurent de Soras + +Please complete the definitions according to your compiler/architecture. +It's not a big deal if it's not possible to get the clock count... + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (stopwatch_ClockCycleCounter_CURRENT_CODEHEADER) + #error Recursive inclusion of ClockCycleCounter code header. +#endif +#define stopwatch_ClockCycleCounter_CURRENT_CODEHEADER + +#if ! defined (stopwatch_ClockCycleCounter_CODEHEADER_INCLUDED) +#define stopwatch_ClockCycleCounter_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "fnc.h" + +#include <climits> + + + +namespace stopwatch +{ + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/* +============================================================================== +Name: start +Description: + Starts the counter. +Throws: Nothing +============================================================================== +*/ + +void ClockCycleCounter::start () +{ + _best_score = (static_cast <Int64> (1) << (sizeof (Int64) * CHAR_BIT - 2)); + const Int64 start_clock = read_clock_counter (); + _start_time = start_clock; + _state = start_clock - _best_score; +} + + + +/* +============================================================================== +Name: stop_lap +Description: + Captures the current time and updates the smallest duration between two + consecutive calls to stop_lap() or the latest start(). + start() must have been called at least once before calling this function. +Throws: Nothing +============================================================================== +*/ + +void ClockCycleCounter::stop_lap () +{ + const Int64 end_clock = read_clock_counter (); + _best_score = min (end_clock - _state, _best_score); + _state = end_clock; +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +Int64 ClockCycleCounter::read_clock_counter () +{ + register Int64 clock_cnt; + +#if defined (_MSC_VER) + + __asm + { + lea edi, clock_cnt + rdtsc + mov [edi ], eax + mov [edi + 4], edx + } + +#elif defined (__GNUC__) && defined (__i386__) + + __asm__ __volatile__ ("rdtsc" : "=A" (clock_cnt)); + +#elif (__MWERKS__) && defined (__POWERPC__) + + asm + { + loop: + mftbu clock_cnt@hiword + mftb clock_cnt@loword + mftbu r5 + cmpw clock_cnt@hiword,r5 + bne loop + } + +#endif + + return (clock_cnt); +} + + + +} // namespace stopwatch + + + +#endif // stopwatch_ClockCycleCounter_CODEHEADER_INCLUDED + +#undef stopwatch_ClockCycleCounter_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/stopwatch/Int64.h b/demos/spectrum/fftreal/stopwatch/Int64.h new file mode 100644 index 0000000..1e786e2 --- /dev/null +++ b/demos/spectrum/fftreal/stopwatch/Int64.h @@ -0,0 +1,71 @@ +/***************************************************************************** + + Int64.h + Copyright (c) 2003 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (stopwatch_Int64_HEADER_INCLUDED) +#define stopwatch_Int64_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +namespace stopwatch +{ + + +#if defined (_MSC_VER) + + typedef __int64 Int64; + +#elif defined (__MWERKS__) || defined (__GNUC__) + + typedef long long Int64; + +#elif defined (__BEOS__) + + typedef int64 Int64; + +#else + + #error No 64-bit integer type defined for this compiler ! + +#endif + + +} // namespace stopwatch + + + +#endif // stopwatch_Int64_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/stopwatch/StopWatch.cpp b/demos/spectrum/fftreal/stopwatch/StopWatch.cpp new file mode 100644 index 0000000..7795d86 --- /dev/null +++ b/demos/spectrum/fftreal/stopwatch/StopWatch.cpp @@ -0,0 +1,101 @@ +/***************************************************************************** + + StopWatch.cpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (_MSC_VER) + #pragma warning (1 : 4130) // "'operator' : logical operation on address of string constant" + #pragma warning (1 : 4223) // "nonstandard extension used : non-lvalue array converted to pointer" + #pragma warning (1 : 4705) // "statement has no effect" + #pragma warning (1 : 4706) // "assignment within conditional expression" + #pragma warning (4 : 4786) // "identifier was truncated to '255' characters in the debug information" + #pragma warning (4 : 4800) // "forcing value to bool 'true' or 'false' (performance warning)" + #pragma warning (4 : 4355) // "'this' : used in base member initializer list" +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "StopWatch.h" + +#include <cassert> + + + +namespace stopwatch +{ + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +StopWatch::StopWatch () +: _ccc () +, _nbr_laps (0) +{ + // Nothing +} + + + +double StopWatch::get_time_total (Int64 nbr_op) const +{ + assert (_nbr_laps > 0); + assert (nbr_op > 0); + + return ( + static_cast <double> (_ccc.get_time_total ()) + / (static_cast <double> (nbr_op) * static_cast <double> (_nbr_laps)) + ); +} + + + +double StopWatch::get_time_best_lap (Int64 nbr_op) const +{ + assert (nbr_op > 0); + + return ( + static_cast <double> (_ccc.get_time_best_lap ()) + / static_cast <double> (nbr_op) + ); +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +} // namespace stopwatch + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/stopwatch/StopWatch.h b/demos/spectrum/fftreal/stopwatch/StopWatch.h new file mode 100644 index 0000000..9cc47e5 --- /dev/null +++ b/demos/spectrum/fftreal/stopwatch/StopWatch.h @@ -0,0 +1,110 @@ +/***************************************************************************** + + StopWatch.h + Copyright (c) 2005 Laurent de Soras + +Utility class based on ClockCycleCounter to measure the unit time of a +repeated operation. + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (stopwatch_StopWatch_HEADER_INCLUDED) +#define stopwatch_StopWatch_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "ClockCycleCounter.h" + + + +namespace stopwatch +{ + + + +class StopWatch +{ + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +public: + + StopWatch (); + + stopwatch_FORCEINLINE void + start (); + stopwatch_FORCEINLINE void + stop_lap (); + + double get_time_total (Int64 nbr_op) const; + double get_time_best_lap (Int64 nbr_op) const; + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +protected: + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + ClockCycleCounter + _ccc; + Int64 _nbr_laps; + + + +/*\\\ FORBIDDEN MEMBER FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +private: + + StopWatch (const StopWatch &other); + StopWatch & operator = (const StopWatch &other); + bool operator == (const StopWatch &other); + bool operator != (const StopWatch &other); + +}; // class StopWatch + + + +} // namespace stopwatch + + + +#include "StopWatch.hpp" + + + +#endif // stopwatch_StopWatch_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/stopwatch/StopWatch.hpp b/demos/spectrum/fftreal/stopwatch/StopWatch.hpp new file mode 100644 index 0000000..74482a7 --- /dev/null +++ b/demos/spectrum/fftreal/stopwatch/StopWatch.hpp @@ -0,0 +1,83 @@ +/***************************************************************************** + + StopWatch.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (stopwatch_StopWatch_CURRENT_CODEHEADER) + #error Recursive inclusion of StopWatch code header. +#endif +#define stopwatch_StopWatch_CURRENT_CODEHEADER + +#if ! defined (stopwatch_StopWatch_CODEHEADER_INCLUDED) +#define stopwatch_StopWatch_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +namespace stopwatch +{ + + + +/*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +void StopWatch::start () +{ + _nbr_laps = 0; + _ccc.start (); +} + + + +void StopWatch::stop_lap () +{ + _ccc.stop_lap (); + ++ _nbr_laps; +} + + + +/*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +/*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +} // namespace stopwatch + + + +#endif // stopwatch_StopWatch_CODEHEADER_INCLUDED + +#undef stopwatch_StopWatch_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/stopwatch/def.h b/demos/spectrum/fftreal/stopwatch/def.h new file mode 100644 index 0000000..81ee6aa --- /dev/null +++ b/demos/spectrum/fftreal/stopwatch/def.h @@ -0,0 +1,65 @@ +/***************************************************************************** + + def.h + Copyright (c) 2003 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (stopwatch_def_HEADER_INCLUDED) +#define stopwatch_def_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +namespace stopwatch +{ + + + +#if defined (_MSC_VER) + + #define stopwatch_FORCEINLINE __forceinline + +#else + + #define stopwatch_FORCEINLINE inline + +#endif + + + +} // namespace stopwatch + + + +#endif // stopwatch_def_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/stopwatch/fnc.h b/demos/spectrum/fftreal/stopwatch/fnc.h new file mode 100644 index 0000000..0554535 --- /dev/null +++ b/demos/spectrum/fftreal/stopwatch/fnc.h @@ -0,0 +1,67 @@ +/***************************************************************************** + + fnc.h + Copyright (c) 2003 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (stopwatch_fnc_HEADER_INCLUDED) +#define stopwatch_fnc_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +namespace stopwatch +{ + + + +template <typename T> +inline T min (T a, T b); + +template <typename T> +inline T max (T a, T b); + +inline int round_int (double x); + + + +} // namespace rsp + + + +#include "fnc.hpp" + + + +#endif // stopwatch_fnc_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/stopwatch/fnc.hpp b/demos/spectrum/fftreal/stopwatch/fnc.hpp new file mode 100644 index 0000000..0ab5949 --- /dev/null +++ b/demos/spectrum/fftreal/stopwatch/fnc.hpp @@ -0,0 +1,85 @@ +/***************************************************************************** + + fnc.hpp + Copyright (c) 2003 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (stopwatch_fnc_CURRENT_CODEHEADER) + #error Recursive inclusion of fnc code header. +#endif +#define stopwatch_fnc_CURRENT_CODEHEADER + +#if ! defined (stopwatch_fnc_CODEHEADER_INCLUDED) +#define stopwatch_fnc_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include <cassert> +#include <cmath> + +namespace std {} + + + +namespace stopwatch +{ + + + +template <typename T> +inline T min (T a, T b) +{ + return ((a < b) ? a : b); +} + + + +template <typename T> +inline T max (T a, T b) +{ + return ((b < a) ? a : b); +} + + + +int round_int (double x) +{ + using namespace std; + + return (static_cast <int> (floor (x + 0.5))); +} + + + +} // namespace stopwatch + + + +#endif // stopwatch_fnc_CODEHEADER_INCLUDED + +#undef stopwatch_fnc_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/test.cpp b/demos/spectrum/fftreal/test.cpp new file mode 100644 index 0000000..7b6ed2c --- /dev/null +++ b/demos/spectrum/fftreal/test.cpp @@ -0,0 +1,267 @@ +/***************************************************************************** + + test.cpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (_MSC_VER) + #pragma warning (4 : 4786) // "identifier was truncated to '255' characters in the debug information" + #pragma warning (4 : 4800) // "forcing value to bool 'true' or 'false' (performance warning)" +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + +#include "test_settings.h" +#include "TestHelperFixLen.h" +#include "TestHelperNormal.h" + +#if defined (_MSC_VER) +#include <crtdbg.h> +#include <new.h> +#endif // _MSC_VER + +#include <new> + +#include <cassert> +#include <cstdio> + + + +#define TEST_ + + +/*\\\ FUNCTIONS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +static int TEST_perform_test_accuracy_all (); +static int TEST_perform_test_speed_all (); + +static void TEST_prog_init (); +static void TEST_prog_end (); + + + +int main (int argc, char *argv []) +{ + using namespace std; + + int ret_val = 0; + + TEST_prog_init (); + + try + { + if (ret_val == 0) + { + ret_val = TEST_perform_test_accuracy_all (); + } + + if (ret_val == 0) + { + ret_val = TEST_perform_test_speed_all (); + } + } + + catch (std::exception &e) + { + printf ("\n*** main(): Exception (std::exception) : %s\n", e.what ()); + ret_val = -1; + } + + catch (...) + { + printf ("\n*** main(): Undefined exception\n"); + ret_val = -1; + } + + TEST_prog_end (); + + return (ret_val); +} + + + +int TEST_perform_test_accuracy_all () +{ + int ret_val = 0; + + TestHelperNormal <float >::perform_test_accuracy (ret_val); + TestHelperNormal <double>::perform_test_accuracy (ret_val); + + TestHelperFixLen < 1>::perform_test_accuracy (ret_val); + TestHelperFixLen < 2>::perform_test_accuracy (ret_val); + TestHelperFixLen < 3>::perform_test_accuracy (ret_val); + TestHelperFixLen < 4>::perform_test_accuracy (ret_val); + TestHelperFixLen < 7>::perform_test_accuracy (ret_val); + TestHelperFixLen < 8>::perform_test_accuracy (ret_val); + TestHelperFixLen <10>::perform_test_accuracy (ret_val); + TestHelperFixLen <12>::perform_test_accuracy (ret_val); + TestHelperFixLen <13>::perform_test_accuracy (ret_val); + + return (ret_val); +} + + + +int TEST_perform_test_speed_all () +{ + int ret_val = 0; + +#if defined (test_settings_SPEED_TEST_ENABLED) + + TestHelperNormal <float >::perform_test_speed (ret_val); + TestHelperNormal <double>::perform_test_speed (ret_val); + + TestHelperFixLen < 1>::perform_test_speed (ret_val); + TestHelperFixLen < 2>::perform_test_speed (ret_val); + TestHelperFixLen < 3>::perform_test_speed (ret_val); + TestHelperFixLen < 4>::perform_test_speed (ret_val); + TestHelperFixLen < 7>::perform_test_speed (ret_val); + TestHelperFixLen < 8>::perform_test_speed (ret_val); + TestHelperFixLen <10>::perform_test_speed (ret_val); + TestHelperFixLen <12>::perform_test_speed (ret_val); + TestHelperFixLen <14>::perform_test_speed (ret_val); + TestHelperFixLen <16>::perform_test_speed (ret_val); + TestHelperFixLen <20>::perform_test_speed (ret_val); + +#endif + + return (ret_val); +} + + + +#if defined (_MSC_VER) +static int __cdecl TEST_new_handler_cb (size_t dummy) +{ + throw std::bad_alloc (); + return (0); +} +#endif // _MSC_VER + + + +#if defined (_MSC_VER) && ! defined (NDEBUG) +static int __cdecl TEST_debug_alloc_hook_cb (int alloc_type, void *user_data_ptr, size_t size, int block_type, long request_nbr, const unsigned char *filename_0, int line_nbr) +{ + if (block_type != _CRT_BLOCK) // Ignore CRT blocks to prevent infinite recursion + { + switch (alloc_type) + { + case _HOOK_ALLOC: + case _HOOK_REALLOC: + case _HOOK_FREE: + + // Put some debug code here + + break; + + default: + assert (false); // Undefined allocation type + break; + } + } + + return (1); +} +#endif + + + +#if defined (_MSC_VER) && ! defined (NDEBUG) +static int __cdecl TEST_debug_report_hook_cb (int report_type, char *user_msg_0, int *ret_val_ptr) +{ + *ret_val_ptr = 0; // 1 to override the CRT default reporting mode + + switch (report_type) + { + case _CRT_WARN: + case _CRT_ERROR: + case _CRT_ASSERT: + +// Put some debug code here + + break; + } + + return (*ret_val_ptr); +} +#endif + + + +static void TEST_prog_init () +{ +#if defined (_MSC_VER) + ::_set_new_handler (::TEST_new_handler_cb); +#endif // _MSC_VER + +#if defined (_MSC_VER) && ! defined (NDEBUG) + { + const int mode = (1 * _CRTDBG_MODE_DEBUG) + | (1 * _CRTDBG_MODE_WNDW); + ::_CrtSetReportMode (_CRT_WARN, mode); + ::_CrtSetReportMode (_CRT_ERROR, mode); + ::_CrtSetReportMode (_CRT_ASSERT, mode); + + const int old_flags = ::_CrtSetDbgFlag (_CRTDBG_REPORT_FLAG); + ::_CrtSetDbgFlag ( old_flags + | (1 * _CRTDBG_LEAK_CHECK_DF) + | (1 * _CRTDBG_CHECK_ALWAYS_DF)); + ::_CrtSetBreakAlloc (-1); // Specify here a memory bloc number + ::_CrtSetAllocHook (TEST_debug_alloc_hook_cb); + ::_CrtSetReportHook (TEST_debug_report_hook_cb); + + // Speed up I/O but breaks C stdio compatibility +// std::cout.sync_with_stdio (false); +// std::cin.sync_with_stdio (false); +// std::cerr.sync_with_stdio (false); +// std::clog.sync_with_stdio (false); + } +#endif // _MSC_VER, NDEBUG +} + + + +static void TEST_prog_end () +{ +#if defined (_MSC_VER) && ! defined (NDEBUG) + { + const int mode = (1 * _CRTDBG_MODE_DEBUG) + | (0 * _CRTDBG_MODE_WNDW); + ::_CrtSetReportMode (_CRT_WARN, mode); + ::_CrtSetReportMode (_CRT_ERROR, mode); + ::_CrtSetReportMode (_CRT_ASSERT, mode); + + ::_CrtMemState mem_state; + ::_CrtMemCheckpoint (&mem_state); + ::_CrtMemDumpStatistics (&mem_state); + } +#endif // _MSC_VER, NDEBUG +} + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/test_fnc.h b/demos/spectrum/fftreal/test_fnc.h new file mode 100644 index 0000000..2622156 --- /dev/null +++ b/demos/spectrum/fftreal/test_fnc.h @@ -0,0 +1,53 @@ +/***************************************************************************** + + test_fnc.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (test_fnc_HEADER_INCLUDED) +#define test_fnc_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class T> +inline T limit (const T &x, const T &inf, const T &sup); + + + +#include "test_fnc.hpp" + + + +#endif // test_fnc_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/test_fnc.hpp b/demos/spectrum/fftreal/test_fnc.hpp new file mode 100644 index 0000000..4b5f9f5 --- /dev/null +++ b/demos/spectrum/fftreal/test_fnc.hpp @@ -0,0 +1,56 @@ +/***************************************************************************** + + test_fnc.hpp + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if defined (test_fnc_CURRENT_CODEHEADER) + #error Recursive inclusion of test_fnc code header. +#endif +#define test_fnc_CURRENT_CODEHEADER + +#if ! defined (test_fnc_CODEHEADER_INCLUDED) +#define test_fnc_CODEHEADER_INCLUDED + + + +/*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ + + + +template <class T> +T limit (const T &x, const T &inf, const T &sup) +{ + assert (! (sup < inf)); + + return ((x < inf) ? inf : ((sup < x) ? sup : x)); +} + + + +#endif // test_fnc_CODEHEADER_INCLUDED + +#undef test_fnc_CURRENT_CODEHEADER + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/test_settings.h b/demos/spectrum/fftreal/test_settings.h new file mode 100644 index 0000000..b893afc --- /dev/null +++ b/demos/spectrum/fftreal/test_settings.h @@ -0,0 +1,45 @@ +/***************************************************************************** + + test_settings.h + Copyright (c) 2005 Laurent de Soras + +--- Legal stuff --- + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +*Tab=3***********************************************************************/ + + + +#if ! defined (test_settings_HEADER_INCLUDED) +#define test_settings_HEADER_INCLUDED + +#if defined (_MSC_VER) + #pragma once + #pragma warning (4 : 4250) // "Inherits via dominance." +#endif + + + +// #undef this label to avoid speed test compilation. +#define test_settings_SPEED_TEST_ENABLED + + + +#endif // test_settings_HEADER_INCLUDED + + + +/*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/ diff --git a/demos/spectrum/fftreal/testapp.dpr b/demos/spectrum/fftreal/testapp.dpr new file mode 100644 index 0000000..54f2eb9 --- /dev/null +++ b/demos/spectrum/fftreal/testapp.dpr @@ -0,0 +1,150 @@ +program testapp; +{$APPTYPE CONSOLE} +uses + SysUtils, + fftreal in 'fftreal.pas', + Math, + Windows; + +var + nbr_points : longint; + x, f : pflt_array; + fft : TFFTReal; + i : longint; + PI : double; + areal, img : double; + f_abs : double; + buffer_size : longint; + nbr_tests : longint; + time0, time1, time2 : int64; + timereso : int64; + offset : longint; + t0, t1 : double; + nbr_s_chn : longint; + tempp1, tempp2 : pflt_array; + +begin + (*______________________________________________ + * + * Exactness test + *______________________________________________ + *) + + WriteLn('Accuracy test:'); + WriteLn; + + nbr_points := 16; // Power of 2 + GetMem(x, nbr_points * sizeof_flt); + GetMem(f, nbr_points * sizeof_flt); + fft := TFFTReal.Create(nbr_points); // FFT object initialized here + + // Test signal + PI := ArcTan(1) * 4; + for i := 0 to nbr_points-1 do + begin + x^[i] := -1 + sin (3*2*PI*i/nbr_points) + + cos (5*2*PI*i/nbr_points) * 2 + - sin (7*2*PI*i/nbr_points) * 3 + + cos (8*2*PI*i/nbr_points) * 5; + end; + + // Compute FFT and IFFT + fft.do_fft(f, x); + fft.do_ifft(f, x); + fft.rescale(x); + + // Display the result + WriteLn('FFT:'); + for i := 0 to nbr_points div 2 do + begin + areal := f^[i]; + if (i > 0) and (i < nbr_points div 2) then + img := f^[i + nbr_points div 2] + else + img := 0; + + f_abs := Sqrt(areal * areal + img * img); + WriteLn(Format('%5d: %12.6f %12.6f (%12.6f)', [i, areal, img, f_abs])); + end; + + WriteLn; + WriteLn('IFFT:'); + for i := 0 to nbr_points-1 do + WriteLn(Format('%5d: %f', [i, x^[i]])); + + WriteLn; + + FreeMem(x); + FreeMem(f); + fft.Free; + + + (*______________________________________________ + * + * Speed test + *______________________________________________ + *) + + WriteLn('Speed test:'); + WriteLn('Please wait...'); + WriteLn; + + nbr_points := 1024; // Power of 2 + buffer_size := 256*nbr_points; // Number of flt_t (float or double) + nbr_tests := 10000; + + assert(nbr_points <= buffer_size); + GetMem(x, buffer_size * sizeof_flt); + GetMem(f, buffer_size * sizeof_flt); + fft := TFFTReal.Create(nbr_points); // FFT object initialized here + + // Test signal: noise + for i := 0 to nbr_points-1 do + x^[i] := Random($7fff) - ($7fff shr 1); + + // timing + QueryPerformanceFrequency(timereso); + QueryPerformanceCounter(time0); + + for i := 0 to nbr_tests-1 do + begin + offset := (i * nbr_points) and (buffer_size - 1); + tempp1 := f; + inc(tempp1, offset); + tempp2 := x; + inc(tempp2, offset); + fft.do_fft(tempp1, tempp2); + end; + + QueryPerformanceCounter(time1); + + for i := 0 to nbr_tests-1 do + begin + offset := (i * nbr_points) and (buffer_size - 1); + tempp1 := f; + inc(tempp1, offset); + tempp2 := x; + inc(tempp2, offset); + fft.do_ifft(tempp1, tempp2); + fft.rescale(x); + end; + + QueryPerformanceCounter(time2); + + t0 := ((time1-time0) / timereso) / nbr_tests; + t1 := ((time2-time1) / timereso) / nbr_tests; + + WriteLn(Format('%d-points FFT : %.0f us.', [nbr_points, t0 * 1000000])); + WriteLn(Format('%d-points IFFT + scaling: %.0f us.', [nbr_points, t1 * 1000000])); + + nbr_s_chn := Floor(nbr_points / ((t0 + t1) * 44100 * 2)); + WriteLn(Format('Peak performance: FFT+IFFT on %d mono channels at 44.1 KHz (with overlapping)', [nbr_s_chn])); + WriteLn; + + FreeMem(x); + FreeMem(f); + fft.Free; + + WriteLn('Press [Return] key to terminate...'); + ReadLn; +end. |