Implemented FFT with n = 1024 and q = 11289 using Montgomery arithmetic
authorAndreas Steffen <andreas.steffen@strongswan.org>
Fri, 22 Jul 2016 14:42:49 +0000 (16:42 +0200)
committerAndreas Steffen <andreas.steffen@strongswan.org>
Fri, 29 Jul 2016 10:36:14 +0000 (12:36 +0200)
src/libstrongswan/plugins/bliss/bliss_fft_params.c
src/libstrongswan/plugins/bliss/bliss_fft_params.h
src/libstrongswan/plugins/bliss/tests/suites/test_bliss_fft.c

index aac5d0f..074d92a 100644 (file)
 #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 = 11289 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, rev_1024
+};
+
+/**
  * FFT twiddle factors in Montgomery form for q = 12289 and n = 512
  */
 static uint16_t wr_12289_512[] = {
@@ -138,7 +619,7 @@ static uint16_t wf_12289_512[] = {
         1000, 12133,  4645,  6403,  6522,    64,  3136,  6196,  8668,  6906,
 
         6591,  3445,  9048,   948,  9585,  2683,  8577,  2447,  9302,  1105,
-        4989, 10970,
+        4989, 10970
 };
 
 /**
@@ -201,7 +682,7 @@ static uint16_t wi_12289_512[] = {
         7002,  6162,  9656,  3959, 12119,  8022,  7186,  3407,  8095,   416,
 
         5526, 10897, 11759, 11275,  6500,  3393,  2828,  7080,  5662,  9395,
-        8468,  1176,
+        8468,  1176
 };
 
 /**
index a709ee4..b38479e 100644 (file)
@@ -93,6 +93,11 @@ struct bliss_fft_params_t {
 };
 
 /**
+ * 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;
index ec67f07..d1328cb 100644 (file)
@@ -22,7 +22,8 @@
 
 static bliss_fft_params_t *fft_params[] = {
        &bliss_fft_17_8,
-       &bliss_fft_12289_512
+       &bliss_fft_12289_512,
+       &bliss_fft_12289_1024
 };
 
 START_TEST(test_bliss_fft_impulse)
@@ -99,15 +100,15 @@ START_TEST(test_bliss_fft_speed)
 {
        bliss_fft_t *fft;
        struct timespec start, stop;
-       uint16_t n = bliss_fft_12289_512.n;
-       uint32_t x[n], X[n];
        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(&bliss_fft_12289_512);
+       fft = bliss_fft_create(fft_params[_i]);
 
        clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
        for (m = 0; m < count; m++)
@@ -117,7 +118,7 @@ START_TEST(test_bliss_fft_speed)
        }
        clock_gettime(CLOCK_THREAD_CPUTIME_ID, &stop);
 
-       DBG0(DBG_LIB, "%d FFT loops in %d ms\n", count,
+       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);
 
@@ -146,7 +147,7 @@ Suite *bliss_fft_suite_create()
 
        tc = tcase_create("speed");
        tcase_set_timeout(tc, 10);
-       tcase_add_test(tc, test_bliss_fft_speed);
+       tcase_add_loop_test(tc, test_bliss_fft_speed, 1, countof(fft_params));
        suite_add_tcase(s, tc);
 
        return s;