1 #include <string.h>
2
3 #include "private/common.h"
4 #include "utils.h"
5
6 /*
7 h = 0
8 */
9
10 static inline void
fe25519_0(fe25519 h)11 fe25519_0(fe25519 h)
12 {
13 memset(&h[0], 0, 10 * sizeof h[0]);
14 }
15
16 /*
17 h = 1
18 */
19
20 static inline void
fe25519_1(fe25519 h)21 fe25519_1(fe25519 h)
22 {
23 h[0] = 1;
24 h[1] = 0;
25 memset(&h[2], 0, 8 * sizeof h[0]);
26 }
27
28 /*
29 h = f + g
30 Can overlap h with f or g.
31 *
32 Preconditions:
33 |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
34 |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
35 *
36 Postconditions:
37 |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
38 */
39
40 static inline void
fe25519_add(fe25519 h,const fe25519 f,const fe25519 g)41 fe25519_add(fe25519 h, const fe25519 f, const fe25519 g)
42 {
43 int32_t h0 = f[0] + g[0];
44 int32_t h1 = f[1] + g[1];
45 int32_t h2 = f[2] + g[2];
46 int32_t h3 = f[3] + g[3];
47 int32_t h4 = f[4] + g[4];
48 int32_t h5 = f[5] + g[5];
49 int32_t h6 = f[6] + g[6];
50 int32_t h7 = f[7] + g[7];
51 int32_t h8 = f[8] + g[8];
52 int32_t h9 = f[9] + g[9];
53
54 h[0] = h0;
55 h[1] = h1;
56 h[2] = h2;
57 h[3] = h3;
58 h[4] = h4;
59 h[5] = h5;
60 h[6] = h6;
61 h[7] = h7;
62 h[8] = h8;
63 h[9] = h9;
64 }
65
66 /*
67 h = f - g
68 Can overlap h with f or g.
69 *
70 Preconditions:
71 |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
72 |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
73 *
74 Postconditions:
75 |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
76 */
77
78 static void
fe25519_sub(fe25519 h,const fe25519 f,const fe25519 g)79 fe25519_sub(fe25519 h, const fe25519 f, const fe25519 g)
80 {
81 int32_t h0 = f[0] - g[0];
82 int32_t h1 = f[1] - g[1];
83 int32_t h2 = f[2] - g[2];
84 int32_t h3 = f[3] - g[3];
85 int32_t h4 = f[4] - g[4];
86 int32_t h5 = f[5] - g[5];
87 int32_t h6 = f[6] - g[6];
88 int32_t h7 = f[7] - g[7];
89 int32_t h8 = f[8] - g[8];
90 int32_t h9 = f[9] - g[9];
91
92 h[0] = h0;
93 h[1] = h1;
94 h[2] = h2;
95 h[3] = h3;
96 h[4] = h4;
97 h[5] = h5;
98 h[6] = h6;
99 h[7] = h7;
100 h[8] = h8;
101 h[9] = h9;
102 }
103
104 /*
105 h = -f
106 *
107 Preconditions:
108 |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
109 *
110 Postconditions:
111 |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
112 */
113
114 static inline void
fe25519_neg(fe25519 h,const fe25519 f)115 fe25519_neg(fe25519 h, const fe25519 f)
116 {
117 int32_t h0 = -f[0];
118 int32_t h1 = -f[1];
119 int32_t h2 = -f[2];
120 int32_t h3 = -f[3];
121 int32_t h4 = -f[4];
122 int32_t h5 = -f[5];
123 int32_t h6 = -f[6];
124 int32_t h7 = -f[7];
125 int32_t h8 = -f[8];
126 int32_t h9 = -f[9];
127
128 h[0] = h0;
129 h[1] = h1;
130 h[2] = h2;
131 h[3] = h3;
132 h[4] = h4;
133 h[5] = h5;
134 h[6] = h6;
135 h[7] = h7;
136 h[8] = h8;
137 h[9] = h9;
138 }
139
140 /*
141 Replace (f,g) with (g,g) if b == 1;
142 replace (f,g) with (f,g) if b == 0.
143 *
144 Preconditions: b in {0,1}.
145 */
146
147 static void
fe25519_cmov(fe25519 f,const fe25519 g,unsigned int b)148 fe25519_cmov(fe25519 f, const fe25519 g, unsigned int b)
149 {
150 const uint32_t mask = (uint32_t) (-(int32_t) b);
151
152 int32_t f0 = f[0];
153 int32_t f1 = f[1];
154 int32_t f2 = f[2];
155 int32_t f3 = f[3];
156 int32_t f4 = f[4];
157 int32_t f5 = f[5];
158 int32_t f6 = f[6];
159 int32_t f7 = f[7];
160 int32_t f8 = f[8];
161 int32_t f9 = f[9];
162
163 int32_t x0 = f0 ^ g[0];
164 int32_t x1 = f1 ^ g[1];
165 int32_t x2 = f2 ^ g[2];
166 int32_t x3 = f3 ^ g[3];
167 int32_t x4 = f4 ^ g[4];
168 int32_t x5 = f5 ^ g[5];
169 int32_t x6 = f6 ^ g[6];
170 int32_t x7 = f7 ^ g[7];
171 int32_t x8 = f8 ^ g[8];
172 int32_t x9 = f9 ^ g[9];
173
174 x0 &= mask;
175 x1 &= mask;
176 x2 &= mask;
177 x3 &= mask;
178 x4 &= mask;
179 x5 &= mask;
180 x6 &= mask;
181 x7 &= mask;
182 x8 &= mask;
183 x9 &= mask;
184
185 f[0] = f0 ^ x0;
186 f[1] = f1 ^ x1;
187 f[2] = f2 ^ x2;
188 f[3] = f3 ^ x3;
189 f[4] = f4 ^ x4;
190 f[5] = f5 ^ x5;
191 f[6] = f6 ^ x6;
192 f[7] = f7 ^ x7;
193 f[8] = f8 ^ x8;
194 f[9] = f9 ^ x9;
195 }
196
197 static void
fe25519_cswap(fe25519 f,fe25519 g,unsigned int b)198 fe25519_cswap(fe25519 f, fe25519 g, unsigned int b)
199 {
200 const uint32_t mask = (uint32_t) (-(int64_t) b);
201
202 int32_t f0 = f[0];
203 int32_t f1 = f[1];
204 int32_t f2 = f[2];
205 int32_t f3 = f[3];
206 int32_t f4 = f[4];
207 int32_t f5 = f[5];
208 int32_t f6 = f[6];
209 int32_t f7 = f[7];
210 int32_t f8 = f[8];
211 int32_t f9 = f[9];
212
213 int32_t g0 = g[0];
214 int32_t g1 = g[1];
215 int32_t g2 = g[2];
216 int32_t g3 = g[3];
217 int32_t g4 = g[4];
218 int32_t g5 = g[5];
219 int32_t g6 = g[6];
220 int32_t g7 = g[7];
221 int32_t g8 = g[8];
222 int32_t g9 = g[9];
223
224 int32_t x0 = f0 ^ g0;
225 int32_t x1 = f1 ^ g1;
226 int32_t x2 = f2 ^ g2;
227 int32_t x3 = f3 ^ g3;
228 int32_t x4 = f4 ^ g4;
229 int32_t x5 = f5 ^ g5;
230 int32_t x6 = f6 ^ g6;
231 int32_t x7 = f7 ^ g7;
232 int32_t x8 = f8 ^ g8;
233 int32_t x9 = f9 ^ g9;
234
235 x0 &= mask;
236 x1 &= mask;
237 x2 &= mask;
238 x3 &= mask;
239 x4 &= mask;
240 x5 &= mask;
241 x6 &= mask;
242 x7 &= mask;
243 x8 &= mask;
244 x9 &= mask;
245
246 f[0] = f0 ^ x0;
247 f[1] = f1 ^ x1;
248 f[2] = f2 ^ x2;
249 f[3] = f3 ^ x3;
250 f[4] = f4 ^ x4;
251 f[5] = f5 ^ x5;
252 f[6] = f6 ^ x6;
253 f[7] = f7 ^ x7;
254 f[8] = f8 ^ x8;
255 f[9] = f9 ^ x9;
256
257 g[0] = g0 ^ x0;
258 g[1] = g1 ^ x1;
259 g[2] = g2 ^ x2;
260 g[3] = g3 ^ x3;
261 g[4] = g4 ^ x4;
262 g[5] = g5 ^ x5;
263 g[6] = g6 ^ x6;
264 g[7] = g7 ^ x7;
265 g[8] = g8 ^ x8;
266 g[9] = g9 ^ x9;
267 }
268
269 /*
270 h = f
271 */
272
273 static inline void
fe25519_copy(fe25519 h,const fe25519 f)274 fe25519_copy(fe25519 h, const fe25519 f)
275 {
276 int32_t f0 = f[0];
277 int32_t f1 = f[1];
278 int32_t f2 = f[2];
279 int32_t f3 = f[3];
280 int32_t f4 = f[4];
281 int32_t f5 = f[5];
282 int32_t f6 = f[6];
283 int32_t f7 = f[7];
284 int32_t f8 = f[8];
285 int32_t f9 = f[9];
286
287 h[0] = f0;
288 h[1] = f1;
289 h[2] = f2;
290 h[3] = f3;
291 h[4] = f4;
292 h[5] = f5;
293 h[6] = f6;
294 h[7] = f7;
295 h[8] = f8;
296 h[9] = f9;
297 }
298
299 /*
300 return 1 if f is in {1,3,5,...,q-2}
301 return 0 if f is in {0,2,4,...,q-1}
302
303 Preconditions:
304 |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
305 */
306
307 static inline int
fe25519_isnegative(const fe25519 f)308 fe25519_isnegative(const fe25519 f)
309 {
310 unsigned char s[32];
311
312 fe25519_tobytes(s, f);
313
314 return s[0] & 1;
315 }
316
317 /*
318 return 1 if f == 0
319 return 0 if f != 0
320
321 Preconditions:
322 |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
323 */
324
325 static inline int
fe25519_iszero(const fe25519 f)326 fe25519_iszero(const fe25519 f)
327 {
328 unsigned char s[32];
329
330 fe25519_tobytes(s, f);
331
332 return sodium_is_zero(s, 32);
333 }
334
335 /*
336 h = f * g
337 Can overlap h with f or g.
338 *
339 Preconditions:
340 |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
341 |g| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
342 *
343 Postconditions:
344 |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
345 */
346
347 /*
348 Notes on implementation strategy:
349 *
350 Using schoolbook multiplication.
351 Karatsuba would save a little in some cost models.
352 *
353 Most multiplications by 2 and 19 are 32-bit precomputations;
354 cheaper than 64-bit postcomputations.
355 *
356 There is one remaining multiplication by 19 in the carry chain;
357 one *19 precomputation can be merged into this,
358 but the resulting data flow is considerably less clean.
359 *
360 There are 12 carries below.
361 10 of them are 2-way parallelizable and vectorizable.
362 Can get away with 11 carries, but then data flow is much deeper.
363 *
364 With tighter constraints on inputs can squeeze carries into int32.
365 */
366
367 static void
fe25519_mul(fe25519 h,const fe25519 f,const fe25519 g)368 fe25519_mul(fe25519 h, const fe25519 f, const fe25519 g)
369 {
370 int32_t f0 = f[0];
371 int32_t f1 = f[1];
372 int32_t f2 = f[2];
373 int32_t f3 = f[3];
374 int32_t f4 = f[4];
375 int32_t f5 = f[5];
376 int32_t f6 = f[6];
377 int32_t f7 = f[7];
378 int32_t f8 = f[8];
379 int32_t f9 = f[9];
380
381 int32_t g0 = g[0];
382 int32_t g1 = g[1];
383 int32_t g2 = g[2];
384 int32_t g3 = g[3];
385 int32_t g4 = g[4];
386 int32_t g5 = g[5];
387 int32_t g6 = g[6];
388 int32_t g7 = g[7];
389 int32_t g8 = g[8];
390 int32_t g9 = g[9];
391
392 int32_t g1_19 = 19 * g1; /* 1.959375*2^29 */
393 int32_t g2_19 = 19 * g2; /* 1.959375*2^30; still ok */
394 int32_t g3_19 = 19 * g3;
395 int32_t g4_19 = 19 * g4;
396 int32_t g5_19 = 19 * g5;
397 int32_t g6_19 = 19 * g6;
398 int32_t g7_19 = 19 * g7;
399 int32_t g8_19 = 19 * g8;
400 int32_t g9_19 = 19 * g9;
401 int32_t f1_2 = 2 * f1;
402 int32_t f3_2 = 2 * f3;
403 int32_t f5_2 = 2 * f5;
404 int32_t f7_2 = 2 * f7;
405 int32_t f9_2 = 2 * f9;
406
407 int64_t f0g0 = f0 * (int64_t) g0;
408 int64_t f0g1 = f0 * (int64_t) g1;
409 int64_t f0g2 = f0 * (int64_t) g2;
410 int64_t f0g3 = f0 * (int64_t) g3;
411 int64_t f0g4 = f0 * (int64_t) g4;
412 int64_t f0g5 = f0 * (int64_t) g5;
413 int64_t f0g6 = f0 * (int64_t) g6;
414 int64_t f0g7 = f0 * (int64_t) g7;
415 int64_t f0g8 = f0 * (int64_t) g8;
416 int64_t f0g9 = f0 * (int64_t) g9;
417 int64_t f1g0 = f1 * (int64_t) g0;
418 int64_t f1g1_2 = f1_2 * (int64_t) g1;
419 int64_t f1g2 = f1 * (int64_t) g2;
420 int64_t f1g3_2 = f1_2 * (int64_t) g3;
421 int64_t f1g4 = f1 * (int64_t) g4;
422 int64_t f1g5_2 = f1_2 * (int64_t) g5;
423 int64_t f1g6 = f1 * (int64_t) g6;
424 int64_t f1g7_2 = f1_2 * (int64_t) g7;
425 int64_t f1g8 = f1 * (int64_t) g8;
426 int64_t f1g9_38 = f1_2 * (int64_t) g9_19;
427 int64_t f2g0 = f2 * (int64_t) g0;
428 int64_t f2g1 = f2 * (int64_t) g1;
429 int64_t f2g2 = f2 * (int64_t) g2;
430 int64_t f2g3 = f2 * (int64_t) g3;
431 int64_t f2g4 = f2 * (int64_t) g4;
432 int64_t f2g5 = f2 * (int64_t) g5;
433 int64_t f2g6 = f2 * (int64_t) g6;
434 int64_t f2g7 = f2 * (int64_t) g7;
435 int64_t f2g8_19 = f2 * (int64_t) g8_19;
436 int64_t f2g9_19 = f2 * (int64_t) g9_19;
437 int64_t f3g0 = f3 * (int64_t) g0;
438 int64_t f3g1_2 = f3_2 * (int64_t) g1;
439 int64_t f3g2 = f3 * (int64_t) g2;
440 int64_t f3g3_2 = f3_2 * (int64_t) g3;
441 int64_t f3g4 = f3 * (int64_t) g4;
442 int64_t f3g5_2 = f3_2 * (int64_t) g5;
443 int64_t f3g6 = f3 * (int64_t) g6;
444 int64_t f3g7_38 = f3_2 * (int64_t) g7_19;
445 int64_t f3g8_19 = f3 * (int64_t) g8_19;
446 int64_t f3g9_38 = f3_2 * (int64_t) g9_19;
447 int64_t f4g0 = f4 * (int64_t) g0;
448 int64_t f4g1 = f4 * (int64_t) g1;
449 int64_t f4g2 = f4 * (int64_t) g2;
450 int64_t f4g3 = f4 * (int64_t) g3;
451 int64_t f4g4 = f4 * (int64_t) g4;
452 int64_t f4g5 = f4 * (int64_t) g5;
453 int64_t f4g6_19 = f4 * (int64_t) g6_19;
454 int64_t f4g7_19 = f4 * (int64_t) g7_19;
455 int64_t f4g8_19 = f4 * (int64_t) g8_19;
456 int64_t f4g9_19 = f4 * (int64_t) g9_19;
457 int64_t f5g0 = f5 * (int64_t) g0;
458 int64_t f5g1_2 = f5_2 * (int64_t) g1;
459 int64_t f5g2 = f5 * (int64_t) g2;
460 int64_t f5g3_2 = f5_2 * (int64_t) g3;
461 int64_t f5g4 = f5 * (int64_t) g4;
462 int64_t f5g5_38 = f5_2 * (int64_t) g5_19;
463 int64_t f5g6_19 = f5 * (int64_t) g6_19;
464 int64_t f5g7_38 = f5_2 * (int64_t) g7_19;
465 int64_t f5g8_19 = f5 * (int64_t) g8_19;
466 int64_t f5g9_38 = f5_2 * (int64_t) g9_19;
467 int64_t f6g0 = f6 * (int64_t) g0;
468 int64_t f6g1 = f6 * (int64_t) g1;
469 int64_t f6g2 = f6 * (int64_t) g2;
470 int64_t f6g3 = f6 * (int64_t) g3;
471 int64_t f6g4_19 = f6 * (int64_t) g4_19;
472 int64_t f6g5_19 = f6 * (int64_t) g5_19;
473 int64_t f6g6_19 = f6 * (int64_t) g6_19;
474 int64_t f6g7_19 = f6 * (int64_t) g7_19;
475 int64_t f6g8_19 = f6 * (int64_t) g8_19;
476 int64_t f6g9_19 = f6 * (int64_t) g9_19;
477 int64_t f7g0 = f7 * (int64_t) g0;
478 int64_t f7g1_2 = f7_2 * (int64_t) g1;
479 int64_t f7g2 = f7 * (int64_t) g2;
480 int64_t f7g3_38 = f7_2 * (int64_t) g3_19;
481 int64_t f7g4_19 = f7 * (int64_t) g4_19;
482 int64_t f7g5_38 = f7_2 * (int64_t) g5_19;
483 int64_t f7g6_19 = f7 * (int64_t) g6_19;
484 int64_t f7g7_38 = f7_2 * (int64_t) g7_19;
485 int64_t f7g8_19 = f7 * (int64_t) g8_19;
486 int64_t f7g9_38 = f7_2 * (int64_t) g9_19;
487 int64_t f8g0 = f8 * (int64_t) g0;
488 int64_t f8g1 = f8 * (int64_t) g1;
489 int64_t f8g2_19 = f8 * (int64_t) g2_19;
490 int64_t f8g3_19 = f8 * (int64_t) g3_19;
491 int64_t f8g4_19 = f8 * (int64_t) g4_19;
492 int64_t f8g5_19 = f8 * (int64_t) g5_19;
493 int64_t f8g6_19 = f8 * (int64_t) g6_19;
494 int64_t f8g7_19 = f8 * (int64_t) g7_19;
495 int64_t f8g8_19 = f8 * (int64_t) g8_19;
496 int64_t f8g9_19 = f8 * (int64_t) g9_19;
497 int64_t f9g0 = f9 * (int64_t) g0;
498 int64_t f9g1_38 = f9_2 * (int64_t) g1_19;
499 int64_t f9g2_19 = f9 * (int64_t) g2_19;
500 int64_t f9g3_38 = f9_2 * (int64_t) g3_19;
501 int64_t f9g4_19 = f9 * (int64_t) g4_19;
502 int64_t f9g5_38 = f9_2 * (int64_t) g5_19;
503 int64_t f9g6_19 = f9 * (int64_t) g6_19;
504 int64_t f9g7_38 = f9_2 * (int64_t) g7_19;
505 int64_t f9g8_19 = f9 * (int64_t) g8_19;
506 int64_t f9g9_38 = f9_2 * (int64_t) g9_19;
507
508 int64_t h0 = f0g0 + f1g9_38 + f2g8_19 + f3g7_38 + f4g6_19 + f5g5_38 +
509 f6g4_19 + f7g3_38 + f8g2_19 + f9g1_38;
510 int64_t h1 = f0g1 + f1g0 + f2g9_19 + f3g8_19 + f4g7_19 + f5g6_19 + f6g5_19 +
511 f7g4_19 + f8g3_19 + f9g2_19;
512 int64_t h2 = f0g2 + f1g1_2 + f2g0 + f3g9_38 + f4g8_19 + f5g7_38 + f6g6_19 +
513 f7g5_38 + f8g4_19 + f9g3_38;
514 int64_t h3 = f0g3 + f1g2 + f2g1 + f3g0 + f4g9_19 + f5g8_19 + f6g7_19 +
515 f7g6_19 + f8g5_19 + f9g4_19;
516 int64_t h4 = f0g4 + f1g3_2 + f2g2 + f3g1_2 + f4g0 + f5g9_38 + f6g8_19 +
517 f7g7_38 + f8g6_19 + f9g5_38;
518 int64_t h5 = f0g5 + f1g4 + f2g3 + f3g2 + f4g1 + f5g0 + f6g9_19 + f7g8_19 +
519 f8g7_19 + f9g6_19;
520 int64_t h6 = f0g6 + f1g5_2 + f2g4 + f3g3_2 + f4g2 + f5g1_2 + f6g0 +
521 f7g9_38 + f8g8_19 + f9g7_38;
522 int64_t h7 = f0g7 + f1g6 + f2g5 + f3g4 + f4g3 + f5g2 + f6g1 + f7g0 +
523 f8g9_19 + f9g8_19;
524 int64_t h8 = f0g8 + f1g7_2 + f2g6 + f3g5_2 + f4g4 + f5g3_2 + f6g2 + f7g1_2 +
525 f8g0 + f9g9_38;
526 int64_t h9 =
527 f0g9 + f1g8 + f2g7 + f3g6 + f4g5 + f5g4 + f6g3 + f7g2 + f8g1 + f9g0;
528
529 int64_t carry0;
530 int64_t carry1;
531 int64_t carry2;
532 int64_t carry3;
533 int64_t carry4;
534 int64_t carry5;
535 int64_t carry6;
536 int64_t carry7;
537 int64_t carry8;
538 int64_t carry9;
539
540 /*
541 |h0| <= (1.65*1.65*2^52*(1+19+19+19+19)+1.65*1.65*2^50*(38+38+38+38+38))
542 i.e. |h0| <= 1.4*2^60; narrower ranges for h2, h4, h6, h8
543 |h1| <= (1.65*1.65*2^51*(1+1+19+19+19+19+19+19+19+19))
544 i.e. |h1| <= 1.7*2^59; narrower ranges for h3, h5, h7, h9
545 */
546
547 carry0 = (h0 + (int64_t)(1L << 25)) >> 26;
548 h1 += carry0;
549 h0 -= carry0 * ((uint64_t) 1L << 26);
550 carry4 = (h4 + (int64_t)(1L << 25)) >> 26;
551 h5 += carry4;
552 h4 -= carry4 * ((uint64_t) 1L << 26);
553 /* |h0| <= 2^25 */
554 /* |h4| <= 2^25 */
555 /* |h1| <= 1.71*2^59 */
556 /* |h5| <= 1.71*2^59 */
557
558 carry1 = (h1 + (int64_t)(1L << 24)) >> 25;
559 h2 += carry1;
560 h1 -= carry1 * ((uint64_t) 1L << 25);
561 carry5 = (h5 + (int64_t)(1L << 24)) >> 25;
562 h6 += carry5;
563 h5 -= carry5 * ((uint64_t) 1L << 25);
564 /* |h1| <= 2^24; from now on fits into int32 */
565 /* |h5| <= 2^24; from now on fits into int32 */
566 /* |h2| <= 1.41*2^60 */
567 /* |h6| <= 1.41*2^60 */
568
569 carry2 = (h2 + (int64_t)(1L << 25)) >> 26;
570 h3 += carry2;
571 h2 -= carry2 * ((uint64_t) 1L << 26);
572 carry6 = (h6 + (int64_t)(1L << 25)) >> 26;
573 h7 += carry6;
574 h6 -= carry6 * ((uint64_t) 1L << 26);
575 /* |h2| <= 2^25; from now on fits into int32 unchanged */
576 /* |h6| <= 2^25; from now on fits into int32 unchanged */
577 /* |h3| <= 1.71*2^59 */
578 /* |h7| <= 1.71*2^59 */
579
580 carry3 = (h3 + (int64_t)(1L << 24)) >> 25;
581 h4 += carry3;
582 h3 -= carry3 * ((uint64_t) 1L << 25);
583 carry7 = (h7 + (int64_t)(1L << 24)) >> 25;
584 h8 += carry7;
585 h7 -= carry7 * ((uint64_t) 1L << 25);
586 /* |h3| <= 2^24; from now on fits into int32 unchanged */
587 /* |h7| <= 2^24; from now on fits into int32 unchanged */
588 /* |h4| <= 1.72*2^34 */
589 /* |h8| <= 1.41*2^60 */
590
591 carry4 = (h4 + (int64_t)(1L << 25)) >> 26;
592 h5 += carry4;
593 h4 -= carry4 * ((uint64_t) 1L << 26);
594 carry8 = (h8 + (int64_t)(1L << 25)) >> 26;
595 h9 += carry8;
596 h8 -= carry8 * ((uint64_t) 1L << 26);
597 /* |h4| <= 2^25; from now on fits into int32 unchanged */
598 /* |h8| <= 2^25; from now on fits into int32 unchanged */
599 /* |h5| <= 1.01*2^24 */
600 /* |h9| <= 1.71*2^59 */
601
602 carry9 = (h9 + (int64_t)(1L << 24)) >> 25;
603 h0 += carry9 * 19;
604 h9 -= carry9 * ((uint64_t) 1L << 25);
605 /* |h9| <= 2^24; from now on fits into int32 unchanged */
606 /* |h0| <= 1.1*2^39 */
607
608 carry0 = (h0 + (int64_t)(1L << 25)) >> 26;
609 h1 += carry0;
610 h0 -= carry0 * ((uint64_t) 1L << 26);
611 /* |h0| <= 2^25; from now on fits into int32 unchanged */
612 /* |h1| <= 1.01*2^24 */
613
614 h[0] = (int32_t) h0;
615 h[1] = (int32_t) h1;
616 h[2] = (int32_t) h2;
617 h[3] = (int32_t) h3;
618 h[4] = (int32_t) h4;
619 h[5] = (int32_t) h5;
620 h[6] = (int32_t) h6;
621 h[7] = (int32_t) h7;
622 h[8] = (int32_t) h8;
623 h[9] = (int32_t) h9;
624 }
625
626 /*
627 h = f * f
628 Can overlap h with f.
629 *
630 Preconditions:
631 |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
632 *
633 Postconditions:
634 |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
635 */
636
637 static void
fe25519_sq(fe25519 h,const fe25519 f)638 fe25519_sq(fe25519 h, const fe25519 f)
639 {
640 int32_t f0 = f[0];
641 int32_t f1 = f[1];
642 int32_t f2 = f[2];
643 int32_t f3 = f[3];
644 int32_t f4 = f[4];
645 int32_t f5 = f[5];
646 int32_t f6 = f[6];
647 int32_t f7 = f[7];
648 int32_t f8 = f[8];
649 int32_t f9 = f[9];
650
651 int32_t f0_2 = 2 * f0;
652 int32_t f1_2 = 2 * f1;
653 int32_t f2_2 = 2 * f2;
654 int32_t f3_2 = 2 * f3;
655 int32_t f4_2 = 2 * f4;
656 int32_t f5_2 = 2 * f5;
657 int32_t f6_2 = 2 * f6;
658 int32_t f7_2 = 2 * f7;
659 int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */
660 int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */
661 int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */
662 int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */
663 int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */
664
665 int64_t f0f0 = f0 * (int64_t) f0;
666 int64_t f0f1_2 = f0_2 * (int64_t) f1;
667 int64_t f0f2_2 = f0_2 * (int64_t) f2;
668 int64_t f0f3_2 = f0_2 * (int64_t) f3;
669 int64_t f0f4_2 = f0_2 * (int64_t) f4;
670 int64_t f0f5_2 = f0_2 * (int64_t) f5;
671 int64_t f0f6_2 = f0_2 * (int64_t) f6;
672 int64_t f0f7_2 = f0_2 * (int64_t) f7;
673 int64_t f0f8_2 = f0_2 * (int64_t) f8;
674 int64_t f0f9_2 = f0_2 * (int64_t) f9;
675 int64_t f1f1_2 = f1_2 * (int64_t) f1;
676 int64_t f1f2_2 = f1_2 * (int64_t) f2;
677 int64_t f1f3_4 = f1_2 * (int64_t) f3_2;
678 int64_t f1f4_2 = f1_2 * (int64_t) f4;
679 int64_t f1f5_4 = f1_2 * (int64_t) f5_2;
680 int64_t f1f6_2 = f1_2 * (int64_t) f6;
681 int64_t f1f7_4 = f1_2 * (int64_t) f7_2;
682 int64_t f1f8_2 = f1_2 * (int64_t) f8;
683 int64_t f1f9_76 = f1_2 * (int64_t) f9_38;
684 int64_t f2f2 = f2 * (int64_t) f2;
685 int64_t f2f3_2 = f2_2 * (int64_t) f3;
686 int64_t f2f4_2 = f2_2 * (int64_t) f4;
687 int64_t f2f5_2 = f2_2 * (int64_t) f5;
688 int64_t f2f6_2 = f2_2 * (int64_t) f6;
689 int64_t f2f7_2 = f2_2 * (int64_t) f7;
690 int64_t f2f8_38 = f2_2 * (int64_t) f8_19;
691 int64_t f2f9_38 = f2 * (int64_t) f9_38;
692 int64_t f3f3_2 = f3_2 * (int64_t) f3;
693 int64_t f3f4_2 = f3_2 * (int64_t) f4;
694 int64_t f3f5_4 = f3_2 * (int64_t) f5_2;
695 int64_t f3f6_2 = f3_2 * (int64_t) f6;
696 int64_t f3f7_76 = f3_2 * (int64_t) f7_38;
697 int64_t f3f8_38 = f3_2 * (int64_t) f8_19;
698 int64_t f3f9_76 = f3_2 * (int64_t) f9_38;
699 int64_t f4f4 = f4 * (int64_t) f4;
700 int64_t f4f5_2 = f4_2 * (int64_t) f5;
701 int64_t f4f6_38 = f4_2 * (int64_t) f6_19;
702 int64_t f4f7_38 = f4 * (int64_t) f7_38;
703 int64_t f4f8_38 = f4_2 * (int64_t) f8_19;
704 int64_t f4f9_38 = f4 * (int64_t) f9_38;
705 int64_t f5f5_38 = f5 * (int64_t) f5_38;
706 int64_t f5f6_38 = f5_2 * (int64_t) f6_19;
707 int64_t f5f7_76 = f5_2 * (int64_t) f7_38;
708 int64_t f5f8_38 = f5_2 * (int64_t) f8_19;
709 int64_t f5f9_76 = f5_2 * (int64_t) f9_38;
710 int64_t f6f6_19 = f6 * (int64_t) f6_19;
711 int64_t f6f7_38 = f6 * (int64_t) f7_38;
712 int64_t f6f8_38 = f6_2 * (int64_t) f8_19;
713 int64_t f6f9_38 = f6 * (int64_t) f9_38;
714 int64_t f7f7_38 = f7 * (int64_t) f7_38;
715 int64_t f7f8_38 = f7_2 * (int64_t) f8_19;
716 int64_t f7f9_76 = f7_2 * (int64_t) f9_38;
717 int64_t f8f8_19 = f8 * (int64_t) f8_19;
718 int64_t f8f9_38 = f8 * (int64_t) f9_38;
719 int64_t f9f9_38 = f9 * (int64_t) f9_38;
720
721 int64_t h0 = f0f0 + f1f9_76 + f2f8_38 + f3f7_76 + f4f6_38 + f5f5_38;
722 int64_t h1 = f0f1_2 + f2f9_38 + f3f8_38 + f4f7_38 + f5f6_38;
723 int64_t h2 = f0f2_2 + f1f1_2 + f3f9_76 + f4f8_38 + f5f7_76 + f6f6_19;
724 int64_t h3 = f0f3_2 + f1f2_2 + f4f9_38 + f5f8_38 + f6f7_38;
725 int64_t h4 = f0f4_2 + f1f3_4 + f2f2 + f5f9_76 + f6f8_38 + f7f7_38;
726 int64_t h5 = f0f5_2 + f1f4_2 + f2f3_2 + f6f9_38 + f7f8_38;
727 int64_t h6 = f0f6_2 + f1f5_4 + f2f4_2 + f3f3_2 + f7f9_76 + f8f8_19;
728 int64_t h7 = f0f7_2 + f1f6_2 + f2f5_2 + f3f4_2 + f8f9_38;
729 int64_t h8 = f0f8_2 + f1f7_4 + f2f6_2 + f3f5_4 + f4f4 + f9f9_38;
730 int64_t h9 = f0f9_2 + f1f8_2 + f2f7_2 + f3f6_2 + f4f5_2;
731
732 int64_t carry0;
733 int64_t carry1;
734 int64_t carry2;
735 int64_t carry3;
736 int64_t carry4;
737 int64_t carry5;
738 int64_t carry6;
739 int64_t carry7;
740 int64_t carry8;
741 int64_t carry9;
742
743 carry0 = (h0 + (int64_t)(1L << 25)) >> 26;
744 h1 += carry0;
745 h0 -= carry0 * ((uint64_t) 1L << 26);
746 carry4 = (h4 + (int64_t)(1L << 25)) >> 26;
747 h5 += carry4;
748 h4 -= carry4 * ((uint64_t) 1L << 26);
749
750 carry1 = (h1 + (int64_t)(1L << 24)) >> 25;
751 h2 += carry1;
752 h1 -= carry1 * ((uint64_t) 1L << 25);
753 carry5 = (h5 + (int64_t)(1L << 24)) >> 25;
754 h6 += carry5;
755 h5 -= carry5 * ((uint64_t) 1L << 25);
756
757 carry2 = (h2 + (int64_t)(1L << 25)) >> 26;
758 h3 += carry2;
759 h2 -= carry2 * ((uint64_t) 1L << 26);
760 carry6 = (h6 + (int64_t)(1L << 25)) >> 26;
761 h7 += carry6;
762 h6 -= carry6 * ((uint64_t) 1L << 26);
763
764 carry3 = (h3 + (int64_t)(1L << 24)) >> 25;
765 h4 += carry3;
766 h3 -= carry3 * ((uint64_t) 1L << 25);
767 carry7 = (h7 + (int64_t)(1L << 24)) >> 25;
768 h8 += carry7;
769 h7 -= carry7 * ((uint64_t) 1L << 25);
770
771 carry4 = (h4 + (int64_t)(1L << 25)) >> 26;
772 h5 += carry4;
773 h4 -= carry4 * ((uint64_t) 1L << 26);
774 carry8 = (h8 + (int64_t)(1L << 25)) >> 26;
775 h9 += carry8;
776 h8 -= carry8 * ((uint64_t) 1L << 26);
777
778 carry9 = (h9 + (int64_t)(1L << 24)) >> 25;
779 h0 += carry9 * 19;
780 h9 -= carry9 * ((uint64_t) 1L << 25);
781
782 carry0 = (h0 + (int64_t)(1L << 25)) >> 26;
783 h1 += carry0;
784 h0 -= carry0 * ((uint64_t) 1L << 26);
785
786 h[0] = (int32_t) h0;
787 h[1] = (int32_t) h1;
788 h[2] = (int32_t) h2;
789 h[3] = (int32_t) h3;
790 h[4] = (int32_t) h4;
791 h[5] = (int32_t) h5;
792 h[6] = (int32_t) h6;
793 h[7] = (int32_t) h7;
794 h[8] = (int32_t) h8;
795 h[9] = (int32_t) h9;
796 }
797
798 /*
799 h = 2 * f * f
800 Can overlap h with f.
801 *
802 Preconditions:
803 |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
804 *
805 Postconditions:
806 |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
807 */
808
809 static void
fe25519_sq2(fe25519 h,const fe25519 f)810 fe25519_sq2(fe25519 h, const fe25519 f)
811 {
812 int32_t f0 = f[0];
813 int32_t f1 = f[1];
814 int32_t f2 = f[2];
815 int32_t f3 = f[3];
816 int32_t f4 = f[4];
817 int32_t f5 = f[5];
818 int32_t f6 = f[6];
819 int32_t f7 = f[7];
820 int32_t f8 = f[8];
821 int32_t f9 = f[9];
822
823 int32_t f0_2 = 2 * f0;
824 int32_t f1_2 = 2 * f1;
825 int32_t f2_2 = 2 * f2;
826 int32_t f3_2 = 2 * f3;
827 int32_t f4_2 = 2 * f4;
828 int32_t f5_2 = 2 * f5;
829 int32_t f6_2 = 2 * f6;
830 int32_t f7_2 = 2 * f7;
831 int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */
832 int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */
833 int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */
834 int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */
835 int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */
836
837 int64_t f0f0 = f0 * (int64_t) f0;
838 int64_t f0f1_2 = f0_2 * (int64_t) f1;
839 int64_t f0f2_2 = f0_2 * (int64_t) f2;
840 int64_t f0f3_2 = f0_2 * (int64_t) f3;
841 int64_t f0f4_2 = f0_2 * (int64_t) f4;
842 int64_t f0f5_2 = f0_2 * (int64_t) f5;
843 int64_t f0f6_2 = f0_2 * (int64_t) f6;
844 int64_t f0f7_2 = f0_2 * (int64_t) f7;
845 int64_t f0f8_2 = f0_2 * (int64_t) f8;
846 int64_t f0f9_2 = f0_2 * (int64_t) f9;
847 int64_t f1f1_2 = f1_2 * (int64_t) f1;
848 int64_t f1f2_2 = f1_2 * (int64_t) f2;
849 int64_t f1f3_4 = f1_2 * (int64_t) f3_2;
850 int64_t f1f4_2 = f1_2 * (int64_t) f4;
851 int64_t f1f5_4 = f1_2 * (int64_t) f5_2;
852 int64_t f1f6_2 = f1_2 * (int64_t) f6;
853 int64_t f1f7_4 = f1_2 * (int64_t) f7_2;
854 int64_t f1f8_2 = f1_2 * (int64_t) f8;
855 int64_t f1f9_76 = f1_2 * (int64_t) f9_38;
856 int64_t f2f2 = f2 * (int64_t) f2;
857 int64_t f2f3_2 = f2_2 * (int64_t) f3;
858 int64_t f2f4_2 = f2_2 * (int64_t) f4;
859 int64_t f2f5_2 = f2_2 * (int64_t) f5;
860 int64_t f2f6_2 = f2_2 * (int64_t) f6;
861 int64_t f2f7_2 = f2_2 * (int64_t) f7;
862 int64_t f2f8_38 = f2_2 * (int64_t) f8_19;
863 int64_t f2f9_38 = f2 * (int64_t) f9_38;
864 int64_t f3f3_2 = f3_2 * (int64_t) f3;
865 int64_t f3f4_2 = f3_2 * (int64_t) f4;
866 int64_t f3f5_4 = f3_2 * (int64_t) f5_2;
867 int64_t f3f6_2 = f3_2 * (int64_t) f6;
868 int64_t f3f7_76 = f3_2 * (int64_t) f7_38;
869 int64_t f3f8_38 = f3_2 * (int64_t) f8_19;
870 int64_t f3f9_76 = f3_2 * (int64_t) f9_38;
871 int64_t f4f4 = f4 * (int64_t) f4;
872 int64_t f4f5_2 = f4_2 * (int64_t) f5;
873 int64_t f4f6_38 = f4_2 * (int64_t) f6_19;
874 int64_t f4f7_38 = f4 * (int64_t) f7_38;
875 int64_t f4f8_38 = f4_2 * (int64_t) f8_19;
876 int64_t f4f9_38 = f4 * (int64_t) f9_38;
877 int64_t f5f5_38 = f5 * (int64_t) f5_38;
878 int64_t f5f6_38 = f5_2 * (int64_t) f6_19;
879 int64_t f5f7_76 = f5_2 * (int64_t) f7_38;
880 int64_t f5f8_38 = f5_2 * (int64_t) f8_19;
881 int64_t f5f9_76 = f5_2 * (int64_t) f9_38;
882 int64_t f6f6_19 = f6 * (int64_t) f6_19;
883 int64_t f6f7_38 = f6 * (int64_t) f7_38;
884 int64_t f6f8_38 = f6_2 * (int64_t) f8_19;
885 int64_t f6f9_38 = f6 * (int64_t) f9_38;
886 int64_t f7f7_38 = f7 * (int64_t) f7_38;
887 int64_t f7f8_38 = f7_2 * (int64_t) f8_19;
888 int64_t f7f9_76 = f7_2 * (int64_t) f9_38;
889 int64_t f8f8_19 = f8 * (int64_t) f8_19;
890 int64_t f8f9_38 = f8 * (int64_t) f9_38;
891 int64_t f9f9_38 = f9 * (int64_t) f9_38;
892
893 int64_t h0 = f0f0 + f1f9_76 + f2f8_38 + f3f7_76 + f4f6_38 + f5f5_38;
894 int64_t h1 = f0f1_2 + f2f9_38 + f3f8_38 + f4f7_38 + f5f6_38;
895 int64_t h2 = f0f2_2 + f1f1_2 + f3f9_76 + f4f8_38 + f5f7_76 + f6f6_19;
896 int64_t h3 = f0f3_2 + f1f2_2 + f4f9_38 + f5f8_38 + f6f7_38;
897 int64_t h4 = f0f4_2 + f1f3_4 + f2f2 + f5f9_76 + f6f8_38 + f7f7_38;
898 int64_t h5 = f0f5_2 + f1f4_2 + f2f3_2 + f6f9_38 + f7f8_38;
899 int64_t h6 = f0f6_2 + f1f5_4 + f2f4_2 + f3f3_2 + f7f9_76 + f8f8_19;
900 int64_t h7 = f0f7_2 + f1f6_2 + f2f5_2 + f3f4_2 + f8f9_38;
901 int64_t h8 = f0f8_2 + f1f7_4 + f2f6_2 + f3f5_4 + f4f4 + f9f9_38;
902 int64_t h9 = f0f9_2 + f1f8_2 + f2f7_2 + f3f6_2 + f4f5_2;
903
904 int64_t carry0;
905 int64_t carry1;
906 int64_t carry2;
907 int64_t carry3;
908 int64_t carry4;
909 int64_t carry5;
910 int64_t carry6;
911 int64_t carry7;
912 int64_t carry8;
913 int64_t carry9;
914
915 h0 += h0;
916 h1 += h1;
917 h2 += h2;
918 h3 += h3;
919 h4 += h4;
920 h5 += h5;
921 h6 += h6;
922 h7 += h7;
923 h8 += h8;
924 h9 += h9;
925
926 carry0 = (h0 + (int64_t)(1L << 25)) >> 26;
927 h1 += carry0;
928 h0 -= carry0 * ((uint64_t) 1L << 26);
929 carry4 = (h4 + (int64_t)(1L << 25)) >> 26;
930 h5 += carry4;
931 h4 -= carry4 * ((uint64_t) 1L << 26);
932
933 carry1 = (h1 + (int64_t)(1L << 24)) >> 25;
934 h2 += carry1;
935 h1 -= carry1 * ((uint64_t) 1L << 25);
936 carry5 = (h5 + (int64_t)(1L << 24)) >> 25;
937 h6 += carry5;
938 h5 -= carry5 * ((uint64_t) 1L << 25);
939
940 carry2 = (h2 + (int64_t)(1L << 25)) >> 26;
941 h3 += carry2;
942 h2 -= carry2 * ((uint64_t) 1L << 26);
943 carry6 = (h6 + (int64_t)(1L << 25)) >> 26;
944 h7 += carry6;
945 h6 -= carry6 * ((uint64_t) 1L << 26);
946
947 carry3 = (h3 + (int64_t)(1L << 24)) >> 25;
948 h4 += carry3;
949 h3 -= carry3 * ((uint64_t) 1L << 25);
950 carry7 = (h7 + (int64_t)(1L << 24)) >> 25;
951 h8 += carry7;
952 h7 -= carry7 * ((uint64_t) 1L << 25);
953
954 carry4 = (h4 + (int64_t)(1L << 25)) >> 26;
955 h5 += carry4;
956 h4 -= carry4 * ((uint64_t) 1L << 26);
957 carry8 = (h8 + (int64_t)(1L << 25)) >> 26;
958 h9 += carry8;
959 h8 -= carry8 * ((uint64_t) 1L << 26);
960
961 carry9 = (h9 + (int64_t)(1L << 24)) >> 25;
962 h0 += carry9 * 19;
963 h9 -= carry9 * ((uint64_t) 1L << 25);
964
965 carry0 = (h0 + (int64_t)(1L << 25)) >> 26;
966 h1 += carry0;
967 h0 -= carry0 * ((uint64_t) 1L << 26);
968
969 h[0] = (int32_t) h0;
970 h[1] = (int32_t) h1;
971 h[2] = (int32_t) h2;
972 h[3] = (int32_t) h3;
973 h[4] = (int32_t) h4;
974 h[5] = (int32_t) h5;
975 h[6] = (int32_t) h6;
976 h[7] = (int32_t) h7;
977 h[8] = (int32_t) h8;
978 h[9] = (int32_t) h9;
979 }
980
981 static void
fe25519_scalar_product(fe25519 h,const fe25519 f,uint32_t n)982 fe25519_scalar_product(fe25519 h, const fe25519 f, uint32_t n)
983 {
984 int64_t sn = (int64_t) n;
985 int32_t f0 = f[0];
986 int32_t f1 = f[1];
987 int32_t f2 = f[2];
988 int32_t f3 = f[3];
989 int32_t f4 = f[4];
990 int32_t f5 = f[5];
991 int32_t f6 = f[6];
992 int32_t f7 = f[7];
993 int32_t f8 = f[8];
994 int32_t f9 = f[9];
995 int64_t h0 = f0 * sn;
996 int64_t h1 = f1 * sn;
997 int64_t h2 = f2 * sn;
998 int64_t h3 = f3 * sn;
999 int64_t h4 = f4 * sn;
1000 int64_t h5 = f5 * sn;
1001 int64_t h6 = f6 * sn;
1002 int64_t h7 = f7 * sn;
1003 int64_t h8 = f8 * sn;
1004 int64_t h9 = f9 * sn;
1005 int64_t carry0, carry1, carry2, carry3, carry4, carry5, carry6, carry7,
1006 carry8, carry9;
1007
1008 carry9 = (h9 + ((int64_t) 1 << 24)) >> 25;
1009 h0 += carry9 * 19;
1010 h9 -= carry9 * ((int64_t) 1 << 25);
1011 carry1 = (h1 + ((int64_t) 1 << 24)) >> 25;
1012 h2 += carry1;
1013 h1 -= carry1 * ((int64_t) 1 << 25);
1014 carry3 = (h3 + ((int64_t) 1 << 24)) >> 25;
1015 h4 += carry3;
1016 h3 -= carry3 * ((int64_t) 1 << 25);
1017 carry5 = (h5 + ((int64_t) 1 << 24)) >> 25;
1018 h6 += carry5;
1019 h5 -= carry5 * ((int64_t) 1 << 25);
1020 carry7 = (h7 + ((int64_t) 1 << 24)) >> 25;
1021 h8 += carry7;
1022 h7 -= carry7 * ((int64_t) 1 << 25);
1023
1024 carry0 = (h0 + ((int64_t) 1 << 25)) >> 26;
1025 h1 += carry0;
1026 h0 -= carry0 * ((int64_t) 1 << 26);
1027 carry2 = (h2 + ((int64_t) 1 << 25)) >> 26;
1028 h3 += carry2;
1029 h2 -= carry2 * ((int64_t) 1 << 26);
1030 carry4 = (h4 + ((int64_t) 1 << 25)) >> 26;
1031 h5 += carry4;
1032 h4 -= carry4 * ((int64_t) 1 << 26);
1033 carry6 = (h6 + ((int64_t) 1 << 25)) >> 26;
1034 h7 += carry6;
1035 h6 -= carry6 * ((int64_t) 1 << 26);
1036 carry8 = (h8 + ((int64_t) 1 << 25)) >> 26;
1037 h9 += carry8;
1038 h8 -= carry8 * ((int64_t) 1 << 26);
1039
1040 h[0] = (int32_t) h0;
1041 h[1] = (int32_t) h1;
1042 h[2] = (int32_t) h2;
1043 h[3] = (int32_t) h3;
1044 h[4] = (int32_t) h4;
1045 h[5] = (int32_t) h5;
1046 h[6] = (int32_t) h6;
1047 h[7] = (int32_t) h7;
1048 h[8] = (int32_t) h8;
1049 h[9] = (int32_t) h9;
1050 }
1051