1/* Test for mpn_invert function.
2
3   Contributed to the GNU project by Marco Bodrato.
4
5Copyright 2009 Free Software Foundation, Inc.
6
7This file is part of the GNU MP Library.
8
9The GNU MP Library is free software; you can redistribute it and/or modify
10it under the terms of the GNU Lesser General Public License as published by
11the Free Software Foundation; either version 3 of the License, or (at your
12option) any later version.
13
14The GNU MP Library is distributed in the hope that it will be useful, but
15WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
16or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
17License for more details.
18
19You should have received a copy of the GNU Lesser General Public License
20along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
21
22
23#include "gmp.h"
24#include "gmp-impl.h"
25#include "tests.h"
26
27#include <stdlib.h>
28#include <stdio.h>
29
30/* Sizes are up to 2^SIZE_LOG limbs */
31#ifndef SIZE_LOG
32#define SIZE_LOG 12
33#endif
34
35#ifndef COUNT
36#define COUNT 1000
37#endif
38
39#define MAX_N (1L << SIZE_LOG)
40#define MIN_N 1
41
42
43static int
44invert_valid (mp_srcptr ip, mp_srcptr dp, mp_size_t n)
45{
46  mp_ptr tp;
47  int cy;
48  TMP_DECL;
49
50  TMP_MARK;
51  tp = TMP_ALLOC_LIMBS (2*n);
52
53  refmpn_mul (tp, ip, n, dp, n);
54  cy  = refmpn_add_n (tp + n, tp + n, dp, n); /* This must not give a carry. */
55  cy -= refmpn_add (tp, tp, 2*n, dp, n); /* This must give a carry. */
56  TMP_FREE;
57
58  return (cy == -1);
59}
60
61/*
62  Chech the result of the mpn_invert function in the library.
63*/
64
65int
66main (int argc, char **argv)
67{
68  mp_ptr ip, dp, scratch;
69  int count = COUNT;
70  int test;
71  gmp_randstate_ptr rands;
72  TMP_DECL;
73  TMP_MARK;
74
75  if (argc > 1)
76    {
77      char *end;
78      count = strtol (argv[1], &end, 0);
79      if (*end || count <= 0)
80	{
81	  fprintf (stderr, "Invalid test count: %s.\n", argv[1]);
82	  return 1;
83	}
84    }
85
86  tests_start ();
87  rands = RANDS;
88
89  dp = TMP_ALLOC_LIMBS (MAX_N);
90  ip = 1+TMP_ALLOC_LIMBS (MAX_N + 2);
91  scratch
92    = 1+TMP_ALLOC_LIMBS (mpn_invert_itch (MAX_N) + 2);
93
94  for (test = 0; test < count; test++)
95    {
96      unsigned size_min;
97      unsigned size_range;
98      mp_size_t n;
99      mp_size_t itch;
100      mp_limb_t i_before, i_after, s_before, s_after;
101
102      for (size_min = 1; (1L << size_min) < MIN_N; size_min++)
103	;
104
105      /* We generate an in the MIN_N <= n <= (1 << size_range). */
106      size_range = size_min
107	+ gmp_urandomm_ui (rands, SIZE_LOG + 1 - size_min);
108
109      n = MIN_N
110	+ gmp_urandomm_ui (rands, (1L << size_range) + 1 - MIN_N);
111
112      mpn_random2 (dp, n);
113
114      mpn_random2 (ip-1, n + 2);
115      i_before = ip[-1];
116      i_after = ip[n];
117
118      itch = mpn_invert_itch (n);
119      ASSERT_ALWAYS (itch <= mpn_invert_itch (MAX_N));
120      mpn_random2 (scratch-1, itch+2);
121      s_before = scratch[-1];
122      s_after = scratch[itch];
123
124      dp[n-1] |= GMP_NUMB_HIGHBIT;
125      mpn_invert (ip, dp, n, scratch);
126      if (ip[-1] != i_before || ip[n] != i_after
127	  || scratch[-1] != s_before || scratch[itch] != s_after
128	  || ! invert_valid(ip, dp, n))
129	{
130	  printf ("ERROR in test %d, n = %d\n",
131		  test, (int) n);
132	  if (ip[-1] != i_before)
133	    {
134	      printf ("before ip:"); mpn_dump (ip -1, 1);
135	      printf ("keep:   "); mpn_dump (&i_before, 1);
136	    }
137	  if (ip[n] != i_after)
138	    {
139	      printf ("after ip:"); mpn_dump (ip + n, 1);
140	      printf ("keep:   "); mpn_dump (&i_after, 1);
141	    }
142	  if (scratch[-1] != s_before)
143	    {
144	      printf ("before scratch:"); mpn_dump (scratch-1, 1);
145	      printf ("keep:   "); mpn_dump (&s_before, 1);
146	    }
147	  if (scratch[itch] != s_after)
148	    {
149	      printf ("after scratch:"); mpn_dump (scratch + itch, 1);
150	      printf ("keep:   "); mpn_dump (&s_after, 1);
151	    }
152	  mpn_dump (dp, n);
153	  mpn_dump (ip, n);
154
155	  abort();
156	}
157    }
158  TMP_FREE;
159  tests_end ();
160  return 0;
161}
162