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 - gcdext.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 16746-c2cb716) Lines: 94 96 97.9 %
Date: 2014-08-31 Functions: 1 1 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 105 114 92.1 %

           Branch data     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                 :   14566179 : 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, lim;
      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                 :   14566179 :   s = absi_cmp(a,b);
      41         [ +  + ]:   14566179 :   if (s < 0)
      42                 :            :   {
      43                 :    5388681 :     t=b; b=a; a=t;
      44                 :    5388681 :     pt=pu; pu=pv; pv=pt;
      45                 :            :   }
      46                 :            :   /* now |a| >= |b| */
      47                 :            : 
      48                 :   14566179 :   sa = signe(a); sb = signe(b);
      49         [ +  + ]:   14566179 :   if (!sb)
      50                 :            :   {
      51         [ +  - ]:     114825 :     if (pv) *pv = gen_0;
      52   [ +  +  +  - ]:     114825 :     switch(sa)
      53                 :            :     {
      54         [ +  - ]:          3 :     case  0: if (pu) *pu = gen_0; return gen_0;
      55         [ +  + ]:     114060 :     case  1: if (pu) *pu = gen_1; return icopy(a);
      56         [ +  - ]:        762 :     case -1: if (pu) *pu = gen_m1; return(negi(a));
      57                 :            :     }
      58                 :            :   }
      59         [ +  + ]:   14451354 :   if (s == 0)                        /* |a| == |b| != 0 */
      60                 :            :   {
      61         [ +  + ]:    3325683 :     if (pu) *pu = gen_0;
      62         [ +  + ]:    3325683 :     if (sb > 0)
      63         [ +  + ]:    2931612 :     { if (pv) *pv = gen_1; return icopy(b); }
      64                 :            :     else
      65         [ +  - ]:     394071 :     { if (pv) *pv = gen_m1; return(negi(b)); }
      66                 :            :   }
      67                 :            :   /* now |a| > |b| > 0 */
      68                 :            : 
      69         [ +  + ]:   11125671 :   if (lgefint(a) == 3)                /* single-word affair */
      70                 :            :   {
      71                 :   10968711 :     g = xxgcduu(uel(a,2), uel(b,2), 0, &xu, &xu1, &xv, &xv1, &s);
      72         [ +  + ]:   10968711 :     sa = s > 0 ? sa : -sa;
      73         [ +  + ]:   10968711 :     sb = s > 0 ? -sb : sb;
      74         [ +  + ]:   10968711 :     if (pu)
      75                 :            :     {
      76         [ +  + ]:    7637022 :       if (xu == 0) *pu = gen_0; /* can happen when b divides a */
      77 [ +  + ][ +  + ]:    3060225 :       else if (xu == 1) *pu = sa < 0 ? gen_m1 : gen_1;
      78 [ +  + ][ +  + ]:    2100264 :       else if (xu == 2) *pu = sa < 0 ? gen_m2 : gen_2;
      79                 :            :       else
      80                 :            :       {
      81                 :    1992210 :         *pu = cgeti(3);
      82                 :    1992210 :         (*pu)[1] = evalsigne(sa)|evallgefint(3);
      83                 :    1992210 :         (*pu)[2] = xu;
      84                 :            :       }
      85                 :            :     }
      86         [ +  + ]:   10968711 :     if (pv)
      87                 :            :     {
      88 [ +  + ][ +  + ]:    9351810 :       if (xv == 1) *pv = sb < 0 ? gen_m1 : gen_1;
      89 [ +  + ][ +  + ]:    4246629 :       else if (xv == 2) *pv = sb < 0 ? gen_m2 : gen_2;
      90                 :            :       else
      91                 :            :       {
      92                 :    4143306 :         *pv = cgeti(3);
      93                 :    4143306 :         (*pv)[1] = evalsigne(sb)|evallgefint(3);
      94                 :    4143306 :         (*pv)[2] = xv;
      95                 :            :       }
      96                 :            :     }
      97         [ +  + ]:   10968711 :     if      (g == 1) return gen_1;
      98         [ +  + ]:    2946762 :     else if (g == 2) return gen_2;
      99                 :    2130783 :     else return utoipos(g);
     100                 :            :   }
     101                 :            : 
     102                 :            :   /* general case */
     103                 :     156960 :   av = avma;
     104                 :     156960 :   (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         [ +  + ]:     156960 :   if (lgefint(a) > lgefint(b))
     109                 :            :   {
     110                 :     132969 :     d = absi(b), q = dvmdii(absi(a), d, &d1);
     111         [ +  + ]:     132969 :     if (!signe(d1))                /* a == qb */
     112                 :            :     {
     113                 :     120351 :       avma = av;
     114         [ +  + ]:     120351 :       if (pu) *pu = gen_0;
     115 [ +  + ][ +  + ]:     120351 :       if (pv) *pv = sb < 0 ? gen_m1 : gen_1;
     116                 :     120351 :       return (icopy(d));
     117                 :            :     }
     118                 :            :     else
     119                 :            :     {
     120                 :      12618 :       u = gen_0;
     121                 :      12618 :       u1 = v = gen_1;
     122                 :      12618 :       v1 = negi(q);
     123                 :            :     }
     124                 :            :     /* if this results in lgefint(d) == 3, will fall past main loop */
     125                 :            :   }
     126                 :            :   else
     127                 :            :   {
     128                 :      23991 :     d = absi(a); d1 = absi(b);
     129                 :      23991 :     u = v1 = gen_1; u1 = v = gen_0;
     130                 :            :   }
     131                 :      36609 :   av1 = avma; lim = stack_lim(av, 1);
     132                 :            : 
     133                 :            :   /* main loop is almost identical to that of invmod() */
     134 [ +  + ][ +  + ]:     113565 :   while (lgefint(d) > 3 && signe(d1))
     135                 :            :   {
     136                 :      76956 :     lhmres = lgcdii((ulong *)d, (ulong *)d1, &xu, &xu1, &xv, &xv1, ULONG_MAX);
     137         [ +  + ]:      76956 :     if (lhmres != 0)                /* check progress */
     138                 :            :     {                                /* apply matrix */
     139 [ +  + ][ +  + ]:      65877 :       if ((lhmres == 1) || (lhmres == -1))
     140                 :            :       {
     141         [ +  + ]:       1812 :         if (xv1 == 1)
     142                 :            :         {
     143                 :        333 :           r = subii(d,d1); d=d1; d1=r;
     144                 :        333 :           a = subii(u,u1); u=u1; u1=a;
     145                 :        333 :           a = subii(v,v1); v=v1; v1=a;
     146                 :            :         }
     147                 :            :         else
     148                 :            :         {
     149                 :        573 :           r = subii(d, mului(xv1,d1)); d=d1; d1=r;
     150                 :        573 :           a = subii(u, mului(xv1,u1)); u=u1; u1=a;
     151                 :        573 :           a = subii(v, mului(xv1,v1)); v=v1; v1=a;
     152                 :            :         }
     153                 :            :       }
     154                 :            :       else
     155                 :            :       {
     156                 :      64971 :         r  = subii(muliu(d,xu),  muliu(d1,xv));
     157                 :      64971 :         d1 = subii(muliu(d,xu1), muliu(d1,xv1)); d = r;
     158                 :      64971 :         a  = subii(muliu(u,xu),  muliu(u1,xv));
     159                 :      64971 :         u1 = subii(muliu(u,xu1), muliu(u1,xv1)); u = a;
     160                 :      64971 :         a  = subii(muliu(v,xu),  muliu(v1,xv));
     161                 :      64971 :         v1 = subii(muliu(v,xu1), muliu(v1,xv1)); v = a;
     162         [ +  + ]:      64971 :         if (lhmres&1) { togglesign(d);  togglesign(u);  togglesign(v); }
     163                 :      32442 :         else          { togglesign(d1); togglesign(u1); togglesign(v1); }
     164                 :            :       }
     165                 :            :     }
     166 [ +  + ][ +  - ]:      76956 :     if (lhmres <= 0 && signe(d1))
     167                 :            :     {
     168                 :      11466 :       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                 :      11466 :       a = subii(u,mulii(q,u1));
     174                 :      11466 :       u=u1; u1=a;
     175                 :      11466 :       a = subii(v,mulii(q,v1));
     176                 :      11466 :       v=v1; v1=a;
     177                 :      11466 :       d=d1; d1=r;
     178                 :            :     }
     179         [ -  + ]:      76956 :     if (low_stack(lim, stack_lim(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         [ +  + ]:      36609 :   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                 :      25764 :     g = xxgcduu(uel(d,2), uel(d1,2), 0, &xu, &xu1, &xv, &xv1, &s);
     193                 :      25764 :     u = subii(muliu(u,xu), muliu(u1, xv));
     194                 :      25764 :     v = subii(muliu(v,xu), muliu(v1, xv));
     195         [ +  + ]:      25764 :     if (s < 0) { sa = -sa; sb = -sb; }
     196                 :      25764 :     avma = av;
     197 [ +  + ][ +  + ]:      25764 :     if (pu) *pu = sa < 0 ? negi(u) : icopy(u);
     198 [ +  + ][ +  + ]:      25764 :     if (pv) *pv = sb < 0 ? negi(v) : icopy(v);
     199         [ +  + ]:      25764 :     if (g == 1) return gen_1;
     200         [ +  + ]:      15879 :     else if (g == 2) return gen_2;
     201                 :      14763 :     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                 :      10845 :   avma = av;
     207 [ +  + ][ +  + ]:      10845 :   if (pu) *pu = sa < 0 ? negi(u) : icopy(u);
     208 [ +  + ][ +  + ]:      10845 :   if (pv) *pv = sb < 0 ? negi(v) : icopy(v);
     209                 :   14566179 :   return icopy(d);
     210                 :            : }
     211                 :            : 

Generated by: LCOV version 1.9