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 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 28 void 29 check_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 51 void 52 check_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 93 unsigned long 94 refmpz_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 117 void 118 check_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 } 152 } 153 mpz_clear (arg); 154 mpz_clear (bs); 155 } 156 157 int 158 main (void) 159 { 160 tests_start (); 161 162 check_onebit (); 163 check_data (); 164 check_random (); 165 166 tests_end (); 167 exit (0); 168 } 169