Debian Codegraph @

crypto_kem/348864/avx/benes.c

raw
1 /*
2 This file is for Benes network related functions
3
4 For the implementation strategy, see
5 https://eprint.iacr.org/2017/793.pdf
6 */
7 // 20221231 djb: remove unused counter increment; tnx thom wiggers
8 // 20221230 djb: add linker lines
9
10 // linker define load_bits benes
11 // linker use transpose_64x64_asm
12
13 #include "util.h"
14 #include "transpose.h"
15 #include "params.h"
16 #include "benes.h"
17
18 static void layer_0(uint64_t *bs, uint64_t *cond)
19 {
20 int x;
21 uint64_t diff;
22
23 for (x = 0; x < (1 << 6); x += 2)
24 {
25 diff = bs[ x ] ^ bs[ x+1 ];
26 diff &= *cond++;
27 bs[ x ] ^= diff;
28 bs[ x+1 ] ^= diff;
29 }
30 }
31
32 static void layer_1(uint64_t *bs, uint64_t *cond)
33 {
34 int x;
35 uint64_t diff;
36
37 for (x = 0; x < (1 << 6); x += 4)
38 {
39 diff = bs[ x+0 ] ^ bs[ x+2 ];
40 diff &= cond[0];
41 bs[ x+0 ] ^= diff;
42 bs[ x+2 ] ^= diff;
43
44 diff = bs[ x+1 ] ^ bs[ x+3 ];
45 diff &= cond[1];
46 bs[ x+1 ] ^= diff;
47 bs[ x+3 ] ^= diff;
48
49 cond += 2;
50 }
51 }
52
53 static void layer_2(uint64_t *bs, uint64_t *cond)
54 {
55 int x;
56 uint64_t diff;
57
58 for (x = 0; x < (1 << 6); x += 8)
59 {
60 diff = bs[ x+0 ] ^ bs[ x+4 ];
61 diff &= cond[0];
62 bs[ x+0 ] ^= diff;
63 bs[ x+4 ] ^= diff;
64
65 diff = bs[ x+1 ] ^ bs[ x+5 ];
66 diff &= cond[1];
67 bs[ x+1 ] ^= diff;
68 bs[ x+5 ] ^= diff;
69
70 diff = bs[ x+2 ] ^ bs[ x+6 ];
71 diff &= cond[2];
72 bs[ x+2 ] ^= diff;
73 bs[ x+6 ] ^= diff;
74
75 diff = bs[ x+3 ] ^ bs[ x+7 ];
76 diff &= cond[3];
77 bs[ x+3 ] ^= diff;
78 bs[ x+7 ] ^= diff;
79
80 cond += 4;
81 }
82 }
83
84 static void layer_3(uint64_t *bs, uint64_t *cond)
85 {
86 int x, s;
87 uint64_t diff;
88
89 for (x = 0; x < (1 << 6); x += 16)
90 for (s = x; s < x + 8; s += 4)
91 {
92 diff = bs[ s+0 ] ^ bs[ s+8 ];
93 diff &= cond[0];
94 bs[ s+0 ] ^= diff;
95 bs[ s+8 ] ^= diff;
96
97 diff = bs[ s+1 ] ^ bs[ s+9 ];
98 diff &= cond[1];
99 bs[ s+1 ] ^= diff;
100 bs[ s+9 ] ^= diff;
101
102 diff = bs[ s+2 ] ^ bs[ s+10 ];
103 diff &= cond[2];
104 bs[ s+2 ] ^= diff;
105 bs[ s+10 ] ^= diff;
106
107 diff = bs[ s+3 ] ^ bs[ s+11 ];
108 diff &= cond[3];
109 bs[ s+3 ] ^= diff;
110 bs[ s+11 ] ^= diff;
111
112 cond += 4;
113 }
114 }
115
116 static void layer_4(uint64_t *bs, uint64_t *cond)
117 {
118 int x, s;
119 uint64_t diff;
120
121 for (x = 0; x < (1 << 6); x += 32)
122 for (s = x; s < x + 16; s += 4)
123 {
124 diff = bs[ s+0 ] ^ bs[ s+16 ];
125 diff &= cond[0];
126 bs[ s+0 ] ^= diff;
127 bs[ s+16 ] ^= diff;
128
129 diff = bs[ s+1 ] ^ bs[ s+17 ];
130 diff &= cond[1];
131 bs[ s+1 ] ^= diff;
132 bs[ s+17 ] ^= diff;
133
134 diff = bs[ s+2 ] ^ bs[ s+18 ];
135 diff &= cond[2];
136 bs[ s+2 ] ^= diff;
137 bs[ s+18 ] ^= diff;
138
139 diff = bs[ s+3 ] ^ bs[ s+19 ];
140 diff &= cond[3];
141 bs[ s+3 ] ^= diff;
142 bs[ s+19 ] ^= diff;
143
144 cond += 4;
145 }
146 }
147
148 static void layer_5(uint64_t *bs, uint64_t *cond)
149 {
150 int x, s;
151 uint64_t diff;
152
153 for (x = 0; x < (1 << 6); x += 64)
154 for (s = x; s < x + 32; s += 4)
155 {
156 diff = bs[ s+0 ] ^ bs[ s+32 ];
157 diff &= cond[0];
158 bs[ s+0 ] ^= diff;
159 bs[ s+32 ] ^= diff;
160
161 diff = bs[ s+1 ] ^ bs[ s+33 ];
162 diff &= cond[1];
163 bs[ s+1 ] ^= diff;
164 bs[ s+33 ] ^= diff;
165
166 diff = bs[ s+2 ] ^ bs[ s+34 ];
167 diff &= cond[2];
168 bs[ s+2 ] ^= diff;
169 bs[ s+34 ] ^= diff;
170
171 diff = bs[ s+3 ] ^ bs[ s+35 ];
172 diff &= cond[3];
173 bs[ s+3 ] ^= diff;
174 bs[ s+35 ] ^= diff;
175
176 cond += 4;
177 }
178 }
179
180 /* input: bits, control bits as array of bytes */
181 /* output: out, control bits as array of 64-bit vectors */
182 void load_bits(uint64_t out[][32], const unsigned char * bits)
183 {
184 int i, low, block = 0;
185
186 uint64_t cond[64];
187
188 //
189
190 for (low = 0; low <= 5; low++)
191 {
192 for (i = 0; i < 64; i++) cond[i] = load4(bits + block*256 + i*4);
193 transpose_64x64(cond);
194
195 for (i = 0; i < 32; i++) out[ block ][i] = cond[i];
196 block++;
197 }
198
199 for (low = 0; low <= 5; low++)
200 {
201 for (i = 0; i < 32; i++) out[ block ][i] = load8(bits + block*256 + i*8);
202 block++;
203 }
204
205 for (low = 4; low >= 0; low--)
206 {
207 for (i = 0; i < 32; i++) out[ block ][i] = load8(bits + block*256 + i*8);
208 block++;
209 }
210
211 for (low = 5; low >= 0; low--)
212 {
213 for (i = 0; i < 64; i++) cond[i] = load4(bits + block*256 + i*4);
214 transpose_64x64(cond);
215
216 for (i = 0; i < 32; i++) out[ block ][i] = cond[i];
217 block++;
218 }
219 }
220
221 /* input: r, sequence of bits to be permuted */
222 /* cond, control bits as array of 64-bit vectors */
223 /* rev, 0 for normal application; !0 for inverse */
224 /* output: r, permuted bits */
225 void benes(uint64_t * r, uint64_t cond[][32], int rev)
226 {
227 int block, inc;
228
229 uint64_t *bs = r;
230
231 //
232
233 if (rev == 0) {block = 0; inc = 1;}
234 else {block = 22; inc = -1;}
235
236 transpose_64x64(bs);
237
238 layer_0(bs, cond[ block ]); block += inc;
239 layer_1(bs, cond[ block ]); block += inc;
240 layer_2(bs, cond[ block ]); block += inc;
241 layer_3(bs, cond[ block ]); block += inc;
242 layer_4(bs, cond[ block ]); block += inc;
243 layer_5(bs, cond[ block ]); block += inc;
244
245 transpose_64x64(bs);
246
247 layer_0(bs, cond[ block ]); block += inc;
248 layer_1(bs, cond[ block ]); block += inc;
249 layer_2(bs, cond[ block ]); block += inc;
250 layer_3(bs, cond[ block ]); block += inc;
251 layer_4(bs, cond[ block ]); block += inc;
252 layer_5(bs, cond[ block ]); block += inc;
253 layer_4(bs, cond[ block ]); block += inc;
254 layer_3(bs, cond[ block ]); block += inc;
255 layer_2(bs, cond[ block ]); block += inc;
256 layer_1(bs, cond[ block ]); block += inc;
257 layer_0(bs, cond[ block ]); block += inc;
258
259 transpose_64x64(bs);
260
261 layer_5(bs, cond[ block ]); block += inc;
262 layer_4(bs, cond[ block ]); block += inc;
263 layer_3(bs, cond[ block ]); block += inc;
264 layer_2(bs, cond[ block ]); block += inc;
265 layer_1(bs, cond[ block ]); block += inc;
266 layer_0(bs, cond[ block ]);
267
268 transpose_64x64(bs);
269 }
270