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 } 168