/*
* ***** BEGIN LICENSE BLOCK *****
* Version: MPL 1.1/GPL 2.0/LGPL 2.1
*
* The contents of this file are subject to the Mozilla Public License Version
* 1.1 (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* Software distributed under the License is distributed on an "AS IS" basis,
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
* for the specific language governing rights and limitations under the
* License.
*
* The Original Code is the Multi-precision Binary Polynomial Arithmetic Library.
*
* The Initial Developer of the Original Code is
* Sun Microsystems, Inc.
* Portions created by the Initial Developer are Copyright (C) 2003
* the Initial Developer. All Rights Reserved.
*
* Contributor(s):
* Sheueling Chang Shantz <sheueling.chang@sun.com> and
* Douglas Stebila <douglas@stebila.ca> of Sun Laboratories.
*
* Alternatively, the contents of this file may be used under the terms of
* either the GNU General Public License Version 2 or later (the "GPL"), or
* the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
* in which case the provisions of the GPL or the LGPL are applicable instead
* of those above. If you wish to allow use of your version of this file only
* under the terms of either the GPL or the LGPL, and not to allow others to
* use your version of this file under the terms of the MPL, indicate your
* decision by deleting the provisions above and replace them with the notice
* and other provisions required by the GPL or the LGPL. If you do not delete
* the provisions above, a recipient may use your version of this file under
* the terms of any one of the MPL, the GPL or the LGPL.
*
* ***** END LICENSE BLOCK ***** */
/*
* Copyright 2007 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*
* Sun elects to use this software under the MPL license.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
#include "mp_gf2m.h"
#include "mp_gf2m-priv.h"
#include "mplogic.h"
#include "mpi-priv.h"
{
0, 1, 4, 5, 16, 17, 20, 21,
64, 65, 68, 69, 80, 81, 84, 85
};
/* Multiply two binary polynomials mp_digits a, b.
* Result is a polynomial with degree < 2 * MP_DIGIT_BITS - 1.
* Output in two mp_digits rh, rl.
*/
#if MP_DIGIT_BITS == 32
void
{
register mp_digit h, l, s;
s = tab[b & 0x7]; l = s;
/* compensate for the top two bits of a */
}
#else
void
{
register mp_digit h, l, s;
s = tab[b & 0xF]; l = s;
/* compensate for the top three bits of a */
}
#endif
/* Compute xor-multiply of two binary polynomials (a1, a0) x (b1, b0)
* result is a binary polynomial in 4 mp_digits r[4].
* The caller MUST ensure that r has the right amount of space allocated.
*/
void
{
/* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */
/* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */
}
/* Compute xor-multiply of two binary polynomials (a2, a1, a0) x (b2, b1, b0)
* result is a binary polynomial in 6 mp_digits r[6].
* The caller MUST ensure that r has the right amount of space allocated.
*/
void
{
zm[0] ^= r[0] ^ r[4];
r[2] ^= zm[0];
}
/* Compute xor-multiply of two binary polynomials (a3, a2, a1, a0) x (b3, b2, b1, b0)
* result is a binary polynomial in 8 mp_digits r[8].
* The caller MUST ensure that r has the right amount of space allocated.
*/
{
zm[0] ^= r[0] ^ r[4];
r[2] ^= zm[0];
}
/* Compute addition of two binary polynomials a and b,
* store result in c; c could be a or b, a and b could be equal;
* c is the bitwise XOR of a and b.
*/
{
/* Add all digits up to the precision of b. If b had more
* precision than a initially, swap a, b first
*/
} else {
}
/* Make sure c has enough precision for the output value */
/* Do word-by-word xor */
}
/* Finish the rest of digits until we're actually done */
}
s_mp_clamp(c);
return res;
}
/* Compute binary polynomial multiply d = a * b */
static void
{
while (a_len--) {
a_i = *a++;
}
*d = carry;
}
/* Compute binary polynomial xor multiply accumulate d ^= a * b */
static void
{
while (a_len--) {
a_i = *a++;
}
*d ^= carry;
}
/* Compute binary polynomial xor multiply c = a * b.
* All parameters may be identical.
*/
{
if (a == c) {
if (a == b)
b = &tmp;
a = &tmp;
} else if (b == c) {
b = &tmp;
}
b = a;
a = xch;
}
/* Outer loop: Digits of b */
/* Inner product: Digits of a */
if (b_i)
else
}
s_mp_clamp(c);
return res;
}
/* Compute modular reduction of a and store result in r.
* r could be a.
* For modular arithmetic, the irreducible polynomial f(t) is represented
* as an array of int[], where f(t) is of the form:
* f(t) = t^p[0] + t^p[1] + ... + t^p[k]
* where m = p[0] > p[1] > ... > p[k] = 0.
*/
{
int j, k;
/* The algorithm does the reduction in place in r,
* if a != r, copy a into r first so reduction can be done in r
*/
if (a != r) {
MP_CHECKOK( mp_copy(a, r) );
}
z = MP_DIGITS(r);
/* start reduction */
dN = p[0] / MP_DIGIT_BITS;
zz = z[j];
if (zz == 0) {
j--; continue;
}
z[j] = 0;
for (k = 1; p[k] > 0; k++) {
/* reducing component t^p[k] */
n = p[0] - p[k];
d0 = n % MP_DIGIT_BITS;
n /= MP_DIGIT_BITS;
if (d0)
}
/* reducing component t^0 */
n = dN;
d0 = p[0] % MP_DIGIT_BITS;
if (d0)
}
/* final round of reduction */
while (j == dN) {
d0 = p[0] % MP_DIGIT_BITS;
if (zz == 0) break;
/* clear up the top d1 bits */
*z ^= zz; /* reduction t^0 component */
for (k = 1; p[k] > 0; k++) {
/* reducing component t^p[k]*/
n = p[k] / MP_DIGIT_BITS;
d0 = p[k] % MP_DIGIT_BITS;
z[n+1] ^= tmp;
}
}
s_mp_clamp(r);
return res;
}
/* Compute the product of two polynomials a and b, reduce modulo p,
* Store the result in r. r could be a or b; a could be b.
*/
{
if (a == b) return mp_bsqrmod(a, p, r);
return res;
return mp_bmod(r, p, r);
}
/* Compute binary polynomial squaring c = a*a mod p .
* Parameter r and a can be identical.
*/
{
if (a == r) {
a = &tmp;
}
}
MP_CHECKOK( mp_bmod(r, p, r) );
s_mp_clamp(r);
return res;
}
/* Compute binary polynomial y/x mod p, y divided by x, reduce modulo p.
* Store the result in r. r could be x or y, and x could equal y.
* Uses algorithm Modular_Division_GF(2^m) from
* Chang-Shantz, S. "From Euclid's GCD to Montgomery Multiplication to
* the Great Divide".
*/
int
const unsigned int p[], mp_int *r)
{
mp_int *a, *b, *u, *v;
/* reduce x and y mod p */
MP_CHECKOK( mp_bmod(a, p, a) );
MP_CHECKOK( mp_bmod(u, p, u) );
while (!mp_isodd(a)) {
s_mp_div2(a);
if (mp_isodd(u)) {
}
s_mp_div2(u);
}
do {
if (mp_cmp_mag(b, a) > 0) {
MP_CHECKOK( mp_badd(b, a, b) );
MP_CHECKOK( mp_badd(v, u, v) );
do {
s_mp_div2(b);
if (mp_isodd(v)) {
}
s_mp_div2(v);
} while (!mp_isodd(b));
}
break;
else {
MP_CHECKOK( mp_badd(a, b, a) );
MP_CHECKOK( mp_badd(u, v, u) );
do {
s_mp_div2(a);
if (mp_isodd(u)) {
}
s_mp_div2(u);
} while (!mp_isodd(a));
}
} while (1);
MP_CHECKOK( mp_copy(u, r) );
/* XXX this appears to be a memory leak in the NSS code */
return res;
}
/* Convert the bit-string representation of a polynomial a into an array
* of integers corresponding to the bits with non-zero coefficient.
* Up to max elements of the array will be filled. Return value is total
* number of coefficients that would be extracted if array was large enough.
*/
int
{
int i, j, k;
top_bit = 1;
for (k = 0; k < max; k++) p[k] = 0;
k = 0;
for (i = MP_USED(a) - 1; i >= 0; i--) {
for (j = MP_DIGIT_BIT - 1; j >= 0; j--) {
if (k < max) p[k] = MP_DIGIT_BIT * i + j;
k++;
}
mask >>= 1;
}
}
return k;
}
/* Convert the coefficient array representation of a polynomial to a
* bit-string. The array must be terminated by 0.
*/
{
int i;
mp_zero(a);
for (i = 0; p[i] > 0; i++) {
}
return res;
}