/* ======================================================================== */
/*  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 <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#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;
}
