Chris@25: <%= $:.unshift('.'); require "#{File.dirname(__FILE__)}/../src/complex.rb"; File.read "#{File.dirname(__FILE__)}/../LICENSE" %>
Chris@25: 
Chris@25: if (!FFT) {
Chris@25: 	var FFT = {}
Chris@25: }
Chris@25: 
Chris@25: void function (namespace) {
Chris@25: 	"use strict"
Chris@25: 	
Chris@25: 	function forwardButterfly2(output, outputOffset, outputStride, input, inputOffset, inputStride, product, n, twiddle, fStride) {
Chris@25: 		var m = n / 2, q = n / product, old = product / 2
Chris@25: 		
Chris@25: 		for (var i = 0; i < q; i++) {
Chris@25: 			var a0 = old * i
Chris@25: 			var a1 = a0 + m
Chris@25: 			
Chris@25: 			var s0 = input[inputOffset + inputStride * a0]
Chris@25: 			var s1 = input[inputOffset + inputStride * a1]
Chris@25: 			
Chris@25: 			var r0 = s0 + s1
Chris@25: 			var r1 = s0 - s1
Chris@25: 			
Chris@25: 			var a0 = product * i
Chris@25: 			var a1 = a0 + product - 1
Chris@25: 			
Chris@25: 			output[outputOffset + outputStride * a0] = r0
Chris@25: 			output[outputOffset + outputStride * a1] = r1
Chris@25: 		}
Chris@25: 		
Chris@25: 		if (old == 1) { return }
Chris@25: 		
Chris@25: 		for (var i = 0; i < old / 2; i++) {
Chris@25: 			<%= load('t1', 'twiddle', -1, 'i') %>
Chris@25: 			
Chris@25: 			for (var j = 0; j < q; j++) {
Chris@25: 				var a0 = j * old + 2 * i - 1
Chris@25: 				var a1 = a0 + m
Chris@25: 				
Chris@25: 				<%= load('s0', 'input', 'inputOffset', 'a0', 'inputStride') %>
Chris@25: 				
Chris@25: 				<%= load('s1', 'input', 'inputOffset', 'a1', 'inputStride') %>
Chris@25: 				<%= cmul('v1', 's1', 't1') %>
Chris@25: 				
Chris@25: 				<%= cadd('r0', 's0', 'v1') %>
Chris@25: 				<%= csub('r1', 's0', 'v1') %>; r1_i = -r1_i
Chris@25: 				
Chris@25: 				var a0 = j * product + 2 * i - 1
Chris@25: 				var a1 = (j - 1) * product - 2 * i - 1
Chris@25: 				
Chris@25: 				<%= store('r0', 'output', 'outputOffset', 'a0', 'outputStride') %>
Chris@25: 				<%= store('r1', 'output', 'outputOffset', 'a1', 'outputStride') %>
Chris@25: 			}
Chris@25: 		}
Chris@25: 		
Chris@25: 		if (old % 2 == 1) { return }
Chris@25: 		
Chris@25: 		for (var i = 0; i < q; i++) {
Chris@25: 			var a0 = (i + 1) * old - 1
Chris@25: 			var a1 = a0 + m
Chris@25: 			
Chris@25: 			var r0_r =  <%= real('input', 'inputOffset', 'a0', 'inputStride') %>
Chris@25: 			var r1_i = -<%= real('input', 'inputOffset', 'a1', 'inputStride') %>
Chris@25: 			
Chris@25: 			var a0 = i * product + old - 1
Chris@25: 			
Chris@25: 			<%= store('r0', 'output', 'outputOffset', 'a0', 'outputStride') %>
Chris@25: 		}
Chris@25: 	}
Chris@25: 	
Chris@25: 	function forwardButterfly(output, outputOffset, outputStride, input, inputOffset, inputStride, product, n, twiddle, fStride, factor) {
Chris@25: 		var m = n / 2, q = n / product, old = product / 2
Chris@25: 		
Chris@25: 		var theta = 2.0 * Math.PI / factor
Chris@25: 		
Chris@25: 		var theta_r =  Math.cos(theta)
Chris@25: 		var theta_i = -Math.sin(theta)
Chris@25: 		
Chris@25: 		for (var i = 0; i < q; i++) {
Chris@25: 			var d_r = 1.0
Chris@25: 			var d_i = 0.0
Chris@25: 			
Chris@25: 			for (var j = 0; j <= Math.floor(factor / 2); j++) {
Chris@25: 				var sum_r = 0.0
Chris@25: 				var sum_i = 0.0
Chris@25: 				
Chris@25: 				var w_r = 1.0
Chris@25: 				var w_i = 0.0
Chris@25: 				
Chris@25: 				if (j > 0) {
Chris@25: 					<%= cmul('t0', 'd', 'theta') %>
Chris@25: 					
Chris@25: 					d_r = t0_r
Chris@25: 					d_i = t0_i
Chris@25: 				}
Chris@25: 				
Chris@25: 				for (var k = 0; k < factor; k++) {
Chris@25: 					var z = <%= real('input', 'inputOffset', 'i * old + k * m', 'inputStride') %>
Chris@25: 					
Chris@25: 					if (k > 0) {
Chris@25: 						<%= cmul('t0', 'd', 'w') %>
Chris@25: 						
Chris@25: 						d_r = t0_r
Chris@25: 						d_i = t0_i
Chris@25: 					}
Chris@25: 					
Chris@25: 					/* TODO: Use Kahan summation..? */
Chris@25: 					s_r += w_r * z
Chris@25: 					s_i += w_i * z
Chris@25: 				}
Chris@25: 				
Chris@25: 				if (j == 0) {
Chris@25: 					var a0 = product * i
Chris@25: 					
Chris@25: 					output[outputOffset + outputStride * a0] = sum_r
Chris@25: 				} else if (j < factor / 2) {
Chris@25: 					var a0 = product * i
Chris@25: 					
Chris@25: 					output[outputOffset + outputStride * a0] = sum_r
Chris@25: 				} else if (j == factor / 2) {
Chris@25: 					
Chris@25: 				}
Chris@25: 			}
Chris@25: 	        for (e1 = 0; e1 <= factor - e1; e1++)
Chris@25: 	          {
Chris@25: 	            if (e1 == 0)
Chris@25: 	              {
Chris@25: 	                const size_t to0 = product * k1;
Chris@25: 	                VECTOR(out,ostride,to0) = sum_real;
Chris@25: 	              }
Chris@25: 	            else if (e1 < factor - e1)
Chris@25: 	              {
Chris@25: 	                const size_t to0 = k1 * product + 2 * e1 * product_1 - 1;
Chris@25: 	                VECTOR(out,ostride,to0) = sum_real;
Chris@25: 	                VECTOR(out,ostride,to0 + 1) = sum_imag;
Chris@25: 	              }
Chris@25: 	            else if (e1 == factor - e1)
Chris@25: 	              {
Chris@25: 	                const size_t to0 = k1 * product + 2 * e1 * product_1 - 1;
Chris@25: 	                VECTOR(out,ostride,to0) = sum_real;
Chris@25: 	              }
Chris@25: 
Chris@25: 	          }
Chris@25: 			
Chris@25: 		}
Chris@25: 		
Chris@25: 		if (old == 1) { return }
Chris@25: 		
Chris@25: 		for (var i = 0; i < old / 2; i++) {
Chris@25: 			
Chris@25: 		}
Chris@25: 		
Chris@25: 		if (old % 2 == 1) { return }
Chris@25: 		
Chris@25: 		var t_arg = Math.PI / factor
Chris@25: 		
Chris@25: 		var t_r =  cos(t_arg)
Chris@25: 		var t_i = -sin(t_arg)
Chris@25: 		
Chris@25: 		for (var i = 0; i < q; i++) {
Chris@25: 			
Chris@25: 		}
Chris@25: 	}
Chris@25: 
Chris@25:     if (product_1 == 1)
Chris@25:       return;
Chris@25: 
Chris@25:     for (k = 1; k < (product_1 + 1) / 2; k++)
Chris@25:       {
Chris@25:         for (k1 = 0; k1 < q; k1++)
Chris@25:           {
Chris@25: 
Chris@25:             ATOMIC dw_real = 1.0, dw_imag = 0.0;
Chris@25: 
Chris@25:             for (e1 = 0; e1 < factor; e1++)
Chris@25:               {
Chris@25:                 ATOMIC sum_real = 0.0, sum_imag = 0.0;
Chris@25: 
Chris@25:                 ATOMIC w_real = 1.0, w_imag = 0.0;
Chris@25: 
Chris@25:                 if (e1 > 0)
Chris@25:                   {
Chris@25:                     const ATOMIC tmp_real = dw_real * cos_d_theta + dw_imag * sin_d_theta;
Chris@25:                     const ATOMIC tmp_imag = -dw_real * sin_d_theta + dw_imag * cos_d_theta;
Chris@25:                     dw_real = tmp_real;
Chris@25:                     dw_imag = tmp_imag;
Chris@25:                   }
Chris@25: 
Chris@25:                 for (e2 = 0; e2 < factor; e2++)
Chris@25:                   {
Chris@25: 
Chris@25:                     int tskip = (product_1 + 1) / 2 - 1;
Chris@25:                     const size_t from0 = k1 * product_1 + 2 * k + e2 * m - 1;
Chris@25:                     ATOMIC tw_real, tw_imag;
Chris@25:                     ATOMIC z_real, z_imag;
Chris@25: 
Chris@25:                     if (e2 == 0)
Chris@25:                       {
Chris@25:                         tw_real = 1.0;
Chris@25:                         tw_imag = 0.0;
Chris@25:                       }
Chris@25:                     else
Chris@25:                       {
Chris@25:                         const size_t t_index = (k - 1) + (e2 - 1) * tskip;
Chris@25:                         tw_real = GSL_REAL(twiddle[t_index]);
Chris@25:                         tw_imag = -GSL_IMAG(twiddle[t_index]);
Chris@25:                       }
Chris@25: 
Chris@25:                     {
Chris@25:                       const ATOMIC f0_real = VECTOR(in,istride,from0);
Chris@25:                       const ATOMIC f0_imag = VECTOR(in,istride,from0 + 1);
Chris@25: 
Chris@25:                       z_real = tw_real * f0_real - tw_imag * f0_imag;
Chris@25:                       z_imag = tw_real * f0_imag + tw_imag * f0_real;
Chris@25:                     }
Chris@25: 
Chris@25:                     if (e2 > 0)
Chris@25:                       {
Chris@25:                         const ATOMIC tmp_real = dw_real * w_real - dw_imag * w_imag;
Chris@25:                         const ATOMIC tmp_imag = dw_real * w_imag + dw_imag * w_real;
Chris@25:                         w_real = tmp_real;
Chris@25:                         w_imag = tmp_imag;
Chris@25:                       }
Chris@25: 
Chris@25:                     sum_real += w_real * z_real - w_imag * z_imag;
Chris@25:                     sum_imag += w_real * z_imag + w_imag * z_real;
Chris@25:                   }
Chris@25: 
Chris@25:                 if (e1 < factor - e1)
Chris@25:                   {
Chris@25:                     const size_t to0 = k1 * product - 1 + 2 * e1 * product_1 + 2 * k;
Chris@25:                     VECTOR(out,ostride,to0) = sum_real;
Chris@25:                     VECTOR(out,ostride,to0 + 1) = sum_imag;
Chris@25:                   }
Chris@25:                 else
Chris@25:                   {
Chris@25:                     const size_t to0 = k1 * product - 1 + 2 * (factor - e1) * product_1 - 2 * k;
Chris@25:                     VECTOR(out,ostride,to0) = sum_real;
Chris@25:                     VECTOR(out,ostride,to0 + 1) = -sum_imag;
Chris@25:                   }
Chris@25: 
Chris@25:               }
Chris@25:           }
Chris@25:       }
Chris@25: 
Chris@25: 
Chris@25:     if (product_1 % 2 == 1)
Chris@25:       return;
Chris@25: 
Chris@25:     {
Chris@25:       double tw_arg = M_PI / ((double) factor);
Chris@25:       ATOMIC cos_tw_arg = cos (tw_arg);
Chris@25:       ATOMIC sin_tw_arg = -sin (tw_arg);
Chris@25: 
Chris@25:       for (k1 = 0; k1 < q; k1++)
Chris@25:         {
Chris@25:           ATOMIC dw_real = 1.0, dw_imag = 0.0;
Chris@25: 
Chris@25:           for (e1 = 0; e1 < factor; e1++)
Chris@25:             {
Chris@25:               ATOMIC z_real, z_imag;
Chris@25: 
Chris@25:               ATOMIC sum_real = 0.0;
Chris@25:               ATOMIC sum_imag = 0.0;
Chris@25: 
Chris@25:               ATOMIC w_real = 1.0, w_imag = 0.0;
Chris@25:               ATOMIC tw_real = 1.0, tw_imag = 0.0;
Chris@25: 
Chris@25:               if (e1 > 0)
Chris@25:                 {
Chris@25:                   ATOMIC t_real = dw_real * cos_d_theta + dw_imag * sin_d_theta;
Chris@25:                   ATOMIC t_imag = -dw_real * sin_d_theta + dw_imag * cos_d_theta;
Chris@25:                   dw_real = t_real;
Chris@25:                   dw_imag = t_imag;
Chris@25:                 }
Chris@25: 
Chris@25:               for (e2 = 0; e2 < factor; e2++)
Chris@25:                 {
Chris@25: 
Chris@25:                   if (e2 > 0)
Chris@25:                     {
Chris@25:                       ATOMIC tmp_real = tw_real * cos_tw_arg - tw_imag * sin_tw_arg;
Chris@25:                       ATOMIC tmp_imag = tw_real * sin_tw_arg + tw_imag * cos_tw_arg;
Chris@25:                       tw_real = tmp_real;
Chris@25:                       tw_imag = tmp_imag;
Chris@25:                     }
Chris@25: 
Chris@25:                   if (e2 > 0)
Chris@25:                     {
Chris@25:                       ATOMIC tmp_real = dw_real * w_real - dw_imag * w_imag;
Chris@25:                       ATOMIC tmp_imag = dw_real * w_imag + dw_imag * w_real;
Chris@25:                       w_real = tmp_real;
Chris@25:                       w_imag = tmp_imag;
Chris@25:                     }
Chris@25: 
Chris@25: 
Chris@25:                   {
Chris@25:                     const size_t from0 = k1 * product_1 + 2 * k + e2 * m - 1;
Chris@25:                     const ATOMIC f0_real = VECTOR(in,istride,from0);
Chris@25:                     z_real = tw_real * f0_real;
Chris@25:                     z_imag = tw_imag * f0_real;
Chris@25:                   }
Chris@25: 
Chris@25:                   sum_real += w_real * z_real - w_imag * z_imag;
Chris@25:                   sum_imag += w_real * z_imag + w_imag * z_real;
Chris@25:                 }
Chris@25: 
Chris@25:               if (e1 + 1 < factor - e1)
Chris@25:                 {
Chris@25:                   const size_t to0 = k1 * product - 1 + 2 * e1 * product_1 + 2 * k;
Chris@25:                   VECTOR(out,ostride,to0) = sum_real;
Chris@25:                   VECTOR(out,ostride,to0 + 1) = sum_imag;
Chris@25:                 }
Chris@25:               else if (e1 + 1 == factor - e1)
Chris@25:                 {
Chris@25:                   const size_t to0 = k1 * product - 1 + 2 * e1 * product_1 + 2 * k;
Chris@25:                   VECTOR(out,ostride,to0) = sum_real;
Chris@25:                 }
Chris@25:               else
Chris@25:                 {
Chris@25:                   const size_t to0 = k1 * product - 1 + 2 * (factor - e1) * product_1 - 2 * k;
Chris@25:                   VECTOR(out,ostride,to0) = sum_real;
Chris@25:                   VECTOR(out,ostride,to0 + 1) = -sum_imag;
Chris@25:                 }
Chris@25: 
Chris@25:             }
Chris@25:         }
Chris@25:     }
Chris@25:     return;
Chris@25: 	
Chris@25: 	function backwardButterfly2(output, outputOffset, outputStride, input, inputOffset, inputStride, product, n, twiddle, fStride) {
Chris@25: 		var m = n / 2, q = n / product, old = product / 2
Chris@25: 		
Chris@25: 		for (var i = 0; i < q; i++) {
Chris@25: 			var a0 = (2 * i) * q
Chris@25: 			var a1 = (2 * i + 2) * q - 1
Chris@25: 			
Chris@25: 			var s0 = input[inputOffset + inputStride * a0]
Chris@25: 			var s1 = input[inputOffset + inputStride * a1]
Chris@25: 			
Chris@25: 			var r0 = s0 + s1
Chris@25: 			var r1 = s0 - s1
Chris@25: 			
Chris@25: 			var a0 = q * i
Chris@25: 			var a1 = q * i + m
Chris@25: 			
Chris@25: 			output[outputOffset + outputStride * a0] = r0
Chris@25: 			output[outputOffset + outputStride * a1] = r1
Chris@25: 		}
Chris@25: 		
Chris@25: 		if (q == 1) { return }
Chris@25: 		
Chris@25: 		for (var i = 0; i < q / 2; i++) {
Chris@25: 			<%= load('t1', 'twiddle', -1, 'i') %>
Chris@25: 			
Chris@25: 			for (var j = 0; j < old; j++) {
Chris@25: 				var a0 = 2 * j * q + 2 * i - 1
Chris@25: 				var a1 = 2 * (j + 1) * q - 2 * i - 1
Chris@25: 				
Chris@25: 				<%= load('s0', 'input', 'inputOffset', 'a0', 'inputStride') %>
Chris@25: 				<%= load('s1', 'input', 'inputOffset', 'a1', 'inputStride') %>
Chris@25: 				
Chris@25: 				var r0_r = s0_r + s1_r
Chris@25: 				var r0_i = s0_i - s1_i
Chris@25: 				
Chris@25: 				var v1_r = s0_r - s1_r
Chris@25: 				var v1_i = s0_i + s1_i
Chris@25: 				
Chris@25: 				<%= cmul('r1', 'v1', 't1') %>
Chris@25: 				
Chris@25: 				var a0 = j * q + 2 * i - 1
Chris@25: 				var a1 = a0 + m
Chris@25: 				
Chris@25: 				<%= store('r0', 'output', 'outputOffset', 'a0', 'outputStride') %>
Chris@25: 				<%= store('r1', 'output', 'outputOffset', 'a1', 'outputStride') %>
Chris@25: 			}
Chris@25: 		}
Chris@25: 		
Chris@25: 		if (q % 2 == 1) { return }
Chris@25: 		
Chris@25: 		for (var i = 0; i < q; i++) {
Chris@25: 			var a0 = 2 * (i + 1) * q - 1
Chris@25: 			
Chris@25: 			<%= load('r0', 'input', 'inputOffset', 'a0', 'inputStride') %>
Chris@25: 			
Chris@25: 			<%= real('input', 'inputOffset', 'a0', 'inputStride') %> =  2 * r0_r
Chris@25: 			<%= imag('input', 'inputOffset', 'a1', 'inputStride') %> = -2 * r0_i
Chris@25: 		}
Chris@25: 	}
Chris@25: 	
Chris@25: 	function work(output, outputOffset, outputStride, f, fOffset, fStride, inputStride, factors, state) {
Chris@25: 		var p = factors.shift()
Chris@25: 		var m = factors.shift()
Chris@25: 		
Chris@25: 		if (m == 1) {
Chris@25: 			for (var i = 0; i < p * m; i++) {
Chris@25: 				<%= load('x0', 'f', 'fOffset', 'i', 'fStride * inputStride') %>
Chris@25: 				<%= store('x0', 'output', 'outputOffset', 'i', 'outputStride') %>
Chris@25: 			}
Chris@25: 		} else {
Chris@25: 			for (var i = 0; i < p; i++) {
Chris@25: 				work(output, outputOffset + outputStride * i * m, outputStride, f, fOffset + i * fStride * inputStride, fStride * p, inputStride, factors.slice(), state)
Chris@25: 			}
Chris@25: 		}
Chris@25: 		
Chris@25: 		switch (p) {
Chris@25: 			case 2: butterfly2(output, outputOffset, outputStride, fStride, state, m); break
Chris@25: 			case 3: butterfly3(output, outputOffset, outputStride, fStride, state, m); break
Chris@25: 			case 4: butterfly4(output, outputOffset, outputStride, fStride, state, m); break
Chris@25: 			default: butterfly(output, outputOffset, outputStride, fStride, state, m, p); break
Chris@25: 		}
Chris@25: 	}
Chris@25: 	
Chris@25: 	var real = function (n, inverse) {
Chris@25: 		var n = ~~n, inverse = !!inverse
Chris@25: 		
Chris@25: 		if (n < 1) {
Chris@25: 			throw new RangeError("n is outside range, should be positive integer, was `" + n + "'")
Chris@25: 		}
Chris@25: 		
Chris@25: 		var state = {
Chris@25: 			n: n,
Chris@25: 			inverse: inverse,
Chris@25: 			
Chris@25: 			factors: [],
Chris@25: 			twiddle: [],
Chris@25: 			scratch: new Float64Array(n)
Chris@25: 		}
Chris@25: 		
Chris@25: 		var t = new Float64Array(n)
Chris@25: 		
Chris@25: 		var p = 4, v = Math.floor(Math.sqrt(n))
Chris@25: 		
Chris@25: 		while (n > 1) {
Chris@25: 			while (n % p) {
Chris@25: 				switch (p) {
Chris@25: 					case 4: p = 2; break
Chris@25: 					case 2: p = 3; break
Chris@25: 					default: p += 2; break
Chris@25: 				}
Chris@25: 				
Chris@25: 				if (p > v) {
Chris@25: 					p = n
Chris@25: 				}
Chris@25: 			}
Chris@25: 			
Chris@25: 			n /= p
Chris@25: 			
Chris@25: 			state.factors.push(p)
Chris@25: 		}
Chris@25: 		
Chris@25: 		var theta = 2 * Math.PI / n, product = 1, twiddle = new Float64Array(n)
Chris@25: 			
Chris@25: 		for (var i = 0, t = 0; i < state.factors.length; i++) {
Chris@25: 			var phase = theta * i, factor = state.factors[i]
Chris@25: 			
Chris@25: 			var old = product, product = product * factor, q = n / product
Chris@25: 			
Chris@25: 			state.twiddle.push(new Float64Array(twiddle, t))
Chris@25: 			
Chris@25: 			if (inverse) {
Chris@25: 				var counter = q, multiplier = old
Chris@25: 			} else {
Chris@25: 				var counter = old, multiplier = q
Chris@25: 			}
Chris@25: 			
Chris@25: 			for (var j = 1; j < factor; j++) {
Chris@25: 				var m = 0
Chris@25: 					
Chris@25: 				for (var k = 1; k < counter / 2; k++, t++) {
Chris@25: 					m = (m + j * multiplier) % n
Chris@25: 						
Chris@25: 					var phase = theta * m
Chris@25: 						
Chris@25: 					<%= real('t', 'i') %> = Math.cos(phase)
Chris@25: 					<%= imag('t', 'i') %> = Math.sin(phase)
Chris@25: 				}
Chris@25: 			}
Chris@25: 		}
Chris@25: 		
Chris@25: 		this.state = state
Chris@25: 	}
Chris@25: 	
Chris@25: 	real.prototype.process = function(output, outputStride, input, inputStride) {
Chris@25: 		var outputStride = ~~outputStride, inputStride = ~~inputStride
Chris@25: 		
Chris@25: 		if (outputStride < 1) {
Chris@25: 			throw new RangeError("outputStride is outside range, should be positive integer, was `" + outputStride + "'")
Chris@25: 		}
Chris@25: 		
Chris@25: 		if (inputStride < 1) {
Chris@25: 			throw new RangeError("inputStride is outside range, should be positive integer, was `" + inputStride + "'")
Chris@25: 		}
Chris@25: 		
Chris@25: 		var product = 1, state = 0, inverse = this.state.inverse
Chris@25: 		
Chris@25: 		var n = this.state.n, factors = this.state.factors
Chris@25: 		var twiddle = this.state.twiddle, scratch = this.state.scratch
Chris@25: 		
Chris@25: 		for (var i = 0; i < factors.length; i++) {
Chris@25: 			var factor = factors[i], old = product, product = product * factor
Chris@25: 			
Chris@25: 			var q = n / product, fStride = Math.ceil(old / 2) - 1
Chris@25: 			
Chris@25: 			if (state == 0) {
Chris@25: 				var inBuffer = input, inStride = inputStride
Chris@25: 				
Chris@25: 				if (this.state.factors.length % 2 == 0) {
Chris@25: 					var outBuffer = scratch, outStride = 1, state = 1
Chris@25: 				} else {
Chris@25: 					var outBuffer = output, outStride = outputStride, state = 2
Chris@25: 				}
Chris@25: 			} else if (state == 1) {
Chris@25: 				var inBuffer = scratch, inStride = 1, outBuffer = output, outStride = outputStride, state = 2
Chris@25: 			} else if (state == 2) {
Chris@25: 				var inBuffer = output, inStride = outputStride, outBuffer = scratch, outStride = 1, state = 1
Chris@25: 			} else {
Chris@25: 				throw new RangeError("state somehow is not in the range (0 .. 2)")
Chris@25: 			}
Chris@25: 			
Chris@25: 			if (inverse) {
Chris@25: 				switch (factor) {
Chris@25: 				case 2: backwardButterfly2(outBuffer, 0, outStride, inBuffer, 0, inStride, product, n, twiddle[i], fStride); break
Chris@25: 				case 3: backwardButterfly3(outBuffer, 0, outStride, inBuffer, 0, inStride, product, n, twiddle[i], fStride); break
Chris@25: 				case 4: backwardButterfly3(outBuffer, 0, outStride, inBuffer, 0, inStride, product, n, twiddle[i], fStride); break
Chris@25: 				case 5: backwardButterfly3(outBuffer, 0, outStride, inBuffer, 0, inStride, product, n, twiddle[i], fStride); break
Chris@25: 				default: backwardButterfly(outBuffer, 0, outStride, inBuffer, 0, inStride, product, n, twiddle[i], fStride, factor); break
Chris@25: 				}
Chris@25: 			} else {
Chris@25: 				switch (factor) {
Chris@25: 				case 2: forwardButterfly2(outBuffer, 0, outStride, inBuffer, 0, inStride, product, n, twiddle[i], fStride); break
Chris@25: 				case 3: forwardButterfly3(outBuffer, 0, outStride, inBuffer, 0, inStride, product, n, twiddle[i], fStride); break
Chris@25: 				case 4: forwardButterfly3(outBuffer, 0, outStride, inBuffer, 0, inStride, product, n, twiddle[i], fStride); break
Chris@25: 				case 5: forwardButterfly3(outBuffer, 0, outStride, inBuffer, 0, inStride, product, n, twiddle[i], fStride); break
Chris@25: 				default: forwardButterfly(outBuffer, 0, outStride, inBuffer, 0, inStride, product, n, twiddle[i], fStride, factor); break
Chris@25: 				}
Chris@25: 			}
Chris@25: 		}
Chris@25: 	}
Chris@25: 	
Chris@25: 	namespace.real = real
Chris@25: }(FFT)