1 /*
2 this file is for functions for field arithmetic
3 */
4
5 #include "gf.h"
6
7 #include "params.h"
8
9 #include <stdio.h>
10
11 /* field multiplication */
PQCLEAN_MCELIECE6688128_AVX_gf_mul(gf in0,gf in1)12 gf PQCLEAN_MCELIECE6688128_AVX_gf_mul(gf in0, gf in1) {
13 int i;
14
15 uint64_t tmp;
16 uint64_t t0;
17 uint64_t t1;
18 uint64_t t;
19
20 t0 = in0;
21 t1 = in1;
22
23 tmp = t0 * (t1 & 1);
24
25 for (i = 1; i < GFBITS; i++) {
26 tmp ^= (t0 * (t1 & ((uint64_t)1 << i)));
27 }
28
29 //
30
31 t = tmp & 0x1FF0000;
32 tmp ^= (t >> 9) ^ (t >> 10) ^ (t >> 12) ^ (t >> 13);
33
34 t = tmp & 0x000E000;
35 tmp ^= (t >> 9) ^ (t >> 10) ^ (t >> 12) ^ (t >> 13);
36
37 return tmp & GFMASK;
38 }
39
40 /* 2 field multiplications */
PQCLEAN_MCELIECE6688128_AVX_gf_mul2(gf a,gf b0,gf b1)41 uint64_t PQCLEAN_MCELIECE6688128_AVX_gf_mul2(gf a, gf b0, gf b1) {
42 int i;
43
44 uint64_t tmp = 0;
45 uint64_t t0;
46 uint64_t t1;
47 uint64_t t;
48 uint64_t mask = 0x0000000100000001;
49
50 t0 = a;
51 t1 = b1;
52 t1 = (t1 << 32) | b0;
53
54 for (i = 0; i < GFBITS; i++) {
55 tmp ^= t0 * (t1 & mask);
56 mask += mask;
57 }
58
59 //
60
61 t = tmp & 0x01FF000001FF0000;
62 tmp ^= (t >> 9) ^ (t >> 10) ^ (t >> 12) ^ (t >> 13);
63
64 t = tmp & 0x0000E0000000E000;
65 tmp ^= (t >> 9) ^ (t >> 10) ^ (t >> 12) ^ (t >> 13);
66
67 return tmp & 0x00001FFF00001FFF;
68 }
69
70 /* 2 field squarings */
gf_sq2(gf in)71 static inline gf gf_sq2(gf in) {
72 int i;
73
74 const uint64_t B[] = {0x1111111111111111,
75 0x0303030303030303,
76 0x000F000F000F000F,
77 0x000000FF000000FF
78 };
79
80 const uint64_t M[] = {0x0001FF0000000000,
81 0x000000FF80000000,
82 0x000000007FC00000,
83 0x00000000003FE000
84 };
85
86 uint64_t x = in;
87 uint64_t t;
88
89 x = (x | (x << 24)) & B[3];
90 x = (x | (x << 12)) & B[2];
91 x = (x | (x << 6)) & B[1];
92 x = (x | (x << 3)) & B[0];
93
94 for (i = 0; i < 4; i++) {
95 t = x & M[i];
96 x ^= (t >> 9) ^ (t >> 10) ^ (t >> 12) ^ (t >> 13);
97 }
98
99 return x & GFMASK;
100 }
101
102 /* square and multiply */
gf_sqmul(gf in,gf m)103 static inline gf gf_sqmul(gf in, gf m) {
104 int i;
105
106 uint64_t x;
107 uint64_t t0;
108 uint64_t t1;
109 uint64_t t;
110
111 const uint64_t M[] = {0x0000001FF0000000,
112 0x000000000FF80000,
113 0x000000000007E000
114 };
115
116 t0 = in;
117 t1 = m;
118
119 x = (t1 << 6) * (t0 & (1 << 6));
120
121 t0 ^= (t0 << 7);
122
123 x ^= (t1 * (t0 & (0x04001)));
124 x ^= (t1 * (t0 & (0x08002))) << 1;
125 x ^= (t1 * (t0 & (0x10004))) << 2;
126 x ^= (t1 * (t0 & (0x20008))) << 3;
127 x ^= (t1 * (t0 & (0x40010))) << 4;
128 x ^= (t1 * (t0 & (0x80020))) << 5;
129
130 for (i = 0; i < 3; i++) {
131 t = x & M[i];
132 x ^= (t >> 9) ^ (t >> 10) ^ (t >> 12) ^ (t >> 13);
133 }
134
135 return x & GFMASK;
136 }
137
138 /* square twice and multiply */
gf_sq2mul(gf in,gf m)139 static inline gf gf_sq2mul(gf in, gf m) {
140 int i;
141
142 uint64_t x;
143 uint64_t t0;
144 uint64_t t1;
145 uint64_t t;
146
147 const uint64_t M[] = {0x1FF0000000000000,
148 0x000FF80000000000,
149 0x000007FC00000000,
150 0x00000003FE000000,
151 0x0000000001FE0000,
152 0x000000000001E000
153 };
154
155 t0 = in;
156 t1 = m;
157
158 x = (t1 << 18) * (t0 & (1 << 6));
159
160 t0 ^= (t0 << 21);
161
162 x ^= (t1 * (t0 & (0x010000001)));
163 x ^= (t1 * (t0 & (0x020000002))) << 3;
164 x ^= (t1 * (t0 & (0x040000004))) << 6;
165 x ^= (t1 * (t0 & (0x080000008))) << 9;
166 x ^= (t1 * (t0 & (0x100000010))) << 12;
167 x ^= (t1 * (t0 & (0x200000020))) << 15;
168
169 for (i = 0; i < 6; i++) {
170 t = x & M[i];
171 x ^= (t >> 9) ^ (t >> 10) ^ (t >> 12) ^ (t >> 13);
172 }
173
174 return x & GFMASK;
175 }
176
177 /* return num/den */
PQCLEAN_MCELIECE6688128_AVX_gf_frac(gf den,gf num)178 gf PQCLEAN_MCELIECE6688128_AVX_gf_frac(gf den, gf num) {
179 gf tmp_11;
180 gf tmp_1111;
181 gf out;
182
183 tmp_11 = gf_sqmul(den, den); // 11
184 tmp_1111 = gf_sq2mul(tmp_11, tmp_11); // 1111
185 out = gf_sq2(tmp_1111);
186 out = gf_sq2mul(out, tmp_1111); // 11111111
187 out = gf_sq2(out);
188 out = gf_sq2mul(out, tmp_1111); // 111111111111
189
190 return gf_sqmul(out, num); // 1111111111110
191 }
192
193 /* return 1/den */
PQCLEAN_MCELIECE6688128_AVX_gf_inv(gf in)194 gf PQCLEAN_MCELIECE6688128_AVX_gf_inv(gf in) {
195 return PQCLEAN_MCELIECE6688128_AVX_gf_frac(in, ((gf) 1));
196 }
197
198 /* check if a == 0 */
PQCLEAN_MCELIECE6688128_AVX_gf_iszero(gf a)199 gf PQCLEAN_MCELIECE6688128_AVX_gf_iszero(gf a) {
200 uint32_t t = a;
201
202 t -= 1;
203 t >>= 19;
204
205 return (gf) t;
206 }
207
208 /* multiplication in GF((2^m)^t) */
PQCLEAN_MCELIECE6688128_AVX_GF_mul(gf * out,const gf * in0,const gf * in1)209 void PQCLEAN_MCELIECE6688128_AVX_GF_mul(gf *out, const gf *in0, const gf *in1) {
210 int i, j;
211
212 gf prod[255];
213
214 for (i = 0; i < 255; i++) {
215 prod[i] = 0;
216 }
217
218 for (i = 0; i < 128; i++) {
219 for (j = 0; j < 128; j++) {
220 prod[i + j] ^= PQCLEAN_MCELIECE6688128_AVX_gf_mul(in0[i], in1[j]);
221 }
222 }
223
224 //
225
226 for (i = 254; i >= 128; i--) {
227 prod[i - 123] ^= PQCLEAN_MCELIECE6688128_AVX_gf_mul(prod[i], (gf) 7682);
228 prod[i - 125] ^= PQCLEAN_MCELIECE6688128_AVX_gf_mul(prod[i], (gf) 2159);
229 prod[i - 128] ^= PQCLEAN_MCELIECE6688128_AVX_gf_mul(prod[i], (gf) 3597);
230 }
231
232 for (i = 0; i < 128; i++) {
233 out[i] = prod[i];
234 }
235 }
236
237