1/* Test mpn_gcdext_1.
2
3Copyright 2019 Free Software Foundation, Inc.
4
5This file is part of the GNU MP Library test suite.
6
7The GNU MP Library test suite is free software; you can redistribute it
8and/or modify it under the terms of the GNU General Public License as
9published by the Free Software Foundation; either version 3 of the License,
10or (at your option) any later version.
11
12The GNU MP Library test suite is distributed in the hope that it will be
13useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
15Public License for more details.
16
17You should have received a copy of the GNU General Public License along with
18the GNU MP Library test suite.  If not, see https://www.gnu.org/licenses/.  */
19
20#include <stdio.h>
21#include <stdlib.h>
22
23#include "gmp-impl.h"
24#include "tests.h"
25
26#ifndef COUNT
27#define COUNT 250000
28#endif
29
30static void
31set_signed_limb (mpz_t r, mp_limb_signed_t x)
32{
33  mpz_t t;
34  mp_limb_t abs_x = ABS_CAST(mp_limb_t, x);
35  mpz_set (r, mpz_roinit_n (t, &abs_x, 1));
36  if (x < 0)
37    mpz_neg (r, r);
38}
39
40static void
41one_test (mp_limb_t a, mp_limb_t b)
42{
43  mp_limb_signed_t s, t;
44  mp_limb_t g;
45
46  g = mpn_gcdext_1 (&s, &t, a, b);
47
48  if (g > 0)
49    {
50      mpz_t d, sz, tz, tmp;
51
52      mpz_init (d);
53      mpz_init (sz);
54      mpz_init (tz);
55
56      set_signed_limb (sz, s);
57      set_signed_limb (tz, t);
58
59      mpz_mul (d, mpz_roinit_n (tmp, &a, 1), sz);
60      mpz_addmul (d, mpz_roinit_n (tmp, &b, 1), tz);
61
62      if (mpz_cmp (d, mpz_roinit_n (tmp, &g, 1)) == 0
63	  && a % g == 0 && b % g == 0)
64	{
65	  mp_limb_t a_div_g = a / g;
66	  mp_limb_t b_div_g = b / g;
67	  mp_limb_t abs_s = ABS_CAST(mp_limb_t, s);
68	  mp_limb_t abs_t = ABS_CAST(mp_limb_t, t);
69	  mpz_mul_ui (sz, sz, 2);
70	  mpz_mul_ui (tz, tz, 2);
71	  if ((abs_s == 1 || mpz_cmpabs (sz, mpz_roinit_n (tmp, &b_div_g, 1)) < 0)
72	       && (abs_t == 1 || mpz_cmpabs (tz, mpz_roinit_n (tmp, &a_div_g, 1)) < 0))
73	    {
74	      mpz_clear (d);
75	      mpz_clear (sz);
76	      mpz_clear (tz);
77
78	      return;
79	    }
80	}
81    }
82  gmp_fprintf (stderr,
83	       "gcdext_1 (0x%Mx, 0x%Mx) failed, got: g = 0x%Mx, s = %s0x%Mx, t = %s0x%Mx\n",
84	       a, b, g,
85	       s < 0 ? "-" : "", ABS_CAST(mp_limb_t, s),
86	       t < 0 ? "-" : "", ABS_CAST(mp_limb_t, t));
87  abort();
88}
89
90int
91main (int argc, char **argv)
92{
93  mpz_t a, b;
94  int count = COUNT;
95  int test;
96  gmp_randstate_ptr rands;
97
98  TESTS_REPS (count, argv, argc);
99
100  tests_start ();
101  rands = RANDS;
102
103  mpz_init (a);
104  mpz_init (b);
105  for (test = 0; test < count; test++)
106    {
107      mp_limb_t al, bl;
108      mp_bitcnt_t asize = 1 + gmp_urandomm_ui(rands, GMP_NUMB_BITS);
109      mp_bitcnt_t bsize = 1 + gmp_urandomm_ui(rands, GMP_NUMB_BITS);
110      if (test & 1)
111	{
112	  mpz_urandomb (a, rands, asize);
113	  mpz_urandomb (b, rands, bsize);
114	}
115      else
116	{
117	  mpz_rrandomb (a, rands, asize);
118	  mpz_rrandomb (b, rands, bsize);
119	}
120
121      al = mpz_getlimbn (a, 0);
122      bl = mpz_getlimbn (b, 0);
123      al += (al == 0);
124      bl += (bl == 0);
125
126      one_test (al, bl);
127    }
128
129  mpz_clear (a);
130  mpz_clear (b);
131
132  tests_end ();
133  return 0;
134}
135