1const assert = require("assert");
  2const refBn128 = require("snarkjs").bn128;
  3const refBigInt = require("snarkjs").bigInt;
  4
  5const buildBn128 = require("../index.js").buildBn128;
  6
  7describe("FFT tests", () => {
  8    it("create a basic FFT", async () => {
  9        const bn128 = await buildBn128();
 10
 11        const N=4;
 12
 13        const p = bn128.alloc(32*N);
 14        for (let i=0; i<N; i++) {
 15            bn128.putInt(p+i*32, i);
 16        }
 17
 18        bn128.fft_toMontgomeryN(p, p, N);
 19        bn128.fft_fft(p, N);
 20        bn128.fft_ifft(p, N);
 21        bn128.fft_fromMontgomeryN(p, p, N);
 22
 23        for (let i=0; i<N; i++) {
 24            const a = bn128.getInt(p+i*32);
 25            assert.equal(a,i);
 26        }
 27    });
 28
 29    it("create a do it reverselly FFT", async () => {
 30        const bn128 = await buildBn128();
 31
 32        const N=1024;
 33
 34        const p = bn128.alloc(32*N);
 35        for (let i=0; i<N; i++) {
 36            bn128.putInt(p+i*32, i);
 37        }
 38
 39        bn128.fft_toMontgomeryN(p, p, N);
 40        bn128.fft_ifft(p, N, 0);
 41        bn128.fft_fft(p, N, 0);
 42        bn128.fft_fromMontgomeryN(p, p, N);
 43
 44        for (let i=0; i<N; i++) {
 45            const a = bn128.getInt(p+i*32);
 46            assert.equal(a,i);
 47        }
 48    });
 49    it("test with zeros", async () => {
 50        const bn128 = await buildBn128();
 51
 52        const N=1024;
 53
 54        const p = bn128.alloc(32*N);
 55        for (let i=0; i<N; i++) {
 56            bn128.putInt(p+i*32, (i%2 == 0)? 0 : 1);
 57        }
 58
 59        bn128.fft_toMontgomeryN(p, p, N);
 60        bn128.fft_ifft(p, N, 0);
 61        bn128.fft_fft(p, N, 0);
 62        bn128.fft_fromMontgomeryN(p, p, N);
 63
 64        for (let i=0; i<N; i++) {
 65            const a = bn128.getInt(p+i*32);
 66            assert.equal(a,(i%2 == 0)? 0 : 1);
 67        }
 68    });
 69    it("test interleaved", async () => {
 70        const bn128 = await buildBn128();
 71
 72        const N=1024;
 73
 74        const p = bn128.alloc(32*N);
 75        const pr1 = bn128.alloc(32*N*2);
 76        const pr2 = bn128.alloc(32*N*2);
 77        for (let i=0; i<N; i++) {
 78            bn128.putInt(p+i*32, i);
 79        }
 80        bn128.fft_toMontgomeryN(p, p, N);
 81        bn128.fft_fft(p, N, 0);
 82        bn128.fft_copyNInterleaved(p, pr1, N);
 83
 84        for (let i=0; i<N; i++) {
 85            bn128.putInt(p+i*32, i);
 86        }
 87        bn128.fft_toMontgomeryN(p, p, N);
 88        bn128.fft_fft(p, N, 1);
 89        bn128.fft_copyNInterleaved(p, pr1+32, N);
 90
 91        bn128.fft_fromMontgomeryN(pr1, pr1, N*2);
 92
 93        for (let i=0; i<N; i++) {
 94            bn128.putInt(pr2+i*32, i);
 95        }
 96        for (let i=N; i<N*2; i++) {
 97            bn128.putInt(pr2+i*32, 0);
 98        }
 99        bn128.fft_toMontgomeryN(pr2, pr2, N*2);
100        bn128.fft_fft(pr2, N*2, 0);
101        bn128.fft_fromMontgomeryN(pr2, pr2, N*2);
102
103        for (let i=0; i<N*2; i++) {
104            const a = bn128.getInt(pr1+i*32, 1);
105            const b = bn128.getInt(pr2+i*32, 1);
106            assert(a.equals(b));
107        }
108
109        bn128.fft_toMontgomeryN(pr1, pr1, N*2);
110        bn128.fft_ifft(pr1, N*2, 0);
111        bn128.fft_fromMontgomeryN(pr1, pr1, N*2);
112        for (let i=0; i<N; i++) {
113            const a = bn128.getInt(pr1+i*32, 1);
114            assert.equal(a,i);
115        }
116        for (let i=N; i<N*2; i++) {
117            const a = bn128.getInt(pr1+i*32, 1);
118            assert.equal(a,0);
119        }
120
121    });
122
123});