0001    // FFT.swift
0002    //
0003    // Copyright (c) 2014–2015 Mattt Thompson (http://mattt.me)//
0005    // Permission is hereby granted, free of charge, to any person obtaining a copy
0006    // of this software and associated documentation files (the "Software"), to deal
0007    // in the Software without restriction, including without limitation the rights
0008    // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
0009    // copies of the Software, and to permit persons to whom the Software is
0010    // furnished to do so, subject to the following conditions:
0011    //
0012    // The above copyright notice and this permission notice shall be included in
0013    // all copies or substantial portions of the Software.
0014    //
0015    // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
0016    // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
0017    // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
0018    // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
0019    // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
0020    // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
0021    // THE SOFTWARE.
0022    
0023    import Accelerate
0024    
0025    // MARK: Fast Fourier Transform
0026    
0027    public func fft(input: [Float]) -> [Float] {
0028        var real = [Float](input)
0029        var imaginary = [Float](count: input.count, repeatedValue: 0.0)
0030        var splitComplex = DSPSplitComplex(realp: &real, imagp: &imaginary)
0031    
0032        let length = vDSP_Length(floor(log2(Float(input.count))))
0033        let radix = FFTRadix(kFFTRadix2)
0034        let weights = vDSP_create_fftsetup(length, radix)
0035        vDSP_fft_zip(weights, &splitComplex, , length, FFTDirection(FFT_FORWARD))
0036    
0037        var magnitudes = [Float](count: input.count, repeatedValue: 0.0)
0038        vDSP_zvmags(&splitComplex, , &magnitudes, , vDSP_Length(input.count))
0039    
0040        var normalizedMagnitudes = [Float](count: input.count, repeatedValue: 0.0)
0041        vDSP_vsmul(sqrt(magnitudes), , [2.0 / Float(input.count)], &normalizedMagnitudes, , vDSP_Length(input.count))
0042    
0043        vDSP_destroy_fftsetup(weights)
0044    
0045        return normalizedMagnitudes
0046    }
0047    
0048    public func fft(input: [Double]) -> [Double] {
0049        var real = [Double](input)
0050        var imaginary = [Double](count: input.count, repeatedValue: 0.0)
0051        var splitComplex = DSPDoubleSplitComplex(realp: &real, imagp: &imaginary)
0052    
0053        let length = vDSP_Length(floor(log2(Float(input.count))))
0054        let radix = FFTRadix(kFFTRadix2)
0055        let weights = vDSP_create_fftsetupD(length, radix)
0056        vDSP_fft_zipD(weights, &splitComplex, , length, FFTDirection(FFT_FORWARD))
0057    
0058        var magnitudes = [Double](count: input.count, repeatedValue: 0.0)
0059        vDSP_zvmagsD(&splitComplex, , &magnitudes, , vDSP_Length(input.count))
0060    
0061        var normalizedMagnitudes = [Double](count: input.count, repeatedValue: 0.0)
0062        vDSP_vsmulD(sqrt(magnitudes), , [2.0 / Double(input.count)], &normalizedMagnitudes, , vDSP_Length(input.count))
0063    
0064        vDSP_destroy_fftsetupD(weights)
0065    
0066        return normalizedMagnitudes
0067    }
0068