1 /* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package org.drrickorang.loopback; 18 19 20 /** 21 * This class computes FFT of inputting data. 22 * Note: this part of code is originally from another project, so there's actually multiple copies 23 * of this code. Should somehow merge these copies in the future. Also, no modification on 24 * naming has been made, but naming should be changed once we merge all copies. 25 */ 26 27 public class FFT { 28 private int m; 29 private double[] cos; // precomputed cosine tables for FFT 30 private double[] sin; // precomputed sine tables for FFT 31 private final int mFFTSamplingSize; 32 33 34 FFT(int FFTSamplingSize) { 35 mFFTSamplingSize = FFTSamplingSize; 36 37 // set up variables needed for computing FFT 38 m = (int) (Math.log(mFFTSamplingSize) / Math.log(2)); 39 40 // Make sure n is a power of 2 41 if (mFFTSamplingSize != (1 << m)) 42 throw new RuntimeException("FFT sampling size must be power of 2"); 43 44 // precomputed tables 45 cos = new double[mFFTSamplingSize / 2]; 46 sin = new double[mFFTSamplingSize / 2]; 47 48 for (int i = 0; i < mFFTSamplingSize / 2; i++) { 49 cos[i] = Math.cos(-2 * Math.PI * i / mFFTSamplingSize); 50 sin[i] = Math.sin(-2 * Math.PI * i / mFFTSamplingSize); 51 } 52 } 53 54 55 /** 56 * Do FFT, and store the result's real part to "x", imaginary part to "y". 57 */ 58 public void fft(double[] x, double[] y, int sign) { 59 int i, j, k, n1, n2, a; 60 double c, s, t1, t2; 61 62 // Bit-reverse 63 j = 0; 64 n2 = mFFTSamplingSize / 2; 65 for (i = 1; i < mFFTSamplingSize - 1; i++) { 66 n1 = n2; 67 while (j >= n1) { 68 j = j - n1; 69 n1 = n1 / 2; 70 } 71 j = j + n1; 72 73 if (i < j) { 74 t1 = x[i]; 75 x[i] = x[j]; 76 x[j] = t1; 77 t1 = y[i]; 78 y[i] = y[j]; 79 y[j] = t1; 80 } 81 } 82 83 // FFT 84 n1 = 0; 85 n2 = 1; 86 87 for (i = 0; i < m; i++) { 88 n1 = n2; 89 n2 = n2 + n2; 90 a = 0; 91 92 for (j = 0; j < n1; j++) { 93 c = cos[a]; 94 s = sign * sin[a]; 95 a += 1 << (m - i - 1); 96 97 for (k = j; k < mFFTSamplingSize; k = k + n2) { 98 t1 = c * x[k + n1] - s * y[k + n1]; 99 t2 = s * x[k + n1] + c * y[k + n1]; 100 x[k + n1] = x[k] - t1; 101 y[k + n1] = y[k] - t2; 102 x[k] = x[k] + t1; 103 y[k] = y[k] + t2; 104 } 105 } 106 } 107 } 108 109 } 110
