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