1 /*
2   ==============================================================================
3 
4    This file is part of the JUCE library.
5    Copyright (c) 2017 - ROLI Ltd.
6 
7    JUCE is an open source library subject to commercial or open-source
8    licensing.
9 
10    By using JUCE, you agree to the terms of both the JUCE 5 End-User License
11    Agreement and JUCE 5 Privacy Policy (both updated and effective as of the
12    27th April 2017).
13 
14    End User License Agreement: www.juce.com/juce-5-licence
15    Privacy Policy: www.juce.com/juce-5-privacy-policy
16 
17    Or: You may also use this code under the terms of the GPL v3 (see
18    www.gnu.org/licenses).
19 
20    JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
21    EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
22    DISCLAIMED.
23 
24   ==============================================================================
25 */
26 
27 namespace juce
28 {
29 namespace dsp
30 {
31 
32 struct FFTUnitTest  : public UnitTest
33 {
FFTUnitTestjuce::dsp::FFTUnitTest34     FFTUnitTest()
35         : UnitTest ("FFT", UnitTestCategories::dsp)
36     {}
37 
fillRandomjuce::dsp::FFTUnitTest38     static void fillRandom (Random& random, Complex<float>* buffer, size_t n)
39     {
40         for (size_t i = 0; i < n; ++i)
41             buffer[i] = Complex<float> ((2.0f * random.nextFloat()) - 1.0f,
42                                              (2.0f * random.nextFloat()) - 1.0f);
43     }
44 
fillRandomjuce::dsp::FFTUnitTest45     static void fillRandom (Random& random, float* buffer, size_t n)
46     {
47         for (size_t i = 0; i < n; ++i)
48             buffer[i] = (2.0f * random.nextFloat()) - 1.0f;
49     }
50 
freqConvolutionjuce::dsp::FFTUnitTest51     static Complex<float> freqConvolution (const Complex<float>* in, float freq, size_t n)
52     {
53         Complex<float> sum (0.0, 0.0);
54         for (size_t i = 0; i < n; ++i)
55             sum += in[i] * exp (Complex<float> (0, static_cast<float> (i) * freq));
56 
57         return sum;
58     }
59 
performReferenceFourierjuce::dsp::FFTUnitTest60     static void performReferenceFourier (const Complex<float>* in, Complex<float>* out,
61                                          size_t n, bool reverse)
62     {
63         auto base_freq = static_cast<float> (((reverse ? 1.0 : -1.0) * MathConstants<double>::twoPi)
64                                                / static_cast<float> (n));
65 
66         for (size_t i = 0; i < n; ++i)
67             out[i] = freqConvolution (in, static_cast<float>(i) * base_freq, n);
68     }
69 
performReferenceFourierjuce::dsp::FFTUnitTest70     static void performReferenceFourier (const float* in, Complex<float>* out,
71                                          size_t n, bool reverse)
72     {
73         HeapBlock<Complex<float>> buffer (n);
74 
75         for (size_t i = 0; i < n; ++i)
76             buffer.getData()[i] = Complex<float> (in[i], 0.0f);
77 
78         float base_freq = static_cast<float> (((reverse ? 1.0 : -1.0) * MathConstants<double>::twoPi)
79                                                 / static_cast<float> (n));
80 
81         for (size_t i = 0; i < n; ++i)
82             out[i] = freqConvolution (buffer.getData(), static_cast<float>(i) * base_freq, n);
83     }
84 
85 
86     //==============================================================================
87     template <typename Type>
checkArrayIsSimilarjuce::dsp::FFTUnitTest88     static bool checkArrayIsSimilar (Type* a, Type* b, size_t n) noexcept
89     {
90         for (size_t i = 0; i < n; ++i)
91             if (std::abs (a[i] - b[i]) > 1e-3f)
92                 return false;
93 
94         return true;
95     }
96 
97     struct RealTest
98     {
runjuce::dsp::FFTUnitTest::RealTest99         static void run (FFTUnitTest& u)
100         {
101             Random random (378272);
102 
103             for (size_t order = 0; order <= 8; ++order)
104             {
105                 auto n = (1u << order);
106 
107                 FFT fft ((int) order);
108 
109                 HeapBlock<float> input (n);
110                 HeapBlock<Complex<float>> reference (n), output (n);
111 
112                 fillRandom (random, input.getData(), n);
113                 performReferenceFourier (input.getData(), reference.getData(), n, false);
114 
115                 // fill only first half with real numbers
116                 zeromem (output.getData(), n * sizeof (Complex<float>));
117                 memcpy (reinterpret_cast<float*> (output.getData()), input.getData(), n * sizeof (float));
118 
119                 fft.performRealOnlyForwardTransform ((float*) output.getData());
120                 u.expect (checkArrayIsSimilar (reference.getData(), output.getData(), n));
121 
122                 // fill only first half with real numbers
123                 zeromem (output.getData(), n * sizeof (Complex<float>));
124                 memcpy (reinterpret_cast<float*> (output.getData()), input.getData(), n * sizeof (float));
125 
126                 fft.performRealOnlyForwardTransform ((float*) output.getData(), true);
127                 std::fill (reference.getData() + ((n >> 1) + 1), reference.getData() + n, std::complex<float> (0.0f));
128                 u.expect (checkArrayIsSimilar (reference.getData(), output.getData(), (n >> 1) + 1));
129 
130                 memcpy (output.getData(), reference.getData(), n * sizeof (Complex<float>));
131                 fft.performRealOnlyInverseTransform ((float*) output.getData());
132                 u.expect (checkArrayIsSimilar ((float*) output.getData(), input.getData(), n));
133             }
134         }
135     };
136 
137     struct FrequencyOnlyTest
138     {
runjuce::dsp::FFTUnitTest::FrequencyOnlyTest139         static void run(FFTUnitTest& u)
140         {
141             Random random (378272);
142             for (size_t order = 0; order <= 8; ++order)
143             {
144                 auto n = (1u << order);
145 
146                 FFT fft ((int) order);
147 
148                 HeapBlock<float> inout (n << 1), reference (n << 1);
149                 HeapBlock<Complex<float>> frequency (n);
150 
151                 fillRandom (random, inout.getData(), n);
152                 zeromem (reference.getData(), sizeof (float) * (n << 1));
153                 performReferenceFourier (inout.getData(), frequency.getData(), n, false);
154 
155                 for (size_t i = 0; i < n; ++i)
156                     reference.getData()[i] = std::abs (frequency.getData()[i]);
157 
158                 fft.performFrequencyOnlyForwardTransform (inout.getData());
159 
160                 u.expect (checkArrayIsSimilar (inout.getData(), reference.getData(), n));
161             }
162         }
163     };
164 
165     struct ComplexTest
166     {
runjuce::dsp::FFTUnitTest::ComplexTest167         static void run(FFTUnitTest& u)
168         {
169             Random random (378272);
170 
171             for (size_t order = 0; order <= 7; ++order)
172             {
173                 auto n = (1u << order);
174 
175                 FFT fft ((int) order);
176 
177                 HeapBlock<Complex<float>> input (n), buffer (n), output (n), reference (n);
178 
179                 fillRandom (random, input.getData(), n);
180                 performReferenceFourier (input.getData(), reference.getData(), n, false);
181 
182                 memcpy (buffer.getData(), input.getData(), sizeof (Complex<float>) * n);
183                 fft.perform (buffer.getData(), output.getData(), false);
184 
185                 u.expect (checkArrayIsSimilar (output.getData(), reference.getData(), n));
186 
187                 memcpy (buffer.getData(), reference.getData(), sizeof (Complex<float>) * n);
188                 fft.perform (buffer.getData(), output.getData(), true);
189 
190 
191                 u.expect (checkArrayIsSimilar (output.getData(), input.getData(), n));
192             }
193         }
194     };
195 
196     template <class TheTest>
runTestForAllTypesjuce::dsp::FFTUnitTest197     void runTestForAllTypes (const char* unitTestName)
198     {
199         beginTest (unitTestName);
200 
201         TheTest::run (*this);
202     }
203 
runTestjuce::dsp::FFTUnitTest204     void runTest() override
205     {
206         runTestForAllTypes<RealTest> ("Real input numbers Test");
207         runTestForAllTypes<FrequencyOnlyTest> ("Frequency only Test");
208         runTestForAllTypes<ComplexTest> ("Complex input numbers Test");
209     }
210 };
211 
212 static FFTUnitTest fftUnitTest;
213 
214 } // namespace dsp
215 } // namespace juce
216