tests/mpn/toom-shared.h

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