+const FFT15_INSWAP: [usize; 20] = [ 0, 5, 10, 42, 3, 8, 13, 42, 6, 11, 1, 42, 9, 14, 4, 42, 12, 2, 7, 42 ];
+const FFT15_OUTSWAP: [usize; 20] = [ 0, 10, 5, 42, 6, 1, 11, 42, 12, 7, 2, 42, 3, 13, 8, 42, 9, 4, 14, 42 ];
+
+impl FFT15 {
+ fn new_data(size: usize, _forward: bool) -> FFTData {
+ FFTData { table: Vec::new(), tmp: Vec::new(), twiddle: Vec::new(), size, step: 0, div: 0 }
+ }
+ fn fft3(dst: &mut [FFTComplex], src: &[FFTComplex], step: usize, n: usize) {
+ let s0 = src[0];
+ let s1 = src[1];
+ let s2 = src[2];
+
+ let t0 = s1 + s2;
+ let t1 = s0 - t0.scale(0.5);
+ let t2 = (s2 - s1).rotate().scale(FFT3_CONST);
+
+ dst[FFT15_OUTSWAP[n * 4 + 0] * step] = s0 + t0;
+ dst[FFT15_OUTSWAP[n * 4 + 1] * step] = t1 + t2;
+ dst[FFT15_OUTSWAP[n * 4 + 2] * step] = t1 - t2;
+ }
+ fn ifft3(dst: &mut [FFTComplex], src: &[FFTComplex], step: usize, n: usize) {
+ let s0 = src[0];
+ let s1 = src[1];
+ let s2 = src[2];
+
+ let t0 = s1 + s2;
+ let t1 = s0 - t0.scale(0.5);
+ let t2 = (s2 - s1).rotate().scale(FFT3_CONST);
+
+ dst[FFT15_OUTSWAP[n * 4 + 0] * step] = s0 + t0;
+ dst[FFT15_OUTSWAP[n * 4 + 1] * step] = t1 - t2;
+ dst[FFT15_OUTSWAP[n * 4 + 2] * step] = t1 + t2;
+ }
+ fn fft5(dst: &mut [FFTComplex], src: &[FFTComplex], step: usize, n: usize) {
+ let s0 = src[FFT15_INSWAP[n + 0 * 4] * step];
+ let s1 = src[FFT15_INSWAP[n + 1 * 4] * step];
+ let s2 = src[FFT15_INSWAP[n + 2 * 4] * step];
+ let s3 = src[FFT15_INSWAP[n + 3 * 4] * step];
+ let s4 = src[FFT15_INSWAP[n + 4 * 4] * step];
+
+ let t0 = s1 + s4;
+ let t1 = s1 - s4;
+ let t2 = s2 + s3;
+ let t3 = s2 - s3;
+ let (t4, t5) = twiddle5(t0, t1, FFT5_CONST2);
+ let (t6, t7) = twiddle5(t2, t3, FFT5_CONST1);
+ let (t8, t9) = twiddle5(t0, t1, FFT5_CONST1);
+ let (ta, tb) = twiddle5(t2, t3, FFT5_CONST2);
+
+ dst[0 * 3] = s0 + t0 + t2;
+ dst[1 * 3] = s0 + t5 - t6;
+ dst[2 * 3] = s0 - t8 + ta;
+ dst[3 * 3] = s0 - t9 + tb;
+ dst[4 * 3] = s0 + t4 - t7;
+ }
+ fn ifft5(dst: &mut [FFTComplex], src: &[FFTComplex], step: usize, n: usize) {
+ let s0 = src[FFT15_INSWAP[n + 0 * 4] * step];
+ let s1 = src[FFT15_INSWAP[n + 1 * 4] * step];
+ let s2 = src[FFT15_INSWAP[n + 2 * 4] * step];
+ let s3 = src[FFT15_INSWAP[n + 3 * 4] * step];
+ let s4 = src[FFT15_INSWAP[n + 4 * 4] * step];
+
+ let t0 = s1 + s4;
+ let t1 = s1 - s4;
+ let t2 = s2 + s3;
+ let t3 = s2 - s3;
+ let (t4, t5) = twiddle5(t0, t1, FFT5_CONST2);
+ let (t6, t7) = twiddle5(t2, t3, FFT5_CONST1);
+ let (t8, t9) = twiddle5(t0, t1, FFT5_CONST1);
+ let (ta, tb) = twiddle5(t2, t3, FFT5_CONST2);
+
+ dst[0 * 3] = s0 + t0 + t2;
+ dst[1 * 3] = s0 + t4 - t7;
+ dst[2 * 3] = s0 - t9 + tb;
+ dst[3 * 3] = s0 - t8 + ta;
+ dst[4 * 3] = s0 + t5 - t6;
+ }
+ fn fft(_fftdata: &mut FFTData, data: &mut [FFTComplex], step: usize) {
+ let mut tmp = [FFTC_ZERO; 15];
+ for n in 0..3 {
+ Self::fft5(&mut tmp[n..], data, step, n);
+ }
+ for n in 0..5 {
+ Self::fft3(data, &tmp[n * 3..][..3], step, n);
+ }
+ }
+ fn ifft(_fftdata: &mut FFTData, data: &mut [FFTComplex], step: usize) {
+ let mut tmp = [FFTC_ZERO; 15];
+ for n in 0..3 {
+ Self::ifft5(&mut tmp[n..], data, step, n);
+ }
+ for n in 0..5 {
+ Self::ifft3(data, &tmp[n * 3..][..3], step, n);
+ }
+ }
+}
+
+
+enum FFTMode {
+ Generic(usize),
+ SplitRadix(u8),
+ Prime15,
+}
+
+impl FFTMode {
+ fn permute(&self, perms: &mut [usize]) {
+ match *self {
+ FFTMode::Generic(_) => {},
+ FFTMode::SplitRadix(bits) => {
+ let div = perms.len() >> bits;
+ gen_sr_perms(perms, 1 << bits);
+ if div > 1 {
+ for i in 0..(1 << bits) {
+ perms[i] *= div;
+ }
+ for i in 1..div {
+ for j in 0..(1 << bits) {
+ perms[(i << bits) + j] = perms[j] + i;