bit.c
上传用户:qaz666999
上传日期:2022-08-06
资源大小:2570k
文件大小:8k
源码类别:

数学计算

开发平台:

Unix_Linux

  1. /* Test mpz_setbit, mpz_clrbit, mpz_tstbit.
  2. Copyright 1997, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
  3. This file is part of the GNU MP Library.
  4. The GNU MP Library is free software; you can redistribute it and/or modify
  5. it under the terms of the GNU Lesser General Public License as published by
  6. the Free Software Foundation; either version 3 of the License, or (at your
  7. option) any later version.
  8. The GNU MP Library is distributed in the hope that it will be useful, but
  9. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  10. or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  11. License for more details.
  12. You should have received a copy of the GNU Lesser General Public License
  13. along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  14. #include <stdio.h>
  15. #include <stdlib.h>
  16. #include "gmp.h"
  17. #include "gmp-impl.h"
  18. #include "tests.h"
  19. #ifndef SIZE
  20. #define SIZE 4
  21. #endif
  22. void
  23. debug_mp (mpz_srcptr x, int base)
  24. {
  25.   mpz_out_str (stdout, base, x); fputc ('n', stdout);
  26. }
  27. /* exercise the case where mpz_clrbit or mpz_combit ends up extending a
  28.    value like -2^(k*GMP_NUMB_BITS-1) when clearing bit k*GMP_NUMB_BITS-1.  */
  29. void
  30. check_clr_extend (void)
  31. {
  32.   mpz_t          got, want;
  33.   unsigned long  i;
  34.   int            f;
  35.   mpz_init (got);
  36.   mpz_init (want);
  37.   for (i = 1; i < 5; i++)
  38.     {
  39.       for (f = 0; f <= 1; f++)
  40. {
  41.   /* lots of 1 bits in _mp_d */
  42.   mpz_set_ui (got, 1L);
  43.   mpz_mul_2exp (got, got, 10*GMP_NUMB_BITS);
  44.   mpz_sub_ui (got, got, 1L);
  45.   /* value -2^(n-1) representing ..11100..00 */
  46.   mpz_set_si (got, -1L);
  47.   mpz_mul_2exp (got, got, i*GMP_NUMB_BITS-1);
  48.   /* complement bit n, giving ..11000..00 which is -2^n */
  49.   if (f == 0)
  50.     mpz_clrbit (got, i*GMP_NUMB_BITS-1);
  51.   else
  52.     mpz_combit (got, i*GMP_NUMB_BITS-1);
  53.   MPZ_CHECK_FORMAT (got);
  54.   mpz_set_si (want, -1L);
  55.   mpz_mul_2exp (want, want, i*GMP_NUMB_BITS);
  56.   if (mpz_cmp (got, want) != 0)
  57.     {
  58.       if (f == 0)
  59. printf ("mpz_clrbit: ");
  60.       else
  61. printf ("mpz_combit: ");
  62.       printf ("wrong after extensionn");
  63.       mpz_trace ("got ", got);
  64.       mpz_trace ("want", want);
  65.       abort ();
  66.     }
  67. }
  68.     }
  69.   mpz_clear (got);
  70.   mpz_clear (want);
  71. }
  72. void
  73. check_com_negs (void)
  74. {
  75.   static const struct {
  76.     unsigned long  bit;
  77.     mp_size_t      inp_size;
  78.     mp_limb_t      inp_n[5];
  79.     mp_size_t      want_size;
  80.     mp_limb_t      want_n[5];
  81.   } data[] = {
  82.     { GMP_NUMB_BITS,   2, { 1, 1 },  1, { 1 } },
  83.     { GMP_NUMB_BITS+1, 2, { 1, 1 },  2, { 1, 3 } },
  84.     { GMP_NUMB_BITS,   2, { 0, 1 },  2, { 0, 2 } },
  85.     { GMP_NUMB_BITS+1, 2, { 0, 1 },  2, { 0, 3 } },
  86.   };
  87.   mpz_t  inp, got, want;
  88.   int    i;
  89.   mpz_init (got);
  90.   mpz_init (want);
  91.   mpz_init (inp);
  92.   for (i = 0; i < numberof (data); i++)
  93.     {
  94.       mpz_set_n (inp, data[i].inp_n, data[i].inp_size);
  95.       mpz_neg (inp, inp);
  96.       mpz_set_n (want, data[i].want_n, data[i].want_size);
  97.       mpz_neg (want, want);
  98.       mpz_set (got, inp);
  99.       mpz_combit (got, data[i].bit);
  100.       if (mpz_cmp (got, want) != 0)
  101. {
  102.   printf ("mpz_combit: wrong on neg data[%d]n", i);
  103.   mpz_trace ("inp ", inp);
  104.   printf    ("bit %lun", data[i].bit);
  105.   mpz_trace ("got ", got);
  106.   mpz_trace ("want", want);
  107.   abort ();
  108. }
  109.     }
  110.   mpz_clear (inp);
  111.   mpz_clear (got);
  112.   mpz_clear (want);
  113. }
  114. /* See that mpz_tstbit matches a twos complement calculated explicitly, for
  115.    various low zeros.  */
  116. void
  117. check_tstbit (void)
  118. {
  119. #define MAX_ZEROS  3
  120. #define NUM_LIMBS  3
  121.   mp_limb_t      pos[1+NUM_LIMBS+MAX_ZEROS];
  122.   mp_limb_t      neg[1+NUM_LIMBS+MAX_ZEROS];
  123.   mpz_t          z;
  124.   unsigned long  i;
  125.   int            zeros, low1;
  126.   int            got, want;
  127.   mpz_init (z);
  128.   for (zeros = 0; zeros <= MAX_ZEROS; zeros++)
  129.     {
  130.       MPN_ZERO (pos, numberof(pos));
  131.       mpn_random2 (pos+zeros, (mp_size_t) NUM_LIMBS);
  132.       for (low1 = 0; low1 <= 1; low1++)
  133. {
  134.   if (low1)
  135.     pos[0] |= 1;
  136.   refmpn_neg (neg, pos, (mp_size_t) numberof(neg));
  137.   mpz_set_n (z, neg, (mp_size_t) numberof(neg));
  138.   mpz_neg (z, z);
  139.   for (i = 0; i < numberof(pos)*GMP_NUMB_BITS; i++)
  140.     {
  141.       got = mpz_tstbit (z, i);
  142.       want = refmpn_tstbit (pos, i);
  143.       if (got != want)
  144. {
  145.   printf ("wrong at bit %lu, with %d zerosn", i, zeros);
  146.   printf ("z neg "); debug_mp (z, -16);
  147.   mpz_set_n (z, pos, (mp_size_t) numberof(pos));
  148.   printf ("pos   "); debug_mp (z, -16);
  149.   mpz_set_n (z, neg, (mp_size_t) numberof(neg));
  150.   printf ("neg   "); debug_mp (z, -16);
  151.   exit (1);
  152. }
  153.     }
  154. }
  155.     }
  156.   mpz_clear (z);
  157. }
  158. void
  159. check_single (void)
  160. {
  161.   mpz_t  x;
  162.   int    limb, offset, initial;
  163.   unsigned long  bit;
  164.   mpz_init (x);
  165.   for (limb = 0; limb < 4; limb++)
  166.     {
  167.       for (offset = (limb==0 ? 0 : -2); offset <= 2; offset++)
  168. {
  169.   for (initial = 0; initial >= -1; initial--)
  170.     {
  171.       mpz_set_si (x, (long) initial);
  172.       bit = (unsigned long) limb*GMP_LIMB_BITS + offset;
  173.       mpz_clrbit (x, bit);
  174.       MPZ_CHECK_FORMAT (x);
  175.       if (mpz_tstbit (x, bit) != 0)
  176. {
  177.   printf ("check_single(): expected 0n");
  178.   abort ();
  179. }
  180.       mpz_setbit (x, bit);
  181.       MPZ_CHECK_FORMAT (x);
  182.       if (mpz_tstbit (x, bit) != 1)
  183. {
  184.   printf ("check_single(): expected 1n");
  185.   abort ();
  186. }
  187.       mpz_clrbit (x, bit);
  188.       MPZ_CHECK_FORMAT (x);
  189.       if (mpz_tstbit (x, bit) != 0)
  190. {
  191.   printf ("check_single(): expected 0n");
  192.   abort ();
  193. }
  194.       mpz_combit (x, bit);
  195.       MPZ_CHECK_FORMAT (x);
  196.       if (mpz_tstbit (x, bit) != 1)
  197. {
  198.   printf ("check_single(): expected 1n");
  199.   abort ();
  200. }
  201.       mpz_combit (x, bit);
  202.       MPZ_CHECK_FORMAT (x);
  203.       if (mpz_tstbit (x, bit) != 0)
  204. {
  205.   printf ("check_single(): expected 0n");
  206.   abort ();
  207. }
  208.     }
  209. }
  210.     }
  211.   mpz_clear (x);
  212. }
  213. void
  214. check_random (int argc, char *argv[])
  215. {
  216.   mpz_t x, s0, s1, s2, s3, m;
  217.   mp_size_t xsize;
  218.   int i;
  219.   int reps = 100000;
  220.   int bit0, bit1, bit2, bit3;
  221.   unsigned long int bitindex;
  222.   const char  *s = "";
  223.   if (argc == 2)
  224.     reps = atoi (argv[1]);
  225.   mpz_init (x);
  226.   mpz_init (s0);
  227.   mpz_init (s1);
  228.   mpz_init (s2);
  229.   mpz_init (s3);
  230.   mpz_init (m);
  231.   for (i = 0; i < reps; i++)
  232.     {
  233.       xsize = urandom () % (2 * SIZE) - SIZE;
  234.       mpz_random2 (x, xsize);
  235.       bitindex = urandom () % SIZE;
  236.       mpz_set (s0, x);
  237.       bit0 = mpz_tstbit (x, bitindex);
  238.       mpz_setbit (x, bitindex);
  239.       MPZ_CHECK_FORMAT (x);
  240.       mpz_set (s1, x);
  241.       bit1 = mpz_tstbit (x, bitindex);
  242.       mpz_clrbit (x, bitindex);
  243.       MPZ_CHECK_FORMAT (x);
  244.       mpz_set (s2, x);
  245.       bit2 = mpz_tstbit (x, bitindex);
  246.       mpz_setbit (x, bitindex);
  247.       MPZ_CHECK_FORMAT (x);
  248.       mpz_set (s3, x);
  249.       bit3 = mpz_tstbit (x, bitindex);
  250. #define FAIL(str) do { s = str; goto fail; } while (0)
  251.       if (bit1 != 1)  FAIL ("bit1 != 1");
  252.       if (bit2 != 0)  FAIL ("bit2 != 0");
  253.       if (bit3 != 1)  FAIL ("bit3 != 1");
  254.       if (bit0 == 0)
  255. {
  256.   if (mpz_cmp (s0, s1) == 0 || mpz_cmp (s0, s2) != 0 || mpz_cmp (s0, s3) == 0)
  257.     abort ();
  258. }
  259.       else
  260. {
  261.   if (mpz_cmp (s0, s1) != 0 || mpz_cmp (s0, s2) == 0 || mpz_cmp (s0, s3) != 0)
  262.     abort ();
  263. }
  264.       if (mpz_cmp (s1, s2) == 0 || mpz_cmp (s1, s3) != 0)
  265. abort ();
  266.       if (mpz_cmp (s2, s3) == 0)
  267. abort ();
  268.       mpz_ui_pow_ui (m, 2L, bitindex);
  269.       MPZ_CHECK_FORMAT (m);
  270.       mpz_ior (x, s2, m);
  271.       MPZ_CHECK_FORMAT (x);
  272.       if (mpz_cmp (x, s3) != 0)
  273. abort ();
  274.       mpz_com (m, m);
  275.       MPZ_CHECK_FORMAT (m);
  276.       mpz_and (x, s1, m);
  277.       MPZ_CHECK_FORMAT (x);
  278.       if (mpz_cmp (x, s2) != 0)
  279. abort ();
  280.     }
  281.   mpz_clear (x);
  282.   mpz_clear (s0);
  283.   mpz_clear (s1);
  284.   mpz_clear (s2);
  285.   mpz_clear (s3);
  286.   mpz_clear (m);
  287.   return;
  288.  fail:
  289.   printf ("%sn", s);
  290.   printf ("bitindex = %lun", bitindex);
  291.   printf ("x = "); mpz_out_str (stdout, -16, x); printf (" hexn");
  292.   exit (1);
  293. }
  294. int
  295. main (int argc, char *argv[])
  296. {
  297.   tests_start ();
  298.   mp_trace_base = -16;
  299.   check_clr_extend ();
  300.   check_com_negs ();
  301.   check_tstbit ();
  302.   check_random (argc, argv);
  303.   check_single ();
  304.   tests_end ();
  305.   exit (0);
  306. }