/*
* Burn the evidence, just in case.
*/
- memset(b, 0, sizeof(b[0]) * (b[0] + 1));
+ smemclr(b, sizeof(b[0]) * (b[0] + 1));
sfree(b);
}
static void internal_mul(const BignumInt *a, const BignumInt *b,
BignumInt *c, int len, BignumInt *scratch)
{
- int i, j;
- BignumDblInt t;
-
if (len > KARATSUBA_THRESHOLD) {
+ int i;
/*
* Karatsuba divide-and-conquer algorithm. Cut each input in
* copied over. */
scratch[0] = scratch[1] = scratch[midlen] = scratch[midlen+1] = 0;
- for (j = 0; j < toplen; j++) {
- scratch[midlen - toplen + j] = a[j]; /* a_1 */
- scratch[2*midlen - toplen + j] = b[j]; /* b_1 */
+ for (i = 0; i < toplen; i++) {
+ scratch[midlen - toplen + i] = a[i]; /* a_1 */
+ scratch[2*midlen - toplen + i] = b[i]; /* b_1 */
}
/* compute a_1 + a_0 */
* product to obtain the middle one.
*/
scratch[0] = scratch[1] = scratch[2] = scratch[3] = 0;
- for (j = 0; j < 2*toplen; j++)
- scratch[2*midlen - 2*toplen + j] = c[j];
+ for (i = 0; i < 2*toplen; i++)
+ scratch[2*midlen - 2*toplen + i] = c[i];
scratch[1] = internal_add(scratch+2, c + 2*toplen,
scratch+2, 2*botlen);
#ifdef KARA_DEBUG
carry = internal_add(c + 2*len - botlen - 2*midlen,
scratch + 2*midlen,
c + 2*len - botlen - 2*midlen, 2*midlen);
- j = 2*len - botlen - 2*midlen - 1;
+ i = 2*len - botlen - 2*midlen - 1;
while (carry) {
- assert(j >= 0);
- carry += c[j];
- c[j] = (BignumInt)carry;
+ assert(i >= 0);
+ carry += c[i];
+ c[i] = (BignumInt)carry;
carry >>= BIGNUM_INT_BITS;
- j--;
+ i--;
}
#ifdef KARA_DEBUG
printf("ab = 0x");
#endif
} else {
+ int i;
+ BignumInt carry;
+ BignumDblInt t;
+ const BignumInt *ap, *bp;
+ BignumInt *cp, *cps;
/*
* Multiply in the ordinary O(N^2) way.
*/
- for (j = 0; j < 2 * len; j++)
- c[j] = 0;
+ for (i = 0; i < 2 * len; i++)
+ c[i] = 0;
- for (i = len - 1; i >= 0; i--) {
- t = 0;
- for (j = len - 1; j >= 0; j--) {
- t += MUL_WORD(a[i], (BignumDblInt) b[j]);
- t += (BignumDblInt) c[i + j + 1];
- c[i + j + 1] = (BignumInt) t;
- t = t >> BIGNUM_INT_BITS;
+ for (cps = c + 2*len, ap = a + len; ap-- > a; cps--) {
+ carry = 0;
+ for (cp = cps, bp = b + len; cp--, bp-- > b ;) {
+ t = (MUL_WORD(*ap, *bp) + carry) + *cp;
+ *cp = (BignumInt) t;
+ carry = (BignumInt)(t >> BIGNUM_INT_BITS);
}
- c[i] = (BignumInt) t;
+ *cp = carry;
}
}
}
static void internal_mul_low(const BignumInt *a, const BignumInt *b,
BignumInt *c, int len, BignumInt *scratch)
{
- int i, j;
- BignumDblInt t;
-
if (len > KARATSUBA_THRESHOLD) {
+ int i;
/*
* Karatsuba-aware version of internal_mul_low. As before, we
scratch + 2*len);
/* Copy the bottom half of the big coefficient into place */
- for (j = 0; j < botlen; j++)
- c[toplen + j] = scratch[2*toplen + botlen + j];
+ for (i = 0; i < botlen; i++)
+ c[toplen + i] = scratch[2*toplen + botlen + i];
/* Add the two small coefficients, throwing away the returned carry */
internal_add(scratch, scratch + toplen, scratch, toplen);
c, toplen);
} else {
+ int i;
+ BignumInt carry;
+ BignumDblInt t;
+ const BignumInt *ap, *bp;
+ BignumInt *cp, *cps;
- for (j = 0; j < len; j++)
- c[j] = 0;
+ /*
+ * Multiply in the ordinary O(N^2) way.
+ */
- for (i = len - 1; i >= 0; i--) {
- t = 0;
- for (j = len - 1; j >= len - i - 1; j--) {
- t += MUL_WORD(a[i], (BignumDblInt) b[j]);
- t += (BignumDblInt) c[i + j + 1 - len];
- c[i + j + 1 - len] = (BignumInt) t;
- t = t >> BIGNUM_INT_BITS;
+ for (i = 0; i < len; i++)
+ c[i] = 0;
+
+ for (cps = c + len, ap = a + len; ap-- > a; cps--) {
+ carry = 0;
+ for (cp = cps, bp = b + len; bp--, cp-- > c ;) {
+ t = (MUL_WORD(*ap, *bp) + carry) + *cp;
+ *cp = (BignumInt) t;
+ carry = (BignumInt)(t >> BIGNUM_INT_BITS);
}
}
-
}
}
result[0]--;
/* Free temporary arrays */
- for (i = 0; i < 2 * mlen; i++)
- a[i] = 0;
+ smemclr(a, 2 * mlen * sizeof(*a));
sfree(a);
- for (i = 0; i < scratchlen; i++)
- scratch[i] = 0;
+ smemclr(scratch, scratchlen * sizeof(*scratch));
sfree(scratch);
- for (i = 0; i < 2 * mlen; i++)
- b[i] = 0;
+ smemclr(b, 2 * mlen * sizeof(*b));
sfree(b);
- for (i = 0; i < mlen; i++)
- m[i] = 0;
+ smemclr(m, mlen * sizeof(*m));
sfree(m);
- for (i = 0; i < mlen; i++)
- n[i] = 0;
+ smemclr(n, mlen * sizeof(*n));
sfree(n);
freebn(base);
mninv = snewn(len, BignumInt);
for (j = 0; j < len; j++)
- mninv[len - 1 - j] = (j < inv[0] ? inv[j + 1] : 0);
+ mninv[len - 1 - j] = (j < (int)inv[0] ? inv[j + 1] : 0);
freebn(inv); /* we don't need this copy of it any more */
/* Now negate mninv mod r, so it's the inverse of -n rather than +n. */
x = snewn(len, BignumInt);
/* x = snewn(len, BignumInt); */ /* already done above */
for (j = 0; j < len; j++)
- x[len - 1 - j] = (j < base[0] ? base[j + 1] : 0);
+ x[len - 1 - j] = (j < (int)base[0] ? base[j + 1] : 0);
freebn(base); /* we don't need this copy of it any more */
a = snewn(2*len, BignumInt);
b = snewn(2*len, BignumInt);
for (j = 0; j < len; j++)
- a[2*len - 1 - j] = (j < rn[0] ? rn[j + 1] : 0);
+ a[2*len - 1 - j] = (j < (int)rn[0] ? rn[j + 1] : 0);
freebn(rn);
/* Scratch space for multiplies */
result[0]--;
/* Free temporary arrays */
- for (i = 0; i < scratchlen; i++)
- scratch[i] = 0;
+ smemclr(scratch, scratchlen * sizeof(*scratch));
sfree(scratch);
- for (i = 0; i < 2 * len; i++)
- a[i] = 0;
+ smemclr(a, 2 * len * sizeof(*a));
sfree(a);
- for (i = 0; i < 2 * len; i++)
- b[i] = 0;
+ smemclr(b, 2 * len * sizeof(*b));
sfree(b);
- for (i = 0; i < len; i++)
- mninv[i] = 0;
+ smemclr(mninv, len * sizeof(*mninv));
sfree(mninv);
- for (i = 0; i < len; i++)
- n[i] = 0;
+ smemclr(n, len * sizeof(*n));
sfree(n);
- for (i = 0; i < len; i++)
- x[i] = 0;
+ smemclr(x, len * sizeof(*x));
sfree(x);
return result;
pqlen = (p[0] > q[0] ? p[0] : q[0]);
+ /*
+ * Make sure that we're allowing enough space. The shifting below
+ * will underflow the vectors we allocate if pqlen is too small.
+ */
+ if (2*pqlen <= mlen)
+ pqlen = mlen/2 + 1;
+
/* Allocate n of size pqlen, copy p to n */
n = snewn(pqlen, BignumInt);
i = pqlen - p[0];
result[0]--;
/* Free temporary arrays */
- for (i = 0; i < scratchlen; i++)
- scratch[i] = 0;
+ smemclr(scratch, scratchlen * sizeof(*scratch));
sfree(scratch);
- for (i = 0; i < 2 * pqlen; i++)
- a[i] = 0;
+ smemclr(a, 2 * pqlen * sizeof(*a));
sfree(a);
- for (i = 0; i < mlen; i++)
- m[i] = 0;
+ smemclr(m, mlen * sizeof(*m));
sfree(m);
- for (i = 0; i < pqlen; i++)
- n[i] = 0;
+ smemclr(n, pqlen * sizeof(*n));
sfree(n);
- for (i = 0; i < pqlen; i++)
- o[i] = 0;
+ smemclr(o, pqlen * sizeof(*o));
sfree(o);
return result;
}
/* Free temporary arrays */
- for (i = 0; i < mlen; i++)
- m[i] = 0;
+ smemclr(m, mlen * sizeof(*m));
sfree(m);
- for (i = 0; i < plen; i++)
- n[i] = 0;
+ smemclr(n, plen * sizeof(*n));
sfree(n);
}
}
ret[0] = maxspot;
- for (i = 0; i < wslen; i++)
- workspace[i] = 0;
+ smemclr(workspace, wslen * sizeof(*workspace));
sfree(workspace);
return ret;
}
/*
* Done.
*/
+ smemclr(workspace, x[0] * sizeof(*workspace));
sfree(workspace);
return ret;
}
#include <ctype.h>
/*
- * gcc -g -O0 -DTESTBN -o testbn sshbn.c misc.c -I unix -I charset
+ * gcc -Wall -g -O0 -DTESTBN -o testbn sshbn.c misc.c conf.c tree234.c unix/uxmisc.c -I. -I unix -I charset
*
* Then feed to this program's standard input the output of
* testdata/bignum.py .
Bignum a, b, c, p;
if (ptrnum != 3) {
- printf("%d: mul with %d parameters, expected 3\n", line);
+ printf("%d: mul with %d parameters, expected 3\n", line, ptrnum);
exit(1);
}
a = bignum_from_bytes(ptrs[0], ptrs[1]-ptrs[0]);
freebn(b);
freebn(c);
freebn(p);
+ } else if (!strcmp(buf, "modmul")) {
+ Bignum a, b, m, c, p;
+
+ if (ptrnum != 4) {
+ printf("%d: modmul with %d parameters, expected 4\n",
+ line, ptrnum);
+ exit(1);
+ }
+ a = bignum_from_bytes(ptrs[0], ptrs[1]-ptrs[0]);
+ b = bignum_from_bytes(ptrs[1], ptrs[2]-ptrs[1]);
+ m = bignum_from_bytes(ptrs[2], ptrs[3]-ptrs[2]);
+ c = bignum_from_bytes(ptrs[3], ptrs[4]-ptrs[3]);
+ p = modmul(a, b, m);
+
+ if (bignum_cmp(c, p) == 0) {
+ passes++;
+ } else {
+ char *as = bignum_decimal(a);
+ char *bs = bignum_decimal(b);
+ char *ms = bignum_decimal(m);
+ char *cs = bignum_decimal(c);
+ char *ps = bignum_decimal(p);
+
+ printf("%d: fail: %s * %s mod %s gave %s expected %s\n",
+ line, as, bs, ms, ps, cs);
+ fails++;
+
+ sfree(as);
+ sfree(bs);
+ sfree(ms);
+ sfree(cs);
+ sfree(ps);
+ }
+ freebn(a);
+ freebn(b);
+ freebn(m);
+ freebn(c);
+ freebn(p);
} else if (!strcmp(buf, "pow")) {
Bignum base, expt, modulus, expected, answer;
if (ptrnum != 4) {
- printf("%d: mul with %d parameters, expected 3\n", line);
+ printf("%d: mul with %d parameters, expected 4\n", line, ptrnum);
exit(1);
}
~mdw / sgt / putty / blobdiff