#include "NTT.h"

const int Rmod_mul_table[NTT_N >> 1] = {
-3050063, -1149528, -2302858, -132780, 3045740, -103466, -3044289, 1686477, -2484496, -60450, -2603529, 184178, 3232854, -1037996, -1315593, -923257, 3225759, -2428258, -1431124, -316317, 2168657, -2923783, -170617, -3065364, -1463241, -3323445, 2966152, -550069, 98138, -2601601, 1191095, 3069551, -2743683, -144858, -660597, 2988693, -1440490, 542147, 42233, 2280251, 798501, -3054418, -2658792, -3024654, 1180913, -2440368, -2180068, -3024785, -2577408, -789061, -1473979, -1871790, -3331397, -3558460, 3438937, 2839152, -3518577, -1588277, 795882, -634030, -384758, -3469197, 2721083, -3335467, -3341808, 365020, -83399, 1725863, 3248967, -334536, 2086389, 1880403, 2914718, -924764, -2745428, -1081296, -1125402, -1327626, 235474, -1467637, -1111230, -3553705, 3522824, 287428, -2157765, 1479754, 1211035, -2837690, -2753738, -2248382, 1630573, -1896338, 1673592, 3256257, 588237, 606079, 2995780, 633752, -1438785, 1665499, -412958, -2598909, 785875, -1507361, 2159637, 2863079, 922769, -489732, -2749359, 1651912, 701468, 3474245, -1841269, 1757547, 1517404, -2872486, -839509, -3131962, -636061, 331360, 1979026, 2136239, 1245434, -1039822, 1174444, -210630, 1308281, 183381, -3483018, 2061534, -768392, -554759, 1195972, 2461031, -3242769, -1719727, 1943974, 117140, 1569501, 1312936, 1469797, -2585433, 3014937, -1251025, -1728603, -1824688, -2735543, -1819612, 1105442, 55875, 3119296, 894462, -1105730, -164584, 2146618, 2973964, -2418224, 1521252, 3382332, -3552899, -3078188, -2447816, 2420598, 2657545, -1407270, -1968501, -2742990, -110541, 1581803, -3083587, -3109151, -2847719, -3144946, -1031268, -1042426, -713251, 2428391, -1395577, 3591341, 469143, 1995867, 892354, 3053079, -2762359, 1354036, 2732487, 3506949, 3562544, -2404006, -1647023, 475268, -1304639, -78472, -2752524, -685338, -2486601, 738397, -2913973, 3420730, -3351503, -134553, 42770, -1348427, -943574, -269813, -610602, 180113, -2036795, -1906959, -362019, 950000, -3013610, -95533, -480612, -692547, 3201046, -1404507, -698310, 825987, -1315536, -178913, -3570625, -1937509, 580793, -2562997, -1586594, -1597047, -2771447, -310187, -1759875, -2485310, 3016005, -705718, -1795755, -3233007, -1519660, 1635541, -1839220, -2179786, -2160794, -803880, -3445475, -2773201, 1793532, -2366129, 3534285, -1150687, -1351910, -2624686, -3130243, 2908900, -646184, 1554680, 390113, 3595566, -2910638
};

const int streamlined_Rmod_root_table[NTT_N << 1] = {
-3050063, -3050063, -1149528, -3050063, -1149528, -2302858, -132780, -3050063, -3050063, -1149528, -3050063, -1149528, -2302858, -132780, -1149528, -2302858, -132780, 3045740, -103466, -3044289, 1686477, -2302858, 3045740, -103466, -2484496, -60450, -2603529, 184178, -132780, -3044289, 1686477, 3232854, -1037996, -1315593, -923257, 3045740, -2484496, -60450, 3225759, -2428258, -1431124, -316317, -103466, -2603529, 184178, 2168657, -2923783, -170617, -3065364, -3044289, 3232854, -1037996, -1463241, -3323445, 2966152, -550069, 1686477, -1315593, -923257, 98138, -2601601, 1191095, 3069551, -3050063, -3050063, -1149528, -3050063, -1149528, -2302858, -132780, -1149528, -2302858, -132780, 3045740, -103466, -3044289, 1686477, -2302858, 3045740, -103466, -2484496, -60450, -2603529, 184178, -132780, -3044289, 1686477, 3232854, -1037996, -1315593, -923257, 3045740, -2484496, -60450, 3225759, -2428258, -1431124, -316317, -103466, -2603529, 184178, 2168657, -2923783, -170617, -3065364, -3044289, 3232854, -1037996, -1463241, -3323445, 2966152, -550069, 1686477, -1315593, -923257, 98138, -2601601, 1191095, 3069551, -2484496, 3225759, -2428258, -2743683, -144858, -660597, 2988693, -60450, -1431124, -316317, -1440490, 542147, 42233, 2280251, -2603529, 2168657, -2923783, 798501, -3054418, -2658792, -3024654, 184178, -170617, -3065364, 1180913, -2440368, -2180068, -3024785, 3232854, -1463241, -3323445, -2577408, -789061, -1473979, -1871790, -1037996, 2966152, -550069, -3331397, -3558460, 3438937, 2839152, -1315593, 98138, -2601601, -3518577, -1588277, 795882, -634030, -923257, 1191095, 3069551, -384758, -3469197, 2721083, -3335467, 3225759, -2743683, -144858, -3341808, 365020, -83399, 1725863, -2428258, -660597, 2988693, 3248967, -334536, 2086389, 1880403, -1431124, -1440490, 542147, 2914718, -924764, -2745428, -1081296, -316317, 42233, 2280251, -1125402, -1327626, 235474, -1467637, 2168657, 798501, -3054418, -1111230, -3553705, 3522824, 287428, -2923783, -2658792, -3024654, -2157765, 1479754, 1211035, -2837690, -170617, 1180913, -2440368, -2753738, -2248382, 1630573, -1896338, -3065364, -2180068, -3024785, 1673592, 3256257, 588237, 606079, -1463241, -2577408, -789061, 2995780, 633752, -1438785, 1665499, -3323445, -1473979, -1871790, -412958, -2598909, 785875, -1507361, 2966152, -3331397, -3558460, 2159637, 2863079, 922769, -489732, -550069, 3438937, 2839152, -2749359, 1651912, 701468, 3474245, 98138, -3518577, -1588277, -1841269, 1757547, 1517404, -2872486, -2601601, 795882, -634030, -839509, -3131962, -636061, 331360, 1191095, -384758, -3469197, 1979026, 2136239, 1245434, -1039822, 3069551, 2721083, -3335467, 1174444, -210630, 1308281, 183381, -2743683, -3341808, 365020, -3483018, 2061534, -768392, -554759, -144858, -83399, 1725863, 1195972, 2461031, -3242769, -1719727, -660597, 3248967, -334536, 1943974, 117140, 1569501, 1312936, 2988693, 2086389, 1880403, 1469797, -2585433, 3014937, -1251025, -1440490, 2914718, -924764, -1728603, -1824688, -2735543, -1819612, 542147, -2745428, -1081296, 1105442, 55875, 3119296, 894462, 42233, -1125402, -1327626, -1105730, -164584, 2146618, 2973964, 2280251, 235474, -1467637, -2418224, 1521252, 3382332, -3552899, 798501, -1111230, -3553705, -3078188, -2447816, 2420598, 2657545, -3054418, 3522824, 287428, -1407270, -1968501, -2742990, -110541, -2658792, -2157765, 1479754, 1581803, -3083587, -3109151, -2847719, -3024654, 1211035, -2837690, -3144946, -1031268, -1042426, -713251, 1180913, -2753738, -2248382, 2428391, -1395577, 3591341, 469143, -2440368, 1630573, -1896338, 1995867, 892354, 3053079, -2762359, -2180068, 1673592, 3256257, 1354036, 2732487, 3506949, 3562544, -3024785, 588237, 606079, -2404006, -1647023, 475268, -1304639, -2577408, 2995780, 633752, -78472, -2752524, -685338, -2486601, -789061, -1438785, 1665499, 738397, -2913973, 3420730, -3351503, -1473979, -412958, -2598909, -134553, 42770, -1348427, -943574, -1871790, 785875, -1507361, -269813, -610602, 180113, -2036795, -3331397, 2159637, 2863079, -1906959, -362019, 950000, -3013610, -3558460, 922769, -489732, -95533, -480612, -692547, 3201046, 3438937, -2749359, 1651912, -1404507, -698310, 825987, -1315536, 2839152, 701468, 3474245, -178913, -3570625, -1937509, 580793, -3518577, -1841269, 1757547, -2562997, -1586594, -1597047, -2771447, -1588277, 1517404, -2872486, -310187, -1759875, -2485310, 3016005, 795882, -839509, -3131962, -705718, -1795755, -3233007, -1519660, -634030, -636061, 331360, 1635541, -1839220, -2179786, -2160794, -384758, 1979026, 2136239, -803880, -3445475, -2773201, 1793532, -3469197, 1245434, -1039822, -2366129, 3534285, -1150687, -1351910, 2721083, 1174444, -210630, -2624686, -3130243, 2908900, -646184, -3335467, 1308281, 183381, 1554680, 390113, 3595566, -2910638
};

const int streamlined_Rmod_root_table_small[8] = {
-3050063, -3050063, -1149528, 1, -2550030, 1446306, -2993116,
};

const int streamlined_Rmod_inv_GS_root_table[NTT_N << 1] = {
-3050063, -3050063, 1149528, -3050063, 1149528, 132780, 2302858, -3050063, -3050063, 1149528, -3050063, 1149528, 132780, 2302858, 1149528, 132780, 2302858, -1686477, 3044289, 103466, -3045740, 132780, -1686477, 3044289, 923257, 1315593, 1037996, -3232854, 2302858, 103466, -3045740, -184178, 2603529, 60450, 2484496, -1686477, 923257, 1315593, -3069551, -1191095, 2601601, -98138, 3044289, 1037996, -3232854, 550069, -2966152, 3323445, 1463241, 103466, -184178, 2603529, 3065364, 170617, 2923783, -2168657, -3045740, 60450, 2484496, 316317, 1431124, 2428258, -3225759, -3050063, -3050063, 1149528, -3050063, 1149528, 132780, 2302858, 1149528, 132780, 2302858, -1686477, 3044289, 103466, -3045740, 132780, -1686477, 3044289, 923257, 1315593, 1037996, -3232854, 2302858, 103466, -3045740, -184178, 2603529, 60450, 2484496, -1686477, 923257, 1315593, -3069551, -1191095, 2601601, -98138, 3044289, 1037996, -3232854, 550069, -2966152, 3323445, 1463241, 103466, -184178, 2603529, 3065364, 170617, 2923783, -2168657, -3045740, 60450, 2484496, 316317, 1431124, 2428258, -3225759, 923257, -3069551, -1191095, 3335467, -2721083, 3469197, 384758, 1315593, 2601601, -98138, 634030, -795882, 1588277, 3518577, 1037996, 550069, -2966152, -2839152, -3438937, 3558460, 3331397, -3232854, 3323445, 1463241, 1871790, 1473979, 789061, 2577408, -184178, 3065364, 170617, 3024785, 2180068, 2440368, -1180913, 2603529, 2923783, -2168657, 3024654, 2658792, 3054418, -798501, 60450, 316317, 1431124, -2280251, -42233, -542147, 1440490, 2484496, 2428258, -3225759, -2988693, 660597, 144858, 2743683, -3069551, 3335467, -2721083, -183381, -1308281, 210630, -1174444, -1191095, 3469197, 384758, 1039822, -1245434, -2136239, -1979026, 2601601, 634030, -795882, -331360, 636061, 3131962, 839509, -98138, 1588277, 3518577, 2872486, -1517404, -1757547, 1841269, 550069, -2839152, -3438937, -3474245, -701468, -1651912, 2749359, -2966152, 3558460, 3331397, 489732, -922769, -2863079, -2159637, 3323445, 1871790, 1473979, 1507361, -785875, 2598909, 412958, 1463241, 789061, 2577408, -1665499, 1438785, -633752, -2995780, 3065364, 3024785, 2180068, -606079, -588237, -3256257, -1673592, 170617, 2440368, -1180913, 1896338, -1630573, 2248382, 2753738, 2923783, 3024654, 2658792, 2837690, -1211035, -1479754, 2157765, -2168657, 3054418, -798501, -287428, -3522824, 3553705, 1111230, 316317, -2280251, -42233, 1467637, -235474, 1327626, 1125402, 1431124, -542147, 1440490, 1081296, 2745428, 924764, -2914718, 2428258, -2988693, 660597, -1880403, -2086389, 334536, -3248967, -3225759, 144858, 2743683, -1725863, 83399, -365020, 3341808, 3335467, -183381, -1308281, 2910638, -3595566, -390113, -1554680, -2721083, 210630, -1174444, 646184, -2908900, 3130243, 2624686, 3469197, 1039822, -1245434, 1351910, 1150687, -3534285, 2366129, 384758, -2136239, -1979026, -1793532, 2773201, 3445475, 803880, 634030, -331360, 636061, 2160794, 2179786, 1839220, -1635541, -795882, 3131962, 839509, 1519660, 3233007, 1795755, 705718, 1588277, 2872486, -1517404, -3016005, 2485310, 1759875, 310187, 3518577, -1757547, 1841269, 2771447, 1597047, 1586594, 2562997, -2839152, -3474245, -701468, -580793, 1937509, 3570625, 178913, -3438937, -1651912, 2749359, 1315536, -825987, 698310, 1404507, 3558460, 489732, -922769, -3201046, 692547, 480612, 95533, 3331397, -2863079, -2159637, 3013610, -950000, 362019, 1906959, 1871790, 1507361, -785875, 2036795, -180113, 610602, 269813, 1473979, 2598909, 412958, 943574, 1348427, -42770, 134553, 789061, -1665499, 1438785, 3351503, -3420730, 2913973, -738397, 2577408, -633752, -2995780, 2486601, 685338, 2752524, 78472, 3024785, -606079, -588237, 1304639, -475268, 1647023, 2404006, 2180068, -3256257, -1673592, -3562544, -3506949, -2732487, -1354036, 2440368, 1896338, -1630573, 2762359, -3053079, -892354, -1995867, -1180913, 2248382, 2753738, -469143, -3591341, 1395577, -2428391, 3024654, 2837690, -1211035, 713251, 1042426, 1031268, 3144946, 2658792, -1479754, 2157765, 2847719, 3109151, 3083587, -1581803, 3054418, -287428, -3522824, 110541, 2742990, 1968501, 1407270, -798501, 3553705, 1111230, -2657545, -2420598, 2447816, 3078188, -2280251, 1467637, -235474, 3552899, -3382332, -1521252, 2418224, -42233, 1327626, 1125402, -2973964, -2146618, 164584, 1105730, -542147, 1081296, 2745428, -894462, -3119296, -55875, -1105442, 1440490, 924764, -2914718, 1819612, 2735543, 1824688, 1728603, -2988693, -1880403, -2086389, 1251025, -3014937, 2585433, -1469797, 660597, 334536, -3248967, -1312936, -1569501, -117140, -1943974, 144858, -1725863, 83399, 1719727, 3242769, -2461031, -1195972, 2743683, -365020, 3341808, 554759, 768392, -2061534, 3483018
};

extern void __asm_ntt_0_1_2(int*, const int*, int, int, int*);
extern void __asm_ntt_0_1_2_small(int*, const int*, int, int, int*);
extern void __asm_ntt_3_4_5_6_7_8(int*, const int*, int, int);
extern void __asm_base_mul(int*, const int*, int, int);
extern void __asm_intt(int*, const int*, int, int);
extern void __asm_final_map(int*, int, int, int, int*);

void polymul_1013x1013_mod7177(int* polyout, int* polyin1, int* polyin2);
void polymul_1013x1013_mod7177(int* polyout, int* polyin1, int* polyin2){
    int mem[1 << 12];
    int *ntt1, *ntt2;
    ntt1 = mem;
    ntt2 = ntt1 + ARRAY_N;
    __asm_ntt_0_1_2(polyin1, streamlined_Rmod_root_table, Mprime, MOD, ntt1);
    __asm_ntt_0_1_2_small(polyin2, streamlined_Rmod_root_table_small, Mprime, MOD, ntt2);
    __asm_ntt_3_4_5_6_7_8(ntt1, streamlined_Rmod_root_table, Mprime, MOD);
    __asm_ntt_3_4_5_6_7_8(ntt2, streamlined_Rmod_root_table, Mprime, MOD);
    __asm_base_mul(ntt1, Rmod_mul_table, Mprime, MOD);
    __asm_intt(ntt1, streamlined_Rmod_inv_GS_root_table, Mprime, MOD);
    __asm_final_map(ntt1, Mhalf, Mprime, MOD, polyout);
}