public void doFFT(double [] xr, double [] xi, boolean invFlag) {
        int n, n2, i, k, kn2, l, p;
        double ang, s, c, tr, ti;

        n2 = (n = (1 << bits)) / 2;

        for (l = 0; l < bits; ++l) {
            for (k = 0; k < n; k += n2) {
                for (i = 0; i < n2; ++i, ++k) {
                    p = bitreverse[k / n2];
                    ang = TWOPI * p / n;
                    c = Math.cos(ang);
                    s = Math.sin(ang);
                    kn2 = k + n2;

                    if (invFlag)
                        s = -s;

                    tr = xr[kn2] * c + xi[kn2] * s;
                    ti = xi[kn2] * c - xr[kn2] * s;

                    xr[kn2] = xr[k] - tr;
                    xi[kn2] = xi[k] - ti;
                    xr[k] += tr;
                    xi[k] += ti;
                }
            }
            n2 /= 2;
        }

        for (k = 0; k < n; k++) {
            if ((i = bitreverse[k]) <= k)
                continue;

            tr = xr[k];
            ti = xi[k];
            xr[k] = xr[i];
            xi[k] = xi[i];
            xr[i] = tr;
            xi[i] = ti;
        }

        // Finally, multiply each value by 1/n, if this is the forward
        // transform.
        if (!invFlag) {
            double f = 1.0 / n;

            for (i = 0; i < n ; i++) {
                xr[i] *= f;
                xi[i] *= f;
            }
        }
    }