LCOV - code coverage report
Current view: top level - tests - t-mpi-bit.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 157 209 75.1 %
Date: 2016-09-12 12:56:58 Functions: 10 12 83.3 %

          Line data    Source code
       1             : /* t-mpi-bit.c  - Tests for bit level functions
       2             :  * Copyright (C) 2006 Free Software Foundation, Inc.
       3             :  *
       4             :  * This file is part of Libgcrypt.
       5             :  *
       6             :  * Libgcrypt is free software; you can redistribute it and/or modify
       7             :  * it under the terms of the GNU Lesser General Public License as
       8             :  * published by the Free Software Foundation; either version 2.1 of
       9             :  * the License, or (at your option) any later version.
      10             :  *
      11             :  * Libgcrypt is distributed in the hope that it will be useful,
      12             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14             :  * GNU Lesser General Public License for more details.
      15             :  *
      16             :  * You should have received a copy of the GNU Lesser General Public
      17             :  * License along with this program; if not, write to the Free Software
      18             :  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
      19             :  * MA 02110-1301, USA.
      20             :  */
      21             : 
      22             : #ifdef HAVE_CONFIG_H
      23             : #include <config.h>
      24             : #endif
      25             : #include <stdio.h>
      26             : #include <stdlib.h>
      27             : #include <string.h>
      28             : #include <assert.h>
      29             : #include <stdarg.h>
      30             : 
      31             : #include "../src/gcrypt-int.h"
      32             : 
      33             : #define PGM "t-mpi-bit"
      34             : 
      35             : static const char *wherestr;
      36             : static int verbose;
      37             : static int error_count;
      38             : 
      39             : #define xmalloc(a)    gcry_xmalloc ((a))
      40             : #define xcalloc(a,b)  gcry_xcalloc ((a),(b))
      41             : #define xfree(a)      gcry_free ((a))
      42             : #define pass() do { ; } while (0)
      43             : 
      44             : static void
      45          15 : show (const char *format, ...)
      46             : {
      47             :   va_list arg_ptr;
      48             : 
      49          15 :   if (!verbose)
      50          30 :     return;
      51           0 :   fprintf (stderr, "%s: ", PGM);
      52           0 :   va_start (arg_ptr, format);
      53           0 :   vfprintf (stderr, format, arg_ptr);
      54           0 :   va_end (arg_ptr);
      55             : }
      56             : 
      57             : static void
      58           0 : fail (const char *format, ...)
      59             : {
      60             :   va_list arg_ptr;
      61             : 
      62           0 :   fflush (stdout);
      63           0 :   fprintf (stderr, "%s: ", PGM);
      64           0 :   if (wherestr)
      65           0 :     fprintf (stderr, "%s: ", wherestr);
      66           0 :   va_start (arg_ptr, format);
      67           0 :   vfprintf (stderr, format, arg_ptr);
      68           0 :   va_end (arg_ptr);
      69           0 :   error_count++;
      70           0 : }
      71             : 
      72             : static void
      73           0 : die (const char *format, ...)
      74             : {
      75             :   va_list arg_ptr;
      76             : 
      77           0 :   fflush (stdout);
      78           0 :   fprintf (stderr, "%s: ", PGM);
      79           0 :   if (wherestr)
      80           0 :     fprintf (stderr, "%s: ", wherestr);
      81           0 :   va_start (arg_ptr, format);
      82           0 :   vfprintf (stderr, format, arg_ptr);
      83           0 :   va_end (arg_ptr);
      84           0 :   exit (1);
      85             : }
      86             : 
      87             : /* Allocate a bit string consisting of '0' and '1' from the MPI
      88             :    A. Return the LENGTH least significant bits. Caller needs to xfree
      89             :    the result. */
      90             : static char *
      91        1502 : mpi2bitstr (gcry_mpi_t a, size_t length)
      92             : {
      93             :   char *p, *buf;
      94             : 
      95        1502 :   buf = p = xmalloc (length+1);
      96      111144 :   while (length--)
      97      108140 :     *p++ = gcry_mpi_test_bit (a, length) ? '1':'0';
      98        1502 :   *p = 0;
      99             : 
     100        1502 :   return buf;
     101             : }
     102             : 
     103             : /* Allocate a bit string consisting of '0' and '1' from the MPI A.  Do
     104             :    not return any leading zero bits. Caller needs to xfree the
     105             :    result. */
     106             : static char *
     107       10500 : mpi2bitstr_nlz (gcry_mpi_t a)
     108             : {
     109             :   char *p, *buf;
     110       10500 :   size_t length = gcry_mpi_get_nbits (a);
     111             : 
     112       10500 :   if (!length)
     113             :     {
     114         750 :       buf = p = xmalloc (2);
     115         750 :       *p++ = '0';
     116             :     }
     117             :   else
     118             :     {
     119        9750 :       buf = p = xmalloc (length + 1);
     120      669675 :       while (length-- > 1)
     121      650175 :         *p++ = gcry_mpi_test_bit (a, length) ? '1':'0';
     122        9750 :       *p++ = gcry_mpi_test_bit (a, 0) ? '1':'0';
     123             :     }
     124       10500 :   *p = 0;
     125       10500 :   return buf;
     126             : }
     127             : 
     128             : /* Shift a bit string to the right. */
     129             : static void
     130         750 : rshiftbitstring (char *string, size_t n)
     131             : {
     132         750 :   size_t len = strlen (string);
     133             : 
     134         750 :   if (n > len)
     135          20 :     n = len;
     136             : 
     137         750 :   memmove (string+n, string, len-n);
     138         750 :   memset (string, '0', n);
     139         750 : }
     140             : 
     141             : /* Shift a bit string to the left. Caller needs to free the result. */
     142             : static char *
     143        5250 : lshiftbitstring (const char *string, size_t n)
     144             : {
     145        5250 :   size_t len = strlen (string);
     146             :   char *result;
     147             : 
     148        5250 :   if (len+n+1 < len)
     149           0 :     die ("internal overflow\n");
     150             :   /* Allocate enough space. */
     151        5250 :   result = xmalloc (len+n+1);
     152        5250 :   for (; *string == '0' && string[1]; string++, len--)
     153             :     ;
     154        5250 :   memcpy (result, string, len);
     155        5250 :   if (*string == '0' && !string[1])
     156         375 :     n = 0; /* Avoid extra nulls for an only 0 string.  */
     157             :   else
     158        4875 :     memset (result+len, '0', n);
     159        5250 :   result[len+n] = 0;
     160        5250 :   return result;
     161             : }
     162             : 
     163             : 
     164             : /* This is to check a bug reported by bpgcrypt at itaparica.org on
     165             :    2006-07-31 against libgcrypt 1.2.2.  */
     166             : static void
     167           2 : one_bit_only (int highbit)
     168             : {
     169             :   gcry_mpi_t a;
     170             :   char *result;
     171             :   int i;
     172             : 
     173           2 :   wherestr = "one_bit_only";
     174           2 :   show ("checking that set_%sbit does only set one bit\n", highbit?"high":"");
     175             : 
     176           2 :   a = gcry_mpi_new (0);
     177           2 :   gcry_mpi_randomize (a, 70, GCRY_WEAK_RANDOM);
     178           2 :   gcry_mpi_set_ui (a, 0);
     179             : 
     180           2 :   if (highbit)
     181           1 :     gcry_mpi_set_highbit (a, 42);
     182             :   else
     183           1 :     gcry_mpi_set_bit (a, 42);
     184           2 :   if (!gcry_mpi_test_bit (a, 42))
     185           0 :     fail ("failed to set a bit\n");
     186           2 :   gcry_mpi_clear_bit (a, 42);
     187           2 :   if (gcry_mpi_test_bit (a, 42))
     188           0 :     fail ("failed to clear a bit\n");
     189           2 :   result = mpi2bitstr (a, 70);
     190           2 :   assert (strlen (result) == 70);
     191         142 :   for (i=0; result[i]; i++)
     192         140 :     if ( result[i] != '0' )
     193           0 :       break;
     194           2 :   if (result[i])
     195           0 :     fail ("spurious bits detected\n");
     196           2 :   xfree (result);
     197           2 :   gcry_mpi_release (a);
     198           2 : }
     199             : 
     200             : /* Check that right shifting actually works for an amount larger than
     201             :    the number of bits per limb. */
     202             : static void
     203           5 : test_rshift (int pass)
     204             : {
     205             :   gcry_mpi_t a, b;
     206             :   char *result, *result2;
     207             :   int i;
     208             : 
     209           5 :   wherestr = "test_rshift";
     210           5 :   show ("checking that rshift works as expected (pass %d)\n", pass);
     211             : 
     212           5 :   a = gcry_mpi_new (0);
     213           5 :   b = gcry_mpi_new (0);
     214           5 :   gcry_mpi_randomize (a, 70, GCRY_WEAK_RANDOM);
     215             : 
     216         380 :   for (i=0; i < 75; i++)
     217             :     {
     218         375 :       gcry_mpi_rshift (b, a, i);
     219             : 
     220         375 :       result = mpi2bitstr (b, 72);
     221         375 :       result2 = mpi2bitstr (a, 72);
     222         375 :       rshiftbitstring (result2, i);
     223         375 :       if (strcmp (result, result2))
     224             :         {
     225           0 :           show ("got =%s\n", result);
     226           0 :           show ("want=%s\n", result2);
     227           0 :           fail ("rshift by %d failed\n", i);
     228             :         }
     229         375 :       xfree (result);
     230         375 :       xfree (result2);
     231             :     }
     232             : 
     233             :   /* Again. This time using in-place operation. */
     234           5 :   gcry_mpi_randomize (a, 70, GCRY_WEAK_RANDOM);
     235             : 
     236         380 :   for (i=0; i < 75; i++)
     237             :     {
     238         375 :       gcry_mpi_release (b);
     239         375 :       b = gcry_mpi_copy (a);
     240         375 :       gcry_mpi_rshift (b, b, i);
     241             : 
     242         375 :       result = mpi2bitstr (b, 72);
     243         375 :       result2 = mpi2bitstr (a, 72);
     244         375 :       rshiftbitstring (result2, i);
     245         375 :       if (strcmp (result, result2))
     246             :         {
     247           0 :           show ("got =%s\n", result);
     248           0 :           show ("want=%s\n", result2);
     249           0 :           fail ("in-place rshift by %d failed\n", i);
     250             :         }
     251         375 :       xfree (result2);
     252         375 :       xfree (result);
     253             :     }
     254             : 
     255           5 :   gcry_mpi_release (b);
     256           5 :   gcry_mpi_release (a);
     257           5 : }
     258             : 
     259             : /* Check that left shifting works correctly.  */
     260             : static void
     261           5 : test_lshift (int pass)
     262             : {
     263             :   static int size_list[] = {1, 31, 32, 63, 64, 65, 70, 0};
     264             :   int size_idx;
     265             :   gcry_mpi_t a, b;
     266             :   char *tmpstr, *result, *result2;
     267             :   int i;
     268             : 
     269           5 :   wherestr = "test_lshift";
     270           5 :   show ("checking that lshift works as expected (pass %d)\n", pass);
     271             : 
     272          40 :   for (size_idx=0; size_list[size_idx]; size_idx++)
     273             :     {
     274          35 :       a = gcry_mpi_new (0);
     275          35 :       b = gcry_mpi_new (0);
     276             : 
     277             :       /* gcry_mpi_randomize rounds up to full bytes, thus we need to
     278             :          use gcry_mpi_clear_highbit to fix that.  */
     279          35 :       gcry_mpi_randomize (a, size_list[size_idx], GCRY_WEAK_RANDOM);
     280          35 :       gcry_mpi_clear_highbit (a, size_list[size_idx]);
     281             : 
     282        2660 :       for (i=0; i < 75; i++)
     283             :         {
     284        2625 :           gcry_mpi_lshift (b, a, i);
     285             : 
     286        2625 :           result = mpi2bitstr_nlz (b);
     287        2625 :           tmpstr = mpi2bitstr_nlz (a);
     288        2625 :           result2 = lshiftbitstring (tmpstr, i);
     289        2625 :           xfree (tmpstr);
     290        2625 :           if (strcmp (result, result2))
     291             :             {
     292           0 :               show ("got =%s\n", result);
     293           0 :               show ("want=%s\n", result2);
     294           0 :               fail ("lshift by %d failed\n", i);
     295             :             }
     296        2625 :           xfree (result);
     297        2625 :           xfree (result2);
     298             :         }
     299             : 
     300             :       /* Again. This time using in-place operation. */
     301          35 :       gcry_mpi_randomize (a, size_list[size_idx], GCRY_WEAK_RANDOM);
     302          35 :       gcry_mpi_clear_highbit (a, size_list[size_idx]);
     303             : 
     304        2660 :       for (i=0; i < 75; i++)
     305             :         {
     306        2625 :           gcry_mpi_release (b);
     307        2625 :           b = gcry_mpi_copy (a);
     308        2625 :           gcry_mpi_lshift (b, b, i);
     309             : 
     310        2625 :           result = mpi2bitstr_nlz (b);
     311        2625 :           tmpstr = mpi2bitstr_nlz (a);
     312        2625 :           result2 = lshiftbitstring (tmpstr, i);
     313        2625 :           xfree (tmpstr);
     314        2625 :           if (strcmp (result, result2))
     315             :             {
     316           0 :               show ("got =%s\n", result);
     317           0 :               show ("want=%s\n", result2);
     318           0 :               fail ("in-place lshift by %d failed\n", i);
     319             :             }
     320        2625 :           xfree (result2);
     321        2625 :           xfree (result);
     322             :         }
     323             : 
     324          35 :       gcry_mpi_release (b);
     325          35 :       gcry_mpi_release (a);
     326             :     }
     327           5 : }
     328             : 
     329             : 
     330             : /* Bug fixed on 2014-05-09:
     331             :       a = gcry_mpi_new (1523);
     332             :       gcry_mpi_set_bit (a, 1536);
     333             :       didn't initialized all limbs in A.  */
     334             : static void
     335           1 : set_bit_with_resize (void)
     336             : {
     337             :   gcry_mpi_t a;
     338             :   int i;
     339             : 
     340           1 :   wherestr = "set_bit_with_resize";
     341           1 :   show ("checking that set_bit initializes all limbs\n");
     342             : 
     343           1 :   a = gcry_mpi_new (1536);
     344           1 :   gcry_mpi_set_bit (a, 1536);
     345             : 
     346           1 :   if (!gcry_mpi_test_bit (a, 1536))
     347           0 :     fail ("failed to set a bit\n");
     348        1537 :   for (i=0; i < 1536; i++)
     349             :     {
     350        1536 :       if (gcry_mpi_test_bit (a, i))
     351             :         {
     352           0 :           fail ("spurious bit detected\n");
     353           0 :           break;
     354             :         }
     355             :     }
     356           1 :   if (gcry_mpi_test_bit (a, 1537))
     357           0 :     fail ("more bits set than expected\n");
     358           1 :   gcry_mpi_release (a);
     359             : 
     360           1 :   wherestr = "set_highbit_with_resize";
     361           1 :   show ("checking that set_highbit initializes all limbs\n");
     362             : 
     363           1 :   a = gcry_mpi_new (1536);
     364           1 :   gcry_mpi_set_highbit (a, 1536);
     365             : 
     366           1 :   if (!gcry_mpi_test_bit (a, 1536))
     367           0 :     fail ("failed to set a bit\n");
     368        1537 :   for (i=0; i < 1536; i++)
     369             :     {
     370        1536 :       if (gcry_mpi_test_bit (a, i))
     371             :         {
     372           0 :           fail ("spurious bit detected\n");
     373           0 :           break;
     374             :         }
     375             :     }
     376           1 :   if (gcry_mpi_test_bit (a, 1537))
     377           0 :     fail ("more bits set than expected\n");
     378           1 :   gcry_mpi_release (a);
     379           1 : }
     380             : 
     381             : 
     382             : int
     383           1 : main (int argc, char **argv)
     384             : {
     385           1 :   int debug = 0;
     386             :   int i;
     387             : 
     388           1 :   if (argc > 1 && !strcmp (argv[1], "--verbose"))
     389           0 :     verbose = 1;
     390           1 :   else if (argc > 1 && !strcmp (argv[1], "--debug"))
     391           0 :     verbose = debug = 1;
     392             : 
     393           1 :   if (!gcry_check_version (GCRYPT_VERSION))
     394           0 :     die ("version mismatch\n");
     395             : 
     396           1 :   gcry_control (GCRYCTL_DISABLE_SECMEM, 0);
     397           1 :   gcry_control (GCRYCTL_ENABLE_QUICK_RANDOM, 0);
     398           1 :   if (debug)
     399           0 :     gcry_control (GCRYCTL_SET_DEBUG_FLAGS, 1u, 0);
     400             : 
     401           1 :   gcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0);
     402             : 
     403           1 :   one_bit_only (0);
     404           1 :   one_bit_only (1);
     405           6 :   for (i=0; i < 5; i++)
     406           5 :     test_rshift (i); /* Run several times due to random initializations. */
     407             : 
     408           6 :   for (i=0; i < 5; i++)
     409           5 :     test_lshift (i); /* Run several times due to random initializations. */
     410             : 
     411           1 :   set_bit_with_resize ();
     412             : 
     413           1 :   show ("All tests completed. Errors: %d\n", error_count);
     414           1 :   return error_count ? 1 : 0;
     415             : }

Generated by: LCOV version 1.11