/*============================================================================

    fourierd.cpp  -  Don Cross <dcross@intersrv.com>

    http://www.intersrv.com/~dcross/fft.html

    Contains definitions for doing Fourier transforms
    and inverse Fourier transforms.

    This module performs operations on arrays of 'double'.

    Revision history:

1998 September 24 [Don Cross]
    Adding a bit-reversal cache so that when multiple FFT's of a 
    single buffer size are done, only one set of bit-reversal
    calculations needs to be made.

1998 September 23 [Don Cross]
    Making minor modifications as a code branch for use in
    the Sonic runtime library.  Compiling as C++ instead of C.

1998 September 19 [Don Cross]
    Updated coding standards.
    Improved efficiency of trig calculations.

============================================================================*/

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

#include <fourier.h>

const double DDC_PI = 4.0 * atan(1.0);

#define CHECKPOINTER(p)  CheckPointer(p,#p)

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


static unsigned *BitReverseTable = NULL;
static unsigned BitReverseSamples = 0;
static int      FailedAllocFlag = 0;


void fft_double (
    unsigned  NumSamples,
    int       InverseTransform,
    double   *RealIn,
    double   *ImagIn,
    double   *RealOut,
    double   *ImagOut )
{
    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 );

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

    if ( NumSamples == BitReverseSamples && BitReverseTable != NULL )
    {
        /*
        **   We can use-precalculated bit reversal table...
        */

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

        if ( BitReverseTable != NULL )
        {
            free ( BitReverseTable );
            BitReverseTable = NULL;
            BitReverseSamples = 0;
        }

        if ( !FailedAllocFlag )
        {
            BitReverseSamples = NumSamples;
            BitReverseTable = (unsigned *) malloc ( sizeof(unsigned) * NumSamples );
            if ( BitReverseTable == NULL )
            {
                FailedAllocFlag = 1;
                BitReverseSamples = 0;
            }
        }

        if ( BitReverseTable == NULL )
        {
            /* 
            **  Even if we can't allocate the bit-reverse table, the code can
            **  still perform its function, albeit more slowly.
            */
            for ( i=0; i < NumSamples; i++ )
            {
                j = ReverseBits ( i, NumBits );
                RealOut[j] = RealIn[i];
                ImagOut[j] = (ImagIn == NULL) ? 0.0 : ImagIn[i];
            }
        }
        else
        {
            for ( i=0; i < NumSamples; i++ )
            {
                j = BitReverseTable[i] = 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 neg_angle = -delta_angle;
        double sm1 = sin ( neg_angle );
        double cm1 = cos ( neg_angle );
        neg_angle *= 2.0;
        double sm2 = sin ( neg_angle );
        double cm2 = cos ( neg_angle );
        double w = 2 * cm1;
        double ar[3], ai[3];

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


/*--- end of file fourierd.cpp ---*/