184865Sobrien/* Test mpz_popcount. 284865Sobrien 384865SobrienCopyright 2001, 2005 Free Software Foundation, Inc. 484865Sobrien 584865SobrienThis file is part of the GNU MP Library. 684865Sobrien 784865SobrienThe GNU MP Library is free software; you can redistribute it and/or modify 884865Sobrienit under the terms of the GNU Lesser General Public License as published by 984865Sobrienthe Free Software Foundation; either version 3 of the License, or (at your 1084865Sobrienoption) any later version. 1184865Sobrien 1284865SobrienThe GNU MP Library is distributed in the hope that it will be useful, but 1384865SobrienWITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 1484865Sobrienor FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 1584865SobrienLicense for more details. 1684865Sobrien 1784865SobrienYou should have received a copy of the GNU Lesser General Public License 1884865Sobrienalong with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ 1984865Sobrien 2084865Sobrien#include <stdio.h> 2184865Sobrien#include <stdlib.h> 2284865Sobrien#include "gmp.h" 2384865Sobrien#include "gmp-impl.h" 2484865Sobrien#include "tests.h" 2584865Sobrien 2684865Sobrien 2784865Sobrien 2884865Sobrienvoid 2984865Sobriencheck_onebit (void) 3084865Sobrien{ 3184865Sobrien mpz_t n; 3284865Sobrien unsigned long i, got; 3384865Sobrien 3484865Sobrien mpz_init (n); 3584865Sobrien for (i = 0; i < 5 * GMP_LIMB_BITS; i++) 3684865Sobrien { 3784865Sobrien mpz_setbit (n, i); 3884865Sobrien got = mpz_popcount (n); 3984865Sobrien if (got != 1) 4084865Sobrien { 4184865Sobrien printf ("mpz_popcount wrong on single bit at %lu\n", i); 4284865Sobrien printf (" got %lu, want 1\n", got); 4384865Sobrien abort(); 4484865Sobrien } 4584865Sobrien mpz_clrbit (n, i); 4684865Sobrien } 4784865Sobrien mpz_clear (n); 4884865Sobrien} 4984865Sobrien 5084865Sobrien 5184865Sobrienvoid 5284865Sobriencheck_data (void) 5384865Sobrien{ 5484865Sobrien static const struct { 5584865Sobrien const char *n; 5684865Sobrien unsigned long want; 5784865Sobrien } data[] = { 5884865Sobrien { "-1", ~ (unsigned long) 0 }, 5984865Sobrien { "-12345678", ~ (unsigned long) 0 }, 6084865Sobrien { "0", 0 }, 6184865Sobrien { "1", 1 }, 6284865Sobrien { "3", 2 }, 6384865Sobrien { "5", 2 }, 6484865Sobrien { "0xFFFF", 16 }, 6584865Sobrien { "0xFFFFFFFF", 32 }, 6684865Sobrien { "0xFFFFFFFFFFFFFFFF", 64 }, 6784865Sobrien { "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 128 }, 6884865Sobrien }; 6984865Sobrien 7084865Sobrien unsigned long got; 7184865Sobrien int i; 7284865Sobrien mpz_t n; 7384865Sobrien 7484865Sobrien mpz_init (n); 7584865Sobrien for (i = 0; i < numberof (data); i++) 7684865Sobrien { 7784865Sobrien mpz_set_str_or_abort (n, data[i].n, 0); 7884865Sobrien got = mpz_popcount (n); 7984865Sobrien if (got != data[i].want) 8084865Sobrien { 8184865Sobrien printf ("mpz_popcount wrong at data[%d]\n", i); 8284865Sobrien printf (" n \"%s\"\n", data[i].n); 8384865Sobrien printf (" "); mpz_out_str (stdout, 10, n); printf ("\n"); 8484865Sobrien printf (" 0x"); mpz_out_str (stdout, 16, n); printf ("\n"); 8584865Sobrien printf (" got %lu\n", got); 8684865Sobrien printf (" want %lu\n", data[i].want); 8784865Sobrien abort(); 8884865Sobrien } 8984865Sobrien } 9084865Sobrien mpz_clear (n); 9184865Sobrien} 9284865Sobrien 9384865Sobrienunsigned long 9484865Sobrienrefmpz_popcount (mpz_t arg) 9584865Sobrien{ 9684865Sobrien mp_size_t n, i; 9784865Sobrien unsigned long cnt; 9884865Sobrien mp_limb_t x; 9984865Sobrien 10084865Sobrien n = SIZ(arg); 10184865Sobrien if (n < 0) 10284865Sobrien return ~(unsigned long) 0; 10384865Sobrien 10484865Sobrien cnt = 0; 10584865Sobrien for (i = 0; i < n; i++) 10684865Sobrien { 10784865Sobrien x = PTR(arg)[i]; 10884865Sobrien while (x != 0) 10984865Sobrien { 11084865Sobrien cnt += (x & 1); 11184865Sobrien x >>= 1; 11284865Sobrien } 11384865Sobrien } 11484865Sobrien return cnt; 11584865Sobrien} 11684865Sobrien 11784865Sobrienvoid 11884865Sobriencheck_random (void) 11984865Sobrien{ 12084865Sobrien gmp_randstate_ptr rands; 12184865Sobrien mpz_t bs; 12284865Sobrien mpz_t arg; 12384865Sobrien unsigned long arg_size, size_range; 12484865Sobrien unsigned long got, ref; 12584865Sobrien int i; 12684865Sobrien 12784865Sobrien rands = RANDS; 12884865Sobrien 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