Table of Contents:
==================
1. Introduction
2. What's working
3. What's going to work
4. How to use it
   4.1. Building and Installing
   4.2. Initializing
   4.3. Assign Sample Data
   4.4. Perform the FFT
   4.5. Examples
5. Build on Android
6. Performing convolutions
7. You said its fast how fast is it?
8. License (LGPL)

1. Introduction of libsimplefft
===============================
This library is designed to run as fast as possible.
Several optimization are implemented by default.
This implementation uses the Radix 2 decimation in frequency
Fast Fourier Transform (Radix 2 DIF FFT).
It's an in place algorithmus using precomputed twiddle factors.
There are no parallel threads working.
This implementation is designed to be as fundamental as possible.

Its a paper and pen implementation by myself.
So it is not ment to compete with other even more faster implementations.
I implemented this library just for fun and my scientific curiosity and 
the urge to find out how this thing manage to be so much faster than plain
DFT implementation. Well in short I found it out and I wanted to share my
results. So have fun looking through the code or use it for your projects.

2. What's working?
===============================
- GNU Auto Build
- FFT and iFFT for single, double and integer precision are implemented
- JNI Access
- Android Build and usage via JNI
- Fast Convolution in C and Java using JNI
- nth dimension FFTs
- Introduced new Integer Precision types (8 and 32 Bit)

3. What's going to work?
===============================
- further low latency optimations
- cast FFTs into another data precision type
- I consider a parallized version running several threads,
  but no commitment on that one.

4. How to use it
===============================

4.1. Building and installing
-------------------------------
At first checkout the source repository.
The current release is shipped with a GNU Auto Build system.

For Android see "Build on Android" section below!

In order to build use:

	./autogen.sh

and followed if finished by:

	./configure

to install the library to your install prefix.
You may change it on the "configure" call to your deeds.

For example if you want to use the java native interface,
provided by this library you'll need to run (this is optional):

	./configure --enable-jni JDK_HOME=/path/to/jdk/root

It will generate all makefiles according to your systems
configuration. Once this is done successfully run:

	make

After finished just run

	sudo make install

4.2. Initializing
-------------------------------
Standard include the file by

	#include<libsimplefft/libsimplefft.h>

NOTE: also check out the header files for further information!

NOTE: the old FFT implementations stays for a few further commits.
Until then the multi dimension FFTs have the "_md" suffix.
Please use these functions and refer the header files for parameter description
The Procedure is the same as in this description!

Allmost done next step is to allocate a FFT context, which computes
necessary twiddle factors and does some other caching work for you.
The function lsfft_init does that for you, it returns a pointer to a valid
FFT_CONTEXT you need to specify several parameters in order to get
this thing to work:

	1.) Enter the samples the FFT is going to be processed.
		Remind that a power of 2 size is required!

	2.) Specify the mode of the FFT, there are for choise:

		FFT_TYPE_NORMAL : which performes the FFT
		                  in the Time to Frequency domain direction
		FFT_TYPE_INVERSE: which performes the inverse FFT
		                  in the Frequency to Time domain direction

	3.) Specify the data, which is going to be processed:

		CPLX_TYPE_SP : which denotes a single precision FFT (float)
		CPLX_TYPE_DP : which denotes a double precision FFT (double)
		CPLX_TYPE_INT: which denotes a 16 bit signed integer FFT (uint16_t)

Now the FFT is fully initialized.

To perform it on some data you'll need to allocate a CPLX_SAMPLES structure,
better a pointer to its location.

Easiest way to do so is using the lsfft_alloc_complex_buffer function.
Remind that you have to specify the datatype as well.

Here you have to specify two parameters to get a valid structure:

	1.) The sample size which needs to be of the same size as you specified
		at the FFT initialization.

	2.) The data type of the samples going to be processed.
		This is also has to be the same as at in the FFT initialization

The function lsfft_alloc_complex_buffer returns the a pointer to the allocated
structure.

4.3. Assign Sample Data
-------------------------------
Now you are ready to go. To assign your data you can cast the re and im field
of the CPLX_SAMPLES structure to a fiting pointer to $TYPE pointer.

For example if you're using single precision FFT you need to cast it to a
float pointer (double if double precision and int16_t on integer precision):

	CPLX_SAMPLES* samples;

	//initialization ... allocation etc.

	float* re = (float*)samples->re;
	float* im = (float*)samples->im;

now you can access the real and imaginary part components of the vector
by using the [] operator. Remind that you have to keep track of your
allocations, and so of the datatypes!

4.4. Perform the FFT
--------------------------------
The last step is to call the lsfft_perform function assigning your FFT_CONTEXT
and your CPLX_SAMPLES pointers, to let the FFT do its work. After returning
the result is stored within the CPLX_SAMPLES structure you assigned to call lsfft_perform
since its an in place FFT.

4.5. Examples
--------------------------------
There are examples on how to use libsimplefft in C just checkout the example directory

5. Build on Android
========================================
Set up your project. Stop at the point where you
have to create the "jni" folder.
Instead of creating it, symbolic link the root directory 
of the libsimplefft repository to the "jni" folder using:

	ln -s /full/path/to/repo/of/libsimplefft/ /full/path/to/project/in/workspace/jni
	
After that you can run:

	ndk-build

To let the Android NDK build libraries

Afterwarts add the "java" directory to your Android applications build path
so you can use the JNI Interface classes.

6. Performing Convolutions
========================================
Since last commitment libsimplefft supports fast convolutions, to provide
fast filtering. It's in an early state and needs some fixes.
I uses the fft implementation to perform the convolution in the frequency
domain (see: convolution theorem).
This implementation has still several issues like decimal place cropping.
So it's is not very accurate yet, and produces noise as
effect of rounding errors (Going to be fixed soon).

To perform a fast convolution create a fast convolution context using the
lsfft_init_convolution function. It requires a single parameter which contains
the real domain convolution kernel and the size of the supporting FFTs.
This CPLX_SAMPLES structure is created using the lsfft_alloc_complex_buffer
function specifying the samples count going to be processed. It makes sure
that this size is a power of two so its recommended to use it.

After that you assign you kernel values to the storage assigned 
to the CPLX_SAMPLES->re pointer.

If you call the lsfft_init_convolution function it will create the
necessary FFTs for you and process the kernel, in transforming it
into the frequency domain.

A valid pointer to a CONVOLUTION_CONTEXT is returned containing all required 
data. To perform a fast convolution assign the CONVOLUTION_CONTEXT
and the signal of the same size of the kernel CPLX_SAMPLES structure.
Now call lsfft_perform_convolution.
The result is stored in the same structure as signal.

7. You said its fast how fast is it?
========================================
it would be a FFT if it would'nt be fast so here some facts:
Test machine :

	Intel i5 430M 2.4 GHz
	4GB RAM 
	Ubuntu linux 3.0.0.17 x64

A dash "-" means there are no time values since clock() returned zero.
This are single precision calculations, if the further types are available, there
going to be added here. If I manage to port it to ARM there will be a benchmark too.

	  size  | time(ms)
	--------+---------
	   1024 |      -
	   2048 |      -
	   4096 |      -
	   8192 |      -
	  16384 |      -
	  32768 |     20
	  65536 |     20
	 131072 |     50
	 262144 |    120
	 524288 |    280
	1048576 |    780

8. License
========================================
Copyright (C) 2012  Kevin Krüger (kkevin@gmx.net)

libsimplefft 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.1 of the License, or (at your option) any later version.

libsimplefft 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 libsimplefft; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA