1 /*
2 This file is for functions required for generating the control bits of the Benes network w.r.t. a random permutation
3 see the Lev-Pippenger-Valiant paper https://www.computer.org/csdl/trans/tc/1981/02/06312171.pdf
4 */
5
6 #include "controlbits.h"
7
8 #include "params.h"
9
10 #include <stdint.h>
11
12 typedef uint8_t bit;
13
14 #define N (1 << GFBITS)
15
is_smaller(uint32_t a,uint32_t b)16 static bit is_smaller(uint32_t a, uint32_t b) {
17 uint32_t ret = 0;
18
19 ret = a - b;
20 ret >>= 31;
21
22 return (bit)ret;
23 }
24
is_smaller_63b(uint64_t a,uint64_t b)25 static bit is_smaller_63b(uint64_t a, uint64_t b) {
26 uint64_t ret = 0;
27
28 ret = a - b;
29 ret >>= 63;
30
31 return (bit)ret;
32 }
33
cswap(uint32_t * x,uint32_t * y,bit swap)34 static void cswap(uint32_t *x, uint32_t *y, bit swap) {
35 uint32_t m;
36 uint32_t d;
37
38 m = swap;
39 m = 0 - m;
40
41 d = (*x ^ *y);
42 d &= m;
43 *x ^= d;
44 *y ^= d;
45 }
46
cswap_63b(uint64_t * x,uint64_t * y,bit swap)47 static void cswap_63b(uint64_t *x, uint64_t *y, bit swap) {
48 uint64_t m;
49 uint64_t d;
50
51 m = swap;
52 m = 0 - m;
53
54 d = (*x ^ *y);
55 d &= m;
56 *x ^= d;
57 *y ^= d;
58 }
59
60 /* output x = min(input x,input y) */
61 /* output y = max(input x,input y) */
62
minmax(uint32_t * x,uint32_t * y)63 static void minmax(uint32_t *x, uint32_t *y) {
64 bit m;
65
66 m = is_smaller(*y, *x);
67 cswap(x, y, m);
68 }
69
minmax_63b(uint64_t * x,uint64_t * y)70 static void minmax_63b(uint64_t *x, uint64_t *y) {
71 bit m;
72
73 m = is_smaller_63b(*y, *x);
74 cswap_63b(x, y, m);
75 }
76
77 /* merge first half of x[0],x[step],...,x[(2*n-1)*step] with second half */
78 /* requires n to be a power of 2 */
79
merge(int n,uint32_t * x,int step)80 static void merge(int n, uint32_t *x, int step) {
81 int i;
82 if (n == 1) {
83 minmax(&x[0], &x[step]);
84 } else {
85 merge(n / 2, x, step * 2);
86 merge(n / 2, x + step, step * 2);
87 for (i = 1; i < 2 * n - 1; i += 2) {
88 minmax(&x[i * step], &x[(i + 1) * step]);
89 }
90 }
91 }
92
merge_63b(int n,uint64_t * x,int step)93 static void merge_63b(int n, uint64_t *x, int step) {
94 int i;
95 if (n == 1) {
96 minmax_63b(&x[0], &x[step]);
97 } else {
98 merge_63b(n / 2, x, step * 2);
99 merge_63b(n / 2, x + step, step * 2);
100 for (i = 1; i < 2 * n - 1; i += 2) {
101 minmax_63b(&x[i * step], &x[(i + 1) * step]);
102 }
103 }
104 }
105
106 /* sort x[0],x[1],...,x[n-1] in place */
107 /* requires n to be a power of 2 */
108
sort(int n,uint32_t * x)109 static void sort(int n, uint32_t *x) {
110 if (n <= 1) {
111 return;
112 }
113 sort(n / 2, x);
114 sort(n / 2, x + n / 2);
115 merge(n / 2, x, 1);
116 }
117
PQCLEAN_MCELIECE348864_AVX_sort_63b(int n,uint64_t * x)118 void PQCLEAN_MCELIECE348864_AVX_sort_63b(int n, uint64_t *x) {
119 if (n <= 1) {
120 return;
121 }
122 PQCLEAN_MCELIECE348864_AVX_sort_63b(n / 2, x);
123 PQCLEAN_MCELIECE348864_AVX_sort_63b(n / 2, x + n / 2);
124 merge_63b(n / 2, x, 1);
125 }
126
127 /* y[pi[i]] = x[i] */
128 /* requires n = 2^w */
129 /* requires pi to be a permutation */
composeinv(int n,uint32_t * y,const uint32_t * x,const uint32_t * pi)130 static void composeinv(int n, uint32_t *y, const uint32_t *x, const uint32_t *pi) { // NC
131 int i;
132 uint32_t t[2 * N];
133
134 for (i = 0; i < n; ++i) {
135 t[i] = x[i] | (pi[i] << 16);
136 }
137
138 sort(n, t);
139
140 for (i = 0; i < n; ++i) {
141 y[i] = t[i] & 0xFFFF;
142 }
143 }
144
145 /* ip[i] = j iff pi[i] = j */
146 /* requires n = 2^w */
147 /* requires pi to be a permutation */
invert(int n,uint32_t * ip,const uint32_t * pi)148 static void invert(int n, uint32_t *ip, const uint32_t *pi) {
149 int i;
150
151 for (i = 0; i < n; i++) {
152 ip[i] = i;
153 }
154
155 composeinv(n, ip, ip, pi);
156 }
157
158
flow(int w,uint32_t * x,const uint32_t * y,int t)159 static void flow(int w, uint32_t *x, const uint32_t *y, int t) {
160 bit m0;
161 bit m1;
162
163 uint32_t b;
164 uint32_t y_copy = *y;
165
166 m0 = is_smaller(*y & ((1 << w) - 1), *x & ((1 << w) - 1));
167 m1 = is_smaller(0, t);
168
169 cswap(x, &y_copy, m0);
170 b = m0 & m1;
171 *x ^= b << w;
172 }
173
174 /* input: permutation pi */
175 /* output: (2w-1)n/2 (or 0 if n==1) control bits c[0],c[step],c[2*step],... */
176 /* requires n = 2^w */
controlbitsfrompermutation(int w,int n,int step,int off,unsigned char * c,const uint32_t * pi)177 static void controlbitsfrompermutation(int w, int n, int step, int off, unsigned char *c, const uint32_t *pi) {
178 int i;
179 int j;
180 int k;
181 int t;
182 uint32_t ip[N] = {0};
183 uint32_t I[2 * N] = {0};
184 uint32_t P[2 * N] = {0};
185 uint32_t PI[2 * N] = {0};
186 uint32_t T[2 * N] = {0};
187 uint32_t piflip[N] = {0};
188 uint32_t subpi[2][N / 2] = {{0}};
189
190 if (w == 1) {
191 c[ off / 8 ] |= (pi[0] & 1) << (off % 8);
192 }
193 if (w <= 1) {
194 return;
195 }
196
197 invert(n, ip, pi);
198
199 for (i = 0; i < n; ++i) {
200 I[i] = ip[i] | (1 << w);
201 I[n + i] = pi[i];
202 }
203
204 for (i = 0; i < 2 * n; ++i) {
205 P[i] = (i >> w) + (i & ((1 << w) - 2)) + ((i & 1) << w);
206 }
207
208 for (t = 0; t < w; ++t) {
209 composeinv(2 * n, PI, P, I);
210
211 for (i = 0; i < 2 * n; ++i) {
212 flow(w, &P[i], &PI[i], t);
213 }
214
215 for (i = 0; i < 2 * n; ++i) {
216 T[i] = I[i ^ 1];
217 }
218
219 composeinv(2 * n, I, I, T);
220
221 for (i = 0; i < 2 * n; ++i) {
222 T[i] = P[i ^ 1];
223 }
224
225 for (i = 0; i < 2 * n; ++i) {
226 flow(w, &P[i], &T[i], 1);
227 }
228 }
229
230 for (i = 0; i < n; ++i) {
231 for (j = 0; j < w; ++j) {
232 piflip[i] = pi[i];
233 }
234 }
235
236 for (i = 0; i < n / 2; ++i) {
237 c[ (off + i * step) / 8 ] |= ((P[i * 2] >> w) & 1) << ((off + i * step) % 8);
238 }
239 for (i = 0; i < n / 2; ++i) {
240 c[ (off + ((w - 1)*n + i) * step) / 8 ] |= ((P[n + i * 2] >> w) & 1) << ((off + ((w - 1) * n + i) * step) % 8);
241 }
242
243 for (i = 0; i < n / 2; ++i) {
244 cswap(&piflip[i * 2], &piflip[i * 2 + 1], (P[n + i * 2] >> w) & 1);
245 }
246
247 for (k = 0; k < 2; ++k) {
248 for (i = 0; i < n / 2; ++i) {
249 subpi[k][i] = piflip[i * 2 + k] >> 1;
250 }
251 }
252
253 for (k = 0; k < 2; ++k) {
254 controlbitsfrompermutation(w - 1, n / 2, step * 2, off + step * (n / 2 + k), c, subpi[k]);
255 }
256 }
257
258 /* input: pi, a permutation*/
259 /* output: out, control bits w.r.t. pi */
PQCLEAN_MCELIECE348864_AVX_controlbits(unsigned char * out,const uint32_t * pi)260 void PQCLEAN_MCELIECE348864_AVX_controlbits(unsigned char *out, const uint32_t *pi) {
261 unsigned int i;
262 unsigned char c[ (2 * GFBITS - 1) * (1 << GFBITS) / 16 ];
263
264 for (i = 0; i < sizeof(c); i++) {
265 c[i] = 0;
266 }
267
268 controlbitsfrompermutation(GFBITS, (1 << GFBITS), 1, 0, c, pi);
269
270 for (i = 0; i < sizeof(c); i++) {
271 out[i] = c[i];
272 }
273 }
274
275