Mercurial > trustbridge > nss-cmake-static

comparison nss/lib/freebl/mpi/mp_gf2m.c @ 0:1e5118fa0cb1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
This is NSS with a Cmake Buildsyste To compile a static NSS library for Windows we've used the Chromium-NSS fork and added a Cmake buildsystem to compile it statically for Windows. See README.chromium for chromium changes and README.trustbridge for our modifications.
author Andre Heinecke <andre.heinecke@intevation.de>
date Mon, 28 Jul 2014 10:47:06 +0200
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:1e5118fa0cb1
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/. */
4
5 #include "mp_gf2m.h"
6 #include "mp_gf2m-priv.h"
7 #include "mplogic.h"
8 #include "mpi-priv.h"
9
10 const mp_digit mp_gf2m_sqr_tb[16] =
11 {
12 0, 1, 4, 5, 16, 17, 20, 21,
13 64, 65, 68, 69, 80, 81, 84, 85
14 };
15
16 /* Multiply two binary polynomials mp_digits a, b.
17 * Result is a polynomial with degree < 2 * MP_DIGIT_BITS - 1.
18 * Output in two mp_digits rh, rl.
19 */
20 #if MP_DIGIT_BITS == 32
21 void
22 s_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b)
23 {
24 register mp_digit h, l, s;
25 mp_digit tab[8], top2b = a >> 30;
26 register mp_digit a1, a2, a4;
27
28 a1 = a & (0x3FFFFFFF); a2 = a1 << 1; a4 = a2 << 1;
29
30 tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2;
31 tab[4] = a4; tab[5] = a1^a4; tab[6] = a2^a4; tab[7] = a1^a2^a4;
32
33 s = tab[b & 0x7]; l = s;
34 s = tab[b >> 3 & 0x7]; l ^= s << 3; h = s >> 29;
35 s = tab[b >> 6 & 0x7]; l ^= s << 6; h ^= s >> 26;
36 s = tab[b >> 9 & 0x7]; l ^= s << 9; h ^= s >> 23;
37 s = tab[b >> 12 & 0x7]; l ^= s << 12; h ^= s >> 20;
38 s = tab[b >> 15 & 0x7]; l ^= s << 15; h ^= s >> 17;
39 s = tab[b >> 18 & 0x7]; l ^= s << 18; h ^= s >> 14;
40 s = tab[b >> 21 & 0x7]; l ^= s << 21; h ^= s >> 11;
41 s = tab[b >> 24 & 0x7]; l ^= s << 24; h ^= s >> 8;
42 s = tab[b >> 27 & 0x7]; l ^= s << 27; h ^= s >> 5;
43 s = tab[b >> 30 ]; l ^= s << 30; h ^= s >> 2;
44
45 /* compensate for the top two bits of a */
46
47 if (top2b & 01) { l ^= b << 30; h ^= b >> 2; }
48 if (top2b & 02) { l ^= b << 31; h ^= b >> 1; }
49
50 *rh = h; *rl = l;
51 }
52 #else
53 void
54 s_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b)
55 {
56 register mp_digit h, l, s;
57 mp_digit tab[16], top3b = a >> 61;
58 register mp_digit a1, a2, a4, a8;
59
60 a1 = a & (0x1FFFFFFFFFFFFFFFULL); a2 = a1 << 1;
61 a4 = a2 << 1; a8 = a4 << 1;
62 tab[ 0] = 0; tab[ 1] = a1; tab[ 2] = a2; tab[ 3] = a1^a2;
63 tab[ 4] = a4; tab[ 5] = a1^a4; tab[ 6] = a2^a4; tab[ 7] = a1^a2^a4;
64 tab[ 8] = a8; tab[ 9] = a1^a8; tab[10] = a2^a8; tab[11] = a1^a2^a8;
65 tab[12] = a4^a8; tab[13] = a1^a4^a8; tab[14] = a2^a4^a8; tab[15] = a1^a2^a4^a8;
66
67 s = tab[b & 0xF]; l = s;
68 s = tab[b >> 4 & 0xF]; l ^= s << 4; h = s >> 60;
69 s = tab[b >> 8 & 0xF]; l ^= s << 8; h ^= s >> 56;
70 s = tab[b >> 12 & 0xF]; l ^= s << 12; h ^= s >> 52;
71 s = tab[b >> 16 & 0xF]; l ^= s << 16; h ^= s >> 48;
72 s = tab[b >> 20 & 0xF]; l ^= s << 20; h ^= s >> 44;
73 s = tab[b >> 24 & 0xF]; l ^= s << 24; h ^= s >> 40;
74 s = tab[b >> 28 & 0xF]; l ^= s << 28; h ^= s >> 36;
75 s = tab[b >> 32 & 0xF]; l ^= s << 32; h ^= s >> 32;
76 s = tab[b >> 36 & 0xF]; l ^= s << 36; h ^= s >> 28;
77 s = tab[b >> 40 & 0xF]; l ^= s << 40; h ^= s >> 24;
78 s = tab[b >> 44 & 0xF]; l ^= s << 44; h ^= s >> 20;
79 s = tab[b >> 48 & 0xF]; l ^= s << 48; h ^= s >> 16;
80 s = tab[b >> 52 & 0xF]; l ^= s << 52; h ^= s >> 12;
81 s = tab[b >> 56 & 0xF]; l ^= s << 56; h ^= s >> 8;
82 s = tab[b >> 60 ]; l ^= s << 60; h ^= s >> 4;
83
84 /* compensate for the top three bits of a */
85
86 if (top3b & 01) { l ^= b << 61; h ^= b >> 3; }
87 if (top3b & 02) { l ^= b << 62; h ^= b >> 2; }
88 if (top3b & 04) { l ^= b << 63; h ^= b >> 1; }
89
90 *rh = h; *rl = l;
91 }
92 #endif
93
94 /* Compute xor-multiply of two binary polynomials (a1, a0) x (b1, b0)
95 * result is a binary polynomial in 4 mp_digits r[4].
96 * The caller MUST ensure that r has the right amount of space allocated.
97 */
98 void
99 s_bmul_2x2(mp_digit *r, const mp_digit a1, const mp_digit a0, const mp_digit b1,
100 const mp_digit b0)
101 {
102 mp_digit m1, m0;
103 /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */
104 s_bmul_1x1(r+3, r+2, a1, b1);
105 s_bmul_1x1(r+1, r, a0, b0);
106 s_bmul_1x1(&m1, &m0, a0 ^ a1, b0 ^ b1);
107 /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */
108 r[2] ^= m1 ^ r[1] ^ r[3]; /* h0 ^= m1 ^ l1 ^ h1; */
109 r[1] = r[3] ^ r[2] ^ r[0] ^ m1 ^ m0; /* l1 ^= l0 ^ h0 ^ m0; */
110 }
111
112 /* Compute xor-multiply of two binary polynomials (a2, a1, a0) x (b2, b1, b0)
113 * result is a binary polynomial in 6 mp_digits r[6].
114 * The caller MUST ensure that r has the right amount of space allocated.
115 */
116 void
117 s_bmul_3x3(mp_digit *r, const mp_digit a2, const mp_digit a1, const mp_digit a0,
118 const mp_digit b2, const mp_digit b1, const mp_digit b0)
119 {
120 mp_digit zm[4];
121
122 s_bmul_1x1(r+5, r+4, a2, b2); /* fill top 2 words */
123 s_bmul_2x2(zm, a1, a2^a0, b1, b2^b0); /* fill middle 4 words */
124 s_bmul_2x2(r, a1, a0, b1, b0); /* fill bottom 4 words */
125
126 zm[3] ^= r[3];
127 zm[2] ^= r[2];
128 zm[1] ^= r[1] ^ r[5];
129 zm[0] ^= r[0] ^ r[4];
130
131 r[5] ^= zm[3];
132 r[4] ^= zm[2];
133 r[3] ^= zm[1];
134 r[2] ^= zm[0];
135 }
136
137 /* Compute xor-multiply of two binary polynomials (a3, a2, a1, a0) x (b3, b2, b1, b0)
138 * result is a binary polynomial in 8 mp_digits r[8].
139 * The caller MUST ensure that r has the right amount of space allocated.
140 */
141 void s_bmul_4x4(mp_digit *r, const mp_digit a3, const mp_digit a2, const mp_digit a1,
142 const mp_digit a0, const mp_digit b3, const mp_digit b2, const mp_digit b1,
143 const mp_digit b0)
144 {
145 mp_digit zm[4];
146
147 s_bmul_2x2(r+4, a3, a2, b3, b2); /* fill top 4 words */
148 s_bmul_2x2(zm, a3^a1, a2^a0, b3^b1, b2^b0); /* fill middle 4 words */
149 s_bmul_2x2(r, a1, a0, b1, b0); /* fill bottom 4 words */
150
151 zm[3] ^= r[3] ^ r[7];
152 zm[2] ^= r[2] ^ r[6];
153 zm[1] ^= r[1] ^ r[5];
154 zm[0] ^= r[0] ^ r[4];
155
156 r[5] ^= zm[3];
157 r[4] ^= zm[2];
158 r[3] ^= zm[1];
159 r[2] ^= zm[0];
160 }
161
162 /* Compute addition of two binary polynomials a and b,
163 * store result in c; c could be a or b, a and b could be equal;
164 * c is the bitwise XOR of a and b.
165 */
166 mp_err
167 mp_badd(const mp_int *a, const mp_int *b, mp_int *c)
168 {
169 mp_digit *pa, *pb, *pc;
170 mp_size ix;
171 mp_size used_pa, used_pb;
172 mp_err res = MP_OKAY;
173
174 /* Add all digits up to the precision of b. If b had more
175 * precision than a initially, swap a, b first
176 */
177 if (MP_USED(a) >= MP_USED(b)) {
178 pa = MP_DIGITS(a);
179 pb = MP_DIGITS(b);
180 used_pa = MP_USED(a);
181 used_pb = MP_USED(b);
182 } else {
183 pa = MP_DIGITS(b);
184 pb = MP_DIGITS(a);
185 used_pa = MP_USED(b);
186 used_pb = MP_USED(a);
187 }
188
189 /* Make sure c has enough precision for the output value */
190 MP_CHECKOK( s_mp_pad(c, used_pa) );
191
192 /* Do word-by-word xor */
193 pc = MP_DIGITS(c);
194 for (ix = 0; ix < used_pb; ix++) {
195 (*pc++) = (*pa++) ^ (*pb++);
196 }
197
198 /* Finish the rest of digits until we're actually done */
199 for (; ix < used_pa; ++ix) {
200 *pc++ = *pa++;
201 }
202
203 MP_USED(c) = used_pa;
204 MP_SIGN(c) = ZPOS;
205 s_mp_clamp(c);
206
207 CLEANUP:
208 return res;
209 }
210
211 #define s_mp_div2(a) MP_CHECKOK( mpl_rsh((a), (a), 1) );
212
213 /* Compute binary polynomial multiply d = a * b */
214 static void
215 s_bmul_d(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d)
216 {
217 mp_digit a_i, a0b0, a1b1, carry = 0;
218 while (a_len--) {
219 a_i = *a++;
220 s_bmul_1x1(&a1b1, &a0b0, a_i, b);
221 *d++ = a0b0 ^ carry;
222 carry = a1b1;
223 }
224 *d = carry;
225 }
226
227 /* Compute binary polynomial xor multiply accumulate d ^= a * b */
228 static void
229 s_bmul_d_add(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d)
230 {
231 mp_digit a_i, a0b0, a1b1, carry = 0;
232 while (a_len--) {
233 a_i = *a++;
234 s_bmul_1x1(&a1b1, &a0b0, a_i, b);
235 *d++ ^= a0b0 ^ carry;
236 carry = a1b1;
237 }
238 *d ^= carry;
239 }
240
241 /* Compute binary polynomial xor multiply c = a * b.
242 * All parameters may be identical.
243 */
244 mp_err
245 mp_bmul(const mp_int *a, const mp_int *b, mp_int *c)
246 {
247 mp_digit *pb, b_i;
248 mp_int tmp;
249 mp_size ib, a_used, b_used;
250 mp_err res = MP_OKAY;
251
252 MP_DIGITS(&tmp) = 0;
253
254 ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
255
256 if (a == c) {
257 MP_CHECKOK( mp_init_copy(&tmp, a) );
258 if (a == b)
259 b = &tmp;
260 a = &tmp;
261 } else if (b == c) {
262 MP_CHECKOK( mp_init_copy(&tmp, b) );
263 b = &tmp;
264 }
265
266 if (MP_USED(a) < MP_USED(b)) {
267 const mp_int *xch = b; /* switch a and b if b longer */
268 b = a;
269 a = xch;
270 }
271
272 MP_USED(c) = 1; MP_DIGIT(c, 0) = 0;
273 MP_CHECKOK( s_mp_pad(c, USED(a) + USED(b)) );
274
275 pb = MP_DIGITS(b);
276 s_bmul_d(MP_DIGITS(a), MP_USED(a), *pb++, MP_DIGITS(c));
277
278 /* Outer loop: Digits of b */
279 a_used = MP_USED(a);
280 b_used = MP_USED(b);
281 MP_USED(c) = a_used + b_used;
282 for (ib = 1; ib < b_used; ib++) {
283 b_i = *pb++;
284
285 /* Inner product: Digits of a */
286 if (b_i)
287 s_bmul_d_add(MP_DIGITS(a), a_used, b_i, MP_DIGITS(c) + ib);
288 else
289 MP_DIGIT(c, ib + a_used) = b_i;
290 }
291
292 s_mp_clamp(c);
293
294 SIGN(c) = ZPOS;
295
296 CLEANUP:
297 mp_clear(&tmp);
298 return res;
299 }
300
301
302 /* Compute modular reduction of a and store result in r.
303 * r could be a.
304 * For modular arithmetic, the irreducible polynomial f(t) is represented
305 * as an array of int[], where f(t) is of the form:
306 * f(t) = t^p[0] + t^p[1] + ... + t^p[k]
307 * where m = p[0] > p[1] > ... > p[k] = 0.
308 */
309 mp_err
310 mp_bmod(const mp_int *a, const unsigned int p[], mp_int *r)
311 {
312 int j, k;
313 int n, dN, d0, d1;
314 mp_digit zz, *z, tmp;
315 mp_size used;
316 mp_err res = MP_OKAY;
317
318 /* The algorithm does the reduction in place in r,
319 * if a != r, copy a into r first so reduction can be done in r
320 */
321 if (a != r) {
322 MP_CHECKOK( mp_copy(a, r) );
323 }
324 z = MP_DIGITS(r);
325
326 /* start reduction */
327 /*dN = p[0] / MP_DIGIT_BITS; */
328 dN = p[0] >> MP_DIGIT_BITS_LOG_2;
329 used = MP_USED(r);
330
331 for (j = used - 1; j > dN;) {
332
333 zz = z[j];
334 if (zz == 0) {
335 j--; continue;
336 }
337 z[j] = 0;
338
339 for (k = 1; p[k] > 0; k++) {
340 /* reducing component t^p[k] */
341 n = p[0] - p[k];
342 /*d0 = n % MP_DIGIT_BITS; */
343 d0 = n & MP_DIGIT_BITS_MASK;
344 d1 = MP_DIGIT_BITS - d0;
345 /*n /= MP_DIGIT_BITS; */
346 n >>= MP_DIGIT_BITS_LOG_2;
347 z[j-n] ^= (zz>>d0);
348 if (d0)
349 z[j-n-1] ^= (zz<<d1);
350 }
351
352 /* reducing component t^0 */
353 n = dN;
354 /*d0 = p[0] % MP_DIGIT_BITS;*/
355 d0 = p[0] & MP_DIGIT_BITS_MASK;
356 d1 = MP_DIGIT_BITS - d0;
357 z[j-n] ^= (zz >> d0);
358 if (d0)
359 z[j-n-1] ^= (zz << d1);
360
361 }
362
363 /* final round of reduction */
364 while (j == dN) {
365
366 /* d0 = p[0] % MP_DIGIT_BITS; */
367 d0 = p[0] & MP_DIGIT_BITS_MASK;
368 zz = z[dN] >> d0;
369 if (zz == 0) break;
370 d1 = MP_DIGIT_BITS - d0;
371
372 /* clear up the top d1 bits */
373 if (d0) {
374 z[dN] = (z[dN] << d1) >> d1;
375 } else {
376 z[dN] = 0;
377 }
378 *z ^= zz; /* reduction t^0 component */
379
380 for (k = 1; p[k] > 0; k++) {
381 /* reducing component t^p[k]*/
382 /* n = p[k] / MP_DIGIT_BITS; */
383 n = p[k] >> MP_DIGIT_BITS_LOG_2;
384 /* d0 = p[k] % MP_DIGIT_BITS; */
385 d0 = p[k] & MP_DIGIT_BITS_MASK;
386 d1 = MP_DIGIT_BITS - d0;
387 z[n] ^= (zz << d0);
388 tmp = zz >> d1;
389 if (d0 && tmp)
390 z[n+1] ^= tmp;
391 }
392 }
393
394 s_mp_clamp(r);
395 CLEANUP:
396 return res;
397 }
398
399 /* Compute the product of two polynomials a and b, reduce modulo p,
400 * Store the result in r. r could be a or b; a could be b.
401 */
402 mp_err
403 mp_bmulmod(const mp_int *a, const mp_int *b, const unsigned int p[], mp_int *r)
404 {
405 mp_err res;
406
407 if (a == b) return mp_bsqrmod(a, p, r);
408 if ((res = mp_bmul(a, b, r) ) != MP_OKAY)
409 return res;
410 return mp_bmod(r, p, r);
411 }
412
413 /* Compute binary polynomial squaring c = a*a mod p .
414 * Parameter r and a can be identical.
415 */
416
417 mp_err
418 mp_bsqrmod(const mp_int *a, const unsigned int p[], mp_int *r)
419 {
420 mp_digit *pa, *pr, a_i;
421 mp_int tmp;
422 mp_size ia, a_used;
423 mp_err res;
424
425 ARGCHK(a != NULL && r != NULL, MP_BADARG);
426 MP_DIGITS(&tmp) = 0;
427
428 if (a == r) {
429 MP_CHECKOK( mp_init_copy(&tmp, a) );
430 a = &tmp;
431 }
432
433 MP_USED(r) = 1; MP_DIGIT(r, 0) = 0;
434 MP_CHECKOK( s_mp_pad(r, 2*USED(a)) );
435
436 pa = MP_DIGITS(a);
437 pr = MP_DIGITS(r);
438 a_used = MP_USED(a);
439 MP_USED(r) = 2 * a_used;
440
441 for (ia = 0; ia < a_used; ia++) {
442 a_i = *pa++;
443 *pr++ = gf2m_SQR0(a_i);
444 *pr++ = gf2m_SQR1(a_i);
445 }
446
447 MP_CHECKOK( mp_bmod(r, p, r) );
448 s_mp_clamp(r);
449 SIGN(r) = ZPOS;
450
451 CLEANUP:
452 mp_clear(&tmp);
453 return res;
454 }
455
456 /* Compute binary polynomial y/x mod p, y divided by x, reduce modulo p.
457 * Store the result in r. r could be x or y, and x could equal y.
458 * Uses algorithm Modular_Division_GF(2^m) from
459 * Chang-Shantz, S. "From Euclid's GCD to Montgomery Multiplication to
460 * the Great Divide".
461 */
462 int
463 mp_bdivmod(const mp_int *y, const mp_int *x, const mp_int *pp,
464 const unsigned int p[], mp_int *r)
465 {
466 mp_int aa, bb, uu;
467 mp_int *a, *b, *u, *v;
468 mp_err res = MP_OKAY;
469
470 MP_DIGITS(&aa) = 0;
471 MP_DIGITS(&bb) = 0;
472 MP_DIGITS(&uu) = 0;
473
474 MP_CHECKOK( mp_init_copy(&aa, x) );
475 MP_CHECKOK( mp_init_copy(&uu, y) );
476 MP_CHECKOK( mp_init_copy(&bb, pp) );
477 MP_CHECKOK( s_mp_pad(r, USED(pp)) );
478 MP_USED(r) = 1; MP_DIGIT(r, 0) = 0;
479
480 a = &aa; b= &bb; u=&uu; v=r;
481 /* reduce x and y mod p */
482 MP_CHECKOK( mp_bmod(a, p, a) );
483 MP_CHECKOK( mp_bmod(u, p, u) );
484
485 while (!mp_isodd(a)) {
486 s_mp_div2(a);
487 if (mp_isodd(u)) {
488 MP_CHECKOK( mp_badd(u, pp, u) );
489 }
490 s_mp_div2(u);
491 }
492
493 do {
494 if (mp_cmp_mag(b, a) > 0) {
495 MP_CHECKOK( mp_badd(b, a, b) );
496 MP_CHECKOK( mp_badd(v, u, v) );
497 do {
498 s_mp_div2(b);
499 if (mp_isodd(v)) {
500 MP_CHECKOK( mp_badd(v, pp, v) );
501 }
502 s_mp_div2(v);
503 } while (!mp_isodd(b));
504 }
505 else if ((MP_DIGIT(a,0) == 1) && (MP_USED(a) == 1))
506 break;
507 else {
508 MP_CHECKOK( mp_badd(a, b, a) );
509 MP_CHECKOK( mp_badd(u, v, u) );
510 do {
511 s_mp_div2(a);
512 if (mp_isodd(u)) {
513 MP_CHECKOK( mp_badd(u, pp, u) );
514 }
515 s_mp_div2(u);
516 } while (!mp_isodd(a));
517 }
518 } while (1);
519
520 MP_CHECKOK( mp_copy(u, r) );
521
522 CLEANUP:
523 mp_clear(&aa);
524 mp_clear(&bb);
525 mp_clear(&uu);
526 return res;
527
528 }
529
530 /* Convert the bit-string representation of a polynomial a into an array
531 * of integers corresponding to the bits with non-zero coefficient.
532 * Up to max elements of the array will be filled. Return value is total
533 * number of coefficients that would be extracted if array was large enough.
534 */
535 int
536 mp_bpoly2arr(const mp_int *a, unsigned int p[], int max)
537 {
538 int i, j, k;
539 mp_digit top_bit, mask;
540
541 top_bit = 1;
542 top_bit <<= MP_DIGIT_BIT - 1;
543
544 for (k = 0; k < max; k++) p[k] = 0;
545 k = 0;
546
547 for (i = MP_USED(a) - 1; i >= 0; i--) {
548 mask = top_bit;
549 for (j = MP_DIGIT_BIT - 1; j >= 0; j--) {
550 if (MP_DIGITS(a)[i] & mask) {
551 if (k < max) p[k] = MP_DIGIT_BIT * i + j;
552 k++;
553 }
554 mask >>= 1;
555 }
556 }
557
558 return k;
559 }
560
561 /* Convert the coefficient array representation of a polynomial to a
562 * bit-string. The array must be terminated by 0.
563 */
564 mp_err
565 mp_barr2poly(const unsigned int p[], mp_int *a)
566 {
567
568 mp_err res = MP_OKAY;
569 int i;
570
571 mp_zero(a);
572 for (i = 0; p[i] > 0; i++) {
573 MP_CHECKOK( mpl_set_bit(a, p[i], 1) );
574 }
575 MP_CHECKOK( mpl_set_bit(a, 0, 1) );
576
577 CLEANUP:
578 return res;
579 }
This site is hosted by Intevation GmbH (Datenschutzerklärung und Impressum | Privacy Policy and Imprint)