*/
#include <stdio.h>
+#include <assert.h>
#include <stdlib.h>
#include <string.h>
__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)
+typedef struct {
+ unsigned __int32 quot;
+ unsigned __int32 remd;
+} msvc_quorem;
+static __declspec(naked) msvc_quorem __stdcall msvc_divmod(
+ unsigned __int32 hi,
+ unsigned __int32 lo,
+ unsigned __int32 w)
+{
+ __asm {
+ mov edx, dword ptr [esp+4]
+ mov eax, dword ptr [esp+8]
+ div dword ptr [esp+12]
+ ret 12
+ };
+}
+#define DIVMOD_WORD(q, r, hi, lo, w) do { \
+ const msvc_quorem qr = msvc_divmod((hi), (lo), (w)); \
+ (q) = qr.quot; (r) = qr.remd; \
+} 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 {
+ 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--;
+ }
}
/* Subtract q * m from a[i...] */
/*
* 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 */
n[i] = 0;
sfree(n);
+ freebn(base);
+
return result;
}
}
/*
- * 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)
{
}
/*
- * 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)
projects / u / mdw / putty / blobdiff