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 butterfly2(output, outputOffset, outputStride, fStride, state, m) {
Chris@25: 		var t = state.twiddle
Chris@25: 		
Chris@25: 		for (var i = 0; i < m; i++) {
Chris@25: 			<%= load('s0', 'output', 'outputOffset', 'i', 'outputStride') %>
Chris@25: 			<%= load('s1', 'output', 'outputOffset', 'i + m', 'outputStride') %>
Chris@25: 			
Chris@25: 			<%= load('t1', 't', 0, 'i', 'fStride') %>
Chris@25: 			
Chris@25: 			<%= cmul('v1', 's1', 't1') %>
Chris@25: 			
Chris@25: 			<%= cadd('r0', 's0', 'v1') %>
Chris@25: 			<%= csub('r1', 's0', 'v1') %>
Chris@25: 			
Chris@25: 			<%= store('r0', 'output', 'outputOffset', 'i', 'outputStride') %>
Chris@25: 			<%= store('r1', 'output', 'outputOffset', 'i + m', 'outputStride') %>
Chris@25: 		}
Chris@25: 	}
Chris@25: 	
Chris@25: 	function butterfly3(output, outputOffset, outputStride, fStride, state, m) {
Chris@25: 		var t = state.twiddle
Chris@25: 		var m1 = m, m2 = 2 * m
Chris@25: 		var fStride1 = fStride, fStride2 = 2 * fStride
Chris@25: 		
Chris@25: 		var e = <%= imag('t', 0, 'm', 'fStride') %>
Chris@25: 		
Chris@25: 		for (var i = 0; i < m; i++) {
Chris@25: 			<%= load('s0', 'output', 'outputOffset', 'i', 'outputStride') %>
Chris@25: 			
Chris@25: 			<%= load('s1', 'output', 'outputOffset', 'i + m1', 'outputStride') %>
Chris@25: 			<%= load('t1', 't', 0, 'i', 'fStride1') %>
Chris@25: 			<%= cmul('v1', 's1', 't1') %>
Chris@25: 			
Chris@25: 			<%= load('s2', 'output', 'outputOffset', 'i + m2', 'outputStride') %>
Chris@25: 			<%= load('t2', 't', 0, 'i', 'fStride2') %>
Chris@25: 			<%= cmul('v2', 's2', 't2') %>
Chris@25: 			
Chris@25: 			<%= cadd('i0', 'v1', 'v2') %>
Chris@25: 			
Chris@25: 			<%= cadd('r0', 's0', 'i0') %>
Chris@25: 			<%= store('r0', 'output', 'outputOffset', 'i', 'outputStride') %>
Chris@25: 			
Chris@25: 			var i1_r = s0_r - i0_r * 0.5
Chris@25: 			var i1_i = s0_i - i0_i * 0.5
Chris@25: 			
Chris@25: 			var i2_r = (v1_r - v2_r) * e
Chris@25: 			var i2_i = (v1_i - v2_i) * e
Chris@25: 			
Chris@25: 			var r1_r = i1_r - i2_i
Chris@25: 			var r1_i = i1_i + i2_r
Chris@25: 			<%= store('r1', 'output', 'outputOffset', 'i + m1', 'outputStride') %>
Chris@25: 			
Chris@25: 			var r2_r = i1_r + i2_i
Chris@25: 			var r2_i = i1_i - i2_r
Chris@25: 			<%= store('r2', 'output', 'outputOffset', 'i + m2', 'outputStride') %>
Chris@25: 		}
Chris@25: 	}
Chris@25: 	
Chris@25: 	function butterfly4(output, outputOffset, outputStride, fStride, state, m) {
Chris@25: 		var t = state.twiddle
Chris@25: 		var m1 = m, m2 = 2 * m, m3 = 3 * m
Chris@25: 		var fStride1 = fStride, fStride2 = 2 * fStride, fStride3 = 3 * fStride
Chris@25: 		
Chris@25: 		for (var i = 0; i < m; i++) {
Chris@25: 			<%= load('s0', 'output', 'outputOffset', 'i', 'outputStride') %>
Chris@25: 			
Chris@25: 			<%= load('s1', 'output', 'outputOffset', 'i + m1', 'outputStride') %>
Chris@25: 			<%= load('t1', 't', 0, 'i', 'fStride1') %>
Chris@25: 			<%= cmul('v1', 's1', 't1') %>
Chris@25: 			
Chris@25: 			<%= load('s2', 'output', 'outputOffset', 'i + m2', 'outputStride') %>
Chris@25: 			<%= load('t2', 't', 0, 'i', 'fStride2') %>
Chris@25: 			<%= cmul('v2', 's2', 't2') %>
Chris@25: 			
Chris@25: 			<%= load('s3', 'output', 'outputOffset', 'i + m3', 'outputStride') %>
Chris@25: 			<%= load('t3', 't', 0, 'i', 'fStride3') %>
Chris@25: 			<%= cmul('v3', 's3', 't3') %>
Chris@25: 			
Chris@25: 			<%= cadd('i0', 's0', 'v2') %>
Chris@25: 			<%= csub('i1', 's0', 'v2') %>
Chris@25: 			<%= cadd('i2', 'v1', 'v3') %>
Chris@25: 			<%= csub('i3', 'v1', 'v3') %>
Chris@25: 			
Chris@25: 			<%= cadd('r0', 'i0', 'i2') %>
Chris@25: 			
Chris@25: 			if (state.inverse) {
Chris@25: 				var r1_r = i1_r - i3_i
Chris@25: 				var r1_i = i1_i + i3_r
Chris@25: 			} else {
Chris@25: 				var r1_r = i1_r + i3_i
Chris@25: 				var r1_i = i1_i - i3_r
Chris@25: 			}
Chris@25: 			
Chris@25: 			<%= csub('r2', 'i0', 'i2') %>
Chris@25: 			
Chris@25: 			if (state.inverse) {
Chris@25: 				var r3_r = i1_r + i3_i
Chris@25: 				var r3_i = i1_i - i3_r
Chris@25: 			} else {
Chris@25: 				var r3_r = i1_r - i3_i
Chris@25: 				var r3_i = i1_i + i3_r
Chris@25: 			}
Chris@25: 			
Chris@25: 			<%= store('r0', 'output', 'outputOffset', 'i', 'outputStride') %>
Chris@25: 			<%= store('r1', 'output', 'outputOffset', 'i + m1', 'outputStride') %>
Chris@25: 			<%= store('r2', 'output', 'outputOffset', 'i + m2', 'outputStride') %>
Chris@25: 			<%= store('r3', 'output', 'outputOffset', 'i + m3', 'outputStride') %>
Chris@25: 		}
Chris@25: 	}
Chris@25: 	
Chris@25: 	function butterfly(output, outputOffset, outputStride, fStride, state, m, p) {
Chris@25: 		var t = state.twiddle, n = state.n, scratch = new Float64Array(2 * p)
Chris@25: 		
Chris@25: 		for (var u = 0; u < m; u++) {
Chris@25: 			for (var q1 = 0, k = u; q1 < p; q1++, k += m) {
Chris@25: 				<%= load('x0', 'output', 'outputOffset', 'k', 'outputStride') %>
Chris@25: 				<%= store('x0', 'scratch', 'q1') %>
Chris@25: 			}
Chris@25: 			
Chris@25: 			for (var q1 = 0, k = u; q1 < p; q1++, k += m) {
Chris@25: 				var tOffset = 0
Chris@25: 				
Chris@25: 				<%= load('x0', 'scratch', 0) %>
Chris@25: 				<%= store('x0', 'output', 'outputOffset', 'k', 'outputStride') %>
Chris@25: 				
Chris@25: 				for (var q = 1; q < p; q++) {
Chris@25: 					tOffset = (tOffset + fStride * k) % n
Chris@25: 					
Chris@25: 					<%= load('s0', 'output', 'outputOffset', 'k', 'outputStride') %>
Chris@25: 					
Chris@25: 					<%= load('s1', 'scratch', 'q') %>
Chris@25: 					<%= load('t1', 't', 'tOffset') %>
Chris@25: 					<%= cmul('v1', 's1', 't1') %>
Chris@25: 					
Chris@25: 					<%= cadd('r0', 's0', 'v1') %>
Chris@25: 					<%= store('r0', 'output', 'outputOffset', 'k', 'outputStride') %>
Chris@25: 				}
Chris@25: 			}
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 complex = function (n, inverse) {
Chris@25: 		if (arguments.length < 2) {
Chris@25: 			throw new RangeError("You didn't pass enough arguments, passed `" + arguments.length + "'")
Chris@25: 		}
Chris@25: 		
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: new Float64Array(2 * n),
Chris@25: 			scratch: new Float64Array(2 * n)
Chris@25: 		}
Chris@25: 		
Chris@25: 		var t = state.twiddle, theta = 2 * Math.PI / n
Chris@25: 		
Chris@25: 		for (var i = 0; i < n; i++) {
Chris@25: 			if (inverse) {
Chris@25: 				var phase =  theta * i
Chris@25: 			} else {
Chris@25: 				var phase = -theta * i
Chris@25: 			}
Chris@25: 			
Chris@25: 			<%= real('t', 'i') %> = Math.cos(phase)
Chris@25: 			<%= imag('t', 'i') %> = Math.sin(phase)
Chris@25: 		}
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: 			state.factors.push(n)
Chris@25: 		}
Chris@25: 		
Chris@25: 		this.state = state
Chris@25: 	}
Chris@25: 	
Chris@25: 	complex.prototype.simple = function (output, input, t) {
Chris@25: 		this.process(output, 0, 1, input, 0, 1, t)
Chris@25: 	}
Chris@25: 	
Chris@25: 	complex.prototype.process = function(output, outputOffset, outputStride, input, inputOffset, inputStride, t) {
Chris@25: 		var outputStride = ~~outputStride, inputStride = ~~inputStride
Chris@25: 		
Chris@25: 		var type = t == 'real' ? t : 'complex'
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: 		if (type == 'real') {
Chris@25: 			for (var i = 0; i < this.state.n; i++) {
Chris@25: 				var x0_r = input[inputOffset + inputStride * i]
Chris@25: 				var x0_i = 0.0
Chris@25: 				
Chris@25: 				<%= store('x0', 'this.state.scratch', 'i') %>
Chris@25: 			}
Chris@25: 			
Chris@25: 			work(output, outputOffset, outputStride, this.state.scratch, 0, 1, 1, this.state.factors.slice(), this.state)
Chris@25: 		} else {
Chris@25: 			if (input == output) {
Chris@25: 				work(this.state.scratch, 0, 1, input, inputOffset, 1, inputStride, this.state.factors.slice(), this.state)
Chris@25: 				
Chris@25: 				for (var i = 0; i < this.state.n; i++) {
Chris@25: 					<%= load('x0', 'this.state.scratch', 'i') %>
Chris@25: 					
Chris@25: 					<%= store('x0', 'output', 'outputOffset', 'i', 'outputStride') %>
Chris@25: 				}
Chris@25: 			} else {
Chris@25: 				work(output, outputOffset, outputStride, input, inputOffset, 1, inputStride, this.state.factors.slice(), this.state)
Chris@25: 			}
Chris@25: 		}
Chris@25: 	}
Chris@25: 	
Chris@25: 	namespace.complex = complex
Chris@25: }(FFT)