/* ======================================================================== */ /* TEXAS INSTRUMENTS, INC. */ /* */ /* NAME */ /* tw_r2fft */ /* */ /* USAGE */ /* This is a stand-alone program intended to generate twiddle-factor */ /* arrays for the DSPF_sp_cfftr2_dit FFT library routine. It is called*/ /* as follows: */ /* */ /* tw_r2fft N > outputfile.c */ /* */ /* The argument 'N' specifies the size of the FFT. This value */ /* must be a power of 2. */ /* */ /* This program will generate the twiddle factor array 'w', */ /* bit-reverse and output the result to the display. Redirect the */ /* output to a file as shown above. */ /* */ /* DESCRIPTION */ /* This program contains the twiddle-factor generation routine */ /* that is described within the source code for the DSPLIB */ /* FFT function DSPF_sp_cfftr2_dit. It does not produce appropriate */ /* twiddle-factor arrays for the other FFT implementations. */ /* */ /* Please consult the specific FFT that you are using for details. */ /* */ /* The final twiddle-factor array generated by the routine will */ /* be 2 * N elements long. */ /* */ /* NOTES */ /* The code below may be adapted to run directly on the target, */ /* rather than running as a separate program running off-line. */ /* Such adaptation is not recommended for time-critical applications. */ /* To adapt this program, remove the 'usage' and 'main' functions, */ /* and call 'gen_twiddle' directly. */ /* */ /* ------------------------------------------------------------------------ */ /* Copyright (c) 2003 Texas Instruments, Incorporated. */ /* All Rights Reserved. */ /* ======================================================================== */ #include #include #include #include #include #ifndef PI # ifdef M_PI # define PI M_PI # else # define PI 3.14159265358979323846 # endif #endif /* ======================================================================== */ /* */ /* TEXAS INSTRUMENTS, INC. */ /* */ /* NAME */ /* bit_rev */ /* */ /* USAGE */ /* This function has the prototype: */ /* */ /* void bit_rev(float *x, int n); */ /* */ /* x : Array to be bit-reversed. */ /* n : Number of complex array elements to bit-reverse. */ /* */ /* DESCRIPTION */ /* This routine bit reverses the floating point array x which */ /* is considered to be an array of complex numbers with the even */ /* numbered elements being thr real parts of the complex numbers */ /* while the odd numbered elements being the imaginary parts of the */ /* complex numbers. This function is made use of in sp_icfftr2_dif */ /* to bit-reverse the twiddle factor array generated using */ /* tw_genr2fft.c. */ /* ======================================================================== */ void bit_rev(float* x, int n) { int i, j, k; float rtemp, itemp; j = 0; for(i=1; i < (n-1); i++) { k = n >> 1; while(k <= j) { j -= k; k >>= 1; } j += k; if(i < j) { rtemp = x[j*2]; x[j*2] = x[i*2]; x[i*2] = rtemp; itemp = x[j*2+1]; x[j*2+1] = x[i*2+1]; x[i*2+1] = itemp; } } } /* ======================================================================== */ /* GEN_TWIDDLE -- Generate twiddle factors for TI's custom FFTs. */ /* */ /* USAGE */ /* This routine is called as follows: */ /* */ /* int tw_r2fft (float *w, int n) */ /* */ /* float *w Pointer to twiddle-factor array */ /* int n Size of FFT */ /* */ /* The routine will generate the twiddle-factors directly into the */ /* array you specify. The array needs to be N elements long. */ /* ======================================================================== */ int gen_twiddle(float *w, int n) { double delta = 2 * PI / n; int i; for(i = 0; i < n/2; i++) { w[2 * i + 1] = sin(i * delta); w[2 * i] = cos(i * delta); } return n; } /* ======================================================================== */ /* USAGE -- Print usage information and optionally an error message. */ /* ======================================================================== */ void usage(char *error) { fprintf(stderr, " \n" "USAGE \n" " This is a stand-alone program intended to generate twiddle-factor \n" " arrays for the DSP_radix2 library routine. It is called as follows:\n" " \n" " tw_r2fft N > outputfile.c \n" " \n" " The argument 'N' specifies the size of the FFT. This value \n" " must be a power of 2. \n" " \n" " This program will generate the twiddle factor array 'w' and \n" " output the result to the display. Redirect the output to \n" " a file as shown above. \n" " \n"); if (error) fprintf(stderr, "ERROR: %s\n", error); exit(1); } /* ======================================================================== */ /* MAIN -- Where the action happens. */ /* ======================================================================== */ int main(int argc, char *argv[]) { int i, n = -1, size, is_pow_2; float *w; char *s; char buf[80]; /* -------------------------------------------------------------------- */ /* Parse the arguments. */ /* -------------------------------------------------------------------- */ if (argc < 2) { usage(NULL); } while (argc-->1) { if (!isdigit(argv[1][0]) || sscanf(argv[1], "%d", &n) != 1) { sprintf(buf, "Unrecognized argument: %-.32s\n", argv[1][0]); usage(buf); } if (n < 8 || n > 16384) usage("FFT size must be between 8 and 16384 points."); for (i = 2; i < 24; i++) if ((1 << i) == n) break; is_pow_2 = !(i & 1); if (i >= 24) { usage("FFT size must be a power of 2\n"); exit(1); } } if (n == -1) usage("Must specify FFT size."); /* -------------------------------------------------------------------- */ /* Allocate memory for the FFT twiddle factors. */ /* -------------------------------------------------------------------- */ w = calloc(2 * sizeof(float), n); if (!w) { fprintf(stderr, "ERROR: Unable to allocate memory for " "twiddle factors\n"); exit(1); } /* -------------------------------------------------------------------- */ /* Generate the twiddle-factor array. */ /* -------------------------------------------------------------------- */ size = gen_twiddle(w, n); bit_rev(w, n>>1); /* -------------------------------------------------------------------- */ /* Print out the resulting twiddle factors. */ /* -------------------------------------------------------------------- */ printf( "/* -------------------------------------------------------------------- */\n" "/* Automatically generated twiddle-factor array. */\n" "/* Number of points: %-5d */\n" "/* Appropriate FFTs: DSPF_sp_cfftr2_dit, DSPF_sp_icfftr2_dif */\n" "/* Required alignment: 8 byte (word) */\n" "/* -------------------------------------------------------------------- */\n" "/* NOTE: It is suggested that this array be aligned in a different */\n" "/* starting bank than the actual FFT data, to reduce bank conflicts. */\n" "/* This can be achieved by using the DATA_MEM_BANK pragma. Please */\n" "/* see the TMS320C6000 Optimizing C Compiler Reference (SPRU187E) */\n" "/* for details on \"#pragma DATA_MEM_BANK\". */\n" "/* -------------------------------------------------------------------- */\n" "\n" "#pragma DATA_ALIGN(w, 8); /* Remove this if using DATA_MEM_BANK */\n" "\n", n); printf("const float w[2 * %d] =\n{", size / 2); for (i = 0; i < size; i++) { printf("%s%c%f", i == 0 ? "\n " : (i & 7) == 0 ? ",\n " : ", ", w[i] < 0 ? '-' : ' ', fabs(w[i])); } printf("\n};\n"); return 0; }