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