1 // Unit tests for FFTPassEffect.
7 #include <gtest/gtest.h>
9 #include "effect_chain.h"
10 #include "fft_pass_effect.h"
11 #include "image_format.h"
12 #include "multiply_effect.h"
13 #include "test_util.h"
19 // Generate a random number uniformly distributed between [-1.0, 1.0].
20 float uniform_random()
22 return 2.0 * ((float)rand() / RAND_MAX - 0.5);
25 void setup_fft(EffectChain *chain, int fft_size, bool inverse,
26 bool add_normalizer = false,
27 FFTPassEffect::Direction direction = FFTPassEffect::HORIZONTAL)
29 assert((fft_size & (fft_size - 1)) == 0); // Must be power of two.
30 for (int i = 1, subsize = 2; subsize <= fft_size; ++i, subsize *= 2) {
31 Effect *fft_effect = chain->add_effect(new FFTPassEffect());
32 bool ok = fft_effect->set_int("fft_size", fft_size);
33 ok |= fft_effect->set_int("pass_number", i);
34 ok |= fft_effect->set_int("inverse", inverse);
35 ok |= fft_effect->set_int("direction", direction);
40 float factor[4] = { 1.0f / fft_size, 1.0f / fft_size, 1.0f / fft_size, 1.0f / fft_size };
41 Effect *multiply_effect = chain->add_effect(new MultiplyEffect());
42 bool ok = multiply_effect->set_vec4("factor", factor);
47 void run_fft(const float *in, float *out, int fft_size, bool inverse,
48 bool add_normalizer = false,
49 FFTPassEffect::Direction direction = FFTPassEffect::HORIZONTAL)
52 if (direction == FFTPassEffect::HORIZONTAL) {
59 EffectChainTester tester(in, width, height, FORMAT_RGBA_PREMULTIPLIED_ALPHA, COLORSPACE_sRGB, GAMMA_LINEAR);
60 setup_fft(tester.get_chain(), fft_size, inverse, add_normalizer, direction);
61 tester.run(out, GL_RGBA, COLORSPACE_sRGB, GAMMA_LINEAR, OUTPUT_ALPHA_FORMAT_PREMULTIPLIED);
66 TEST(FFTPassEffectTest, ZeroStaysZero) {
67 const int fft_size = 64;
68 float data[fft_size * 4] = { 0 };
69 float out_data[fft_size * 4];
71 run_fft(data, out_data, fft_size, false);
72 expect_equal(data, out_data, 4, fft_size);
74 run_fft(data, out_data, fft_size, true);
75 expect_equal(data, out_data, 4, fft_size);
78 TEST(FFTPassEffectTest, Impulse) {
79 const int fft_size = 64;
80 float data[fft_size * 4] = { 0 };
81 float expected_data[fft_size * 4], out_data[fft_size * 4];
87 for (int i = 0; i < fft_size; ++i) {
88 expected_data[i * 4 + 0] = data[0];
89 expected_data[i * 4 + 1] = data[1];
90 expected_data[i * 4 + 2] = data[2];
91 expected_data[i * 4 + 3] = data[3];
94 run_fft(data, out_data, fft_size, false);
95 expect_equal(expected_data, out_data, 4, fft_size);
97 run_fft(data, out_data, fft_size, true);
98 expect_equal(expected_data, out_data, 4, fft_size);
101 TEST(FFTPassEffectTest, SingleFrequency) {
102 const int fft_size = 16;
103 float data[fft_size * 4] = { 0 };
104 float expected_data[fft_size * 4], out_data[fft_size * 4];
105 for (int i = 0; i < fft_size; ++i) {
106 data[i * 4 + 0] = sin(2.0 * M_PI * (4.0 * i) / fft_size);
107 data[i * 4 + 1] = 0.0;
108 data[i * 4 + 2] = 0.0;
109 data[i * 4 + 3] = 0.0;
111 for (int i = 0; i < fft_size; ++i) {
112 expected_data[i * 4 + 0] = 0.0;
113 expected_data[i * 4 + 1] = 0.0;
114 expected_data[i * 4 + 2] = 0.0;
115 expected_data[i * 4 + 3] = 0.0;
117 expected_data[4 * 4 + 1] = -8.0;
118 expected_data[12 * 4 + 1] = 8.0;
120 run_fft(data, out_data, fft_size, false, false, FFTPassEffect::HORIZONTAL);
121 expect_equal(expected_data, out_data, 4, fft_size);
123 run_fft(data, out_data, fft_size, false, false, FFTPassEffect::VERTICAL);
124 expect_equal(expected_data, out_data, 4, fft_size);
127 TEST(FFTPassEffectTest, Repeat) {
129 for (int fft_size = 2; fft_size <= 128; fft_size *= 2) {
130 const int num_repeats = 31; // Prime, to make things more challenging.
131 float data[num_repeats * fft_size * 4];
132 float expected_data[num_repeats * fft_size * 4], out_data[num_repeats * fft_size * 4];
134 for (int i = 0; i < num_repeats * fft_size * 4; ++i) {
135 data[i] = uniform_random();
138 for (int i = 0; i < num_repeats; ++i) {
139 run_fft(data + i * fft_size * 4, expected_data + i * fft_size * 4, fft_size, false);
144 EffectChainTester tester(data, num_repeats * fft_size, 1, FORMAT_RGBA_PREMULTIPLIED_ALPHA, COLORSPACE_sRGB, GAMMA_LINEAR);
145 setup_fft(tester.get_chain(), fft_size, false);
146 tester.run(out_data, GL_RGBA, COLORSPACE_sRGB, GAMMA_LINEAR, OUTPUT_ALPHA_FORMAT_PREMULTIPLIED);
148 expect_equal(expected_data, out_data, 4, num_repeats * fft_size);
152 EffectChainTester tester(data, 1, num_repeats * fft_size, FORMAT_RGBA_PREMULTIPLIED_ALPHA, COLORSPACE_sRGB, GAMMA_LINEAR);
153 setup_fft(tester.get_chain(), fft_size, false, false, FFTPassEffect::VERTICAL);
154 tester.run(out_data, GL_RGBA, COLORSPACE_sRGB, GAMMA_LINEAR, OUTPUT_ALPHA_FORMAT_PREMULTIPLIED);
156 expect_equal(expected_data, out_data, 4, num_repeats * fft_size);
161 TEST(FFTPassEffectTest, TwoDimensional) { // Implicitly tests vertical.
163 const int fft_size = 16;
164 float in[fft_size * fft_size * 4], out[fft_size * fft_size * 4], expected_out[fft_size * fft_size * 4];
165 for (int y = 0; y < fft_size; ++y) {
166 for (int x = 0; x < fft_size; ++x) {
167 in[(y * fft_size + x) * 4 + 0] =
168 sin(2.0 * M_PI * (2 * x + 3 * y) / fft_size);
169 in[(y * fft_size + x) * 4 + 1] = 0.0;
170 in[(y * fft_size + x) * 4 + 2] = 0.0;
171 in[(y * fft_size + x) * 4 + 3] = 0.0;
174 memset(expected_out, 0, sizeof(expected_out));
176 // This result has been verified using the fft2() function in Octave,
178 expected_out[(3 * fft_size + 2) * 4 + 1] = -128.0;
179 expected_out[(13 * fft_size + 14) * 4 + 1] = 128.0;
181 EffectChainTester tester(in, fft_size, fft_size, FORMAT_RGBA_PREMULTIPLIED_ALPHA, COLORSPACE_sRGB, GAMMA_LINEAR);
182 setup_fft(tester.get_chain(), fft_size, false, false, FFTPassEffect::HORIZONTAL);
183 setup_fft(tester.get_chain(), fft_size, false, false, FFTPassEffect::VERTICAL);
184 tester.run(out, GL_RGBA, COLORSPACE_sRGB, GAMMA_LINEAR, OUTPUT_ALPHA_FORMAT_PREMULTIPLIED);
186 expect_equal(expected_out, out, 4 * fft_size, fft_size, 0.25, 0.0005);
189 // The classic paper for FFT correctness testing is Funda Ergün:
190 // “Testing Multivariate Linear Functions: Overcoming the Generator Bottleneck”
191 // (http://www.cs.sfu.ca/~funda/PUBLICATIONS/stoc95.ps), which proves that
192 // testing three basic properties of FFTs guarantees that the function is
193 // correct (at least under the assumption that errors are random).
195 // We don't follow the paper directly, though, for a few reasons: First,
196 // Ergün's paper really considers _self-correcting_ systems, which may
197 // be stochastically faulty, and thus uses various relatively complicated
198 // bounds and tests we don't really need. Second, the FFTs it considers
199 // are all about polynomials over finite fields, which means that results
200 // are exact and thus easy to test; we work with floats (half-floats!),
201 // and thus need some error tolerance.
203 // So instead, we follow the implementation of FFTW, which is really the
204 // gold standard when it comes to FFTs these days. They hard-code 20
205 // testing rounds as opposed to the more complicated bounds in the paper,
206 // and have a simpler version of the third test.
208 // The error bounds are set somewhat empirically, but remember that these
209 // inputs will give frequency values as large as ~16, where 0.025 is
210 // within the 9th bit (of 11 total mantissa bits in fp16).
211 const int ergun_rounds = 20;
213 // Test 1: Test that FFT(a + b) = FFT(a) + FFT(b).
214 TEST(FFTPassEffectTest, ErgunLinearityTest) {
216 const int max_fft_size = 64;
217 float a[max_fft_size * 4], b[max_fft_size * 4], sum[max_fft_size * 4];
218 float a_out[max_fft_size * 4], b_out[max_fft_size * 4], sum_out[max_fft_size * 4], expected_sum_out[max_fft_size * 4];
219 for (int fft_size = 2; fft_size <= max_fft_size; fft_size *= 2) {
220 for (int inverse = 0; inverse <= 1; ++inverse) {
221 for (int i = 0; i < ergun_rounds; ++i) {
222 for (int j = 0; j < fft_size * 4; ++j) {
223 a[j] = uniform_random();
224 b[j] = uniform_random();
226 run_fft(a, a_out, fft_size, inverse);
227 run_fft(b, b_out, fft_size, inverse);
229 for (int j = 0; j < fft_size * 4; ++j) {
230 sum[j] = a[j] + b[j];
231 expected_sum_out[j] = a_out[j] + b_out[j];
234 run_fft(sum, sum_out, fft_size, inverse);
235 expect_equal(expected_sum_out, sum_out, 4, fft_size, 0.03, 0.0005);
241 // Test 2: Test that FFT(delta(i)) = 1 (where delta(i) = [1 0 0 0 ...]),
242 // or more specifically, test that FFT(a + delta(i)) - FFT(a) = 1.
243 TEST(FFTPassEffectTest, ErgunImpulseTransform) {
245 const int max_fft_size = 64;
246 float a[max_fft_size * 4], b[max_fft_size * 4];
247 float a_out[max_fft_size * 4], b_out[max_fft_size * 4], sum_out[max_fft_size * 4], expected_sum_out[max_fft_size * 4];
248 for (int fft_size = 2; fft_size <= max_fft_size; fft_size *= 2) {
249 for (int inverse = 0; inverse <= 1; ++inverse) {
250 for (int i = 0; i < ergun_rounds; ++i) {
251 for (int j = 0; j < fft_size * 4; ++j) {
252 a[j] = uniform_random();
254 // Compute delta(j) - a.
261 run_fft(a, a_out, fft_size, inverse);
262 run_fft(b, b_out, fft_size, inverse);
264 for (int j = 0; j < fft_size * 4; ++j) {
265 sum_out[j] = a_out[j] + b_out[j];
266 expected_sum_out[j] = 1.0;
268 expect_equal(expected_sum_out, sum_out, 4, fft_size, 0.025, 0.0005);
274 // Test 3: Test the time-shift property of the FFT, in that a circular left-shift
275 // multiplies the result by e^(j 2pi k/N) (linear phase adjustment).
276 // As fftw_test.c says, “The paper performs more tests, but this code should be
278 TEST(FFTPassEffectTest, ErgunShiftProperty) {
280 const int max_fft_size = 64;
281 float a[max_fft_size * 4], b[max_fft_size * 4];
282 float a_out[max_fft_size * 4], b_out[max_fft_size * 4], expected_a_out[max_fft_size * 4];
283 for (int fft_size = 2; fft_size <= max_fft_size; fft_size *= 2) {
284 for (int inverse = 0; inverse <= 1; ++inverse) {
285 for (int direction = 0; direction <= 1; ++direction) {
286 for (int i = 0; i < ergun_rounds; ++i) {
287 for (int j = 0; j < fft_size * 4; ++j) {
288 a[j] = uniform_random();
291 // Circular shift left by one step.
292 for (int j = 0; j < fft_size * 4; ++j) {
293 b[j] = a[(j + 4) % (fft_size * 4)];
295 run_fft(a, a_out, fft_size, inverse, false, FFTPassEffect::Direction(direction));
296 run_fft(b, b_out, fft_size, inverse, false, FFTPassEffect::Direction(direction));
298 for (int j = 0; j < fft_size; ++j) {
299 double s = -sin(j * 2.0 * M_PI / fft_size);
300 double c = cos(j * 2.0 * M_PI / fft_size);
305 expected_a_out[j * 4 + 0] = b_out[j * 4 + 0] * c - b_out[j * 4 + 1] * s;
306 expected_a_out[j * 4 + 1] = b_out[j * 4 + 0] * s + b_out[j * 4 + 1] * c;
308 expected_a_out[j * 4 + 2] = b_out[j * 4 + 2] * c - b_out[j * 4 + 3] * s;
309 expected_a_out[j * 4 + 3] = b_out[j * 4 + 2] * s + b_out[j * 4 + 3] * c;
311 expect_equal(expected_a_out, a_out, 4, fft_size, 0.025, 0.0005);
318 TEST(FFTPassEffectTest, BigFFTAccuracy) {
320 const int max_fft_size = 2048;
321 float in[max_fft_size * 4], out[max_fft_size * 4], out2[max_fft_size * 4];
322 for (int fft_size = 2; fft_size <= max_fft_size; fft_size *= 2) {
323 for (int j = 0; j < fft_size * 4; ++j) {
324 in[j] = uniform_random();
326 run_fft(in, out, fft_size, false, true); // Forward, with normalization.
327 run_fft(out, out2, fft_size, true); // Reverse.
329 // These error bounds come from
330 // http://en.wikipedia.org/wiki/Fast_Fourier_transform#Accuracy_and_approximations,
331 // with empirically estimated epsilons. Note that the calculated
332 // rms in expect_equal() is divided by sqrt(N), so we compensate
334 double max_error = 0.0009 * log2(fft_size);
335 double rms_limit = 0.0007 * sqrt(log2(fft_size)) / sqrt(fft_size);
336 expect_equal(in, out2, 4, fft_size, max_error, rms_limit);