Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux1.fr machine (x86_64 architecture), and agregate them in the final report:

The target is 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - kernel/none - invmod.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 16804-345a01c) Lines: 51 53 96.2 %
Date: 2014-09-20 Functions: 2 2 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 37 42 88.1 %

           Branch data     Line data    Source code
       1                 :            : #line 2 "../src/kernel/none/invmod.c"
       2                 :            : /* Copyright (C) 2003  The PARI group.
       3                 :            : 
       4                 :            : This file is part of the PARI/GP package.
       5                 :            : 
       6                 :            : PARI/GP is free software; you can redistribute it and/or modify it under the
       7                 :            : terms of the GNU General Public License as published by the Free Software
       8                 :            : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       9                 :            : ANY WARRANTY WHATSOEVER.
      10                 :            : 
      11                 :            : Check the License for details. You should have received a copy of it, along
      12                 :            : with the package; see the file 'COPYING'. If not, write to the Free Software
      13                 :            : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      14                 :            : 
      15                 :            : /*==================================
      16                 :            :  * invmod(a,b,res)
      17                 :            :  *==================================
      18                 :            :  *    If a is invertible, return 1, and set res  = a^{ -1 }
      19                 :            :  *    Otherwise, return 0, and set res = gcd(a,b)
      20                 :            :  *
      21                 :            :  * This is sufficiently different from bezout() to be implemented separately
      22                 :            :  * instead of having a bunch of extra conditionals in a single function body
      23                 :            :  * to meet both purposes.
      24                 :            :  */
      25                 :            : 
      26                 :            : #ifdef INVMOD_PARI
      27                 :            : INLINE int
      28                 :    1961934 : invmod_pari(GEN a, GEN b, GEN *res)
      29                 :            : #else
      30                 :            : int
      31                 :    1986891 : invmod(GEN a, GEN b, GEN *res)
      32                 :            : #endif
      33                 :            : {
      34                 :            :   GEN v,v1,d,d1,q,r;
      35                 :            :   pari_sp av, av1;
      36                 :            :   long s;
      37                 :            :   ulong g;
      38                 :            :   ulong xu,xu1,xv,xv1; /* Lehmer stage recurrence matrix */
      39                 :            :   int lhmres; /* Lehmer stage return value */
      40                 :            : 
      41         [ -  + ]:    3948825 :   if (!signe(b)) { *res=absi(a); return 0; }
      42                 :    3948825 :   av = avma;
      43         [ +  + ]:    3948825 :   if (lgefint(b) == 3) /* single-word affair */
      44                 :            :   {
      45                 :    1968238 :     ulong d1 = umodiu(a, uel(b,2));
      46         [ +  + ]:    1968238 :     if (d1 == 0)
      47                 :            :     {
      48         [ +  + ]:        542 :       if (b[2] == 1L)
      49                 :         84 :         { *res = gen_0; return 1; }
      50                 :            :       else
      51                 :        458 :         { *res = absi(b); return 0; }
      52                 :            :     }
      53                 :    1967696 :     g = xgcduu(uel(b,2), d1, 1, &xv, &xv1, &s);
      54                 :            : #ifdef DEBUG_LEHMER
      55                 :            :     err_printf(" <- %lu,%lu\n", uel(b,2), uel(d1,2));
      56                 :            :     err_printf(" -> %lu,%ld,%lu; %lx\n", g,s,xv1,avma);
      57                 :            : #endif
      58                 :    1967696 :     avma = av;
      59         [ +  + ]:    1967696 :     if (g != 1UL) { *res = utoipos(g); return 0; }
      60         [ +  + ]:    1967669 :     xv = xv1 % uel(b,2); if (s < 0) xv = uel(b,2) - xv;
      61                 :    1967669 :     *res = utoipos(xv); return 1;
      62                 :            :   }
      63                 :            : 
      64                 :    1980587 :   (void)new_chunk(lgefint(b));
      65                 :    1980587 :   d = absi(b); d1 = modii(a,d);
      66                 :            : 
      67                 :    1980587 :   v=gen_0; v1=gen_1;        /* general case */
      68                 :            : #ifdef DEBUG_LEHMER
      69                 :            :   err_printf("INVERT: -------------------------\n");
      70                 :            :   output(d1);
      71                 :            : #endif
      72                 :    1980587 :   av1 = avma;
      73                 :            : 
      74 [ +  + ][ +  + ]:    5097601 :   while (lgefint(d) > 3 && signe(d1))
      75                 :            :   {
      76                 :            : #ifdef DEBUG_LEHMER
      77                 :            :     err_printf("Calling Lehmer:\n");
      78                 :            : #endif
      79                 :    3117014 :     lhmres = lgcdii((ulong*)d, (ulong*)d1, &xu, &xu1, &xv, &xv1, ULONG_MAX);
      80         [ +  + ]:    3117014 :     if (lhmres != 0)                /* check progress */
      81                 :            :     {                                /* apply matrix */
      82                 :            : #ifdef DEBUG_LEHMER
      83                 :            :       err_printf("Lehmer returned %d [%lu,%lu;%lu,%lu].\n",
      84                 :            :               lhmres, xu, xu1, xv, xv1);
      85                 :            : #endif
      86 [ +  + ][ +  + ]:    2833330 :       if ((lhmres == 1) || (lhmres == -1))
      87                 :            :       {
      88         [ +  + ]:     124496 :         if (xv1 == 1)
      89                 :            :         {
      90                 :      58867 :           r = subii(d,d1); d=d1; d1=r;
      91                 :      58867 :           a = subii(v,v1); v=v1; v1=a;
      92                 :            :         }
      93                 :            :         else
      94                 :            :         {
      95                 :       3381 :           r = subii(d, mului(xv1,d1)); d=d1; d1=r;
      96                 :       3381 :           a = subii(v, mului(xv1,v1)); v=v1; v1=a;
      97                 :            :         }
      98                 :            :       }
      99                 :            :       else
     100                 :            :       {
     101                 :    2771082 :         r  = subii(muliu(d,xu),  muliu(d1,xv));
     102                 :    2771082 :         a  = subii(muliu(v,xu),  muliu(v1,xv));
     103                 :    2771082 :         d1 = subii(muliu(d,xu1), muliu(d1,xv1)); d = r;
     104                 :    2771082 :         v1 = subii(muliu(v,xu1), muliu(v1,xv1)); v = a;
     105         [ +  + ]:    2771082 :         if (lhmres&1) { togglesign(d);  togglesign(v); }
     106                 :    1407299 :         else          { togglesign(d1); togglesign(v1); }
     107                 :            :       }
     108                 :            :     }
     109                 :            : #ifdef DEBUG_LEHMER
     110                 :            :     else
     111                 :            :       err_printf("Lehmer returned 0.\n");
     112                 :            :     output(d); output(d1); output(v); output(v1);
     113                 :            :     sleep(1);
     114                 :            : #endif
     115                 :            : 
     116 [ +  + ][ +  - ]:    3117014 :     if (lhmres <= 0 && signe(d1))
     117                 :            :     {
     118                 :     340826 :       q = dvmdii(d,d1,&r);
     119                 :            : #ifdef DEBUG_LEHMER
     120                 :            :       err_printf("Full division:\n");
     121                 :            :       printf("  q = "); output(q); sleep (1);
     122                 :            : #endif
     123                 :     340826 :       a = subii(v,mulii(q,v1));
     124                 :     340826 :       v=v1; v1=a;
     125                 :     340826 :       d=d1; d1=r;
     126                 :            :     }
     127         [ -  + ]:    3117014 :     if (gc_needed(av,1))
     128                 :            :     {
     129         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"invmod");
     130                 :          0 :       gerepileall(av1, 4, &d,&d1,&v,&v1);
     131                 :            :     }
     132                 :            :   } /* end while */
     133                 :            : 
     134                 :            :   /* Postprocessing - final sprint */
     135         [ +  + ]:    1980587 :   if (signe(d1))
     136                 :            :   {
     137                 :            :     /* Assertions: lgefint(d)==lgefint(d1)==3, and
     138                 :            :      * gcd(d,d1) is nonzero and fits into one word
     139                 :            :      */
     140                 :    1945288 :     g = xxgcduu(uel(d,2), uel(d1,2), 1, &xu, &xu1, &xv, &xv1, &s);
     141                 :            : #ifdef DEBUG_LEHMER
     142                 :            :     output(d);output(d1);output(v);output(v1);
     143                 :            :     err_printf(" <- %lu,%lu\n", uel(d,2), uel(d1,2));
     144                 :            :     err_printf(" -> %lu,%ld,%lu; %lx\n", g,s,xv1,avma);
     145                 :            : #endif
     146         [ +  + ]:    1945288 :     if (g != 1UL) { avma = av; *res = utoipos(g); return 0; }
     147                 :            :     /* (From the xgcduu() blurb:)
     148                 :            :      * For finishing the multiword modinv, we now have to multiply the
     149                 :            :      * returned matrix  (with properly adjusted signs)  onto the values
     150                 :            :      * v' and v1' previously obtained from the multiword division steps.
     151                 :            :      * Actually, it is sufficient to take the scalar product of [v',v1']
     152                 :            :      * with [u1,-v1], and change the sign if s==1.
     153                 :            :      */
     154                 :    1945259 :     v = subii(muliu(v,xu1),muliu(v1,xv1));
     155         [ +  + ]:    1945259 :     if (s > 0) setsigne(v,-signe(v));
     156                 :    1945259 :     avma = av; *res = modii(v,b);
     157                 :            : #ifdef DEBUG_LEHMER
     158                 :            :     output(*res); fprintfderr("============================Done.\n");
     159                 :            :     sleep(1);
     160                 :            : #endif
     161                 :    1945259 :     return 1;
     162                 :            :   }
     163                 :            :   /* get here when the final sprint was skipped (d1 was zero already) */
     164                 :      35299 :   avma = av;
     165         [ +  + ]:      35299 :   if (!equalii(d,gen_1)) { *res = icopy(d); return 0; }
     166                 :      35263 :   *res = modii(v,b);
     167                 :            : #ifdef DEBUG_LEHMER
     168                 :            :   output(*res); err_printf("============================Done.\n");
     169                 :            :   sleep(1);
     170                 :            : #endif
     171                 :    3948825 :   return 1;
     172                 :            : }
     173                 :            : 

Generated by: LCOV version 1.9