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