| 1 |
#!/usr/bin/env python3 |
| 2 |
|
| 3 |
import re |
| 4 |
import sys |
| 5 |
from math import ceil |
| 6 |
|
| 7 |
p = int(sys.argv[1]) |
| 8 |
numvec = ceil(p/256) |
| 9 |
ppad = 256*numvec |
| 10 |
|
| 11 |
# see comment below about order of coefficients |
| 12 |
f = [-1,-1] + [0]*(p-2) + [1] |
| 13 |
f = list(reversed(f)) |
| 14 |
while len(f)%256: f += [0] |
| 15 |
f0 = [] |
| 16 |
for j in range(len(f)//256): |
| 17 |
for i in range(4): |
| 18 |
for k in range(64): |
| 19 |
f0 += [f[j*256+i+k*4]] |
| 20 |
f1 = [1 if f0i<0 else 0 for f0i in f0] |
| 21 |
f0 = [f0i&1 for f0i in f0] |
| 22 |
|
| 23 |
# ---------- utility functions |
| 24 |
|
| 25 |
out = """\ |
| 26 |
// 20250302 djb: port to -Wc++-compat |
| 27 |
// 20240812 djb: more cryptoint usage |
| 28 |
#include "crypto_core.h" |
| 29 |
|
| 30 |
#include <immintrin.h> |
| 31 |
|
| 32 |
#include "crypto_int8.h" |
| 33 |
#define int8 crypto_int8 |
| 34 |
typedef int8 small; |
| 35 |
|
| 36 |
#include "crypto_int32.h" |
| 37 |
#include "crypto_int64.h" |
| 38 |
#include "crypto_uint64.h" |
| 39 |
|
| 40 |
#define p P |
| 41 |
#define ppad PPAD |
| 42 |
#define numvec NUMVEC |
| 43 |
|
| 44 |
typedef __m256i vec256; |
| 45 |
|
| 46 |
/* |
| 47 |
This code stores PPAD-coeff poly as vec256[NUMVEC]. |
| 48 |
Order of 256 coefficients in each vec256 |
| 49 |
is optimized in light of costs of vector instructions: |
| 50 |
0,4,...,252 in 64-bit word; |
| 51 |
1,5,...,253 in 64-bit word; |
| 52 |
2,6,...,254 in 64-bit word; |
| 53 |
3,7,...,255 in 64-bit word. |
| 54 |
*/ |
| 55 |
|
| 56 |
static inline void vec256_frombits(vec256 *v,const small *b) |
| 57 |
{ |
| 58 |
int i; |
| 59 |
|
| 60 |
for (i = 0;i < numvec;++i) { |
| 61 |
vec256 b0 = _mm256_loadu_si256((vec256 *) b); b += 32; /* 0,1,...,31 */ |
| 62 |
vec256 b1 = _mm256_loadu_si256((vec256 *) b); b += 32; /* 32,33,... */ |
| 63 |
vec256 b2 = _mm256_loadu_si256((vec256 *) b); b += 32; |
| 64 |
vec256 b3 = _mm256_loadu_si256((vec256 *) b); b += 32; |
| 65 |
vec256 b4 = _mm256_loadu_si256((vec256 *) b); b += 32; |
| 66 |
vec256 b5 = _mm256_loadu_si256((vec256 *) b); b += 32; |
| 67 |
vec256 b6 = _mm256_loadu_si256((vec256 *) b); b += 32; |
| 68 |
vec256 b7 = _mm256_loadu_si256((vec256 *) b); b += 32; |
| 69 |
|
| 70 |
vec256 c0 = _mm256_unpacklo_epi32(b0,b1); /* 0 1 2 3 32 33 34 35 4 5 6 7 36 37 38 39 ... 55 */ |
| 71 |
vec256 c1 = _mm256_unpackhi_epi32(b0,b1); /* 8 9 10 11 40 41 42 43 ... 63 */ |
| 72 |
vec256 c2 = _mm256_unpacklo_epi32(b2,b3); |
| 73 |
vec256 c3 = _mm256_unpackhi_epi32(b2,b3); |
| 74 |
vec256 c4 = _mm256_unpacklo_epi32(b4,b5); |
| 75 |
vec256 c5 = _mm256_unpackhi_epi32(b4,b5); |
| 76 |
vec256 c6 = _mm256_unpacklo_epi32(b6,b7); |
| 77 |
vec256 c7 = _mm256_unpackhi_epi32(b6,b7); |
| 78 |
|
| 79 |
vec256 d0 = c0 | _mm256_slli_epi32(c1,2); /* 0 8, 1 9, 2 10, 3 11, 32 40, 33 41, ..., 55 63 */ |
| 80 |
vec256 d2 = c2 | _mm256_slli_epi32(c3,2); |
| 81 |
vec256 d4 = c4 | _mm256_slli_epi32(c5,2); |
| 82 |
vec256 d6 = c6 | _mm256_slli_epi32(c7,2); |
| 83 |
|
| 84 |
vec256 e0 = _mm256_unpacklo_epi64(d0,d2); |
| 85 |
vec256 e2 = _mm256_unpackhi_epi64(d0,d2); |
| 86 |
vec256 e4 = _mm256_unpacklo_epi64(d4,d6); |
| 87 |
vec256 e6 = _mm256_unpackhi_epi64(d4,d6); |
| 88 |
|
| 89 |
vec256 f0 = e0 | _mm256_slli_epi32(e2,1); |
| 90 |
vec256 f4 = e4 | _mm256_slli_epi32(e6,1); |
| 91 |
|
| 92 |
vec256 g0 = _mm256_permute2x128_si256(f0,f4,0x20); |
| 93 |
vec256 g4 = _mm256_permute2x128_si256(f0,f4,0x31); |
| 94 |
|
| 95 |
vec256 h = g0 | _mm256_slli_epi32(g4,4); |
| 96 |
|
| 97 |
#define TRANSPOSE _mm256_set_epi8( 31,27,23,19, 30,26,22,18, 29,25,21,17, 28,24,20,16, 15,11,7,3, 14,10,6,2, 13,9,5,1, 12,8,4,0 ) |
| 98 |
h = _mm256_shuffle_epi8(h,TRANSPOSE); |
| 99 |
h = _mm256_permute4x64_epi64(h,0xd8); |
| 100 |
h = _mm256_shuffle_epi32(h,0xd8); |
| 101 |
|
| 102 |
*v++ = h; |
| 103 |
} |
| 104 |
} |
| 105 |
|
| 106 |
static inline void vec256_tobits(const vec256 *v,small *b) |
| 107 |
{ |
| 108 |
int i; |
| 109 |
|
| 110 |
for (i = 0;i < numvec;++i) { |
| 111 |
vec256 h = *v++; |
| 112 |
|
| 113 |
h = _mm256_shuffle_epi32(h,0xd8); |
| 114 |
h = _mm256_permute4x64_epi64(h,0xd8); |
| 115 |
h = _mm256_shuffle_epi8(h,TRANSPOSE); |
| 116 |
|
| 117 |
vec256 g0 = h & _mm256_set1_epi8(15); |
| 118 |
vec256 g4 = _mm256_srli_epi32(h,4) & _mm256_set1_epi8(15); |
| 119 |
|
| 120 |
vec256 f0 = _mm256_permute2x128_si256(g0,g4,0x20); |
| 121 |
vec256 f4 = _mm256_permute2x128_si256(g0,g4,0x31); |
| 122 |
|
| 123 |
vec256 e0 = f0 & _mm256_set1_epi8(5); |
| 124 |
vec256 e2 = _mm256_srli_epi32(f0,1) & _mm256_set1_epi8(5); |
| 125 |
vec256 e4 = f4 & _mm256_set1_epi8(5); |
| 126 |
vec256 e6 = _mm256_srli_epi32(f4,1) & _mm256_set1_epi8(5); |
| 127 |
|
| 128 |
vec256 d0 = _mm256_unpacklo_epi32(e0,e2); |
| 129 |
vec256 d2 = _mm256_unpackhi_epi32(e0,e2); |
| 130 |
vec256 d4 = _mm256_unpacklo_epi32(e4,e6); |
| 131 |
vec256 d6 = _mm256_unpackhi_epi32(e4,e6); |
| 132 |
|
| 133 |
vec256 c0 = d0 & _mm256_set1_epi8(1); |
| 134 |
vec256 c1 = _mm256_srli_epi32(d0,2) & _mm256_set1_epi8(1); |
| 135 |
vec256 c2 = d2 & _mm256_set1_epi8(1); |
| 136 |
vec256 c3 = _mm256_srli_epi32(d2,2) & _mm256_set1_epi8(1); |
| 137 |
vec256 c4 = d4 & _mm256_set1_epi8(1); |
| 138 |
vec256 c5 = _mm256_srli_epi32(d4,2) & _mm256_set1_epi8(1); |
| 139 |
vec256 c6 = d6 & _mm256_set1_epi8(1); |
| 140 |
vec256 c7 = _mm256_srli_epi32(d6,2) & _mm256_set1_epi8(1); |
| 141 |
|
| 142 |
vec256 b0 = _mm256_unpacklo_epi64(c0,c1); |
| 143 |
vec256 b1 = _mm256_unpackhi_epi64(c0,c1); |
| 144 |
vec256 b2 = _mm256_unpacklo_epi64(c2,c3); |
| 145 |
vec256 b3 = _mm256_unpackhi_epi64(c2,c3); |
| 146 |
vec256 b4 = _mm256_unpacklo_epi64(c4,c5); |
| 147 |
vec256 b5 = _mm256_unpackhi_epi64(c4,c5); |
| 148 |
vec256 b6 = _mm256_unpacklo_epi64(c6,c7); |
| 149 |
vec256 b7 = _mm256_unpackhi_epi64(c6,c7); |
| 150 |
|
| 151 |
_mm256_storeu_si256((vec256 *) b,b0); b += 32; |
| 152 |
_mm256_storeu_si256((vec256 *) b,b1); b += 32; |
| 153 |
_mm256_storeu_si256((vec256 *) b,b2); b += 32; |
| 154 |
_mm256_storeu_si256((vec256 *) b,b3); b += 32; |
| 155 |
_mm256_storeu_si256((vec256 *) b,b4); b += 32; |
| 156 |
_mm256_storeu_si256((vec256 *) b,b5); b += 32; |
| 157 |
_mm256_storeu_si256((vec256 *) b,b6); b += 32; |
| 158 |
_mm256_storeu_si256((vec256 *) b,b7); b += 32; |
| 159 |
} |
| 160 |
} |
| 161 |
|
| 162 |
static void vec256_init(vec256 *G0,vec256 *G1,const small *s) |
| 163 |
{ |
| 164 |
int i; |
| 165 |
small srev[ppad+(ppad-p)]; |
| 166 |
small si; |
| 167 |
small g0[ppad]; |
| 168 |
small g1[ppad]; |
| 169 |
|
| 170 |
for (i = 0;i < p;++i) srev[ppad-1-i] = s[i]; |
| 171 |
for (i = 0;i < ppad-p;++i) srev[i] = 0; |
| 172 |
for (i = p;i < ppad;++i) srev[i+ppad-p] = 0; |
| 173 |
|
| 174 |
for (i = 0;i < ppad;++i) { |
| 175 |
si = srev[i+ppad-p]; |
| 176 |
g0[i] = crypto_int8_bottombit_01(si); |
| 177 |
g1[i] = (si >> 1) & g0[i]; |
| 178 |
} |
| 179 |
|
| 180 |
vec256_frombits(G0,g0); |
| 181 |
vec256_frombits(G1,g1); |
| 182 |
} |
| 183 |
|
| 184 |
static void vec256_final(small *out,const vec256 *V0,const vec256 *V1) |
| 185 |
{ |
| 186 |
int i; |
| 187 |
small v0[ppad]; |
| 188 |
small v1[ppad]; |
| 189 |
small v[ppad]; |
| 190 |
small vrev[ppad+(ppad-p)]; |
| 191 |
|
| 192 |
vec256_tobits(V0,v0); |
| 193 |
vec256_tobits(V1,v1); |
| 194 |
|
| 195 |
for (i = 0;i < ppad;++i) |
| 196 |
v[i] = v0[i] + 2*v1[i] - 4*(v0[i]&v1[i]); |
| 197 |
|
| 198 |
for (i = 0;i < ppad;++i) vrev[i] = v[ppad-1-i]; |
| 199 |
for (i = ppad;i < ppad+(ppad-p);++i) vrev[i] = 0; |
| 200 |
|
| 201 |
for (i = 0;i < p;++i) out[i] = vrev[i+ppad-p]; |
| 202 |
} |
| 203 |
|
| 204 |
static inline void vec256_swap(vec256 *f,vec256 *g,int len,vec256 mask) |
| 205 |
{ |
| 206 |
vec256 flip; |
| 207 |
int i; |
| 208 |
|
| 209 |
for (i = 0;i < len;++i) { |
| 210 |
flip = mask & (f[i] ^ g[i]); |
| 211 |
f[i] ^= flip; |
| 212 |
g[i] ^= flip; |
| 213 |
} |
| 214 |
} |
| 215 |
|
| 216 |
static inline void vec256_scale(vec256 *f0,vec256 *f1,const vec256 c0,const vec256 c1) |
| 217 |
{ |
| 218 |
int i; |
| 219 |
|
| 220 |
for (i = 0;i < numvec;++i) { |
| 221 |
vec256 f0i = f0[i]; |
| 222 |
vec256 f1i = f1[i]; |
| 223 |
|
| 224 |
f0i &= c0; |
| 225 |
f1i ^= c1; |
| 226 |
f1i &= f0i; |
| 227 |
|
| 228 |
f0[i] = f0i; |
| 229 |
f1[i] = f1i; |
| 230 |
} |
| 231 |
} |
| 232 |
|
| 233 |
static inline void vec256_eliminate(vec256 *f0,vec256 *f1,vec256 *g0,vec256 *g1,int len,const vec256 c0,const vec256 c1) |
| 234 |
{ |
| 235 |
int i; |
| 236 |
|
| 237 |
for (i = 0;i < len;++i) { |
| 238 |
vec256 f0i = f0[i]; |
| 239 |
vec256 f1i = f1[i]; |
| 240 |
vec256 g0i = g0[i]; |
| 241 |
vec256 g1i = g1[i]; |
| 242 |
vec256 t; |
| 243 |
|
| 244 |
f0i &= c0; |
| 245 |
f1i ^= c1; |
| 246 |
f1i &= f0i; |
| 247 |
|
| 248 |
t = g0i ^ f0i; |
| 249 |
g0[i] = t | (g1i ^ f1i); |
| 250 |
g1[i] = (g1i ^ f0i) & (f1i ^ t); |
| 251 |
} |
| 252 |
} |
| 253 |
|
| 254 |
static inline int vec256_bit0mask(vec256 *f) |
| 255 |
{ |
| 256 |
return crypto_int32_bottombit_mask(_mm_cvtsi128_si32(_mm256_castsi256_si128(f[0]))); |
| 257 |
} |
| 258 |
|
| 259 |
""" |
| 260 |
|
| 261 |
# ---------- divx |
| 262 |
|
| 263 |
for j in range(1,numvec+1): |
| 264 |
out += 'static inline void vec256_divx_%d(vec256 *f)\n' % j |
| 265 |
out += '{\n' |
| 266 |
for i in range(j): |
| 267 |
out += ' vec256 f%d = f[%d];\n' % (i,i) |
| 268 |
out += '\n' |
| 269 |
for i in range(j): |
| 270 |
out += ' unsigned long long low%d = _mm_cvtsi128_si64(_mm256_castsi256_si128(f%d));\n' % (i,i) |
| 271 |
out += '\n' |
| 272 |
for i in range(j): |
| 273 |
if i == j-1: |
| 274 |
out += ' low%d = low%d >> 1;\n' % (i,i) |
| 275 |
else: |
| 276 |
out += ' low%d = (low%d >> 1) | crypto_uint64_shlmod(low%d,63);\n' % (i,i,i+1) |
| 277 |
out += '\n' |
| 278 |
for i in range(j): |
| 279 |
out += ' f%d = _mm256_blend_epi32(f%d,_mm256_set_epi64x(0,0,0,low%d),0x3);\n' % (i,i,i) |
| 280 |
out += '\n' |
| 281 |
for i in range(j): |
| 282 |
out += ' f[%d] = _mm256_permute4x64_epi64(f%d,0x39);\n' % (i,i) |
| 283 |
out += '}\n' |
| 284 |
out += '\n' |
| 285 |
|
| 286 |
# ---------- |
| 287 |
|
| 288 |
for j in range(1,numvec+1): |
| 289 |
out += 'static inline void vec256_timesx_%d(vec256 *f)\n' % j |
| 290 |
out += '{\n' |
| 291 |
for i in range(j): |
| 292 |
out += ' vec256 f%d = _mm256_permute4x64_epi64(f[%d],0x93);\n' % (i,i) |
| 293 |
out += '\n' |
| 294 |
for i in range(j): |
| 295 |
if (j,i) in [(3,0),(3,1)]: # XXX: search through subsets for optimal timings |
| 296 |
out += ' unsigned long long low%d = *(unsigned long long *) &f%d;\n' % (i,i) |
| 297 |
else: |
| 298 |
out += ' unsigned long long low%d = _mm_cvtsi128_si64(_mm256_castsi256_si128(f%d));\n' % (i,i) |
| 299 |
out += '\n' |
| 300 |
for i in reversed(range(j)): |
| 301 |
if i == 0: |
| 302 |
out += ' low%d = low%d << 1;\n' % (i,i) |
| 303 |
else: |
| 304 |
out += ' low%d = (low%d << 1) | crypto_int64_negative_01(low%d);\n' % (i,i,i-1) |
| 305 |
out += '\n' |
| 306 |
for i in range(j): |
| 307 |
if (j,i) in [(3,0),(3,1)]: # XXX: search through subsets for optimal timings |
| 308 |
out += ' *(unsigned long long *) &f%d = low%d;\n' % (i,i) |
| 309 |
else: |
| 310 |
out += ' f%d = _mm256_blend_epi32(f%d,_mm256_set_epi64x(0,0,0,low%d),0x3);\n' % (i,i,i) |
| 311 |
out += '\n' |
| 312 |
for i in range(j): |
| 313 |
out += ' f[%d] = f%d;\n' % (i,i) |
| 314 |
out += '}\n' |
| 315 |
out += '\n' |
| 316 |
|
| 317 |
# ---------- reciprocal initialization |
| 318 |
|
| 319 |
out += """ |
| 320 |
void crypto_core(unsigned char *outbytes,const unsigned char *inbytes,const unsigned char *kbytes,const unsigned char *cbytes) |
| 321 |
{ |
| 322 |
small *out = (small *) outbytes; |
| 323 |
small *in = (small *) inbytes; |
| 324 |
vec256 F0[numvec]; |
| 325 |
vec256 F1[numvec]; |
| 326 |
vec256 G0[numvec]; |
| 327 |
vec256 G1[numvec]; |
| 328 |
vec256 V0[numvec]; |
| 329 |
vec256 V1[numvec]; |
| 330 |
vec256 R0[numvec]; |
| 331 |
vec256 R1[numvec]; |
| 332 |
vec256 c0vec,c1vec; |
| 333 |
int loop; |
| 334 |
int c0,c1; |
| 335 |
int minusdelta = -1; |
| 336 |
int swapmask; |
| 337 |
vec256 swapvec; |
| 338 |
|
| 339 |
vec256_init(G0,G1,in); |
| 340 |
""" |
| 341 |
|
| 342 |
for name,bits in [('F0',f0),('F1',f1)]: |
| 343 |
for j in range(len(bits)//256): |
| 344 |
u = [] |
| 345 |
for k in range(j*256,j*256+256,32): |
| 346 |
u = [sum(bits[k+i]<<i for i in range(32))] + u |
| 347 |
if u == [0]*8: |
| 348 |
out += ' %s[%d] = _mm256_set1_epi32(0);\n' % (name,j) |
| 349 |
else: |
| 350 |
u = ','.join(str(uk if uk < 2**31 else uk-2**32) for uk in u) |
| 351 |
out += ' %s[%d] = _mm256_set_epi32(%s);\n' % (name,j,u) |
| 352 |
|
| 353 |
out += '\n' |
| 354 |
for i in range(numvec): |
| 355 |
out += ' V0[%d] = _mm256_set1_epi32(0);\n' % i |
| 356 |
out += ' V1[%d] = _mm256_set1_epi32(0);\n' % i |
| 357 |
|
| 358 |
out += '\n' |
| 359 |
for i in range(numvec): |
| 360 |
if i == 0: |
| 361 |
out += ' R0[%d] = _mm256_set_epi32(0,0,0,0,0,0,0,1);\n' % i |
| 362 |
else: |
| 363 |
out += ' R0[%d] = _mm256_set1_epi32(0);\n' % i |
| 364 |
out += ' R1[%d] = _mm256_set1_epi32(0);\n' % i |
| 365 |
|
| 366 |
# ---------- reciprocal main loop |
| 367 |
|
| 368 |
vvecgvec = [] |
| 369 |
for loop in range(2*p-1): |
| 370 |
vvec = min(numvec,1+loop//256) |
| 371 |
gvec = min(numvec,1+(2*p-2-loop)//256) |
| 372 |
vvecgvec += [(vvec,gvec)] |
| 373 |
|
| 374 |
while len(vvecgvec) > 0: |
| 375 |
vvec,gvec = vvecgvec[0] |
| 376 |
loops = 1 |
| 377 |
while loops < len(vvecgvec) and vvecgvec[loops] == (vvec,gvec): |
| 378 |
loops += 1 |
| 379 |
|
| 380 |
out += """ |
| 381 |
for (loop = %d;loop > 0;--loop) { |
| 382 |
vec256_timesx_%d(V0); |
| 383 |
vec256_timesx_%d(V1); |
| 384 |
swapmask = crypto_int32_negative_mask(minusdelta) & vec256_bit0mask(G0); |
| 385 |
|
| 386 |
c0 = vec256_bit0mask(F0) & vec256_bit0mask(G0); |
| 387 |
c1 = vec256_bit0mask(F1) ^ vec256_bit0mask(G1); |
| 388 |
c1 &= c0; |
| 389 |
|
| 390 |
minusdelta ^= swapmask & (minusdelta ^ -minusdelta); |
| 391 |
minusdelta -= 1; |
| 392 |
|
| 393 |
swapvec = _mm256_set1_epi32(swapmask); |
| 394 |
vec256_swap(F0,G0,%d,swapvec); |
| 395 |
vec256_swap(F1,G1,%d,swapvec); |
| 396 |
|
| 397 |
c0vec = _mm256_set1_epi32(c0); |
| 398 |
c1vec = _mm256_set1_epi32(c1); |
| 399 |
|
| 400 |
vec256_eliminate(F0,F1,G0,G1,%d,c0vec,c1vec); |
| 401 |
vec256_divx_%d(G0); |
| 402 |
vec256_divx_%d(G1); |
| 403 |
|
| 404 |
vec256_swap(V0,R0,%d,swapvec); |
| 405 |
vec256_swap(V1,R1,%d,swapvec); |
| 406 |
vec256_eliminate(V0,V1,R0,R1,%d,c0vec,c1vec); |
| 407 |
} |
| 408 |
""" % (loops,vvec,vvec,gvec,gvec,gvec,gvec,gvec,vvec,vvec,vvec) |
| 409 |
|
| 410 |
vvecgvec = vvecgvec[loops:] |
| 411 |
|
| 412 |
# ---------- reciprocal finalization |
| 413 |
|
| 414 |
out += """ |
| 415 |
c0vec = _mm256_set1_epi32(vec256_bit0mask(F0)); |
| 416 |
c1vec = _mm256_set1_epi32(vec256_bit0mask(F1)); |
| 417 |
vec256_scale(V0,V1,c0vec,c1vec); |
| 418 |
|
| 419 |
vec256_final(out,V0,V1); |
| 420 |
out[p] = crypto_int32_negative_mask(minusdelta); |
| 421 |
}\ |
| 422 |
""" |
| 423 |
|
| 424 |
out = re.sub(r'\bP\b',str(p),out) |
| 425 |
out = re.sub(r'\bPPAD\b',str(ppad),out) |
| 426 |
out = re.sub(r'\bNUMVEC\b',str(numvec),out) |
| 427 |
|
| 428 |
print(out) |