Line data    Source code

       1             : #include "config.h"
       2             : #include <stdio.h>
       3             : #include <stdlib.h>
       4             : #include <limits.h> /* for LONG_MAX */
       5             : #include <assert.h>
       6             : #include <time.h>
       7             : #include <string.h>
       8             : 
       9             : #if TIME_WITH_SYS_TIME
      10             : # include <sys/time.h>
      11             : # include <time.h>
      12             : #else
      13             : # if HAVE_SYS_TIME_H
      14             : #  include <sys/time.h>
      15             : # else
      16             : #  include <time.h>
      17             : # endif
      18             : #endif
      19             : 
      20             : #define LOOPCOUNT 10000000UL
      21             : #define MAXSIZE 20
      22             : 
      23             : int tune_mul[MAXSIZE+1], tune_sqr[MAXSIZE+1], redc_n_ok[MAXSIZE+1];
      24             : int verbose = 0;
      25             : 
      26             : #include <gmp.h>
      27             : #ifdef USE_ASM_REDC
      28             : #include "mulredc.h"
      29             : #endif
      30             : #include "mpmod.h"
      31             : #include "ecm-gmp.h"
      32             : 
      33             : #ifdef HAVE___GMPN_REDC_N
      34             : #ifndef __gmpn_redc_N
      35             : void __gmpn_redc_n (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr);
      36             : #endif
      37             : #endif
      38             : 
      39             : /* cputime () gives the elapsed time in milliseconds */
      40             : 
      41             : #if defined (_WIN32)
      42             : /* First case - GetProcessTimes () is the only known way of getting process
      43             :  * time (as opposed to calendar time) under mingw32 */
      44             : 
      45             : #include <windows.h>
      46             : 
      47             : long
      48             : cputime ()
      49             : {
      50             :   FILETIME lpCreationTime, lpExitTime, lpKernelTime, lpUserTime;
      51             :   ULARGE_INTEGER n;
      52             : 
      53             :   HANDLE hProcess = GetCurrentProcess();
      54             :   
      55             :   GetProcessTimes (hProcess, &lpCreationTime, &lpExitTime, &lpKernelTime,
      56             :       &lpUserTime);
      57             : 
      58             :   /* copy FILETIME to a ULARGE_INTEGER as recommended by MSDN docs */
      59             :   n.u.LowPart = lpUserTime.dwLowDateTime;
      60             :   n.u.HighPart = lpUserTime.dwHighDateTime;
      61             : 
      62             :   /* lpUserTime is in units of 100 ns. Return time in milliseconds */
      63             :   return (long) (n.QuadPart / 10000);
      64             : }
      65             : 
      66             : #elif defined (HAVE_GETRUSAGE)
      67             : /* Next case: getrusage () has higher resolution than clock () and so is
      68             :    preferred. */
      69             : 
      70             : #ifdef HAVE_SYS_TYPES_H
      71             : # include <sys/types.h>
      72             : #endif
      73             : #ifdef HAVE_SYS_RESOURCE_H
      74             : # include <sys/resource.h>
      75             : #endif
      76             : 
      77             : long
      78         937 : cputime ()
      79             : {
      80             :   struct rusage rus;
      81             : 
      82         937 :   getrusage (RUSAGE_SELF, &rus);
      83             :   /* This overflows a 32 bit signed int after 2147483s = 24.85 days */
      84         937 :   return rus.ru_utime.tv_sec * 1000L + rus.ru_utime.tv_usec / 1000L;
      85             : }
      86             : 
      87             : #else
      88             : /* Resort to clock (), which on some systems may return calendar time. */
      89             : 
      90             : long
      91             : cputime ()
      92             : {
      93             :   /* Return time in milliseconds */
      94             :   return (long) (clock () * (1000. / (double) CLOCKS_PER_SEC));
      95             : }
      96             : 
      97             : #endif /* defining cputime () */
      98             : 
      99          20 : void bench(mp_size_t N)
     100             : {
     101             :   mp_limb_t *x, *y, *z, *zref, *m, *invm, *tmp;
     102             :   unsigned long i;
     103             :   unsigned long iter;
     104             :   long tmul, tsqr, tredc_1, t_mulredc_1, t_sqrredc_1;
     105          20 :   long tmul_best = LONG_MAX, tsqr_best = LONG_MAX, tredc_best = LONG_MAX;
     106             :   mpz_t M, B;
     107             : #ifdef USE_ASM_REDC
     108             :   long t2;
     109             : #endif
     110             : #ifdef HAVE_NATIVE_MULREDC1_N
     111          20 :   long t3 = 0;
     112             : #endif
     113             : #ifdef HAVE___GMPN_REDC_2
     114             :   long tredc_2, t_mulredc_2, t_sqrredc_2;
     115             : #endif
     116             : #ifdef HAVE___GMPN_REDC_N
     117          20 :   long tredc_n = LONG_MAX, t_mulredc_n, t_sqrredc_n;
     118             : #endif
     119             :   
     120          20 :   x = (mp_limb_t *) malloc(N*sizeof(mp_limb_t));
     121          20 :   y = (mp_limb_t *) malloc(N*sizeof(mp_limb_t));
     122          20 :   z = (mp_limb_t *) malloc((2*N)*sizeof(mp_limb_t));
     123          20 :   zref = (mp_limb_t *) malloc((2*N)*sizeof(mp_limb_t));
     124          20 :   m = (mp_limb_t *) malloc(N*sizeof(mp_limb_t));
     125          20 :   tmp = (mp_limb_t *) malloc((2*N+2)*sizeof(mp_limb_t));
     126          20 :   invm = (mp_limb_t *) malloc(N*sizeof(mp_limb_t));
     127             :  
     128          20 :   mpn_random(m, N);
     129          20 :   m[0] |= 1UL;
     130          20 :   if (m[N-1] == 0) 
     131           0 :     m[N-1] = 1UL;
     132             : 
     133          20 :   mpz_init (M);
     134          20 :   mpz_init (B);
     135          20 :   mpz_set_ui (M, m[1]);
     136          20 :   mpz_mul_2exp (M, M, GMP_NUMB_BITS);
     137          20 :   mpz_add_ui (M, M, m[0]);
     138          20 :   mpz_set_ui (B, 1);
     139          20 :   mpz_mul_2exp (B, B, 2 * GMP_NUMB_BITS);
     140          20 :   mpz_invert (M, M, B);
     141          20 :   mpz_sub (M, B, M);
     142             : 
     143         230 :   for (i = 0; i < (unsigned) N; i++)
     144         210 :     invm[i] = mpz_getlimbn(M, i);
     145             : 
     146          20 :   tmp[N] = mpn_mul_1 (tmp, m, N, invm[0]); /* {tmp,N+1} should be = -1 mod B */
     147          20 :   mpn_add_1 (tmp, tmp, N + 1, 1); /* now = 0 mod B */
     148             : 
     149          20 :   mpz_clear (M);
     150          20 :   mpz_clear (B);
     151             : 
     152          20 :   mpn_random(x, N);
     153          20 :   mpn_random(y, N);
     154             : 
     155             :   /* we set 'iter' to get about 100ms for each test */
     156          20 :   tmul = cputime();
     157          20 :   i = 0;
     158          20 :   iter = 1;
     159             :   do
     160             :     {
     161         417 :       iter = 2 * iter;
     162    76546465 :       for (; i < iter; i++)
     163    76546048 :         mpn_mul_n (tmp, x, y, N);
     164             :     }
     165         417 :   while (cputime() - tmul < 100);
     166          20 :   iter = (long) (((double) iter * 100.0) / (double) (cputime() - tmul));
     167             : 
     168          20 :   tmul = cputime();
     169    54199432 :   for (i = 0; i < iter; ++i)
     170    54199412 :     mpn_mul_n(tmp, x, y, N);
     171          20 :   tmul = cputime()-tmul;
     172             : 
     173          20 :   tsqr = cputime();
     174    54199432 :   for (i = 0; i < iter; ++i)
     175    54199412 :     mpn_sqr (tmp, x, N);
     176          20 :   tsqr = cputime()-tsqr;
     177             : 
     178             :   /* compute reference redc result */
     179          20 :   mpn_mul_n (zref, x, y, N);
     180       13460 :   for (i = 0; i < (unsigned long) N * GMP_NUMB_BITS; i++)
     181             :     {
     182       13440 :       mp_limb_t cy = 0;
     183       13440 :       if (zref[0] & 1)
     184        6695 :         cy = mpn_add (zref, zref, 2*N, m, N);
     185       13440 :       mpn_rshift (zref, zref, 2*N, 1);
     186       13440 :       zref[2*N-1] |= cy << (GMP_NUMB_BITS - 1);
     187             :     }
     188             : 
     189             : #ifdef HAVE___GMPN_REDC_1
     190          20 :   mpn_mul_n(tmp, x, y, N);
     191          20 :   REDC1(z, tmp, m, N, invm[0]);
     192             :   ASSERT (mpn_cmp (z, zref, N) == 0);
     193          20 :   tredc_1 = cputime();
     194    54199432 :   for (i = 0; i < iter; ++i)
     195    54199412 :     REDC1(z, tmp, m, N, invm[0]);
     196          20 :   tredc_1 = cputime()-tredc_1;
     197          20 :   if (tredc_1 < tredc_best)
     198          20 :     tredc_best = tredc_1;
     199             : #endif
     200             : 
     201             : #ifdef HAVE___GMPN_REDC_2
     202          20 :   mpn_mul_n(tmp, x, y, N);
     203          20 :   REDC2 (z, tmp, m, N, invm);
     204             :   ASSERT (mpn_cmp (z, zref, N) == 0);
     205          20 :   tredc_2 = cputime();
     206    54199432 :   for (i = 0; i < iter; ++i)
     207    54199412 :     REDC2 (z, tmp, m, N, invm);
     208          20 :   tredc_2 = cputime() - tredc_2;
     209          20 :   if (tredc_2 < tredc_best)
     210           0 :     tredc_best = tredc_2;
     211             : #endif
     212             : 
     213             : /* GMP uses the opposite convention for the precomputed inverse in redc_n
     214             :    wrt redc_1 or redc_2, which gives wrong results so far. */
     215             : #ifdef HAVE___GMPN_REDC_N
     216          20 :   mpn_mul_n(tmp, x, y, N);
     217          20 :   __gmpn_redc_n (z, tmp, m, N, invm);
     218          20 :   if (mpn_cmp (z, zref, N) != 0)
     219          20 :     redc_n_ok[N] = 0;
     220             :   else
     221             :     {
     222           0 :       redc_n_ok[N] = 1;
     223           0 :       tredc_n = cputime();
     224           0 :       for (i = 0; i < iter; ++i)
     225           0 :         __gmpn_redc_n (z, tmp, m, N, invm);
     226           0 :       tredc_n = cputime()-tredc_n;
     227           0 :       if (tredc_n < tredc_best)
     228           0 :         tredc_best = tredc_n;
     229             :     }
     230             : #endif
     231             : 
     232             : #ifdef USE_ASM_REDC
     233             :   /* Mixed mul and redc */
     234          20 :   t2 = cputime();
     235          20 :   switch (N) {
     236           1 :    case 1:
     237    13751817 :     for (i=0; i < iter; ++i) {
     238    13751816 :       mulredc1(z, x[0], y[0], m[0], invm[0]);
     239    13751816 :       x[0] += tmp[0];
     240             :     }
     241           1 :     break;
     242           1 :    case 2:
     243    10292771 :     for (i=0; i < iter; ++i) {
     244    10292770 :       mulredc2(z, x, y, m, invm[0]);
     245    10292770 :       x[0] += tmp[0];
     246             :     }
     247           1 :     break;
     248           1 :    case 3:
     249     7231559 :     for (i=0; i < iter; ++i) {
     250     7231558 :       mulredc3(z, x, y, m, invm[0]);
     251     7231558 :       x[0] += tmp[0];
     252             :     }
     253           1 :     break;
     254           1 :    case 4:
     255     5343063 :     for (i=0; i < iter; ++i) {
     256     5343062 :       mulredc4(z, x, y, m, invm[0]);
     257     5343062 :       x[0] += tmp[0];
     258             :     }
     259           1 :     break;
     260           1 :    case 5:
     261     3679215 :     for (i=0; i < iter; ++i) {
     262     3679214 :       mulredc5(z, x, y, m, invm[0]);
     263     3679214 :       x[0] += tmp[0];
     264             :     }
     265           1 :     break;
     266           1 :    case 6:
     267     2796203 :     for (i=0; i < iter; ++i) {
     268     2796202 :       mulredc6(z, x, y, m, invm[0]);
     269     2796202 :       x[0] += tmp[0];
     270             :     }
     271           1 :     break;
     272           1 :    case 7:
     273     2107691 :     for (i=0; i < iter; ++i) {
     274     2107690 :       mulredc7(z, x, y, m, invm[0]);
     275     2107690 :       x[0] += tmp[0];
     276             :     }
     277           1 :     break;
     278           1 :    case 8:
     279     1588752 :     for (i=0; i < iter; ++i) {
     280     1588751 :       mulredc8(z, x, y, m, invm[0]);
     281     1588751 :       x[0] += tmp[0];
     282             :     }
     283           1 :     break;
     284           1 :    case 9:
     285     1335766 :     for (i=0; i < iter; ++i) {
     286     1335765 :       mulredc9(z, x, y, m, invm[0]);
     287     1335765 :       x[0] += tmp[0];
     288             :     }
     289           1 :     break;
     290           1 :    case 10:
     291     1081007 :     for (i=0; i < iter; ++i) {
     292     1081006 :       mulredc10(z, x, y, m, invm[0]);
     293     1081006 :       x[0] += tmp[0];
     294             :     }
     295           1 :     break;
     296           1 :    case 11:
     297      881157 :     for (i=0; i < iter; ++i) {
     298      881156 :       mulredc11(z, x, y, m, invm[0]);
     299      881156 :       x[0] += tmp[0];
     300             :     }
     301           1 :     break;
     302           1 :    case 12:
     303      748983 :     for (i=0; i < iter; ++i) {
     304      748982 :       mulredc12(z, x, y, m, invm[0]);
     305      748982 :       x[0] += tmp[0];
     306             :     }
     307           1 :     break;
     308           1 :    case 13:
     309      639376 :     for (i=0; i < iter; ++i) {
     310      639375 :       mulredc13(z, x, y, m, invm[0]);
     311      639375 :       x[0] += tmp[0];
     312             :     }
     313           1 :     break;
     314           1 :    case 14:
     315      560736 :     for (i=0; i < iter; ++i) {
     316      560735 :       mulredc14(z, x, y, m, invm[0]);
     317      560735 :       x[0] += tmp[0];
     318             :     }
     319           1 :     break;
     320           1 :    case 15:
     321      476626 :     for (i=0; i < iter; ++i) {
     322      476625 :       mulredc15(z, x, y, m, invm[0]);
     323      476625 :       x[0] += tmp[0];
     324             :     }
     325           1 :     break;
     326           1 :    case 16:
     327      419431 :     for (i=0; i < iter; ++i) {
     328      419430 :       mulredc16(z, x, y, m, invm[0]);
     329      419430 :       x[0] += tmp[0];
     330             :     }
     331           1 :     break;
     332           1 :    case 17:
     333      371836 :     for (i=0; i < iter; ++i) {
     334      371835 :       mulredc17(z, x, y, m, invm[0]);
     335      371835 :       x[0] += tmp[0];
     336             :     }
     337           1 :     break;
     338           1 :    case 18:
     339      329741 :     for (i=0; i < iter; ++i) {
     340      329740 :       mulredc18(z, x, y, m, invm[0]);
     341      329740 :       x[0] += tmp[0];
     342             :     }
     343           1 :     break;
     344           1 :    case 19:
     345      296208 :     for (i=0; i < iter; ++i) {
     346      296207 :       mulredc19(z, x, y, m, invm[0]);
     347      296207 :       x[0] += tmp[0];
     348             :     }
     349           1 :     break;
     350           1 :    case 20:
     351      267494 :     for (i=0; i < iter; ++i) {
     352      267493 :       mulredc20(z, x, y, m, invm[0]);
     353      267493 :       x[0] += tmp[0];
     354             :     }
     355           1 :     break;
     356           0 :    default:
     357           0 :     for (i=0; i < iter; ++i) {
     358           0 :       mulredc20(z, x, y, m,  invm[0]);
     359           0 :       x[0] += tmp[0];
     360             :     }
     361             :   }
     362          20 :   t2 = cputime()-t2;
     363          20 :   if (t2 < tmul_best)
     364             :     {
     365          20 :       tmul_best = t2;
     366          20 :       tune_mul[N] = MPMOD_MULREDC;
     367             :     }
     368          20 :   if (t2 < tsqr_best)
     369             :     {
     370          20 :       tsqr_best = t2;
     371          20 :       tune_sqr[N] = MPMOD_MULREDC;
     372             :     }
     373             : #endif
     374             :   
     375             :   /* Mul followed by mpn_redc_1 */
     376             : #ifdef HAVE___GMPN_REDC_1
     377          20 :   t_mulredc_1 = cputime();
     378    54199432 :   for (i = 0; i < iter; ++i) {
     379    54199412 :     mpn_mul_n(tmp, x, y, N);
     380    54199412 :     __gmpn_redc_1 (z, tmp, m, N, invm[0]);
     381    54199412 :     x[0] += tmp[0];
     382             :   }
     383          20 :   t_mulredc_1 = cputime()-t_mulredc_1;
     384          20 :   if (t_mulredc_1 < tmul_best)
     385             :     {
     386          13 :       tune_mul[N] = MPMOD_MUL_REDC1;
     387          13 :       tmul_best = t_mulredc_1;
     388             :     }
     389             : #endif
     390             :   
     391             :   /* Mul followed by mpn_redc_2 */
     392             : #ifdef HAVE___GMPN_REDC_2
     393          20 :   t_mulredc_2 = cputime();
     394    54199432 :   for (i = 0; i < iter; ++i) {
     395    54199412 :     mpn_mul_n(tmp, x, y, N);
     396    54199412 :     __gmpn_redc_2 (z, tmp, m, N, invm);
     397    54199412 :     x[0] += tmp[0];
     398             :   }
     399          20 :   t_mulredc_2 = cputime()-t_mulredc_2;
     400          20 :   if (t_mulredc_2 < tmul_best)
     401             :     {
     402           0 :       tune_mul[N] = MPMOD_MUL_REDC2;
     403           0 :       tmul_best = t_mulredc_2;
     404             :     }
     405             : #endif
     406             :   
     407             :   /* Mul followed by mpn_redc_n */
     408             : #ifdef HAVE___GMPN_REDC_N
     409          20 :   t_mulredc_n = cputime();
     410    54199432 :   for (i = 0; i < iter; ++i)
     411             :     {
     412    54199412 :       mpn_mul_n (tmp, x, y, N);
     413    54199412 :       __gmpn_redc_n (z, tmp, m, N, invm);
     414             :     }
     415          20 :   t_mulredc_n = cputime()-t_mulredc_n;
     416          20 :   if (redc_n_ok[N] && t_mulredc_n < tmul_best)
     417             :     {
     418           0 :       tune_mul[N] = MPMOD_MUL_REDCN;
     419           0 :       tmul_best = t_mulredc_n;
     420             :     }
     421             : #endif
     422             :   
     423             :   /* Sqr followed by mpn_redc_1 */
     424             : #ifdef HAVE___GMPN_REDC_1
     425          20 :   t_sqrredc_1 = cputime();
     426    54199432 :   for (i = 0; i < iter; ++i) {
     427    54199412 :     mpn_sqr(tmp, x, N);
     428    54199412 :     __gmpn_redc_1 (z, tmp, m, N, invm[0]);
     429    54199412 :     x[0] += tmp[0];
     430             :   }
     431          20 :   t_sqrredc_1 = cputime()-t_sqrredc_1;
     432          20 :   if (t_sqrredc_1 < tsqr_best)
     433             :     {
     434          16 :       tune_sqr[N] = MPMOD_MUL_REDC1;
     435          16 :       tsqr_best = t_sqrredc_1;
     436             :     }
     437             : #endif
     438             :   
     439             :   /* Sqr followed by mpn_redc_2 */
     440             : #ifdef HAVE___GMPN_REDC_2
     441          20 :   t_sqrredc_2 = cputime();
     442    54199432 :   for (i = 0; i < iter; ++i) {
     443    54199412 :     mpn_sqr(tmp, x, N);
     444    54199412 :     __gmpn_redc_2 (z, tmp, m, N, invm);
     445    54199412 :     x[0] += tmp[0];
     446             :   }
     447          20 :   t_sqrredc_2 = cputime()-t_sqrredc_2;
     448          20 :   if (t_sqrredc_2 < tsqr_best)
     449             :     {
     450           0 :       tune_sqr[N] = MPMOD_MUL_REDC2;
     451           0 :       tsqr_best = t_sqrredc_2;
     452             :     }
     453             : #endif
     454             :   
     455             :   /* Sqr followed by mpn_redc_n */
     456             : #ifdef HAVE___GMPN_REDC_N
     457          20 :   t_sqrredc_n = cputime();
     458    54199432 :   for (i = 0; i < iter; ++i)
     459             :     {
     460    54199412 :       mpn_sqr (tmp, x, N);
     461    54199412 :       __gmpn_redc_n (z, tmp, m, N, invm);
     462             :     }
     463          20 :   t_sqrredc_n = cputime()-t_sqrredc_n;
     464          20 :   if (redc_n_ok[N] && t_sqrredc_n < tsqr_best)
     465             :     {
     466           0 :       tune_sqr[N] = MPMOD_MUL_REDCN;
     467           0 :       tsqr_best = t_sqrredc_n;
     468             :     }
     469             : #endif
     470             :   
     471             : #ifdef HAVE_NATIVE_MULREDC1_N
     472             :   /* mulredc1 */
     473          20 :   t3 = cputime();
     474          20 :   switch (N) {
     475           1 :    case 1:
     476    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     477    10000000 :       mulredc1(z, x[0], y[0], m[0], invm[0]);
     478    10000000 :       x[0] += tmp[0];
     479             :     }
     480           1 :     break;
     481           1 :    case 2:
     482    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     483    10000000 :       mulredc1_2(z, x[0], y, m, invm[0]);
     484    10000000 :       x[0] += tmp[0];
     485             :     }
     486           1 :     break;
     487           1 :    case 3:
     488    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     489    10000000 :       mulredc1_3(z, x[0], y, m, invm[0]);
     490    10000000 :       x[0] += tmp[0];
     491             :     }
     492           1 :     break;
     493           1 :    case 4:
     494    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     495    10000000 :       mulredc1_4(z, x[0], y, m, invm[0]);
     496    10000000 :       x[0] += tmp[0];
     497             :     }
     498           1 :     break;
     499           1 :    case 5:
     500    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     501    10000000 :       mulredc1_5(z, x[0], y, m, invm[0]);
     502    10000000 :       x[0] += tmp[0];
     503             :     }
     504           1 :     break;
     505           1 :    case 6:
     506    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     507    10000000 :       mulredc1_6(z, x[0], y, m, invm[0]);
     508    10000000 :       x[0] += tmp[0];
     509             :     }
     510           1 :     break;
     511           1 :    case 7:
     512    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     513    10000000 :       mulredc1_7(z, x[0], y, m, invm[0]);
     514    10000000 :       x[0] += tmp[0];
     515             :     }
     516           1 :     break;
     517           1 :    case 8:
     518    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     519    10000000 :       mulredc1_8(z, x[0], y, m, invm[0]);
     520    10000000 :       x[0] += tmp[0];
     521             :     }
     522           1 :     break;
     523           1 :    case 9:
     524    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     525    10000000 :       mulredc1_9(z, x[0], y, m, invm[0]);
     526    10000000 :       x[0] += tmp[0];
     527             :     }
     528           1 :     break;
     529           1 :    case 10:
     530    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     531    10000000 :       mulredc1_10(z, x[0], y, m, invm[0]);
     532    10000000 :       x[0] += tmp[0];
     533             :     }
     534           1 :     break;
     535           1 :    case 11:
     536    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     537    10000000 :       mulredc1_11(z, x[0], y, m, invm[0]);
     538    10000000 :       x[0] += tmp[0];
     539             :     }
     540           1 :     break;
     541           1 :    case 12:
     542    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     543    10000000 :       mulredc1_12(z, x[0], y, m, invm[0]);
     544    10000000 :       x[0] += tmp[0];
     545             :     }
     546           1 :     break;
     547           1 :    case 13:
     548    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     549    10000000 :       mulredc1_13(z, x[0], y, m, invm[0]);
     550    10000000 :       x[0] += tmp[0];
     551             :     }
     552           1 :     break;
     553           1 :    case 14:
     554    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     555    10000000 :       mulredc1_14(z, x[0], y, m, invm[0]);
     556    10000000 :       x[0] += tmp[0];
     557             :     }
     558           1 :     break;
     559           1 :    case 15:
     560    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     561    10000000 :       mulredc1_15(z, x[0], y, m, invm[0]);
     562    10000000 :       x[0] += tmp[0];
     563             :     }
     564           1 :     break;
     565           1 :    case 16:
     566    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     567    10000000 :       mulredc1_16(z, x[0], y, m, invm[0]);
     568    10000000 :       x[0] += tmp[0];
     569             :     }
     570           1 :     break;
     571           1 :    case 17:
     572    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     573    10000000 :       mulredc1_17(z, x[0], y, m, invm[0]);
     574    10000000 :       x[0] += tmp[0];
     575             :     }
     576           1 :     break;
     577           1 :    case 18:
     578    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     579    10000000 :       mulredc1_18(z, x[0], y, m, invm[0]);
     580    10000000 :       x[0] += tmp[0];
     581             :     }
     582           1 :     break;
     583           1 :    case 19:
     584    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     585    10000000 :       mulredc1_19(z, x[0], y, m, invm[0]);
     586    10000000 :       x[0] += tmp[0];
     587             :     }
     588           1 :     break;
     589           1 :    case 20:
     590    10000001 :     for (i=0; i<LOOPCOUNT; ++i) {
     591    10000000 :       mulredc1_20(z, x[0], y, m, invm[0]);
     592    10000000 :       x[0] += tmp[0];
     593             :     }
     594           1 :     break;
     595          20 :    default: ;
     596             :   }
     597          20 :   t3 = cputime() - t3;
     598             : #endif /* ifdef HAVE_NATIVE_MULREDC1_N */
     599             : 
     600          20 :   if (verbose)
     601             :     {
     602          20 :       fprintf (stderr, "******************\n");
     603          20 :       fprintf (stderr, "Time in microseconds per call, size=%lu (iter=%lu):\n",
     604             :                N, iter);
     605             : 
     606             :       /* basic operations */
     607          20 :       fprintf (stderr, "mpn_mul_n  = %.3f\n",
     608          20 :                (double) tmul * 1e3 / (double) iter);
     609          20 :       fprintf (stderr, "mpn_sqr    = %.3f\n",
     610          20 :                (double) tsqr * 1e3 / (double) iter);
     611             : #ifdef HAVE___GMPN_REDC_1
     612          20 :       fprintf (stderr, "mpn_redc_1 = %.3f",
     613          20 :                (double) tredc_1 * 1e3 / (double) iter);
     614          20 :       if (tredc_1 == tredc_best)
     615          20 :         fprintf (stderr, " *");
     616          20 :       fprintf (stderr, "\n");
     617             : #endif
     618             : #ifdef HAVE___GMPN_REDC_2
     619          20 :       fprintf (stderr, "mpn_redc_2 = %.3f",
     620          20 :                (double) tredc_2 * 1e3 / (double) iter);
     621          20 :       if (tredc_2 == tredc_best)
     622           0 :         fprintf (stderr, " *");
     623          20 :       fprintf (stderr, "\n");
     624             : #endif
     625             : #ifdef HAVE___GMPN_REDC_N
     626          20 :       if (redc_n_ok[N])
     627             :         {
     628           0 :           fprintf (stderr, "mpn_redc_n = %.3f",
     629           0 :                    (double) tredc_n * 1e3 / (double) iter);
     630           0 :           if (tredc_n == tredc_best)
     631           0 :             fprintf (stderr, " *");
     632           0 :           fprintf (stderr, "\n");
     633             :         }
     634             :   else
     635          20 :     fprintf (stderr, "mpn_redc_n = disabled\n");
     636             : #endif
     637             : 
     638          20 :       fprintf (stderr, "\n");
     639             : 
     640             :   /* modular multiplication */
     641             : #ifdef USE_ASM_REDC
     642          20 :       fprintf (stderr, "mulredc    = %.3f",
     643          20 :                (double) t2 * 1e3 / (double) iter);
     644          20 :       if (tmul_best == t2)
     645           7 :         fprintf (stderr, " *");
     646          20 :       fprintf (stderr, "\n");
     647             : #endif
     648             : #ifdef HAVE___GMPN_REDC_1
     649          20 :       fprintf (stderr, "mul+redc_1 = %.3f",
     650          20 :                (double) t_mulredc_1 * 1e3 / (double) iter);
     651          20 :       if (tmul_best == t_mulredc_1)
     652          13 :         fprintf (stderr, " *");
     653          20 :       fprintf (stderr, "\n");
     654             : #endif
     655             : #ifdef HAVE___GMPN_REDC_2
     656          20 :       fprintf (stderr, "mul+redc_2 = %.3f",
     657          20 :                (double) t_mulredc_2 * 1e3 / (double) iter);
     658          20 :       if (tmul_best == t_mulredc_2)
     659           0 :         fprintf (stderr, " *");
     660          20 :       fprintf (stderr, "\n");
     661             : #endif
     662             : #ifdef HAVE___GMPN_REDC_N
     663          20 :       if (redc_n_ok[N])
     664             :         {
     665           0 :           fprintf (stderr, "mul+redc_n = %.3f",
     666           0 :                    (double) t_mulredc_n * 1e3 / (double) iter);
     667           0 :           if (tmul_best == t_mulredc_n)
     668           0 :             fprintf (stderr, " *");
     669           0 :           fprintf (stderr, "\n");
     670             :     }
     671             :   else
     672          20 :     fprintf (stderr, "mul+redc_n = disabled\n");
     673             : #endif
     674             : 
     675          20 :       fprintf (stderr, "\n");
     676             : 
     677             :   /* modular squaring */
     678             : #ifdef USE_ASM_REDC
     679          20 :       fprintf (stderr, "mulredc    = %.3f",
     680          20 :                (double) t2 * 1e3 / (double) iter);
     681          20 :       if (tsqr_best == t2)
     682           4 :         fprintf (stderr, " *");
     683          20 :       fprintf (stderr, "\n");
     684             : #endif
     685             : #ifdef HAVE___GMPN_REDC_1
     686          20 :       fprintf (stderr, "sqr+redc_1 = %.3f",
     687          20 :                (double) t_sqrredc_1 * 1e3 / (double) iter);
     688          20 :       if (tsqr_best == t_sqrredc_1)
     689          16 :         fprintf (stderr, " *");
     690          20 :       fprintf (stderr, "\n");
     691             : #endif
     692             : #ifdef HAVE___GMPN_REDC_2
     693          20 :       fprintf (stderr, "sqr+redc_2 = %.3f",
     694          20 :                (double) t_sqrredc_2 * 1e3 / (double) iter);
     695          20 :       if (tsqr_best == t_sqrredc_2)
     696           0 :         fprintf (stderr, " *");
     697          20 :       fprintf (stderr, "\n");
     698             : #endif
     699             : #ifdef HAVE___GMPN_REDC_N
     700          20 :       if (redc_n_ok[N])
     701             :         {
     702           0 :           fprintf (stderr, "sqr+redc_n = %.3f",
     703           0 :                    (double) t_sqrredc_n * 1e3 / (double) iter);
     704           0 :           if (tsqr_best == t_sqrredc_n)
     705           0 :             fprintf (stderr, " *");
     706           0 :           fprintf (stderr, "\n");
     707             :         }
     708             :   else
     709          20 :     fprintf (stderr, "sqr+redc_n = disabled\n");
     710             : #endif
     711             : 
     712             : #ifdef HAVE_NATIVE_MULREDC1_N
     713             :       /* multiplication of n limbs by one limb */
     714          20 :       fprintf (stderr, "mulredc1   = %.3f\n",
     715          20 :                (double) t3 * 1e3 / (double) LOOPCOUNT);
     716             : #endif
     717          20 :       fflush (stderr);
     718             :     }
     719             :   
     720          20 :   free (tmp);
     721          20 :   free (x);
     722          20 :   free (y);
     723          20 :   free (z);
     724          20 :   free (zref);
     725          20 :   free (m);
     726          20 :   free (invm);
     727          20 : }
     728             : 
     729             : int
     730           1 : main (int argc, char** argv)
     731             : {
     732             :   int i;
     733           1 :   int minsize = 1, maxsize = MAXSIZE;
     734             : 
     735           1 :   if (argc >= 2 && strcmp (argv[1], "-v") == 0)
     736             :     {
     737           1 :       verbose = 1;
     738           1 :       argc --;
     739           1 :       argv ++;
     740             :     }
     741             : 
     742           1 :   if (argc > 1)
     743           0 :     minsize = atoi (argv[1]);
     744           1 :   if (argc > 2)
     745           0 :     maxsize = atoi (argv[2]);
     746             :   
     747          21 :   for (i = minsize; i <= maxsize; ++i)
     748          20 :     bench(i);
     749             : 
     750           1 :   printf ("/* 0:mulredc 1:mul+redc_1 2:mul+redc_2 3:mul+redc_n */\n");
     751           1 :   printf ("#define TUNE_MULREDC_TABLE {0");
     752          21 :   for (i = 1; i <= maxsize; i++)
     753          20 :     printf (",%d", tune_mul[i]);
     754           1 :   printf ("}\n");
     755           1 :   printf ("/* 0:mulredc 1:sqr+redc_1 2:sqr+redc_2 3:sqr+redc_n */\n");
     756           1 :   printf ("#define TUNE_SQRREDC_TABLE {0");
     757          21 :   for (i = 1; i <= maxsize; i++)
     758          20 :     printf (",%d", tune_sqr[i]);
     759           1 :   printf ("}\n");
     760           1 :   fflush (stdout);
     761             : 
     762           1 :   return 0;
     763             : }