1 /* Test mpz_setbit, mpz_clrbit, mpz_tstbit. 2 3 Copyright 1997, 2000-2003, 2012, 2013 Free Software Foundation, Inc. 4 5 This file is part of the GNU MP Library test suite. 6 7 The GNU MP Library test suite is free software; you can redistribute it 8 and/or modify it under the terms of the GNU General Public License as 9 published by the Free Software Foundation; either version 3 of the License, 10 or (at your option) any later version. 11 12 The GNU MP Library test suite is distributed in the hope that it will be 13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General 15 Public License for more details. 16 17 You should have received a copy of the GNU General Public License along with 18 the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ 19 20 #include <stdio.h> 21 #include <stdlib.h> 22 23 #include "gmp-impl.h" 24 #include "tests.h" 25 26 #ifndef SIZE 27 #define SIZE 4 28 #endif 29 30 31 void 32 debug_mp (mpz_srcptr x, int base) 33 { 34 mpz_out_str (stdout, base, x); fputc ('\n', stdout); 35 } 36 37 38 /* exercise the case where mpz_clrbit or mpz_combit ends up extending a 39 value like -2^(k*GMP_NUMB_BITS-1) when clearing bit k*GMP_NUMB_BITS-1. */ 40 /* And vice-versa. */ 41 void 42 check_clr_extend (void) 43 { 44 mpz_t got, want; 45 unsigned long i; 46 int f; 47 48 mpz_init (got); 49 mpz_init (want); 50 51 for (i = 1; i < 5; i++) 52 { 53 for (f = 0; f <= 1; f++) 54 { 55 /* lots of 1 bits in _mp_d */ 56 mpz_set_si (got, 1L); 57 mpz_mul_2exp (got, got, 10*GMP_NUMB_BITS); 58 mpz_sub_ui (got, got, 1L); 59 60 /* value -2^(n-1) representing ..11100..00 */ 61 mpz_set_si (got, -1L); 62 mpz_mul_2exp (got, got, i*GMP_NUMB_BITS-1); 63 64 /* complement bit n, giving ..11000..00 which is -2^n */ 65 if (f == 0) 66 mpz_clrbit (got, i*GMP_NUMB_BITS-1); 67 else 68 mpz_combit (got, i*GMP_NUMB_BITS-1); 69 MPZ_CHECK_FORMAT (got); 70 71 mpz_set_si (want, -1L); 72 mpz_mul_2exp (want, want, i*GMP_NUMB_BITS); 73 74 if (mpz_cmp (got, want) != 0) 75 { 76 if (f == 0) 77 printf ("mpz_clrbit: "); 78 else 79 printf ("mpz_combit: "); 80 printf ("wrong after extension\n"); 81 mpz_trace ("got ", got); 82 mpz_trace ("want", want); 83 abort (); 84 } 85 86 /* complement bit n, going back to ..11100..00 which is -2^(n-1) */ 87 if (f == 0) 88 mpz_setbit (got, i*GMP_NUMB_BITS-1); 89 else 90 mpz_combit (got, i*GMP_NUMB_BITS-1); 91 MPZ_CHECK_FORMAT (got); 92 93 mpz_set_si (want, -1L); 94 mpz_mul_2exp (want, want, i*GMP_NUMB_BITS - 1); 95 96 if (mpz_cmp (got, want) != 0) 97 { 98 if (f == 0) 99 printf ("mpz_setbit: "); 100 else 101 printf ("mpz_combit: "); 102 printf ("wrong after shrinking\n"); 103 mpz_trace ("got ", got); 104 mpz_trace ("want", want); 105 abort (); 106 } 107 } 108 } 109 110 mpz_clear (got); 111 mpz_clear (want); 112 } 113 114 void 115 check_com_negs (void) 116 { 117 static const struct { 118 unsigned long bit; 119 mp_size_t inp_size; 120 mp_limb_t inp_n[5]; 121 mp_size_t want_size; 122 mp_limb_t want_n[5]; 123 } data[] = { 124 { GMP_NUMB_BITS, 2, { 1, 1 }, 1, { 1 } }, 125 { GMP_NUMB_BITS+1, 2, { 1, 1 }, 2, { 1, 3 } }, 126 127 { GMP_NUMB_BITS, 2, { 0, 1 }, 2, { 0, 2 } }, 128 { GMP_NUMB_BITS+1, 2, { 0, 1 }, 2, { 0, 3 } }, 129 }; 130 mpz_t inp, got, want; 131 int i; 132 133 mpz_init (got); 134 mpz_init (want); 135 mpz_init (inp); 136 137 for (i = 0; i < numberof (data); i++) 138 { 139 mpz_set_n (inp, data[i].inp_n, data[i].inp_size); 140 mpz_neg (inp, inp); 141 142 mpz_set_n (want, data[i].want_n, data[i].want_size); 143 mpz_neg (want, want); 144 145 mpz_set (got, inp); 146 mpz_combit (got, data[i].bit); 147 148 if (mpz_cmp (got, want) != 0) 149 { 150 printf ("mpz_combit: wrong on neg data[%d]\n", i); 151 mpz_trace ("inp ", inp); 152 printf ("bit %lu\n", data[i].bit); 153 mpz_trace ("got ", got); 154 mpz_trace ("want", want); 155 abort (); 156 } 157 } 158 159 mpz_clear (inp); 160 mpz_clear (got); 161 mpz_clear (want); 162 } 163 164 /* See that mpz_tstbit matches a twos complement calculated explicitly, for 165 various low zeros. */ 166 void 167 check_tstbit (void) 168 { 169 #define MAX_ZEROS 3 170 #define NUM_LIMBS 3 171 172 mp_limb_t pos[1+NUM_LIMBS+MAX_ZEROS]; 173 mp_limb_t neg[1+NUM_LIMBS+MAX_ZEROS]; 174 mpz_t z; 175 unsigned long i; 176 int zeros, low1; 177 int got, want; 178 179 mpz_init (z); 180 for (zeros = 0; zeros <= MAX_ZEROS; zeros++) 181 { 182 MPN_ZERO (pos, numberof(pos)); 183 mpn_random2 (pos+zeros, (mp_size_t) NUM_LIMBS); 184 185 for (low1 = 0; low1 <= 1; low1++) 186 { 187 if (low1) 188 pos[0] |= 1; 189 190 refmpn_neg (neg, pos, (mp_size_t) numberof(neg)); 191 mpz_set_n (z, neg, (mp_size_t) numberof(neg)); 192 mpz_neg (z, z); 193 194 for (i = 0; i < numberof(pos)*GMP_NUMB_BITS; i++) 195 { 196 got = mpz_tstbit (z, i); 197 want = refmpn_tstbit (pos, i); 198 if (got != want) 199 { 200 printf ("wrong at bit %lu, with %d zeros\n", i, zeros); 201 printf ("z neg "); debug_mp (z, -16); 202 mpz_set_n (z, pos, (mp_size_t) numberof(pos)); 203 printf ("pos "); debug_mp (z, -16); 204 mpz_set_n (z, neg, (mp_size_t) numberof(neg)); 205 printf ("neg "); debug_mp (z, -16); 206 exit (1); 207 } 208 } 209 } 210 } 211 mpz_clear (z); 212 } 213 214 215 void 216 check_single (void) 217 { 218 mpz_t x; 219 int limb, offset, initial; 220 unsigned long bit; 221 222 mpz_init (x); 223 224 for (limb = 0; limb < 4; limb++) 225 { 226 for (offset = (limb==0 ? 0 : -2); offset <= 2; offset++) 227 { 228 for (initial = 1; initial >= -1; initial--) 229 { 230 mpz_set_si (x, (long) initial); 231 232 bit = (unsigned long) limb*GMP_LIMB_BITS + offset; 233 234 mpz_clrbit (x, bit); 235 MPZ_CHECK_FORMAT (x); 236 if (mpz_tstbit (x, bit) != 0) 237 { 238 printf ("check_single(): expected 0\n"); 239 abort (); 240 } 241 242 mpz_setbit (x, bit); 243 MPZ_CHECK_FORMAT (x); 244 if (mpz_tstbit (x, bit) != 1) 245 { 246 printf ("check_single(): expected 1\n"); 247 abort (); 248 } 249 250 mpz_clrbit (x, bit); 251 MPZ_CHECK_FORMAT (x); 252 if (mpz_tstbit (x, bit) != 0) 253 { 254 printf ("check_single(): expected 0\n"); 255 abort (); 256 } 257 258 mpz_combit (x, bit); 259 MPZ_CHECK_FORMAT (x); 260 if (mpz_tstbit (x, bit) != 1) 261 { 262 printf ("check_single(): expected 1\n"); 263 abort (); 264 } 265 266 mpz_combit (x, bit); 267 MPZ_CHECK_FORMAT (x); 268 if (mpz_tstbit (x, bit) != 0) 269 { 270 printf ("check_single(): expected 0\n"); 271 abort (); 272 } 273 } 274 } 275 } 276 277 mpz_clear (x); 278 } 279 280 281 void 282 check_random (int argc, char *argv[]) 283 { 284 mpz_t x, s0, s1, s2, s3, m; 285 mp_size_t xsize; 286 int i; 287 int reps = 100000; 288 int bit0, bit1, bit2, bit3; 289 unsigned long int bitindex; 290 const char *s = ""; 291 292 if (argc == 2) 293 reps = atoi (argv[1]); 294 295 mpz_init (x); 296 mpz_init (s0); 297 mpz_init (s1); 298 mpz_init (s2); 299 mpz_init (s3); 300 mpz_init (m); 301 302 for (i = 0; i < reps; i++) 303 { 304 xsize = urandom () % (2 * SIZE) - SIZE; 305 mpz_random2 (x, xsize); 306 bitindex = urandom () % SIZE; 307 308 mpz_set (s0, x); 309 bit0 = mpz_tstbit (x, bitindex); 310 mpz_setbit (x, bitindex); 311 MPZ_CHECK_FORMAT (x); 312 313 mpz_set (s1, x); 314 bit1 = mpz_tstbit (x, bitindex); 315 mpz_clrbit (x, bitindex); 316 MPZ_CHECK_FORMAT (x); 317 318 mpz_set (s2, x); 319 bit2 = mpz_tstbit (x, bitindex); 320 mpz_combit (x, bitindex); 321 MPZ_CHECK_FORMAT (x); 322 323 mpz_set (s3, x); 324 bit3 = mpz_tstbit (x, bitindex); 325 326 #define FAIL(str) do { s = str; goto fail; } while (0) 327 328 if (bit1 != 1) FAIL ("bit1 != 1"); 329 if (bit2 != 0) FAIL ("bit2 != 0"); 330 if (bit3 != 1) FAIL ("bit3 != 1"); 331 332 if (bit0 == 0) 333 { 334 if (mpz_cmp (s0, s1) == 0 || mpz_cmp (s0, s2) != 0 || mpz_cmp (s0, s3) == 0) 335 abort (); 336 } 337 else 338 { 339 if (mpz_cmp (s0, s1) != 0 || mpz_cmp (s0, s2) == 0 || mpz_cmp (s0, s3) != 0) 340 abort (); 341 } 342 343 if (mpz_cmp (s1, s2) == 0 || mpz_cmp (s1, s3) != 0) 344 abort (); 345 if (mpz_cmp (s2, s3) == 0) 346 abort (); 347 348 mpz_combit (x, bitindex); 349 MPZ_CHECK_FORMAT (x); 350 if (mpz_cmp (s2, x) != 0) 351 abort (); 352 353 mpz_clrbit (x, bitindex); 354 MPZ_CHECK_FORMAT (x); 355 if (mpz_cmp (s2, x) != 0) 356 abort (); 357 358 mpz_ui_pow_ui (m, 2L, bitindex); 359 MPZ_CHECK_FORMAT (m); 360 mpz_ior (x, s0, m); 361 MPZ_CHECK_FORMAT (x); 362 if (mpz_cmp (x, s3) != 0) 363 abort (); 364 365 mpz_com (m, m); 366 MPZ_CHECK_FORMAT (m); 367 mpz_and (x, s0, m); 368 MPZ_CHECK_FORMAT (x); 369 if (mpz_cmp (x, s2) != 0) 370 abort (); 371 } 372 373 mpz_clear (x); 374 mpz_clear (s0); 375 mpz_clear (s1); 376 mpz_clear (s2); 377 mpz_clear (s3); 378 mpz_clear (m); 379 return; 380 381 382 fail: 383 printf ("%s\n", s); 384 printf ("bitindex = %lu\n", bitindex); 385 printf ("x = "); mpz_out_str (stdout, -16, x); printf (" hex\n"); 386 exit (1); 387 } 388 389 390 391 int 392 main (int argc, char *argv[]) 393 { 394 tests_start (); 395 mp_trace_base = -16; 396 397 check_clr_extend (); 398 check_com_negs (); 399 check_tstbit (); 400 check_random (argc, argv); 401 check_single (); 402 403 tests_end (); 404 exit (0); 405 } 406