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.h"
32
33#define PGM "t-mpi-bit"
34
35static const char *wherestr;
36static int verbose;
37static 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
44static void
45show (const char *format, ...)
46{
47  va_list arg_ptr;
48
49  if (!verbose)
50    return;
51  fprintf (stderr, "%s: ", PGM);
52  va_start (arg_ptr, format);
53  vfprintf (stderr, format, arg_ptr);
54  va_end (arg_ptr);
55}
56
57static void
58fail (const char *format, ...)
59{
60  va_list arg_ptr;
61
62  fflush (stdout);
63  fprintf (stderr, "%s: ", PGM);
64  if (wherestr)
65    fprintf (stderr, "%s: ", wherestr);
66  va_start (arg_ptr, format);
67  vfprintf (stderr, format, arg_ptr);
68  va_end (arg_ptr);
69  error_count++;
70}
71
72static void
73die (const char *format, ...)
74{
75  va_list arg_ptr;
76
77  fflush (stdout);
78  fprintf (stderr, "%s: ", PGM);
79  if (wherestr)
80    fprintf (stderr, "%s: ", wherestr);
81  va_start (arg_ptr, format);
82  vfprintf (stderr, format, arg_ptr);
83  va_end (arg_ptr);
84  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. */
90static char *
91mpi2bitstr (gcry_mpi_t a, size_t length)
92{
93  char *p, *buf;
94
95  buf = p = xmalloc (length+1);
96  while (length--)
97    *p++ = gcry_mpi_test_bit (a, length) ? '1':'0';
98  *p = 0;
99
100  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. */
106static char *
107mpi2bitstr_nlz (gcry_mpi_t a)
108{
109  char *p, *buf;
110  size_t length = gcry_mpi_get_nbits (a);
111
112  if (!length)
113    {
114      buf = p = xmalloc (2);
115      *p++ = '0';
116    }
117  else
118    {
119      buf = p = xmalloc (length + 1);
120      while (length-- > 1)
121        *p++ = gcry_mpi_test_bit (a, length) ? '1':'0';
122      *p++ = gcry_mpi_test_bit (a, 0) ? '1':'0';
123    }
124  *p = 0;
125  return buf;
126}
127
128/* Shift a bit string to the right. */
129static void
130rshiftbitstring (char *string, size_t n)
131{
132  size_t len = strlen (string);
133
134  if (n > len)
135    n = len;
136
137  memmove (string+n, string, len-n);
138  memset (string, '0', n);
139}
140
141/* Shift a bit string to the left. Caller needs to free the result. */
142static char *
143lshiftbitstring (const char *string, size_t n)
144{
145  size_t len = strlen (string);
146  char *result;
147
148  if (len+n+1 < len)
149    die ("internal overflow\n");
150  /* Allocate enough space. */
151  result = xmalloc (len+n+1);
152  for (; *string == '0' && string[1]; string++, len--)
153    ;
154  memcpy (result, string, len);
155  if (*string == '0' && !string[1])
156    n = 0; /* Avoid extra nulls for an only 0 string.  */
157  else
158    memset (result+len, '0', n);
159  result[len+n] = 0;
160  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.  */
166static void
167one_bit_only (int highbit)
168{
169  gcry_mpi_t a;
170  char *result;
171  int i;
172
173  wherestr = "one_bit_only";
174  show ("checking that set_%sbit does only set one bit\n", highbit?"high":"");
175
176  a = gcry_mpi_new (0);
177  gcry_mpi_randomize (a, 70, GCRY_WEAK_RANDOM);
178  gcry_mpi_set_ui (a, 0);
179
180  if (highbit)
181    gcry_mpi_set_highbit (a, 42);
182  else
183    gcry_mpi_set_bit (a, 42);
184  if (!gcry_mpi_test_bit (a, 42))
185    fail ("failed to set a bit\n");
186  gcry_mpi_clear_bit (a, 42);
187  if (gcry_mpi_test_bit (a, 42))
188    fail ("failed to clear a bit\n");
189  result = mpi2bitstr (a, 70);
190  assert (strlen (result) == 70);
191  for (i=0; result[i]; i++)
192    if ( result[i] != '0' )
193      break;
194  if (result[i])
195    fail ("spurious bits detected\n");
196  xfree (result);
197  gcry_mpi_release (a);
198}
199
200/* Check that right shifting actually works for an amount larger than
201   the number of bits per limb. */
202static void
203test_rshift (int pass)
204{
205  gcry_mpi_t a, b;
206  char *result, *result2;
207  int i;
208
209  wherestr = "test_rshift";
210  show ("checking that rshift works as expected (pass %d)\n", pass);
211
212  a = gcry_mpi_new (0);
213  b = gcry_mpi_new (0);
214  gcry_mpi_randomize (a, 70, GCRY_WEAK_RANDOM);
215
216  for (i=0; i < 75; i++)
217    {
218      gcry_mpi_rshift (b, a, i);
219
220      result = mpi2bitstr (b, 72);
221      result2 = mpi2bitstr (a, 72);
222      rshiftbitstring (result2, i);
223      if (strcmp (result, result2))
224        {
225          show ("got =%s\n", result);
226          show ("want=%s\n", result2);
227          fail ("rshift by %d failed\n", i);
228        }
229      xfree (result);
230      xfree (result2);
231    }
232
233  /* Again. This time using in-place operation. */
234  gcry_mpi_randomize (a, 70, GCRY_WEAK_RANDOM);
235
236  for (i=0; i < 75; i++)
237    {
238      gcry_mpi_release (b);
239      b = gcry_mpi_copy (a);
240      gcry_mpi_rshift (b, b, i);
241
242      result = mpi2bitstr (b, 72);
243      result2 = mpi2bitstr (a, 72);
244      rshiftbitstring (result2, i);
245      if (strcmp (result, result2))
246        {
247          show ("got =%s\n", result);
248          show ("want=%s\n", result2);
249          fail ("in-place rshift by %d failed\n", i);
250        }
251      xfree (result2);
252      xfree (result);
253    }
254
255  gcry_mpi_release (b);
256  gcry_mpi_release (a);
257}
258
259/* Check that left shifting works correctly.  */
260static void
261test_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  wherestr = "test_lshift";
270  show ("checking that lshift works as expected (pass %d)\n", pass);
271
272  for (size_idx=0; size_list[size_idx]; size_idx++)
273    {
274      a = gcry_mpi_new (0);
275      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      gcry_mpi_randomize (a, size_list[size_idx], GCRY_WEAK_RANDOM);
280      gcry_mpi_clear_highbit (a, size_list[size_idx]);
281
282      for (i=0; i < 75; i++)
283        {
284          gcry_mpi_lshift (b, a, i);
285
286          result = mpi2bitstr_nlz (b);
287          tmpstr = mpi2bitstr_nlz (a);
288          result2 = lshiftbitstring (tmpstr, i);
289          xfree (tmpstr);
290          if (strcmp (result, result2))
291            {
292              show ("got =%s\n", result);
293              show ("want=%s\n", result2);
294              fail ("lshift by %d failed\n", i);
295            }
296          xfree (result);
297          xfree (result2);
298        }
299
300      /* Again. This time using in-place operation. */
301      gcry_mpi_randomize (a, size_list[size_idx], GCRY_WEAK_RANDOM);
302      gcry_mpi_clear_highbit (a, size_list[size_idx]);
303
304      for (i=0; i < 75; i++)
305        {
306          gcry_mpi_release (b);
307          b = gcry_mpi_copy (a);
308          gcry_mpi_lshift (b, b, i);
309
310          result = mpi2bitstr_nlz (b);
311          tmpstr = mpi2bitstr_nlz (a);
312          result2 = lshiftbitstring (tmpstr, i);
313          xfree (tmpstr);
314          if (strcmp (result, result2))
315            {
316              show ("got =%s\n", result);
317              show ("want=%s\n", result2);
318              fail ("in-place lshift by %d failed\n", i);
319            }
320          xfree (result2);
321          xfree (result);
322        }
323
324      gcry_mpi_release (b);
325      gcry_mpi_release (a);
326    }
327}
328
329
330int
331main (int argc, char **argv)
332{
333  int debug = 0;
334  int i;
335
336  if (argc > 1 && !strcmp (argv[1], "--verbose"))
337    verbose = 1;
338  else if (argc > 1 && !strcmp (argv[1], "--debug"))
339    verbose = debug = 1;
340
341  if (!gcry_check_version (GCRYPT_VERSION))
342    die ("version mismatch\n");
343
344  gcry_control (GCRYCTL_DISABLE_SECMEM, 0);
345  gcry_control (GCRYCTL_ENABLE_QUICK_RANDOM, 0);
346  if (debug)
347    gcry_control (GCRYCTL_SET_DEBUG_FLAGS, 1u, 0);
348
349  gcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0);
350
351  one_bit_only (0);
352  one_bit_only (1);
353  for (i=0; i < 5; i++)
354    test_rshift (i); /* Run several times due to random initializations. */
355
356  for (i=0; i < 5; i++)
357    test_lshift (i); /* Run several times due to random initializations. */
358
359  show ("All tests completed. Errors: %d\n", error_count);
360  return error_count ? 1 : 0;
361}
362