*/
#include <stdio.h>
+#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "misc.h"
+/*
+ * Usage notes:
+ * * Do not call the DIVMOD_WORD macro with expressions such as array
+ * subscripts, as some implementations object to this (see below).
+ * * Note that none of the division methods below will cope if the
+ * quotient won't fit into BIGNUM_INT_BITS. Callers should be careful
+ * to avoid this case.
+ * If this condition occurs, in the case of the x86 DIV instruction,
+ * an overflow exception will occur, which (according to a correspondent)
+ * will manifest on Windows as something like
+ * 0xC0000095: Integer overflow
+ * The C variant won't give the right answer, either.
+ */
+
#if defined __GNUC__ && defined __i386__
typedef unsigned long BignumInt;
typedef unsigned long long BignumDblInt;
__asm__("div %2" : \
"=d" (r), "=a" (q) : \
"r" (w), "d" (hi), "a" (lo))
+#elif defined _MSC_VER && defined _M_IX86
+typedef unsigned __int32 BignumInt;
+typedef unsigned __int64 BignumDblInt;
+#define BIGNUM_INT_MASK 0xFFFFFFFFUL
+#define BIGNUM_TOP_BIT 0x80000000UL
+#define BIGNUM_INT_BITS 32
+#define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)
+/* Note: MASM interprets array subscripts in the macro arguments as
+ * assembler syntax, which gives the wrong answer. Don't supply them.
+ * <http://msdn2.microsoft.com/en-us/library/bf1dw62z.aspx> */
+#define DIVMOD_WORD(q, r, hi, lo, w) do { \
+ __asm mov edx, hi \
+ __asm mov eax, lo \
+ __asm div w \
+ __asm mov r, edx \
+ __asm mov q, eax \
+} while(0)
#else
typedef unsigned short BignumInt;
typedef unsigned long BignumDblInt;
int bshift = shift % BIGNUM_INT_BITS;
BignumDblInt addend;
- addend = n << bshift;
+ addend = (BignumDblInt)n << bshift;
while (addend) {
addend += number[word];
ai1 = a[i + 1];
/* Find q = h:a[i] / m0 */
- DIVMOD_WORD(q, r, h, a[i], m0);
-
- /* Refine our estimate of q by looking at
- h:a[i]:a[i+1] / m0:m1 */
- t = MUL_WORD(m1, q);
- if (t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) {
- q--;
- t -= m1;
- r = (r + m0) & BIGNUM_INT_MASK; /* overflow? */
- if (r >= (BignumDblInt) m0 &&
- t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) q--;
+ if (h >= m0) {
+ /*
+ * Special case.
+ *
+ * To illustrate it, suppose a BignumInt is 8 bits, and
+ * we are dividing (say) A1:23:45:67 by A1:B2:C3. Then
+ * our initial division will be 0xA123 / 0xA1, which
+ * will give a quotient of 0x100 and a divide overflow.
+ * However, the invariants in this division algorithm
+ * are not violated, since the full number A1:23:... is
+ * _less_ than the quotient prefix A1:B2:... and so the
+ * following correction loop would have sorted it out.
+ *
+ * In this situation we set q to be the largest
+ * quotient we _can_ stomach (0xFF, of course).
+ */
+ q = BIGNUM_INT_MASK;
+ } else {
+ /* Macro doesn't want an array subscript expression passed
+ * into it (see definition), so use a temporary. */
+ BignumInt tmplo = a[i];
+ DIVMOD_WORD(q, r, h, tmplo, m0);
+
+ /* Refine our estimate of q by looking at
+ h:a[i]:a[i+1] / m0:m1 */
+ t = MUL_WORD(m1, q);
+ if (t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) {
+ q--;
+ t -= m1;
+ r = (r + m0) & BIGNUM_INT_MASK; /* overflow? */
+ if (r >= (BignumDblInt) m0 &&
+ t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) q--;
+ }
}
/* Subtract q * m from a[i...] */
for (k = mlen - 1; k >= 0; k--) {
t = MUL_WORD(q, m[k]);
t += c;
- c = t >> BIGNUM_INT_BITS;
+ c = (unsigned)(t >> BIGNUM_INT_BITS);
if ((BignumInt) t > a[i + k])
c++;
a[i + k] -= (BignumInt) t;
/*
* Compute (base ^ exp) % mod.
- * The base MUST be smaller than the modulus.
- * The most significant word of mod MUST be non-zero.
- * We assume that the result array is the same size as the mod array.
*/
-Bignum modpow(Bignum base, Bignum exp, Bignum mod)
+Bignum modpow(Bignum base_in, Bignum exp, Bignum mod)
{
BignumInt *a, *b, *n, *m;
int mshift;
int mlen, i, j;
- Bignum result;
+ Bignum base, result;
+
+ /*
+ * The most significant word of mod needs to be non-zero. It
+ * should already be, but let's make sure.
+ */
+ assert(mod[mod[0]] != 0);
+
+ /*
+ * Make sure the base is smaller than the modulus, by reducing
+ * it modulo the modulus if not.
+ */
+ base = bigmod(base_in, mod);
/* Allocate m of size mlen, copy mod to m */
/* We use big endian internally */
i = mlen - base[0];
for (j = 0; j < i; j++)
n[j] = 0;
- for (j = 0; j < base[0]; j++)
+ for (j = 0; j < (int)base[0]; j++)
n[i + j] = base[base[0] - j];
/* Allocate a and b of size 2*mlen. Set a = 1 */
/* Skip leading zero bits of exp. */
i = 0;
j = BIGNUM_INT_BITS-1;
- while (i < exp[0] && (exp[exp[0] - i] & (1 << j)) == 0) {
+ while (i < (int)exp[0] && (exp[exp[0] - i] & (1 << j)) == 0) {
j--;
if (j < 0) {
i++;
}
/* Main computation */
- while (i < exp[0]) {
+ while (i < (int)exp[0]) {
while (j >= 0) {
internal_mul(a + mlen, a + mlen, b, mlen);
internal_mod(b, mlen * 2, m, mlen, NULL, 0);
n[i] = 0;
sfree(n);
+ freebn(base);
+
return result;
}
i = pqlen - p[0];
for (j = 0; j < i; j++)
n[j] = 0;
- for (j = 0; j < p[0]; j++)
+ for (j = 0; j < (int)p[0]; j++)
n[i + j] = p[p[0] - j];
/* Allocate o of size pqlen, copy q to o */
i = pqlen - q[0];
for (j = 0; j < i; j++)
o[j] = 0;
- for (j = 0; j < q[0]; j++)
+ for (j = 0; j < (int)q[0]; j++)
o[i + j] = q[q[0] - j];
/* Allocate a of size 2*pqlen for result */
n = snewn(plen, BignumInt);
for (j = 0; j < plen; j++)
n[j] = 0;
- for (j = 1; j <= p[0]; j++)
+ for (j = 1; j <= (int)p[0]; j++)
n[plen - j] = p[j];
/* Main computation */
/* Copy result to buffer */
if (result) {
- for (i = 1; i <= result[0]; i++) {
+ for (i = 1; i <= (int)result[0]; i++) {
int j = plen - i;
result[i] = j >= 0 ? n[j] : 0;
}
void decbn(Bignum bn)
{
int i = 1;
- while (i < bn[0] && bn[i] == 0)
+ while (i < (int)bn[0] && bn[i] == 0)
bn[i++] = BIGNUM_INT_MASK;
bn[i]--;
}
}
/*
- * Read an ssh1-format bignum from a data buffer. Return the number
- * of bytes consumed.
+ * Read an SSH-1-format bignum from a data buffer. Return the number
+ * of bytes consumed, or -1 if there wasn't enough data.
*/
-int ssh1_read_bignum(const unsigned char *data, Bignum * result)
+int ssh1_read_bignum(const unsigned char *data, int len, Bignum * result)
{
const unsigned char *p = data;
int i;
int w, b;
+ if (len < 2)
+ return -1;
+
w = 0;
for (i = 0; i < 2; i++)
w = (w << 8) + *p++;
b = (w + 7) / 8; /* bits -> bytes */
+ if (len < b+2)
+ return -1;
+
if (!result) /* just return length */
return b + 2;
}
/*
- * Return the bit count of a bignum, for ssh1 encoding.
+ * Return the bit count of a bignum, for SSH-1 encoding.
*/
int bignum_bitcount(Bignum bn)
{
}
/*
- * Return the byte length of a bignum when ssh1 encoded.
+ * Return the byte length of a bignum when SSH-1 encoded.
*/
int ssh1_bignum_length(Bignum bn)
{
}
/*
- * Return the byte length of a bignum when ssh2 encoded.
+ * Return the byte length of a bignum when SSH-2 encoded.
*/
int ssh2_bignum_length(Bignum bn)
{
*/
int bignum_byte(Bignum bn, int i)
{
- if (i >= BIGNUM_INT_BYTES * bn[0])
+ if (i >= (int)(BIGNUM_INT_BYTES * bn[0]))
return 0; /* beyond the end */
else
return (bn[i / BIGNUM_INT_BYTES + 1] >>
*/
int bignum_bit(Bignum bn, int i)
{
- if (i >= BIGNUM_INT_BITS * bn[0])
+ if (i >= (int)(BIGNUM_INT_BITS * bn[0]))
return 0; /* beyond the end */
else
return (bn[i / BIGNUM_INT_BITS + 1] >> (i % BIGNUM_INT_BITS)) & 1;
*/
void bignum_set_bit(Bignum bn, int bitnum, int value)
{
- if (bitnum >= BIGNUM_INT_BITS * bn[0])
+ if (bitnum >= (int)(BIGNUM_INT_BITS * bn[0]))
abort(); /* beyond the end */
else {
int v = bitnum / BIGNUM_INT_BITS + 1;
}
/*
- * Write a ssh1-format bignum into a buffer. It is assumed the
+ * Write a SSH-1-format bignum into a buffer. It is assumed the
* buffer is big enough. Returns the number of bytes used.
*/
int ssh1_write_bignum(void *data, Bignum bn)
shiftbb = BIGNUM_INT_BITS - shiftb;
ai1 = a[shiftw + 1];
- for (i = 1; i <= ret[0]; i++) {
+ for (i = 1; i <= (int)ret[0]; i++) {
ai = ai1;
- ai1 = (i + shiftw + 1 <= a[0] ? a[i + shiftw + 1] : 0);
+ ai1 = (i + shiftw + 1 <= (int)a[0] ? a[i + shiftw + 1] : 0);
ret[i] = ((ai >> shiftb) | (ai1 << shiftbb)) & BIGNUM_INT_MASK;
}
}
/* mlen space for a, mlen space for b, 2*mlen for result */
workspace = snewn(mlen * 4, BignumInt);
for (i = 0; i < mlen; i++) {
- workspace[0 * mlen + i] = (mlen - i <= a[0] ? a[mlen - i] : 0);
- workspace[1 * mlen + i] = (mlen - i <= b[0] ? b[mlen - i] : 0);
+ workspace[0 * mlen + i] = (mlen - i <= (int)a[0] ? a[mlen - i] : 0);
+ workspace[1 * mlen + i] = (mlen - i <= (int)b[0] ? b[mlen - i] : 0);
}
internal_mul(workspace + 0 * mlen, workspace + 1 * mlen,
/* now just copy the result back */
rlen = alen + blen + 1;
- if (addend && rlen <= addend[0])
+ if (addend && rlen <= (int)addend[0])
rlen = addend[0] + 1;
ret = newbn(rlen);
maxspot = 0;
- for (i = 1; i <= ret[0]; i++) {
+ for (i = 1; i <= (int)ret[0]; i++) {
ret[i] = (i <= 2 * mlen ? workspace[4 * mlen - i] : 0);
if (ret[i] != 0)
maxspot = i;
if (addend) {
BignumDblInt carry = 0;
for (i = 1; i <= rlen; i++) {
- carry += (i <= ret[0] ? ret[i] : 0);
- carry += (i <= addend[0] ? addend[i] : 0);
+ carry += (i <= (int)ret[0] ? ret[i] : 0);
+ carry += (i <= (int)addend[0] ? addend[i] : 0);
ret[i] = (BignumInt) carry & BIGNUM_INT_MASK;
carry >>= BIGNUM_INT_BITS;
if (ret[i] != 0 && i > maxspot)
int i, maxspot = 0;
BignumDblInt carry = 0, addend = addendx;
- for (i = 1; i <= ret[0]; i++) {
+ for (i = 1; i <= (int)ret[0]; i++) {
carry += addend & BIGNUM_INT_MASK;
- carry += (i <= number[0] ? number[i] : 0);
+ carry += (i <= (int)number[0] ? number[i] : 0);
addend >>= BIGNUM_INT_BITS;
ret[i] = (BignumInt) carry & BIGNUM_INT_MASK;
carry >>= BIGNUM_INT_BITS;
int maxspot = 1;
int i;
- for (i = 1; i <= newx[0]; i++) {
- BignumInt aword = (i <= modulus[0] ? modulus[i] : 0);
- BignumInt bword = (i <= x[0] ? x[i] : 0);
+ for (i = 1; i <= (int)newx[0]; i++) {
+ BignumInt aword = (i <= (int)modulus[0] ? modulus[i] : 0);
+ BignumInt bword = (i <= (int)x[0] ? x[i] : 0);
newx[i] = aword - bword - carry;
bword = ~bword;
carry = carry ? (newx[i] >= bword) : (newx[i] > bword);
* round up (rounding down might make it less than x again).
* Therefore if we multiply the bit count by 28/93, rounding
* up, we will have enough digits.
+ *
+ * i=0 (i.e., x=0) is an irritating special case.
*/
i = bignum_bitcount(x);
- ndigits = (28 * i + 92) / 93; /* multiply by 28/93 and round up */
+ if (!i)
+ ndigits = 1; /* x = 0 */
+ else
+ ndigits = (28 * i + 92) / 93; /* multiply by 28/93 and round up */
ndigits++; /* allow for trailing \0 */
ret = snewn(ndigits, char);
* big-endian form of the number.
*/
workspace = snewn(x[0], BignumInt);
- for (i = 0; i < x[0]; i++)
+ for (i = 0; i < (int)x[0]; i++)
workspace[i] = x[x[0] - i];
/*
do {
iszero = 1;
carry = 0;
- for (i = 0; i < x[0]; i++) {
+ for (i = 0; i < (int)x[0]; i++) {
carry = (carry << BIGNUM_INT_BITS) + workspace[i];
workspace[i] = (BignumInt) (carry / 10);
if (workspace[i])
projects / u / mdw / putty / blobdiff