tests/mpz/bit.c

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