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