Index: mpi-1.8.6/mpi.c =================================================================== --- mpi-1.8.6.orig/mpi.c 2012-09-16 10:50:08.270639006 -0700 +++ mpi-1.8.6/mpi.c 2012-09-17 07:33:38.563334756 -0700 @@ -16,6 +16,9 @@ #include #include +#define MAX(A, B) ((A) > (B) ? (A) : (B)) +#define MIN(A, B) ((A) < (B) ? (A) : (B)) + typedef unsigned char mem_t; extern mem_t *chk_malloc(size_t size); extern mem_t *chk_calloc(size_t n, size_t size); @@ -159,6 +162,7 @@ mp_err s_mp_grow(mp_int *mp, mp_size min); /* increase allocated size */ mp_err s_mp_pad(mp_int *mp, mp_size min); /* left pad with zeroes */ +static int s_highest_bit(mp_digit n); int s_highest_bit_mp(mp_int *a); mp_err s_mp_set_bit(mp_int *a, int bit); @@ -2330,6 +2334,414 @@ /* }}} */ +/* + * Convert a's bit vector to its two's complement, up to the + * number of words that it contains, storing result in b. The numeric value of + * this result depends on the size of mpi_digit. This is a building block for + * handling negative operands in the bit operations. + */ +mp_err mp_2comp(mp_int *a, mp_int *b, mp_size dig) +{ + mp_err res; + mp_size ix, adig = USED(a); + mp_digit *pa, *pb; + mp_digit padding = ISNEG(a) ? MP_DIGIT_MAX : 0; + mp_word w; + + ARGCHK(a != NULL && b != NULL, MP_BADARG); + + if (a != b) { + if ((res = mp_init_size(b, dig)) != MP_OKAY) + return res; + SIGN(b) = SIGN(a); + } else { + if((res = s_mp_pad(b, dig)) != MP_OKAY) + return res; + } + + for (pa = DIGITS(a), pb = DIGITS(b), w = 0, ix = 0; ix < dig; ix++) { + w += (ix == 0); + w += (ix < adig) ? ~pa[ix] : ~padding; + pb[ix] = ACCUM(w); + w = CARRYOUT(w); + } + + USED(b) = dig; + + return MP_OKAY; +} + +mp_err mp_and(mp_int *a, mp_int *b, mp_int *c) +{ + mp_err res; + mp_size ix, extent = 0; + mp_digit *pa, *pb, *pc; + mp_int tmp_a, tmp_b; + + ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG); + + if (a == b) + return mp_copy(a, c); + + if (ISNEG(a)) { + mp_init_size(&tmp_a, extent); + extent = USED(b); + if ((res = mp_2comp(a, &tmp_a, extent)) != MP_OKAY) + return res; + a = &tmp_a; + } + + if (ISNEG(b)) { + mp_init_size(&tmp_b, extent); + extent = USED(a); + if ((res = mp_2comp(b, &tmp_b, extent)) != MP_OKAY) { + if (ISNEG(a)) + mp_clear(&tmp_a); + return res; + } + b = &tmp_b; + } + + if (!extent) + extent = MIN(USED(a), USED(b)); + + if (c != a && c != b) { + if ((res = mp_init_size(c, extent)) != MP_OKAY) + return res; + } + + for (pa = DIGITS(a), pb = DIGITS(b), pc = DIGITS(c), ix = 0; + ix < extent; ix++) + { + pc[ix] = pa[ix] & pb[ix]; + } + + USED(c) = extent; + + if (ISNEG(a) && ISNEG(b)) { + mp_2comp(c, c, extent); + SIGN(c) = MP_NEG; + } + + s_mp_clamp(c); + + if (ISNEG(a)) + mp_clear(&tmp_a); + + if (ISNEG(b)) + mp_clear(&tmp_b); + + return MP_OKAY; +} + +mp_err mp_or(mp_int *a, mp_int *b, mp_int *c) +{ + mp_err res; + mp_size ix, extent = 0; + mp_digit *pa, *pb, *pc; + mp_int tmp_a, tmp_b; + + ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG); + + extent = MAX(USED(a), USED(b)); + + if (a == b) + return mp_copy(a, c); + + if (ISNEG(a)) { + mp_init_size(&tmp_a, extent); + if ((res = mp_2comp(a, &tmp_a, extent)) != MP_OKAY) + return res; + a = &tmp_a; + } + + if (ISNEG(b)) { + mp_init_size(&tmp_b, extent); + if ((res = mp_2comp(b, &tmp_b, extent)) != MP_OKAY) { + if (ISNEG(a)) + mp_clear(&tmp_a); + return res; + } + b = &tmp_b; + } + + + if (c != a && c != b) + res = mp_init_size(c, extent); + else + res = s_mp_pad(c, extent); + + if (res != MP_OKAY) + return res; + + for (pa = DIGITS(a), pb = DIGITS(b), pc = DIGITS(c), ix = 0; + ix < extent; ix++) + { + pc[ix] = pa[ix] | pb[ix]; + } + + USED(c) = extent; + + if (ISNEG(a) || ISNEG(b)) { + mp_2comp(c, c, extent); + SIGN(c) = MP_NEG; + } + + s_mp_clamp(c); + + if (ISNEG(a)) + mp_clear(&tmp_a); + + if (ISNEG(b)) + mp_clear(&tmp_b); + + return MP_OKAY; +} + +mp_err mp_xor(mp_int *a, mp_int *b, mp_int *c) +{ + mp_err res; + mp_size ix, extent = 0; + mp_digit *pa, *pb, *pc; + mp_int tmp_a, tmp_b; + + ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG); + + if (a == b) { + mp_zero(c); + return MP_OKAY; + } + + extent = MAX(USED(a), USED(b)); + + if (ISNEG(a)) { + mp_init_size(&tmp_a, extent); + if ((res = mp_2comp(a, &tmp_a, extent)) != MP_OKAY) + return res; + a = &tmp_a; + } + + if (ISNEG(b)) { + mp_init_size(&tmp_b, extent); + if ((res = mp_2comp(b, &tmp_b, extent)) != MP_OKAY) { + if (ISNEG(a)) + mp_clear(&tmp_a); + return res; + } + b = &tmp_b; + } + + + if (c != a && c != b) + res = mp_init_size(c, extent); + else + res = s_mp_pad(c, extent); + + if (res != MP_OKAY) + return res; + + for (pa = DIGITS(a), pb = DIGITS(b), pc = DIGITS(c), ix = 0; + ix < extent; ix++) + { + pc[ix] = pa[ix] ^ pb[ix]; + } + + USED(c) = extent; + + if (ISNEG(a) ^ ISNEG(b)) { + mp_2comp(c, c, extent); + SIGN(c) = MP_NEG; + } + + s_mp_clamp(c); + + if (ISNEG(a)) + mp_clear(&tmp_a); + + if (ISNEG(b)) + mp_clear(&tmp_b); + + return MP_OKAY; +} + +mp_err mp_comp(mp_int *a, mp_int *b) +{ + mp_err res; + mp_size ix, dig = USED(a); + mp_digit *pa, *pb; + mp_int tmp; + + ARGCHK(a != NULL && b != NULL, MP_BADARG); + + if (a != b) + res = mp_init_size(b, dig); + else + res = s_mp_pad(b, dig); + + if (res != MP_OKAY) + return res; + + if (ISNEG(a)) { + mp_init_size(&tmp, dig); + if ((res = mp_2comp(a, &tmp, dig)) != MP_OKAY) + return res; + a = &tmp; + } + + for (pa = DIGITS(a), pb = DIGITS(b), ix = 0; ix < dig; ix++) + pb[ix] = ~pa[ix]; + + USED(b) = dig; + + if (ISNEG(a)) { + mp_clear(&tmp); + } else { + if ((res = mp_2comp(b, b, dig)) != MP_OKAY) + return res; + SIGN(b) = MP_NEG; + } + + s_mp_clamp(b); + return MP_OKAY; +} + +mp_err mp_trunc_comp(mp_int *a, mp_int *b, mp_digit bits) +{ + mp_err res; + mp_size ix, dig = bits / DIGIT_BIT, rembits = bits % DIGIT_BIT; + mp_size adig = USED(a); + mp_digit padding = ISNEG(a) ? MP_DIGIT_MAX : 0; + int extra = (rembits != 0); + mp_digit *pa, *pb; + mp_int tmp; + + ARGCHK(a != NULL && b != NULL, MP_BADARG); + + if (a != b) + res = mp_init_size(b, dig + extra); + else + res = s_mp_pad(b, dig + extra); + + if (res != MP_OKAY) + return res; + + if (ISNEG(a)) { + mp_init_size(&tmp, dig + extra); + if ((res = mp_2comp(a, &tmp, dig + extra)) != MP_OKAY) + return res; + a = &tmp; + } + + for (pa = DIGITS(a), pb = DIGITS(b), ix = 0; ix < dig; ix++) + pb[ix] = (ix < adig) ? ~pa[ix] : ~padding; + + if (rembits) { + mp_digit mask = (MP_DIGIT_MAX >> (DIGIT_BIT - rembits)); + pb[ix] = (((ix < adig) ? pa[ix] : padding) & mask) ^ mask; + } + + USED(b) = dig + extra; + + if (ISNEG(a)) + mp_clear(&tmp); + + s_mp_clamp(b); + return MP_OKAY; +} + +mp_err mp_trunc(mp_int *a, mp_int *b, mp_digit bits) +{ + mp_err res; + mp_size ix, dig = bits / DIGIT_BIT, rembits = bits % DIGIT_BIT; + mp_size adig = USED(a); + mp_digit padding = ISNEG(a) ? MP_DIGIT_MAX : 0; + int extra = (rembits != 0); + mp_digit *pa, *pb; + mp_int tmp; + + ARGCHK(a != NULL && b != NULL, MP_BADARG); + + if (a != b) + res = mp_init_size(b, dig + extra); + else + res = s_mp_pad(b, dig + extra); + + if (res != MP_OKAY) + return res; + + if (ISNEG(a)) { + mp_init_size(&tmp, dig + extra); + if ((res = mp_2comp(a, &tmp, dig + extra)) != MP_OKAY) + return res; + a = &tmp; + } + + for (pa = DIGITS(a), pb = DIGITS(b), ix = 0; ix < dig; ix++) + pb[ix] = (ix < adig) ? pa[ix] : padding; + + if (rembits) { + mp_digit mask = (MP_DIGIT_MAX >> (DIGIT_BIT - rembits)); + pb[ix] = ((ix < adig) ? pa[ix] : padding) & mask; + } + + USED(b) = dig + extra; + + if (ISNEG(a)) + mp_clear(&tmp); + + s_mp_clamp(b); + return MP_OKAY; +} + +mp_err mp_shift(mp_int *a, mp_int *b, int bits) +{ + mp_int tmp; + mp_err res; + int a_neg = ISNEG(a); + + if (bits == 0) + return mp_copy(a, b); + + if (a_neg) { + mp_size ua = USED(a); + mp_init_size(&tmp, ua); + if ((res = mp_2comp(a, &tmp, ua)) != MP_OKAY) + return res; + SIGN(&tmp) = MP_ZPOS; + a = &tmp; + } + + if (bits > 0) + res = mp_mul_2d(a, bits, b); + else + res = mp_div_2d(a, -bits, b, NULL); + + if (res != MP_OKAY) + return res; + + if (a_neg) { + int hb, msd; + mp_digit *db; + + mp_clear(&tmp); + + msd = USED(b)-1; + db = DIGITS(b); + hb = s_highest_bit(db[msd]); + + if (hb < DIGIT_BIT) + db[msd] |= MP_DIGIT_MAX << hb; + + if ((res = mp_2comp(b, b, USED(b))) != MP_OKAY) + return res; + + SIGN(b) = MP_NEG; + s_mp_clamp(b); + } + + return MP_OKAY; +} + mp_err mp_to_double(mp_int *mp, double *d) { int ix; Index: mpi-1.8.6/mpi.h =================================================================== --- mpi-1.8.6.orig/mpi.h 2012-09-16 10:50:08.046513006 -0700 +++ mpi-1.8.6/mpi.h 2012-09-17 07:32:54.738697256 -0700 @@ -54,6 +54,7 @@ /* Macros for accessing the mp_int internals */ #define SIGN(MP) ((MP)->sign) +#define ISNEG(MP) ((MP)->sign == MP_NEG) #define USED(MP) ((MP)->used) #define ALLOC(MP) ((MP)->alloc) #define DIGITS(MP) ((MP)->dp) @@ -187,6 +188,17 @@ #endif /* end MP_NUMTH */ /*------------------------------------------------------------------------*/ +/* Bit ops */ +mp_err mp_2comp(mp_int *a, mp_int *b, mp_size dig); /* peculiar semantics */ +mp_err mp_and(mp_int *a, mp_int *b, mp_int *c); +mp_err mp_or(mp_int *a, mp_int *b, mp_int *c); +mp_err mp_xor(mp_int *a, mp_int *b, mp_int *c); +mp_err mp_comp(mp_int *a, mp_int *b); +mp_err mp_trunc_comp(mp_int *a, mp_int *b, mp_digit bits); +mp_err mp_trunc(mp_int *a, mp_int *b, mp_digit bits); +mp_err mp_shift(mp_int *a, mp_int *b, int bits); /* + left, - right */ + +/*------------------------------------------------------------------------*/ /* Conversions */ mp_err mp_to_double(mp_int *mp, double *d);