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 1050 : buf = p = xmalloc (2);
115 1050 : *p++ = '0';
116 : }
117 : else
118 : {
119 9450 : buf = p = xmalloc (length + 1);
120 661875 : while (length-- > 1)
121 642975 : *p++ = gcry_mpi_test_bit (a, length) ? '1':'0';
122 9450 : *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 525 : n = 0; /* Avoid extra nulls for an only 0 string. */
157 : else
158 4725 : 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 : }
|
