Back to index

lightning-sunbird  0.9+nobinonly
Functions
mp_gf2m.h File Reference
#include "mpi.h"
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

mp_err mp_badd (const mp_int *a, const mp_int *b, mp_int *c)
mp_err mp_bmul (const mp_int *a, const mp_int *b, mp_int *c)
mp_err mp_bmod (const mp_int *a, const unsigned int p[], mp_int *r)
mp_err mp_bmulmod (const mp_int *a, const mp_int *b, const unsigned int p[], mp_int *r)
mp_err mp_bsqrmod (const mp_int *a, const unsigned int p[], mp_int *r)
mp_err mp_bdivmod (const mp_int *y, const mp_int *x, const mp_int *pp, const unsigned int p[], mp_int *r)
int mp_bpoly2arr (const mp_int *a, unsigned int p[], int max)
mp_err mp_barr2poly (const unsigned int p[], mp_int *a)

Function Documentation

mp_err mp_badd ( const mp_int a,
const mp_int b,
mp_int c 
)

Definition at line 202 of file mp_gf2m.c.

{
    mp_digit *pa, *pb, *pc;
    mp_size ix;
    mp_size used_pa, used_pb;
    mp_err res = MP_OKAY;

    /* Add all digits up to the precision of b.  If b had more
     * precision than a initially, swap a, b first
     */
    if (MP_USED(a) >= MP_USED(b)) {
        pa = MP_DIGITS(a);
        pb = MP_DIGITS(b);
        used_pa = MP_USED(a);
        used_pb = MP_USED(b);
    } else {
        pa = MP_DIGITS(b);
        pb = MP_DIGITS(a);
        used_pa = MP_USED(b);
        used_pb = MP_USED(a);
    }

    /* Make sure c has enough precision for the output value */
    MP_CHECKOK( s_mp_pad(c, used_pa) );

    /* Do word-by-word xor */
    pc = MP_DIGITS(c);
    for (ix = 0; ix < used_pb; ix++) {
        (*pc++) = (*pa++) ^ (*pb++);
    }

    /* Finish the rest of digits until we're actually done */
    for (; ix < used_pa; ++ix) {
        *pc++ = *pa++;
    }

    MP_USED(c) = used_pa;
    MP_SIGN(c) = ZPOS;
    s_mp_clamp(c);

CLEANUP:
    return res;
} 
mp_err mp_barr2poly ( const unsigned int  p[],
mp_int a 
)

Definition at line 589 of file mp_gf2m.c.

{

    mp_err res = MP_OKAY;
    int i;

    mp_zero(a);
    for (i = 0; p[i] > 0; i++) {
       MP_CHECKOK( mpl_set_bit(a, p[i], 1) );
    }
    MP_CHECKOK( mpl_set_bit(a, 0, 1) );
       
CLEANUP:
    return res;
}
mp_err mp_bdivmod ( const mp_int y,
const mp_int x,
const mp_int pp,
const unsigned int  p[],
mp_int r 
)

Definition at line 487 of file mp_gf2m.c.

{
    mp_int aa, bb, uu;
    mp_int *a, *b, *u, *v;
    mp_err res = MP_OKAY;

    MP_DIGITS(&aa) = 0;
    MP_DIGITS(&bb) = 0;
    MP_DIGITS(&uu) = 0;

    MP_CHECKOK( mp_init_copy(&aa, x) );
    MP_CHECKOK( mp_init_copy(&uu, y) );
    MP_CHECKOK( mp_init_copy(&bb, pp) );
    MP_CHECKOK( s_mp_pad(r, USED(pp)) );
    MP_USED(r) = 1; MP_DIGIT(r, 0) = 0;

    a = &aa; b= &bb; u=&uu; v=r;
    /* 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)) {
            MP_CHECKOK( mp_badd(u, pp, 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)) {
                    MP_CHECKOK( mp_badd(v, pp, v) );
                }
                s_mp_div2(v);
            } while (!mp_isodd(b));
        }
        else if ((MP_DIGIT(a,0) == 1) && (MP_USED(a) == 1))
            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)) {
                    MP_CHECKOK( mp_badd(u, pp, u) );
                }
                s_mp_div2(u);
            } while (!mp_isodd(a));
        }
    } while (1);

    MP_CHECKOK( mp_copy(u, r) );

CLEANUP:
    mp_clear(&aa);
    mp_clear(&bb);
    mp_clear(&uu);
    return res;

}
mp_err mp_bmod ( const mp_int a,
const unsigned int  p[],
mp_int r 
)

Definition at line 345 of file mp_gf2m.c.

{
    int j, k;
    int n, dN, d0, d1;
    mp_digit zz, *z, tmp;
    mp_size used;
    mp_err res = MP_OKAY;

    /* 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;
    used = MP_USED(r);

    for (j = used - 1; j > dN;) {

        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;  
            d1 = MP_DIGIT_BITS - d0;
            n /= MP_DIGIT_BITS;
            z[j-n] ^= (zz>>d0);
            if (d0) 
                z[j-n-1] ^= (zz<<d1);
        }

        /* reducing component t^0 */
        n = dN;  
        d0 = p[0] % MP_DIGIT_BITS;
        d1 = MP_DIGIT_BITS - d0;
        z[j-n] ^= (zz >> d0);
        if (d0) 
            z[j-n-1] ^= (zz << d1);

    }

    /* final round of reduction */
    while (j == dN) {

        d0 = p[0] % MP_DIGIT_BITS;
        zz = z[dN] >> d0;  
        if (zz == 0) break;
        d1 = MP_DIGIT_BITS - d0;

        /* clear up the top d1 bits */
        if (d0) z[dN] = (z[dN] << d1) >> d1; 
        *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;
            d1 = MP_DIGIT_BITS - d0;
            z[n] ^= (zz << d0);
            tmp = zz >> d1;
            if (d0 && tmp)
                z[n+1] ^= tmp;
        }
    }

    s_mp_clamp(r);
CLEANUP:
    return res;
}
mp_err mp_bmul ( const mp_int a,
const mp_int b,
mp_int c 
)

Definition at line 280 of file mp_gf2m.c.

{
    mp_digit *pb, b_i;
    mp_int tmp;
    mp_size ib, a_used, b_used;
    mp_err res = MP_OKAY;

    MP_DIGITS(&tmp) = 0;

    ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);

    if (a == c) {
        MP_CHECKOK( mp_init_copy(&tmp, a) );
        if (a == b)
            b = &tmp;
        a = &tmp;
    } else if (b == c) {
        MP_CHECKOK( mp_init_copy(&tmp, b) );
        b = &tmp;
    }

    if (MP_USED(a) < MP_USED(b)) {
        const mp_int *xch = b;      /* switch a and b if b longer */
        b = a;
        a = xch;
    }

    MP_USED(c) = 1; MP_DIGIT(c, 0) = 0;
    MP_CHECKOK( s_mp_pad(c, USED(a) + USED(b)) );

    pb = MP_DIGITS(b);
    s_bmul_d(MP_DIGITS(a), MP_USED(a), *pb++, MP_DIGITS(c));

    /* Outer loop:  Digits of b */
    a_used = MP_USED(a);
    b_used = MP_USED(b);
       MP_USED(c) = a_used + b_used;
    for (ib = 1; ib < b_used; ib++) {
        b_i = *pb++;

        /* Inner product:  Digits of a */
        if (b_i)
            s_bmul_d_add(MP_DIGITS(a), a_used, b_i, MP_DIGITS(c) + ib);
        else
            MP_DIGIT(c, ib + a_used) = b_i;
    }

    s_mp_clamp(c);

    SIGN(c) = ZPOS;

CLEANUP:
    mp_clear(&tmp);
    return res;
}
mp_err mp_bmulmod ( const mp_int a,
const mp_int b,
const unsigned int  p[],
mp_int r 
)

Definition at line 427 of file mp_gf2m.c.

{
    mp_err res;
    
    if (a == b) return mp_bsqrmod(a, p, r);
    if ((res = mp_bmul(a, b, r) ) != MP_OKAY)
       return res;
    return mp_bmod(r, p, r);
}
int mp_bpoly2arr ( const mp_int a,
unsigned int  p[],
int  max 
)

Definition at line 560 of file mp_gf2m.c.

{
    int i, j, k;
    mp_digit top_bit, mask;

    top_bit = 1;
    top_bit <<= MP_DIGIT_BIT - 1;

    for (k = 0; k < max; k++) p[k] = 0;
    k = 0;

    for (i = MP_USED(a) - 1; i >= 0; i--) {
        mask = top_bit;
        for (j = MP_DIGIT_BIT - 1; j >= 0; j--) {
            if (MP_DIGITS(a)[i] & mask) {
                if (k < max) p[k] = MP_DIGIT_BIT * i + j;
                k++;
            }
            mask >>= 1;
        }
    }

    return k;
}
mp_err mp_bsqrmod ( const mp_int a,
const unsigned int  p[],
mp_int r 
)

Definition at line 442 of file mp_gf2m.c.

{
    mp_digit *pa, *pr, a_i;
    mp_int tmp;
    mp_size ia, a_used;
    mp_err res;

    ARGCHK(a != NULL && r != NULL, MP_BADARG);
    MP_DIGITS(&tmp) = 0;

    if (a == r) {
        MP_CHECKOK( mp_init_copy(&tmp, a) );
        a = &tmp;
    }

    MP_USED(r) = 1; MP_DIGIT(r, 0) = 0;
    MP_CHECKOK( s_mp_pad(r, 2*USED(a)) );

    pa = MP_DIGITS(a);
    pr = MP_DIGITS(r);
    a_used = MP_USED(a);
       MP_USED(r) = 2 * a_used;

    for (ia = 0; ia < a_used; ia++) {
        a_i = *pa++;
        *pr++ = gf2m_SQR0(a_i);
        *pr++ = gf2m_SQR1(a_i);
    }

    MP_CHECKOK( mp_bmod(r, p, r) );
    s_mp_clamp(r);
    SIGN(r) = ZPOS;

CLEANUP:
    mp_clear(&tmp);
    return res;
}