tests/mpz/t-popcount.c

   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 }