pfamcc.c

seismic software,very useful

/* Copyright (c) Colorado School of Mines, 1990.
/* All rights reserved.                       */

/*
FUNCTION:  prime factor fft:  multiple complex to complex transforms, in place

PARAMETERS:
isign       i sign of isign is the sign of exponent in fourier kernel
n           i number of complex elements per transform (see notes below)
nt          i number of transforms
k           i stride in complex elements within transforms
kt          i stride in complex elements between transforms
z           b array of complex elements to be transformed in place
 
NOTES:
n must be factorable into mutually prime factors taken 
from the set {2,3,4,5,7,8,9,11,13,16}.  in other words,
    n = 2**p * 3**q * 5**r * 7**s * 11**t * 13**u
where
    0 <= p <= 4,  0 <= q <= 2,  0 <= r,s,t,u <= 1
is required for pfamcc to yield meaningful results.  this
restriction implies that n is restricted to the range
    1 <= n <= 720720 (= 5*7*9*11*13*16)

To perform a two-dimensional transform of an n1 by n2 complex array 
(assuming that both n1 and n2 are valid "n"), stored with n1 fast 
and n2 slow:
    pfamcc(isign,n1,n2,1,n1,z); (to transform 1st dimension)
    pfamcc(isign,n2,n1,n1,1,z); (to transform 2nd dimension)
 
REFERENCES:  
Temperton, C., 1985, Implementation of a self-sorting
in-place prime factor fft algorithm:  Journal of
Computational Physics, v. 58, p. 283-299.

Temperton, C., 1988, A new set of minimum-add rotated
rotated dft modules: Journal of Computational Physics,
v. 75, p. 190-198.

AUTHOR:  I. D. Hale, Colorado School of Mines, 06/15/89
*/

#define P120 0.120536680
#define P142 0.142314838
#define P173 0.173648178
#define P222 0.222520934
#define P239 0.239315664
#define P281 0.281732557
#define P342 0.342020143
#define P354 0.354604887
#define P382 0.382683432
#define P415 0.415415013
#define P433 0.433883739
#define P464 0.464723172
#define P540 0.540640817
#define P559 0.559016994
#define P568 0.568064747
#define P587 0.587785252
#define P623 0.623489802
#define P642 0.642787610
#define P654 0.654860734
#define P663 0.663122658
#define P707 0.707106781
#define P748 0.748510748
#define P755 0.755749574
#define P766 0.766044443
#define P781 0.781831482
#define P822 0.822983866
#define P841 0.841253533
#define P866 0.866025404
#define P885 0.885456026
#define P900 0.900968868
#define P909 0.909631995
#define P923 0.923879533
#define P935 0.935016243
#define P939 0.939692621
#define P951 0.951056516
#define P959 0.959492974
#define P970 0.970941817
#define P974 0.974927912
#define P984 0.984807753
#define P989 0.989821442
#define P992 0.992708874
#define NFAX 10

typedef struct _complexStruct {
    float r,i;
} complex;

void pfamcc (int isign, int n, int nt, int k, int kt, complex cz[])
{
    static int kfax[] = { 16,13,11,9,8,7,5,4,3,2 };
    register float *z=(float*)cz;
    register int j0,j1,j2,j3,j4,j5,j6,j7,j8,j9,j10,j11,j12,j13,j14,j15;
    int nleft,jfax,ifac,jfac,iinc,imax,ndiv,m,mm,mu,l,istep,jstep,
        jt,i0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12,i13,i14,i15,it;
    float t1r,t1i,t2r,t2i,t3r,t3i,t4r,t4i,t5r,t5i,
        t6r,t6i,t7r,t7i,t8r,t8i,t9r,t9i,t10r,t10i,
        t11r,t11i,t12r,t12i,t13r,t13i,t14r,t14i,t15r,t15i,
        t16r,t16i,t17r,t17i,t18r,t18i,t19r,t19i,t20r,t20i,
        t21r,t21i,t22r,t22i,t23r,t23i,t24r,t24i,t25r,t25i,
        t26r,t26i,t27r,t27i,t28r,t28i,t29r,t29i,t30r,t30i,
        t31r,t31i,t32r,t32i,t33r,t33i,t34r,t34i,t35r,t35i,
        t36r,t36i,t37r,t37i,t38r,t38i,t39r,t39i,t40r,t40i,
        t41r,t41i,t42r,t42i,
        y1r,y1i,y2r,y2i,y3r,y3i,y4r,y4i,y5r,y5i,
        y6r,y6i,y7r,y7i,y8r,y8i,y9r,y9i,y10r,y10i,
        y11r,y11i,y12r,y12i,y13r,y13i,y14r,y14i,y15r,y15i,
        c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12;

    /* determine step within and between transforms */
    istep = 2*k;
    jstep = 2*kt;

    /* keep track of n left after dividing by factors */
    nleft = n;

    /* begin loop over possible factors (from biggest to smallest) */
    for (jfax=0; jfax<NFAX; jfax++) {

        /* skip if not a mutually prime factor of n */
        ifac = kfax[jfax];
        ndiv = nleft/ifac;
        if (ndiv*ifac!=nleft) continue;
 
        /* update n left and determine n divided by factor */
        nleft = ndiv;
        m = n/ifac;
 
        /* determine rotation factor mu and stride mm */
        for (jfac=1; jfac<=ifac; jfac++) {
            mu = jfac;
            mm = jfac*m;
            if (mm%ifac==1) break;
        }
 
        /* adjust rotation factor for sign of transform */
        if (isign<0) mu = ifac-mu;
 
        /* compute stride, limit, and pointers */
        iinc = istep*mm;
        imax = istep*n;
        i0 = 0;
        i1 = i0+iinc;

        /* if factor is 2 */
        if (ifac==2) {
            for (l=0; l<m; l++) {
                j0 = i0;
                j1 = i1;
                for (jt=0; jt<nt; jt++) {
                    t1r = z[j0]-z[j1];
                    t1i = z[j0+1]-z[j1+1];
                    z[j0] = z[j0]+z[j1];
                    z[j0+1] = z[j0+1]+z[j1+1];
                    z[j1] = t1r;
                    z[j1+1] = t1i;
                    j0 += jstep;
                    j1 += jstep;
                }
                it = i1+istep;
                i1 = i0+istep;
                i0 = it;
            }
            continue;
        }
        i2 = i1+iinc;
        if (i2>=imax) i2 = i2-imax;

        /* if factor is 3 */
        if (ifac==3) {
            if (mu==1)
                c1 = P866;
            else
                c1 = -P866;
            for (l=0; l<m; l++) {
                j0 = i0;
                j1 = i1;
                j2 = i2;
                for (jt=0; jt<nt; jt++) {
                    t1r = z[j1]+z[j2];
                    t1i = z[j1+1]+z[j2+1];
                    y1r = z[j0]-0.5*t1r;
                    y1i = z[j0+1]-0.5*t1i;
                    y2r = c1*(z[j1]-z[j2]);
                    y2i = c1*(z[j1+1]-z[j2+1]);
                    z[j0] = z[j0]+t1r;
                    z[j0+1] = z[j0+1]+t1i;
                    z[j1] = y1r-y2i;
                    z[j1+1] = y1i+y2r;
                    z[j2] = y1r+y2i;
                    z[j2+1] = y1i-y2r;
                    j0 += jstep;
                    j1 += jstep;
                    j2 += jstep;
                }
                it = i2+istep;
                i2 = i1+istep;
                i1 = i0+istep;
                i0 = it;
            }
            continue;
        }
        i3 = i2+iinc;
        if (i3>=imax) i3 = i3-imax;

        /* if factor is 4 */
        if (ifac==4) {
            if (mu==1)
                c1 = 1.0;
            else
                c1 = -1.0;
            for (l=0; l<m; l++) {
                j0 = i0;
                j1 = i1;
                j2 = i2;
                j3 = i3;
                for (jt=0; jt<nt; jt++) {
                    t1r = z[j0]+z[j2];
                    t1i = z[j0+1]+z[j2+1];
                    t2r = z[j1]+z[j3];
                    t2i = z[j1+1]+z[j3+1];
                    y1r = z[j0]-z[j2];
                    y1i = z[j0+1]-z[j2+1];
                    y3r = c1*(z[j1]-z[j3]);
                    y3i = c1*(z[j1+1]-z[j3+1]);
                    z[j0] = t1r+t2r;
                    z[j0+1] = t1i+t2i;
                    z[j1] = y1r-y3i;
                    z[j1+1] = y1i+y3r;
                    z[j2] = t1r-t2r;
                    z[j2+1] = t1i-t2i;
                    z[j3] = y1r+y3i;
                    z[j3+1] = y1i-y3r;
                    j0 += jstep;
                    j1 += jstep;
                    j2 += jstep;
                    j3 += jstep;
                }
                it = i3+istep;
                i3 = i2+istep;
                i2 = i1+istep;
                i1 = i0+istep;
                i0 = it;
            }
            continue;
        }
        i4 = i3+iinc;
        if (i4>=imax) i4 = i4-imax;

        /* if factor is 5 */
        if (ifac==5) {
            if (mu==1) {
                c1 = P559;
                c2 = P951;
                c3 = P587;
            } else if (mu==2) {
                c1 = -P559;
                c2 = P587;
                c3 = -P951;
            } else if (mu==3) {
                c1 = -P559;
                c2 = -P587;
                c3 = P951;
            } else { 
                c1 = P559;
                c2 = -P951;
                c3 = -P587;
            }
            for (l=0; l<m; l++) {
                j0 = i0;
                j1 = i1;
                j2 = i2;
                j3 = i3;
                j4 = i4;
                for (jt=0; jt<nt; jt++) {
                    t1r = z[j1]+z[j4];
                    t1i = z[j1+1]+z[j4+1];
                    t2r = z[j2]+z[j3];
                    t2i = z[j2+1]+z[j3+1];
                    t3r = z[j1]-z[j4];
                    t3i = z[j1+1]-z[j4+1];
                    t4r = z[j2]-z[j3];
                    t4i = z[j2+1]-z[j3+1];
                    t5r = t1r+t2r;
                    t5i = t1i+t2i;
                    t6r = c1*(t1r-t2r);
                    t6i = c1*(t1i-t2i);
                    t7r = z[j0]-0.25*t5r;
                    t7i = z[j0+1]-0.25*t5i;
                    y1r = t7r+t6r;
                    y1i = t7i+t6i;
                    y2r = t7r-t6r;
                    y2i = t7i-t6i;
                    y3r = c3*t3r-c2*t4r;
                    y3i = c3*t3i-c2*t4i;
                    y4r = c2*t3r+c3*t4r;
                    y4i = c2*t3i+c3*t4i;
                    z[j0] = z[j0]+t5r;
                    z[j0+1] = z[j0+1]+t5i;
                    z[j1] = y1r-y4i;
                    z[j1+1] = y1i+y4r;
                    z[j2] = y2r-y3i;
                    z[j2+1] = y2i+y3r;
                    z[j3] = y2r+y3i;
                    z[j3+1] = y2i-y3r;
                    z[j4] = y1r+y4i;
                    z[j4+1] = y1i-y4r;
                    j0 += jstep;
                    j1 += jstep;
                    j2 += jstep;
                    j3 += jstep;
                    j4 += jstep;
                }
                it = i4+istep;
                i4 = i3+istep;
                i3 = i2+istep;
                i2 = i1+istep;
                i1 = i0+istep;
                i0 = it;
            }
            continue;
        }
        i5 = i4+iinc;
        if (i5>=imax) i5 = i5-imax;
        i6 = i5+iinc;
        if (i6>=imax) i6 = i6-imax;

        /* if factor is 7 */
        if (ifac==7) {
            if (mu==1) {
                c1 = P623;
                c2 = -P222;
                c3 = -P900;
                c4 = P781;
                c5 = P974;
                c6 = P433;
            } else if (mu==2) {
                c1 = -P222;
                c2 = -P900;
                c3 = P623;
                c4 = P974;
                c5 = -P433;
                c6 = -P781;
            } else if (mu==3) {
                c1 = -P900;
                c2 = P623;
                c3 = -P222;
                c4 = P433;
                c5 = -P781;
                c6 = P974;
            } else if (mu==4) {
                c1 = -P900;
                c2 = P623;
                c3 = -P222;
                c4 = -P433;
                c5 = P781;
                c6 = -P974;
            } else if (mu==5) {
                c1 = -P222;
                c2 = -P900;
                c3 = P623;
                c4 = -P974;
                c5 = P433;
                c6 = P781;
            } else {
                c1 = P623;
                c2 = -P222;
                c3 = -P900;
                c4 = -P781;
                c5 = -P974;
                c6 = -P433;