TI-radar AWR1843 C674x DSP core  1
gen_twiddle_fft32x32.c
Go to the documentation of this file.
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 /* 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_fft32x32.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 'int', with clamping. */
72 /* ======================================================================== */
73 static int d2i(double d)
74 {
75  if (d >= 2147483647.0) return (int)0x7FFFFFFF;
76  if (d <= -2147483648.0) return (int)0x80000000;
77  return (int)d;
78 }
79 
80 
81 /* ======================================================================== */
82 /* GEN_TWIDDLE -- Generate twiddle factors for TI's custom FFTs. */
83 /* */
84 /* USAGE */
85 /* This routine is called as follows: */
86 /* */
87 /* int gen_twiddle_fft32x32(short *w, int n, double scale) */
88 /* */
89 /* int *w Pointer to twiddle-factor array */
90 /* int n Size of FFT */
91 /* double scale Scale factor to apply to values. */
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 int gen_twiddle_fft32x32(int *w, int n, double scale)
99 {
100  int i, j, k, s=0, t;
101 
102  for (j = 1, k = 0; j < n >> 2; j = j << 2, s++) {
103  for (i = t=0; i < n >> 2; i += j, t++) {
104  w[k + 5] = d2i(scale * cos(6.0 * PI * i / n));
105  w[k + 4] = d2i(scale * sin(6.0 * PI * i / n));
106 
107  w[k + 3] = d2i(scale * cos(4.0 * PI * i / n));
108  w[k + 2] = d2i(scale * sin(4.0 * PI * i / n));
109 
110  w[k + 1] = d2i(scale * cos(2.0 * PI * i / n));
111  w[k + 0] = d2i(scale * sin(2.0 * PI * i / n));
112 
113  k += 6;
114  }
115  }
116  return k;
117 }
118 
119 /* ======================================================================= */
120 /* End of file: gen_twiddle_fft32x32.c */
121 /* ----------------------------------------------------------------------- */
122 /* Copyright (c) 2011 Texas Instruments, Incorporated. */
123 /* All Rights Reserved. */
124 /* ======================================================================= */
125 
gen_twiddle_fft32x32
int gen_twiddle_fft32x32(int *w, int n, double scale)
Definition: gen_twiddle_fft32x32.c:98
PI
#define PI
Definition: gen_twiddle_fft32x32.c:65
d2i
static int d2i(double d)
Definition: gen_twiddle_fft32x32.c:73