tests/mpz/bit.c

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