security/nss/lib/freebl/ecl/ecl_gf.c@6474c204b198
security/nss/lib/freebl/ecl/ecl_gf.c
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 #include "mpi.h"
6 #include "mp_gf2m.h"
7 #include "ecl-priv.h"
8 #include "mpi-priv.h"
9 #include <stdlib.h>
11 /* Allocate memory for a new GFMethod object. */
12 GFMethod *
13 GFMethod_new()
14 {
15 mp_err res = MP_OKAY;
16 GFMethod *meth;
17 meth = (GFMethod *) malloc(sizeof(GFMethod));
18 if (meth == NULL)
19 return NULL;
20 meth->constructed = MP_YES;
21 MP_DIGITS(&meth->irr) = 0;
22 meth->extra_free = NULL;
23 MP_CHECKOK(mp_init(&meth->irr));
25 CLEANUP:
26 if (res != MP_OKAY) {
27 GFMethod_free(meth);
28 return NULL;
29 }
30 return meth;
31 }
33 /* Construct a generic GFMethod for arithmetic over prime fields with
34 * irreducible irr. */
35 GFMethod *
36 GFMethod_consGFp(const mp_int *irr)
37 {
38 mp_err res = MP_OKAY;
39 GFMethod *meth = NULL;
41 meth = GFMethod_new();
42 if (meth == NULL)
43 return NULL;
45 MP_CHECKOK(mp_copy(irr, &meth->irr));
46 meth->irr_arr[0] = mpl_significant_bits(irr);
47 meth->irr_arr[1] = meth->irr_arr[2] = meth->irr_arr[3] =
48 meth->irr_arr[4] = 0;
49 switch(MP_USED(&meth->irr)) {
50 /* maybe we need 1 and 2 words here as well?*/
51 case 3:
52 meth->field_add = &ec_GFp_add_3;
53 meth->field_sub = &ec_GFp_sub_3;
54 break;
55 case 4:
56 meth->field_add = &ec_GFp_add_4;
57 meth->field_sub = &ec_GFp_sub_4;
58 break;
59 case 5:
60 meth->field_add = &ec_GFp_add_5;
61 meth->field_sub = &ec_GFp_sub_5;
62 break;
63 case 6:
64 meth->field_add = &ec_GFp_add_6;
65 meth->field_sub = &ec_GFp_sub_6;
66 break;
67 default:
68 meth->field_add = &ec_GFp_add;
69 meth->field_sub = &ec_GFp_sub;
70 }
71 meth->field_neg = &ec_GFp_neg;
72 meth->field_mod = &ec_GFp_mod;
73 meth->field_mul = &ec_GFp_mul;
74 meth->field_sqr = &ec_GFp_sqr;
75 meth->field_div = &ec_GFp_div;
76 meth->field_enc = NULL;
77 meth->field_dec = NULL;
78 meth->extra1 = NULL;
79 meth->extra2 = NULL;
80 meth->extra_free = NULL;
82 CLEANUP:
83 if (res != MP_OKAY) {
84 GFMethod_free(meth);
85 return NULL;
86 }
87 return meth;
88 }
90 /* Construct a generic GFMethod for arithmetic over binary polynomial
91 * fields with irreducible irr that has array representation irr_arr (see
92 * ecl-priv.h for description of the representation). If irr_arr is NULL,
93 * then it is constructed from the bitstring representation. */
94 GFMethod *
95 GFMethod_consGF2m(const mp_int *irr, const unsigned int irr_arr[5])
96 {
97 mp_err res = MP_OKAY;
98 int ret;
99 GFMethod *meth = NULL;
101 meth = GFMethod_new();
102 if (meth == NULL)
103 return NULL;
105 MP_CHECKOK(mp_copy(irr, &meth->irr));
106 if (irr_arr != NULL) {
107 /* Irreducible polynomials are either trinomials or pentanomials. */
108 meth->irr_arr[0] = irr_arr[0];
109 meth->irr_arr[1] = irr_arr[1];
110 meth->irr_arr[2] = irr_arr[2];
111 if (irr_arr[2] > 0) {
112 meth->irr_arr[3] = irr_arr[3];
113 meth->irr_arr[4] = irr_arr[4];
114 } else {
115 meth->irr_arr[3] = meth->irr_arr[4] = 0;
116 }
117 } else {
118 ret = mp_bpoly2arr(irr, meth->irr_arr, 5);
119 /* Irreducible polynomials are either trinomials or pentanomials. */
120 if ((ret != 5) && (ret != 3)) {
121 res = MP_UNDEF;
122 goto CLEANUP;
123 }
124 }
125 meth->field_add = &ec_GF2m_add;
126 meth->field_neg = &ec_GF2m_neg;
127 meth->field_sub = &ec_GF2m_add;
128 meth->field_mod = &ec_GF2m_mod;
129 meth->field_mul = &ec_GF2m_mul;
130 meth->field_sqr = &ec_GF2m_sqr;
131 meth->field_div = &ec_GF2m_div;
132 meth->field_enc = NULL;
133 meth->field_dec = NULL;
134 meth->extra1 = NULL;
135 meth->extra2 = NULL;
136 meth->extra_free = NULL;
138 CLEANUP:
139 if (res != MP_OKAY) {
140 GFMethod_free(meth);
141 return NULL;
142 }
143 return meth;
144 }
146 /* Free the memory allocated (if any) to a GFMethod object. */
147 void
148 GFMethod_free(GFMethod *meth)
149 {
150 if (meth == NULL)
151 return;
152 if (meth->constructed == MP_NO)
153 return;
154 mp_clear(&meth->irr);
155 if (meth->extra_free != NULL)
156 meth->extra_free(meth);
157 free(meth);
158 }
160 /* Wrapper functions for generic prime field arithmetic. */
162 /* Add two field elements. Assumes that 0 <= a, b < meth->irr */
163 mp_err
164 ec_GFp_add(const mp_int *a, const mp_int *b, mp_int *r,
165 const GFMethod *meth)
166 {
167 /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a + b (mod p) */
168 mp_err res;
170 if ((res = mp_add(a, b, r)) != MP_OKAY) {
171 return res;
172 }
173 if (mp_cmp(r, &meth->irr) >= 0) {
174 return mp_sub(r, &meth->irr, r);
175 }
176 return res;
177 }
179 /* Negates a field element. Assumes that 0 <= a < meth->irr */
180 mp_err
181 ec_GFp_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
182 {
183 /* PRE: 0 <= a < p = meth->irr POST: 0 <= r < p, r = -a (mod p) */
185 if (mp_cmp_z(a) == 0) {
186 mp_zero(r);
187 return MP_OKAY;
188 }
189 return mp_sub(&meth->irr, a, r);
190 }
192 /* Subtracts two field elements. Assumes that 0 <= a, b < meth->irr */
193 mp_err
194 ec_GFp_sub(const mp_int *a, const mp_int *b, mp_int *r,
195 const GFMethod *meth)
196 {
197 mp_err res = MP_OKAY;
199 /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a - b (mod p) */
200 res = mp_sub(a, b, r);
201 if (res == MP_RANGE) {
202 MP_CHECKOK(mp_sub(b, a, r));
203 if (mp_cmp_z(r) < 0) {
204 MP_CHECKOK(mp_add(r, &meth->irr, r));
205 }
206 MP_CHECKOK(ec_GFp_neg(r, r, meth));
207 }
208 if (mp_cmp_z(r) < 0) {
209 MP_CHECKOK(mp_add(r, &meth->irr, r));
210 }
211 CLEANUP:
212 return res;
213 }
214 /*
215 * Inline adds for small curve lengths.
216 */
217 /* 3 words */
218 mp_err
219 ec_GFp_add_3(const mp_int *a, const mp_int *b, mp_int *r,
220 const GFMethod *meth)
221 {
222 mp_err res = MP_OKAY;
223 mp_digit a0 = 0, a1 = 0, a2 = 0;
224 mp_digit r0 = 0, r1 = 0, r2 = 0;
225 mp_digit carry;
227 switch(MP_USED(a)) {
228 case 3:
229 a2 = MP_DIGIT(a,2);
230 case 2:
231 a1 = MP_DIGIT(a,1);
232 case 1:
233 a0 = MP_DIGIT(a,0);
234 }
235 switch(MP_USED(b)) {
236 case 3:
237 r2 = MP_DIGIT(b,2);
238 case 2:
239 r1 = MP_DIGIT(b,1);
240 case 1:
241 r0 = MP_DIGIT(b,0);
242 }
244 #ifndef MPI_AMD64_ADD
245 MP_ADD_CARRY(a0, r0, r0, 0, carry);
246 MP_ADD_CARRY(a1, r1, r1, carry, carry);
247 MP_ADD_CARRY(a2, r2, r2, carry, carry);
248 #else
249 __asm__ (
250 "xorq %3,%3 \n\t"
251 "addq %4,%0 \n\t"
252 "adcq %5,%1 \n\t"
253 "adcq %6,%2 \n\t"
254 "adcq $0,%3 \n\t"
255 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry)
256 : "r" (a0), "r" (a1), "r" (a2),
257 "0" (r0), "1" (r1), "2" (r2)
258 : "%cc" );
259 #endif
261 MP_CHECKOK(s_mp_pad(r, 3));
262 MP_DIGIT(r, 2) = r2;
263 MP_DIGIT(r, 1) = r1;
264 MP_DIGIT(r, 0) = r0;
265 MP_SIGN(r) = MP_ZPOS;
266 MP_USED(r) = 3;
268 /* Do quick 'subract' if we've gone over
269 * (add the 2's complement of the curve field) */
270 a2 = MP_DIGIT(&meth->irr,2);
271 if (carry || r2 > a2 ||
272 ((r2 == a2) && mp_cmp(r,&meth->irr) != MP_LT)) {
273 a1 = MP_DIGIT(&meth->irr,1);
274 a0 = MP_DIGIT(&meth->irr,0);
275 #ifndef MPI_AMD64_ADD
276 MP_SUB_BORROW(r0, a0, r0, 0, carry);
277 MP_SUB_BORROW(r1, a1, r1, carry, carry);
278 MP_SUB_BORROW(r2, a2, r2, carry, carry);
279 #else
280 __asm__ (
281 "subq %3,%0 \n\t"
282 "sbbq %4,%1 \n\t"
283 "sbbq %5,%2 \n\t"
284 : "=r"(r0), "=r"(r1), "=r"(r2)
285 : "r" (a0), "r" (a1), "r" (a2),
286 "0" (r0), "1" (r1), "2" (r2)
287 : "%cc" );
288 #endif
289 MP_DIGIT(r, 2) = r2;
290 MP_DIGIT(r, 1) = r1;
291 MP_DIGIT(r, 0) = r0;
292 }
294 s_mp_clamp(r);
296 CLEANUP:
297 return res;
298 }
300 /* 4 words */
301 mp_err
302 ec_GFp_add_4(const mp_int *a, const mp_int *b, mp_int *r,
303 const GFMethod *meth)
304 {
305 mp_err res = MP_OKAY;
306 mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0;
307 mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
308 mp_digit carry;
310 switch(MP_USED(a)) {
311 case 4:
312 a3 = MP_DIGIT(a,3);
313 case 3:
314 a2 = MP_DIGIT(a,2);
315 case 2:
316 a1 = MP_DIGIT(a,1);
317 case 1:
318 a0 = MP_DIGIT(a,0);
319 }
320 switch(MP_USED(b)) {
321 case 4:
322 r3 = MP_DIGIT(b,3);
323 case 3:
324 r2 = MP_DIGIT(b,2);
325 case 2:
326 r1 = MP_DIGIT(b,1);
327 case 1:
328 r0 = MP_DIGIT(b,0);
329 }
331 #ifndef MPI_AMD64_ADD
332 MP_ADD_CARRY(a0, r0, r0, 0, carry);
333 MP_ADD_CARRY(a1, r1, r1, carry, carry);
334 MP_ADD_CARRY(a2, r2, r2, carry, carry);
335 MP_ADD_CARRY(a3, r3, r3, carry, carry);
336 #else
337 __asm__ (
338 "xorq %4,%4 \n\t"
339 "addq %5,%0 \n\t"
340 "adcq %6,%1 \n\t"
341 "adcq %7,%2 \n\t"
342 "adcq %8,%3 \n\t"
343 "adcq $0,%4 \n\t"
344 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(carry)
345 : "r" (a0), "r" (a1), "r" (a2), "r" (a3),
346 "0" (r0), "1" (r1), "2" (r2), "3" (r3)
347 : "%cc" );
348 #endif
350 MP_CHECKOK(s_mp_pad(r, 4));
351 MP_DIGIT(r, 3) = r3;
352 MP_DIGIT(r, 2) = r2;
353 MP_DIGIT(r, 1) = r1;
354 MP_DIGIT(r, 0) = r0;
355 MP_SIGN(r) = MP_ZPOS;
356 MP_USED(r) = 4;
358 /* Do quick 'subract' if we've gone over
359 * (add the 2's complement of the curve field) */
360 a3 = MP_DIGIT(&meth->irr,3);
361 if (carry || r3 > a3 ||
362 ((r3 == a3) && mp_cmp(r,&meth->irr) != MP_LT)) {
363 a2 = MP_DIGIT(&meth->irr,2);
364 a1 = MP_DIGIT(&meth->irr,1);
365 a0 = MP_DIGIT(&meth->irr,0);
366 #ifndef MPI_AMD64_ADD
367 MP_SUB_BORROW(r0, a0, r0, 0, carry);
368 MP_SUB_BORROW(r1, a1, r1, carry, carry);
369 MP_SUB_BORROW(r2, a2, r2, carry, carry);
370 MP_SUB_BORROW(r3, a3, r3, carry, carry);
371 #else
372 __asm__ (
373 "subq %4,%0 \n\t"
374 "sbbq %5,%1 \n\t"
375 "sbbq %6,%2 \n\t"
376 "sbbq %7,%3 \n\t"
377 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
378 : "r" (a0), "r" (a1), "r" (a2), "r" (a3),
379 "0" (r0), "1" (r1), "2" (r2), "3" (r3)
380 : "%cc" );
381 #endif
382 MP_DIGIT(r, 3) = r3;
383 MP_DIGIT(r, 2) = r2;
384 MP_DIGIT(r, 1) = r1;
385 MP_DIGIT(r, 0) = r0;
386 }
388 s_mp_clamp(r);
390 CLEANUP:
391 return res;
392 }
394 /* 5 words */
395 mp_err
396 ec_GFp_add_5(const mp_int *a, const mp_int *b, mp_int *r,
397 const GFMethod *meth)
398 {
399 mp_err res = MP_OKAY;
400 mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0;
401 mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
402 mp_digit carry;
404 switch(MP_USED(a)) {
405 case 5:
406 a4 = MP_DIGIT(a,4);
407 case 4:
408 a3 = MP_DIGIT(a,3);
409 case 3:
410 a2 = MP_DIGIT(a,2);
411 case 2:
412 a1 = MP_DIGIT(a,1);
413 case 1:
414 a0 = MP_DIGIT(a,0);
415 }
416 switch(MP_USED(b)) {
417 case 5:
418 r4 = MP_DIGIT(b,4);
419 case 4:
420 r3 = MP_DIGIT(b,3);
421 case 3:
422 r2 = MP_DIGIT(b,2);
423 case 2:
424 r1 = MP_DIGIT(b,1);
425 case 1:
426 r0 = MP_DIGIT(b,0);
427 }
429 MP_ADD_CARRY(a0, r0, r0, 0, carry);
430 MP_ADD_CARRY(a1, r1, r1, carry, carry);
431 MP_ADD_CARRY(a2, r2, r2, carry, carry);
432 MP_ADD_CARRY(a3, r3, r3, carry, carry);
433 MP_ADD_CARRY(a4, r4, r4, carry, carry);
435 MP_CHECKOK(s_mp_pad(r, 5));
436 MP_DIGIT(r, 4) = r4;
437 MP_DIGIT(r, 3) = r3;
438 MP_DIGIT(r, 2) = r2;
439 MP_DIGIT(r, 1) = r1;
440 MP_DIGIT(r, 0) = r0;
441 MP_SIGN(r) = MP_ZPOS;
442 MP_USED(r) = 5;
444 /* Do quick 'subract' if we've gone over
445 * (add the 2's complement of the curve field) */
446 a4 = MP_DIGIT(&meth->irr,4);
447 if (carry || r4 > a4 ||
448 ((r4 == a4) && mp_cmp(r,&meth->irr) != MP_LT)) {
449 a3 = MP_DIGIT(&meth->irr,3);
450 a2 = MP_DIGIT(&meth->irr,2);
451 a1 = MP_DIGIT(&meth->irr,1);
452 a0 = MP_DIGIT(&meth->irr,0);
453 MP_SUB_BORROW(r0, a0, r0, 0, carry);
454 MP_SUB_BORROW(r1, a1, r1, carry, carry);
455 MP_SUB_BORROW(r2, a2, r2, carry, carry);
456 MP_SUB_BORROW(r3, a3, r3, carry, carry);
457 MP_SUB_BORROW(r4, a4, r4, carry, carry);
458 MP_DIGIT(r, 4) = r4;
459 MP_DIGIT(r, 3) = r3;
460 MP_DIGIT(r, 2) = r2;
461 MP_DIGIT(r, 1) = r1;
462 MP_DIGIT(r, 0) = r0;
463 }
465 s_mp_clamp(r);
467 CLEANUP:
468 return res;
469 }
471 /* 6 words */
472 mp_err
473 ec_GFp_add_6(const mp_int *a, const mp_int *b, mp_int *r,
474 const GFMethod *meth)
475 {
476 mp_err res = MP_OKAY;
477 mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0, a5 = 0;
478 mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
479 mp_digit carry;
481 switch(MP_USED(a)) {
482 case 6:
483 a5 = MP_DIGIT(a,5);
484 case 5:
485 a4 = MP_DIGIT(a,4);
486 case 4:
487 a3 = MP_DIGIT(a,3);
488 case 3:
489 a2 = MP_DIGIT(a,2);
490 case 2:
491 a1 = MP_DIGIT(a,1);
492 case 1:
493 a0 = MP_DIGIT(a,0);
494 }
495 switch(MP_USED(b)) {
496 case 6:
497 r5 = MP_DIGIT(b,5);
498 case 5:
499 r4 = MP_DIGIT(b,4);
500 case 4:
501 r3 = MP_DIGIT(b,3);
502 case 3:
503 r2 = MP_DIGIT(b,2);
504 case 2:
505 r1 = MP_DIGIT(b,1);
506 case 1:
507 r0 = MP_DIGIT(b,0);
508 }
510 MP_ADD_CARRY(a0, r0, r0, 0, carry);
511 MP_ADD_CARRY(a1, r1, r1, carry, carry);
512 MP_ADD_CARRY(a2, r2, r2, carry, carry);
513 MP_ADD_CARRY(a3, r3, r3, carry, carry);
514 MP_ADD_CARRY(a4, r4, r4, carry, carry);
515 MP_ADD_CARRY(a5, r5, r5, carry, carry);
517 MP_CHECKOK(s_mp_pad(r, 6));
518 MP_DIGIT(r, 5) = r5;
519 MP_DIGIT(r, 4) = r4;
520 MP_DIGIT(r, 3) = r3;
521 MP_DIGIT(r, 2) = r2;
522 MP_DIGIT(r, 1) = r1;
523 MP_DIGIT(r, 0) = r0;
524 MP_SIGN(r) = MP_ZPOS;
525 MP_USED(r) = 6;
527 /* Do quick 'subract' if we've gone over
528 * (add the 2's complement of the curve field) */
529 a5 = MP_DIGIT(&meth->irr,5);
530 if (carry || r5 > a5 ||
531 ((r5 == a5) && mp_cmp(r,&meth->irr) != MP_LT)) {
532 a4 = MP_DIGIT(&meth->irr,4);
533 a3 = MP_DIGIT(&meth->irr,3);
534 a2 = MP_DIGIT(&meth->irr,2);
535 a1 = MP_DIGIT(&meth->irr,1);
536 a0 = MP_DIGIT(&meth->irr,0);
537 MP_SUB_BORROW(r0, a0, r0, 0, carry);
538 MP_SUB_BORROW(r1, a1, r1, carry, carry);
539 MP_SUB_BORROW(r2, a2, r2, carry, carry);
540 MP_SUB_BORROW(r3, a3, r3, carry, carry);
541 MP_SUB_BORROW(r4, a4, r4, carry, carry);
542 MP_SUB_BORROW(r5, a5, r5, carry, carry);
543 MP_DIGIT(r, 5) = r5;
544 MP_DIGIT(r, 4) = r4;
545 MP_DIGIT(r, 3) = r3;
546 MP_DIGIT(r, 2) = r2;
547 MP_DIGIT(r, 1) = r1;
548 MP_DIGIT(r, 0) = r0;
549 }
551 s_mp_clamp(r);
553 CLEANUP:
554 return res;
555 }
557 /*
558 * The following subraction functions do in-line subractions based
559 * on our curve size.
560 *
561 * ... 3 words
562 */
563 mp_err
564 ec_GFp_sub_3(const mp_int *a, const mp_int *b, mp_int *r,
565 const GFMethod *meth)
566 {
567 mp_err res = MP_OKAY;
568 mp_digit b0 = 0, b1 = 0, b2 = 0;
569 mp_digit r0 = 0, r1 = 0, r2 = 0;
570 mp_digit borrow;
572 switch(MP_USED(a)) {
573 case 3:
574 r2 = MP_DIGIT(a,2);
575 case 2:
576 r1 = MP_DIGIT(a,1);
577 case 1:
578 r0 = MP_DIGIT(a,0);
579 }
580 switch(MP_USED(b)) {
581 case 3:
582 b2 = MP_DIGIT(b,2);
583 case 2:
584 b1 = MP_DIGIT(b,1);
585 case 1:
586 b0 = MP_DIGIT(b,0);
587 }
589 #ifndef MPI_AMD64_ADD
590 MP_SUB_BORROW(r0, b0, r0, 0, borrow);
591 MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
592 MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
593 #else
594 __asm__ (
595 "xorq %3,%3 \n\t"
596 "subq %4,%0 \n\t"
597 "sbbq %5,%1 \n\t"
598 "sbbq %6,%2 \n\t"
599 "adcq $0,%3 \n\t"
600 : "=r"(r0), "=r"(r1), "=r"(r2), "=r" (borrow)
601 : "r" (b0), "r" (b1), "r" (b2),
602 "0" (r0), "1" (r1), "2" (r2)
603 : "%cc" );
604 #endif
606 /* Do quick 'add' if we've gone under 0
607 * (subtract the 2's complement of the curve field) */
608 if (borrow) {
609 b2 = MP_DIGIT(&meth->irr,2);
610 b1 = MP_DIGIT(&meth->irr,1);
611 b0 = MP_DIGIT(&meth->irr,0);
612 #ifndef MPI_AMD64_ADD
613 MP_ADD_CARRY(b0, r0, r0, 0, borrow);
614 MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
615 MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
616 #else
617 __asm__ (
618 "addq %3,%0 \n\t"
619 "adcq %4,%1 \n\t"
620 "adcq %5,%2 \n\t"
621 : "=r"(r0), "=r"(r1), "=r"(r2)
622 : "r" (b0), "r" (b1), "r" (b2),
623 "0" (r0), "1" (r1), "2" (r2)
624 : "%cc" );
625 #endif
626 }
628 #ifdef MPI_AMD64_ADD
629 /* compiler fakeout? */
630 if ((r2 == b0) && (r1 == b0) && (r0 == b0)) {
631 MP_CHECKOK(s_mp_pad(r, 4));
632 }
633 #endif
634 MP_CHECKOK(s_mp_pad(r, 3));
635 MP_DIGIT(r, 2) = r2;
636 MP_DIGIT(r, 1) = r1;
637 MP_DIGIT(r, 0) = r0;
638 MP_SIGN(r) = MP_ZPOS;
639 MP_USED(r) = 3;
640 s_mp_clamp(r);
642 CLEANUP:
643 return res;
644 }
646 /* 4 words */
647 mp_err
648 ec_GFp_sub_4(const mp_int *a, const mp_int *b, mp_int *r,
649 const GFMethod *meth)
650 {
651 mp_err res = MP_OKAY;
652 mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0;
653 mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
654 mp_digit borrow;
656 switch(MP_USED(a)) {
657 case 4:
658 r3 = MP_DIGIT(a,3);
659 case 3:
660 r2 = MP_DIGIT(a,2);
661 case 2:
662 r1 = MP_DIGIT(a,1);
663 case 1:
664 r0 = MP_DIGIT(a,0);
665 }
666 switch(MP_USED(b)) {
667 case 4:
668 b3 = MP_DIGIT(b,3);
669 case 3:
670 b2 = MP_DIGIT(b,2);
671 case 2:
672 b1 = MP_DIGIT(b,1);
673 case 1:
674 b0 = MP_DIGIT(b,0);
675 }
677 #ifndef MPI_AMD64_ADD
678 MP_SUB_BORROW(r0, b0, r0, 0, borrow);
679 MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
680 MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
681 MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
682 #else
683 __asm__ (
684 "xorq %4,%4 \n\t"
685 "subq %5,%0 \n\t"
686 "sbbq %6,%1 \n\t"
687 "sbbq %7,%2 \n\t"
688 "sbbq %8,%3 \n\t"
689 "adcq $0,%4 \n\t"
690 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r" (borrow)
691 : "r" (b0), "r" (b1), "r" (b2), "r" (b3),
692 "0" (r0), "1" (r1), "2" (r2), "3" (r3)
693 : "%cc" );
694 #endif
696 /* Do quick 'add' if we've gone under 0
697 * (subtract the 2's complement of the curve field) */
698 if (borrow) {
699 b3 = MP_DIGIT(&meth->irr,3);
700 b2 = MP_DIGIT(&meth->irr,2);
701 b1 = MP_DIGIT(&meth->irr,1);
702 b0 = MP_DIGIT(&meth->irr,0);
703 #ifndef MPI_AMD64_ADD
704 MP_ADD_CARRY(b0, r0, r0, 0, borrow);
705 MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
706 MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
707 MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
708 #else
709 __asm__ (
710 "addq %4,%0 \n\t"
711 "adcq %5,%1 \n\t"
712 "adcq %6,%2 \n\t"
713 "adcq %7,%3 \n\t"
714 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
715 : "r" (b0), "r" (b1), "r" (b2), "r" (b3),
716 "0" (r0), "1" (r1), "2" (r2), "3" (r3)
717 : "%cc" );
718 #endif
719 }
720 #ifdef MPI_AMD64_ADD
721 /* compiler fakeout? */
722 if ((r3 == b0) && (r1 == b0) && (r0 == b0)) {
723 MP_CHECKOK(s_mp_pad(r, 4));
724 }
725 #endif
726 MP_CHECKOK(s_mp_pad(r, 4));
727 MP_DIGIT(r, 3) = r3;
728 MP_DIGIT(r, 2) = r2;
729 MP_DIGIT(r, 1) = r1;
730 MP_DIGIT(r, 0) = r0;
731 MP_SIGN(r) = MP_ZPOS;
732 MP_USED(r) = 4;
733 s_mp_clamp(r);
735 CLEANUP:
736 return res;
737 }
739 /* 5 words */
740 mp_err
741 ec_GFp_sub_5(const mp_int *a, const mp_int *b, mp_int *r,
742 const GFMethod *meth)
743 {
744 mp_err res = MP_OKAY;
745 mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0;
746 mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
747 mp_digit borrow;
749 switch(MP_USED(a)) {
750 case 5:
751 r4 = MP_DIGIT(a,4);
752 case 4:
753 r3 = MP_DIGIT(a,3);
754 case 3:
755 r2 = MP_DIGIT(a,2);
756 case 2:
757 r1 = MP_DIGIT(a,1);
758 case 1:
759 r0 = MP_DIGIT(a,0);
760 }
761 switch(MP_USED(b)) {
762 case 5:
763 b4 = MP_DIGIT(b,4);
764 case 4:
765 b3 = MP_DIGIT(b,3);
766 case 3:
767 b2 = MP_DIGIT(b,2);
768 case 2:
769 b1 = MP_DIGIT(b,1);
770 case 1:
771 b0 = MP_DIGIT(b,0);
772 }
774 MP_SUB_BORROW(r0, b0, r0, 0, borrow);
775 MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
776 MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
777 MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
778 MP_SUB_BORROW(r4, b4, r4, borrow, borrow);
780 /* Do quick 'add' if we've gone under 0
781 * (subtract the 2's complement of the curve field) */
782 if (borrow) {
783 b4 = MP_DIGIT(&meth->irr,4);
784 b3 = MP_DIGIT(&meth->irr,3);
785 b2 = MP_DIGIT(&meth->irr,2);
786 b1 = MP_DIGIT(&meth->irr,1);
787 b0 = MP_DIGIT(&meth->irr,0);
788 MP_ADD_CARRY(b0, r0, r0, 0, borrow);
789 MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
790 MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
791 MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
792 }
793 MP_CHECKOK(s_mp_pad(r, 5));
794 MP_DIGIT(r, 4) = r4;
795 MP_DIGIT(r, 3) = r3;
796 MP_DIGIT(r, 2) = r2;
797 MP_DIGIT(r, 1) = r1;
798 MP_DIGIT(r, 0) = r0;
799 MP_SIGN(r) = MP_ZPOS;
800 MP_USED(r) = 5;
801 s_mp_clamp(r);
803 CLEANUP:
804 return res;
805 }
807 /* 6 words */
808 mp_err
809 ec_GFp_sub_6(const mp_int *a, const mp_int *b, mp_int *r,
810 const GFMethod *meth)
811 {
812 mp_err res = MP_OKAY;
813 mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0, b5 = 0;
814 mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
815 mp_digit borrow;
817 switch(MP_USED(a)) {
818 case 6:
819 r5 = MP_DIGIT(a,5);
820 case 5:
821 r4 = MP_DIGIT(a,4);
822 case 4:
823 r3 = MP_DIGIT(a,3);
824 case 3:
825 r2 = MP_DIGIT(a,2);
826 case 2:
827 r1 = MP_DIGIT(a,1);
828 case 1:
829 r0 = MP_DIGIT(a,0);
830 }
831 switch(MP_USED(b)) {
832 case 6:
833 b5 = MP_DIGIT(b,5);
834 case 5:
835 b4 = MP_DIGIT(b,4);
836 case 4:
837 b3 = MP_DIGIT(b,3);
838 case 3:
839 b2 = MP_DIGIT(b,2);
840 case 2:
841 b1 = MP_DIGIT(b,1);
842 case 1:
843 b0 = MP_DIGIT(b,0);
844 }
846 MP_SUB_BORROW(r0, b0, r0, 0, borrow);
847 MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
848 MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
849 MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
850 MP_SUB_BORROW(r4, b4, r4, borrow, borrow);
851 MP_SUB_BORROW(r5, b5, r5, borrow, borrow);
853 /* Do quick 'add' if we've gone under 0
854 * (subtract the 2's complement of the curve field) */
855 if (borrow) {
856 b5 = MP_DIGIT(&meth->irr,5);
857 b4 = MP_DIGIT(&meth->irr,4);
858 b3 = MP_DIGIT(&meth->irr,3);
859 b2 = MP_DIGIT(&meth->irr,2);
860 b1 = MP_DIGIT(&meth->irr,1);
861 b0 = MP_DIGIT(&meth->irr,0);
862 MP_ADD_CARRY(b0, r0, r0, 0, borrow);
863 MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
864 MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
865 MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
866 MP_ADD_CARRY(b4, r4, r4, borrow, borrow);
867 }
869 MP_CHECKOK(s_mp_pad(r, 6));
870 MP_DIGIT(r, 5) = r5;
871 MP_DIGIT(r, 4) = r4;
872 MP_DIGIT(r, 3) = r3;
873 MP_DIGIT(r, 2) = r2;
874 MP_DIGIT(r, 1) = r1;
875 MP_DIGIT(r, 0) = r0;
876 MP_SIGN(r) = MP_ZPOS;
877 MP_USED(r) = 6;
878 s_mp_clamp(r);
880 CLEANUP:
881 return res;
882 }
885 /* Reduces an integer to a field element. */
886 mp_err
887 ec_GFp_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
888 {
889 return mp_mod(a, &meth->irr, r);
890 }
892 /* Multiplies two field elements. */
893 mp_err
894 ec_GFp_mul(const mp_int *a, const mp_int *b, mp_int *r,
895 const GFMethod *meth)
896 {
897 return mp_mulmod(a, b, &meth->irr, r);
898 }
900 /* Squares a field element. */
901 mp_err
902 ec_GFp_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
903 {
904 return mp_sqrmod(a, &meth->irr, r);
905 }
907 /* Divides two field elements. If a is NULL, then returns the inverse of
908 * b. */
909 mp_err
910 ec_GFp_div(const mp_int *a, const mp_int *b, mp_int *r,
911 const GFMethod *meth)
912 {
913 mp_err res = MP_OKAY;
914 mp_int t;
916 /* If a is NULL, then return the inverse of b, otherwise return a/b. */
917 if (a == NULL) {
918 return mp_invmod(b, &meth->irr, r);
919 } else {
920 /* MPI doesn't support divmod, so we implement it using invmod and
921 * mulmod. */
922 MP_CHECKOK(mp_init(&t));
923 MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
924 MP_CHECKOK(mp_mulmod(a, &t, &meth->irr, r));
925 CLEANUP:
926 mp_clear(&t);
927 return res;
928 }
929 }
931 /* Wrapper functions for generic binary polynomial field arithmetic. */
933 /* Adds two field elements. */
934 mp_err
935 ec_GF2m_add(const mp_int *a, const mp_int *b, mp_int *r,
936 const GFMethod *meth)
937 {
938 return mp_badd(a, b, r);
939 }
941 /* Negates a field element. Note that for binary polynomial fields, the
942 * negation of a field element is the field element itself. */
943 mp_err
944 ec_GF2m_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
945 {
946 if (a == r) {
947 return MP_OKAY;
948 } else {
949 return mp_copy(a, r);
950 }
951 }
953 /* Reduces a binary polynomial to a field element. */
954 mp_err
955 ec_GF2m_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
956 {
957 return mp_bmod(a, meth->irr_arr, r);
958 }
960 /* Multiplies two field elements. */
961 mp_err
962 ec_GF2m_mul(const mp_int *a, const mp_int *b, mp_int *r,
963 const GFMethod *meth)
964 {
965 return mp_bmulmod(a, b, meth->irr_arr, r);
966 }
968 /* Squares a field element. */
969 mp_err
970 ec_GF2m_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
971 {
972 return mp_bsqrmod(a, meth->irr_arr, r);
973 }
975 /* Divides two field elements. If a is NULL, then returns the inverse of
976 * b. */
977 mp_err
978 ec_GF2m_div(const mp_int *a, const mp_int *b, mp_int *r,
979 const GFMethod *meth)
980 {
981 mp_err res = MP_OKAY;
982 mp_int t;
984 /* If a is NULL, then return the inverse of b, otherwise return a/b. */
985 if (a == NULL) {
986 /* The GF(2^m) portion of MPI doesn't support invmod, so we
987 * compute 1/b. */
988 MP_CHECKOK(mp_init(&t));
989 MP_CHECKOK(mp_set_int(&t, 1));
990 MP_CHECKOK(mp_bdivmod(&t, b, &meth->irr, meth->irr_arr, r));
991 CLEANUP:
992 mp_clear(&t);
993 return res;
994 } else {
995 return mp_bdivmod(a, b, &meth->irr, meth->irr_arr, r);
996 }
997 }
