/* rfft - Fast Fourier Transform
** R. Winters, original edits, 03/03/02
**
** rfft computes the Fourier transform (or rffti the inverse transform)
** of the complex inputs to produce the complex outputs.
** See Chapter 12 of "Numerical Recipes in FORTRAN" by
** Press, Teukolsky, Vetterling, and Flannery,
** Cambridge University Press.
**
** Command Line Program Usage: rfft infile <return>
** The program produces an output file named infile.out in CSV format.
** infile sample data must be in the format:
** realFloat0, imgFloat0,
** realFloat1, imgFloat1,
** ...
** realFloatN, imgFloatN,
**
** The number of samples must be a power of two to do the
** recursive decomposition of the FFT algorithm.
**
** To compile: g++ rfft.cpp -o rfft
*/

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define TRUE  1
#define FALSE 0
#define MAXSAMPLES (8192)
#define DDC_PI (3.14159265358979323846)
#define CHECKPOINTER(p) CheckPointer(p,#p)
//#define BITS_PER_WORD (sizeof(unsigned) * 8)

/* Function Prototypes */
void fft_float (
    unsigned  NumSamples,          /* must be a power of 2 */
    int       InverseTransform,    /* 0=forward FFT, 1=inverse FFT */
    float    *RealIn,              /* array of input's real samples */
    float    *ImaginaryIn,         /* array of input's imag samples */
    float    *RealOut,             /* array of output's reals */
    float    *ImaginaryOut );      /* array of output's imaginaries */

/*
**   The following function returns an "abstract frequency" of a
**   given index into a buffer with a given number of frequency samples.
**   Multiply return value by sampling rate to get frequency expressed in Hz.
*/
double Index_to_frequency ( unsigned NumSamples, unsigned Index );

int IsPowerOfTwo ( unsigned x );
unsigned NumberOfBitsNeeded ( unsigned PowerOfTwo );
unsigned ReverseBits ( unsigned index, unsigned NumBits );
static void CheckPointer ( void *p, char *name );

/* Sample Data Arrays */
float fftin_r[MAXSAMPLES], fftin_i[MAXSAMPLES];
float fftout_r[MAXSAMPLES], fftout_i[MAXSAMPLES];

static void CheckPointer ( void *p, char *name )
{
    if ( p == NULL )
    {
        fprintf ( stderr, "Error in fft_float():  %s == NULL\n", name );
        exit(1);
    }
}

void fft_float (
    unsigned  NumSamples,
    int       InverseTransform,
    float    *RealIn,
    float    *ImagIn,
    float    *RealOut,
    float    *ImagOut )
{
    unsigned NumBits;    /* Number of bits needed to store indices */
    unsigned i, j, k, n;
    unsigned BlockSize, BlockEnd;

    double angle_numerator = 2.0 * DDC_PI;
    double tr, ti;     /* temp real, temp imaginary */

    if ( !IsPowerOfTwo(NumSamples) )
    {
        fprintf (
            stderr,
            "Error in fft():  NumSamples=%u is not power of two\n",
            NumSamples );

        exit(1);
    }

    if ( InverseTransform )
        angle_numerator = -angle_numerator;

    CHECKPOINTER ( RealIn );
    CHECKPOINTER ( RealOut );
    CHECKPOINTER ( ImagOut );

    NumBits = NumberOfBitsNeeded ( NumSamples );

    /*
    **   Do simultaneous data copy and bit-reversal ordering into outputs...
    */

    for ( i=0; i < NumSamples; i++ )
    {
        j = ReverseBits ( i, NumBits );
        RealOut[j] = RealIn[i];
        ImagOut[j] = (ImagIn == NULL) ? 0.0 : ImagIn[i];
    }

    /*
    **   Do the FFT itself...
    */

    BlockEnd = 1;
    for ( BlockSize = 2; BlockSize <= NumSamples; BlockSize <<= 1 )
    {
        double delta_angle = angle_numerator / (double)BlockSize;
        double sm2 = sin ( -2 * delta_angle );
        double sm1 = sin ( -delta_angle );
        double cm2 = cos ( -2 * delta_angle );
        double cm1 = cos ( -delta_angle );
        double w = 2 * cm1;
        double ar[3], ai[3];
        double temp;

        for ( i=0; i < NumSamples; i += BlockSize )
        {
            ar[2] = cm2;
            ar[1] = cm1;

            ai[2] = sm2;
            ai[1] = sm1;

            for ( j=i, n=0; n < BlockEnd; j++, n++ )
            {
                ar[0] = w*ar[1] - ar[2];
                ar[2] = ar[1];
                ar[1] = ar[0];

                ai[0] = w*ai[1] - ai[2];
                ai[2] = ai[1];
                ai[1] = ai[0];

                k = j + BlockEnd;
                tr = ar[0]*RealOut[k] - ai[0]*ImagOut[k];
                ti = ar[0]*ImagOut[k] + ai[0]*RealOut[k];

                RealOut[k] = RealOut[j] - tr;
                ImagOut[k] = ImagOut[j] - ti;

                RealOut[j] += tr;
                ImagOut[j] += ti;
            }
        }

        BlockEnd = BlockSize;
    }

    /*
    **   Need to normalize if inverse transform...
    */

    if ( InverseTransform )
    {
        double denom = (double)NumSamples;

        for ( i=0; i < NumSamples; i++ )
        {
            RealOut[i] /= denom;
            ImagOut[i] /= denom;
        }
    }
}


int IsPowerOfTwo ( unsigned x )
{
    if ( x < 2 )
        return FALSE;

    if ( x & (x-1) )        // Thanks to 'byang' for this cute trick!
        return FALSE;

    return TRUE;
}


unsigned NumberOfBitsNeeded ( unsigned PowerOfTwo )
{
    unsigned i;

    if ( PowerOfTwo < 2 )
    {
        fprintf (
            stderr,
            ">>> Error in fftmisc.c: argument %d to NumberOfBitsNeeded is too small.\n",
            PowerOfTwo );

        exit(1);
    }

    for ( i=0; ; i++ )
    {
        if ( PowerOfTwo & (1 << i) )
            return i;
    }
}



unsigned ReverseBits ( unsigned index, unsigned NumBits )
{
    unsigned i, rev;

    for ( i=rev=0; i < NumBits; i++ )
    {
        rev = (rev << 1) | (index & 1);
        index >>= 1;
    }

    return rev;
}


double Index_to_frequency ( unsigned NumSamples, unsigned Index )
{
    if ( Index >= NumSamples )
        return 0.0;
    else if ( Index <= NumSamples/2 )
        return (double)Index / (double)NumSamples;

    return -(double)(NumSamples-Index) / (double)NumSamples;
}


int main (int argc, char *argv[])
{
int i=0, samples=0;
FILE *fpin, *fpout;
char fin[32], fout[36];

   sprintf(fin, "%s", argv[1]);
   sprintf(fout, "%s.out", fin);

   if ((fpin = fopen(fin, "rt"))  == NULL)
   {
      fprintf(stderr, "Cannot open input file.\n");
      return 1;
   }

   if ((fpout = fopen(fout, "wt")) == NULL)
   {
      fprintf(stderr, "Cannot open output file.\n");
      return 1;
   }

while (fscanf(fpin,"%f,%f,\n",&fftin_r[samples],&fftin_i[samples]) != EOF && i < MAXSAMPLES) {
  //  printf ("sample=%d,real=%f,img=%f\n", samples, fftin_r[samples], fftin_i[samples]);
  samples++;
  }

fft_float(samples,0,fftin_r,fftin_i,fftout_r,fftout_i);

for (i=0;i<samples;i++) {
  fprintf (fpout, "%d, %f, %f, %f\n", i, fftout_r[i], fftout_i[i], sqrt(pow(fftout_r[i],2)+pow(fftout_i[i],2)));
  printf ("%d, %f, %f, %f\n", i, fftout_r[i], fftout_i[i], sqrt(pow(fftout_r[i],2)+pow(fftout_i[i],2)));
  }

  fclose(fpin);
  fclose(fpout);
return 0;
}

/*--- end of file rfft.c ---*/