1 /* Test mpz_popcount.
2
3 Copyright 2001, 2005 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 #include "gmp-impl.h"
23 #include "tests.h"
24
25
26
27 void
28 check_onebit (void)
29 {
30 mpz_t n;
31 unsigned long i, got;
32
33 mpz_init (n);
34 for (i = 0; i < 5 * GMP_LIMB_BITS; i++)
35 {
36 mpz_setbit (n, i);
37 got = mpz_popcount (n);
38 if (got != 1)
39 {
40 printf ("mpz_popcount wrong on single bit at %lu\n", i);
41 printf (" got %lu, want 1\n", got);
42 abort();
43 }
44 mpz_clrbit (n, i);
45 }
46 mpz_clear (n);
47 }
48
49
50 void
51 check_data (void)
52 {
53 static const struct {
54 const char *n;
55 unsigned long want;
56 } data[] = {
57 { "-1", ~ (unsigned long) 0 },
58 { "-12345678", ~ (unsigned long) 0 },
59 { "0", 0 },
60 { "1", 1 },
61 { "3", 2 },
62 { "5", 2 },
63 { "0xFFFF", 16 },
64 { "0xFFFFFFFF", 32 },
65 { "0xFFFFFFFFFFFFFFFF", 64 },
66 { "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 128 },
67 };
68
69 unsigned long got;
70 int i;
71 mpz_t n;
72
73 mpz_init (n);
74 for (i = 0; i < numberof (data); i++)
75 {
76 mpz_set_str_or_abort (n, data[i].n, 0);
77 got = mpz_popcount (n);
78 if (got != data[i].want)
79 {
80 printf ("mpz_popcount wrong at data[%d]\n", i);
81 printf (" n \"%s\"\n", data[i].n);
82 printf (" "); mpz_out_str (stdout, 10, n); printf ("\n");
83 printf (" 0x"); mpz_out_str (stdout, 16, n); printf ("\n");
84 printf (" got %lu\n", got);
85 printf (" want %lu\n", data[i].want);
86 abort ();
87 }
88 }
89 mpz_clear (n);
90 }
91
92 unsigned long
93 refmpz_popcount (mpz_t arg)
94 {
95 mp_size_t n, i;
96 unsigned long cnt;
97 mp_limb_t x;
98
99 n = SIZ(arg);
100 if (n < 0)
101 return ~(unsigned long) 0;
102
103 cnt = 0;
104 for (i = 0; i < n; i++)
105 {
106 x = PTR(arg)[i];
107 while (x != 0)
108 {
109 cnt += (x & 1);
110 x >>= 1;
111 }
112 }
113 return cnt;
114 }
115
116 void
117 check_random (void)
118 {
119 gmp_randstate_ptr rands;
120 mpz_t bs;
121 mpz_t arg;
122 unsigned long arg_size, size_range;
123 unsigned long got, ref;
124 int i;
125
126 rands = RANDS;
127
128 mpz_init (bs);
129 mpz_init (arg);
130
131 for (i = 0; i < 10000; i++)
132 {
133 mpz_urandomb (bs, rands, 32);
134 size_range = mpz_get_ui (bs) % 11 + 2; /* 0..4096 bit operands */
135
136 mpz_urandomb (bs, rands, size_range);
137 arg_size = mpz_get_ui (bs);
138 mpz_rrandomb (arg, rands, arg_size);
139
140 got = mpz_popcount (arg);
141 ref = refmpz_popcount (arg);
142 if (got != ref)
143 {
144 printf ("mpz_popcount wrong on random\n");
145 printf (" "); mpz_out_str (stdout, 10, arg); printf ("\n");
146 printf (" 0x"); mpz_out_str (stdout, 16, arg); printf ("\n");
147 printf (" got %lu\n", got);
148 printf (" want %lu\n", ref);
149 abort ();
150 }
151 }
152 mpz_clear (arg);
153 mpz_clear (bs);
154 }
155
156 int
157 main (void)
158 {
159 tests_start ();
160
161 check_onebit ();
162 check_data ();
163 check_random ();
164
165 tests_end ();
166 exit (0);
167 }