/*	Copyright (c) 1982 Michael Landy, Yoav Cohen, and George Sperling

Disclaimer:  No guarantees of performance accompany this software,
nor is any responsibility assumed on the part of the authors.  All the
software has been tested extensively and every effort has been made to
insure its reliability.   */

/* 1991 Modified by N. Dessipris to return a valid code on error */

/* fft -- fast fourier transform, adapted from 
** Gonzalez & Wintz p.87.
**
** No division by N is performed.
**
** Timing: rough estimates:
**   two-dimensional arrays, (including copying columns
**	 back and forth):
**	 for arrays up to 16X16: less than 1 sec.
**	 for 32X32 arrays: about 3.0 sec.
**	 for 64X64 arrays: about 9.0 sec.
**	 for 128X128 arrays: about 31.0 sec.
**
** Calling sequence:
**
** float *rvec,*ivec;
** int loglen,skip;
**
** fft_2d(rvec,ivec,loglen)
** performs a 2-dimensional fft where loglen is the log of the length of
** a side of the array
**
** fft_2dgen(rvec,ivec,logrows,logcols)
** performs a 2-dimensional fft where logrows is the log of the number of
** rows, and logcols is the log of the number of columns
**
** fftn(rvec,ivec,loglen,skip)
** performs a 1-dimensional fft on every skip-th entry
*/

/*

    This file is part of VIPS.
    
    VIPS is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 */

/*

    These files are distributed with VIPS - http://www.vips.ecs.soton.ac.uk

 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif /*HAVE_CONFIG_H*/
#include <vips/intl.h>

/* Only compile this if we're missing the fftw library.
 */
#if !HAVE_FFTW && !HAVE_FFTW3

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

#include <vips/vips.h>

#ifdef WITH_DMALLOC
#include <dmalloc.h>
#endif /*WITH_DMALLOC*/

static float *Const = NULL, *iConst = NULL;
static int storesize = 0, Constsize = 0;

static int 
fftn(rvec,ivec,loglen,nskip)

float *rvec,*ivec;
int loglen,nskip;

{
	int n,nv2,nm1,i,j,k,l,le,le1,c,nle;
	float	*rveci , *rvecj , *iveci , *ivecj ;
	float	t,wr,wi,tr,ti ;

	if(loglen==0)
		return(-1);
	n=1<<loglen ;
	nv2=n >> 1 ; nm1=n-1 ; j=0 ;
	if (storesize<nv2) {
		if ((0==(Const=(float *)calloc((unsigned)nv2,sizeof(float)))) ||
		    (0==(iConst=(float *)calloc((unsigned)nv2,sizeof(float))))){
			im_errormsg( "Not enough core for fftn" );
			return(-1);
		}
		storesize = nv2;
	}
	if (Constsize!=nv2) {
		Constsize = nv2;
		wr =  cos(2*IM_PI/n);
		wi = -sin(2*IM_PI/n);
		Const[0] = 1.;
		iConst[0] = 0.;
		for (i=1;i<nv2;i++) {
			Const[i] = wr*Const[i-1] - wi*iConst[i-1];
			iConst[i] = wr*iConst[i-1] + wi*Const[i-1];
		}
	}
	for (i=0;i<nm1;i++) {
		if(i<j) {
			rveci=rvec+i*nskip ; rvecj=rvec+j*nskip ;
			t=(*rvecj) ; *rvecj=(*rveci) ; *rveci=t ; 
			iveci=ivec+i*nskip ; ivecj=ivec+j*nskip ;
			t=(*ivecj) ; *ivecj=(*iveci) ; *iveci=t ;
		}
		k=nv2 ;
		while (k<=j) {
			j-=k ; k>>=1 ;
		}
		j+=k ;
	}
	le=1 ;
	for (l=0;l<loglen;l++) {
		le1=le ; le+=le ; c = 0; nle = n/le;
		for (j=0;j<le1;j++) {
			for (i=j;i<n;i+=le) {
				if(i+le1>=n) {
					im_warning("index=%d\n",i+le1);
					return(-1);
				}
				rveci=rvec+i*nskip ; rvecj=rvec+(i+le1)*nskip;
			  	iveci=ivec+i*nskip ; ivecj=ivec+(i+le1)*nskip;

			  	if (c==0) {
					tr = *rvecj;
					ti = *ivecj;
				}
				else {
					tr = *rvecj*Const[c] - *ivecj*iConst[c];
					ti = *rvecj*iConst[c] + *ivecj*Const[c];
				}
				*rvecj = *rveci - tr;
				*ivecj = *iveci - ti;

				*rveci += tr;
				*iveci += ti;
			}
			c += nle;
		}
	}
/* Division by n
	for(i=0;i<n;i++)
		{rvec[i*nskip]/=n ; ivec[i*nskip]/=n ;}
*/
	return(0);
}


static void
free_store( void )
{
	if( Const ) {
		free( Const );
		Const = NULL;
	}
	if( iConst ) {
		free( iConst );
		iConst = NULL;
	}

	storesize = 0;
	Constsize = 0;
}

int
im__fft_sp( float *rvec, float *ivec, int logrows, int logcols )
{
	int i,rows,cols,size;

	rows = 1<<logrows;
	cols = 1<<logcols;
	size = rows * cols;

	for (i=0;i<size;i+=cols)
		if ( fftn(rvec+i,ivec+i,logcols,1) == -1) {
			free_store();
			return(-1);
		}

	for (i=0;i<cols;i++)
		if ( fftn(rvec+i,ivec+i,logrows,cols) == -1) {
			free_store();
			return(-1);
		}

	free_store();
	return(0);
}

#endif /*HAVE_FFTW*/