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