From ee4d4642216dd04c84a360a5dd59c090e095114c Mon Sep 17 00:00:00 2001
From: Werner Koch <wk@gnupg.org>
Date: Wed, 20 Aug 2008 14:10:11 +0000
Subject: Implemented gcry_mpi_lshift. Reordered some code in mpi-bit.c

---
 mpi/mpi-bit.c | 100 +++++++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 68 insertions(+), 32 deletions(-)

(limited to 'mpi/mpi-bit.c')

diff --git a/mpi/mpi-bit.c b/mpi/mpi-bit.c
index 6899fcd0..326e9522 100644
--- a/mpi/mpi-bit.c
+++ b/mpi/mpi-bit.c
@@ -188,6 +188,29 @@ gcry_mpi_clear_bit( gcry_mpi_t a, unsigned int n )
 }
 
 
+/****************
+ * Shift A by COUNT limbs to the right
+ * This is used only within the MPI library
+ */
+void
+_gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count )
+{
+    mpi_ptr_t ap = a->d;
+    mpi_size_t n = a->nlimbs;
+    unsigned int i;
+
+    if( count >= n ) {
+	a->nlimbs = 0;
+	return;
+    }
+
+    for( i = 0; i < n - count; i++ )
+	ap[i] = ap[i+count];
+    ap[i] = 0;
+    a->nlimbs -= count;
+}
+
+
 /*
  * Shift A by N bits to the right.
  */
@@ -277,23 +300,23 @@ gcry_mpi_rshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
  * This is used only within the MPI library
  */
 void
-_gcry_mpi_lshift_limbs( gcry_mpi_t a, unsigned int count )
+_gcry_mpi_lshift_limbs (gcry_mpi_t a, unsigned int count)
 {
-    mpi_ptr_t ap;
-    int n = a->nlimbs;
-    int i;
+  mpi_ptr_t ap;
+  int n = a->nlimbs;
+  int i;
 
-    if( !count || !n )
-	return;
+  if (!count || !n)
+    return;
 
-    RESIZE_IF_NEEDED( a, n+count );
+  RESIZE_IF_NEEDED (a, n+count);
 
-    ap = a->d;
-    for( i = n-1; i >= 0; i-- )
-	ap[i+count] = ap[i];
-    for(i=0; i < count; i++ )
-	ap[i] = 0;
-    a->nlimbs += count;
+  ap = a->d;
+  for (i = n-1; i >= 0; i--)
+    ap[i+count] = ap[i];
+  for (i=0; i < count; i++ )
+    ap[i] = 0;
+  a->nlimbs += count;
 }
 
 
@@ -303,28 +326,41 @@ _gcry_mpi_lshift_limbs( gcry_mpi_t a, unsigned int count )
 void
 gcry_mpi_lshift ( gcry_mpi_t x, gcry_mpi_t a, unsigned int n )
 {
-  BUG (); /* Not yet implemented in 1.4.2rc1 but will be soon.  */
-}
+  unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
+  unsigned int nbits = (n%BITS_PER_MPI_LIMB);
 
+  if (x == a && !n)
+    return;  /* In-place shift with an amount of zero.  */
 
-/****************
- * Shift A by COUNT limbs to the right
- * This is used only within the MPI library
- */
-void
-_gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count )
-{
-    mpi_ptr_t ap = a->d;
-    mpi_size_t n = a->nlimbs;
-    unsigned int i;
+  if ( x != a )
+    {
+      /* Copy A to X.  */
+      unsigned int alimbs = a->nlimbs;
+      int asign  = a->sign;
+      mpi_ptr_t xp, ap;
+
+      RESIZE_IF_NEEDED (x, alimbs+nlimbs+1);
+      xp = x->d;
+      ap = a->d;
+      MPN_COPY (xp, ap, alimbs);
+      x->nlimbs = alimbs;
+      x->flags = a->flags;
+      x->sign = asign;
+    }
 
-    if( count >= n ) {
-	a->nlimbs = 0;
-	return;
+  if (nlimbs && !nbits)
+    {
+      /* Shift a full number of limbs.  */
+      _gcry_mpi_lshift_limbs (x, nlimbs);
+    }
+  else if (n)
+    {
+      /* We use a very dump approach: Shift left by the number of
+         limbs plus one and than fix it up by an rshift.  */
+      _gcry_mpi_lshift_limbs (x, nlimbs+1);
+      gcry_mpi_rshift (x, x, BITS_PER_MPI_LIMB - nbits);
     }
 
-    for( i = 0; i < n - count; i++ )
-	ap[i] = ap[i+count];
-    ap[i] = 0;
-    a->nlimbs -= count;
+  MPN_NORMALIZE (x->d, x->nlimbs);
 }
+
-- 
cgit v1.2.1