t-minvert.c revision 1.1.1.2 
1/* Copyright 2013-2015 Free Software Foundation, Inc.
2
3This file is part of the GNU MP Library test suite.
4
5The GNU MP Library test suite is free software; you can redistribute it
6and/or modify it under the terms of the GNU General Public License as
7published by the Free Software Foundation; either version 3 of the License,
8or (at your option) any later version.
9
10The GNU MP Library test suite is distributed in the hope that it will be
11useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
13Public License for more details.
14
15You should have received a copy of the GNU General Public License along with
16the GNU MP Library test suite.  If not, see https://www.gnu.org/licenses/.  */
17
18#include <stdio.h>
19#include <stdlib.h>		/* for strtol */
20
21#include "gmp-impl.h"
22#include "longlong.h"
23#include "tests/tests.h"
24
25#define MAX_SIZE 50
26
27#define COUNT 200
28
29static void
30mpz_to_mpn (mp_ptr ap, mp_size_t an, const mpz_t b)
31{
32  mp_size_t bn = mpz_size (b);
33  ASSERT_ALWAYS (bn <= an);
34  MPN_COPY_INCR (ap, mpz_limbs_read (b), bn);
35  MPN_ZERO (ap + bn, an - bn);
36}
37
38int
39mpz_eq_mpn (mp_ptr ap, mp_size_t an, const mpz_t b)
40{
41  mp_size_t bn = mpz_size (b);
42
43  return (bn >= 0 && bn <= an
44	  && mpn_cmp (ap, mpz_limbs_read (b), bn) == 0
45	  && (an == bn || mpn_zero_p (ap + bn, an - bn)));
46}
47
48static mp_bitcnt_t
49bit_size (mp_srcptr xp, mp_size_t n)
50{
51  MPN_NORMALIZE (xp, n);
52  return n > 0 ? mpn_sizeinbase (xp, n, 2) : 0;
53}
54
55int
56main (int argc, char **argv)
57{
58  gmp_randstate_ptr rands;
59  long count = COUNT;
60  mp_ptr mp;
61  mp_ptr ap;
62  mp_ptr tp;
63  mp_ptr scratch;
64  mpz_t m, a, r, g;
65  int test;
66  mp_limb_t ran;
67  mp_size_t itch;
68  TMP_DECL;
69
70  tests_start ();
71  rands = RANDS;
72
73
74  TMP_MARK;
75  mpz_init (m);
76  mpz_init (a);
77  mpz_init (r);
78  mpz_init (g);
79
80  TESTS_REPS (count, argv, argc);
81
82  mp = TMP_ALLOC_LIMBS (MAX_SIZE);
83  ap = TMP_ALLOC_LIMBS (MAX_SIZE);
84  tp = TMP_ALLOC_LIMBS (MAX_SIZE);
85  scratch = TMP_ALLOC_LIMBS (mpn_sec_invert_itch (MAX_SIZE) + 1);
86
87  for (test = 0; test < count; test++)
88    {
89      mp_bitcnt_t bits;
90      int rres, tres;
91      mp_size_t n;
92
93      bits = urandom () % (GMP_NUMB_BITS * MAX_SIZE) + 1;
94
95      if (test & 1)
96	mpz_rrandomb (m, rands, bits);
97      else
98	mpz_urandomb (m, rands, bits);
99      if (test & 2)
100	mpz_rrandomb (a, rands, bits);
101      else
102	mpz_urandomb (a, rands, bits);
103
104      mpz_setbit (m, 0);
105      if (test & 4)
106	{
107	  /* Ensure it really is invertible */
108	  if (mpz_sgn (a) == 0)
109	    mpz_set_ui (a, 1);
110	  else
111	    for (;;)
112	      {
113		mpz_gcd (g, a, m);
114		if (mpz_cmp_ui (g, 1) == 0)
115		  break;
116		mpz_remove (a, a, g);
117	      }
118	}
119
120      rres = mpz_invert (r, a, m);
121      if ( (test & 4) && !rres)
122	{
123	  gmp_fprintf (stderr, "test %d: Not invertible!\n"
124		       "m = %Zd\n"
125		       "a = %Zd\n", test, m, a);
126	  abort ();
127	}
128      ASSERT_ALWAYS (! (test & 4) || rres);
129
130      n = (bits + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS;
131      ASSERT_ALWAYS (n <= MAX_SIZE);
132      itch = mpn_sec_invert_itch (n);
133      scratch[itch] = ran = urandom ();
134
135      mpz_to_mpn (ap, n, a);
136      mpz_to_mpn (mp, n, m);
137      tres = mpn_sec_invert (tp, ap, mp, n,
138			     bit_size (ap, n) + bit_size (mp, n),
139			     scratch);
140
141      if (rres != tres || (rres == 1 && !mpz_eq_mpn (tp, n, r)) || ran != scratch[itch])
142	{
143	  gmp_fprintf (stderr, "Test %d failed.\n"
144		       "m = %Zd\n"
145		       "a = %Zd\n", test, m, a);
146	  fprintf (stderr, "ref ret: %d\n"
147		  "got ret: %d\n", rres, tres);
148	  if (rres)
149	    gmp_fprintf (stderr, "ref: %Zd\n", r);
150	  if (tres)
151	    gmp_fprintf (stderr, "got: %Nd\n", tp, n);
152	  if (ran != scratch[itch])
153	    fprintf (stderr, "scratch[itch] changed.\n");
154	  abort ();
155	}
156    }
157
158  TMP_FREE;
159
160  mpz_clear (m);
161  mpz_clear (a);
162  mpz_clear (r);
163  mpz_clear (g);
164
165  tests_end ();
166  return 0;
167}
168