sshbn.c: New functions for left and right shifts of bignums.

Signed-off-by: Mark Wooding <mdw@distorted.org.uk>

diff --git a/ssh.h b/ssh.h
index 1ac4e5e..a61866d 100644 (file)
--- a/ssh.h
+++ b/ssh.h
@@ -452,6 +452,8 @@ unsigned short bignum_mod_short(Bignum number, unsigned short modulus);
 Bignum bignum_add_long(Bignum number, unsigned long addend);
 Bignum bigadd(Bignum a, Bignum b);
 Bignum bigsub(Bignum a, Bignum b);
+Bignum biglsl(Bignum x, int n);
+Bignum biglsr(Bignum x, int n);
 Bignum bigmul(Bignum a, Bignum b);
 Bignum bigmuladd(Bignum a, Bignum b, Bignum addend);
 Bignum bigdiv(Bignum a, Bignum b);

diff --git a/sshbn.c b/sshbn.c
index 7c6b13a..ed0f509 100644 (file)
--- a/sshbn.c
+++ b/sshbn.c
@@ -1385,6 +1385,106 @@ Bignum bigsub(Bignum a, Bignum b)
 }
 
 /*
+ * 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;
+
+    /* Eliminate some simple special cases. */
+    if (!n || !x[0]) return copybn(x);
+    else if (n < 0) return biglsr(x, -n);
+
+    /* Some initial setup. */
+    o = n/BIGNUM_INT_BITS;
+    n %= BIGNUM_INT_BITS;
+    d = newbn(x[0] + o + !!n);
+
+    /* Clear the low-significant words of d. */
+    for (i = 1; i <= o; i++) d[i] = 0;
+
+    if (!n) {
+        /* Easy case: we're shifting by a multiple of the word size, so we
+         * can just copy whole words.
+         */
+        for (i = 1; i <= x[0]; i++) d[o + i] = x[i];
+    } else {
+        /* Hard case: destination words can be a combination of two source
+         * words.
+         */
+
+        /* Take the low bits from the least significant source word. */
+        d[o + 1] = x[1] << n;
+
+        /* The intermediate words really are a combination of two source
+         * words.
+         */
+        for (i = 2; i <= x[0]; i++)
+            d[o + i] = (x[i] << n) | (x[i - 1] >> (BIGNUM_INT_BITS - n));
+
+        /* Finally, the high bits of the most significant input word. */
+        d[o + i + 1] = x[i] >> (BIGNUM_INT_BITS - n);
+    }
+
+    /* The destination length is a conservative estimate, so we'll need to
+     * sort that out.
+     */
+    bn_restore_invariant(d);
+
+    /* We're done. */
+    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;
+
+    /* Eliminate some simple special cases. */
+    if (!n || !x[0]) return copybn(x);
+    else if (n < 0) return biglsl(x, -n);
+
+    /* Some initial setup. */
+    o = n/BIGNUM_INT_BITS;
+    n %= BIGNUM_INT_BITS;
+    d = newbn(x[0] - o);
+
+    if (!n) {
+        /* Simple case: we're shifting by a multiple of the word size, so we
+         * can just copy whole words across.
+         */
+        for (i = o + 1; i <= x[0]; i++) d[i - o] = x[i];
+    } else {
+        /* Hard case: some destination words will be a combination of two
+         * source words.  We get to discard some of the input words.
+         */
+
+        /* The intermediate words are combinations of two input words. */
+        for (i = o + 1; i < x[0]; i++)
+            d[i - o] = (x[i] >> n) | (x[i + 1] << (BIGNUM_INT_BITS - n));
+
+        /* And finally the high-significance bits of the top source word. */
+        d[i - o + 1] = x[i] << (BIGNUM_INT_BITS - n);
+    }
+
+    /* The destination length is a conservative estimate, so we'll need to
+     * sort that out.
+     */
+    bn_restore_invariant(d);
+
+    /* And we're done. */
+    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.