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-bordeaux.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 19588-1c9967d) Lines: 51 53 96.2 %
Date: 2016-09-24 05:54:29 Functions: 2 2 100.0 %
Legend: Lines: hit not hit

          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     4524009 : invmod_pari(GEN a, GEN b, GEN *res)
      29             : #else
      30             : int
      31     2700842 : 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     7224851 :   if (!signe(b)) { *res=absi(a); return 0; }
      42     7224851 :   av = avma;
      43     7224851 :   if (lgefint(b) == 3) /* single-word affair */
      44             :   {
      45     2890750 :     ulong d1 = umodiu(a, uel(b,2));
      46     2890750 :     if (d1 == 0)
      47             :     {
      48         507 :       if (b[2] == 1L)
      49          49 :         { *res = gen_0; return 1; }
      50             :       else
      51         458 :         { *res = absi(b); return 0; }
      52             :     }
      53     2890243 :     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     2890243 :     avma = av;
      59     2890243 :     if (g != 1UL) { *res = utoipos(g); return 0; }
      60     2890223 :     xv = xv1 % uel(b,2); if (s < 0) xv = uel(b,2) - xv;
      61     2890223 :     *res = utoipos(xv); return 1;
      62             :   }
      63             : 
      64     4334101 :   (void)new_chunk(lgefint(b));
      65     4318641 :   d = absi(b); d1 = modii(a,d);
      66             : 
      67     4313172 :   v=gen_0; v1=gen_1;        /* general case */
      68             : #ifdef DEBUG_LEHMER
      69             :   err_printf("INVERT: -------------------------\n");
      70             :   output(d1);
      71             : #endif
      72     4313172 :   av1 = avma;
      73             : 
      74    14382925 :   while (lgefint(d) > 3 && signe(d1))
      75             :   {
      76             : #ifdef DEBUG_LEHMER
      77             :     err_printf("Calling Lehmer:\n");
      78             : #endif
      79     5755711 :     lhmres = lgcdii((ulong*)d, (ulong*)d1, &xu, &xu1, &xv, &xv1, ULONG_MAX);
      80     5793976 :     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     5275504 :       if ((lhmres == 1) || (lhmres == -1))
      87             :       {
      88      198024 :         if (xv1 == 1)
      89             :         {
      90       93467 :           r = subii(d,d1); d=d1; d1=r;
      91       93467 :           a = subii(v,v1); v=v1; v1=a;
      92             :         }
      93             :         else
      94             :         {
      95        5545 :           r = subii(d, mului(xv1,d1)); d=d1; d1=r;
      96        5545 :           a = subii(v, mului(xv1,v1)); v=v1; v1=a;
      97             :         }
      98             :       }
      99             :       else
     100             :       {
     101     5176492 :         r  = subii(muliu(d,xu),  muliu(d1,xv));
     102     5154468 :         a  = subii(muliu(v,xu),  muliu(v1,xv));
     103     5127165 :         d1 = subii(muliu(d,xu1), muliu(d1,xv1)); d = r;
     104     5153313 :         v1 = subii(muliu(v,xu1), muliu(v1,xv1)); v = a;
     105     5156660 :         if (lhmres&1) { togglesign(d);  togglesign(v); }
     106     2592943 :         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     5756593 :     if (lhmres <= 0 && signe(d1))
     117             :     {
     118      573183 :       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      573157 :       a = subii(v,mulii(q,v1));
     124      573171 :       v=v1; v1=a;
     125      573171 :       d=d1; d1=r;
     126             :     }
     127     5756581 :     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     4314042 :   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     4230760 :     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     4266952 :     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     4266920 :     v = subii(muliu(v,xu1),muliu(v1,xv1));
     155     4242291 :     if (s > 0) setsigne(v,-signe(v));
     156     4242291 :     avma = av; *res = modii(v,b);
     157             : #ifdef DEBUG_LEHMER
     158             :     output(*res); fprintfderr("============================Done.\n");
     159             :     sleep(1);
     160             : #endif
     161     4212850 :     return 1;
     162             :   }
     163             :   /* get here when the final sprint was skipped (d1 was zero already) */
     164       83282 :   avma = av;
     165       83282 :   if (!equalii(d,gen_1)) { *res = icopy(d); return 0; }
     166       83243 :   *res = modii(v,b);
     167             : #ifdef DEBUG_LEHMER
     168             :   output(*res); err_printf("============================Done.\n");
     169             :   sleep(1);
     170             : #endif
     171       83243 :   return 1;
     172             : }
     173             : 

Generated by: LCOV version 1.11