/* ======================================================================= */ /* gen_twiddle_fft32x32.c -- File with twiddle factor generators. */ /* ======================================================================= */ /* This code requires a special sequence of twiddle factors stored */ /* in 1Q15 fixed-point format. The following C code is used for */ /* the natural C and intrinsic C implementations. */ /* */ /* In order to vectorize the FFT, it is desirable to access twiddle */ /* factor array using double word wide loads and fetch the twiddle */ /* factors needed. In order to do this a modified twiddle factor */ /* array is created, in which the factors WN/4, WN/2, W3N/4 are */ /* arranged to be contiguous. This eliminates the seperation between */ /* twiddle factors within a butterfly. However this implies that as */ /* the loop is traversed from one stage to another, that we maintain */ /* a redundant version of the twiddle factor array. Hence the size */ /* of the twiddle factor array increases as compared to the normal */ /* Cooley Tukey FFT. The modified twiddle factor array is of size */ /* "2 * N" where the conventional Cooley Tukey FFT is of size"3N/4" */ /* where N is the number of complex points to be transformed. The */ /* routine that generates the modified twiddle factor array was */ /* presented earlier. With the above transformation of the FFT, */ /* both the input data and the twiddle factor array can be accessed */ /* using double-word wide loads to enable packed data processing. */ /* */ /* */ /* Copyright (C) 2011 Texas Instruments Incorporated - http://www.ti.com/ */ /* */ /* */ /* Redistribution and use in source and binary forms, with or without */ /* modification, are permitted provided that the following conditions */ /* are met: */ /* */ /* Redistributions of source code must retain the above copyright */ /* notice, this list of conditions and the following disclaimer. */ /* */ /* Redistributions in binary form must reproduce the above copyright */ /* notice, this list of conditions and the following disclaimer in the */ /* documentation and/or other materials provided with the */ /* distribution. */ /* */ /* Neither the name of Texas Instruments Incorporated nor the names of */ /* its contributors may be used to endorse or promote products derived */ /* from this software without specific prior written permission. */ /* */ /* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS */ /* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT */ /* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR */ /* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT */ /* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, */ /* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT */ /* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, */ /* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY */ /* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT */ /* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE */ /* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /* */ /* ======================================================================= */ #include #include "gen_twiddle_fft32x32.h" #ifndef PI # ifdef M_PI # define PI M_PI # else # define PI 3.14159265358979323846 # endif #endif /* ======================================================================== */ /* D2S -- Truncate a 'double' to a 'int', with clamping. */ /* ======================================================================== */ static int d2i(double d) { if (d >= 2147483647.0) return (int)0x7FFFFFFF; if (d <= -2147483648.0) return (int)0x80000000; return (int)d; } /* ======================================================================== */ /* GEN_TWIDDLE -- Generate twiddle factors for TI's custom FFTs. */ /* */ /* USAGE */ /* This routine is called as follows: */ /* */ /* int gen_twiddle_fft32x32(short *w, int n, double scale) */ /* */ /* int *w Pointer to twiddle-factor array */ /* int n Size of FFT */ /* double scale Scale factor to apply to values. */ /* */ /* The routine will generate the twiddle-factors directly into the */ /* array you specify. The array needs to be approximately 2*N */ /* elements long. (The actual size, which is slightly smaller, is */ /* returned by the function.) */ /* ======================================================================== */ #ifdef _LITTLE_ENDIAN int gen_twiddle_fft32x32(int *w, int n, double scale) { int i, j, k, s=0, t; for (j = 1, k = 0; j < n >> 2; j = j << 2, s++) { for (i = t=0; i < n >> 2; i += j, t++) { w[k + 5] = d2i(scale * cos(6.0 * PI * i / n)); w[k + 4] = d2i(scale * sin(6.0 * PI * i / n)); w[k + 3] = d2i(scale * cos(4.0 * PI * i / n)); w[k + 2] = d2i(scale * sin(4.0 * PI * i / n)); w[k + 1] = d2i(scale * cos(2.0 * PI * i / n)); w[k + 0] = d2i(scale * sin(2.0 * PI * i / n)); k += 6; } } return k; } #else int gen_twiddle_fft32x32(int *w, int n, double scale) { int i, j, k, s=0, t; for (j = 1, k = 0; j < n >> 2; j = j << 2, s++) { for (i = t=0; i < n >> 2; i += j, t++) { w[k + 5] =-d2i(scale * sin(6.0 * PI * i / n)); w[k + 4] = d2i(scale * cos(6.0 * PI * i / n)); w[k + 3] =-d2i(scale * sin(4.0 * PI * i / n)); w[k + 2] = d2i(scale * cos(4.0 * PI * i / n)); w[k + 1] =-d2i(scale * sin(2.0 * PI * i / n)); w[k + 0] = d2i(scale * cos(2.0 * PI * i / n)); k += 6; } } return k; } #endif /* ======================================================================= */ /* End of file: gen_twiddle_fft32x32.c */ /* ----------------------------------------------------------------------- */ /* Copyright (c) 2011 Texas Instruments, Incorporated. */ /* All Rights Reserved. */ /* ======================================================================= */