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