Lines Matching +full:a +full:- +full:z

5  * a copy of this software and associated documentation files (the
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
72 * A field element is encoded as four 64-bit integers, in basis 2^63.
77 #define MASK63 (((uint64_t)1 << 63) - (uint64_t)1)
80 * Swap two field elements, conditionally on a flag.
83 f255_cswap(uint64_t *a, uint64_t *b, uint32_t ctl) in f255_cswap() argument
87 m = -(uint64_t)ctl; in f255_cswap()
88 w = m & (a[0] ^ b[0]); a[0] ^= w; b[0] ^= w; in f255_cswap()
89 w = m & (a[1] ^ b[1]); a[1] ^= w; b[1] ^= w; in f255_cswap()
90 w = m & (a[2] ^ b[2]); a[2] ^= w; b[2] ^= w; in f255_cswap()
91 w = m & (a[3] ^ b[3]); a[3] ^= w; b[3] ^= w; in f255_cswap()
98 f255_add(uint64_t *d, const uint64_t *a, const uint64_t *b) in f255_add() argument
103 unsigned __int128 z; in f255_add() local
105 z = (unsigned __int128)a[0] + (unsigned __int128)b[0]; in f255_add()
106 t0 = (uint64_t)z; in f255_add()
107 z = (unsigned __int128)a[1] + (unsigned __int128)b[1] + (z >> 64); in f255_add()
108 t1 = (uint64_t)z; in f255_add()
109 z = (unsigned __int128)a[2] + (unsigned __int128)b[2] + (z >> 64); in f255_add()
110 t2 = (uint64_t)z; in f255_add()
111 z = (unsigned __int128)a[3] + (unsigned __int128)b[3] + (z >> 64); in f255_add()
112 t3 = (uint64_t)z & MASK63; in f255_add()
113 cc = (uint64_t)(z >> 63); in f255_add()
120 * Since we add 0, 19 or 38 to a value that fits on 255 bits, in f255_add()
123 z = (unsigned __int128)t0 + (unsigned __int128)(19 * cc); in f255_add()
124 d[0] = (uint64_t)z; in f255_add()
125 z = (unsigned __int128)t1 + (z >> 64); in f255_add()
126 d[1] = (uint64_t)z; in f255_add()
127 z = (unsigned __int128)t2 + (z >> 64); in f255_add()
128 d[2] = (uint64_t)z; in f255_add()
129 d[3] = t3 + (uint64_t)(z >> 64); in f255_add()
136 k = _addcarry_u64(0, a[0], b[0], &t0); in f255_add()
137 k = _addcarry_u64(k, a[1], b[1], &t1); in f255_add()
138 k = _addcarry_u64(k, a[2], b[2], &t2); in f255_add()
139 k = _addcarry_u64(k, a[3], b[3], &t3); in f255_add()
148 * Since we add 0, 19 or 38 to a value that fits on 255 bits, in f255_add()
163 f255_sub(uint64_t *d, const uint64_t *a, const uint64_t *b) in f255_sub() argument
168 * We compute t = 2^256 - 38 + a - b, which is necessarily in f255_sub()
169 * positive but lower than 2^256 + 2^255, since a <= 2^255 + 37 in f255_sub()
175 unsigned __int128 z; in f255_sub() local
177 z = (unsigned __int128)a[0] - (unsigned __int128)b[0] - 38; in f255_sub()
178 t0 = (uint64_t)z; in f255_sub()
179 cc = -(uint64_t)(z >> 64); in f255_sub()
180 z = (unsigned __int128)a[1] - (unsigned __int128)b[1] in f255_sub()
181 - (unsigned __int128)cc; in f255_sub()
182 t1 = (uint64_t)z; in f255_sub()
183 cc = -(uint64_t)(z >> 64); in f255_sub()
184 z = (unsigned __int128)a[2] - (unsigned __int128)b[2] in f255_sub()
185 - (unsigned __int128)cc; in f255_sub()
186 t2 = (uint64_t)z; in f255_sub()
187 cc = -(uint64_t)(z >> 64); in f255_sub()
188 z = (unsigned __int128)a[3] - (unsigned __int128)b[3] in f255_sub()
189 - (unsigned __int128)cc; in f255_sub()
190 t3 = (uint64_t)z; in f255_sub()
191 t4 = 1 + (uint64_t)(z >> 64); in f255_sub()
194 * We have a 257-bit result. The two top bits can be 00, 01 or 10, in f255_sub()
195 * but not 11 (value t <= 2^256 - 38 + 2^255 + 37 = 2^256 + 2^255 - 1). in f255_sub()
199 cc = (38 & -t4) + (19 & -(t3 >> 63)); in f255_sub()
201 z = (unsigned __int128)t0 + (unsigned __int128)cc; in f255_sub()
202 d[0] = (uint64_t)z; in f255_sub()
203 z = (unsigned __int128)t1 + (z >> 64); in f255_sub()
204 d[1] = (uint64_t)z; in f255_sub()
205 z = (unsigned __int128)t2 + (z >> 64); in f255_sub()
206 d[2] = (uint64_t)z; in f255_sub()
207 d[3] = t3 + (uint64_t)(z >> 64); in f255_sub()
212 * We compute t = 2^256 - 38 + a - b, which is necessarily in f255_sub()
213 * positive but lower than 2^256 + 2^255, since a <= 2^255 + 37 in f255_sub()
221 k = _subborrow_u64(0, a[0], b[0], &t0); in f255_sub()
222 k = _subborrow_u64(k, a[1], b[1], &t1); in f255_sub()
223 k = _subborrow_u64(k, a[2], b[2], &t2); in f255_sub()
224 k = _subborrow_u64(k, a[3], b[3], &t3); in f255_sub()
234 * We have a 257-bit result. The two top bits can be 00, 01 or 10, in f255_sub()
235 * but not 11 (value t <= 2^256 - 38 + 2^255 + 37 = 2^256 + 2^255 - 1). in f255_sub()
239 t4 = (38 & -t4) + (19 & -(t3 >> 63)); in f255_sub()
253 f255_mul(uint64_t *d, uint64_t *a, uint64_t *b) in f255_mul() argument
257 unsigned __int128 z; in f255_mul() local
261 * Compute the product a*b over plain integers. in f255_mul()
263 z = (unsigned __int128)a[0] * (unsigned __int128)b[0]; in f255_mul()
264 t0 = (uint64_t)z; in f255_mul()
265 z = (unsigned __int128)a[0] * (unsigned __int128)b[1] + (z >> 64); in f255_mul()
266 t1 = (uint64_t)z; in f255_mul()
267 z = (unsigned __int128)a[0] * (unsigned __int128)b[2] + (z >> 64); in f255_mul()
268 t2 = (uint64_t)z; in f255_mul()
269 z = (unsigned __int128)a[0] * (unsigned __int128)b[3] + (z >> 64); in f255_mul()
270 t3 = (uint64_t)z; in f255_mul()
271 t4 = (uint64_t)(z >> 64); in f255_mul()
273 z = (unsigned __int128)a[1] * (unsigned __int128)b[0] in f255_mul()
275 t1 = (uint64_t)z; in f255_mul()
276 z = (unsigned __int128)a[1] * (unsigned __int128)b[1] in f255_mul()
277 + (unsigned __int128)t2 + (z >> 64); in f255_mul()
278 t2 = (uint64_t)z; in f255_mul()
279 z = (unsigned __int128)a[1] * (unsigned __int128)b[2] in f255_mul()
280 + (unsigned __int128)t3 + (z >> 64); in f255_mul()
281 t3 = (uint64_t)z; in f255_mul()
282 z = (unsigned __int128)a[1] * (unsigned __int128)b[3] in f255_mul()
283 + (unsigned __int128)t4 + (z >> 64); in f255_mul()
284 t4 = (uint64_t)z; in f255_mul()
285 t5 = (uint64_t)(z >> 64); in f255_mul()
287 z = (unsigned __int128)a[2] * (unsigned __int128)b[0] in f255_mul()
289 t2 = (uint64_t)z; in f255_mul()
290 z = (unsigned __int128)a[2] * (unsigned __int128)b[1] in f255_mul()
291 + (unsigned __int128)t3 + (z >> 64); in f255_mul()
292 t3 = (uint64_t)z; in f255_mul()
293 z = (unsigned __int128)a[2] * (unsigned __int128)b[2] in f255_mul()
294 + (unsigned __int128)t4 + (z >> 64); in f255_mul()
295 t4 = (uint64_t)z; in f255_mul()
296 z = (unsigned __int128)a[2] * (unsigned __int128)b[3] in f255_mul()
297 + (unsigned __int128)t5 + (z >> 64); in f255_mul()
298 t5 = (uint64_t)z; in f255_mul()
299 t6 = (uint64_t)(z >> 64); in f255_mul()
301 z = (unsigned __int128)a[3] * (unsigned __int128)b[0] in f255_mul()
303 t3 = (uint64_t)z; in f255_mul()
304 z = (unsigned __int128)a[3] * (unsigned __int128)b[1] in f255_mul()
305 + (unsigned __int128)t4 + (z >> 64); in f255_mul()
306 t4 = (uint64_t)z; in f255_mul()
307 z = (unsigned __int128)a[3] * (unsigned __int128)b[2] in f255_mul()
308 + (unsigned __int128)t5 + (z >> 64); in f255_mul()
309 t5 = (uint64_t)z; in f255_mul()
310 z = (unsigned __int128)a[3] * (unsigned __int128)b[3] in f255_mul()
311 + (unsigned __int128)t6 + (z >> 64); in f255_mul()
312 t6 = (uint64_t)z; in f255_mul()
313 t7 = (uint64_t)(z >> 64); in f255_mul()
323 * The upper one can only be a single bit (th), since the in f255_mul()
337 z = (unsigned __int128)t4 * 19; in f255_mul()
338 t4 = (uint64_t)z; in f255_mul()
339 z = (unsigned __int128)t5 * 19 + (z >> 64); in f255_mul()
340 t5 = (uint64_t)z; in f255_mul()
341 z = (unsigned __int128)t6 * 19 + (z >> 64); in f255_mul()
342 t6 = (uint64_t)z; in f255_mul()
343 z = (unsigned __int128)t7 * 19 + (z >> 64); in f255_mul()
344 t7 = (uint64_t)z & MASK63; in f255_mul()
346 th = (361 & -th) + (19 * (uint64_t)(z >> 63)); in f255_mul()
355 z = (unsigned __int128)t0 + (unsigned __int128)t4 in f255_mul()
357 t0 = (uint64_t)z; in f255_mul()
358 z = (unsigned __int128)t1 + (unsigned __int128)t5 + (z >> 64); in f255_mul()
359 t1 = (uint64_t)z; in f255_mul()
360 z = (unsigned __int128)t2 + (unsigned __int128)t6 + (z >> 64); in f255_mul()
361 t2 = (uint64_t)z; in f255_mul()
362 z = (unsigned __int128)t3 + (unsigned __int128)t7 + (z >> 64); in f255_mul()
363 t3 = (uint64_t)z & MASK63; in f255_mul()
364 th = (uint64_t)(z >> 63); in f255_mul()
369 * guarantees a result of at most 2^255+37. in f255_mul()
371 z = (unsigned __int128)t0 + (19 * th); in f255_mul()
372 d[0] = (uint64_t)z; in f255_mul()
373 z = (unsigned __int128)t1 + (z >> 64); in f255_mul()
374 d[1] = (uint64_t)z; in f255_mul()
375 z = (unsigned __int128)t2 + (z >> 64); in f255_mul()
376 d[2] = (uint64_t)z; in f255_mul()
377 d[3] = t3 + (uint64_t)(z >> 64); in f255_mul()
386 * Compute the product a*b over plain integers. in f255_mul()
388 t0 = _umul128(a[0], b[0], &h0); in f255_mul()
389 t1 = _umul128(a[0], b[1], &h1); in f255_mul()
391 t2 = _umul128(a[0], b[2], &h2); in f255_mul()
393 t3 = _umul128(a[0], b[3], &h3); in f255_mul()
397 k = _addcarry_u64(0, _umul128(a[1], b[0], &h0), t1, &t1); in f255_mul()
398 k = _addcarry_u64(k, _umul128(a[1], b[1], &h1), t2, &t2); in f255_mul()
399 k = _addcarry_u64(k, _umul128(a[1], b[2], &h2), t3, &t3); in f255_mul()
400 k = _addcarry_u64(k, _umul128(a[1], b[3], &h3), t4, &t4); in f255_mul()
407 k = _addcarry_u64(0, _umul128(a[2], b[0], &h0), t2, &t2); in f255_mul()
408 k = _addcarry_u64(k, _umul128(a[2], b[1], &h1), t3, &t3); in f255_mul()
409 k = _addcarry_u64(k, _umul128(a[2], b[2], &h2), t4, &t4); in f255_mul()
410 k = _addcarry_u64(k, _umul128(a[2], b[3], &h3), t5, &t5); in f255_mul()
417 k = _addcarry_u64(0, _umul128(a[3], b[0], &h0), t3, &t3); in f255_mul()
418 k = _addcarry_u64(k, _umul128(a[3], b[1], &h1), t4, &t4); in f255_mul()
419 k = _addcarry_u64(k, _umul128(a[3], b[2], &h2), t5, &t5); in f255_mul()
420 k = _addcarry_u64(k, _umul128(a[3], b[3], &h3), t6, &t6); in f255_mul()
435 * The upper one can only be a single bit (th), since the in f255_mul()
457 th = (361 & -th) + (19 * ((h3 << 1) + (t7 >> 63))); in f255_mul()
484 * guarantees a result of at most 2^255+37. in f255_mul()
498 f255_mul_a24(uint64_t *d, const uint64_t *a) in f255_mul_a24() argument
503 unsigned __int128 z; in f255_mul_a24() local
505 z = (unsigned __int128)a[0] * 121665; in f255_mul_a24()
506 t0 = (uint64_t)z; in f255_mul_a24()
507 z = (unsigned __int128)a[1] * 121665 + (z >> 64); in f255_mul_a24()
508 t1 = (uint64_t)z; in f255_mul_a24()
509 z = (unsigned __int128)a[2] * 121665 + (z >> 64); in f255_mul_a24()
510 t2 = (uint64_t)z; in f255_mul_a24()
511 z = (unsigned __int128)a[3] * 121665 + (z >> 64); in f255_mul_a24()
512 t3 = (uint64_t)z & MASK63; in f255_mul_a24()
514 z = (unsigned __int128)t0 + (19 * (uint64_t)(z >> 63)); in f255_mul_a24()
515 t0 = (uint64_t)z; in f255_mul_a24()
516 z = (unsigned __int128)t1 + (z >> 64); in f255_mul_a24()
517 t1 = (uint64_t)z; in f255_mul_a24()
518 z = (unsigned __int128)t2 + (z >> 64); in f255_mul_a24()
519 t2 = (uint64_t)z; in f255_mul_a24()
520 t3 = t3 + (uint64_t)(z >> 64); in f255_mul_a24()
522 z = (unsigned __int128)t0 + (19 & -(t3 >> 63)); in f255_mul_a24()
523 d[0] = (uint64_t)z; in f255_mul_a24()
524 z = (unsigned __int128)t1 + (z >> 64); in f255_mul_a24()
525 d[1] = (uint64_t)z; in f255_mul_a24()
526 z = (unsigned __int128)t2 + (z >> 64); in f255_mul_a24()
527 d[2] = (uint64_t)z; in f255_mul_a24()
528 d[3] = (t3 & MASK63) + (uint64_t)(z >> 64); in f255_mul_a24()
535 t0 = _umul128(a[0], 121665, &h0); in f255_mul_a24()
536 t1 = _umul128(a[1], 121665, &h1); in f255_mul_a24()
538 t2 = _umul128(a[2], 121665, &h2); in f255_mul_a24()
540 t3 = _umul128(a[3], 121665, &h3); in f255_mul_a24()
551 t4 = 19 & -(t3 >> 63); in f255_mul_a24()
565 f255_final_reduce(uint64_t *a) in f255_final_reduce() argument
570 unsigned __int128 z; in f255_final_reduce() local
573 * We add 19. If the result (in t) is below 2^255, then a[] in f255_final_reduce()
574 * is already less than 2^255-19, thus already reduced. in f255_final_reduce()
576 * have t = a - (2^255-19), and that's our result. in f255_final_reduce()
578 z = (unsigned __int128)a[0] + 19; in f255_final_reduce()
579 t0 = (uint64_t)z; in f255_final_reduce()
580 z = (unsigned __int128)a[1] + (z >> 64); in f255_final_reduce()
581 t1 = (uint64_t)z; in f255_final_reduce()
582 z = (unsigned __int128)a[2] + (z >> 64); in f255_final_reduce()
583 t2 = (uint64_t)z; in f255_final_reduce()
584 t3 = a[3] + (uint64_t)(z >> 64); in f255_final_reduce()
586 m = -(t3 >> 63); in f255_final_reduce()
588 a[0] ^= m & (a[0] ^ t0); in f255_final_reduce()
589 a[1] ^= m & (a[1] ^ t1); in f255_final_reduce()
590 a[2] ^= m & (a[2] ^ t2); in f255_final_reduce()
591 a[3] ^= m & (a[3] ^ t3); in f255_final_reduce()
599 * We add 19. If the result (in t) is below 2^255, then a[] in f255_final_reduce()
600 * is already less than 2^255-19, thus already reduced. in f255_final_reduce()
602 * have t = a - (2^255-19), and that's our result. in f255_final_reduce()
604 k = _addcarry_u64(0, a[0], 19, &t0); in f255_final_reduce()
605 k = _addcarry_u64(k, a[1], 0, &t1); in f255_final_reduce()
606 k = _addcarry_u64(k, a[2], 0, &t2); in f255_final_reduce()
607 (void)_addcarry_u64(k, a[3], 0, &t3); in f255_final_reduce()
609 m = -(t3 >> 63); in f255_final_reduce()
611 a[0] ^= m & (a[0] ^ t0); in f255_final_reduce()
612 a[1] ^= m & (a[1] ^ t1); in f255_final_reduce()
613 a[2] ^= m & (a[2] ^ t2); in f255_final_reduce()
614 a[3] ^= m & (a[3] ^ t3); in f255_final_reduce()
648 * We can use memset() to clear values, because exact-width types in api_mul()
659 * The multiplier is provided in big-endian notation, and in api_mul()
662 memset(k, 0, (sizeof k) - kblen); in api_mul()
663 memcpy(k + (sizeof k) - kblen, kb, kblen); in api_mul()
670 for (i = 254; i >= 0; i --) { in api_mul()
671 uint64_t a[4], aa[4], b[4], bb[4], e[4]; in api_mul() local
675 kt = (k[31 - (i >> 3)] >> (i & 7)) & 1; in api_mul()
681 /* A = x_2 + z_2 */ in api_mul()
682 f255_add(a, x2, z2); in api_mul()
684 /* AA = A^2 */ in api_mul()
685 f255_mul(aa, a, a); in api_mul()
687 /* B = x_2 - z_2 */ in api_mul()
693 /* E = AA - BB */ in api_mul()
699 /* D = x_3 - z_3 */ in api_mul()
702 /* DA = D * A */ in api_mul()
703 f255_mul(da, d, a); in api_mul()
712 /* z_3 = x_1 * (DA - CB)^2 */ in api_mul()
730 * Compute 1/z2 = z2^(p-2). Since p = 2^255-19, we can mutualize in api_mul()
731 * most non-squarings. We use x1 and x3, now useless, as temporaries. in api_mul()
747 for (i = 14; i >= 0; i --) { in api_mul()
761 * Encode the final x2 value in little-endian. in api_mul()
784 api_muladd(unsigned char *A, const unsigned char *B, size_t len, in api_muladd() argument
793 (void)A; in api_muladd()