#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;
-#define BIGNUM_INT_MASK 0xFFFFFFFFUL
-#define BIGNUM_TOP_BIT 0x80000000UL
-#define BIGNUM_INT_BITS 32
-#define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)
-#define DIVMOD_WORD(q, r, hi, lo, w) \
- __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)
-#elif defined _LP64
-/* 64-bit architectures can do 32x32->64 chunks at a time */
-typedef unsigned int BignumInt;
-typedef unsigned long BignumDblInt;
-#define BIGNUM_INT_MASK 0xFFFFFFFFU
-#define BIGNUM_TOP_BIT 0x80000000U
-#define BIGNUM_INT_BITS 32
-#define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)
-#define DIVMOD_WORD(q, r, hi, lo, w) do { \
- BignumDblInt n = (((BignumDblInt)hi) << BIGNUM_INT_BITS) | lo; \
- q = n / w; \
- r = n % w; \
-} while (0)
-#elif defined _LLP64
-/* 64-bit architectures in which unsigned long is 32 bits, not 64 */
-typedef unsigned long BignumInt;
-typedef unsigned long long BignumDblInt;
-#define BIGNUM_INT_MASK 0xFFFFFFFFUL
-#define BIGNUM_TOP_BIT 0x80000000UL
-#define BIGNUM_INT_BITS 32
-#define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)
-#define DIVMOD_WORD(q, r, hi, lo, w) do { \
- BignumDblInt n = (((BignumDblInt)hi) << BIGNUM_INT_BITS) | lo; \
- q = n / w; \
- r = n % w; \
-} while (0)
-#else
-/* Fallback for all other cases */
-typedef unsigned short BignumInt;
-typedef unsigned long BignumDblInt;
-#define BIGNUM_INT_MASK 0xFFFFU
-#define BIGNUM_TOP_BIT 0x8000U
-#define BIGNUM_INT_BITS 16
-#define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)
-#define DIVMOD_WORD(q, r, hi, lo, w) do { \
- BignumDblInt n = (((BignumDblInt)hi) << BIGNUM_INT_BITS) | lo; \
- q = n / w; \
- r = n % w; \
-} while (0)
-#endif
-
-#define BIGNUM_INT_BYTES (BIGNUM_INT_BITS / 8)
-
-#define BIGNUM_INTERNAL
-typedef BignumInt *Bignum;
-
+#include "bn-internal.h"
#include "ssh.h"
BignumInt bnZero[1] = { 0 };
}
/*
+ * Return a bignum which is the result of shifting another left by N bits.
+ * If N is negative then you get a right shift instead.
+ */
+Bignum biglsl(Bignum x, int n)
+{
+ Bignum d;
+ unsigned o, i;
+
+ if (!n || !x[0])
+ return copybn(x);
+ else if (n < 0)
+ return biglsr(x, -n);
+
+ o = n/BIGNUM_INT_BITS;
+ n %= BIGNUM_INT_BITS;
+ d = newbn(x[0] + o + !!n);
+
+ for (i = 1; i <= o; i++)
+ d[i] = 0;
+
+ if (!n) {
+ for (i = 1; i <= x[0]; i++)
+ d[o + i] = x[i];
+ } else {
+ d[o + 1] = x[1] << n;
+ for (i = 2; i <= x[0]; i--)
+ d[o + i] = (x[i] << n) | (x[i - 1] >> (BIGNUM_INT_BITS - n));
+ d[o + x[0] + 1] = x[x[0]] >> (BIGNUM_INT_BITS - n);
+ }
+
+ bn_restore_invariant(d);
+ return d;
+}
+
+/*
+ * Return a bignum which is the result of shifting another right by N bits
+ * (discarding the least significant N bits, and shifting zeroes in at the
+ * most significant end). If N is negative then you get a left shift
+ * instead.
+ */
+Bignum biglsr(Bignum x, int n)
+{
+ Bignum d;
+ unsigned o, i;
+
+ if (!n || !x[0])
+ return copybn(x);
+ else if (n < 0)
+ return biglsl(x, -n);
+
+ o = n/BIGNUM_INT_BITS;
+ n %= BIGNUM_INT_BITS;
+ d = newbn(x[0]);
+
+ if (!n) {
+ for (i = o + 1; i <= x[0]; i++)
+ d[i - o] = x[i];
+ } else {
+ d[1] = x[o + 1] >> n;
+ for (i = o + 2; i < x[0]; i++)
+ d[i - o] = x[
+ d[o + x[0] + 1] = x[x[0]] >> (BIGNUM_INT_BITS - n);
+ for (i = x[0]; i > 1; i--)
+ d[o + i] = (x[i] << n) | (x[i - 1] >> (BIGNUM_INT_BITS - n));
+ d[o + 1] = x[1] << n;
+ }
+
+ bn_restore_invariant(d);
+ return d;
+}
+
+/*
* Create a bignum which is the bitmask covering another one. That
* is, the smallest integer which is >= N and is also one less than
* a power of two.
projects / u / mdw / putty / blobdiff