Created libnttfft
authorAndreas Steffen <andreas.steffen@strongswan.org>
Sun, 24 Jul 2016 17:57:54 +0000 (19:57 +0200)
committerAndreas Steffen <andreas.steffen@strongswan.org>
Fri, 29 Jul 2016 10:36:15 +0000 (12:36 +0200)
This makes Number Theoretic Transforms (NTT) based on the efficient
Fast-Fourier-Transform (FFT) available to multiple plugins.

26 files changed:
configure.ac
src/libstrongswan/Makefile.am
src/libstrongswan/math/libnttfft/Makefile.am [new file with mode: 0644]
src/libstrongswan/math/libnttfft/ntt_fft.c [new file with mode: 0644]
src/libstrongswan/math/libnttfft/ntt_fft.h [new file with mode: 0644]
src/libstrongswan/math/libnttfft/ntt_fft_params.c [new file with mode: 0644]
src/libstrongswan/math/libnttfft/ntt_fft_params.h [new file with mode: 0644]
src/libstrongswan/math/libnttfft/ntt_fft_reduce.h [new file with mode: 0644]
src/libstrongswan/math/libnttfft/tests/.gitignore [new file with mode: 0644]
src/libstrongswan/math/libnttfft/tests/Makefile.am [new file with mode: 0644]
src/libstrongswan/math/libnttfft/tests/ntt_fft_tests.c [new file with mode: 0644]
src/libstrongswan/math/libnttfft/tests/ntt_fft_tests.h [new file with mode: 0644]
src/libstrongswan/math/libnttfft/tests/suites/test_ntt_fft.c [new file with mode: 0644]
src/libstrongswan/plugins/bliss/Makefile.am
src/libstrongswan/plugins/bliss/bliss_fft.c [deleted file]
src/libstrongswan/plugins/bliss/bliss_fft.h [deleted file]
src/libstrongswan/plugins/bliss/bliss_fft_params.c [deleted file]
src/libstrongswan/plugins/bliss/bliss_fft_params.h [deleted file]
src/libstrongswan/plugins/bliss/bliss_param_set.c
src/libstrongswan/plugins/bliss/bliss_param_set.h
src/libstrongswan/plugins/bliss/bliss_private_key.c
src/libstrongswan/plugins/bliss/bliss_public_key.c
src/libstrongswan/plugins/bliss/bliss_reduce.h [deleted file]
src/libstrongswan/plugins/bliss/tests/Makefile.am
src/libstrongswan/plugins/bliss/tests/bliss_tests.h
src/libstrongswan/plugins/bliss/tests/suites/test_bliss_fft.c [deleted file]

index 875d98a..07f0d5f 100644 (file)
@@ -1630,6 +1630,7 @@ AM_CONDITIONAL(USE_CONFTEST, test x$conftest = xtrue)
 AM_CONDITIONAL(USE_LIBSTRONGSWAN, test x$charon = xtrue -o x$pki = xtrue -o x$scepclient = xtrue -o x$conftest = xtrue -o x$fast = xtrue -o x$imcv = xtrue -o x$nm = xtrue -o x$tkm = xtrue -o x$cmd = xtrue -o x$tls = xtrue -o x$tnc_tnccs = xtrue -o x$aikgen = xtrue -o x$aikpub2 = xtrue -o x$svc = xtrue -o x$systemd = xtrue)
 AM_CONDITIONAL(USE_LIBCHARON, test x$charon = xtrue -o x$conftest = xtrue -o x$nm = xtrue -o x$tkm = xtrue -o x$cmd = xtrue -o x$svc = xtrue -o x$systemd = xtrue)
 AM_CONDITIONAL(USE_LIBIPSEC, test x$libipsec = xtrue)
+AM_CONDITIONAL(USE_LIBNTTFFT, test x$bliss = xtrue)
 AM_CONDITIONAL(USE_LIBTNCIF, test x$tnc_tnccs = xtrue -o x$imcv = xtrue)
 AM_CONDITIONAL(USE_LIBTNCCS, test x$tnc_tnccs = xtrue)
 AM_CONDITIONAL(USE_LIBPTTLS, test x$tnc_tnccs = xtrue)
@@ -1722,6 +1723,8 @@ AC_CONFIG_FILES([
        src/Makefile
        src/include/Makefile
        src/libstrongswan/Makefile
+       src/libstrongswan/math/libnttfft/Makefile
+       src/libstrongswan/math/libnttfft/tests/Makefile
        src/libstrongswan/plugins/aes/Makefile
        src/libstrongswan/plugins/cmac/Makefile
        src/libstrongswan/plugins/des/Makefile
index 965bf7a..4546878 100644 (file)
@@ -221,16 +221,22 @@ $(srcdir)/crypto/proposal/proposal_keywords_static.c:     $(srcdir)/crypto/proposal/
                $(GPERF) -N proposal_get_token_static -m 10 -C -G -c -t -D < \
                                                                                                $(srcdir)/crypto/proposal/proposal_keywords_static.txt > $@
 
-
-# build plugins with their own Makefile
-#######################################
-
 if MONOLITHIC
 SUBDIRS =
 else
 SUBDIRS = .
 endif
 
+# build libnttfft used by some plugins
+######################################
+
+if USE_LIBNTTFFT
+  SUBDIRS += math/libnttfft
+endif
+
+# build plugins with their own Makefile
+#######################################
+
 if USE_AF_ALG
   SUBDIRS += plugins/af_alg
 if MONOLITHIC
@@ -605,7 +611,16 @@ endif
 if MONOLITHIC
   SUBDIRS += .
 endif
+
+# build unit tests
+##################
+
 SUBDIRS += tests
+
+if USE_LIBNTTFFT
+  SUBDIRS += math/libnttfft/tests
+endif
+
 if USE_BLISS
   SUBDIRS += plugins/bliss/tests
 endif
diff --git a/src/libstrongswan/math/libnttfft/Makefile.am b/src/libstrongswan/math/libnttfft/Makefile.am
new file mode 100644 (file)
index 0000000..ec98abe
--- /dev/null
@@ -0,0 +1,15 @@
+AM_CPPFLAGS = \
+       -I$(top_srcdir)/src/libstrongswan
+
+AM_CFLAGS = \
+       @COVERAGE_CFLAGS@
+
+AM_LDFLAGS = \
+       -no-undefined
+
+ipseclib_LTLIBRARIES = libnttfft.la
+
+libnttfft_la_SOURCES = \
+       ntt_fft_reduce.h ntt_fft.h ntt_fft.c \
+       ntt_fft_params.h ntt_fft_params.c
+
diff --git a/src/libstrongswan/math/libnttfft/ntt_fft.c b/src/libstrongswan/math/libnttfft/ntt_fft.c
new file mode 100644 (file)
index 0000000..d742c0a
--- /dev/null
@@ -0,0 +1,199 @@
+/*
+ * Copyright (C) 2014-2016 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program 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 General Public License
+ * for more details.
+ */
+
+#include "ntt_fft.h"
+#include "ntt_fft_reduce.h"
+
+typedef struct private_ntt_fft_t private_ntt_fft_t;
+
+/**
+ * Private data structure for ntt_fft_t object
+ */
+struct private_ntt_fft_t {
+
+       /**
+        * Public interface.
+        */
+       ntt_fft_t public;
+
+       /**
+        * FFT parameter set used as constants
+        */
+       ntt_fft_params_t *p;
+
+};
+
+METHOD(ntt_fft_t, get_size, uint16_t,
+       private_ntt_fft_t *this)
+{
+       return this->p->n;
+}
+
+METHOD(ntt_fft_t, get_modulus, uint16_t,
+       private_ntt_fft_t *this)
+{
+       return this->p->q;
+}
+
+/**
+ * Do an FFT butterfly operation
+ *
+ * x[i1] ---|+|------- x[i1]
+ *        \/
+ *        /\    w[iw]  
+ * x[i2] ---|-|--|*|-- x[i2]
+ *
+ */
+static void butterfly(private_ntt_fft_t *this, uint32_t *x, int i1,int i2, int iw)
+{
+       uint32_t xp, xm;
+
+       xp = x[i1] + x[i2];
+       xm = x[i1] + (this->p->q - x[i2]);
+       if (xp >= this->p->q)
+       {
+               xp -= this->p->q;
+       }
+       x[i1] = xp;
+       x[i2] = ntt_fft_mreduce(xm * this->p->wr[iw], this->p);
+}
+
+/**
+ * Trivial butterfly operation of last FFT stage
+ */
+static void butterfly_last(private_ntt_fft_t *this, uint32_t *x, int i1)
+{
+       uint32_t xp, xm;
+       int i2 = i1 + 1;
+
+       xp = x[i1] + x[i2];
+       xm = x[i1] + (this->p->q - x[i2]);
+       if (xp >= this->p->q)
+       {
+               xp -= this->p->q;
+       }
+       if (xm >= this->p->q)
+       {
+               xm -= this->p->q;
+       }
+       x[i1] = xp;
+       x[i2] = xm;
+}
+
+METHOD(ntt_fft_t, transform, void,
+       private_ntt_fft_t *this, uint32_t *a, uint32_t *b, bool inverse)
+{
+       int stage, i, j, k, m, n, s, t, iw, i_rev;
+       uint32_t tmp;
+
+       /* we are going to use the transform size n a lot */
+       n = this->p->n;
+       s = this->p->s;
+
+       if (!inverse)
+       {
+               /* apply linear phase needed for negative wrapped convolution */
+               for (i = 0; i < n; i++)
+               {
+                       b[i] = ntt_fft_mreduce(a[i] * this->p->wf[s*i], this->p);
+               }
+       }
+       else if (a != b)
+       {
+               /* copy if input and output array are not the same */
+               for (i = 0; i < n; i++)
+               {
+                       b[i] = a[i];
+               }
+       }
+
+       m = n;
+       k = 1;
+
+       for (stage = this->p->stages; stage > 0; stage--)
+       {
+               m >>= 1;
+               t = 0;
+
+               for (j = 0; j < k; j++)
+               {
+                       if (stage == 1)
+                       {
+                               butterfly_last(this, b, t);
+                       }
+                       else
+                       {
+                               for (i = 0; i < m; i++)
+                               {
+                                       iw = s * (inverse ? (n - i * k) : (i * k));
+                                       butterfly(this, b, t + i, t + i + m, iw);
+                               }                               
+                       }
+                       t += 2*m;
+               }
+               k <<= 1;
+       }
+
+       /* Sort output in bit-reverse order */
+       for (i = 0; i < n; i++)
+       {
+               i_rev = this->p->rev[i];
+
+               if (i_rev > i)
+               {
+                       tmp = b[i];
+                       b[i] = b[i_rev];
+                       b[i_rev] = tmp;
+               }
+       }
+
+       /**
+        * Compensate the linear phase needed for negative wrapped convolution
+        * and normalize the output array with 1/n mod q after the inverse FFT. 
+        */
+       if (inverse)
+       {
+               for (i = 0; i < n; i++)
+               {
+                       b[i] = ntt_fft_mreduce(b[i] * this->p->wi[i], this->p);
+               }
+       }
+}
+
+METHOD(ntt_fft_t, destroy, void,
+       private_ntt_fft_t *this)
+{
+       free(this);
+}
+
+/**
+ * See header.
+ */
+ntt_fft_t *ntt_fft_create(ntt_fft_params_t *params)
+{
+       private_ntt_fft_t *this;
+
+       INIT(this,
+               .public = {
+                       .get_size = _get_size,
+                       .get_modulus = _get_modulus,
+                       .transform = _transform,
+                       .destroy = _destroy,
+               },
+               .p = params,
+       );
+
+       return &this->public;
+}
diff --git a/src/libstrongswan/math/libnttfft/ntt_fft.h b/src/libstrongswan/math/libnttfft/ntt_fft.h
new file mode 100644 (file)
index 0000000..0054a6c
--- /dev/null
@@ -0,0 +1,71 @@
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program 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 General Public License
+ * for more details.
+ */
+
+/**
+ * @defgroup ntt_fft ntt_fft
+ * @{ @ingroup bliss_p
+ */
+
+#ifndef NTT_FFT_H_
+#define NTT_FFT_H_
+
+#include "ntt_fft_params.h"
+
+#include <library.h>
+
+typedef struct ntt_fft_t ntt_fft_t;
+
+/**
+ * Implements a Number Theoretic Transform (NTT) via the FFT algorithm
+ */
+struct ntt_fft_t {
+
+       /**
+        * Get the size of the Number Theoretic Transform
+        *
+        * @result                      Transform size
+        */
+       uint16_t (*get_size)(ntt_fft_t *this);
+
+       /**
+        * Get the prime modulus of the Number Theoretic Transform
+        *
+        * @result                      Prime modulus
+        */
+       uint16_t (*get_modulus)(ntt_fft_t *this);
+
+       /**
+        * Compute the [inverse] NTT of a polynomial
+        *
+        * @param a                     Coefficient of input polynomial
+        * @param b                     Coefficient of output polynomial
+        * @param inverse       TRUE if the inverse NTT has to be computed
+        */
+       void (*transform)(ntt_fft_t *this, uint32_t *a, uint32_t *b, bool inverse);
+
+       /**
+        * Destroy ntt_fft_t object
+        */
+       void (*destroy)(ntt_fft_t *this);
+};
+
+/**
+ * Create a ntt_fft_t object for a given FFT parameter set
+ *
+ * @param params               FFT parameters
+ */
+ntt_fft_t *ntt_fft_create(ntt_fft_params_t *params);
+
+#endif /** NTT_FFT_H_ @}*/
diff --git a/src/libstrongswan/math/libnttfft/ntt_fft_params.c b/src/libstrongswan/math/libnttfft/ntt_fft_params.c
new file mode 100644 (file)
index 0000000..33e78c5
--- /dev/null
@@ -0,0 +1,652 @@
+/*
+ * Copyright (C) 2014-2016 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program 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 General Public License
+ * for more details.
+ */
+
+#include "ntt_fft_params.h"
+
+/**
+ * FFT twiddle factors in Montgomery form for q = 12289 and n = 1024
+ */
+static uint16_t wr_12289_1024[] = {
+        4075,  3051,  2031,  1207,  9987, 10092,  2948,  9273, 11973,  9094,
+        3202,  9430,  7377,  5092,  3728, 10626,  4536,  1062,  2882,  6039,
+         975, 10908,  6065,  2249, 11889,  4978, 10431,  7270, 12138,  4890,
+        6119,  4895,  6364,  4611,  4737, 10911,  6212,  9452,  8455,  8758,
+       11316,  1479, 11026, 11847,  2920,  7901,  6190,  8374,  4789,  1170,
+        8174,  7278,   241, 11809,  1058,  2686,  8724,  9650,  5868,  4885,
+        5874,  5179,  7991, 10600,  3262,    81,  3969, 10146,  5594,  3748,
+       11606,  3400,  6843,  3504, 11939,  7428,  7591,  3289,  1404,  7351,
+        3818,  2747, 11713,  8643,  5681,  8011, 11580,  2126,  5862,  4591,
+        3757, 12047,   431,  8830,  2555,  2305,  2344,  4255, 11871,  4096,
+
+        4080,  3296,  1747, 11869,  3998, 11567,  1489, 11516, 11279, 11955,
+        8212,  9140,  5456,  9275, 12071,  1607,  5009, 11950,  7967,  9424,
+        7083,  2975, 10596,  3066,  2766,   355,  5106,  4414,  7373,  4896,
+        6413,  7012, 11785, 12171,  6507, 11618,  3988, 11077,  2057,  2481,
+       10968,  9005, 11130,  4654,  6844,  3553,  2051,  2187,  8851,  3584,
+        3570,  2884,  6137,  5777,   426,  8585,  2839,  3932,  8333,  2780,
+        1041,  1853,  4774,   435,  9026, 12159,  5919,  7384,  5435,  8246,
+       10806,  1067,  3127,  5755, 11637,  4919,  7540,   790,  1843,  4284,
+        1003, 12280, 11848,  2969, 10302,   949,  9634,  5084,  3336,  3707,
+        9597,  3271,   522,  1000, 12133,  4645,  6403,  6522,    64,  3136,
+
+        6196,  8668,  6906,  6591,  3445,  9048,   948,  9585,  2683,  8577,
+        2447,  9302,  1105,  4989, 10970,  9103,  3643,  6461,  9364,  4143,
+        6383,  5542,  1200,  9644,  5574,  2768,   453,  9908,  6221,  9893,
+        5486, 10745, 10367,  4134,  5942,  8511, 11502, 10593,  2919,  7852,
+        3789,  1326,  3529,   875,  6008, 11745, 10211,  8779,    56,  2744,
+       11566,  1440,  9115,  4231, 10695,  7917,  6974,  9923,  6956,  9041,
+         605,  5067,  2503, 12046,   382,  6429,  7796,  1045,  2049,  2089,
+        4049,  1777,  1050,  2294,  1805,  2422,  8077,  2525,   835,  4048,
+        1728, 10938,  7535,   545,  2127,  5911,  6992, 10805,  1018,   726,
+       10996, 10377,  4624,  5374,  5257, 11813,  1254,     1,    49,  2401,
+
+        7048,  1260,   295,  2166,  7822,  2319,  3030,  1002, 12231,  9447,
+        8210,  9042,   654,  7468,  9551,  1017,   677,  8595,  3329,  3364,
+        5079,  3091,  3991, 11224,  9260, 11336,  2459,  9890,  5339,  3542,
+        1512,   354,  5057,  2013,   325,  3636,  6118,  4846,  3963,  9852,
+        3477, 10616,  4046,  1630,  6136,  5728, 10314,  1537,  1579,  3637,
+        6167,  7247, 11011, 11112,  3772,   493, 11868,  3949,  9166,  6730,
+       10256, 10984,  9789,   390,  6821,  2426,  8273, 12129,  4449,  9088,
+        2908,  7313,  1956,  9821,  1958,  9919,  6760, 11726,  9280,    27,
+        1323,  3382,  5961,  9442,  7965,  9326,  2281,  1168,  8076,  2476,
+       10723,  9289,   468, 10643,  5369,  5012, 12097,  2881,  5990, 10863,
+
+        3860,  4805,  1954,  9723,  9445,  8112,  4240, 11136,  4948,  8961,
+        8974,  9611,  3957,  9558,  1360,  5195,  8775, 12149,  5429,  7952,
+        8689,  7935,  7856,  3985, 10930,  7143,  5915,  7188,  8120,  4632,
+        5766, 12176,  6752, 11334,  2361,  5088,  3532,  1022,   922,  8311,
+        1702,  9664,  6554,  1632,  6234, 10530, 12121,  4057,  2169,  7969,
+        9522, 11885,  4782,   827,  3656,  7098,  3710,  9744, 10474,  9377,
+        4780,   729, 11143,  5291,  1190,  9154,  6142,  6022,   142,  6958,
+        9139,  5407,  6874,  5023,   347,  4714,  9784,   145,  7105,  4053,
+        1973, 10654,  5908,  6845,  3602,  4452,  9235, 10111,  3879,  5736,
+       10706,  8456,  8807,  1428,  8527, 12286, 12142,  5086,  3434,  8509,
+
+       11404,  5791,  1112,  5332,  3199,  9283,   174,  8526, 12237,  9741,
+       10327,  2174,  8214,  9238, 10258, 11082,  2302,  2197,  9341,  3016,
+         316,  3195,  9087,  2859,  4912,  7197,  8561,  1663,  7753, 11227,
+        9407,  6250, 11314,  1381,  6224, 10040,   400,  7311,  1858,  5019,
+         151,  7399,  6170,  7394,  5925,  7678,  7552,  1378,  6077,  2837,
+        3834,  3531,   973, 10810,  1263,   442,  9369,  4388,  6099,  3915,
+        7500, 11119,  4115,  5011, 12048,   480, 11231,  9603,  3565,  2639,
+        6421,  7404,  6415,  7110,  4298,  1689,  9027, 12208,  8320,  2143,
+        6695,  8541,   683,  8889,  5446,  8785,   350,  4861,  4698,  9000,
+       10885,  4938,  8471,  9542,   576,  3646,  6608,  4278,   709, 10163,
+
+        6427,  7698,  8532,   242, 11858,  3459,  9734,  9984,  9945,  8034,
+         418,  8193,  8209,  8993, 10542,   420,  8291,   722, 10800,   773,
+        1010,   334,  4077,  3149,  6833,  3014,   218, 10682,  7280,   339,
+        4322,  2865,  5206,  9314,  1693,  9223,  9523, 11934,  7183,  7875,
+        4916,  7393,  5876,  5277,   504,   118,  5782,   671,  8301,  1212,
+       10232,  9808,  1321,  3284,  1159,  7635,  5445,  8736, 10238, 10102,
+        3438,  8705,  8719,  9405,  6152,  6512, 11863,  3704,  9450,  8357,
+        3956,  9509, 11248, 10436,  7515, 11854,  3263,   130,  6370,  4905,
+        6854,  4043,  1483, 11222,  9162,  6534,   652,  7370,  4749, 11499,
+       10446,  8005, 11286,     9,   441,  9320,  1987, 11340,  2655,  7205,
+
+        8953,  8582,  2692,  9018, 11767, 11289,   156,  7644,  5886,  5767,
+       12225,  9153,  6093,  3621,  5383,  5698,  8844,  3241, 11341,  2704,
+        9606,  3712,  9842,  2987, 11184,  7300,  1319,  3186,  8646,  5828,
+        2925,  8146,  5906,  6747, 11089,  2645,  6715,  9521, 11836,  2381,
+        6068,  2396,  6803,  1544,  1922,  8155,  6347,  3778,   787,  1696,
+        9370,  4437,  8500, 10963,  8760, 11414,  6281,   544,  2078,  3510,
+       12233,  9545,   723, 10849,  3174,  8058,  1594,  4372,  5315,  2366,
+        5333,  3248, 11684,  7222,  9786,   243, 11907,  5860,  4493, 11244,
+       10240, 10200,  8240, 10512, 11239,  9995, 10484,  9867,  4212,  9764,
+       11454,  8241, 10561,  1351,  4754, 11744, 10162,  6378,  5297,  1484,
+
+       11271, 11563,  1293,  1912,  7665,  6915,  7032,   476, 11035, 12288,
+       12240,  9888,  5241, 11029, 11994, 10123,  4467,  9970,  9259, 11287,
+          58,  2842,  4079,  3247, 11635,  4821,  2738, 11272, 11612,  3694,
+        8960,  8925,  7210,  9198,  8298,  1065,  3029,   953,  9830,  2399,
+        6950,  8747, 10777, 11935,  7232, 10276, 11964,  8653,  6171,  7443,
+        8326,  2437,  8812,  1673,  8243, 10659,  6153,  6561,  1975, 10752,
+       10710,  8652,  6122,  5042,  1278,  1177,  8517, 11796,   421,  8340,
+        3123,  5559,  2033,  1305,  2500, 11899,  5468,  9863,  4016,   160,
+        7840,  3201,  9381,  4976, 10333,  2468, 10331,  2370,  5529,   563,
+        3009, 12262, 10966,  8907,  6328,  2847,  4324,  2963, 10008, 11121,
+
+        4213,  9813,  1566,  3000, 11821,  1646,  6920,  7277,   192,  9408,
+        6299,  1426,  8429,  7484, 10335,  2566,  2844,  4177,  8049,  1153,
+        7341,  3328,  3315,  2678,  8332,  2731, 10929,  7094,  3514,   140,
+        6860,  4337,  3600,  4354,  4433,  8304,  1359,  5146,  6374,  5101,
+        4169,  7657,  6523,   113,  5537,   955,  9928,  7201,  8757, 11267,
+       11367,  3978, 10587,  2625,  5735, 10657,  6055,  1759,   168,  8232,
+       10120,  4320,  2767,   404,  7507, 11462,  8633,  5191,  8579,  2545,
+        1815,  2912,  7509, 11560,  1146,  6998, 11099,  3135,  6147,  6267,
+       12147,  5331,  3150,  6882,  5415,  7266, 11942,  7575,  2505, 12144,
+        5184,  8236, 10316,  1635,  6381,  5444,  8687,  7837,  3054,  2178,
+
+        8410,  6553,  1583,  3833,  3482, 10861,  3762,     3,   147,  7203,
+        8855,  3780,   885,  6498, 11177,  6957,  9090,  3006, 12115,  3763,
+          52,  2548,  1962, 10115,  4075
+};
+
+/**
+ * FFT phase shift in forward transform for q = 12289 and n = 1024
+ */
+static uint16_t wf_12289_1024[] = {
+        3186, 10013,  8646, 11366,  5828,  3929,  2925,  8186,  8146,  7866,
+        5906,  4475,  6747, 10362, 11089,  3889,  2645,  6226,  6715, 10138,
+        9521,  5202, 11836,  9118,  2381,  4378,  6068,  5609,  2396,  4483,
+        6803, 10754,  1544, 10808,  1922,  1165,  8155,  7929,  6347,  7562,
+        3778,  1868,   787,  5509,  1696, 11872,  9370,  4145,  4437,  6481,
+        8500, 10344, 10963,  3007,  8760, 12164, 11414,  6164,  6281,  7100,
+         544,  3808,  2078,  2257,  3510, 12281, 12233, 11897,  9545,  5370,
+         723,  5061, 10849,  2209,  3174,  9929,  8058,  7250,  1594, 11158,
+        4372,  6026,  5315,   338,  2366,  4273,  5333,   464,  3248, 10447,
+       11684,  8054,  7222,  1398,  9786,  7057,   243,  1701, 11907,  9615,
+
+        5860,  4153,  4493,  6873, 11244,  4974, 10240, 10235, 10200,  9955,
+        8240,  8524, 10512, 12139, 11239,  4939,  9995,  8520, 10484, 11943,
+        9867,  7624,  4212,  4906,  9764,  6903, 11454,  6444,  8241,  8531,
+       10561,   193,  1351,  9457,  4754,  8700, 11744,  8474, 10162,  9689,
+        6378,  7779,  5297,   212,  1484, 10388, 11271,  5163, 11563,  7207,
+        1293,  9051,  1912,  1095,  7665,  4499,  6915, 11538,  7032,    68,
+         476,  3332, 11035,  3511, 12288, 12282, 12240, 11946,  9888,  7771,
+        5241, 12109, 11029,  3469, 11994, 10224, 10123,  9416,  4467,  6691,
+        9970,  8345,  9259,  3368, 11287,  5275,    58,   406,  2842,  7605,
+        4079,  3975,  3247, 10440, 11635,  7711,  4821,  9169,  2738,  6877,
+
+       11272,  5170, 11612,  7550,  3694,  1280,  8960,  1275,  8925,  1030,
+        7210,  1314,  9198,  2941,  8298,  8930,  1065,  7455,  3029,  8914,
+         953,  6671,  9830,  7365,  2399,  4504,  6950, 11783,  8747, 12073,
+       10777,  1705, 11935,  9811,  7232,  1468, 10276, 10487, 11964, 10014,
+        8653, 11415,  6171,  6330,  7443,  2945,  8326,  9126,  2437,  4770,
+        8812,   239,  1673, 11711,  8243,  8545, 10659,   879,  6153,  6204,
+        6561,  9060,  1975,  1536, 10752,  1530, 10710,  1236,  8652, 11408,
+        6122,  5987,  5042, 10716,  1278,  8946,  1177,  8239,  8517, 10463,
+       11796,  8838,   421,  2947,  8340,  9224,  3123,  9572,  5559,  2046,
+        2033,  1942,  1305,  9135,  2500,  5211, 11899,  9559,  5468,  1409,
+
+        9863,  7596,  4016,  3534,   160,  1120,  7840,  5724,  3201, 10118,
+        9381,  4222,  4976, 10254, 10333, 10886,  2468,  4987, 10331, 10872,
+        2370,  4301,  5529,  1836,   563,  3941,  3009,  8774, 12262, 12100,
+       10966,  3028,  8907,   904,  6328,  7429,  2847,  7640,  4324,  5690,
+        2963,  8452, 10008,  8611, 11121,  4113,  4213,  4913,  9813,  7246,
+        1566, 10962,  3000,  8711, 11821,  9013,  1646, 11522,  6920, 11573,
+        7277,  1783,   192,  1344,  9408,  4411,  6299,  7226,  1426,  9982,
+        8429,  9847,  7484,  3232, 10335, 10900,  2566,  5673,  2844,  7619,
+        4177,  4661,  8049,  7187,  1153,  8071,  7341,  2231,  3328, 11007,
+        3315, 10916,  2678,  6457,  8332,  9168,  2731,  6828, 10929,  2769,
+
+        7094,   502,  3514,    20,   140,   980,  6860, 11153,  4337,  5781,
+        3600,   622,  4354,  5900,  4433,  6453,  8304,  8972,  1359,  9513,
+        5146, 11444,  6374,  7751,  5101, 11129,  4169,  4605,  7657,  4443,
+        6523,  8794,   113,   791,  5537,  1892,   955,  6685,  9928,  8051,
+        7201,  1251,  8757, 12143, 11267,  5135, 11367,  5835,  3978,  3268,
+       10587,   375,  2625,  6086,  5735,  3278, 10657,   865,  6055,  5518,
+        1759,    24,   168,  1176,  8232,  8468, 10120,  9395,  4320,  5662,
+        2767,  7080,   404,  2828,  7507,  3393, 11462,  6500,  8633, 11275,
+        5191, 11759,  8579, 10897,  2545,  5526,  1815,   416,  2912,  8095,
+        7509,  3407, 11560,  7186,  1146,  8022,  6998, 12119, 11099,  3959,
+
+        3135,  9656,  6147,  6162,  6267,  7002, 12147, 11295,  5331,   450,
+        3150,  9761,  6882, 11307,  5415,  1038,  7266,  1706, 11942,  9860,
+        7575,  3869,  2505,  5246, 12144, 11274,  5184, 11710,  8236,  8496,
+       10316, 10767,  1635, 11445,  6381,  7800,  5444,  1241,  8687, 11653,
+        7837,  5703,  3054,  9089,  2178,  2957,  8410,  9714,  6553,  9004,
+        1583, 11081,  3833,  2253,  3482, 12085, 10861,  2293,  3762,  1756,
+           3,    21,   147,  1029,  7203,  1265,  8855,   540,  3780,  1882,
+         885,  6195,  6498,  8619, 11177,  4505,  6957, 11832,  9090,  2185,
+        3006,  8753, 12115, 11071,  3763,  1763,    52,   364,  2548,  5547,
+        1962,  1445, 10115,  9360,  4075,  3947,  3051,  9068,  2031,  1928,
+
+        1207,  8449,  9987,  8464, 10092,  9199,  2948,  8347,  9273,  3466,
+       11973, 10077,  9094,  2213,  3202, 10125,  9430,  4565,  7377,  2483,
+        5092, 11066,  3728,  1518, 10626,   648,  4536,  7174,  1062,  7434,
+        2882,  7885,  6039,  5406,   975,  6825, 10908,  2622,  6065,  5588,
+        2249,  3454, 11889,  9489,  4978, 10268, 10431, 11572,  7270,  1734,
+       12138, 11232,  4890,  9652,  6119,  5966,  4895,  9687,  6364,  7681,
+        4611,  7699,  4737,  8581, 10911,  2643,  6212,  6617,  9452,  4719,
+        8455, 10029,  8758, 12150, 11316,  5478,  1479, 10353, 11026,  3448,
+       11847,  9195,  2920,  8151,  7901,  6151,  6190,  6463,  8374,  9462,
+        4789,  8945,  1170,  8190,  8174,  8062,  7278,  1790,   241,  1687,
+
+       11809,  8929,  1058,  7406,  2686,  6513,  8724, 11912,  9650,  6105,
+        5868,  4209,  4885,  9617,  5874,  4251,  5179, 11675,  7991,  6781,
+       10600,   466,  3262, 10545,    81,   567,  3969,  3205, 10146,  9577,
+        5594,  2291,  3748,  1658, 11606,  7508,  3400, 11511,  6843, 11034,
+        3504, 12239, 11939,  9839,  7428,  2840,  7591,  3981,  3289, 10734,
+        1404,  9828,  7351,  2301,  3818,  2148,  2747,  6940, 11713,  8257,
+        8643, 11345,  5681,  2900,  8011,  6921, 11580,  7326,  2126,  2593,
+        5862,  4167,  4591,  7559,  3757,  1721, 12047, 10595,   431,  3017,
+        8830,   365,  2555,  5596,  2305,  3846,  2344,  4119,  4255,  5207,
+       11871,  9363,  4096,  4094,  4080,  3982,  3296, 10783,  1747, 12229,
+
+       11869,  9349,  3998,  3408, 11567,  7235,  1489, 10423, 11516,  6878,
+       11279,  5219, 11955,  9951,  8212,  8328,  9140,  2535,  5456,  1325,
+        9275,  3480, 12071, 10763,  1607, 11249,  5009, 10485, 11950,  9916,
+        7967,  6613,  9424,  4523,  7083,   425,  2975,  8536, 10596,   438,
+        3066,  9173,  2766,  7073,   355,  2485,  5106, 11164,  4414,  6320,
+        7373,  2455,  4896,  9694,  6413,  8024,  7012, 12217, 11785,  8761,
+       12171, 11463,  6507,  8682, 11618,  7592,  3988,  3338, 11077,  3805,
+        2057,  2110,  2481,  5078, 10968,  3042,  9005,  1590, 11130,  4176,
+        4654,  8000,  6844, 11041,  3553,   293,  2051,  2068,  2187,  3020,
+        8851,   512,  3584,   510,  3570,   412,  2884,  7899,  6137,  6092,
+
+        5777,  3572,   426,  2982,  8585, 10939,  2839,  7584,  3932,  2946,
+        8333,  9175,  2780,  7171,  1041,  7287,  1853,   682,  4774,  8840,
+         435,  3045,  9026,  1737, 12159, 11379,  5919,  4566,  7384,  2532,
+        5435,  1178,  8246,  8566, 10806,  1908,  1067,  7469,  3127,  9600,
+        5755,  3418, 11637,  7725,  4919,  9855,  7540,  3624,   790,  5530,
+        1843,   612,  4284,  5410,  1003,  7021, 12280, 12226, 11848,  9202,
+        2969,  8494, 10302, 10669,   949,  6643,  9634,  5993,  5084, 11010,
+        3336, 11063,  3707,  1371,  9597,  5734,  3271, 10608,   522,  3654,
+        1000,  7000, 12133, 11197,  4645,  7937,  6403,  7954,  6522,  8787,
+          64,   448,  3136,  9663,  6196,  6505,  8668, 11520,  6906, 11475,
+
+        6591,  9270,  3445, 11826,  9048,  1891,   948,  6636,  9585,  5650,
+        2683,  6492,  8577, 10883,  2447,  4840,  9302,  3669,  1105,  7735,
+        4989, 10345, 10970,  3056
+};
+
+/**
+ * FFT phase shift and scaling inverse transform for q = 12289 and n = 1024
+ */
+static uint16_t wi_12289_1024[] = {
+       12277,  5265,  9530,  3117,  5712,   816, 10650,  3277,  9246,  4832,
+        5957,   851, 10655, 10300,  3227,   461,  3577,   511,    73,  1766,
+        5519,  2544,  2119,  7325,  2802,  5667, 11343,  3376,  5749,  6088,
+        7892,  2883,  3923,  2316,  3842,  4060,   580,  3594,  2269,  9102,
+        6567,  9716,  1388,  5465,  7803,  8137,  2918,  3928,  9339, 10112,
+       11978, 10489,  3254,  3976,   568,  8859, 11799, 12219, 12279, 10532,
+       12038,  8742,  4760,   680,  8875,  4779,  7705,  8123,  2916, 10950,
+        6831,  4487,   641, 10625,  5029,  2474,  2109,  5568,  2551,  2120,
+        3814,  4056,  2335, 10867,  3308, 11006,  6839,   977, 10673,  8547,
+        1221,  1930,  7298, 11576,  8676,  2995,  3939,  7585, 11617, 12193,
+
+        5253,  2506,   358,  8829,  6528, 11466,  1638,   234,  1789, 10789,
+        6808, 11506,  8666,  1238,  3688,  4038,  4088,   584,  1839,  7285,
+        8063,  4663,  9444, 10127,  8469,  4721,  2430,  9125, 11837,  1691,
+       10775,  6806,  6239,  6158,  7902,  4640,  4174,  5863, 11371,  3380,
+        3994, 11104,  6853,   979,  3651, 11055,  6846,   978,  7162,  9801,
+       10178,  1454,  7230,  4544,  9427,  8369, 11729, 12209, 10522, 10281,
+        8491,  1213,  5440,  9555,  1365,   195,  3539, 11039,  1577,  5492,
+       11318,  5128, 11266,  3365,  7503,  4583,  7677,  8119,  4671,  5934,
+        7870,  6391,   913,  1886,  2025,  5556,  7816, 11650,  6931,  9768,
+        3151,  9228,  6585,  7963, 11671,  6934, 11524,  6913, 11521,  5157,
+
+        7759,  2864,  9187,  3068,  5705,   815,  1872,  2023,   289,  5308,
+        6025,  7883,  9904,  4926,  7726,  8126,  4672,  2423,  9124,  3059,
+         437,  1818,  7282,  6307,   901,  7151, 11555,  8673,  1239,   177,
+        5292,   756,   108,  1771,   253,  8814, 10037,  4945,  2462,  7374,
+        2809,  5668,  7832,  4630,  2417,  5612,  7824,  8140,  4674,  7690,
+       11632,  8684, 11774,  1682,  5507,  7809, 11649, 10442,  8514,  6483,
+        9704,  6653,  2706, 10920,  1560,  3734,  2289,   327,  7069,  4521,
+        4157,  4105,  2342, 10868, 12086, 12260,  3507,   501, 10605,  1515,
+        1972,  7304,  2799,  3911,  7581,  1083,  7177,  6292,  4410,   630,
+          90,  3524,  2259,  7345,  6316,  6169,  6148,  6145,  4389,   627,
+
+       10623, 12051, 12255,  8773,  6520,  2687,  3895,  2312,  5597, 11333,
+        1619,  5498,  2541,   363,  3563,   509,  7095, 11547, 12183,  3496,
+        2255,  9100,  1300,  7208,  8052,  6417,  7939,  9912,  1416,  5469,
+        6048,   864,  1879,  2024,  9067,  6562,  2693,  7407,  9836, 10183,
+        8477,  1211,   173,  7047,  8029,  1147,  3675,   525,    75,  7033,
+        8027,  8169,  1167,  7189,  1027,  7169,  9802,  6667,  2708,  3898,
+        4068,  9359,  1337,   191,  5294,  6023,  2616,  7396, 11590,  8678,
+        8262,  6447,   921, 10665, 12057,  3478,  4008, 11106, 12120,  3487,
+        9276, 10103,  6710, 11492,  8664,  8260,  1180, 10702,  5040,   720,
+        3614,  5783,  9604,  1372,   196,    28,     4, 10534,  5016, 11250,
+
+       10385, 12017,  8739,  3004,  9207,  6582,  6207,  7909,  4641,   663,
+        7117,  8039,  2904,  3926,  4072,  7604,  6353, 11441,  3390,  5751,
+       11355, 10400,  8508,  2971,  2180,  2067,  5562, 11328,  6885, 11517,
+        6912,  2743,  3903, 11091,  3340,  9255, 10100,  4954,  7730,  6371,
+        9688,  1384,  7220,  2787,  9176,  4822,  4200,   600,  7108,  2771,
+        3907,  9336,  8356,  8216,  8196,  4682,  4180,  9375,  6606,  7966,
+        1138, 10696,  1528,  5485, 11317,  8639, 10012,  6697,  7979,  4651,
+        2420,  7368, 11586, 10433,  3246,  7486,  2825, 10937,  3318,   474,
+        7090,  4524,  5913,  7867,  4635,  9440, 11882,  3453,  5760,  4334,
+        9397,  3098, 10976,  1568,   224,    32, 10538,  3261,  3977,  9346,
+
+       10113,  8467, 11743, 12211,  3500,   500,  1827,   261,  5304,  7780,
+        2867, 10943,  6830,  7998, 11676,  1668,  5505,  2542,  9141,  4817,
+        9466,  6619, 11479,  5151,  4247,  7629,  4601,  5924,  6113,  6140,
+        9655,  6646,  2705,  2142,   306,  7066,  2765,   395,  1812,  3770,
+       11072,  8604, 10007, 11963,  1709,  9022,  4800,  7708,  9879,  6678,
+         954,  5403,  4283,  4123,   589,  8862,  1266,  3692,  2283,  9104,
+       11834, 12224,  7013,  4513,  7667,  6362,  4420,  2387,   341,  7071,
+        9788,  6665,  9730,  1390, 10732, 10311,  1473,  1966,  3792,  7564,
+       11614, 10437,  1491,   213,  1786,  9033,  3046,  9213, 10094,  1442,
+         206,  1785,   255,  1792,   256, 10570,  1510,  7238,  1034,  7170,
+
+        6291,  7921, 11665,  3422,  4000,  2327,  2088,  5565,   795, 10647,
+        1521,  5484,  2539,  7385,  1055,  7173,  8047, 11683,  1669,  1994,
+        3796,  5809,  4341,  9398, 11876, 12230, 10525, 12037, 12253,  3506,
+        4012,  9351,  4847,  2448,  7372,  9831,  3160,  2207,  5582,  2553,
+        7387,  6322,  9681,  1383, 10731,  1533,   219,  5298,  4268,  7632,
+        6357,  9686,  8406,  4712,  9451, 10128,  4958,  5975, 11387,  8649,
+       11769,  6948, 11526, 12180,  1740, 10782,  6807,  2728,  7412,  4570,
+        4164,  4106, 11120, 12122,  8754, 11784,  3439,  5758, 11356,  6889,
+        9762, 11928,  1704,  1999, 10819, 12079, 12259,  7018, 11536,  1648,
+        1991,  2040,  2047,  2048, 10826, 12080,  8748,  8272,  8204,  1172,
+
+        1923,  7297,  2798,  7422,  6327,  4415,  7653,  6360, 11442, 12168,
+        7005,  8023,  9924,  8440,  8228,  2931,  7441,  1063,  3663,  5790,
+        9605, 10150,  1450,  8985, 11817, 10466, 10273, 12001,  3470,  7518,
+        1074,  1909,  7295,  9820,  4914,   702,  5367,  7789,  8135,  9940,
+        1420,  3714, 11064, 12114, 12264,  1752,  5517,  9566, 11900,  1700,
+        3754,  5803,   829,  1874,  7290,  2797, 10933,  5073,  7747,  8129,
+        6428,  6185, 11417,  1631,   233,  5300,  9535, 10140, 11982,  8734,
+        8270,  2937, 10953,  8587,  8249,  2934,  9197,  4825,  5956,  4362,
+        9401,  1343,  3703,   529, 10609, 12049,  6988,  6265,   895,  3639,
+        4031,  4087,  4095,   585, 10617,  8539,  4731,  4187,  9376,  3095,
+
+        9220, 10095, 10220,  1460, 10742, 12068,  1724,  5513, 11321,  6884,
+        2739,  5658,  6075,  4379, 11159, 10372,  8504,  4726,  9453,  3106,
+        7466, 11600, 10435,  8513,  9994,  8450,  9985,  3182, 10988,  8592,
+        2983,  9204,  4826,  2445,  5616,  6069,   867,  3635,  5786, 11360,
+        5134,  2489, 10889, 12089,  1727,  7269,  2794,  9177,  1311,  5454,
+        9557,  6632,  2703,  9164, 10087,  1441,  3717,   531,  3587,  2268,
+         324,  5313,   759,  1864,  5533,  2546,  7386,  9833,  8427,  4715,
+       11207,  1601,  7251,  4547, 11183, 12131,  1733, 10781, 10318,  1474,
+       10744,  5046,  4232, 11138, 10369,  6748,   964,  7160,  4534,  7670,
+        8118,  8182,  4680, 11202,  6867,   981,  8918,  1274,   182,    26,
+
+        7026,  8026, 11680, 12202, 10521,  1503,  7237,  4545,  5916,  9623,
+        8397, 11733, 10454,  3249,  9242,  6587,   941,  1890,   270, 10572,
+        6777,  9746,  6659,  6218,  6155,  6146,   878,  1881,  7291, 11575,
+       12187,  1741,  7271,  8061, 11685,  6936,  4502,  9421,  4857,  4205,
+        7623,  1089, 10689,  1527,  8996, 10063, 11971, 10488,  6765,  2722,
+        3900,  9335, 11867,  6962, 11528,  5158,  4248,  4118,  5855,  2592,
+        5637,  6072,  2623,  7397,  8079,  9932,  4930,  5971,   853,  3633,
+         519,  8852, 11798,  3441, 11025,  1575,   225,  8810, 11792, 12218,
+        3501,  9278,  3081,  9218,  4828,  7712,  8124, 11694, 12204,  3499,
+        4011,   573,  3593,  5780,  7848,  9899, 10192,  1456,   208,  7052,
+
+        2763,  7417, 11593, 10434, 12024,  8740, 11782, 10461,  3250,  5731,
+        7841,  9898,  1414,   202,  3540,  7528,  2831,  2160, 10842,  5060,
+        4234,  4116,   588,    84
+};
+
+/**
+ * Bit-reversed indices for n = 1024
+ */
+static uint16_t rev_1024[] = {
+          0,  512,  256,  768,  128,  640,  384,  896,   64,  576,
+        320,  832,  192,  704,  448,  960,   32,  544,  288,  800,
+        160,  672,  416,  928,   96,  608,  352,  864,  224,  736,
+        480,  992,   16,  528,  272,  784,  144,  656,  400,  912,
+         80,  592,  336,  848,  208,  720,  464,  976,   48,  560,
+        304,  816,  176,  688,  432,  944,  112,  624,  368,  880,
+        240,  752,  496, 1008,    8,  520,  264,  776,  136,  648,
+        392,  904,   72,  584,  328,  840,  200,  712,  456,  968,
+         40,  552,  296,  808,  168,  680,  424,  936,  104,  616,
+        360,  872,  232,  744,  488, 1000,   24,  536,  280,  792,
+
+        152,  664,  408,  920,   88,  600,  344,  856,  216,  728,
+        472,  984,   56,  568,  312,  824,  184,  696,  440,  952,
+        120,  632,  376,  888,  248,  760,  504, 1016,    4,  516,
+        260,  772,  132,  644,  388,  900,   68,  580,  324,  836,
+        196,  708,  452,  964,   36,  548,  292,  804,  164,  676,
+        420,  932,  100,  612,  356,  868,  228,  740,  484,  996,
+         20,  532,  276,  788,  148,  660,  404,  916,   84,  596,
+        340,  852,  212,  724,  468,  980,   52,  564,  308,  820,
+        180,  692,  436,  948,  116,  628,  372,  884,  244,  756,
+        500, 1012,   12,  524,  268,  780,  140,  652,  396,  908,
+
+         76,  588,  332,  844,  204,  716,  460,  972,   44,  556,
+        300,  812,  172,  684,  428,  940,  108,  620,  364,  876,
+        236,  748,  492, 1004,   28,  540,  284,  796,  156,  668,
+        412,  924,   92,  604,  348,  860,  220,  732,  476,  988,
+         60,  572,  316,  828,  188,  700,  444,  956,  124,  636,
+        380,  892,  252,  764,  508, 1020,    2,  514,  258,  770,
+        130,  642,  386,  898,   66,  578,  322,  834,  194,  706,
+        450,  962,   34,  546,  290,  802,  162,  674,  418,  930,
+         98,  610,  354,  866,  226,  738,  482,  994,   18,  530,
+        274,  786,  146,  658,  402,  914,   82,  594,  338,  850,
+
+        210,  722,  466,  978,   50,  562,  306,  818,  178,  690,
+        434,  946,  114,  626,  370,  882,  242,  754,  498, 1010,
+         10,  522,  266,  778,  138,  650,  394,  906,   74,  586,
+        330,  842,  202,  714,  458,  970,   42,  554,  298,  810,
+        170,  682,  426,  938,  106,  618,  362,  874,  234,  746,
+        490, 1002,   26,  538,  282,  794,  154,  666,  410,  922,
+         90,  602,  346,  858,  218,  730,  474,  986,   58,  570,
+        314,  826,  186,  698,  442,  954,  122,  634,  378,  890,
+        250,  762,  506, 1018,    6,  518,  262,  774,  134,  646,
+        390,  902,   70,  582,  326,  838,  198,  710,  454,  966,
+
+         38,  550,  294,  806,  166,  678,  422,  934,  102,  614,
+        358,  870,  230,  742,  486,  998,   22,  534,  278,  790,
+        150,  662,  406,  918,   86,  598,  342,  854,  214,  726,
+        470,  982,   54,  566,  310,  822,  182,  694,  438,  950,
+        118,  630,  374,  886,  246,  758,  502, 1014,   14,  526,
+        270,  782,  142,  654,  398,  910,   78,  590,  334,  846,
+        206,  718,  462,  974,   46,  558,  302,  814,  174,  686,
+        430,  942,  110,  622,  366,  878,  238,  750,  494, 1006,
+         30,  542,  286,  798,  158,  670,  414,  926,   94,  606,
+        350,  862,  222,  734,  478,  990,   62,  574,  318,  830,
+
+        190,  702,  446,  958,  126,  638,  382,  894,  254,  766,
+        510, 1022,    1,  513,  257,  769,  129,  641,  385,  897,
+         65,  577,  321,  833,  193,  705,  449,  961,   33,  545,
+        289,  801,  161,  673,  417,  929,   97,  609,  353,  865,
+        225,  737,  481,  993,   17,  529,  273,  785,  145,  657,
+        401,  913,   81,  593,  337,  849,  209,  721,  465,  977,
+         49,  561,  305,  817,  177,  689,  433,  945,  113,  625,
+        369,  881,  241,  753,  497, 1009,    9,  521,  265,  777,
+        137,  649,  393,  905,   73,  585,  329,  841,  201,  713,
+        457,  969,   41,  553,  297,  809,  169,  681,  425,  937,
+
+        105,  617,  361,  873,  233,  745,  489, 1001,   25,  537,
+        281,  793,  153,  665,  409,  921,   89,  601,  345,  857,
+        217,  729,  473,  985,   57,  569,  313,  825,  185,  697,
+        441,  953,  121,  633,  377,  889,  249,  761,  505, 1017,
+          5,  517,  261,  773,  133,  645,  389,  901,   69,  581,
+        325,  837,  197,  709,  453,  965,   37,  549,  293,  805,
+        165,  677,  421,  933,  101,  613,  357,  869,  229,  741,
+        485,  997,   21,  533,  277,  789,  149,  661,  405,  917,
+         85,  597,  341,  853,  213,  725,  469,  981,   53,  565,
+        309,  821,  181,  693,  437,  949,  117,  629,  373,  885,
+
+        245,  757,  501, 1013,   13,  525,  269,  781,  141,  653,
+        397,  909,   77,  589,  333,  845,  205,  717,  461,  973,
+         45,  557,  301,  813,  173,  685,  429,  941,  109,  621,
+        365,  877,  237,  749,  493, 1005,   29,  541,  285,  797,
+        157,  669,  413,  925,   93,  605,  349,  861,  221,  733,
+        477,  989,   61,  573,  317,  829,  189,  701,  445,  957,
+        125,  637,  381,  893,  253,  765,  509, 1021,    3,  515,
+        259,  771,  131,  643,  387,  899,   67,  579,  323,  835,
+        195,  707,  451,  963,   35,  547,  291,  803,  163,  675,
+        419,  931,   99,  611,  355,  867,  227,  739,  483,  995,
+
+         19,  531,  275,  787,  147,  659,  403,  915,   83,  595,
+        339,  851,  211,  723,  467,  979,   51,  563,  307,  819,
+        179,  691,  435,  947,  115,  627,  371,  883,  243,  755,
+        499, 1011,   11,  523,  267,  779,  139,  651,  395,  907,
+         75,  587,  331,  843,  203,  715,  459,  971,   43,  555,
+        299,  811,  171,  683,  427,  939,  107,  619,  363,  875,
+        235,  747,  491, 1003,   27,  539,  283,  795,  155,  667,
+        411,  923,   91,  603,  347,  859,  219,  731,  475,  987,
+         59,  571,  315,  827,  187,  699,  443,  955,  123,  635,
+        379,  891,  251,  763,  507, 1019,    7,  519,  263,  775,
+
+        135,  647,  391,  903,   71,  583,  327,  839,  199,  711,
+        455,  967,   39,  551,  295,  807,  167,  679,  423,  935,
+        103,  615,  359,  871,  231,  743,  487,  999,   23,  535,
+        279,  791,  151,  663,  407,  919,   87,  599,  343,  855,
+        215,  727,  471,  983,   55,  567,  311,  823,  183,  695,
+        439,  951,  119,  631,  375,  887,  247,  759,  503, 1015,
+         15,  527,  271,  783,  143,  655,  399,  911,   79,  591,
+        335,  847,  207,  719,  463,  975,   47,  559,  303,  815,
+        175,  687,  431,  943,  111,  623,  367,  879,  239,  751,
+        495, 1007,   31,  543,  287,  799,  159,  671,  415,  927,
+
+         95,  607,  351,  863,  223,  735,  479,  991,   63,  575,
+        319,  831,  191,  703,  447,  959,  127,  639,  383,  895,
+        255,  767,  511, 1023
+};
+
+ntt_fft_params_t ntt_fft_12289_1024 = {
+       12289, 12287, 18, 3186, (1<<18)-1, 1024, 12277, 10,
+       wr_12289_1024, wf_12289_1024, wi_12289_1024, 1, rev_1024
+};
+
+/**
+ * FFT phase shift and scaling inverse transform for q = 12289 and n = 512
+ */
+static uint16_t wi_12289_512[] = {
+       12265,  6771, 11424,  9011,  6203, 11914,  9021,  6454,  7154,   146,
+       11038,  4238,  5604, 10397, 11498,  3495,  7846,  7684,  1160,  4538,
+         845,  2776,  3317,  5836,  6389, 11667,  6508,  1136, 11309, 12269,
+       11787,  9520,  5461,  3121,  5832,  1373,  1282, 10058,  4218,  5102,
+        7628,  4670,  6616,  1389,  9057,  2442,  2307,  5063,  7878, 10945,
+       10506,   716,   767,  3276,  3578,  1327,  5043,  7376,  8176,  3678,
+        3837,  6599,  4649,  4860, 11385,  9261,   189,  3515,  8348, 10453,
+        7988,  1417,  7302,  1403,  2035,  8067,  2171,  6565, 11169,  8755,
+        4693, 10880,  2730,  7078,  3154, 10347, 10243,  2717,  3065,  9342,
+        3451,  1826,  4050,  3343,  1573,  6302,   881, 11053, 10759, 10753,
+
+        3229,  6085, 11410,  3744,   578, 12050,  7519,  3163,  9344,  5959,
+         874,  2275,  1802, 10821,  2478, 10584,   216,   506,  7785,  4924,
+        5618,  3375,  4834,  3359,  9348, 10975, 11259, 11014, 11009,  4739,
+        7119,  5412,  3120,  4578,  1849,  8314,  4684, 11883,  7014,  8921,
+        3944,  5598,  2873,  2065,  8820,   180,  4518,   343,     7,  8778,
+        8957, 12221,   751,  7790, 11194,  3238,  5082,  7126,  1901, 12077,
+        4510,  2600,  3815,  3589,  2832, 12096,  3758,  5845,  5386,  7383,
+        4665,   346,  3769,  7350,   150,  3765,  2334,  2054,  7315,  5416,
+        8136,  2674, 10588,  5232, 10891,  4235,  1842, 11825,  8016, 11951,
+        6263,  1131,  5039,  2360, 10080,  7228,  6919,   392,     8, 10032,
+
+        8481,  5189,  6125,   125,  9282,  1945,  5808,  8144,   417,  6780,
+       10421,  4727,  4360, 11124,  1481,  1535,  7806,  6680,  7911,  3171,
+        7087,  2151,  6063,  8400,  1927,  7814,  4423,  4103,  8360,   923,
+        2276,  3056, 10345,  7735,  3669,  4840, 10883,  6492,  5650,  6636,
+        1891, 11826,  9270, 11475, 11520,  6505,  9663,   448,  8787,  7954,
+        7937, 11197,  7000,  3654, 10608,  5734,  1371, 11063, 11010,  5993,
+        6643, 10669,  8494,  9202, 12226,  7021,  5410,   612,  5530,  3624,
+        9855,  7725,  3418,  9600,  7469,  1908,  8566,  1178,  2532,  4566,
+       11379,  1737,  3045,  8840,   682,  7287,  7171,  9175,  2946,  7584,
+       10939,  2982,  3572,  6092,  7899,   412,   510,   512,  3020,  2068,
+
+         293, 11041,  8000,  4176,  1590,  3042,  5078,  2110,  3805,  3338,
+        7592,  8682, 11463,  8761, 12217,  8024,  9694,  2455,  6320, 11164,
+        2485,  7073,  9173,   438,  8536,   425,  4523,  6613,  9916, 10485,
+       11249, 10763,  3480,  1325,  2535,  8328,  9951,  5219,  6878, 10423,
+        7235,  3408,  9349, 12229, 10783,  3982,  4094,  9363,  5207,  4119,
+        3846,  5596,   365,  3017, 10595,  1721,  7559,  4167,  2593,  7326,
+        6921,  2900, 11345,  8257,  6940,  2148,  2301,  9828, 10734,  3981,
+        2840,  9839, 12239, 11034, 11511,  7508,  1658,  2291,  9577,  3205,
+         567, 10545,   466,  6781, 11675,  4251,  9617,  4209,  6105, 11912,
+        6513,  7406,  8929,  1687,  1790,  8062,  8190,  8945,  9462,  6463,
+
+        6151,  8151,  9195,  3448, 10353,  5478, 12150, 10029,  4719,  6617,
+        2643,  8581,  7699,  7681,  9687,  5966,  9652, 11232,  1734, 11572,
+       10268,  9489,  3454,  5588,  2622,  6825,  5406,  7885,  7434,  7174,
+         648,  1518, 11066,  2483,  4565, 10125,  2213, 10077,  3466,  8347,
+        9199,  8464,  8449,  1928,  9068,  3947,  9360,  1445,  5547,   364,
+        1763, 11071,  8753,  2185, 11832,  4505,  8619,  6195,  1882,   540,
+        1265,  1029,    21,  1756,  2293, 12085,  2253, 11081,  9004,  9714,
+        2957,  9089,  5703, 11653,  1241,  7800, 11445, 10767,  8496, 11710,
+       11274,  5246,  3869,  9860,  1706,  1038, 11307,  9761,   450, 11295,
+        7002,  6162,  9656,  3959, 12119,  8022,  7186,  3407,  8095,   416,
+
+        5526, 10897, 11759, 11275,  6500,  3393,  2828,  7080,  5662,  9395,
+        8468,  1176
+};
+
+/**
+ * Bit-reversed indices for n = 512
+ */
+static uint16_t rev_512[] = {
+         0, 256, 128, 384,  64, 320, 192, 448,  32, 288, 
+       160, 416,  96, 352, 224, 480,  16, 272, 144, 400,
+        80, 336, 208, 464,  48, 304, 176, 432, 112, 368,
+       240, 496,   8, 264, 136, 392,  72, 328, 200, 456,
+        40, 296, 168, 424, 104, 360, 232, 488,  24, 280,
+       152, 408,  88, 344, 216, 472,  56, 312, 184, 440,
+       120, 376, 248, 504,   4, 260, 132, 388,  68, 324,
+       196, 452,  36, 292, 164, 420, 100, 356, 228, 484,
+        20, 276, 148, 404,  84, 340, 212, 468,  52, 308,
+       180, 436, 116, 372, 244, 500,  12, 268, 140, 396,
+
+        76, 332, 204, 460,  44, 300, 172, 428, 108, 364,
+       236, 492,  28, 284, 156, 412,  92, 348, 220, 476,
+        60, 316, 188, 444, 124, 380, 252, 508,   2, 258,
+       130, 386,  66, 322, 194, 450,  34, 290, 162, 418,
+        98, 354, 226, 482,  18, 274, 146, 402,  82, 338,
+       210, 466,  50, 306, 178, 434, 114, 370, 242, 498,
+        10, 266, 138, 394,  74, 330, 202, 458,  42, 298,
+       170, 426, 106, 362, 234, 490,  26, 282, 154, 410,
+        90, 346, 218, 474,  58, 314, 186, 442, 122, 378,
+       250, 506,   6, 262, 134, 390,  70, 326, 198, 454,
+
+        38, 294, 166, 422, 102, 358, 230, 486,  22, 278,
+       150, 406,  86, 342, 214, 470,  54, 310, 182, 438,
+       118, 374, 246, 502,  14, 270, 142, 398,  78, 334,
+       206, 462,  46, 302, 174, 430, 110, 366, 238, 494,
+        30, 286, 158, 414,  94, 350, 222, 478,  62, 318,
+       190, 446, 126, 382, 254, 510,   1, 257, 129, 385,
+        65, 321, 193, 449,  33, 289, 161, 417,  97, 353,
+       225, 481,  17, 273, 145, 401,  81, 337, 209, 465,
+        49, 305, 177, 433, 113, 369, 241, 497,   9, 265,
+       137, 393,  73, 329, 201, 457,  41, 297, 169, 425,
+
+       105, 361, 233, 489,  25, 281, 153, 409,  89, 345,
+       217, 473,  57, 313, 185, 441, 121, 377, 249, 505,
+         5, 261, 133, 389,  69, 325, 197, 453,  37, 293,
+       165, 421, 101, 357, 229, 485,  21, 277, 149, 405,
+        85, 341, 213, 469,  53, 309, 181, 437, 117, 373,
+       245, 501,  13, 269, 141, 397,  77, 333, 205, 461,
+        45, 301, 173, 429, 109, 365, 237, 493,  29, 285,
+       157, 413,  93, 349, 221, 477,  61, 317, 189, 445,
+       125, 381, 253, 509,   3, 259, 131, 387,  67, 323,
+       195, 451,  35, 291, 163, 419,  99, 355, 227, 483,
+
+        19, 275, 147, 403,  83, 339, 211, 467,  51, 307,
+       179, 435, 115, 371, 243, 499,  11, 267, 139, 395,
+        75, 331, 203, 459,  43, 299, 171, 427, 107, 363,
+       235, 491,  27, 283, 155, 411,  91, 347, 219, 475,
+        59, 315, 187, 443, 123, 379, 251, 507,   7, 263,
+       135, 391,  71, 327, 199, 455,  39, 295, 167, 423,
+       103, 359, 231, 487,  23, 279, 151, 407,  87, 343,
+       215, 471,  55, 311, 183, 439, 119, 375, 247, 503,
+        15, 271, 143, 399,  79, 335, 207, 463,  47, 303,
+       175, 431, 111, 367, 239, 495,  31, 287, 159, 415,
+
+        95, 351, 223, 479,  63, 319, 191, 447, 127, 383,
+       255, 511
+};
+
+ntt_fft_params_t ntt_fft_12289_512 = {
+       12289, 12287, 18, 3186, (1<<18)-1, 512, 12265, 9,
+       wr_12289_1024, wf_12289_1024, wi_12289_512, 2, rev_512
+};
+
+/**
+ * FFT twiddle factors in Montgomery form for q = 17 and n = 8
+ */
+static uint16_t wr_17_8[] = { 15, 16, 8, 4, 2, 1, 9, 13, 15 };
+
+/**
+ * FFT phase shift in forward transform for q = 17 and n = 8
+ */
+static uint16_t wf_17_8[] = { 4, 12, 2, 6, 1, 3, 9, 10 };
+
+/**
+ * FFT phase shift and scaling inverse transform for q = 17 and n = 8
+ */
+static uint16_t wi_17_8[] = { 15, 5, 13, 10, 9, 3, 1, 6 };
+
+/**
+ * Bit-reversed indices for n = 8
+ */
+static uint16_t rev_8[] = { 0, 4, 2, 6, 1, 5, 3, 7 };
+
+ntt_fft_params_t ntt_fft_17_8 = {
+       17, 15, 5, 4, (1<<5)-1, 8, 15, 3, wr_17_8, wf_17_8, wi_17_8, 1, rev_8
+};
diff --git a/src/libstrongswan/math/libnttfft/ntt_fft_params.h b/src/libstrongswan/math/libnttfft/ntt_fft_params.h
new file mode 100644 (file)
index 0000000..1fefac4
--- /dev/null
@@ -0,0 +1,115 @@
+/*
+ * Copyright (C) 2014-2016 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program 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 General Public License
+ * for more details.
+ */
+
+/**
+ * @defgroup ntt_fft_params ntt_fft_params
+ * @{ @ingroup ntt_p
+ */
+
+#ifndef NTT_FFT_PARAMS_H_
+#define NTT_FFT_PARAMS_H_
+
+#include <library.h>
+
+typedef struct ntt_fft_params_t ntt_fft_params_t;
+
+/**
+ * Defines the parameters for an NTT computed via the FFT algorithm
+ */
+struct ntt_fft_params_t {
+
+       /**
+        * Prime modulus
+        */
+       uint16_t q;
+
+       /**
+        * Inverse of Prime modulus (-q_inv * q mod r = 1)
+        */
+       uint16_t q_inv;
+
+       /**
+        * Logarithm of Montgomery radix: log2(r)
+        */
+       uint16_t rlog;
+
+       /**
+        * Square of Montgomery radix: r^2 mod q
+        */
+       uint32_t r2;
+
+       /**
+        * Montgomery radix mask: (1<<rlog) - 1
+        */
+       uint32_t rmask;
+
+       /**
+        * Size of the FFT with the condition k * n = q-1
+        */
+       uint16_t n;
+
+       /**
+        * Inverse of n mod q used for normalization of the FFT
+        */
+       uint16_t n_inv;
+
+       /**
+        * Number of FFT stages  stages = log2(n)
+        */
+       uint16_t stages;
+
+       /**
+        * FFT twiddle factors (n-th roots of unity) in Montgomery form
+        */
+       uint16_t *wr;
+
+       /**
+        * FFT phase shift (2n-th roots of unity) in forward transform
+        */
+       uint16_t *wf;
+
+       /**
+        * FFT phase shift (2n-th roots of unity) and scaling in inverse transform
+        */
+       uint16_t *wi;
+
+       /**
+        * Subsampling of FFT twiddle factors table
+        */
+       uint16_t s;
+
+       /**
+        * FFT bit reversal
+        */
+       uint16_t *rev;
+
+};
+
+/**
+ * FFT parameters for q = 12289 and n = 1024
+ */
+extern ntt_fft_params_t ntt_fft_12289_1024;
+
+/**
+ * FFT parameters for q = 12289 and n = 512
+ */
+extern ntt_fft_params_t ntt_fft_12289_512;
+
+/**
+ * FFT parameters for q = 17 and n = 8
+ */
+extern ntt_fft_params_t ntt_fft_17_8;
+
+#endif /** NTT_FFT_PARAMS_H_ @}*/
diff --git a/src/libstrongswan/math/libnttfft/ntt_fft_reduce.h b/src/libstrongswan/math/libnttfft/ntt_fft_reduce.h
new file mode 100644 (file)
index 0000000..76a7260
--- /dev/null
@@ -0,0 +1,42 @@
+/*
+ * Copyright (C) 2016 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program 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 General Public License
+ * for more details.
+ */
+
+/**
+ * @defgroup ntt_fft ntt_fft
+ * @{ @ingroup ntt_p
+ */
+
+#ifndef NTT_REDUCE_H_
+#define NTT_REDUCE_H_
+
+#include "ntt_fft_params.h"
+
+/**
+ * Montgomery Reduction
+ *
+ * Montgomery, P. L. Modular multiplication without trial division.
+ * Mathematics of Computation 44, 170 (1985), 519–521.
+ */
+static inline uint32_t ntt_fft_mreduce(uint32_t x, ntt_fft_params_t *p)
+{
+       uint32_t m, t;
+       
+       m = (x * p->q_inv) & p->rmask;
+       t = (x + m * p->q) >> p->rlog;
+
+       return (t < p->q) ? t : t - p->q;
+}
+
+#endif /** NTT_REDUCE_H_ @}*/
diff --git a/src/libstrongswan/math/libnttfft/tests/.gitignore b/src/libstrongswan/math/libnttfft/tests/.gitignore
new file mode 100644 (file)
index 0000000..da0c7d5
--- /dev/null
@@ -0,0 +1 @@
+ntt_fft_tests
diff --git a/src/libstrongswan/math/libnttfft/tests/Makefile.am b/src/libstrongswan/math/libnttfft/tests/Makefile.am
new file mode 100644 (file)
index 0000000..55e6fff
--- /dev/null
@@ -0,0 +1,21 @@
+TESTS = ntt_fft_tests
+
+check_PROGRAMS = $(TESTS)
+
+ntt_fft_tests_SOURCES = \
+       suites/test_ntt_fft.c \
+       ntt_fft_tests.h ntt_fft_tests.c
+
+ntt_fft_tests_CFLAGS = \
+       -I$(top_srcdir)/src/libstrongswan \
+       -I$(top_srcdir)/src/libstrongswan/tests \
+       -I$(top_srcdir)/src/libstrongswan/math/libnttfft \
+       -DPLUGINDIR=\""$(abs_top_builddir)/src/libstrongswan/plugins\"" \
+       -DPLUGINS=\""${s_plugins}\"" \
+       @COVERAGE_CFLAGS@
+
+ntt_fft_tests_LDFLAGS = @COVERAGE_LDFLAGS@
+ntt_fft_tests_LDADD = \
+       $(top_builddir)/src/libstrongswan/libstrongswan.la \
+       $(top_builddir)/src/libstrongswan/tests/libtest.la \
+       ../libnttfft.la
diff --git a/src/libstrongswan/math/libnttfft/tests/ntt_fft_tests.c b/src/libstrongswan/math/libnttfft/tests/ntt_fft_tests.c
new file mode 100644 (file)
index 0000000..71f5664
--- /dev/null
@@ -0,0 +1,60 @@
+/*
+ * Copyright (C) 2016 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program 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 General Public License
+ * for more details.
+ */
+
+#include <test_runner.h>
+
+#include <library.h>
+
+/* declare test suite constructors */
+#define TEST_SUITE(x) test_suite_t* x();
+#include "ntt_fft_tests.h"
+#undef TEST_SUITE
+
+static test_configuration_t tests[] = {
+#define TEST_SUITE(x) \
+       { .suite = x, },
+#include "ntt_fft_tests.h"
+       { .suite = NULL, }
+};
+
+static bool test_runner_init(bool init)
+{
+       if (init)
+       {
+               char *plugins, *plugindir;
+
+               plugins = lib->settings->get_str(lib->settings,
+                                                                               "tests.load", PLUGINS);
+               plugindir = lib->settings->get_str(lib->settings,
+                                                                               "tests.plugindir", PLUGINDIR);
+               plugin_loader_add_plugindirs(plugindir, plugins);
+               if (!lib->plugins->load(lib->plugins, plugins))
+               {
+                       return FALSE;
+               }
+       }
+       else
+       {
+               lib->processor->set_threads(lib->processor, 0);
+               lib->processor->cancel(lib->processor);
+               lib->plugins->unload(lib->plugins);
+       }
+       return TRUE;
+}
+
+int main(int argc, char *argv[])
+{
+       return test_runner_run("ntt_fft", tests, test_runner_init);
+}
diff --git a/src/libstrongswan/math/libnttfft/tests/ntt_fft_tests.h b/src/libstrongswan/math/libnttfft/tests/ntt_fft_tests.h
new file mode 100644 (file)
index 0000000..200b5b0
--- /dev/null
@@ -0,0 +1,17 @@
+/*
+ * Copyright (C) 2016 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program 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 General Public License
+ * for more details.
+ */
+
+TEST_SUITE(ntt_fft_suite_create)
+
diff --git a/src/libstrongswan/math/libnttfft/tests/suites/test_ntt_fft.c b/src/libstrongswan/math/libnttfft/tests/suites/test_ntt_fft.c
new file mode 100644 (file)
index 0000000..3a8b020
--- /dev/null
@@ -0,0 +1,154 @@
+/*
+ * Copyright (C) 2014-2016 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program 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 General Public License
+ * for more details.
+ */
+
+#include "test_suite.h"
+
+#include <ntt_fft.h>
+#include <ntt_fft_reduce.h>
+
+#include <time.h>
+
+static ntt_fft_params_t *fft_params[] = {
+       &ntt_fft_17_8,
+       &ntt_fft_12289_512,
+       &ntt_fft_12289_1024
+};
+
+START_TEST(test_ntt_fft_impulse)
+{
+       ntt_fft_t *fft;
+       uint16_t n = fft_params[_i]->n;
+       uint32_t rq = (1 << fft_params[_i]->rlog) % fft_params[_i]->q;
+       uint32_t x[n], X[n];
+       int i;
+
+       for (i = 0; i < n; i++)
+       {
+               x[i] = 0;
+       }
+       x[0] = 1;
+       fft = ntt_fft_create(fft_params[_i]);
+       fft->transform(fft, x, X, FALSE);
+
+       for (i = 0; i < n; i++)
+       {
+               ck_assert(X[i] == rq);
+       }
+       fft->transform(fft, X, x, TRUE);
+
+       for (i = 0; i < n; i++)
+       {
+               ck_assert(x[i] == (i == 0));
+       }
+       fft->destroy(fft);
+}
+END_TEST
+
+START_TEST(test_ntt_fft_wrap)
+{
+       ntt_fft_t *fft;
+       uint16_t n = fft_params[_i]->n;
+       uint16_t q = fft_params[_i]->q;
+       uint32_t x[n],y[n], X[n], Y[n];
+       int i, j;
+
+       for (i = 0; i < n; i++)
+       {
+               x[i] = i;
+               y[i] = 0;
+       }
+       fft = ntt_fft_create(fft_params[_i]);
+       ck_assert(fft->get_size(fft) == n);
+       ck_assert(fft->get_modulus(fft) == q); 
+       fft->transform(fft, x, X, FALSE);
+
+       for (j = 0; j < n; j++)
+       {
+               y[j] = 1;
+               fft->transform(fft, y, Y, FALSE);
+
+               for (i = 0; i < n; i++)
+               {
+                       Y[i] = ntt_fft_mreduce(X[i] * Y[i], fft_params[_i]);
+               }
+               fft->transform(fft, Y, Y, TRUE);
+
+               for (i = 0; i < n; i++)
+               {
+                       ck_assert(Y[i] == ( i < j ? q - n - i + j : i - j));
+               }
+               y[j] = 0;
+       }
+       fft->destroy(fft);  
+}
+END_TEST
+
+START_TEST(test_ntt_fft_speed)
+{
+       ntt_fft_t *fft;
+       struct timespec start, stop;
+       int i, m, count = 10000;
+       int n = fft_params[_i]->n;
+       uint32_t x[n], X[n];
+
+       for (i = 0; i < n; i++)
+       {
+               x[i] = i;
+       }
+       fft = ntt_fft_create(fft_params[_i]);
+
+       clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
+       for (m = 0; m < count; m++)
+       {
+               fft->transform(fft, x, X, FALSE);
+               fft->transform(fft, X, x, TRUE);
+       }
+       clock_gettime(CLOCK_THREAD_CPUTIME_ID, &stop);
+
+       DBG0(DBG_LIB, "%d FFT-%d loops in %d ms\n", count, n,
+                                 (stop.tv_nsec - start.tv_nsec) / 1000000 +
+                                 (stop.tv_sec - start.tv_sec) * 1000);
+
+       for (i = 0; i < n; i++)
+       {
+               ck_assert(x[i] == i);
+       }
+       fft->destroy(fft);
+}
+END_TEST
+
+Suite *ntt_fft_suite_create()
+{
+       Suite *s;
+       TCase *tc;
+
+       s = suite_create("ntt_fft");
+
+       tc = tcase_create("impulse");
+       tcase_add_loop_test(tc, test_ntt_fft_impulse, 0, countof(fft_params));
+       suite_add_tcase(s, tc);
+
+       tc = tcase_create("negative_wrap");
+       tcase_add_loop_test(tc, test_ntt_fft_wrap, 0, countof(fft_params));
+       suite_add_tcase(s, tc);
+
+       tc = tcase_create("speed");
+       tcase_set_timeout(tc, 10);
+       tcase_add_loop_test(tc, test_ntt_fft_speed, 1, countof(fft_params));
+       suite_add_tcase(s, tc);
+
+       return s;
+}
index 7ce6f32..b2d0942 100644 (file)
@@ -1,5 +1,6 @@
 AM_CPPFLAGS = \
-       -I$(top_srcdir)/src/libstrongswan
+       -I$(top_srcdir)/src/libstrongswan \
+       -I$(top_srcdir)/src/libstrongswan/math/libnttfft
 
 AM_CFLAGS = \
        $(PLUGIN_CFLAGS) \
@@ -7,9 +8,12 @@ AM_CFLAGS = \
 
 # these file are also used by bliss_huffman
 noinst_LTLIBRARIES = libbliss-params.la
+
 libbliss_params_la_SOURCES = \
-       bliss_param_set.h bliss_param_set.c \
-       bliss_fft_params.h bliss_fft_params.c
+       bliss_param_set.h bliss_param_set.c
+
+libbliss_params_la_LIBADD = \
+       $(top_builddir)/src/libstrongswan/math/libnttfft/libnttfft.la
 
 # these files are also used by the tests, we can't directly refer to them
 # because of the subdirectory, which would cause distclean to fail
@@ -20,12 +24,14 @@ libbliss_la_SOURCES = \
        bliss_signature.h bliss_signature.c \
        bliss_utils.h bliss_utils.c \
        bliss_bitpacker.h bliss_bitpacker.c \
-       bliss_reduce.h bliss_fft.h bliss_fft.c \
        bliss_huffman_code.h bliss_huffman_code.c \
        bliss_huffman_code_1.c bliss_huffman_code_3.c bliss_huffman_code_4.c \
        bliss_huffman_coder.h bliss_huffman_coder.c \
        bliss_sampler.h bliss_sampler.c
-libbliss_la_LIBADD = libbliss-params.la
+
+libbliss_la_LIBADD = \
+       $(top_builddir)/src/libstrongswan/math/libnttfft/libnttfft.la \
+       libbliss-params.la
 
 if MONOLITHIC
 noinst_LTLIBRARIES += libstrongswan-bliss.la
@@ -43,7 +49,10 @@ libstrongswan_bliss_la_LIBADD = libbliss.la
 noinst_PROGRAMS = bliss_huffman
 
 bliss_huffman_SOURCES = bliss_huffman.c
-bliss_huffman_LDADD = -lm libbliss-params.la
+
+bliss_huffman_LDADD = -lm \
+       $(top_builddir)/src/libstrongswan/math/libnttfft/libnttfft.la \
+       libbliss-params.la
 
 recreate-bliss-huffman :       bliss_huffman bliss_huffman_code.h
        $(AM_V_GEN) \
diff --git a/src/libstrongswan/plugins/bliss/bliss_fft.c b/src/libstrongswan/plugins/bliss/bliss_fft.c
deleted file mode 100644 (file)
index 2355a9f..0000000
+++ /dev/null
@@ -1,200 +0,0 @@
-/*
- * Copyright (C) 2014-2016 Andreas Steffen
- * HSR Hochschule fuer Technik Rapperswil
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
- *
- * This program 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 General Public License
- * for more details.
- */
-
-#include "bliss_fft.h"
-#include "bliss_reduce.h"
-
-typedef struct private_bliss_fft_t private_bliss_fft_t;
-
-/**
- * Private data structure for bliss_fft_t object
- */
-struct private_bliss_fft_t {
-
-       /**
-        * Public interface.
-        */
-       bliss_fft_t public;
-
-       /**
-        * FFT parameter set used as constants
-        */
-       bliss_fft_params_t *p;
-
-};
-
-METHOD(bliss_fft_t, get_size, uint16_t,
-       private_bliss_fft_t *this)
-{
-       return this->p->n;
-}
-
-METHOD(bliss_fft_t, get_modulus, uint16_t,
-       private_bliss_fft_t *this)
-{
-       return this->p->q;
-}
-
-/**
- * Do an FFT butterfly operation
- *
- * x[i1] ---|+|------- x[i1]
- *        \/
- *        /\    w[iw]  
- * x[i2] ---|-|--|*|-- x[i2]
- *
- */
-static void butterfly(private_bliss_fft_t *this, uint32_t *x, int i1,int i2,
-                                                                                                                         int iw)
-{
-       uint32_t xp, xm;
-
-       xp = x[i1] + x[i2];
-       xm = x[i1] + (this->p->q - x[i2]);
-       if (xp >= this->p->q)
-       {
-               xp -= this->p->q;
-       }
-       x[i1] = xp;
-       x[i2] = bliss_mreduce(xm * this->p->wr[iw], this->p);
-}
-
-/**
- * Trivial butterfly operation of last FFT stage
- */
-static void butterfly_last(private_bliss_fft_t *this, uint32_t *x, int i1)
-{
-       uint32_t xp, xm;
-       int i2 = i1 + 1;
-
-       xp = x[i1] + x[i2];
-       xm = x[i1] + (this->p->q - x[i2]);
-       if (xp >= this->p->q)
-       {
-               xp -= this->p->q;
-       }
-       if (xm >= this->p->q)
-       {
-               xm -= this->p->q;
-       }
-       x[i1] = xp;
-       x[i2] = xm;
-}
-
-METHOD(bliss_fft_t, transform, void,
-       private_bliss_fft_t *this, uint32_t *a, uint32_t *b, bool inverse)
-{
-       int stage, i, j, k, m, n, s, t, iw, i_rev;
-       uint32_t tmp;
-
-       /* we are going to use the transform size n a lot */
-       n = this->p->n;
-       s = this->p->s;
-
-       if (!inverse)
-       {
-               /* apply linear phase needed for negative wrapped convolution */
-               for (i = 0; i < n; i++)
-               {
-                       b[i] = bliss_mreduce(a[i] * this->p->wf[s*i], this->p);
-               }
-       }
-       else if (a != b)
-       {
-               /* copy if input and output array are not the same */
-               for (i = 0; i < n; i++)
-               {
-                       b[i] = a[i];
-               }
-       }
-
-       m = n;
-       k = 1;
-
-       for (stage = this->p->stages; stage > 0; stage--)
-       {
-               m >>= 1;
-               t = 0;
-
-               for (j = 0; j < k; j++)
-               {
-                       if (stage == 1)
-                       {
-                               butterfly_last(this, b, t);
-                       }
-                       else
-                       {
-                               for (i = 0; i < m; i++)
-                               {
-                                       iw = s * (inverse ? (n - i * k) : (i * k));
-                                       butterfly(this, b, t + i, t + i + m, iw);
-                               }                               
-                       }
-                       t += 2*m;
-               }
-               k <<= 1;
-       }
-
-       /* Sort output in bit-reverse order */
-       for (i = 0; i < n; i++)
-       {
-               i_rev = this->p->rev[i];
-
-               if (i_rev > i)
-               {
-                       tmp = b[i];
-                       b[i] = b[i_rev];
-                       b[i_rev] = tmp;
-               }
-       }
-
-       /**
-        * Compensate the linear phase needed for negative wrapped convolution
-        * and normalize the output array with 1/n mod q after the inverse FFT. 
-        */
-       if (inverse)
-       {
-               for (i = 0; i < n; i++)
-               {
-                       b[i] = bliss_mreduce(b[i] * this->p->wi[i], this->p);
-               }
-       }
-}
-
-METHOD(bliss_fft_t, destroy, void,
-       private_bliss_fft_t *this)
-{
-       free(this);
-}
-
-/**
- * See header.
- */
-bliss_fft_t *bliss_fft_create(bliss_fft_params_t *params)
-{
-       private_bliss_fft_t *this;
-
-       INIT(this,
-               .public = {
-                       .get_size = _get_size,
-                       .get_modulus = _get_modulus,
-                       .transform = _transform,
-                       .destroy = _destroy,
-               },
-               .p = params,
-       );
-
-       return &this->public;
-}
diff --git a/src/libstrongswan/plugins/bliss/bliss_fft.h b/src/libstrongswan/plugins/bliss/bliss_fft.h
deleted file mode 100644 (file)
index a79edd2..0000000
+++ /dev/null
@@ -1,71 +0,0 @@
-/*
- * Copyright (C) 2014 Andreas Steffen
- * HSR Hochschule fuer Technik Rapperswil
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
- *
- * This program 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 General Public License
- * for more details.
- */
-
-/**
- * @defgroup bliss_fft bliss_fft
- * @{ @ingroup bliss_p
- */
-
-#ifndef BLISS_FFT_H_
-#define BLISS_FFT_H_
-
-#include "bliss_fft_params.h"
-
-#include <library.h>
-
-typedef struct bliss_fft_t bliss_fft_t;
-
-/**
- * Implements a Number Theoretic Transform (NTT) via the FFT algorithm
- */
-struct bliss_fft_t {
-
-       /**
-        * Get the size of the Number Theoretic Transform
-        *
-        * @result                      Transform size
-        */
-       uint16_t (*get_size)(bliss_fft_t *this);
-
-       /**
-        * Get the prime modulus of the Number Theoretic Transform
-        *
-        * @result                      Prime modulus
-        */
-       uint16_t (*get_modulus)(bliss_fft_t *this);
-
-       /**
-        * Compute the [inverse] NTT of a polynomial
-        *
-        * @param a                     Coefficient of input polynomial
-        * @param b                     Coefficient of output polynomial
-        * @param inverse       TRUE if the inverse NTT has to be computed
-        */
-       void (*transform)(bliss_fft_t *this, uint32_t *a, uint32_t *b, bool inverse);
-
-       /**
-        * Destroy bliss_fft_t object
-        */
-       void (*destroy)(bliss_fft_t *this);
-};
-
-/**
- * Create a bliss_fft_t object for a given FFT parameter set
- *
- * @param params               FFT parameters
- */
-bliss_fft_t *bliss_fft_create(bliss_fft_params_t *params);
-
-#endif /** BLISS_FFT_H_ @}*/
diff --git a/src/libstrongswan/plugins/bliss/bliss_fft_params.c b/src/libstrongswan/plugins/bliss/bliss_fft_params.c
deleted file mode 100644 (file)
index db6abea..0000000
+++ /dev/null
@@ -1,652 +0,0 @@
-/*
- * Copyright (C) 2014-2016 Andreas Steffen
- * HSR Hochschule fuer Technik Rapperswil
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
- *
- * This program 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 General Public License
- * for more details.
- */
-
-#include "bliss_fft_params.h"
-
-/**
- * FFT twiddle factors in Montgomery form for q = 12289 and n = 1024
- */
-static uint16_t wr_12289_1024[] = {
-        4075,  3051,  2031,  1207,  9987, 10092,  2948,  9273, 11973,  9094,
-        3202,  9430,  7377,  5092,  3728, 10626,  4536,  1062,  2882,  6039,
-         975, 10908,  6065,  2249, 11889,  4978, 10431,  7270, 12138,  4890,
-        6119,  4895,  6364,  4611,  4737, 10911,  6212,  9452,  8455,  8758,
-       11316,  1479, 11026, 11847,  2920,  7901,  6190,  8374,  4789,  1170,
-        8174,  7278,   241, 11809,  1058,  2686,  8724,  9650,  5868,  4885,
-        5874,  5179,  7991, 10600,  3262,    81,  3969, 10146,  5594,  3748,
-       11606,  3400,  6843,  3504, 11939,  7428,  7591,  3289,  1404,  7351,
-        3818,  2747, 11713,  8643,  5681,  8011, 11580,  2126,  5862,  4591,
-        3757, 12047,   431,  8830,  2555,  2305,  2344,  4255, 11871,  4096,
-
-        4080,  3296,  1747, 11869,  3998, 11567,  1489, 11516, 11279, 11955,
-        8212,  9140,  5456,  9275, 12071,  1607,  5009, 11950,  7967,  9424,
-        7083,  2975, 10596,  3066,  2766,   355,  5106,  4414,  7373,  4896,
-        6413,  7012, 11785, 12171,  6507, 11618,  3988, 11077,  2057,  2481,
-       10968,  9005, 11130,  4654,  6844,  3553,  2051,  2187,  8851,  3584,
-        3570,  2884,  6137,  5777,   426,  8585,  2839,  3932,  8333,  2780,
-        1041,  1853,  4774,   435,  9026, 12159,  5919,  7384,  5435,  8246,
-       10806,  1067,  3127,  5755, 11637,  4919,  7540,   790,  1843,  4284,
-        1003, 12280, 11848,  2969, 10302,   949,  9634,  5084,  3336,  3707,
-        9597,  3271,   522,  1000, 12133,  4645,  6403,  6522,    64,  3136,
-
-        6196,  8668,  6906,  6591,  3445,  9048,   948,  9585,  2683,  8577,
-        2447,  9302,  1105,  4989, 10970,  9103,  3643,  6461,  9364,  4143,
-        6383,  5542,  1200,  9644,  5574,  2768,   453,  9908,  6221,  9893,
-        5486, 10745, 10367,  4134,  5942,  8511, 11502, 10593,  2919,  7852,
-        3789,  1326,  3529,   875,  6008, 11745, 10211,  8779,    56,  2744,
-       11566,  1440,  9115,  4231, 10695,  7917,  6974,  9923,  6956,  9041,
-         605,  5067,  2503, 12046,   382,  6429,  7796,  1045,  2049,  2089,
-        4049,  1777,  1050,  2294,  1805,  2422,  8077,  2525,   835,  4048,
-        1728, 10938,  7535,   545,  2127,  5911,  6992, 10805,  1018,   726,
-       10996, 10377,  4624,  5374,  5257, 11813,  1254,     1,    49,  2401,
-
-        7048,  1260,   295,  2166,  7822,  2319,  3030,  1002, 12231,  9447,
-        8210,  9042,   654,  7468,  9551,  1017,   677,  8595,  3329,  3364,
-        5079,  3091,  3991, 11224,  9260, 11336,  2459,  9890,  5339,  3542,
-        1512,   354,  5057,  2013,   325,  3636,  6118,  4846,  3963,  9852,
-        3477, 10616,  4046,  1630,  6136,  5728, 10314,  1537,  1579,  3637,
-        6167,  7247, 11011, 11112,  3772,   493, 11868,  3949,  9166,  6730,
-       10256, 10984,  9789,   390,  6821,  2426,  8273, 12129,  4449,  9088,
-        2908,  7313,  1956,  9821,  1958,  9919,  6760, 11726,  9280,    27,
-        1323,  3382,  5961,  9442,  7965,  9326,  2281,  1168,  8076,  2476,
-       10723,  9289,   468, 10643,  5369,  5012, 12097,  2881,  5990, 10863,
-
-        3860,  4805,  1954,  9723,  9445,  8112,  4240, 11136,  4948,  8961,
-        8974,  9611,  3957,  9558,  1360,  5195,  8775, 12149,  5429,  7952,
-        8689,  7935,  7856,  3985, 10930,  7143,  5915,  7188,  8120,  4632,
-        5766, 12176,  6752, 11334,  2361,  5088,  3532,  1022,   922,  8311,
-        1702,  9664,  6554,  1632,  6234, 10530, 12121,  4057,  2169,  7969,
-        9522, 11885,  4782,   827,  3656,  7098,  3710,  9744, 10474,  9377,
-        4780,   729, 11143,  5291,  1190,  9154,  6142,  6022,   142,  6958,
-        9139,  5407,  6874,  5023,   347,  4714,  9784,   145,  7105,  4053,
-        1973, 10654,  5908,  6845,  3602,  4452,  9235, 10111,  3879,  5736,
-       10706,  8456,  8807,  1428,  8527, 12286, 12142,  5086,  3434,  8509,
-
-       11404,  5791,  1112,  5332,  3199,  9283,   174,  8526, 12237,  9741,
-       10327,  2174,  8214,  9238, 10258, 11082,  2302,  2197,  9341,  3016,
-         316,  3195,  9087,  2859,  4912,  7197,  8561,  1663,  7753, 11227,
-        9407,  6250, 11314,  1381,  6224, 10040,   400,  7311,  1858,  5019,
-         151,  7399,  6170,  7394,  5925,  7678,  7552,  1378,  6077,  2837,
-        3834,  3531,   973, 10810,  1263,   442,  9369,  4388,  6099,  3915,
-        7500, 11119,  4115,  5011, 12048,   480, 11231,  9603,  3565,  2639,
-        6421,  7404,  6415,  7110,  4298,  1689,  9027, 12208,  8320,  2143,
-        6695,  8541,   683,  8889,  5446,  8785,   350,  4861,  4698,  9000,
-       10885,  4938,  8471,  9542,   576,  3646,  6608,  4278,   709, 10163,
-
-        6427,  7698,  8532,   242, 11858,  3459,  9734,  9984,  9945,  8034,
-         418,  8193,  8209,  8993, 10542,   420,  8291,   722, 10800,   773,
-        1010,   334,  4077,  3149,  6833,  3014,   218, 10682,  7280,   339,
-        4322,  2865,  5206,  9314,  1693,  9223,  9523, 11934,  7183,  7875,
-        4916,  7393,  5876,  5277,   504,   118,  5782,   671,  8301,  1212,
-       10232,  9808,  1321,  3284,  1159,  7635,  5445,  8736, 10238, 10102,
-        3438,  8705,  8719,  9405,  6152,  6512, 11863,  3704,  9450,  8357,
-        3956,  9509, 11248, 10436,  7515, 11854,  3263,   130,  6370,  4905,
-        6854,  4043,  1483, 11222,  9162,  6534,   652,  7370,  4749, 11499,
-       10446,  8005, 11286,     9,   441,  9320,  1987, 11340,  2655,  7205,
-
-        8953,  8582,  2692,  9018, 11767, 11289,   156,  7644,  5886,  5767,
-       12225,  9153,  6093,  3621,  5383,  5698,  8844,  3241, 11341,  2704,
-        9606,  3712,  9842,  2987, 11184,  7300,  1319,  3186,  8646,  5828,
-        2925,  8146,  5906,  6747, 11089,  2645,  6715,  9521, 11836,  2381,
-        6068,  2396,  6803,  1544,  1922,  8155,  6347,  3778,   787,  1696,
-        9370,  4437,  8500, 10963,  8760, 11414,  6281,   544,  2078,  3510,
-       12233,  9545,   723, 10849,  3174,  8058,  1594,  4372,  5315,  2366,
-        5333,  3248, 11684,  7222,  9786,   243, 11907,  5860,  4493, 11244,
-       10240, 10200,  8240, 10512, 11239,  9995, 10484,  9867,  4212,  9764,
-       11454,  8241, 10561,  1351,  4754, 11744, 10162,  6378,  5297,  1484,
-
-       11271, 11563,  1293,  1912,  7665,  6915,  7032,   476, 11035, 12288,
-       12240,  9888,  5241, 11029, 11994, 10123,  4467,  9970,  9259, 11287,
-          58,  2842,  4079,  3247, 11635,  4821,  2738, 11272, 11612,  3694,
-        8960,  8925,  7210,  9198,  8298,  1065,  3029,   953,  9830,  2399,
-        6950,  8747, 10777, 11935,  7232, 10276, 11964,  8653,  6171,  7443,
-        8326,  2437,  8812,  1673,  8243, 10659,  6153,  6561,  1975, 10752,
-       10710,  8652,  6122,  5042,  1278,  1177,  8517, 11796,   421,  8340,
-        3123,  5559,  2033,  1305,  2500, 11899,  5468,  9863,  4016,   160,
-        7840,  3201,  9381,  4976, 10333,  2468, 10331,  2370,  5529,   563,
-        3009, 12262, 10966,  8907,  6328,  2847,  4324,  2963, 10008, 11121,
-
-        4213,  9813,  1566,  3000, 11821,  1646,  6920,  7277,   192,  9408,
-        6299,  1426,  8429,  7484, 10335,  2566,  2844,  4177,  8049,  1153,
-        7341,  3328,  3315,  2678,  8332,  2731, 10929,  7094,  3514,   140,
-        6860,  4337,  3600,  4354,  4433,  8304,  1359,  5146,  6374,  5101,
-        4169,  7657,  6523,   113,  5537,   955,  9928,  7201,  8757, 11267,
-       11367,  3978, 10587,  2625,  5735, 10657,  6055,  1759,   168,  8232,
-       10120,  4320,  2767,   404,  7507, 11462,  8633,  5191,  8579,  2545,
-        1815,  2912,  7509, 11560,  1146,  6998, 11099,  3135,  6147,  6267,
-       12147,  5331,  3150,  6882,  5415,  7266, 11942,  7575,  2505, 12144,
-        5184,  8236, 10316,  1635,  6381,  5444,  8687,  7837,  3054,  2178,
-
-        8410,  6553,  1583,  3833,  3482, 10861,  3762,     3,   147,  7203,
-        8855,  3780,   885,  6498, 11177,  6957,  9090,  3006, 12115,  3763,
-          52,  2548,  1962, 10115,  4075
-};
-
-/**
- * FFT phase shift in forward transform for q = 12289 and n = 1024
- */
-static uint16_t wf_12289_1024[] = {
-        3186, 10013,  8646, 11366,  5828,  3929,  2925,  8186,  8146,  7866,
-        5906,  4475,  6747, 10362, 11089,  3889,  2645,  6226,  6715, 10138,
-        9521,  5202, 11836,  9118,  2381,  4378,  6068,  5609,  2396,  4483,
-        6803, 10754,  1544, 10808,  1922,  1165,  8155,  7929,  6347,  7562,
-        3778,  1868,   787,  5509,  1696, 11872,  9370,  4145,  4437,  6481,
-        8500, 10344, 10963,  3007,  8760, 12164, 11414,  6164,  6281,  7100,
-         544,  3808,  2078,  2257,  3510, 12281, 12233, 11897,  9545,  5370,
-         723,  5061, 10849,  2209,  3174,  9929,  8058,  7250,  1594, 11158,
-        4372,  6026,  5315,   338,  2366,  4273,  5333,   464,  3248, 10447,
-       11684,  8054,  7222,  1398,  9786,  7057,   243,  1701, 11907,  9615,
-
-        5860,  4153,  4493,  6873, 11244,  4974, 10240, 10235, 10200,  9955,
-        8240,  8524, 10512, 12139, 11239,  4939,  9995,  8520, 10484, 11943,
-        9867,  7624,  4212,  4906,  9764,  6903, 11454,  6444,  8241,  8531,
-       10561,   193,  1351,  9457,  4754,  8700, 11744,  8474, 10162,  9689,
-        6378,  7779,  5297,   212,  1484, 10388, 11271,  5163, 11563,  7207,
-        1293,  9051,  1912,  1095,  7665,  4499,  6915, 11538,  7032,    68,
-         476,  3332, 11035,  3511, 12288, 12282, 12240, 11946,  9888,  7771,
-        5241, 12109, 11029,  3469, 11994, 10224, 10123,  9416,  4467,  6691,
-        9970,  8345,  9259,  3368, 11287,  5275,    58,   406,  2842,  7605,
-        4079,  3975,  3247, 10440, 11635,  7711,  4821,  9169,  2738,  6877,
-
-       11272,  5170, 11612,  7550,  3694,  1280,  8960,  1275,  8925,  1030,
-        7210,  1314,  9198,  2941,  8298,  8930,  1065,  7455,  3029,  8914,
-         953,  6671,  9830,  7365,  2399,  4504,  6950, 11783,  8747, 12073,
-       10777,  1705, 11935,  9811,  7232,  1468, 10276, 10487, 11964, 10014,
-        8653, 11415,  6171,  6330,  7443,  2945,  8326,  9126,  2437,  4770,
-        8812,   239,  1673, 11711,  8243,  8545, 10659,   879,  6153,  6204,
-        6561,  9060,  1975,  1536, 10752,  1530, 10710,  1236,  8652, 11408,
-        6122,  5987,  5042, 10716,  1278,  8946,  1177,  8239,  8517, 10463,
-       11796,  8838,   421,  2947,  8340,  9224,  3123,  9572,  5559,  2046,
-        2033,  1942,  1305,  9135,  2500,  5211, 11899,  9559,  5468,  1409,
-
-        9863,  7596,  4016,  3534,   160,  1120,  7840,  5724,  3201, 10118,
-        9381,  4222,  4976, 10254, 10333, 10886,  2468,  4987, 10331, 10872,
-        2370,  4301,  5529,  1836,   563,  3941,  3009,  8774, 12262, 12100,
-       10966,  3028,  8907,   904,  6328,  7429,  2847,  7640,  4324,  5690,
-        2963,  8452, 10008,  8611, 11121,  4113,  4213,  4913,  9813,  7246,
-        1566, 10962,  3000,  8711, 11821,  9013,  1646, 11522,  6920, 11573,
-        7277,  1783,   192,  1344,  9408,  4411,  6299,  7226,  1426,  9982,
-        8429,  9847,  7484,  3232, 10335, 10900,  2566,  5673,  2844,  7619,
-        4177,  4661,  8049,  7187,  1153,  8071,  7341,  2231,  3328, 11007,
-        3315, 10916,  2678,  6457,  8332,  9168,  2731,  6828, 10929,  2769,
-
-        7094,   502,  3514,    20,   140,   980,  6860, 11153,  4337,  5781,
-        3600,   622,  4354,  5900,  4433,  6453,  8304,  8972,  1359,  9513,
-        5146, 11444,  6374,  7751,  5101, 11129,  4169,  4605,  7657,  4443,
-        6523,  8794,   113,   791,  5537,  1892,   955,  6685,  9928,  8051,
-        7201,  1251,  8757, 12143, 11267,  5135, 11367,  5835,  3978,  3268,
-       10587,   375,  2625,  6086,  5735,  3278, 10657,   865,  6055,  5518,
-        1759,    24,   168,  1176,  8232,  8468, 10120,  9395,  4320,  5662,
-        2767,  7080,   404,  2828,  7507,  3393, 11462,  6500,  8633, 11275,
-        5191, 11759,  8579, 10897,  2545,  5526,  1815,   416,  2912,  8095,
-        7509,  3407, 11560,  7186,  1146,  8022,  6998, 12119, 11099,  3959,
-
-        3135,  9656,  6147,  6162,  6267,  7002, 12147, 11295,  5331,   450,
-        3150,  9761,  6882, 11307,  5415,  1038,  7266,  1706, 11942,  9860,
-        7575,  3869,  2505,  5246, 12144, 11274,  5184, 11710,  8236,  8496,
-       10316, 10767,  1635, 11445,  6381,  7800,  5444,  1241,  8687, 11653,
-        7837,  5703,  3054,  9089,  2178,  2957,  8410,  9714,  6553,  9004,
-        1583, 11081,  3833,  2253,  3482, 12085, 10861,  2293,  3762,  1756,
-           3,    21,   147,  1029,  7203,  1265,  8855,   540,  3780,  1882,
-         885,  6195,  6498,  8619, 11177,  4505,  6957, 11832,  9090,  2185,
-        3006,  8753, 12115, 11071,  3763,  1763,    52,   364,  2548,  5547,
-        1962,  1445, 10115,  9360,  4075,  3947,  3051,  9068,  2031,  1928,
-
-        1207,  8449,  9987,  8464, 10092,  9199,  2948,  8347,  9273,  3466,
-       11973, 10077,  9094,  2213,  3202, 10125,  9430,  4565,  7377,  2483,
-        5092, 11066,  3728,  1518, 10626,   648,  4536,  7174,  1062,  7434,
-        2882,  7885,  6039,  5406,   975,  6825, 10908,  2622,  6065,  5588,
-        2249,  3454, 11889,  9489,  4978, 10268, 10431, 11572,  7270,  1734,
-       12138, 11232,  4890,  9652,  6119,  5966,  4895,  9687,  6364,  7681,
-        4611,  7699,  4737,  8581, 10911,  2643,  6212,  6617,  9452,  4719,
-        8455, 10029,  8758, 12150, 11316,  5478,  1479, 10353, 11026,  3448,
-       11847,  9195,  2920,  8151,  7901,  6151,  6190,  6463,  8374,  9462,
-        4789,  8945,  1170,  8190,  8174,  8062,  7278,  1790,   241,  1687,
-
-       11809,  8929,  1058,  7406,  2686,  6513,  8724, 11912,  9650,  6105,
-        5868,  4209,  4885,  9617,  5874,  4251,  5179, 11675,  7991,  6781,
-       10600,   466,  3262, 10545,    81,   567,  3969,  3205, 10146,  9577,
-        5594,  2291,  3748,  1658, 11606,  7508,  3400, 11511,  6843, 11034,
-        3504, 12239, 11939,  9839,  7428,  2840,  7591,  3981,  3289, 10734,
-        1404,  9828,  7351,  2301,  3818,  2148,  2747,  6940, 11713,  8257,
-        8643, 11345,  5681,  2900,  8011,  6921, 11580,  7326,  2126,  2593,
-        5862,  4167,  4591,  7559,  3757,  1721, 12047, 10595,   431,  3017,
-        8830,   365,  2555,  5596,  2305,  3846,  2344,  4119,  4255,  5207,
-       11871,  9363,  4096,  4094,  4080,  3982,  3296, 10783,  1747, 12229,
-
-       11869,  9349,  3998,  3408, 11567,  7235,  1489, 10423, 11516,  6878,
-       11279,  5219, 11955,  9951,  8212,  8328,  9140,  2535,  5456,  1325,
-        9275,  3480, 12071, 10763,  1607, 11249,  5009, 10485, 11950,  9916,
-        7967,  6613,  9424,  4523,  7083,   425,  2975,  8536, 10596,   438,
-        3066,  9173,  2766,  7073,   355,  2485,  5106, 11164,  4414,  6320,
-        7373,  2455,  4896,  9694,  6413,  8024,  7012, 12217, 11785,  8761,
-       12171, 11463,  6507,  8682, 11618,  7592,  3988,  3338, 11077,  3805,
-        2057,  2110,  2481,  5078, 10968,  3042,  9005,  1590, 11130,  4176,
-        4654,  8000,  6844, 11041,  3553,   293,  2051,  2068,  2187,  3020,
-        8851,   512,  3584,   510,  3570,   412,  2884,  7899,  6137,  6092,
-
-        5777,  3572,   426,  2982,  8585, 10939,  2839,  7584,  3932,  2946,
-        8333,  9175,  2780,  7171,  1041,  7287,  1853,   682,  4774,  8840,
-         435,  3045,  9026,  1737, 12159, 11379,  5919,  4566,  7384,  2532,
-        5435,  1178,  8246,  8566, 10806,  1908,  1067,  7469,  3127,  9600,
-        5755,  3418, 11637,  7725,  4919,  9855,  7540,  3624,   790,  5530,
-        1843,   612,  4284,  5410,  1003,  7021, 12280, 12226, 11848,  9202,
-        2969,  8494, 10302, 10669,   949,  6643,  9634,  5993,  5084, 11010,
-        3336, 11063,  3707,  1371,  9597,  5734,  3271, 10608,   522,  3654,
-        1000,  7000, 12133, 11197,  4645,  7937,  6403,  7954,  6522,  8787,
-          64,   448,  3136,  9663,  6196,  6505,  8668, 11520,  6906, 11475,
-
-        6591,  9270,  3445, 11826,  9048,  1891,   948,  6636,  9585,  5650,
-        2683,  6492,  8577, 10883,  2447,  4840,  9302,  3669,  1105,  7735,
-        4989, 10345, 10970,  3056
-};
-
-/**
- * FFT phase shift and scaling inverse transform for q = 12289 and n = 1024
- */
-static uint16_t wi_12289_1024[] = {
-       12277,  5265,  9530,  3117,  5712,   816, 10650,  3277,  9246,  4832,
-        5957,   851, 10655, 10300,  3227,   461,  3577,   511,    73,  1766,
-        5519,  2544,  2119,  7325,  2802,  5667, 11343,  3376,  5749,  6088,
-        7892,  2883,  3923,  2316,  3842,  4060,   580,  3594,  2269,  9102,
-        6567,  9716,  1388,  5465,  7803,  8137,  2918,  3928,  9339, 10112,
-       11978, 10489,  3254,  3976,   568,  8859, 11799, 12219, 12279, 10532,
-       12038,  8742,  4760,   680,  8875,  4779,  7705,  8123,  2916, 10950,
-        6831,  4487,   641, 10625,  5029,  2474,  2109,  5568,  2551,  2120,
-        3814,  4056,  2335, 10867,  3308, 11006,  6839,   977, 10673,  8547,
-        1221,  1930,  7298, 11576,  8676,  2995,  3939,  7585, 11617, 12193,
-
-        5253,  2506,   358,  8829,  6528, 11466,  1638,   234,  1789, 10789,
-        6808, 11506,  8666,  1238,  3688,  4038,  4088,   584,  1839,  7285,
-        8063,  4663,  9444, 10127,  8469,  4721,  2430,  9125, 11837,  1691,
-       10775,  6806,  6239,  6158,  7902,  4640,  4174,  5863, 11371,  3380,
-        3994, 11104,  6853,   979,  3651, 11055,  6846,   978,  7162,  9801,
-       10178,  1454,  7230,  4544,  9427,  8369, 11729, 12209, 10522, 10281,
-        8491,  1213,  5440,  9555,  1365,   195,  3539, 11039,  1577,  5492,
-       11318,  5128, 11266,  3365,  7503,  4583,  7677,  8119,  4671,  5934,
-        7870,  6391,   913,  1886,  2025,  5556,  7816, 11650,  6931,  9768,
-        3151,  9228,  6585,  7963, 11671,  6934, 11524,  6913, 11521,  5157,
-
-        7759,  2864,  9187,  3068,  5705,   815,  1872,  2023,   289,  5308,
-        6025,  7883,  9904,  4926,  7726,  8126,  4672,  2423,  9124,  3059,
-         437,  1818,  7282,  6307,   901,  7151, 11555,  8673,  1239,   177,
-        5292,   756,   108,  1771,   253,  8814, 10037,  4945,  2462,  7374,
-        2809,  5668,  7832,  4630,  2417,  5612,  7824,  8140,  4674,  7690,
-       11632,  8684, 11774,  1682,  5507,  7809, 11649, 10442,  8514,  6483,
-        9704,  6653,  2706, 10920,  1560,  3734,  2289,   327,  7069,  4521,
-        4157,  4105,  2342, 10868, 12086, 12260,  3507,   501, 10605,  1515,
-        1972,  7304,  2799,  3911,  7581,  1083,  7177,  6292,  4410,   630,
-          90,  3524,  2259,  7345,  6316,  6169,  6148,  6145,  4389,   627,
-
-       10623, 12051, 12255,  8773,  6520,  2687,  3895,  2312,  5597, 11333,
-        1619,  5498,  2541,   363,  3563,   509,  7095, 11547, 12183,  3496,
-        2255,  9100,  1300,  7208,  8052,  6417,  7939,  9912,  1416,  5469,
-        6048,   864,  1879,  2024,  9067,  6562,  2693,  7407,  9836, 10183,
-        8477,  1211,   173,  7047,  8029,  1147,  3675,   525,    75,  7033,
-        8027,  8169,  1167,  7189,  1027,  7169,  9802,  6667,  2708,  3898,
-        4068,  9359,  1337,   191,  5294,  6023,  2616,  7396, 11590,  8678,
-        8262,  6447,   921, 10665, 12057,  3478,  4008, 11106, 12120,  3487,
-        9276, 10103,  6710, 11492,  8664,  8260,  1180, 10702,  5040,   720,
-        3614,  5783,  9604,  1372,   196,    28,     4, 10534,  5016, 11250,
-
-       10385, 12017,  8739,  3004,  9207,  6582,  6207,  7909,  4641,   663,
-        7117,  8039,  2904,  3926,  4072,  7604,  6353, 11441,  3390,  5751,
-       11355, 10400,  8508,  2971,  2180,  2067,  5562, 11328,  6885, 11517,
-        6912,  2743,  3903, 11091,  3340,  9255, 10100,  4954,  7730,  6371,
-        9688,  1384,  7220,  2787,  9176,  4822,  4200,   600,  7108,  2771,
-        3907,  9336,  8356,  8216,  8196,  4682,  4180,  9375,  6606,  7966,
-        1138, 10696,  1528,  5485, 11317,  8639, 10012,  6697,  7979,  4651,
-        2420,  7368, 11586, 10433,  3246,  7486,  2825, 10937,  3318,   474,
-        7090,  4524,  5913,  7867,  4635,  9440, 11882,  3453,  5760,  4334,
-        9397,  3098, 10976,  1568,   224,    32, 10538,  3261,  3977,  9346,
-
-       10113,  8467, 11743, 12211,  3500,   500,  1827,   261,  5304,  7780,
-        2867, 10943,  6830,  7998, 11676,  1668,  5505,  2542,  9141,  4817,
-        9466,  6619, 11479,  5151,  4247,  7629,  4601,  5924,  6113,  6140,
-        9655,  6646,  2705,  2142,   306,  7066,  2765,   395,  1812,  3770,
-       11072,  8604, 10007, 11963,  1709,  9022,  4800,  7708,  9879,  6678,
-         954,  5403,  4283,  4123,   589,  8862,  1266,  3692,  2283,  9104,
-       11834, 12224,  7013,  4513,  7667,  6362,  4420,  2387,   341,  7071,
-        9788,  6665,  9730,  1390, 10732, 10311,  1473,  1966,  3792,  7564,
-       11614, 10437,  1491,   213,  1786,  9033,  3046,  9213, 10094,  1442,
-         206,  1785,   255,  1792,   256, 10570,  1510,  7238,  1034,  7170,
-
-        6291,  7921, 11665,  3422,  4000,  2327,  2088,  5565,   795, 10647,
-        1521,  5484,  2539,  7385,  1055,  7173,  8047, 11683,  1669,  1994,
-        3796,  5809,  4341,  9398, 11876, 12230, 10525, 12037, 12253,  3506,
-        4012,  9351,  4847,  2448,  7372,  9831,  3160,  2207,  5582,  2553,
-        7387,  6322,  9681,  1383, 10731,  1533,   219,  5298,  4268,  7632,
-        6357,  9686,  8406,  4712,  9451, 10128,  4958,  5975, 11387,  8649,
-       11769,  6948, 11526, 12180,  1740, 10782,  6807,  2728,  7412,  4570,
-        4164,  4106, 11120, 12122,  8754, 11784,  3439,  5758, 11356,  6889,
-        9762, 11928,  1704,  1999, 10819, 12079, 12259,  7018, 11536,  1648,
-        1991,  2040,  2047,  2048, 10826, 12080,  8748,  8272,  8204,  1172,
-
-        1923,  7297,  2798,  7422,  6327,  4415,  7653,  6360, 11442, 12168,
-        7005,  8023,  9924,  8440,  8228,  2931,  7441,  1063,  3663,  5790,
-        9605, 10150,  1450,  8985, 11817, 10466, 10273, 12001,  3470,  7518,
-        1074,  1909,  7295,  9820,  4914,   702,  5367,  7789,  8135,  9940,
-        1420,  3714, 11064, 12114, 12264,  1752,  5517,  9566, 11900,  1700,
-        3754,  5803,   829,  1874,  7290,  2797, 10933,  5073,  7747,  8129,
-        6428,  6185, 11417,  1631,   233,  5300,  9535, 10140, 11982,  8734,
-        8270,  2937, 10953,  8587,  8249,  2934,  9197,  4825,  5956,  4362,
-        9401,  1343,  3703,   529, 10609, 12049,  6988,  6265,   895,  3639,
-        4031,  4087,  4095,   585, 10617,  8539,  4731,  4187,  9376,  3095,
-
-        9220, 10095, 10220,  1460, 10742, 12068,  1724,  5513, 11321,  6884,
-        2739,  5658,  6075,  4379, 11159, 10372,  8504,  4726,  9453,  3106,
-        7466, 11600, 10435,  8513,  9994,  8450,  9985,  3182, 10988,  8592,
-        2983,  9204,  4826,  2445,  5616,  6069,   867,  3635,  5786, 11360,
-        5134,  2489, 10889, 12089,  1727,  7269,  2794,  9177,  1311,  5454,
-        9557,  6632,  2703,  9164, 10087,  1441,  3717,   531,  3587,  2268,
-         324,  5313,   759,  1864,  5533,  2546,  7386,  9833,  8427,  4715,
-       11207,  1601,  7251,  4547, 11183, 12131,  1733, 10781, 10318,  1474,
-       10744,  5046,  4232, 11138, 10369,  6748,   964,  7160,  4534,  7670,
-        8118,  8182,  4680, 11202,  6867,   981,  8918,  1274,   182,    26,
-
-        7026,  8026, 11680, 12202, 10521,  1503,  7237,  4545,  5916,  9623,
-        8397, 11733, 10454,  3249,  9242,  6587,   941,  1890,   270, 10572,
-        6777,  9746,  6659,  6218,  6155,  6146,   878,  1881,  7291, 11575,
-       12187,  1741,  7271,  8061, 11685,  6936,  4502,  9421,  4857,  4205,
-        7623,  1089, 10689,  1527,  8996, 10063, 11971, 10488,  6765,  2722,
-        3900,  9335, 11867,  6962, 11528,  5158,  4248,  4118,  5855,  2592,
-        5637,  6072,  2623,  7397,  8079,  9932,  4930,  5971,   853,  3633,
-         519,  8852, 11798,  3441, 11025,  1575,   225,  8810, 11792, 12218,
-        3501,  9278,  3081,  9218,  4828,  7712,  8124, 11694, 12204,  3499,
-        4011,   573,  3593,  5780,  7848,  9899, 10192,  1456,   208,  7052,
-
-        2763,  7417, 11593, 10434, 12024,  8740, 11782, 10461,  3250,  5731,
-        7841,  9898,  1414,   202,  3540,  7528,  2831,  2160, 10842,  5060,
-        4234,  4116,   588,    84
-};
-
-/**
- * Bit-reversed indices for n = 1024
- */
-static uint16_t rev_1024[] = {
-          0,  512,  256,  768,  128,  640,  384,  896,   64,  576,
-        320,  832,  192,  704,  448,  960,   32,  544,  288,  800,
-        160,  672,  416,  928,   96,  608,  352,  864,  224,  736,
-        480,  992,   16,  528,  272,  784,  144,  656,  400,  912,
-         80,  592,  336,  848,  208,  720,  464,  976,   48,  560,
-        304,  816,  176,  688,  432,  944,  112,  624,  368,  880,
-        240,  752,  496, 1008,    8,  520,  264,  776,  136,  648,
-        392,  904,   72,  584,  328,  840,  200,  712,  456,  968,
-         40,  552,  296,  808,  168,  680,  424,  936,  104,  616,
-        360,  872,  232,  744,  488, 1000,   24,  536,  280,  792,
-
-        152,  664,  408,  920,   88,  600,  344,  856,  216,  728,
-        472,  984,   56,  568,  312,  824,  184,  696,  440,  952,
-        120,  632,  376,  888,  248,  760,  504, 1016,    4,  516,
-        260,  772,  132,  644,  388,  900,   68,  580,  324,  836,
-        196,  708,  452,  964,   36,  548,  292,  804,  164,  676,
-        420,  932,  100,  612,  356,  868,  228,  740,  484,  996,
-         20,  532,  276,  788,  148,  660,  404,  916,   84,  596,
-        340,  852,  212,  724,  468,  980,   52,  564,  308,  820,
-        180,  692,  436,  948,  116,  628,  372,  884,  244,  756,
-        500, 1012,   12,  524,  268,  780,  140,  652,  396,  908,
-
-         76,  588,  332,  844,  204,  716,  460,  972,   44,  556,
-        300,  812,  172,  684,  428,  940,  108,  620,  364,  876,
-        236,  748,  492, 1004,   28,  540,  284,  796,  156,  668,
-        412,  924,   92,  604,  348,  860,  220,  732,  476,  988,
-         60,  572,  316,  828,  188,  700,  444,  956,  124,  636,
-        380,  892,  252,  764,  508, 1020,    2,  514,  258,  770,
-        130,  642,  386,  898,   66,  578,  322,  834,  194,  706,
-        450,  962,   34,  546,  290,  802,  162,  674,  418,  930,
-         98,  610,  354,  866,  226,  738,  482,  994,   18,  530,
-        274,  786,  146,  658,  402,  914,   82,  594,  338,  850,
-
-        210,  722,  466,  978,   50,  562,  306,  818,  178,  690,
-        434,  946,  114,  626,  370,  882,  242,  754,  498, 1010,
-         10,  522,  266,  778,  138,  650,  394,  906,   74,  586,
-        330,  842,  202,  714,  458,  970,   42,  554,  298,  810,
-        170,  682,  426,  938,  106,  618,  362,  874,  234,  746,
-        490, 1002,   26,  538,  282,  794,  154,  666,  410,  922,
-         90,  602,  346,  858,  218,  730,  474,  986,   58,  570,
-        314,  826,  186,  698,  442,  954,  122,  634,  378,  890,
-        250,  762,  506, 1018,    6,  518,  262,  774,  134,  646,
-        390,  902,   70,  582,  326,  838,  198,  710,  454,  966,
-
-         38,  550,  294,  806,  166,  678,  422,  934,  102,  614,
-        358,  870,  230,  742,  486,  998,   22,  534,  278,  790,
-        150,  662,  406,  918,   86,  598,  342,  854,  214,  726,
-        470,  982,   54,  566,  310,  822,  182,  694,  438,  950,
-        118,  630,  374,  886,  246,  758,  502, 1014,   14,  526,
-        270,  782,  142,  654,  398,  910,   78,  590,  334,  846,
-        206,  718,  462,  974,   46,  558,  302,  814,  174,  686,
-        430,  942,  110,  622,  366,  878,  238,  750,  494, 1006,
-         30,  542,  286,  798,  158,  670,  414,  926,   94,  606,
-        350,  862,  222,  734,  478,  990,   62,  574,  318,  830,
-
-        190,  702,  446,  958,  126,  638,  382,  894,  254,  766,
-        510, 1022,    1,  513,  257,  769,  129,  641,  385,  897,
-         65,  577,  321,  833,  193,  705,  449,  961,   33,  545,
-        289,  801,  161,  673,  417,  929,   97,  609,  353,  865,
-        225,  737,  481,  993,   17,  529,  273,  785,  145,  657,
-        401,  913,   81,  593,  337,  849,  209,  721,  465,  977,
-         49,  561,  305,  817,  177,  689,  433,  945,  113,  625,
-        369,  881,  241,  753,  497, 1009,    9,  521,  265,  777,
-        137,  649,  393,  905,   73,  585,  329,  841,  201,  713,
-        457,  969,   41,  553,  297,  809,  169,  681,  425,  937,
-
-        105,  617,  361,  873,  233,  745,  489, 1001,   25,  537,
-        281,  793,  153,  665,  409,  921,   89,  601,  345,  857,
-        217,  729,  473,  985,   57,  569,  313,  825,  185,  697,
-        441,  953,  121,  633,  377,  889,  249,  761,  505, 1017,
-          5,  517,  261,  773,  133,  645,  389,  901,   69,  581,
-        325,  837,  197,  709,  453,  965,   37,  549,  293,  805,
-        165,  677,  421,  933,  101,  613,  357,  869,  229,  741,
-        485,  997,   21,  533,  277,  789,  149,  661,  405,  917,
-         85,  597,  341,  853,  213,  725,  469,  981,   53,  565,
-        309,  821,  181,  693,  437,  949,  117,  629,  373,  885,
-
-        245,  757,  501, 1013,   13,  525,  269,  781,  141,  653,
-        397,  909,   77,  589,  333,  845,  205,  717,  461,  973,
-         45,  557,  301,  813,  173,  685,  429,  941,  109,  621,
-        365,  877,  237,  749,  493, 1005,   29,  541,  285,  797,
-        157,  669,  413,  925,   93,  605,  349,  861,  221,  733,
-        477,  989,   61,  573,  317,  829,  189,  701,  445,  957,
-        125,  637,  381,  893,  253,  765,  509, 1021,    3,  515,
-        259,  771,  131,  643,  387,  899,   67,  579,  323,  835,
-        195,  707,  451,  963,   35,  547,  291,  803,  163,  675,
-        419,  931,   99,  611,  355,  867,  227,  739,  483,  995,
-
-         19,  531,  275,  787,  147,  659,  403,  915,   83,  595,
-        339,  851,  211,  723,  467,  979,   51,  563,  307,  819,
-        179,  691,  435,  947,  115,  627,  371,  883,  243,  755,
-        499, 1011,   11,  523,  267,  779,  139,  651,  395,  907,
-         75,  587,  331,  843,  203,  715,  459,  971,   43,  555,
-        299,  811,  171,  683,  427,  939,  107,  619,  363,  875,
-        235,  747,  491, 1003,   27,  539,  283,  795,  155,  667,
-        411,  923,   91,  603,  347,  859,  219,  731,  475,  987,
-         59,  571,  315,  827,  187,  699,  443,  955,  123,  635,
-        379,  891,  251,  763,  507, 1019,    7,  519,  263,  775,
-
-        135,  647,  391,  903,   71,  583,  327,  839,  199,  711,
-        455,  967,   39,  551,  295,  807,  167,  679,  423,  935,
-        103,  615,  359,  871,  231,  743,  487,  999,   23,  535,
-        279,  791,  151,  663,  407,  919,   87,  599,  343,  855,
-        215,  727,  471,  983,   55,  567,  311,  823,  183,  695,
-        439,  951,  119,  631,  375,  887,  247,  759,  503, 1015,
-         15,  527,  271,  783,  143,  655,  399,  911,   79,  591,
-        335,  847,  207,  719,  463,  975,   47,  559,  303,  815,
-        175,  687,  431,  943,  111,  623,  367,  879,  239,  751,
-        495, 1007,   31,  543,  287,  799,  159,  671,  415,  927,
-
-         95,  607,  351,  863,  223,  735,  479,  991,   63,  575,
-        319,  831,  191,  703,  447,  959,  127,  639,  383,  895,
-        255,  767,  511, 1023
-};
-
-bliss_fft_params_t bliss_fft_12289_1024 = {
-       12289, 12287, 18, 3186, (1<<18)-1, 1024, 12277, 10,
-       wr_12289_1024, wf_12289_1024, wi_12289_1024, 1, rev_1024
-};
-
-/**
- * FFT phase shift and scaling inverse transform for q = 12289 and n = 512
- */
-static uint16_t wi_12289_512[] = {
-       12265,  6771, 11424,  9011,  6203, 11914,  9021,  6454,  7154,   146,
-       11038,  4238,  5604, 10397, 11498,  3495,  7846,  7684,  1160,  4538,
-         845,  2776,  3317,  5836,  6389, 11667,  6508,  1136, 11309, 12269,
-       11787,  9520,  5461,  3121,  5832,  1373,  1282, 10058,  4218,  5102,
-        7628,  4670,  6616,  1389,  9057,  2442,  2307,  5063,  7878, 10945,
-       10506,   716,   767,  3276,  3578,  1327,  5043,  7376,  8176,  3678,
-        3837,  6599,  4649,  4860, 11385,  9261,   189,  3515,  8348, 10453,
-        7988,  1417,  7302,  1403,  2035,  8067,  2171,  6565, 11169,  8755,
-        4693, 10880,  2730,  7078,  3154, 10347, 10243,  2717,  3065,  9342,
-        3451,  1826,  4050,  3343,  1573,  6302,   881, 11053, 10759, 10753,
-
-        3229,  6085, 11410,  3744,   578, 12050,  7519,  3163,  9344,  5959,
-         874,  2275,  1802, 10821,  2478, 10584,   216,   506,  7785,  4924,
-        5618,  3375,  4834,  3359,  9348, 10975, 11259, 11014, 11009,  4739,
-        7119,  5412,  3120,  4578,  1849,  8314,  4684, 11883,  7014,  8921,
-        3944,  5598,  2873,  2065,  8820,   180,  4518,   343,     7,  8778,
-        8957, 12221,   751,  7790, 11194,  3238,  5082,  7126,  1901, 12077,
-        4510,  2600,  3815,  3589,  2832, 12096,  3758,  5845,  5386,  7383,
-        4665,   346,  3769,  7350,   150,  3765,  2334,  2054,  7315,  5416,
-        8136,  2674, 10588,  5232, 10891,  4235,  1842, 11825,  8016, 11951,
-        6263,  1131,  5039,  2360, 10080,  7228,  6919,   392,     8, 10032,
-
-        8481,  5189,  6125,   125,  9282,  1945,  5808,  8144,   417,  6780,
-       10421,  4727,  4360, 11124,  1481,  1535,  7806,  6680,  7911,  3171,
-        7087,  2151,  6063,  8400,  1927,  7814,  4423,  4103,  8360,   923,
-        2276,  3056, 10345,  7735,  3669,  4840, 10883,  6492,  5650,  6636,
-        1891, 11826,  9270, 11475, 11520,  6505,  9663,   448,  8787,  7954,
-        7937, 11197,  7000,  3654, 10608,  5734,  1371, 11063, 11010,  5993,
-        6643, 10669,  8494,  9202, 12226,  7021,  5410,   612,  5530,  3624,
-        9855,  7725,  3418,  9600,  7469,  1908,  8566,  1178,  2532,  4566,
-       11379,  1737,  3045,  8840,   682,  7287,  7171,  9175,  2946,  7584,
-       10939,  2982,  3572,  6092,  7899,   412,   510,   512,  3020,  2068,
-
-         293, 11041,  8000,  4176,  1590,  3042,  5078,  2110,  3805,  3338,
-        7592,  8682, 11463,  8761, 12217,  8024,  9694,  2455,  6320, 11164,
-        2485,  7073,  9173,   438,  8536,   425,  4523,  6613,  9916, 10485,
-       11249, 10763,  3480,  1325,  2535,  8328,  9951,  5219,  6878, 10423,
-        7235,  3408,  9349, 12229, 10783,  3982,  4094,  9363,  5207,  4119,
-        3846,  5596,   365,  3017, 10595,  1721,  7559,  4167,  2593,  7326,
-        6921,  2900, 11345,  8257,  6940,  2148,  2301,  9828, 10734,  3981,
-        2840,  9839, 12239, 11034, 11511,  7508,  1658,  2291,  9577,  3205,
-         567, 10545,   466,  6781, 11675,  4251,  9617,  4209,  6105, 11912,
-        6513,  7406,  8929,  1687,  1790,  8062,  8190,  8945,  9462,  6463,
-
-        6151,  8151,  9195,  3448, 10353,  5478, 12150, 10029,  4719,  6617,
-        2643,  8581,  7699,  7681,  9687,  5966,  9652, 11232,  1734, 11572,
-       10268,  9489,  3454,  5588,  2622,  6825,  5406,  7885,  7434,  7174,
-         648,  1518, 11066,  2483,  4565, 10125,  2213, 10077,  3466,  8347,
-        9199,  8464,  8449,  1928,  9068,  3947,  9360,  1445,  5547,   364,
-        1763, 11071,  8753,  2185, 11832,  4505,  8619,  6195,  1882,   540,
-        1265,  1029,    21,  1756,  2293, 12085,  2253, 11081,  9004,  9714,
-        2957,  9089,  5703, 11653,  1241,  7800, 11445, 10767,  8496, 11710,
-       11274,  5246,  3869,  9860,  1706,  1038, 11307,  9761,   450, 11295,
-        7002,  6162,  9656,  3959, 12119,  8022,  7186,  3407,  8095,   416,
-
-        5526, 10897, 11759, 11275,  6500,  3393,  2828,  7080,  5662,  9395,
-        8468,  1176
-};
-
-/**
- * Bit-reversed indices for n = 512
- */
-static uint16_t rev_512[] = {
-         0, 256, 128, 384,  64, 320, 192, 448,  32, 288, 
-       160, 416,  96, 352, 224, 480,  16, 272, 144, 400,
-        80, 336, 208, 464,  48, 304, 176, 432, 112, 368,
-       240, 496,   8, 264, 136, 392,  72, 328, 200, 456,
-        40, 296, 168, 424, 104, 360, 232, 488,  24, 280,
-       152, 408,  88, 344, 216, 472,  56, 312, 184, 440,
-       120, 376, 248, 504,   4, 260, 132, 388,  68, 324,
-       196, 452,  36, 292, 164, 420, 100, 356, 228, 484,
-        20, 276, 148, 404,  84, 340, 212, 468,  52, 308,
-       180, 436, 116, 372, 244, 500,  12, 268, 140, 396,
-
-        76, 332, 204, 460,  44, 300, 172, 428, 108, 364,
-       236, 492,  28, 284, 156, 412,  92, 348, 220, 476,
-        60, 316, 188, 444, 124, 380, 252, 508,   2, 258,
-       130, 386,  66, 322, 194, 450,  34, 290, 162, 418,
-        98, 354, 226, 482,  18, 274, 146, 402,  82, 338,
-       210, 466,  50, 306, 178, 434, 114, 370, 242, 498,
-        10, 266, 138, 394,  74, 330, 202, 458,  42, 298,
-       170, 426, 106, 362, 234, 490,  26, 282, 154, 410,
-        90, 346, 218, 474,  58, 314, 186, 442, 122, 378,
-       250, 506,   6, 262, 134, 390,  70, 326, 198, 454,
-
-        38, 294, 166, 422, 102, 358, 230, 486,  22, 278,
-       150, 406,  86, 342, 214, 470,  54, 310, 182, 438,
-       118, 374, 246, 502,  14, 270, 142, 398,  78, 334,
-       206, 462,  46, 302, 174, 430, 110, 366, 238, 494,
-        30, 286, 158, 414,  94, 350, 222, 478,  62, 318,
-       190, 446, 126, 382, 254, 510,   1, 257, 129, 385,
-        65, 321, 193, 449,  33, 289, 161, 417,  97, 353,
-       225, 481,  17, 273, 145, 401,  81, 337, 209, 465,
-        49, 305, 177, 433, 113, 369, 241, 497,   9, 265,
-       137, 393,  73, 329, 201, 457,  41, 297, 169, 425,
-
-       105, 361, 233, 489,  25, 281, 153, 409,  89, 345,
-       217, 473,  57, 313, 185, 441, 121, 377, 249, 505,
-         5, 261, 133, 389,  69, 325, 197, 453,  37, 293,
-       165, 421, 101, 357, 229, 485,  21, 277, 149, 405,
-        85, 341, 213, 469,  53, 309, 181, 437, 117, 373,
-       245, 501,  13, 269, 141, 397,  77, 333, 205, 461,
-        45, 301, 173, 429, 109, 365, 237, 493,  29, 285,
-       157, 413,  93, 349, 221, 477,  61, 317, 189, 445,
-       125, 381, 253, 509,   3, 259, 131, 387,  67, 323,
-       195, 451,  35, 291, 163, 419,  99, 355, 227, 483,
-
-        19, 275, 147, 403,  83, 339, 211, 467,  51, 307,
-       179, 435, 115, 371, 243, 499,  11, 267, 139, 395,
-        75, 331, 203, 459,  43, 299, 171, 427, 107, 363,
-       235, 491,  27, 283, 155, 411,  91, 347, 219, 475,
-        59, 315, 187, 443, 123, 379, 251, 507,   7, 263,
-       135, 391,  71, 327, 199, 455,  39, 295, 167, 423,
-       103, 359, 231, 487,  23, 279, 151, 407,  87, 343,
-       215, 471,  55, 311, 183, 439, 119, 375, 247, 503,
-        15, 271, 143, 399,  79, 335, 207, 463,  47, 303,
-       175, 431, 111, 367, 239, 495,  31, 287, 159, 415,
-
-        95, 351, 223, 479,  63, 319, 191, 447, 127, 383,
-       255, 511
-};
-
-bliss_fft_params_t bliss_fft_12289_512 = {
-       12289, 12287, 18, 3186, (1<<18)-1, 512, 12265, 9,
-       wr_12289_1024, wf_12289_1024, wi_12289_512, 2, rev_512
-};
-
-/**
- * FFT twiddle factors in Montgomery form for q = 17 and n = 8
- */
-static uint16_t wr_17_8[] = { 15, 16, 8, 4, 2, 1, 9, 13, 15 };
-
-/**
- * FFT phase shift in forward transform for q = 17 and n = 8
- */
-static uint16_t wf_17_8[] = { 4, 12, 2, 6, 1, 3, 9, 10 };
-
-/**
- * FFT phase shift and scaling inverse transform for q = 17 and n = 8
- */
-static uint16_t wi_17_8[] = { 15, 5, 13, 10, 9, 3, 1, 6 };
-
-/**
- * Bit-reversed indices for n = 8
- */
-static uint16_t rev_8[] = { 0, 4, 2, 6, 1, 5, 3, 7 };
-
-bliss_fft_params_t bliss_fft_17_8 = {
-       17, 15, 5, 4, (1<<5)-1, 8, 15, 3, wr_17_8, wf_17_8, wi_17_8, 1, rev_8
-};
diff --git a/src/libstrongswan/plugins/bliss/bliss_fft_params.h b/src/libstrongswan/plugins/bliss/bliss_fft_params.h
deleted file mode 100644 (file)
index 0ed49b2..0000000
+++ /dev/null
@@ -1,115 +0,0 @@
-/*
- * Copyright (C) 2014-2016 Andreas Steffen
- * HSR Hochschule fuer Technik Rapperswil
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
- *
- * This program 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 General Public License
- * for more details.
- */
-
-/**
- * @defgroup bliss_fft_params bliss_fft_params
- * @{ @ingroup bliss_p
- */
-
-#ifndef BLISS_FFT_PARAMS_H_
-#define BLISS_FFT_PARAMS_H_
-
-#include <library.h>
-
-typedef struct bliss_fft_params_t bliss_fft_params_t;
-
-/**
- * Defines the parameters for an NTT computed via the FFT algorithm
- */
-struct bliss_fft_params_t {
-
-       /**
-        * Prime modulus
-        */
-       uint16_t q;
-
-       /**
-        * Inverse of Prime modulus (-q_inv * q mod r = 1)
-        */
-       uint16_t q_inv;
-
-       /**
-        * Logarithm of Montgomery radix: log2(r)
-        */
-       uint16_t rlog;
-
-       /**
-        * Square of Montgomery radix: r^2 mod q
-        */
-       uint32_t r2;
-
-       /**
-        * Montgomery radix mask: (1<<rlog) - 1
-        */
-       uint32_t rmask;
-
-       /**
-        * Size of the FFT with the condition k * n = q-1
-        */
-       uint16_t n;
-
-       /**
-        * Inverse of n mod q used for normalization of the FFT
-        */
-       uint16_t n_inv;
-
-       /**
-        * Number of FFT stages  stages = log2(n)
-        */
-       uint16_t stages;
-
-       /**
-        * FFT twiddle factors (n-th roots of unity) in Montgomery form
-        */
-       uint16_t *wr;
-
-       /**
-        * FFT phase shift (2n-th roots of unity) in forward transform
-        */
-       uint16_t *wf;
-
-       /**
-        * FFT phase shift (2n-th roots of unity) and scaling in inverse transform
-        */
-       uint16_t *wi;
-
-       /**
-        * Subsampling of FFT twiddle factors table
-        */
-       uint16_t s;
-
-       /**
-        * FFT bit reversal
-        */
-       uint16_t *rev;
-
-};
-
-/**
- * FFT parameters for q = 12289 and n = 1024
- */
-extern bliss_fft_params_t bliss_fft_12289_1024;
-
-/**
- * FFT parameters for q = 12289 and n = 512
- */
-extern bliss_fft_params_t bliss_fft_12289_512;
-
-/**
- * FFT parameters for q = 17 and n = 8
- */
-extern bliss_fft_params_t bliss_fft_17_8;
-
-#endif /** BLISS_FFT_PARAMS_H_ @}*/
index 3781a58..80a7c0d 100644 (file)
@@ -131,7 +131,7 @@ static bliss_param_set_t bliss_param_sets[] = {
                .q2_inv = 6145,
                .n = 512,
                .n_bits = 9,
-               .fft_params = &bliss_fft_12289_512,
+               .fft_params = &ntt_fft_12289_512,
                .non_zero1 = 154,
                .non_zero2 = 0,
                .kappa = 23,
@@ -161,7 +161,7 @@ static bliss_param_set_t bliss_param_sets[] = {
                .q2_inv = 6145,
                .n = 512,
                .n_bits = 9,
-               .fft_params = &bliss_fft_12289_512,
+               .fft_params = &ntt_fft_12289_512,
                .non_zero1 = 216,
                .non_zero2 = 16,
                .kappa = 30,
@@ -191,7 +191,7 @@ static bliss_param_set_t bliss_param_sets[] = {
                .q2_inv = 6145,
                .n = 512,
                .n_bits = 9,
-               .fft_params = &bliss_fft_12289_512,
+               .fft_params = &ntt_fft_12289_512,
                .non_zero1 = 231,
                .non_zero2 = 31,
                .kappa = 39,
@@ -221,7 +221,7 @@ static bliss_param_set_t bliss_param_sets[] = {
                .q2_inv = 6145,
                .n = 512,
                .n_bits = 9,
-               .fft_params = &bliss_fft_12289_512,
+               .fft_params = &ntt_fft_12289_512,
                .non_zero1 = 154,
                .non_zero2 = 0,
                .kappa = 23,
@@ -251,7 +251,7 @@ static bliss_param_set_t bliss_param_sets[] = {
                .q2_inv = 6145,
                .n = 512,
                .n_bits = 9,
-               .fft_params = &bliss_fft_12289_512,
+               .fft_params = &ntt_fft_12289_512,
                .non_zero1 = 216,
                .non_zero2 = 16,
                .kappa = 30,
@@ -281,7 +281,7 @@ static bliss_param_set_t bliss_param_sets[] = {
                .q2_inv = 6145,
                .n = 512,
                .n_bits = 9,
-               .fft_params = &bliss_fft_12289_512,
+               .fft_params = &ntt_fft_12289_512,
                .non_zero1 = 231,
                .non_zero2 = 31,
                .kappa = 39,
index 33a8009..19fdc48 100644 (file)
@@ -24,7 +24,7 @@
 typedef enum bliss_param_set_id_t bliss_param_set_id_t;
 typedef struct bliss_param_set_t bliss_param_set_t;
 
-#include "bliss_fft_params.h"
+#include "ntt_fft_params.h"
 #include "bliss_huffman_code.h"
 
 #include <library.h>
@@ -93,7 +93,7 @@ struct bliss_param_set_t {
        /**
         * FFT parameters
         */
-       bliss_fft_params_t *fft_params;
+       ntt_fft_params_t *fft_params;
 
        /**
         * Number of [-1, +1] secret key coefficients
index 68c0ea2..d4cc000 100644 (file)
@@ -20,8 +20,8 @@
 #include "bliss_sampler.h"
 #include "bliss_signature.h"
 #include "bliss_bitpacker.h"
-#include "bliss_fft.h"
-#include "bliss_reduce.h"
+#include "ntt_fft.h"
+#include "ntt_fft_reduce.h"
 
 #include <crypto/mgf1/mgf1_bitspender.h>
 #include <asn1/asn1.h>
@@ -169,7 +169,7 @@ static void greedy_sc(int8_t *s1, int8_t *s2, int n, uint16_t *c_indices,
 static bool sign_bliss(private_bliss_private_key_t *this, hash_algorithm_t alg,
                                           chunk_t data, chunk_t *signature)
 {
-       bliss_fft_t *fft;
+       ntt_fft_t *fft;
        bliss_signature_t *sig;
        bliss_sampler_t *sampler = NULL;
        rng_t *rng;
@@ -247,7 +247,7 @@ static bool sign_bliss(private_bliss_private_key_t *this, hash_algorithm_t alg,
        y2 = z2;
        ud = z2d;
 
-       fft = bliss_fft_create(this->set->fft_params);
+       fft = ntt_fft_create(this->set->fft_params);
 
        /* Use of the enhanced BLISS-B signature algorithm? */
        switch (this->set->id)
@@ -343,7 +343,7 @@ static bool sign_bliss(private_bliss_private_key_t *this, hash_algorithm_t alg,
 
                for (i = 0; i < n; i++)
                {
-                       ay[i] = bliss_mreduce(this->Ar[i] * ay[i], this->set->fft_params);
+                       ay[i] = ntt_fft_mreduce(this->Ar[i] * ay[i], this->set->fft_params);
                }
                fft->transform(fft, ay, ay, TRUE);
 
@@ -819,11 +819,11 @@ static uint32_t invert(private_bliss_private_key_t *this, uint32_t x)
        }
        for (i = 1; i <= i_max; i++)
        {
-               x2 = bliss_mreduce(x2 * x2, this->set->fft_params);
+               x2 = ntt_fft_mreduce(x2 * x2, this->set->fft_params);
 
                if (q2 & (1 << i))
                {
-                       x1 = bliss_mreduce(x1 * x2, this->set->fft_params);
+                       x1 = ntt_fft_mreduce(x1 * x2, this->set->fft_params);
                }
        }
 
@@ -1008,7 +1008,7 @@ bliss_private_key_t *bliss_private_key_gen(key_type_t type, va_list args)
        uint16_t q;
        bool success = FALSE;
        bliss_param_set_t *set;
-       bliss_fft_t *fft;
+       ntt_fft_t *fft;
        rng_t *rng;
 
        while (TRUE)
@@ -1069,7 +1069,7 @@ bliss_private_key_t *bliss_private_key_gen(key_type_t type, va_list args)
        this->set = set;
 
        /* We derive the public key from the private key using the FFT */
-       fft = bliss_fft_create(set->fft_params);
+       fft = ntt_fft_create(set->fft_params);
 
        /* Some vectors needed to derive the publi key */
        S1 = malloc(n * sizeof(uint32_t));
@@ -1113,8 +1113,8 @@ bliss_private_key_t *bliss_private_key_gen(key_type_t type, va_list args)
                                break;
                        }
                        this->Ar[i] = invert(this, S1[i]);
-                       this->Ar[i] = bliss_mreduce(S2[i] * this->Ar[i], set->fft_params);
-                       this->A[i]  = bliss_mreduce(this->Ar[i], set->fft_params);
+                       this->Ar[i] = ntt_fft_mreduce(S2[i] * this->Ar[i], set->fft_params);
+                       this->A[i]  = ntt_fft_mreduce(this->Ar[i], set->fft_params);
                }
        }
        while (!success && trials < SECRET_KEY_TRIALS_MAX);
@@ -1131,7 +1131,7 @@ bliss_private_key_t *bliss_private_key_gen(key_type_t type, va_list args)
                {
                        DBG4(DBG_LIB, "%4d %3d %3d %5u %5u %5u %5u",
                                                  i, this->s1[i], this->s2[i],
-                                                 bliss_mreduce(a[i], set->fft_params),
+                                                 ntt_fft_mreduce(a[i], set->fft_params),
                                                  S1[i], S2[i], this->A[i]);
                }
        }
@@ -1265,8 +1265,8 @@ bliss_private_key_t *bliss_private_key_load(key_type_t type, va_list args)
 
                                for (i = 0; i < this->set->n; i++)
                                {
-                                       this->Ar[i] = bliss_mreduce(this->A[i] * r2,
-                                                                                               this->set->fft_params);
+                                       this->Ar[i] = ntt_fft_mreduce(this->A[i] * r2,
+                                                                                                 this->set->fft_params);
                                }
                                break;
                        case PRIV_KEY_SECRET1:
index 2f63fdb..1016aec 100644 (file)
@@ -16,8 +16,8 @@
 #include "bliss_public_key.h"
 #include "bliss_signature.h"
 #include "bliss_bitpacker.h"
-#include "bliss_fft.h"
-#include "bliss_reduce.h"
+#include "ntt_fft.h"
+#include "ntt_fft_reduce.h"
 #include "bliss_utils.h"
 
 #include <asn1/asn1.h>
@@ -77,7 +77,7 @@ static bool verify_bliss(private_bliss_public_key_t *this, hash_algorithm_t alg,
        chunk_t data_hash;
        hasher_t *hasher;
        hash_algorithm_t oracle_alg;
-       bliss_fft_t *fft;
+       ntt_fft_t *fft;
        bliss_signature_t *sig;
        bool success = FALSE;
 
@@ -126,12 +126,12 @@ static bool verify_bliss(private_bliss_public_key_t *this, hash_algorithm_t alg,
        {
                az[i] = z1[i] < 0 ? q + z1[i] : z1[i];
        }
-       fft = bliss_fft_create(this->set->fft_params);
+       fft = ntt_fft_create(this->set->fft_params);
        fft->transform(fft, az, az, FALSE);
 
        for (i = 0; i < n; i++)
        {
-               az[i] = bliss_mreduce(this->Ar[i] * az[i], this->set->fft_params);
+               az[i] = ntt_fft_mreduce(this->Ar[i] * az[i], this->set->fft_params);
        }
        fft->transform(fft, az, az, TRUE);
 
@@ -393,8 +393,8 @@ bliss_public_key_t *bliss_public_key_load(key_type_t type, va_list args)
 
                                for (i = 0; i < this->set->n; i++)
                                {
-                                       this->Ar[i] = bliss_mreduce(this->A[i] * r2,
-                                                                                               this->set->fft_params);
+                                       this->Ar[i] = ntt_fft_mreduce(this->A[i] * r2,
+                                                                                                 this->set->fft_params);
                                }
                                break;
                }
diff --git a/src/libstrongswan/plugins/bliss/bliss_reduce.h b/src/libstrongswan/plugins/bliss/bliss_reduce.h
deleted file mode 100644 (file)
index 2a53d9a..0000000
+++ /dev/null
@@ -1,42 +0,0 @@
-/*
- * Copyright (C) 2016 Andreas Steffen
- * HSR Hochschule fuer Technik Rapperswil
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
- *
- * This program 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 General Public License
- * for more details.
- */
-
-/**
- * @defgroup bliss_fft bliss_fft
- * @{ @ingroup bliss_p
- */
-
-#ifndef BLISS_REDUCE_H_
-#define BLISS_REDUCE_H_
-
-#include "bliss_fft_params.h"
-
-/**
- * Montgomery Reduction
- *
- * Montgomery, P. L. Modular multiplication without trial division.
- * Mathematics of Computation 44, 170 (1985), 519–521.
- */
-static inline uint32_t bliss_mreduce(uint32_t x, bliss_fft_params_t *p)
-{
-       uint32_t m, t;
-       
-       m = (x * p->q_inv) & p->rmask;
-       t = (x + m * p->q) >> p->rlog;
-
-       return (t < p->q) ? t : t - p->q;
-}
-
-#endif /** BLISS_REDUCE_H_ @}*/
index bd87753..1ec8d55 100644 (file)
@@ -3,7 +3,6 @@ TESTS = bliss_tests
 check_PROGRAMS = $(TESTS)
 
 bliss_tests_SOURCES = \
-       suites/test_bliss_fft.c \
        suites/test_bliss_bitpacker.c \
        suites/test_bliss_huffman.c \
        suites/test_bliss_keys.c \
@@ -15,6 +14,7 @@ bliss_tests_SOURCES = \
 bliss_tests_CFLAGS = \
        -I$(top_srcdir)/src/libstrongswan \
        -I$(top_srcdir)/src/libstrongswan/tests \
+       -I$(top_srcdir)/src/libstrongswan/math/libnttfft \
        -I$(top_srcdir)/src/libstrongswan/plugins/bliss \
        -DPLUGINDIR=\""$(abs_top_builddir)/src/libstrongswan/plugins\"" \
        -DPLUGINS=\""${s_plugins}\"" \
@@ -24,4 +24,5 @@ bliss_tests_LDFLAGS = @COVERAGE_LDFLAGS@
 bliss_tests_LDADD = \
        $(top_builddir)/src/libstrongswan/libstrongswan.la \
        $(top_builddir)/src/libstrongswan/tests/libtest.la \
+       $(top_builddir)/src/libstrongswan/math/libnttfft/libnttfft.la \
        ../libbliss.la
index f0959cc..61f37d5 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014-2015 Andreas Steffen
+ * Copyright (C) 2014-2016 Andreas Steffen
  * HSR Hochschule fuer Technik Rapperswil
  *
  * This program is free software; you can redistribute it and/or modify it
@@ -13,7 +13,6 @@
  * for more details.
  */
 
-TEST_SUITE(bliss_fft_suite_create)
 TEST_SUITE(bliss_bitpacker_suite_create)
 TEST_SUITE(bliss_huffman_suite_create)
 TEST_SUITE(bliss_keys_suite_create)
diff --git a/src/libstrongswan/plugins/bliss/tests/suites/test_bliss_fft.c b/src/libstrongswan/plugins/bliss/tests/suites/test_bliss_fft.c
deleted file mode 100644 (file)
index d1328cb..0000000
+++ /dev/null
@@ -1,154 +0,0 @@
-/*
- * Copyright (C) 2014-2016 Andreas Steffen
- * HSR Hochschule fuer Technik Rapperswil
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2 of the License, or (at your
- * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
- *
- * This program 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 General Public License
- * for more details.
- */
-
-#include "test_suite.h"
-
-#include <bliss_fft.h>
-#include <bliss_reduce.h>
-
-#include <time.h>
-
-static bliss_fft_params_t *fft_params[] = {
-       &bliss_fft_17_8,
-       &bliss_fft_12289_512,
-       &bliss_fft_12289_1024
-};
-
-START_TEST(test_bliss_fft_impulse)
-{
-       bliss_fft_t *fft;
-       uint16_t n = fft_params[_i]->n;
-       uint32_t rq = (1 << fft_params[_i]->rlog) % fft_params[_i]->q;
-       uint32_t x[n], X[n];
-       int i;
-
-       for (i = 0; i < n; i++)
-       {
-               x[i] = 0;
-       }
-       x[0] = 1;
-       fft = bliss_fft_create(fft_params[_i]);
-       fft->transform(fft, x, X, FALSE);
-
-       for (i = 0; i < n; i++)
-       {
-               ck_assert(X[i] == rq);
-       }
-       fft->transform(fft, X, x, TRUE);
-
-       for (i = 0; i < n; i++)
-       {
-               ck_assert(x[i] == (i == 0));
-       }
-       fft->destroy(fft);
-}
-END_TEST
-
-START_TEST(test_bliss_fft_wrap)
-{
-       bliss_fft_t *fft;
-       uint16_t n = fft_params[_i]->n;
-       uint16_t q = fft_params[_i]->q;
-       uint32_t x[n],y[n], X[n], Y[n];
-       int i, j;
-
-       for (i = 0; i < n; i++)
-       {
-               x[i] = i;
-               y[i] = 0;
-       }
-       fft = bliss_fft_create(fft_params[_i]);
-       ck_assert(fft->get_size(fft) == n);
-       ck_assert(fft->get_modulus(fft) == q); 
-       fft->transform(fft, x, X, FALSE);
-
-       for (j = 0; j < n; j++)
-       {
-               y[j] = 1;
-               fft->transform(fft, y, Y, FALSE);
-
-               for (i = 0; i < n; i++)
-               {
-                       Y[i] = bliss_mreduce(X[i] * Y[i], fft_params[_i]);
-               }
-               fft->transform(fft, Y, Y, TRUE);
-
-               for (i = 0; i < n; i++)
-               {
-                       ck_assert(Y[i] == ( i < j ? q - n - i + j : i - j));
-               }
-               y[j] = 0;
-       }
-       fft->destroy(fft);  
-}
-END_TEST
-
-START_TEST(test_bliss_fft_speed)
-{
-       bliss_fft_t *fft;
-       struct timespec start, stop;
-       int i, m, count = 10000;
-       int n = fft_params[_i]->n;
-       uint32_t x[n], X[n];
-
-       for (i = 0; i < n; i++)
-       {
-               x[i] = i;
-       }
-       fft = bliss_fft_create(fft_params[_i]);
-
-       clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
-       for (m = 0; m < count; m++)
-       {
-               fft->transform(fft, x, X, FALSE);
-               fft->transform(fft, X, x, TRUE);
-       }
-       clock_gettime(CLOCK_THREAD_CPUTIME_ID, &stop);
-
-       DBG0(DBG_LIB, "%d FFT-%d loops in %d ms\n", count, n,
-                                 (stop.tv_nsec - start.tv_nsec) / 1000000 +
-                                 (stop.tv_sec - start.tv_sec) * 1000);
-
-       for (i = 0; i < n; i++)
-       {
-               ck_assert(x[i] == i);
-       }
-       fft->destroy(fft);
-}
-END_TEST
-
-Suite *bliss_fft_suite_create()
-{
-       Suite *s;
-       TCase *tc;
-
-       s = suite_create("bliss_fft");
-
-       tc = tcase_create("impulse");
-       tcase_add_loop_test(tc, test_bliss_fft_impulse, 0, countof(fft_params));
-       suite_add_tcase(s, tc);
-
-       tc = tcase_create("negative_wrap");
-       tcase_add_loop_test(tc, test_bliss_fft_wrap, 0, countof(fft_params));
-       suite_add_tcase(s, tc);
-
-       tc = tcase_create("speed");
-       tcase_set_timeout(tc, 10);
-       tcase_add_loop_test(tc, test_bliss_fft_speed, 1, countof(fft_params));
-       suite_add_tcase(s, tc);
-
-       return s;
-}