• Rostislav Pehlivanov's avatar
    imdct15: replace the FFT with a faster PFA FFT algorithm · 2d208aaa
    Rostislav Pehlivanov authored
    This commit replaces the current inefficient non-power-of-two FFT with a
    much faster FFT based on the Prime Factor Algorithm.
    Although it is already much faster than the old algorithm without SIMD,
    the new algorithm makes use of the already very throughouly SIMD'd power
    of two FFT, which improves performance even more across all platforms
    which we have SIMD support for.
    
    Most of the work was done by Peter Barfuss, who passed the code to me to
    implement into the iMDCT and the current codebase. The code for a
    5-point and 15-point FFT was derived from the previous implementation,
    although it was optimized and simplified, which will make its future
    SIMD easier. The 15-point FFT is currently using 6% of the current
    overall decoder overhead.
    
    The FFT can now easily be used as a forward transform by simply not
    multiplying the 5-point FFT's imaginary component by -1 (which comes
    from the fact that changing the complex exponential's angle by -1 also
    changes the output by that) and by multiplying the "theta" angle of the
    main exptab by -1. Hence the deliberately left multiplication by -1 at
    the end.
    
    FATE passes, and performance reports on other platforms/CPUs are
    welcome.
    
    Performance comparisons:
    
    iMDCT, PFA:
    101127 decicycles in speed,   32765 runs,      3 skips
    iMDCT, Old:
    211022 decicycles in speed,   32768 runs,      0 skips
    
    Standalone FFT, 300000 transforms of size 960:
        PFA        Old FFT     kiss_fft    libfftw3f
        3.659695s, 15.726912s, 13.300789s, 1.182222s
    
    Being only 3x slower than libfftw3f is a big achievement by itself.
    
    There appears to be something capping the performance in the iMDCT side
    of things, possibly during the pre-stage reindexing. However, it is
    certainly fast enough for now.
    Signed-off-by: 's avatarRostislav Pehlivanov <atomnuker@gmail.com>
    2d208aaa
imdct15.h 1.54 KB