Index: mpi-1.8.6/mpi.c
===================================================================
--- mpi-1.8.6.orig/mpi.c 2014-02-19 19:01:39.562347737 -0800
+++ mpi-1.8.6/mpi.c 2014-02-19 19:01:43.174297255 -0800
@@ -16,6 +16,9 @@
#include <ctype.h>
#include <math.h>
+#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);
@@ -2336,6 +2340,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 2014-02-19 19:01:29.302491325 -0800
+++ mpi-1.8.6/mpi.h 2014-02-19 19:01:43.178297199 -0800
@@ -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);