1 /* Test mpz_popcount. 2 3 Copyright 2001, 2005 Free Software Foundation, Inc. 4 5 This file is part of the GNU MP Library. 6 7 The GNU MP Library is free software; you can redistribute it and/or modify 8 it under the terms of the GNU Lesser General Public License as published by 9 the Free Software Foundation; either version 3 of the License, or (at your 10 option) any later version. 11 12 The GNU MP Library is distributed in the hope that it will be useful, but 13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 15 License for more details. 16 17 You should have received a copy of the GNU Lesser General Public License 18 along 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 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 abort (); 152 } 153 } 154 mpz_clear (arg); 155 mpz_clear (bs); 156 } 157 158 int 159 main (void) 160 { 161 tests_start (); 162 163 check_onebit (); 164 check_data (); 165 check_random (); 166 167 tests_end (); 168 exit (0); 169 } 170