tests/mpz/bit.c

   1 /* Test mpz_setbit, mpz_clrbit, mpz_tstbit.
   2
   3 Copyright 1997, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
   4
   5 This file is part of the GNU MP Library.
   6
   7 The GNU MP Library is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU Lesser General Public License as published by
   9 the Free Software Foundation; either version 3 of the License, or (at your
  10 option) any later version.
  11
  12 The GNU MP Library is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15 License for more details.
  16
  17 You should have received a copy of the GNU Lesser General Public License
  18 along 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
  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 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_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
  92 void
  93 check_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.  */
 144 void
 145 check_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
 193 void
 194 check_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
 259 void
 260 check_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
 359 int
 360 main (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 }