1 /*
2 This file is for functions for field arithmetic
3 */
4
5 #include "gf.h"
6
7 #include "params.h"
8
PQCLEAN_MCELIECE348864F_AVX_gf_iszero(gf a)9 gf PQCLEAN_MCELIECE348864F_AVX_gf_iszero(gf a) {
10 uint32_t t = a;
11
12 t -= 1;
13 t >>= 20;
14
15 return (gf) t;
16 }
17
PQCLEAN_MCELIECE348864F_AVX_gf_add(gf in0,gf in1)18 gf PQCLEAN_MCELIECE348864F_AVX_gf_add(gf in0, gf in1) {
19 return in0 ^ in1;
20 }
21
PQCLEAN_MCELIECE348864F_AVX_gf_mul(gf in0,gf in1)22 gf PQCLEAN_MCELIECE348864F_AVX_gf_mul(gf in0, gf in1) {
23 int i;
24
25 uint32_t tmp;
26 uint32_t t0;
27 uint32_t t1;
28 uint32_t t;
29
30 t0 = in0;
31 t1 = in1;
32
33 tmp = t0 * (t1 & 1);
34
35 for (i = 1; i < GFBITS; i++) {
36 tmp ^= (t0 * (t1 & (1 << i)));
37 }
38
39 t = tmp & 0x7FC000;
40 tmp ^= t >> 9;
41 tmp ^= t >> 12;
42
43 t = tmp & 0x3000;
44 tmp ^= t >> 9;
45 tmp ^= t >> 12;
46
47 return tmp & ((1 << GFBITS) - 1);
48 }
49
50 /* input: field element in */
51 /* return: in^2 */
gf_sq(gf in)52 static inline gf gf_sq(gf in) {
53 const uint32_t B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
54
55 uint32_t x = in;
56 uint32_t t;
57
58 x = (x | (x << 8)) & B[3];
59 x = (x | (x << 4)) & B[2];
60 x = (x | (x << 2)) & B[1];
61 x = (x | (x << 1)) & B[0];
62
63 t = x & 0x7FC000;
64 x ^= t >> 9;
65 x ^= t >> 12;
66
67 t = x & 0x3000;
68 x ^= t >> 9;
69 x ^= t >> 12;
70
71 return x & ((1 << GFBITS) - 1);
72 }
73
PQCLEAN_MCELIECE348864F_AVX_gf_inv(gf in)74 gf PQCLEAN_MCELIECE348864F_AVX_gf_inv(gf in) {
75 gf tmp_11;
76 gf tmp_1111;
77
78 gf out = in;
79
80 out = gf_sq(out);
81 tmp_11 = PQCLEAN_MCELIECE348864F_AVX_gf_mul(out, in); // 11
82
83 out = gf_sq(tmp_11);
84 out = gf_sq(out);
85 tmp_1111 = PQCLEAN_MCELIECE348864F_AVX_gf_mul(out, tmp_11); // 1111
86
87 out = gf_sq(tmp_1111);
88 out = gf_sq(out);
89 out = gf_sq(out);
90 out = gf_sq(out);
91 out = PQCLEAN_MCELIECE348864F_AVX_gf_mul(out, tmp_1111); // 11111111
92
93 out = gf_sq(out);
94 out = gf_sq(out);
95 out = PQCLEAN_MCELIECE348864F_AVX_gf_mul(out, tmp_11); // 1111111111
96
97 out = gf_sq(out);
98 out = PQCLEAN_MCELIECE348864F_AVX_gf_mul(out, in); // 11111111111
99
100 return gf_sq(out); // 111111111110
101 }
102
103 /* input: field element den, num */
104 /* return: (num/den) */
PQCLEAN_MCELIECE348864F_AVX_gf_frac(gf den,gf num)105 gf PQCLEAN_MCELIECE348864F_AVX_gf_frac(gf den, gf num) {
106 return PQCLEAN_MCELIECE348864F_AVX_gf_mul(PQCLEAN_MCELIECE348864F_AVX_gf_inv(den), num);
107 }
108
109 /* input: in0, in1 in GF((2^m)^t)*/
110 /* output: out = in0*in1 */
PQCLEAN_MCELIECE348864F_AVX_GF_mul(gf * out,const gf * in0,const gf * in1)111 void PQCLEAN_MCELIECE348864F_AVX_GF_mul(gf *out, const gf *in0, const gf *in1) {
112 int i, j;
113
114 gf prod[ SYS_T * 2 - 1 ];
115
116 for (i = 0; i < SYS_T * 2 - 1; i++) {
117 prod[i] = 0;
118 }
119
120 for (i = 0; i < SYS_T; i++) {
121 for (j = 0; j < SYS_T; j++) {
122 prod[i + j] ^= PQCLEAN_MCELIECE348864F_AVX_gf_mul(in0[i], in1[j]);
123 }
124 }
125
126 //
127
128 for (i = (SYS_T - 1) * 2; i >= SYS_T; i--) {
129 prod[i - SYS_T + 9] ^= PQCLEAN_MCELIECE348864F_AVX_gf_mul(prod[i], (gf) 877);
130 prod[i - SYS_T + 7] ^= PQCLEAN_MCELIECE348864F_AVX_gf_mul(prod[i], (gf) 2888);
131 prod[i - SYS_T + 5] ^= PQCLEAN_MCELIECE348864F_AVX_gf_mul(prod[i], (gf) 1781);
132 prod[i - SYS_T + 0] ^= PQCLEAN_MCELIECE348864F_AVX_gf_mul(prod[i], (gf) 373);
133 }
134
135 for (i = 0; i < SYS_T; i++) {
136 out[i] = prod[i];
137 }
138 }
139
140 /* 2 field multiplications */
PQCLEAN_MCELIECE348864F_AVX_gf_mul2(gf a,gf b0,gf b1)141 uint64_t PQCLEAN_MCELIECE348864F_AVX_gf_mul2(gf a, gf b0, gf b1) {
142 int i;
143
144 uint64_t tmp = 0;
145 uint64_t t0;
146 uint64_t t1;
147 uint64_t t;
148 uint64_t mask = 0x0000000100000001;
149
150 t0 = a;
151 t1 = b1;
152 t1 = (t1 << 32) | b0;
153
154 for (i = 0; i < GFBITS; i++) {
155 tmp ^= t0 * (t1 & mask);
156 mask += mask;
157 }
158
159 //
160
161 t = tmp & 0x007FC000007FC000;
162 tmp ^= (t >> 9) ^ (t >> 12);
163
164 t = tmp & 0x0000300000003000;
165 tmp ^= (t >> 9) ^ (t >> 12);
166
167 return tmp & 0x00000FFF00000FFF;
168 }
169
170