ti/dsplib/examples/fft_ex/gen_twiddle_fft16x32.c

   1 /* ======================================================================= */
   2 /*      gen_twiddle_fft16x32.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 /* Copyright (C) 2011 Texas Instruments Incorporated - http://www.ti.com/  */
  26 /*                                                                         */
  27 /*                                                                         */
  28 /*  Redistribution and use in source and binary forms, with or without     */
  29 /*  modification, are permitted provided that the following conditions     */
  30 /*  are met:                                                               */
  31 /*                                                                         */
  32 /*    Redistributions of source code must retain the above copyright       */
  33 /*    notice, this list of conditions and the following disclaimer.        */
  34 /*                                                                         */
  35 /*    Redistributions in binary form must reproduce the above copyright    */
  36 /*    notice, this list of conditions and the following disclaimer in the  */
  37 /*    documentation and/or other materials provided with the               */
  38 /*    distribution.                                                        */
  39 /*                                                                         */
  40 /*    Neither the name of Texas Instruments Incorporated nor the names of  */
  41 /*    its contributors may be used to endorse or promote products derived  */
  42 /*    from this software without specific prior written permission.        */
  43 /*                                                                         */
  44 /*  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS    */
  45 /*  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT      */
  46 /*  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR  */
  47 /*  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT   */
  48 /*  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,  */
  49 /*  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT       */
  50 /*  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,  */
  51 /*  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY  */
  52 /*  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT    */
  53 /*  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE  */
  54 /*  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.   */
  55 /*                                                                         */
  56 /* ======================================================================= */
  57
  58 #include <math.h>
  59 #include "gen_twiddle_fft16x32.h"
  60
  61 #ifndef PI
  62 # ifdef M_PI
  63 #  define PI M_PI
  64 # else
  65 #  define PI 3.14159265358979323846
  66 # endif
  67 #endif
  68
  69
  70 /* ======================================================================== */
  71 /*  D2S -- Truncate a 'double' to a 'short', with clamping.                 */
  72 /* ======================================================================== */
  73 static short d2s(double d)
  74 {
  75     d = floor(0.5 + d);  // Explicit rounding to integer //
  76     if (d >=  32767.0) return  32767;
  77     if (d <= -32768.0) return -32768;
  78     return (short)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_fft16x32(short *w, int n)                       */
  89 /*                                                                          */
  90 /*          short *w      Pointer to twiddle-factor array                   */
  91 /*          int   n       Size of FFT                                       */
  92 /*                                                                          */
  93 /*      The routine will generate the twiddle-factors directly into the     */
  94 /*      array you specify.  The array needs to be approximately 2*N         */
  95 /*      elements long.  (The actual size, which is slightly smaller, is     */
  96 /*      returned by the function.)                                          */
  97 /* ======================================================================== */
  98 #ifdef _LITTLE_ENDIAN
  99 int gen_twiddle_fft16x32(short *w, int n)
 100 {
 101     int i, j, k;
 102     double M = 32767.5;
 103
 104     for (j = 1, k = 0; j < n >> 2; j = j << 2) {
 105         for (i = 0; i < n >> 2; i += 2*j) {
 106
 107             w[k +  3] = d2s(M * cos(2.0 * PI * (i+j) / n));
 108             w[k +  2] = d2s(M * sin(2.0 * PI * (i+j) / n));
 109
 110             w[k +  1] = d2s(M * cos(2.0 * PI * i / n));
 111             w[k +  0] = d2s(M * sin(2.0 * PI * i / n));
 112
 113             k += 4;
 114         }
 115     }
 116     return k;
 117 }
 118 #else
 119 int gen_twiddle_fft16x32(short *w, int n)
 120 {
 121     int i, j, k;
 122     double M = 32767.5;
 123
 124     for (j = 1, k = 0; j < n >> 2; j = j << 2) {
 125         for (i = 0; i < n >> 2; i += 2*j) {
 126
 127             w[k +  3] =-d2s(M * sin(2.0 * PI * (i+j) / n));
 128             w[k +  2] = d2s(M * cos(2.0 * PI * (i+j) / n));
 129
 130             w[k +  1] =-d2s(M * sin(2.0 * PI * i / n));
 131             w[k +  0] = d2s(M * cos(2.0 * PI * i / n));
 132
 133             k += 4;
 134         }
 135     }
 136     return k;
 137 }
 138 #endif
 139 /* ======================================================================= */
 140 /*  End of file:  gen_twiddle_fft16x32.c                                   */
 141 /* ----------------------------------------------------------------------- */
 142 /*            Copyright (c) 2011 Texas Instruments, Incorporated.          */
 143 /*                           All Rights Reserved.                          */
 144 /* ======================================================================= */
 145