Function cfft

KeyboardVisualizerCommon/chuck_fft.c:212–258

----------------------------------------------------------------------------- name: cfft() desc: complex value fft these routines from CARL software, spect.c check out the CARL CMusic distribution for more software cfft replaces float array x containing NC complex values (2*NC float values alternating real, imagininary, etc.) by its Fourier transform if forward is true, or by its inverse Fourier

//
//-----------------------------------------------------------------------------
void cfft(float * x, long NC, unsigned int forward)
{
    float wr, wi, wpr, wpi, theta, scale;
    long mmax, ND, m, i, j, delta;
    ND = NC << 1;
    bit_reverse(x, ND);

    for (mmax = 2; mmax < ND; mmax = delta)
    {
        delta = mmax << 1;
        theta = TWOPI / (forward ? mmax : -mmax);
        wpr = (float)(-2.*pow(sin(0.5*theta), 2.));
        wpi = (float)sin(theta);
        wr = 1.;
        wi = 0.;

        for (m = 0; m < mmax; m += 2)
        {
            register float rtemp, itemp;
            for (i = m; i < ND; i += delta)
            {
                j = i + mmax;
                rtemp = wr*x[j] - wi*x[j + 1];
                itemp = wr*x[j + 1] + wi*x[j];
                if (j >= 511 || i >= 511)
                {
                    j = 0;
                }
                x[j] = x[i] - rtemp;
                x[j + 1] = x[i + 1] - itemp;
                x[i] += rtemp;
                x[i + 1] += itemp;
            }

            wr = (rtemp = wr)*wpr - wi*wpi + wr;
            wi = wi*wpr + rtemp*wpi + wi;
        }
    }

    // scale output
    scale = (float)(forward ? 1. / ND : 2.);
    {
        register float *xi = x, *xe = x + ND;
        while (xi < xe)
            *xi++ *= scale;
    }
}