/* fft512.c  complex data stored  re, im, re, im, re, ... im */

void fft512(float Z[1024]) /* input data points and output  [0] to [1023] */
{
  static float W[1024];    /* scratch vector, used many times, */
  static float E[514] =    /* constants for FFT algorithm */
  {1.0, 0.0, 0.999925, 0.0122715,
   0.999699, 0.0245412, 0.999322, 0.0368072,
   0.998796, 0.0490677, 0.998118, 0.0613207,
   0.99729, 0.0735646, 0.996313, 0.0857973,
   0.995185, 0.0980171, 0.993907, 0.110222,
   0.99248, 0.122411, 0.990903, 0.134581,
   0.989177, 0.14673, 0.987302, 0.158858,
   0.985278, 0.170962, 0.983106, 0.18304,
   0.980785, 0.19509, 0.978318, 0.207111,
   0.975702, 0.219101, 0.97294, 0.231058,
   0.970031, 0.24298, 0.966977, 0.254866,
   0.963776, 0.266713, 0.960431, 0.27852,
   0.95694, 0.290285, 0.953306, 0.302006,
   0.949528, 0.313682, 0.945607, 0.32531,
   0.941544, 0.33689, 0.937339, 0.348419,
   0.932993, 0.359895, 0.928506, 0.371317,
   0.92388, 0.382683, 0.919114, 0.393992,
   0.91421, 0.405241, 0.909168, 0.41643,
   0.903989, 0.427555, 0.898675, 0.438616,
   0.893224, 0.449611, 0.88764, 0.460539,
   0.881921, 0.471397, 0.87607, 0.482184,
   0.870087, 0.492898, 0.863973, 0.503538,
   0.857729, 0.514103, 0.851355, 0.52459,
   0.844854, 0.534998, 0.838225, 0.545325,
   0.83147, 0.55557, 0.824589, 0.565732,
   0.817585, 0.575808, 0.810457, 0.585798,
   0.803208, 0.595699, 0.795837, 0.605511,
   0.788346, 0.615232, 0.780737, 0.62486,
   0.77301, 0.634393, 0.765167, 0.643832,
   0.757209, 0.653173, 0.749136, 0.662416,
   0.740951, 0.671559, 0.732654, 0.680601,
   0.724247, 0.689541, 0.715731, 0.698376,
   0.707107, 0.707107, 0.698376, 0.715731,
   0.689541, 0.724247, 0.680601, 0.732654,
   0.671559, 0.740951, 0.662416, 0.749136,
   0.653173, 0.757209, 0.643832, 0.765167,
   0.634393, 0.77301, 0.62486, 0.780737,
   0.615232, 0.788346, 0.605511, 0.795837,
   0.595699, 0.803208, 0.585798, 0.810457,
   0.575808, 0.817585, 0.565732, 0.824589,
   0.55557, 0.83147, 0.545325, 0.838225,
   0.534998, 0.844854, 0.52459, 0.851355,
   0.514103, 0.857729, 0.503538, 0.863973,
   0.492898, 0.870087, 0.482184, 0.87607,
   0.471397, 0.881921, 0.460539, 0.88764,
   0.449611, 0.893224, 0.438616, 0.898675,
   0.427555, 0.903989, 0.41643, 0.909168,
   0.405241, 0.91421, 0.393992, 0.919114,
   0.382683, 0.92388, 0.371317, 0.928506,
   0.359895, 0.932993, 0.348419, 0.937339,
   0.33689, 0.941544, 0.32531, 0.945607,
   0.313682, 0.949528, 0.302006, 0.953306,
   0.290285, 0.95694, 0.27852, 0.960431,
   0.266713, 0.963776, 0.254866, 0.966977,
   0.24298, 0.970031, 0.231058, 0.97294,
   0.219101, 0.975702, 0.207111, 0.978318,
   0.19509, 0.980785, 0.18304, 0.983106,
   0.170962, 0.985278, 0.158858, 0.987302,
   0.14673, 0.989177, 0.134581, 0.990903,
   0.122411, 0.99248, 0.110222, 0.993907,
   0.0980171, 0.995185, 0.0857973, 0.996313,
   0.0735646, 0.99729, 0.0613207, 0.998118,
   0.0490677, 0.998796, 0.0368072, 0.999322,
   0.0245412, 0.999699, 0.0122715, 0.999925,
   0.0, 1.0, -0.0122715, 0.999925,
   -0.0245412, 0.999699, -0.0368072, 0.999322,
   -0.0490677, 0.998796, -0.0613207, 0.998118,
   -0.0735646, 0.99729, -0.0857973, 0.996313,
   -0.0980171, 0.995185, -0.110222, 0.993907,
   -0.122411, 0.99248, -0.134581, 0.990903,
   -0.14673, 0.989177, -0.158858, 0.987302,
   -0.170962, 0.985278, -0.18304, 0.983106,
   -0.19509, 0.980785, -0.207111, 0.978318,
   -0.219101, 0.975702, -0.231058, 0.97294,
   -0.24298, 0.970031, -0.254866, 0.966977,
   -0.266713, 0.963776, -0.27852, 0.960431,
   -0.290285, 0.95694, -0.302006, 0.953306,
   -0.313682, 0.949528, -0.32531, 0.945607,
   -0.33689, 0.941544, -0.348419, 0.937339,
   -0.359895, 0.932993, -0.371317, 0.928506,
   -0.382683, 0.92388, -0.393992, 0.919114,
   -0.405241, 0.91421, -0.41643, 0.909168,
   -0.427555, 0.903989, -0.438616, 0.898675,
   -0.449611, 0.893224, -0.460539, 0.88764,
   -0.471397, 0.881921, -0.482184, 0.87607,
   -0.492898, 0.870087, -0.503538, 0.863973,
   -0.514103, 0.857729, -0.52459, 0.851355,
   -0.534998, 0.844854, -0.545325, 0.838225,
   -0.55557, 0.83147, -0.565732, 0.824589,
   -0.575808, 0.817585, -0.585798, 0.810457,
   -0.595699, 0.803208, -0.605511, 0.795837,
   -0.615232, 0.788346, -0.62486, 0.780737,
   -0.634393, 0.77301, -0.643832, 0.765167,
   -0.653173, 0.757209, -0.662416, 0.749136,
   -0.671559, 0.740951, -0.680601, 0.732654,
   -0.689541, 0.724247, -0.698376, 0.715731,
   -0.707107, 0.707107, -0.715731, 0.698376,
   -0.724247, 0.689541, -0.732654, 0.680601,
   -0.740951, 0.671559, -0.749136, 0.662416,
   -0.757209, 0.653173, -0.765167, 0.643832,
   -0.77301, 0.634393, -0.780737, 0.62486,
   -0.788346, 0.615232, -0.795837, 0.605511,
   -0.803208, 0.595699, -0.810457, 0.585798,
   -0.817585, 0.575808, -0.824589, 0.565732,
   -0.83147, 0.55557, -0.838225, 0.545325,
   -0.844854, 0.534998, -0.851355, 0.52459,
   -0.857729, 0.514103, -0.863973, 0.503538,
   -0.870087, 0.492898, -0.87607, 0.482184,
   -0.881921, 0.471397, -0.88764, 0.460539,
   -0.893224, 0.449611, -0.898675, 0.438616,
   -0.903989, 0.427555, -0.909168, 0.41643,
   -0.91421, 0.405241, -0.919114, 0.393992,
   -0.92388, 0.382683, -0.928506, 0.371317,
   -0.932993, 0.359895, -0.937339, 0.348419,
   -0.941544, 0.33689, -0.945607, 0.32531,
   -0.949528, 0.313682, -0.953306, 0.302006,
   -0.95694, 0.290285, -0.960431, 0.27852,
   -0.963776, 0.266713, -0.966977, 0.254866,
   -0.970031, 0.24298, -0.97294, 0.231058,
   -0.975702, 0.219101, -0.978318, 0.207111,
   -0.980785, 0.19509, -0.983106, 0.18304,
   -0.985278, 0.170962, -0.987302, 0.158858,
   -0.989177, 0.14673, -0.990903, 0.134581,
   -0.99248, 0.122411, -0.993907, 0.110222,
   -0.995185, 0.0980171, -0.996313, 0.0857973,
   -0.99729, 0.0735646, -0.998118, 0.0613207,
   -0.998796, 0.0490677, -0.999322, 0.0368072,
   -0.999699, 0.0245412, -0.999925, 0.0122715,
   -1.0, 0.0};
  float Tre, Tim;
  int i, j, k, l, m;

   m = 256;
   l = 1;
   while(1)
   { 
      k = 0;
      j = l;
      i = 0;
      while(1)
      { 
         while(1)
	 {
	   /* W[i+k] = Z[i] + Z[m+i]; complex */
           W[2*(i+k)]   = Z[2*i]   + Z[2*(m+i)];
           W[2*(i+k)+1] = Z[2*i+1] + Z[2*(m+i)+1];

           /* W[i+j] = E[k] * (Z[i] - Z[m+i]); complex */
           Tre = Z[2*i]   - Z[2*(m+i)];
           Tim = Z[2*i+1] - Z[2*(m+i)+1];
           W[2*(i+j)]   = E[2*k] * Tre - E[2*k+1] * Tim;
           W[2*(i+j)+1] = E[2*k] * Tim + E[2*k+1] * Tre; 
           i++;
           if(i >= j) break;
	 }
         k = j;
         j = k+l;
         if(j > m) break;
      }
      l = l+l;
      if(l > m)
      {
        for(i=0; i<4*m; i++) Z[i] = W[i]; // odd power finish
        return;
      }
                  /* work back other way without copying */
      k = 0;
      j = l;
      i = 0;
      while(1)
      {
        while(1)
	{
          /* Z[i+k] = W[i] + W[m+i]; complex */
          Z[2*(i+k)]   = W[2*i]   + W[2*(m+i)];
          Z[2*(i+k)+1] = W[2*i+1] + W[2*(m+i)+1];

          /* Z[i+j] = E[k] * (W[i] - W[m+i]); complex */
          Tre = W[2*i]   - W[2*(m+i)];
          Tim = W[2*i+1] - W[2*(m+i)+1];
          Z[2*(i+j)]   = E[2*k] * Tre - E[2*k+1] * Tim;
          Z[2*(i+j)+1] = E[2*k] * Tim + E[2*k+1] * Tre;
          i++;
          if(i >= j) break;
	}
        k = j;
        j = k+l;
        if(j > m) break;
      }
      l = l+l;
      if(l > m) break; // result is in Z
   }
} /* end fft512 */