tests/mpn/t-invert.c

   1 /* Test for mpn_invert function.
   2
   3    Contributed to the GNU project by Marco Bodrato.
   4
   5 Copyright 2009 Free Software Foundation, Inc.
   6
   7 This file is part of the GNU MP Library.
   8
   9 The GNU MP Library is free software; you can redistribute it and/or modify
  10 it under the terms of the GNU Lesser General Public License as published by
  11 the Free Software Foundation; either version 3 of the License, or (at your
  12 option) any later version.
  13
  14 The GNU MP Library is distributed in the hope that it will be useful, but
  15 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  16 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  17 License for more details.
  18
  19 You should have received a copy of the GNU Lesser General Public License
  20 along 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
  43 static int
  44 invert_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
  65 int
  66 main (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 }