Implemented gcry_mpi_lshift.
authorWerner Koch <wk@gnupg.org>
Wed, 20 Aug 2008 14:10:11 +0000 (14:10 +0000)
committerWerner Koch <wk@gnupg.org>
Wed, 20 Aug 2008 14:10:11 +0000 (14:10 +0000)
Reordered some code in mpi-bit.c

NEWS
configure.ac
doc/gcrypt.texi
mpi/ChangeLog
mpi/mpi-bit.c
src/gcrypt.h.in
tests/ChangeLog
tests/t-mpi-bit.c

diff --git a/NEWS b/NEWS
index 518b5b1..bb5d05e 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -12,8 +12,7 @@ Noteworthy changes in version 1.4.2 (unreleased)
  * The thread initialization structure now carries version
    information.
 
- * The long missing gcry_mpi_lshift function has been added.  Note
-   that it is not yet working in 1.4.2rc1.
+ * The long missing gcry_mpi_lshift function has been added.
 
  * Interface changes relative to the 1.3.0 release:
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
index 561894a..e332ce2 100644 (file)
@@ -26,8 +26,8 @@ min_automake_version="1.10"
 # Remember to change the version number immediately *after* a release.
 # Set my_issvn to "yes" for non-released code.  Remember to run an
 # "svn up" and "autogen.sh" right before creating a distribution.
-m4_define([my_version], [1.4.2rc1])
-m4_define([my_issvn], [no])
+m4_define([my_version], [1.4.2])
+m4_define([my_issvn], [yes])
 
 m4_define([svn_revision], m4_esyscmd([echo -n $( (svn info 2>/dev/null \
             || echo 'Revision: 0')|sed -n '/^Revision:/ {s/[^0-9]//gp;q;}')]))
index 2cf4c93..7d2adee 100644 (file)
@@ -3700,8 +3700,9 @@ The constants for the random quality levels are of this type.
 
 @table @code
 @item GCRY_WEAK_RANDOM
-This should not anymore be used.  It has recently been changed to an
-alias of GCRY_STRONG_RANDOM.  Use @code{gcry_create_nonce} instead.
+For all functions, except for @code{gcry_mpi_randomize}, this level maps
+to GCRY_STRONG_RANDOM. IF you do not want this, consider using
+@code{gcry_create_nonce}.
 @item GCRY_STRONG_RANDOM
 Use this level for e.g. session keys and similar purposes.
 @item GCRY_VERY_STRONG_RANDOM
@@ -4368,7 +4369,9 @@ Return true when the @var{flag} is set for @var{a}.
 Set the multi-precision-integers @var{w} to a random value of
 @var{nbits}, using random data quality of level @var{level}.  In case
 @var{nbits} is not a multiple of a byte, @var{nbits} is rounded up to
-the next byte boundary.
+the next byte boundary.  When using a @var{level} of
+@code{GCRY_WEAK_RANDOM} this function makes use of
+@code{gcry_create_nonce}.
 @end deftypefun
 
 @c **********************************************************
index eb37add..8ed99e7 100644 (file)
@@ -1,3 +1,7 @@
+2008-08-20  Werner Koch  <wk@g10code.com>
+
+       * mpi-bit.c (gcry_mpi_lshift): Actually implement.
+
 2008-08-19  Werner Koch  <wk@g10code.com>
 
        * mpi-bit.c (gcry_mpi_lshift): New.
index 6899fcd..326e952 100644 (file)
@@ -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);
 }
+
index 5239a76..1bf8628 100644 (file)
@@ -1612,8 +1612,8 @@ gcry_error_t gcry_ac_name_to_id (const char *name,
 
 /* The possible values for the random quality.  The rule of thumb is
    to use STRONG for session keys and VERY_STRONG for key material.
-   WEAK is currently an alias for STRONG and should not be used
-   anymore - use gcry_create_nonce instead. */
+   WEAK is usually an alias for STRONG and should not be used anymore
+   (except with gcry_mpi_randomize); use gcry_create_nonce instead. */
 typedef enum gcry_random_level
   {
     GCRY_WEAK_RANDOM = 0,
@@ -1652,7 +1652,8 @@ void *gcry_random_bytes_secure (size_t nbytes, enum gcry_random_level level)
 
 
 /* Set the big integer W to a random value of NBITS using a random
-   generator with quality LEVEL. */
+   generator with quality LEVEL.  Note that using a level of
+   GCRY_WEAK_RANDOM here, uses gcry_create_nonce internally. */
 void gcry_mpi_randomize (gcry_mpi_t w,
                          unsigned int nbits, enum gcry_random_level level);
 
index 38e65f3..8817632 100644 (file)
@@ -1,3 +1,9 @@
+2008-08-20  Werner Koch  <wk@g10code.com>
+
+       * t-mpi-bit.c (test_lshift): New.
+       (mpi2bitstr_nlz, lshiftbitstring): New.
+       (main): Run test.
+
 2008-08-18  Werner Koch  <wk@g10code.com>
 
        * basic.c (main): Add option --fips.
index 2465a8f..208a127 100644 (file)
@@ -100,6 +100,24 @@ mpi2bitstr (gcry_mpi_t a, size_t length)
   return buf;
 }
 
+/* Allocate a bit string consisting of '0' and '1' from the MPI A.  Do
+   not return any leading zero bits. Caller needs to xfree the
+   result. */
+static char *
+mpi2bitstr_nlz (gcry_mpi_t a)
+{
+  char *p, *buf;
+  size_t length = gcry_mpi_get_nbits (a);
+  
+  buf = p = xmalloc (length + 1);
+  while (length-- > 1)
+    *p++ = gcry_mpi_test_bit (a, length) ? '1':'0';
+  *p++ = gcry_mpi_test_bit (a, 0) ? '1':'0';
+  *p = 0;
+
+  return buf;
+}
+
 /* Shift a bit string to the right. */
 static void
 rshiftbitstring (char *string, size_t n)
@@ -113,6 +131,28 @@ rshiftbitstring (char *string, size_t n)
   memset (string, '0', n);
 }
 
+/* Shift a bit string to the left. Caller needs to free the result. */
+static char *
+lshiftbitstring (const char *string, size_t n)
+{
+  size_t len = strlen (string);
+  char *result;
+
+  if (len+n+1 < len)
+    die ("internal overflow\n");
+  /* Allocate enough space. */ 
+  result = xmalloc (len+n+1);
+  for (; *string == '0' && string[1]; string++, len--)
+    ;
+  memcpy (result, string, len);
+  if (*string == '0' && !string[1])
+    n = 0; /* Avoid extra nulls for an only 0 string.  */
+  else
+    memset (result+len, '0', n);
+  result[len+n] = 0;
+  return result;
+}
+
 
 /* This is to check a bug reported by bpgcrypt at itaparica.org on
    2006-07-31 against libgcrypt 1.2.2.  */
@@ -141,7 +181,6 @@ one_bit_only (int highbit)
     fail ("failed to clear a bit\n");
   result = mpi2bitstr (a, 70);
   assert (strlen (result) == 70);
-  show ("r=%s\n", result);
   for (i=0; result[i]; i++)
     if ( result[i] != '0' )
       break;
@@ -210,6 +249,76 @@ test_rshift (int pass)
   gcry_mpi_release (a);
 }
 
+/* Check that the left shifting.  */
+static void
+test_lshift (int pass)
+{
+  static int size_list[] = {1, 31, 32, 63, 64, 65, 70, 0};
+  int size_idx;
+  gcry_mpi_t a, b;
+  char *tmpstr, *result, *result2;
+  int i;
+
+  wherestr = "test_lshift";
+  show ("checking that lshift works as expected (pass %d)\n", pass);
+
+  for (size_idx=0; size_list[size_idx]; size_idx++)
+    {
+      a = gcry_mpi_new (0);
+      b = gcry_mpi_new (0);
+
+      /* gcry_mpi_randomize rounds up to full bytes, thus we need to
+         use gcry_mpi_clear_highbit to fix that.  */
+      gcry_mpi_randomize (a, size_list[size_idx], GCRY_WEAK_RANDOM);
+      gcry_mpi_clear_highbit (a, size_list[size_idx]);
+
+      for (i=0; i < 75; i++)
+        {
+          gcry_mpi_lshift (b, a, i);
+          
+          result = mpi2bitstr_nlz (b);
+          tmpstr = mpi2bitstr_nlz (a);
+          result2 = lshiftbitstring (tmpstr, i);
+          xfree (tmpstr);
+          if (strcmp (result, result2))
+            {
+              show ("got =%s\n", result);
+              show ("want=%s\n", result2);
+              fail ("lshift by %d failed\n", i);
+            }
+          xfree (result);
+          xfree (result2);
+        }
+      
+      /* Again. This time using in-place operation. */
+      gcry_mpi_randomize (a, size_list[size_idx], GCRY_WEAK_RANDOM);
+      gcry_mpi_clear_highbit (a, size_list[size_idx]);
+      
+      for (i=0; i < 75; i++)
+        {
+          gcry_mpi_release (b);
+          b = gcry_mpi_copy (a);
+          gcry_mpi_lshift (b, b, i);
+
+          result = mpi2bitstr_nlz (b);
+          tmpstr = mpi2bitstr_nlz (a);
+          result2 = lshiftbitstring (tmpstr, i);
+          xfree (tmpstr);
+          if (strcmp (result, result2))
+            {
+              show ("got =%s\n", result);
+              show ("want=%s\n", result2);
+              fail ("in-place lshift by %d failed\n", i);
+            }
+          xfree (result2);
+          xfree (result);
+        }
+
+      gcry_mpi_release (b);
+      gcry_mpi_release (a);
+    }
+}
+
 
 int
 main (int argc, char **argv)
@@ -226,15 +335,19 @@ main (int argc, char **argv)
     die ("version mismatch\n");
 
   gcry_control (GCRYCTL_DISABLE_SECMEM, 0);
-  gcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0);
+  gcry_control (GCRYCTL_ENABLE_QUICK_RANDOM, 0);
   if (debug)
     gcry_control (GCRYCTL_SET_DEBUG_FLAGS, 1u, 0);
-  gcry_control (GCRYCTL_ENABLE_QUICK_RANDOM, 0);
+
+  gcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0);
 
   one_bit_only (0);
   one_bit_only (1);
   for (i=0; i < 5; i++)
     test_rshift (i); /* Run several times due to random initializations. */
+
+  for (i=0; i < 5; i++)
+    test_lshift (i); /* Run several times due to random initializations. */
   
   show ("All tests completed. Errors: %d\n", error_count);
   return error_count ? 1 : 0;