ti/dsplib/examples/fft_ex/gen_twiddle_fft32x32.c

   1 /* ======================================================================= */
   2 /*      gen_twiddle_fft32x32.c -- File with twiddle factor generators.     */
   3 /* ======================================================================= */
   4 /*      This code requires a special sequence of twiddle factors stored    */
   5 /*      in 1Q15 fixed-point format.  The following C code is used for      */
   6 /*      the natural C and intrinsic C implementations.                     */
   7 /*                                                                         */
   8 /*      In order to vectorize the FFT, it is desirable to access twiddle   */
   9 /*      factor array using double word wide loads and fetch the twiddle    */
  10 /*      factors needed. In order to do this a modified twiddle factor      */
  11 /*      array is created, in which the factors WN/4, WN/2, W3N/4 are       */
  12 /*      arranged to be contiguous. This eliminates the seperation between  */
  13 /*      twiddle factors within a butterfly. However this implies that as   */
  14 /*      the loop is traversed from one stage to another, that we maintain  */
  15 /*      a redundant version of the twiddle factor array. Hence the size    */
  16 /*      of the twiddle factor array increases as compared to the normal    */
  17 /*      Cooley Tukey FFT.  The modified twiddle factor array is of size    */
  18 /*      "2 * N" where the conventional Cooley Tukey FFT is of size"3N/4"   */
  19 /*      where N is the number of complex points to be transformed. The     */
  20 /*      routine that generates the modified twiddle factor array was       */
  21 /*      presented earlier. With the above transformation of the FFT,       */
  22 /*      both the input data and the twiddle factor array can be accessed   */
  23 /*      using double-word wide loads to enable packed data processing.     */
  24 /*                                                                         */
  25 /*                                                                         */
  26 /* Copyright (C) 2011 Texas Instruments Incorporated - http://www.ti.com/  */
  27 /*                                                                         */
  28 /*                                                                         */
  29 /*  Redistribution and use in source and binary forms, with or without     */
  30 /*  modification, are permitted provided that the following conditions     */
  31 /*  are met:                                                               */
  32 /*                                                                         */
  33 /*    Redistributions of source code must retain the above copyright       */
  34 /*    notice, this list of conditions and the following disclaimer.        */
  35 /*                                                                         */
  36 /*    Redistributions in binary form must reproduce the above copyright    */
  37 /*    notice, this list of conditions and the following disclaimer in the  */
  38 /*    documentation and/or other materials provided with the               */
  39 /*    distribution.                                                        */
  40 /*                                                                         */
  41 /*    Neither the name of Texas Instruments Incorporated nor the names of  */
  42 /*    its contributors may be used to endorse or promote products derived  */
  43 /*    from this software without specific prior written permission.        */
  44 /*                                                                         */
  45 /*  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS    */
  46 /*  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT      */
  47 /*  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR  */
  48 /*  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT   */
  49 /*  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,  */
  50 /*  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT       */
  51 /*  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,  */
  52 /*  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY  */
  53 /*  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT    */
  54 /*  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE  */
  55 /*  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.   */
  56 /*                                                                         */
  57 /* ======================================================================= */
  58
  59 #include <math.h>
  60 #include "gen_twiddle_fft32x32.h"
  61
  62 #ifndef PI
  63 # ifdef M_PI
  64 #  define PI M_PI
  65 # else
  66 #  define PI 3.14159265358979323846
  67 # endif
  68 #endif
  69
  70
  71 /* ======================================================================== */
  72 /*  D2S -- Truncate a 'double' to a 'int',   with clamping.                 */
  73 /* ======================================================================== */
  74 static int d2i(double d)
  75 {
  76     if (d >=  2147483647.0) return (int)0x7FFFFFFF;
  77     if (d <= -2147483648.0) return (int)0x80000000;
  78     return (int)d;
  79 }
  80
  81
  82 /* ======================================================================== */
  83 /*  GEN_TWIDDLE -- Generate twiddle factors for TI's custom FFTs.           */
  84 /*                                                                          */
  85 /*  USAGE                                                                   */
  86 /*      This routine is called as follows:                                  */
  87 /*                                                                          */
  88 /*          int gen_twiddle_fft32x32(short *w, int n, double scale)         */
  89 /*                                                                          */
  90 /*          int    *w     Pointer to twiddle-factor array                   */
  91 /*          int    n      Size of FFT                                       */
  92 /*          double scale  Scale factor to apply to values.                  */
  93 /*                                                                          */
  94 /*      The routine will generate the twiddle-factors directly into the     */
  95 /*      array you specify.  The array needs to be approximately 2*N         */
  96 /*      elements long.  (The actual size, which is slightly smaller, is     */
  97 /*      returned by the function.)                                          */
  98 /* ======================================================================== */
  99 #ifdef _LITTLE_ENDIAN
 100 int gen_twiddle_fft32x32(int *w, int n, double scale)
 101 {
 102     int i, j, k, s=0, t;
 103
 104     for (j = 1, k = 0; j < n >> 2; j = j << 2, s++) {
 105         for (i = t=0; i < n >> 2; i += j, t++) {
 106             w[k +  5] = d2i(scale * cos(6.0 * PI * i / n));
 107             w[k +  4] = d2i(scale * sin(6.0 * PI * i / n));
 108
 109             w[k +  3] = d2i(scale * cos(4.0 * PI * i / n));
 110             w[k +  2] = d2i(scale * sin(4.0 * PI * i / n));
 111
 112             w[k +  1] = d2i(scale * cos(2.0 * PI * i / n));
 113             w[k +  0] = d2i(scale * sin(2.0 * PI * i / n));
 114
 115             k += 6;
 116         }
 117     }
 118     return k;
 119 }
 120 #else
 121 int gen_twiddle_fft32x32(int *w, int n, double scale)
 122 {
 123     int i, j, k, s=0, t;
 124
 125     for (j = 1, k = 0; j < n >> 2; j = j << 2, s++) {
 126         for (i = t=0; i < n >> 2; i += j, t++) {
 127             w[k +  5] =-d2i(scale * sin(6.0 * PI * i / n));
 128             w[k +  4] = d2i(scale * cos(6.0 * PI * i / n));
 129
 130             w[k +  3] =-d2i(scale * sin(4.0 * PI * i / n));
 131             w[k +  2] = d2i(scale * cos(4.0 * PI * i / n));
 132
 133             w[k +  1] =-d2i(scale * sin(2.0 * PI * i / n));
 134             w[k +  0] = d2i(scale * cos(2.0 * PI * i / n));
 135
 136             k += 6;
 137         }
 138     }
 139     return k;
 140 }
 141 #endif
 142 /* ======================================================================= */
 143 /*  End of file:  gen_twiddle_fft32x32.c                                   */
 144 /* ----------------------------------------------------------------------- */
 145 /*            Copyright (c) 2011 Texas Instruments, Incorporated.          */
 146 /*                           All Rights Reserved.                          */
 147 /* ======================================================================= */
 148