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 to exceed 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.12.1 lcov report (development 25819-e703fe1174) Lines: 103 126 81.7 %
Date: 2020-09-18 06:10:04 Functions: 2 4 50.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             : static GEN
      30    82761789 : bezout_lehmer(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    82761789 :   s = abscmpii(a,b);
      41    82761789 :   if (s < 0)
      42             :   {
      43    60366729 :     t=b; b=a; a=t;
      44    60366729 :     pt=pu; pu=pv; pv=pt;
      45             :   }
      46             :   /* now |a| >= |b| */
      47             : 
      48    82761789 :   sa = signe(a); sb = signe(b);
      49    82761789 :   if (!sb)
      50             :   {
      51     1707573 :     if (pv) *pv = gen_0;
      52     1707573 :     switch(sa)
      53             :     {
      54           3 :     case  0: if (pu) *pu = gen_0; return gen_0;
      55     1705563 :     case  1: if (pu) *pu = gen_1; return icopy(a);
      56        2007 :     case -1: if (pu) *pu = gen_m1; return(negi(a));
      57             :     }
      58             :   }
      59    81054216 :   if (s == 0)                        /* |a| == |b| != 0 */
      60             :   {
      61     6221712 :     if (pu) *pu = gen_0;
      62     6221712 :     if (sb > 0)
      63     6059322 :     { if (pv) *pv = gen_1; return icopy(b); }
      64             :     else
      65      162390 :     { if (pv) *pv = gen_m1; return(negi(b)); }
      66             :   }
      67             :   /* now |a| > |b| > 0 */
      68             : 
      69    74832504 :   if (lgefint(a) == 3)                /* single-word affair */
      70             :   {
      71    73527501 :     g = xxgcduu(uel(a,2), uel(b,2), 0, &xu, &xu1, &xv, &xv1, &s);
      72    73527501 :     sa = s > 0 ? sa : -sa;
      73    73527501 :     sb = s > 0 ? -sb : sb;
      74    73527501 :     if (pu)
      75             :     {
      76    26739594 :       if (xu == 0) *pu = gen_0; /* can happen when b divides a */
      77    11464707 :       else if (xu == 1) *pu = sa < 0 ? gen_m1 : gen_1;
      78     4916952 :       else if (xu == 2) *pu = sa < 0 ? gen_m2 : gen_2;
      79             :       else
      80             :       {
      81     4293948 :         *pu = cgeti(3);
      82     4293948 :         (*pu)[1] = evalsigne(sa)|evallgefint(3);
      83     4293948 :         (*pu)[2] = xu;
      84             :       }
      85             :     }
      86    73527501 :     if (pv)
      87             :     {
      88    67934901 :       if (xv == 1) *pv = sb < 0 ? gen_m1 : gen_1;
      89    35911014 :       else if (xv == 2) *pv = sb < 0 ? gen_m2 : gen_2;
      90             :       else
      91             :       {
      92    31875162 :         *pv = cgeti(3);
      93    31875162 :         (*pv)[1] = evalsigne(sb)|evallgefint(3);
      94    31875162 :         (*pv)[2] = xv;
      95             :       }
      96             :     }
      97    73527501 :     if      (g == 1) return gen_1;
      98    19615116 :     else if (g == 2) return gen_2;
      99    12818604 :     else return utoipos(g);
     100             :   }
     101             : 
     102             :   /* general case */
     103     1305003 :   av = avma;
     104     1305003 :   (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     1305003 :   if (lgefint(a) > lgefint(b))
     109             :   {
     110      795183 :     d = absi_shallow(b);
     111      795183 :     q = dvmdii(absi_shallow(a), d, &d1);
     112      795183 :     if (!signe(d1))                /* a == qb */
     113             :     {
     114      687627 :       set_avma(av);
     115      687627 :       if (pu) *pu = gen_0;
     116      687627 :       if (pv) *pv = sb < 0 ? gen_m1 : gen_1;
     117      687627 :       return icopy(d);
     118             :     }
     119             :     else
     120             :     {
     121      107556 :       u = gen_0;
     122      107556 :       u1 = v = gen_1;
     123      107556 :       v1 = negi(q);
     124             :     }
     125             :     /* if this results in lgefint(d) == 3, will fall past main loop */
     126             :   }
     127             :   else
     128             :   {
     129      509820 :     d = absi_shallow(a);
     130      509820 :     d1 = absi_shallow(b);
     131      509820 :     u = v1 = gen_1; u1 = v = gen_0;
     132             :   }
     133      617376 :   av1 = avma;
     134             : 
     135             :   /* main loop is almost identical to that of invmod() */
     136     2085717 :   while (lgefint(d) > 3 && signe(d1))
     137             :   {
     138     1468341 :     lhmres = lgcdii((ulong *)d, (ulong *)d1, &xu, &xu1, &xv, &xv1, ULONG_MAX);
     139     1468341 :     if (lhmres != 0)                /* check progress */
     140             :     {                                /* apply matrix */
     141     1180737 :       if ((lhmres == 1) || (lhmres == -1))
     142             :       {
     143      402504 :         if (xv1 == 1)
     144             :         {
     145       23388 :           r = subii(d,d1); d=d1; d1=r;
     146       23388 :           a = subii(u,u1); u=u1; u1=a;
     147       23388 :           a = subii(v,v1); v=v1; v1=a;
     148             :         }
     149             :         else
     150             :         {
     151      177864 :           r = subii(d, mului(xv1,d1)); d=d1; d1=r;
     152      177864 :           a = subii(u, mului(xv1,u1)); u=u1; u1=a;
     153      177864 :           a = subii(v, mului(xv1,v1)); v=v1; v1=a;
     154             :         }
     155             :       }
     156             :       else
     157             :       {
     158      979485 :         r  = subii(muliu(d,xu),  muliu(d1,xv));
     159      979485 :         d1 = subii(muliu(d,xu1), muliu(d1,xv1)); d = r;
     160      979485 :         a  = subii(muliu(u,xu),  muliu(u1,xv));
     161      979485 :         u1 = subii(muliu(u,xu1), muliu(u1,xv1)); u = a;
     162      979485 :         a  = subii(muliu(v,xu),  muliu(v1,xv));
     163      979485 :         v1 = subii(muliu(v,xu1), muliu(v1,xv1)); v = a;
     164      979485 :         if (lhmres&1) { togglesign(d);  togglesign(u);  togglesign(v); }
     165      494613 :         else          { togglesign(d1); togglesign(u1); togglesign(v1); }
     166             :       }
     167             :     }
     168     1468341 :     if (lhmres <= 0 && signe(d1))
     169             :     {
     170      305268 :       q = dvmdii(d,d1,&r);
     171      305268 :       a = subii(u,mulii(q,u1));
     172      305268 :       u=u1; u1=a;
     173      305268 :       a = subii(v,mulii(q,v1));
     174      305268 :       v=v1; v1=a;
     175      305268 :       d=d1; d1=r;
     176             :     }
     177     1468341 :     if (gc_needed(av,1))
     178             :     {
     179           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"bezout");
     180           0 :       gerepileall(av1,6, &d,&d1,&u,&u1,&v,&v1);
     181             :     }
     182             :   } /* end while */
     183             : 
     184             :   /* Postprocessing - final sprint */
     185      617376 :   if (signe(d1))
     186             :   {
     187             :     /* Assertions: lgefint(d)==lgefint(d1)==3, and
     188             :      * gcd(d,d1) is nonzero and fits into one word
     189             :      */
     190      325899 :     g = xxgcduu(uel(d,2), uel(d1,2), 0, &xu, &xu1, &xv, &xv1, &s);
     191      325899 :     u = subii(muliu(u,xu), muliu(u1, xv));
     192      325899 :     v = subii(muliu(v,xu), muliu(v1, xv));
     193      325899 :     if (s < 0) { sa = -sa; sb = -sb; }
     194      325899 :     set_avma(av);
     195      325899 :     if (pu) *pu = sa < 0 ? negi(u) : icopy(u);
     196      325899 :     if (pv) *pv = sb < 0 ? negi(v) : icopy(v);
     197      325899 :     if (g == 1) return gen_1;
     198      114732 :     else if (g == 2) return gen_2;
     199      108450 :     else return utoipos(g);
     200             :   }
     201             :   /* get here when the final sprint was skipped (d1 was zero already).
     202             :    * Now the matrix is final, and d contains the gcd.
     203             :    */
     204      291477 :   set_avma(av);
     205      291477 :   if (pu) *pu = sa < 0 ? negi(u) : icopy(u);
     206      291477 :   if (pv) *pv = sb < 0 ? negi(v) : icopy(v);
     207      291477 :   return icopy(d);
     208             : }
     209             : 
     210             : static GEN
     211           0 : addmulmul(GEN u, GEN v, GEN x, GEN y)
     212           0 : { return addii(mulii(u, x),mulii(v, y)); }
     213             : 
     214             : static GEN
     215           0 : bezout_halfgcd(GEN x, GEN y, GEN *ptu, GEN *ptv)
     216             : {
     217           0 :   pari_sp av=avma;
     218           0 :   GEN u, v, R = matid(2);
     219           0 :   while (lgefint(y)-2 >= EXTGCD_HALFGCD_LIMIT)
     220             :   {
     221           0 :     GEN M = HGCD0(x,y);
     222           0 :     R = ZM_mul2(R, gel(M, 1));
     223           0 :     x = gel(M,2); y = gel(M,3);
     224           0 :     if (signe(y) && expi(y)<magic_threshold(x))
     225             :     {
     226           0 :       GEN r, q = dvmdii(x, y, &r);
     227           0 :       x = y; y = r;
     228           0 :       R = mulq(R, q);
     229             :     }
     230           0 :     if (gc_needed(av, 1))
     231           0 :       gerepileall(av,3,&x,&y,&R);
     232             :   }
     233           0 :   y = bezout_lehmer(x,y,&u,&v);
     234           0 :   R = ZM_inv2(R);
     235           0 :   if (ptu) *ptu = addmulmul(u,v,gcoeff(R,1,1),gcoeff(R,2,1));
     236           0 :   if (ptv) *ptv = addmulmul(u,v,gcoeff(R,1,2),gcoeff(R,2,2));
     237           0 :   return y;
     238             : }
     239             : 
     240             : GEN
     241    82761789 : bezout(GEN x, GEN y, GEN *ptu, GEN *ptv)
     242             : {
     243    82761789 :   pari_sp ltop=avma;
     244             :   GEN d;
     245    82761789 :   if (lgefint(y)-2 >= EXTGCD_HALFGCD_LIMIT)
     246           0 :     d = bezout_halfgcd(x, y, ptu, ptv);
     247             :   else
     248    82761789 :     d = bezout_lehmer(x, y, ptu, ptv);
     249    82761789 :   if (ptv) gerepileall(ltop,ptu?3:2,&d,ptv,ptu);
     250    55736550 :   else gerepileall(ltop,ptu?2:1,&d,ptu);
     251    82761789 :   return d;
     252             : }

Generated by: LCOV version 1.13