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 - gcdext.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 19350-bd5f220) Lines: 94 96 97.9 %
Date: 2016-08-24 06:11:24 Functions: 1 1 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : #line 2 "../src/kernel/none/gcdext.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             :  * bezout(a,b,pu,pv)
      17             :  *==================================
      18             :  *    Return g = gcd(a,b) >= 0, and assign GENs u,v through pointers pu,pv
      19             :  *    such that g = u*a + v*b.
      20             :  * Special cases:
      21             :  *    a == b == 0 ==> pick u=1, v=0
      22             :  *    a != 0 == b ==> keep v=0
      23             :  *    a == 0 != b ==> keep u=0
      24             :  *    |a| == |b| != 0 ==> keep u=0, set v=+-1
      25             :  * Assignments through pu,pv will be suppressed when the corresponding
      26             :  * pointer is NULL  (but the computations will happen nonetheless).
      27             :  */
      28             : 
      29             : GEN
      30    68236478 : bezout(GEN a, GEN b, GEN *pu, GEN *pv)
      31             : {
      32             :   GEN t,u,u1,v,v1,d,d1,q,r;
      33             :   GEN *pt;
      34             :   pari_sp av, av1;
      35             :   long s, sa, sb;
      36             :   ulong g;
      37             :   ulong xu,xu1,xv,xv1;                /* Lehmer stage recurrence matrix */
      38             :   int lhmres;                        /* Lehmer stage return value */
      39             : 
      40    68236478 :   s = abscmpii(a,b);
      41    68236478 :   if (s < 0)
      42             :   {
      43    46282054 :     t=b; b=a; a=t;
      44    46282054 :     pt=pu; pu=pv; pv=pt;
      45             :   }
      46             :   /* now |a| >= |b| */
      47             : 
      48    68236478 :   sa = signe(a); sb = signe(b);
      49    68236478 :   if (!sb)
      50             :   {
      51     1372698 :     if (pv) *pv = gen_0;
      52     1372698 :     switch(sa)
      53             :     {
      54           3 :     case  0: if (pu) *pu = gen_0; return gen_0;
      55     1371039 :     case  1: if (pu) *pu = gen_1; return icopy(a);
      56        1656 :     case -1: if (pu) *pu = gen_m1; return(negi(a));
      57             :     }
      58             :   }
      59    66863780 :   if (s == 0)                        /* |a| == |b| != 0 */
      60             :   {
      61     7154154 :     if (pu) *pu = gen_0;
      62     7154154 :     if (sb > 0)
      63     6739065 :     { if (pv) *pv = gen_1; return icopy(b); }
      64             :     else
      65      415089 :     { if (pv) *pv = gen_m1; return(negi(b)); }
      66             :   }
      67             :   /* now |a| > |b| > 0 */
      68             : 
      69    59709626 :   if (lgefint(a) == 3)                /* single-word affair */
      70             :   {
      71    59494118 :     g = xxgcduu(uel(a,2), uel(b,2), 0, &xu, &xu1, &xv, &xv1, &s);
      72    59494118 :     sa = s > 0 ? sa : -sa;
      73    59494118 :     sb = s > 0 ? -sb : sb;
      74    59494118 :     if (pu)
      75             :     {
      76    20644754 :       if (xu == 0) *pu = gen_0; /* can happen when b divides a */
      77    10085095 :       else if (xu == 1) *pu = sa < 0 ? gen_m1 : gen_1;
      78     4178067 :       else if (xu == 2) *pu = sa < 0 ? gen_m2 : gen_2;
      79             :       else
      80             :       {
      81     3638463 :         *pu = cgeti(3);
      82     3638463 :         (*pu)[1] = evalsigne(sa)|evallgefint(3);
      83     3638463 :         (*pu)[2] = xu;
      84             :       }
      85             :     }
      86    59494118 :     if (pv)
      87             :     {
      88    54166487 :       if (xv == 1) *pv = sb < 0 ? gen_m1 : gen_1;
      89    30086011 :       else if (xv == 2) *pv = sb < 0 ? gen_m2 : gen_2;
      90             :       else
      91             :       {
      92    26769327 :         *pv = cgeti(3);
      93    26769327 :         (*pv)[1] = evalsigne(sb)|evallgefint(3);
      94    26769327 :         (*pv)[2] = xv;
      95             :       }
      96             :     }
      97    59494118 :     if      (g == 1) return gen_1;
      98    15174228 :     else if (g == 2) return gen_2;
      99     9567762 :     else return utoipos(g);
     100             :   }
     101             : 
     102             :   /* general case */
     103      215508 :   av = avma;
     104      215508 :   (void)new_chunk(lgefint(b) + (lgefint(a)<<1)); /* room for u,v,gcd */
     105             :   /* if a is significantly larger than b, calling lgcdii() is not the best
     106             :    * way to start -- reduce a mod b first
     107             :    */
     108      215508 :   if (lgefint(a) > lgefint(b))
     109             :   {
     110      182658 :     d = absi(b), q = dvmdii(absi(a), d, &d1);
     111      182658 :     if (!signe(d1))                /* a == qb */
     112             :     {
     113      166020 :       avma = av;
     114      166020 :       if (pu) *pu = gen_0;
     115      166020 :       if (pv) *pv = sb < 0 ? gen_m1 : gen_1;
     116      166020 :       return (icopy(d));
     117             :     }
     118             :     else
     119             :     {
     120       16638 :       u = gen_0;
     121       16638 :       u1 = v = gen_1;
     122       16638 :       v1 = negi(q);
     123             :     }
     124             :     /* if this results in lgefint(d) == 3, will fall past main loop */
     125             :   }
     126             :   else
     127             :   {
     128       32850 :     d = absi(a); d1 = absi(b);
     129       32850 :     u = v1 = gen_1; u1 = v = gen_0;
     130             :   }
     131       49488 :   av1 = avma;
     132             : 
     133             :   /* main loop is almost identical to that of invmod() */
     134      202071 :   while (lgefint(d) > 3 && signe(d1))
     135             :   {
     136      103095 :     lhmres = lgcdii((ulong *)d, (ulong *)d1, &xu, &xu1, &xv, &xv1, ULONG_MAX);
     137      103095 :     if (lhmres != 0)                /* check progress */
     138             :     {                                /* apply matrix */
     139       92388 :       if ((lhmres == 1) || (lhmres == -1))
     140             :       {
     141        3198 :         if (xv1 == 1)
     142             :         {
     143         690 :           r = subii(d,d1); d=d1; d1=r;
     144         690 :           a = subii(u,u1); u=u1; u1=a;
     145         690 :           a = subii(v,v1); v=v1; v1=a;
     146             :         }
     147             :         else
     148             :         {
     149         909 :           r = subii(d, mului(xv1,d1)); d=d1; d1=r;
     150         909 :           a = subii(u, mului(xv1,u1)); u=u1; u1=a;
     151         909 :           a = subii(v, mului(xv1,v1)); v=v1; v1=a;
     152             :         }
     153             :       }
     154             :       else
     155             :       {
     156       90789 :         r  = subii(muliu(d,xu),  muliu(d1,xv));
     157       90789 :         d1 = subii(muliu(d,xu1), muliu(d1,xv1)); d = r;
     158       90789 :         a  = subii(muliu(u,xu),  muliu(u1,xv));
     159       90789 :         u1 = subii(muliu(u,xu1), muliu(u1,xv1)); u = a;
     160       90789 :         a  = subii(muliu(v,xu),  muliu(v1,xv));
     161       90789 :         v1 = subii(muliu(v,xu1), muliu(v1,xv1)); v = a;
     162       90789 :         if (lhmres&1) { togglesign(d);  togglesign(u);  togglesign(v); }
     163       45531 :         else          { togglesign(d1); togglesign(u1); togglesign(v1); }
     164             :       }
     165             :     }
     166      103095 :     if (lhmres <= 0 && signe(d1))
     167             :     {
     168       11499 :       q = dvmdii(d,d1,&r);
     169             : #ifdef DEBUG_LEHMER
     170             :       err_printf("Full division:\n");
     171             :       printf("  q = "); output(q); sleep (1);
     172             : #endif
     173       11499 :       a = subii(u,mulii(q,u1));
     174       11499 :       u=u1; u1=a;
     175       11499 :       a = subii(v,mulii(q,v1));
     176       11499 :       v=v1; v1=a;
     177       11499 :       d=d1; d1=r;
     178             :     }
     179      103095 :     if (gc_needed(av,1))
     180             :     {
     181           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"bezout");
     182           0 :       gerepileall(av1,6, &d,&d1,&u,&u1,&v,&v1);
     183             :     }
     184             :   } /* end while */
     185             : 
     186             :   /* Postprocessing - final sprint */
     187       49488 :   if (signe(d1))
     188             :   {
     189             :     /* Assertions: lgefint(d)==lgefint(d1)==3, and
     190             :      * gcd(d,d1) is nonzero and fits into one word
     191             :      */
     192       38688 :     g = xxgcduu(uel(d,2), uel(d1,2), 0, &xu, &xu1, &xv, &xv1, &s);
     193       38688 :     u = subii(muliu(u,xu), muliu(u1, xv));
     194       38688 :     v = subii(muliu(v,xu), muliu(v1, xv));
     195       38688 :     if (s < 0) { sa = -sa; sb = -sb; }
     196       38688 :     avma = av;
     197       38688 :     if (pu) *pu = sa < 0 ? negi(u) : icopy(u);
     198       38688 :     if (pv) *pv = sb < 0 ? negi(v) : icopy(v);
     199       38688 :     if (g == 1) return gen_1;
     200       20055 :     else if (g == 2) return gen_2;
     201       17316 :     else return utoipos(g);
     202             :   }
     203             :   /* get here when the final sprint was skipped (d1 was zero already).
     204             :    * Now the matrix is final, and d contains the gcd.
     205             :    */
     206       10800 :   avma = av;
     207       10800 :   if (pu) *pu = sa < 0 ? negi(u) : icopy(u);
     208       10800 :   if (pv) *pv = sb < 0 ? negi(v) : icopy(v);
     209       10800 :   return icopy(d);
     210             : }
     211             : 

Generated by: LCOV version 1.11