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