ti/dsplib/src/DSP_fft16x16r/c64P/gen_twiddle_fft16x16.c

   1 /* ======================================================================= */
   2 /*      gen_twiddle_fft16x16.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_fft16x16.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 'short', with clamping.                 */
  73 /* ======================================================================== */
  74 static short d2s(double d)
  75 {
  76     d = floor(0.5 + d);  // Explicit rounding to integer //
  77     if (d >=  32767.0) return  32767;
  78     if (d <= -32768.0) return -32768;
  79     return (short)d;
  80 }
  81
  82
  83 /* ======================================================================== */
  84 /*  GEN_TWIDDLE -- Generate twiddle factors for TI's custom FFTs.           */
  85 /*                                                                          */
  86 /*  USAGE                                                                   */
  87 /*      This routine is called as follows:                                  */
  88 /*                                                                          */
  89 /*          int gen_twiddle_fft16x16(short *w, int n)                       */
  90 /*                                                                          */
  91 /*          short *w      Pointer to twiddle-factor array                   */
  92 /*          int   n       Size of FFT                                       */
  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_fft16x16(short *w, int n)
 101 {
 102     int i, j, k;
 103     double M = 32767.5;
 104
 105     for (j = 1, k = 0; j < n >> 2; j = j << 2) {
 106         for (i = 0; i < n >> 2; i += j << 1) {
 107             w[k + 11] =  d2s(M * cos(6.0 * PI * (i + j) / n));
 108             w[k + 10] =  d2s(M * sin(6.0 * PI * (i + j) / n));
 109             w[k +  9] =  d2s(M * cos(6.0 * PI * (i    ) / n));
 110             w[k +  8] =  d2s(M * sin(6.0 * PI * (i    ) / n));
 111
 112             w[k +  7] = -d2s(M * cos(4.0 * PI * (i + j) / n));
 113             w[k +  6] = -d2s(M * sin(4.0 * PI * (i + j) / n));
 114             w[k +  5] = -d2s(M * cos(4.0 * PI * (i    ) / n));
 115             w[k +  4] = -d2s(M * sin(4.0 * PI * (i    ) / n));
 116
 117             w[k +  3] =  d2s(M * cos(2.0 * PI * (i + j) / n));
 118             w[k +  2] =  d2s(M * sin(2.0 * PI * (i + j) / n));
 119             w[k +  1] =  d2s(M * cos(2.0 * PI * (i    ) / n));
 120             w[k +  0] =  d2s(M * sin(2.0 * PI * (i    ) / n));
 121
 122             k += 12;
 123         }
 124     }
 125     return k;
 126 }
 127
 128 #else
 129 int gen_twiddle_fft16x16(short *w, int n)
 130 {
 131     int i, j, k;
 132     double M = 32767.5;
 133
 134     for (j = 1, k = 0; j < n >> 2; j = j << 2) {
 135         for (i = 0; i < n >> 2; i += j << 1) {
 136             w[k + 11] = -d2s(M * sin(6.0 * PI * (i + j) / n));
 137             w[k + 10] =  d2s(M * cos(6.0 * PI * (i + j) / n));
 138             w[k +  9] = -d2s(M * sin(6.0 * PI * (i    ) / n));
 139             w[k +  8] =  d2s(M * cos(6.0 * PI * (i    ) / n));
 140
 141             w[k +  7] =  d2s(M * sin(4.0 * PI * (i + j) / n));
 142             w[k +  6] = -d2s(M * cos(4.0 * PI * (i + j) / n));
 143             w[k +  5] =  d2s(M * sin(4.0 * PI * (i    ) / n));
 144             w[k +  4] = -d2s(M * cos(4.0 * PI * (i    ) / n));
 145
 146             w[k +  3] = -d2s(M * sin(2.0 * PI * (i + j) / n));
 147             w[k +  2] =  d2s(M * cos(2.0 * PI * (i + j) / n));
 148             w[k +  1] = -d2s(M * sin(2.0 * PI * (i    ) / n));
 149             w[k +  0] =  d2s(M * cos(2.0 * PI * (i    ) / n));
 150
 151             k += 12;
 152         }
 153     }
 154     return k;
 155 }
 156
 157 #endif
 158 /* ======================================================================= */
 159 /*  End of file:  gen_twiddle_fft16x16.c                                   */
 160 /* ----------------------------------------------------------------------- */
 161 /*            Copyright (c) 2011 Texas Instruments, Incorporated.          */
 162 /*                           All Rights Reserved.                          */
 163 /* ======================================================================= */
 164