Debian Codegraph @

crypto_kem/8192128pcf/vec/controlbits.c

raw
1 /* This file is for implementing the Nassimi-Sahni algorithm */
2 /* See David Nassimi, Sartaj Sahni "Parallel algorithms to set up the Benes permutationnetwork" */
3 /* See also https://cr.yp.to/papers/controlbits-20200923.pdf */
4
5 // 20250428 djb: rename inner x to avoid shadow warning
6 // 20240805 djb: more mask usage
7 // 20240508 djb: switch to crypto_sort_int32
8 // 20221230 djb: add linker line
9
10 // linker define controlbitsfrompermutation
11
12 #include <string.h>
13 #include "crypto_declassify.h"
14 #include "controlbits.h"
15 #include "crypto_sort_int32.h"
16 typedef int16_t int16;
17 typedef int32_t int32;
18 #include "crypto_int32.h"
19 #define int32_min crypto_int32_min
20 #include "crypto_int16.h"
21 #include "crypto_int8.h"
22
23 /* parameters: 1 <= w <= 14; n = 2^w */
24 /* input: permutation pi of {0,1,...,n-1} */
25 /* output: (2m-1)n/2 control bits at positions pos,pos+step,... */
26 /* output position pos is by definition 1&(out[pos/8]>>(pos&7)) */
27 /* caller must 0-initialize positions first */
28 /* temp must have space for int32[2*n] */
29 static void cbrecursion(unsigned char *out,long long pos,long long step,const int16 *pi,long long w,long long n,int32 *temp)
30 {
31 #define A temp
32 #define B (temp+n)
33 #define q ((int16 *) (temp+n+n/4))
34 /* q can start anywhere between temp+n and temp+n/2 */
35
36 long long x,i,j,k;
37
38 if (w == 1) {
39 out[pos>>3] ^= pi[0]<<(pos&7);
40 return;
41 }
42
43 for (x = 0;x < n;++x) A[x] = ((pi[x]^1)<<16)|pi[x^1];
44 crypto_sort_int32(A,n); /* A = (id<<16)+pibar */
45
46 for (x = 0;x < n;++x) {
47 int32 Ax = A[x];
48 int32 px = Ax&0xffff;
49 int32 cx = int32_min(px,x);
50 B[x] = (px<<16)|cx;
51 }
52 /* B = (p<<16)+c */
53
54 for (x = 0;x < n;++x) A[x] = (A[x]<<16)|x; /* A = (pibar<<16)+id */
55 crypto_sort_int32(A,n); /* A = (id<<16)+pibar^-1 */
56
57 for (x = 0;x < n;++x) A[x] = (A[x]<<16)+(B[x]>>16); /* A = (pibar^(-1)<<16)+pibar */
58 crypto_sort_int32(A,n); /* A = (id<<16)+pibar^2 */
59
60 if (w <= 10) {
61 for (x = 0;x < n;++x) B[x] = ((A[x]&0xffff)<<10)|(B[x]&0x3ff);
62
63 for (i = 1;i < w-1;++i) {
64 /* B = (p<<10)+c */
65
66 for (x = 0;x < n;++x) A[x] = ((B[x]&~0x3ff)<<6)|x; /* A = (p<<16)+id */
67 crypto_sort_int32(A,n); /* A = (id<<16)+p^{-1} */
68
69 for (x = 0;x < n;++x) A[x] = (A[x]<<20)|B[x]; /* A = (p^{-1}<<20)+(p<<10)+c */
70 crypto_sort_int32(A,n); /* A = (id<<20)+(pp<<10)+cp */
71
72 for (x = 0;x < n;++x) {
73 int32 ppcpx = A[x]&0xfffff;
74 int32 ppcx = (A[x]&0xffc00)|(B[x]&0x3ff);
75 B[x] = int32_min(ppcx,ppcpx);
76 }
77 }
78 for (x = 0;x < n;++x) B[x] &= 0x3ff;
79 } else {
80 for (x = 0;x < n;++x) B[x] = (A[x]<<16)|(B[x]&0xffff);
81
82 for (i = 1;i < w-1;++i) {
83 /* B = (p<<16)+c */
84
85 for (x = 0;x < n;++x) A[x] = (B[x]&~0xffff)|x;
86 crypto_sort_int32(A,n); /* A = (id<<16)+p^(-1) */
87
88 for (x = 0;x < n;++x) A[x] = (A[x]<<16)|(B[x]&0xffff);
89 /* A = p^(-1)<<16+c */
90
91 if (i < w-2) {
92 for (x = 0;x < n;++x) B[x] = (A[x]&~0xffff)|(B[x]>>16);
93 /* B = (p^(-1)<<16)+p */
94 crypto_sort_int32(B,n); /* B = (id<<16)+p^(-2) */
95 for (x = 0;x < n;++x) B[x] = (B[x]<<16)|(A[x]&0xffff);
96 /* B = (p^(-2)<<16)+c */
97 }
98
99 crypto_sort_int32(A,n);
100 /* A = id<<16+cp */
101 for (x = 0;x < n;++x) {
102 int32 cpx = (B[x]&~0xffff)|(A[x]&0xffff);
103 B[x] = int32_min(B[x],cpx);
104 }
105 }
106 for (x = 0;x < n;++x) B[x] &= 0xffff;
107 }
108
109 for (x = 0;x < n;++x) A[x] = (((int32)pi[x])<<16)+x;
110 crypto_sort_int32(A,n); /* A = (id<<16)+pi^(-1) */
111
112 for (j = 0;j < n/2;++j) {
113 long long z = 2*j;
114 int32 fj = crypto_int32_bottombit_01(B[z]); /* f[j] */
115 int32 Fz = z+fj; /* F[z] */
116 int32 Fz1 = Fz^1; /* F[z+1] */
117
118 out[pos>>3] ^= fj<<(pos&7);
119 pos += step;
120
121 B[z] = (A[z]<<16)|Fz;
122 B[z+1] = (A[z+1]<<16)|Fz1;
123 }
124 /* B = (pi^(-1)<<16)+F */
125
126 crypto_sort_int32(B,n); /* B = (id<<16)+F(pi) */
127
128 pos += (2*w-3)*step*(n/2);
129
130 for (k = 0;k < n/2;++k) {
131 long long y = 2*k;
132 int32 lk = crypto_int32_bottombit_01(B[y]); /* l[k] */
133 int32 Ly = y+lk; /* L[y] */
134 int32 Ly1 = Ly^1; /* L[y+1] */
135
136 out[pos>>3] ^= lk<<(pos&7);
137 pos += step;
138
139 A[y] = (Ly<<16)|(B[y]&0xffff);
140 A[y+1] = (Ly1<<16)|(B[y+1]&0xffff);
141 }
142 /* A = (L<<16)+F(pi) */
143
144 crypto_sort_int32(A,n); /* A = (id<<16)+F(pi(L)) = (id<<16)+M */
145
146 pos -= (2*w-2)*step*(n/2);
147
148 for (j = 0;j < n/2;++j) {
149 q[j] = (A[2*j]&0xffff)>>1;
150 q[j+n/2] = (A[2*j+1]&0xffff)>>1;
151 }
152
153 cbrecursion(out,pos,step*2,q,w-1,n/2,temp);
154 cbrecursion(out,pos+step,step*2,q+n/2,w-1,n/2,temp);
155 }
156
157 /* input: p, an array of int16 */
158 /* input: n, length of p */
159 /* input: s, meaning that stride-2^s cswaps are performed */
160 /* input: cb, the control bits */
161 /* output: the result of apply the control bits to p */
162 static void layer(int16_t *p, const unsigned char *cb, int s, int n)
163 {
164 int i, j;
165 int stride = 1 << s;
166 int index = 0;
167 int16_t d;
168
169 for (i = 0; i < n; i += stride*2)
170 {
171 for (j = 0; j < stride; j++)
172 {
173 d = p[ i+j ] ^ p[ i+j+stride ];
174 d &= crypto_int8_bitmod_mask(cb[ index >> 3 ], index);
175 p[ i+j ] ^= d;
176 p[ i+j+stride ] ^= d;
177 index++;
178 }
179 }
180 }
181
182 /* parameters: 1 <= w <= 14; n = 2^w */
183 /* input: permutation pi of {0,1,...,n-1} */
184 /* output: (2m-1)n/2 control bits at positions 0,1,... */
185 /* output position pos is by definition 1&(out[pos/8]>>(pos&7)) */
186 void controlbitsfrompermutation(unsigned char *out,const int16 *pi,long long w,long long n)
187 {
188 int32 temp[2*n];
189 int16 pi_test[n], diff;
190 int i;
191 unsigned char *ptr;
192
193 while (1)
194 {
195 memset(out,0,(((2*w-1)*n/2)+7)/8);
196 cbrecursion(out,0,1,pi,w,n,temp);
197
198 // check for correctness
199
200 for (i = 0; i < n; i++)
201 pi_test[i] = i;
202
203 ptr = out;
204 for (i = 0; i < w; i++)
205 {
206 layer(pi_test, ptr, i, n);
207 ptr += n >> 4;
208 }
209
210 for (i = w-2; i >= 0; i--)
211 {
212 layer(pi_test, ptr, i, n);
213 ptr += n >> 4;
214 }
215
216 diff = 0;
217 for (i = 0; i < n; i++)
218 diff |= pi[i] ^ pi_test[i];
219
220 diff = crypto_int16_nonzero_mask(diff);
221 crypto_declassify(&diff,sizeof diff);
222 if (diff == 0)
223 break;
224 }
225 }
226