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 : #define PGM "t-mpi-bit"
32 : #include "t-common.h"
33 :
34 :
35 : /* Allocate a bit string consisting of '0' and '1' from the MPI
36 : A. Return the LENGTH least significant bits. Caller needs to xfree
37 : the result. */
38 : static char *
39 1502 : mpi2bitstr (gcry_mpi_t a, size_t length)
40 : {
41 : char *p, *buf;
42 :
43 1502 : buf = p = xmalloc (length+1);
44 111144 : while (length--)
45 108140 : *p++ = gcry_mpi_test_bit (a, length) ? '1':'0';
46 1502 : *p = 0;
47 :
48 1502 : return buf;
49 : }
50 :
51 : /* Allocate a bit string consisting of '0' and '1' from the MPI A. Do
52 : not return any leading zero bits. Caller needs to xfree the
53 : result. */
54 : static char *
55 10500 : mpi2bitstr_nlz (gcry_mpi_t a)
56 : {
57 : char *p, *buf;
58 10500 : size_t length = gcry_mpi_get_nbits (a);
59 :
60 10500 : if (!length)
61 : {
62 1200 : buf = p = xmalloc (2);
63 1200 : *p++ = '0';
64 : }
65 : else
66 : {
67 9300 : buf = p = xmalloc (length + 1);
68 659700 : while (length-- > 1)
69 641100 : *p++ = gcry_mpi_test_bit (a, length) ? '1':'0';
70 9300 : *p++ = gcry_mpi_test_bit (a, 0) ? '1':'0';
71 : }
72 10500 : *p = 0;
73 10500 : return buf;
74 : }
75 :
76 : /* Shift a bit string to the right. */
77 : static void
78 750 : rshiftbitstring (char *string, size_t n)
79 : {
80 750 : size_t len = strlen (string);
81 :
82 750 : if (n > len)
83 20 : n = len;
84 :
85 750 : memmove (string+n, string, len-n);
86 750 : memset (string, '0', n);
87 750 : }
88 :
89 : /* Shift a bit string to the left. Caller needs to free the result. */
90 : static char *
91 5250 : lshiftbitstring (const char *string, size_t n)
92 : {
93 5250 : size_t len = strlen (string);
94 : char *result;
95 :
96 5250 : if (len+n+1 < len)
97 0 : die ("internal overflow\n");
98 : /* Allocate enough space. */
99 5250 : result = xmalloc (len+n+1);
100 5250 : for (; *string == '0' && string[1]; string++, len--)
101 : ;
102 5250 : memcpy (result, string, len);
103 5250 : if (*string == '0' && !string[1])
104 600 : n = 0; /* Avoid extra nulls for an only 0 string. */
105 : else
106 4650 : memset (result+len, '0', n);
107 5250 : result[len+n] = 0;
108 5250 : return result;
109 : }
110 :
111 :
112 : /* This is to check a bug reported by bpgcrypt at itaparica.org on
113 : 2006-07-31 against libgcrypt 1.2.2. */
114 : static void
115 2 : one_bit_only (int highbit)
116 : {
117 : gcry_mpi_t a;
118 : char *result;
119 : int i;
120 :
121 2 : wherestr = "one_bit_only";
122 2 : info ("checking that set_%sbit does only set one bit\n", highbit?"high":"");
123 :
124 2 : a = gcry_mpi_new (0);
125 2 : gcry_mpi_randomize (a, 70, GCRY_WEAK_RANDOM);
126 2 : gcry_mpi_set_ui (a, 0);
127 :
128 2 : if (highbit)
129 1 : gcry_mpi_set_highbit (a, 42);
130 : else
131 1 : gcry_mpi_set_bit (a, 42);
132 2 : if (!gcry_mpi_test_bit (a, 42))
133 0 : fail ("failed to set a bit\n");
134 2 : gcry_mpi_clear_bit (a, 42);
135 2 : if (gcry_mpi_test_bit (a, 42))
136 0 : fail ("failed to clear a bit\n");
137 2 : result = mpi2bitstr (a, 70);
138 2 : assert (strlen (result) == 70);
139 142 : for (i=0; result[i]; i++)
140 140 : if ( result[i] != '0' )
141 0 : break;
142 2 : if (result[i])
143 0 : fail ("spurious bits detected\n");
144 2 : xfree (result);
145 2 : gcry_mpi_release (a);
146 2 : }
147 :
148 : /* Check that right shifting actually works for an amount larger than
149 : the number of bits per limb. */
150 : static void
151 5 : test_rshift (int pass)
152 : {
153 : gcry_mpi_t a, b;
154 : char *result, *result2;
155 : int i;
156 :
157 5 : wherestr = "test_rshift";
158 5 : info ("checking that rshift works as expected (pass %d)\n", pass);
159 :
160 5 : a = gcry_mpi_new (0);
161 5 : b = gcry_mpi_new (0);
162 5 : gcry_mpi_randomize (a, 70, GCRY_WEAK_RANDOM);
163 :
164 380 : for (i=0; i < 75; i++)
165 : {
166 375 : gcry_mpi_rshift (b, a, i);
167 :
168 375 : result = mpi2bitstr (b, 72);
169 375 : result2 = mpi2bitstr (a, 72);
170 375 : rshiftbitstring (result2, i);
171 375 : if (strcmp (result, result2))
172 : {
173 0 : info ("got =%s\n", result);
174 0 : info ("want=%s\n", result2);
175 0 : fail ("rshift by %d failed\n", i);
176 : }
177 375 : xfree (result);
178 375 : xfree (result2);
179 : }
180 :
181 : /* Again. This time using in-place operation. */
182 5 : gcry_mpi_randomize (a, 70, GCRY_WEAK_RANDOM);
183 :
184 380 : for (i=0; i < 75; i++)
185 : {
186 375 : gcry_mpi_release (b);
187 375 : b = gcry_mpi_copy (a);
188 375 : gcry_mpi_rshift (b, b, i);
189 :
190 375 : result = mpi2bitstr (b, 72);
191 375 : result2 = mpi2bitstr (a, 72);
192 375 : rshiftbitstring (result2, i);
193 375 : if (strcmp (result, result2))
194 : {
195 0 : info ("got =%s\n", result);
196 0 : info ("want=%s\n", result2);
197 0 : fail ("in-place rshift by %d failed\n", i);
198 : }
199 375 : xfree (result2);
200 375 : xfree (result);
201 : }
202 :
203 5 : gcry_mpi_release (b);
204 5 : gcry_mpi_release (a);
205 5 : }
206 :
207 : /* Check that left shifting works correctly. */
208 : static void
209 5 : test_lshift (int pass)
210 : {
211 : static int size_list[] = {1, 31, 32, 63, 64, 65, 70, 0};
212 : int size_idx;
213 : gcry_mpi_t a, b;
214 : char *tmpstr, *result, *result2;
215 : int i;
216 :
217 5 : wherestr = "test_lshift";
218 5 : info ("checking that lshift works as expected (pass %d)\n", pass);
219 :
220 40 : for (size_idx=0; size_list[size_idx]; size_idx++)
221 : {
222 35 : a = gcry_mpi_new (0);
223 35 : b = gcry_mpi_new (0);
224 :
225 : /* gcry_mpi_randomize rounds up to full bytes, thus we need to
226 : use gcry_mpi_clear_highbit to fix that. */
227 35 : gcry_mpi_randomize (a, size_list[size_idx], GCRY_WEAK_RANDOM);
228 35 : gcry_mpi_clear_highbit (a, size_list[size_idx]);
229 :
230 2660 : for (i=0; i < 75; i++)
231 : {
232 2625 : gcry_mpi_lshift (b, a, i);
233 :
234 2625 : result = mpi2bitstr_nlz (b);
235 2625 : tmpstr = mpi2bitstr_nlz (a);
236 2625 : result2 = lshiftbitstring (tmpstr, i);
237 2625 : xfree (tmpstr);
238 2625 : if (strcmp (result, result2))
239 : {
240 0 : info ("got =%s\n", result);
241 0 : info ("want=%s\n", result2);
242 0 : fail ("lshift by %d failed\n", i);
243 : }
244 2625 : xfree (result);
245 2625 : xfree (result2);
246 : }
247 :
248 : /* Again. This time using in-place operation. */
249 35 : gcry_mpi_randomize (a, size_list[size_idx], GCRY_WEAK_RANDOM);
250 35 : gcry_mpi_clear_highbit (a, size_list[size_idx]);
251 :
252 2660 : for (i=0; i < 75; i++)
253 : {
254 2625 : gcry_mpi_release (b);
255 2625 : b = gcry_mpi_copy (a);
256 2625 : gcry_mpi_lshift (b, b, i);
257 :
258 2625 : result = mpi2bitstr_nlz (b);
259 2625 : tmpstr = mpi2bitstr_nlz (a);
260 2625 : result2 = lshiftbitstring (tmpstr, i);
261 2625 : xfree (tmpstr);
262 2625 : if (strcmp (result, result2))
263 : {
264 0 : info ("got =%s\n", result);
265 0 : info ("want=%s\n", result2);
266 0 : fail ("in-place lshift by %d failed\n", i);
267 : }
268 2625 : xfree (result2);
269 2625 : xfree (result);
270 : }
271 :
272 35 : gcry_mpi_release (b);
273 35 : gcry_mpi_release (a);
274 : }
275 5 : }
276 :
277 :
278 : /* Bug fixed on 2014-05-09:
279 : a = gcry_mpi_new (1523);
280 : gcry_mpi_set_bit (a, 1536);
281 : didn't initialized all limbs in A. */
282 : static void
283 1 : set_bit_with_resize (void)
284 : {
285 : gcry_mpi_t a;
286 : int i;
287 :
288 1 : wherestr = "set_bit_with_resize";
289 1 : info ("checking that set_bit initializes all limbs\n");
290 :
291 1 : a = gcry_mpi_new (1536);
292 1 : gcry_mpi_set_bit (a, 1536);
293 :
294 1 : if (!gcry_mpi_test_bit (a, 1536))
295 0 : fail ("failed to set a bit\n");
296 1537 : for (i=0; i < 1536; i++)
297 : {
298 1536 : if (gcry_mpi_test_bit (a, i))
299 : {
300 0 : fail ("spurious bit detected\n");
301 0 : break;
302 : }
303 : }
304 1 : if (gcry_mpi_test_bit (a, 1537))
305 0 : fail ("more bits set than expected\n");
306 1 : gcry_mpi_release (a);
307 :
308 1 : wherestr = "set_highbit_with_resize";
309 1 : info ("checking that set_highbit initializes all limbs\n");
310 :
311 1 : a = gcry_mpi_new (1536);
312 1 : gcry_mpi_set_highbit (a, 1536);
313 :
314 1 : if (!gcry_mpi_test_bit (a, 1536))
315 0 : fail ("failed to set a bit\n");
316 1537 : for (i=0; i < 1536; i++)
317 : {
318 1536 : if (gcry_mpi_test_bit (a, i))
319 : {
320 0 : fail ("spurious bit detected\n");
321 0 : break;
322 : }
323 : }
324 1 : if (gcry_mpi_test_bit (a, 1537))
325 0 : fail ("more bits set than expected\n");
326 1 : gcry_mpi_release (a);
327 1 : }
328 :
329 :
330 : int
331 1 : main (int argc, char **argv)
332 : {
333 : int i;
334 :
335 1 : if (argc > 1 && !strcmp (argv[1], "--verbose"))
336 0 : verbose = 1;
337 1 : else if (argc > 1 && !strcmp (argv[1], "--debug"))
338 0 : verbose = debug = 1;
339 :
340 1 : if (!gcry_check_version (GCRYPT_VERSION))
341 0 : die ("version mismatch\n");
342 :
343 1 : xgcry_control (GCRYCTL_DISABLE_SECMEM, 0);
344 1 : xgcry_control (GCRYCTL_ENABLE_QUICK_RANDOM, 0);
345 1 : if (debug)
346 0 : xgcry_control (GCRYCTL_SET_DEBUG_FLAGS, 1u, 0);
347 :
348 1 : xgcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0);
349 :
350 1 : one_bit_only (0);
351 1 : one_bit_only (1);
352 6 : for (i=0; i < 5; i++)
353 5 : test_rshift (i); /* Run several times due to random initializations. */
354 :
355 6 : for (i=0; i < 5; i++)
356 5 : test_lshift (i); /* Run several times due to random initializations. */
357 :
358 1 : set_bit_with_resize ();
359 :
360 1 : info ("All tests completed. Errors: %d\n", error_count);
361 1 : return error_count ? 1 : 0;
362 : }
|
