TI-radar AWR1843 C674x DSP core  1
gen_twiddle_fft16x16.c
Go to the documentation of this file.
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 /* 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_fft16x16.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_fft16x16(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_fft16x16(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 += j << 1) {
106  w[k + 11] = d2s(M * cos(6.0 * PI * (i + j) / n));
107  w[k + 10] = d2s(M * sin(6.0 * PI * (i + j) / n));
108  w[k + 9] = d2s(M * cos(6.0 * PI * (i ) / n));
109  w[k + 8] = d2s(M * sin(6.0 * PI * (i ) / n));
110 
111  w[k + 7] = -d2s(M * cos(4.0 * PI * (i + j) / n));
112  w[k + 6] = -d2s(M * sin(4.0 * PI * (i + j) / n));
113  w[k + 5] = -d2s(M * cos(4.0 * PI * (i ) / n));
114  w[k + 4] = -d2s(M * sin(4.0 * PI * (i ) / n));
115 
116  w[k + 3] = d2s(M * cos(2.0 * PI * (i + j) / n));
117  w[k + 2] = d2s(M * sin(2.0 * PI * (i + j) / n));
118  w[k + 1] = d2s(M * cos(2.0 * PI * (i ) / n));
119  w[k + 0] = d2s(M * sin(2.0 * PI * (i ) / n));
120 
121  k += 12;
122  }
123  }
124  return k;
125 }
126 
127 #else
128 int gen_twiddle_fft16x16(short *w, int n)
129 {
130  int i, j, k;
131  double M = 32767.5;
132 
133  for (j = 1, k = 0; j < n >> 2; j = j << 2) {
134  for (i = 0; i < n >> 2; i += j << 1) {
135  w[k + 11] = -d2s(M * sin(6.0 * PI * (i + j) / n));
136  w[k + 10] = d2s(M * cos(6.0 * PI * (i + j) / n));
137  w[k + 9] = -d2s(M * sin(6.0 * PI * (i ) / n));
138  w[k + 8] = d2s(M * cos(6.0 * PI * (i ) / n));
139 
140  w[k + 7] = d2s(M * sin(4.0 * PI * (i + j) / n));
141  w[k + 6] = -d2s(M * cos(4.0 * PI * (i + j) / n));
142  w[k + 5] = d2s(M * sin(4.0 * PI * (i ) / n));
143  w[k + 4] = -d2s(M * cos(4.0 * PI * (i ) / n));
144 
145  w[k + 3] = -d2s(M * sin(2.0 * PI * (i + j) / n));
146  w[k + 2] = d2s(M * cos(2.0 * PI * (i + j) / n));
147  w[k + 1] = -d2s(M * sin(2.0 * PI * (i ) / n));
148  w[k + 0] = d2s(M * cos(2.0 * PI * (i ) / n));
149 
150  k += 12;
151  }
152  }
153  return k;
154 }
155 #endif
156 
157 /* ======================================================================= */
158 /* End of file: gen_twiddle_fft16x16.c */
159 /* ----------------------------------------------------------------------- */
160 /* Copyright (c) 2011 Texas Instruments, Incorporated. */
161 /* All Rights Reserved. */
162 /* ======================================================================= */
163 
d2s
static short d2s(double d)
Definition: gen_twiddle_fft16x16.c:73
gen_twiddle_fft16x16
int gen_twiddle_fft16x16(short *w, int n)
Definition: gen_twiddle_fft16x16.c:128
PI
#define PI
Definition: gen_twiddle_fft16x16.c:65