Debian Codegraph @

crypto_core/invsntrup761/avx/recip.c

raw
1 // 20250302 djb: port to -Wc++-compat
2 // 20240806 djb: some automated conversion to cryptoint
3 #include <immintrin.h>
4
5 #include "crypto_int8.h"
6 #include "crypto_int16.h"
7 #include "crypto_int32.h"
8 #include "crypto_int64.h"
9 #define int8 crypto_int8
10 #define int16 crypto_int16
11 #define int32 crypto_int32
12
13 #include "crypto_core.h"
14
15 #include "params.h"
16
17 /* ----- arithmetic mod q */
18
19 typedef int8 small;
20
21 typedef int16 Fq;
22 /* always represented as -(q-1)/2...(q-1)/2 */
23
24 /* works for -7000000 < x < 7000000 if q in 4591, 4621, 5167, 6343, 7177, 7879 */
25 static Fq Fq_freeze(int32 x)
26 {
27 x -= q*((q18*x)>>18);
28 x -= q*((q27*x+67108864)>>27);
29 return x;
30 }
31
32 static Fq Fq_bigfreeze(int32 x)
33 {
34 x -= q*((q14*x)>>14);
35 x -= q*((q18*x)>>18);
36 x -= q*((q27*x+67108864)>>27);
37 x -= q*((q27*x+67108864)>>27);
38 return x;
39 }
40
41 /* nonnegative e */
42 static Fq Fq_pow(Fq a,int e)
43 {
44 if (e == 0) return 1;
45 if (e == 1) return a;
46 if (crypto_int64_bottombit_01(e)) return Fq_bigfreeze(a*(int32)Fq_pow(a,e-1));
47 a = Fq_bigfreeze(a*(int32)a);
48 return Fq_pow(a,e>>1);
49 }
50
51 static Fq Fq_recip(Fq a)
52 {
53 return Fq_pow(a,q-2);
54 }
55
56 /* ----- more */
57
58 #define qvec _mm256_set1_epi16(q)
59 #define qinvvec _mm256_set1_epi16(qinv)
60
61 static inline __m256i montproduct(__m256i x,__m256i y,__m256i yqinv)
62 {
63 __m256i hi,d,e;
64
65 d = _mm256_mullo_epi16(x,yqinv);
66 hi = _mm256_mulhi_epi16(x,y);
67 e = _mm256_mulhi_epi16(d,qvec);
68 return _mm256_sub_epi16(hi,e);
69 }
70
71 static inline void vectormodq_swapeliminate(Fq *f,Fq *g,int len,const Fq f0,const Fq g0,int mask)
72 {
73 __m256i f0vec = _mm256_set1_epi16(f0);
74 __m256i g0vec = _mm256_set1_epi16(g0);
75 __m256i f0vecqinv = _mm256_mullo_epi16(f0vec,qinvvec);
76 __m256i g0vecqinv = _mm256_mullo_epi16(g0vec,qinvvec);
77 __m256i maskvec = _mm256_set1_epi32(mask);
78
79 while (len > 0) {
80 __m256i fi = _mm256_loadu_si256((__m256i *) f);
81 __m256i gi = _mm256_loadu_si256((__m256i *) g);
82 __m256i finew = _mm256_blendv_epi8(fi,gi,maskvec);
83 __m256i ginew = _mm256_blendv_epi8(gi,fi,maskvec);
84 ginew = _mm256_sub_epi16(montproduct(ginew,f0vec,f0vecqinv),montproduct(finew,g0vec,g0vecqinv));
85 _mm256_storeu_si256((__m256i *) f,finew);
86 _mm256_storeu_si256((__m256i *) (g-1),ginew);
87 f += 16;
88 g += 16;
89 len -= 16;
90 }
91 }
92
93 static inline void vectormodq_xswapeliminate(Fq *f,Fq *g,int len,const Fq f0,const Fq g0,int mask)
94 {
95 __m256i f0vec = _mm256_set1_epi16(f0);
96 __m256i g0vec = _mm256_set1_epi16(g0);
97 __m256i f0vecqinv = _mm256_mullo_epi16(f0vec,qinvvec);
98 __m256i g0vecqinv = _mm256_mullo_epi16(g0vec,qinvvec);
99 __m256i maskvec = _mm256_set1_epi32(mask);
100
101 f += len + (-len & 15);
102 g += len + (-len & 15);
103 while (len > 0) {
104 f -= 16;
105 g -= 16;
106 len -= 16;
107 __m256i fi = _mm256_loadu_si256((__m256i *) f);
108 __m256i gi = _mm256_loadu_si256((__m256i *) g);
109 __m256i finew = _mm256_blendv_epi8(fi,gi,maskvec);
110 __m256i ginew = _mm256_blendv_epi8(gi,fi,maskvec);
111 ginew = _mm256_sub_epi16(montproduct(ginew,f0vec,f0vecqinv),montproduct(finew,g0vec,g0vecqinv));
112 _mm256_storeu_si256((__m256i *) (f+1),finew);
113 _mm256_storeu_si256((__m256i *) g,ginew);
114 }
115 }
116
117 void crypto_core(unsigned char *outbytes,const unsigned char *inbytes,const unsigned char *kbytes,const unsigned char *cbytes)
118 {
119 small *in = (small *) inbytes;
120 int loop;
121 Fq out[p],f[ppad],g[ppad],v[ppad],r[ppad];
122 Fq f0,g0;
123 Fq scale;
124 int i;
125 int delta = 1;
126 int minusdelta;
127 int fgflip;
128 int swap;
129
130 for (i = 0;i < ppad;++i) f[i] = 0;
131 f[0] = 1;
132 f[p-1] = -1;
133 f[p] = -1;
134 /* generalization: initialize f to reversal of any deg-p polynomial m */
135
136 for (i = 0;i < p;++i) g[i] = in[p-1-i];
137 for (i = p;i < ppad;++i) g[i] = 0;
138
139 for (i = 0;i < ppad;++i) r[i] = 0;
140 r[0] = Fq_recip(3);
141
142 for (i = 0;i < ppad;++i) v[i] = 0;
143
144 for (loop = 0;loop < p;++loop) {
145 g0 = Fq_freeze(g[0]);
146 f0 = f[0];
147 if (q > 5167) f0 = Fq_freeze(f0);
148
149 minusdelta = -delta;
150 swap = crypto_int16_negative_mask(minusdelta) & crypto_int16_nonzero_mask(g0);
151 delta ^= swap & (delta ^ minusdelta);
152 delta += 1;
153
154 fgflip = swap & (f0 ^ g0);
155 f0 ^= fgflip;
156 g0 ^= fgflip;
157
158 f[0] = f0;
159
160 vectormodq_swapeliminate(f+1,g+1,p,f0,g0,swap);
161 vectormodq_xswapeliminate(v,r,loop+1,f0,g0,swap);
162 }
163
164 for (loop = p-1;loop > 0;--loop) {
165 g0 = Fq_freeze(g[0]);
166 f0 = f[0];
167 if (q > 5167) f0 = Fq_freeze(f0);
168
169 minusdelta = -delta;
170 swap = crypto_int16_negative_mask(minusdelta) & crypto_int16_nonzero_mask(g0);
171 delta ^= swap & (delta ^ minusdelta);
172 delta += 1;
173
174 fgflip = swap & (f0 ^ g0);
175 f0 ^= fgflip;
176 g0 ^= fgflip;
177
178 f[0] = f0;
179
180 vectormodq_swapeliminate(f+1,g+1,loop,f0,g0,swap);
181 vectormodq_xswapeliminate(v,r,p,f0,g0,swap);
182 }
183
184 scale = Fq_recip(Fq_freeze(f[0]));
185 for (i = 0;i < p;++i) out[i] = Fq_bigfreeze(scale*(int32)Fq_freeze(v[p-i]));
186
187 crypto_encode_pxint16(outbytes,out);
188 outbytes[2*p] = crypto_int16_nonzero_mask(delta);
189 }