mediaproviders/thirdparty/fft.cpp

0001 /*
0002  * Copyright (c) 2016 Daniel Holanda Noronha. All rights reserved.
0003  *
0004  * This work is licensed under the terms of the MIT license.
0005  * For a copy, see <https://opensource.org/licenses/MIT>.
0006  *
0007  */
0008
0009 #include "fft.h"
0010
0011 void fft(CArray& x){
0012     const size_t N = x.size();
0013     if (N <= 1) return;
0014
0015     CArray even = x[std::slice(0, N/2, 2)];
0016     CArray  odd = x[std::slice(1, N/2, 2)];
0017
0018     fft(even);
0019     fft(odd);
0020
0021     for (size_t k = 0; k < N/2; ++k)
0022     {
0023         Complex t = std::polar(1.0, -2 * PI * k / N) * odd[k];
0024         x[k    ] = even[k] + t;
0025         x[k+N/2] = even[k] - t;
0026     }
0027 }
0028
0029 void ifft(CArray& x){
0030     x = x.apply(std::conj);
0031     fft( x );
0032     x = x.apply(std::conj);
0033     x /= x.size();
0034 }