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 - basemath - F2v.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.1 lcov report (development 24988-2584e74448) Lines: 251 343 73.2 %
Date: 2020-01-26 05:57:03 Functions: 31 47 66.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2012-2019 The PARI group.
       2             : 
       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             : #include "pari.h"
      16             : #include "paripriv.h"
      17             : 
      18             : /***********************************************************************/
      19             : /**                                                                   **/
      20             : /**                             F2v                                   **/
      21             : /**                                                                   **/
      22             : /***********************************************************************/
      23             : /* F2v objects are defined as follows:
      24             :    An F2v is a t_VECSMALL:
      25             :    v[0] = codeword
      26             :    v[1] = number of components
      27             :    x[2] = a_0...a_31 x[3] = a_32..a_63, etc.  on 32bit
      28             :    x[2] = a_0...a_63 x[3] = a_64..a_127, etc. on 64bit
      29             : 
      30             :    where the a_i are bits.
      31             : */
      32             : 
      33             : int
      34           0 : F2v_equal0(GEN V)
      35             : {
      36           0 :   long l = lg(V);
      37           0 :   while (--l > 1)
      38           0 :     if (V[l]) return 0;
      39           0 :   return 1;
      40             : }
      41             : 
      42             : GEN
      43      790141 : F2c_to_ZC(GEN x)
      44             : {
      45      790141 :   long l = x[1]+1, lx = lg(x);
      46      790141 :   GEN  z = cgetg(l, t_COL);
      47             :   long i, j, k;
      48     1583242 :   for (i=2, k=1; i<lx; i++)
      49     8982455 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
      50     8189354 :       gel(z,k) = (x[i]&(1UL<<j))? gen_1: gen_0;
      51      790141 :   return z;
      52             : }
      53             : GEN
      54        1610 : F2c_to_mod(GEN x)
      55             : {
      56        1610 :   long l = x[1]+1, lx = lg(x);
      57        1610 :   GEN  z = cgetg(l, t_COL);
      58        1610 :   GEN _0 = mkintmod(gen_0,gen_2);
      59        1610 :   GEN _1 = mkintmod(gen_1,gen_2);
      60             :   long i, j, k;
      61        8020 :   for (i=2, k=1; i<lx; i++)
      62      287047 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
      63      280637 :       gel(z,k) = (x[i]&(1UL<<j))? _1: _0;
      64        1610 :   return z;
      65             : }
      66             : 
      67             : /* x[a..b], a <= b */
      68             : GEN
      69          28 : F2v_slice(GEN x, long a, long b)
      70             : {
      71          28 :   long i,j,k, l = b-a+1;
      72          28 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
      73          28 :   z[1] = l;
      74          98 :   for(i=a,k=1,j=BITS_IN_LONG; i<=b; i++,j++)
      75             :   {
      76          70 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
      77          70 :     if (F2v_coeff(x,i)) z[k] |= 1UL<<j;
      78             :   }
      79          28 :   return z;
      80             : }
      81             : /* x[a..b,], a <= b */
      82             : GEN
      83          14 : F2m_rowslice(GEN x, long a, long b)
      84             : {
      85             :   long i, l;
      86          14 :   GEN y = cgetg_copy(x, &l);
      87          14 :   for (i = 1; i < l; i++) gel(y,i) = F2v_slice(gel(x,i),a,b);
      88          14 :   return y;
      89             : }
      90             : 
      91             : GEN
      92      180957 : F2m_to_ZM(GEN z)
      93             : {
      94      180957 :   long i, l = lg(z);
      95      180957 :   GEN x = cgetg(l,t_MAT);
      96      180957 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_ZC(gel(z,i));
      97      180957 :   return x;
      98             : }
      99             : GEN
     100          84 : F2m_to_mod(GEN z)
     101             : {
     102          84 :   long i, l = lg(z);
     103          84 :   GEN x = cgetg(l,t_MAT);
     104          84 :   for (i=1; i<l; i++) gel(x,i) = F2c_to_mod(gel(z,i));
     105          84 :   return x;
     106             : }
     107             : 
     108             : GEN
     109           0 : F2v_to_Flv(GEN x)
     110             : {
     111           0 :   long l = x[1]+1, lx = lg(x);
     112           0 :   GEN  z = cgetg(l, t_VECSMALL);
     113             :   long i,j,k;
     114           0 :   for (i=2, k=1; i<lx; i++)
     115           0 :     for (j=0; j<BITS_IN_LONG && k<l; j++,k++)
     116           0 :       z[k] = (x[i]>>j)&1UL;
     117           0 :   return z;
     118             : }
     119             : 
     120             : GEN
     121           0 : F2m_to_Flm(GEN z)
     122             : {
     123           0 :   long i, l = lg(z);
     124           0 :   GEN x = cgetg(l,t_MAT);
     125           0 :   for (i=1; i<l; i++) gel(x,i) = F2v_to_Flv(gel(z,i));
     126           0 :   return x;
     127             : }
     128             : 
     129             : GEN
     130     2367362 : ZV_to_F2v(GEN x)
     131             : {
     132     2367362 :   long l = lg(x)-1;
     133     2367362 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
     134             :   long i,j,k;
     135     2367362 :   z[1] = l;
     136    31607132 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
     137             :   {
     138    29239770 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
     139    29239770 :     if (mpodd(gel(x,i))) z[k] |= 1UL<<j;
     140             :   }
     141     2367362 :   return z;
     142             : }
     143             : 
     144             : GEN
     145        4788 : RgV_to_F2v(GEN x)
     146             : {
     147        4788 :   long l = lg(x)-1;
     148        4788 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
     149             :   long i,j,k;
     150        4788 :   z[1] = l;
     151      846650 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
     152             :   {
     153      841862 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
     154      841862 :     if (Rg_to_F2(gel(x,i))) z[k] |= 1UL<<j;
     155             :   }
     156        4788 :   return z;
     157             : }
     158             : 
     159             : GEN
     160         665 : Flv_to_F2v(GEN x)
     161             : {
     162         665 :   long l = lg(x)-1;
     163         665 :   GEN z = cgetg(nbits2lg(l), t_VECSMALL);
     164             :   long i,j,k;
     165         665 :   z[1] = l;
     166        5369 :   for(i=1,k=1,j=BITS_IN_LONG; i<=l; i++,j++)
     167             :   {
     168        4704 :     if (j==BITS_IN_LONG) { j=0; z[++k]=0; }
     169        4704 :     if (x[i]&1L) z[k] |= 1UL<<j;
     170             :   }
     171         665 :   return z;
     172             : }
     173             : 
     174             : GEN
     175      375093 : ZM_to_F2m(GEN x) { pari_APPLY_same(ZV_to_F2v(gel(x,i))) }
     176             : GEN
     177         238 : RgM_to_F2m(GEN x) { pari_APPLY_same(RgV_to_F2v(gel(x,i))) }
     178             : GEN
     179           0 : Flm_to_F2m(GEN x) { pari_APPLY_same(Flv_to_F2v(gel(x,i))) }
     180             : 
     181             : GEN
     182      375503 : const_F2v(long m)
     183             : {
     184      375503 :   long i, l = nbits2lg(m);
     185      375503 :   GEN c = cgetg(l, t_VECSMALL);
     186      375503 :   c[1] = m;
     187      375503 :   for (i = 2; i < l; i++) uel(c,i) = -1UL;
     188      375503 :   if (remsBIL(m)) uel(c,l-1) = (1UL<<remsBIL(m))-1UL;
     189      375503 :   return c;
     190             : }
     191             : 
     192             : /* Allow lg(y)<lg(x) */
     193             : void
     194    42067844 : F2v_add_inplace(GEN x, GEN y)
     195             : {
     196    42067844 :   long n = lg(y);
     197    42067844 :   long r = (n-2)&7L, q = n-r, i;
     198   162606282 :   for (i = 2; i < q; i += 8)
     199             :   {
     200   120538438 :     x[  i] ^= y[  i]; x[1+i] ^= y[1+i]; x[2+i] ^= y[2+i]; x[3+i] ^= y[3+i];
     201   120538438 :     x[4+i] ^= y[4+i]; x[5+i] ^= y[5+i]; x[6+i] ^= y[6+i]; x[7+i] ^= y[7+i];
     202             :   }
     203    42067844 :   switch (r)
     204             :   {
     205    13632350 :     case 7: x[i] ^= y[i]; i++; case 6: x[i] ^= y[i]; i++;
     206    16763852 :     case 5: x[i] ^= y[i]; i++; case 4: x[i] ^= y[i]; i++;
     207    24480642 :     case 3: x[i] ^= y[i]; i++; case 2: x[i] ^= y[i]; i++;
     208    32096929 :     case 1: x[i] ^= y[i]; i++;
     209             :   }
     210    42067844 : }
     211             : 
     212             : /* Allow lg(y)<lg(x) */
     213             : void
     214           0 : F2v_and_inplace(GEN x, GEN y)
     215             : {
     216           0 :   long n = lg(y);
     217           0 :   long r = (n-2)&7L, q = n-r, i;
     218           0 :   for (i = 2; i < q; i += 8)
     219             :   {
     220           0 :     x[  i] &= y[  i]; x[1+i] &= y[1+i]; x[2+i] &= y[2+i]; x[3+i] &= y[3+i];
     221           0 :     x[4+i] &= y[4+i]; x[5+i] &= y[5+i]; x[6+i] &= y[6+i]; x[7+i] &= y[7+i];
     222             :   }
     223           0 :   switch (r)
     224             :   {
     225           0 :     case 7: x[i] &= y[i]; i++; case 6: x[i] &= y[i]; i++;
     226           0 :     case 5: x[i] &= y[i]; i++; case 4: x[i] &= y[i]; i++;
     227           0 :     case 3: x[i] &= y[i]; i++; case 2: x[i] &= y[i]; i++;
     228           0 :     case 1: x[i] &= y[i]; i++;
     229             :   }
     230           0 : }
     231             : 
     232             : /* Allow lg(y)<lg(x) */
     233             : void
     234           0 : F2v_or_inplace(GEN x, GEN y)
     235             : {
     236           0 :   long n = lg(y);
     237           0 :   long r = (n-2)&7L, q = n-r, i;
     238           0 :   for (i = 2; i < q; i += 8)
     239             :   {
     240           0 :     x[  i] |= y[  i]; x[1+i] |= y[1+i]; x[2+i] |= y[2+i]; x[3+i] |= y[3+i];
     241           0 :     x[4+i] |= y[4+i]; x[5+i] |= y[5+i]; x[6+i] |= y[6+i]; x[7+i] |= y[7+i];
     242             :   }
     243           0 :   switch (r)
     244             :   {
     245           0 :     case 7: x[i] |= y[i]; i++; case 6: x[i] |= y[i]; i++;
     246           0 :     case 5: x[i] |= y[i]; i++; case 4: x[i] |= y[i]; i++;
     247           0 :     case 3: x[i] |= y[i]; i++; case 2: x[i] |= y[i]; i++;
     248           0 :     case 1: x[i] |= y[i]; i++;
     249             :   }
     250           0 : }
     251             : 
     252             : /* Allow lg(y)<lg(x) */
     253             : void
     254           0 : F2v_negimply_inplace(GEN x, GEN y)
     255             : {
     256           0 :   long n = lg(y);
     257           0 :   long r = (n-2)&7L, q = n-r, i;
     258           0 :   for (i = 2; i < q; i += 8)
     259             :   {
     260           0 :     x[  i] &= ~y[  i]; x[1+i] &= ~y[1+i]; x[2+i] &= ~y[2+i]; x[3+i] &= ~y[3+i];
     261           0 :     x[4+i] &= ~y[4+i]; x[5+i] &= ~y[5+i]; x[6+i] &= ~y[6+i]; x[7+i] &= ~y[7+i];
     262             :   }
     263           0 :   switch (r)
     264             :   {
     265           0 :     case 7: x[i] &= ~y[i]; i++; case 6: x[i] &= ~y[i]; i++;
     266           0 :     case 5: x[i] &= ~y[i]; i++; case 4: x[i] &= ~y[i]; i++;
     267           0 :     case 3: x[i] &= ~y[i]; i++; case 2: x[i] &= ~y[i]; i++;
     268           0 :     case 1: x[i] &= ~y[i]; i++;
     269             :   }
     270           0 : }
     271             : 
     272             : ulong
     273           0 : F2v_dotproduct(GEN x, GEN y)
     274             : {
     275           0 :   long i, lx = lg(x);
     276             :   ulong c;
     277           0 :   if (lx <= 2) return 0;
     278           0 :   c = uel(x,2) & uel(y,2);
     279           0 :   for (i=3; i<lx; i++) c ^= uel(x,i) & uel(y,i);
     280             : #ifdef LONG_IS_64BIT
     281           0 :   c ^= c >> 32;
     282             : #endif
     283           0 :   c ^= c >> 16;
     284           0 :   c ^= c >>  8;
     285           0 :   c ^= c >>  4;
     286           0 :   c ^= c >>  2;
     287           0 :   c ^= c >>  1;
     288           0 :   return c & 1;
     289             : }
     290             : 
     291             : ulong
     292           0 : F2v_hamming(GEN H)
     293             : {
     294           0 :   long i, n=0, l=lg(H);
     295           0 :   for (i=2; i<l; i++) n += hammingl(uel(H,i));
     296           0 :   return n;
     297             : }
     298             : 
     299             : GEN
     300       22497 : matid_F2m(long n)
     301             : {
     302       22497 :   GEN y = cgetg(n+1,t_MAT);
     303             :   long i;
     304       22497 :   if (n < 0) pari_err_DOMAIN("matid_F2m", "dimension","<",gen_0,stoi(n));
     305       22497 :   for (i=1; i<=n; i++) { gel(y,i) = zero_F2v(n); F2v_set(gel(y,i),i); }
     306       22497 :   return y;
     307             : }
     308             : 
     309             : INLINE GEN
     310      425748 : F2m_F2c_mul_i(GEN x, GEN y, long lx, long l)
     311             : {
     312             :   long j;
     313      425748 :   GEN z = NULL;
     314             : 
     315     4769569 :   for (j=1; j<lx; j++)
     316             :   {
     317     4343821 :     if (!F2v_coeff(y,j)) continue;
     318     1024812 :     if (!z) z = vecsmall_copy(gel(x,j));
     319      625264 :     else F2v_add_inplace(z,gel(x,j));
     320             :   }
     321      425748 :   if (!z) z = zero_F2v(l);
     322      425748 :   return z;
     323             : }
     324             : 
     325             : GEN
     326      100725 : F2m_mul(GEN x, GEN y)
     327             : {
     328      100725 :   long i,j,l,lx=lg(x), ly=lg(y);
     329             :   GEN z;
     330      100725 :   if (ly==1) return cgetg(1,t_MAT);
     331      100725 :   z = cgetg(ly,t_MAT);
     332      100725 :   if (lx==1)
     333             :   {
     334           0 :     for (i=1; i<ly; i++) gel(z,i) = mkvecsmall(0);
     335           0 :     return z;
     336             :   }
     337      100725 :   l = coeff(x,1,1);
     338      100725 :   for (j=1; j<ly; j++) gel(z,j) = F2m_F2c_mul_i(x, gel(y,j), lx, l);
     339      100725 :   return z;
     340             : }
     341             : 
     342             : GEN
     343           0 : F2m_F2c_mul(GEN x, GEN y)
     344             : {
     345           0 :   long l, lx = lg(x);
     346           0 :   if (lx==1) return cgetg(1,t_VECSMALL);
     347           0 :   l = coeff(x,1,1);
     348           0 :   return F2m_F2c_mul_i(x, y, lx, l);
     349             : }
     350             : 
     351             : static GEN
     352           0 : _F2m_mul(void *data, GEN x, GEN y) { (void) data; return F2m_mul(x,y); }
     353             : static GEN
     354           0 : _F2m_sqr(void *data, GEN x) { (void) data; return F2m_mul(x,x); }
     355             : GEN
     356           0 : F2m_powu(GEN x, ulong n)
     357             : {
     358           0 :   if (!n) return matid(lg(x)-1);
     359           0 :   return gen_powu(x, n,NULL, &_F2m_sqr, &_F2m_mul);
     360             : }
     361             : 
     362             : static long
     363     2667831 : F2v_find_nonzero(GEN x0, GEN mask0, long m)
     364             : {
     365     2667831 :   ulong *x = (ulong *)x0+2, *mask = (ulong *)mask0+2, e;
     366     2667831 :   long i, l = lg(x0)-2;
     367     4881774 :   for (i = 0; i < l; i++)
     368             :   {
     369     4250322 :     e = *x++ & *mask++;
     370     4250322 :     if (e) return i*BITS_IN_LONG+vals(e)+1;
     371             :   }
     372      631452 :   return m+1;
     373             : }
     374             : 
     375             : /* in place, destroy x */
     376             : GEN
     377      331413 : F2m_ker_sp(GEN x, long deplin)
     378             : {
     379             :   GEN y, c, d;
     380             :   long i, j, k, r, m, n;
     381             : 
     382      331413 :   n = lg(x)-1;
     383      331413 :   m = mael(x,1,1); r=0;
     384             : 
     385      331413 :   d = cgetg(n+1, t_VECSMALL);
     386      331413 :   c = const_F2v(m);
     387     2658136 :   for (k=1; k<=n; k++)
     388             :   {
     389     2356059 :     GEN xk = gel(x,k);
     390     2356059 :     j = F2v_find_nonzero(xk, c, m);
     391     2356063 :     if (j>m)
     392             :     {
     393      514647 :       if (deplin) {
     394       29336 :         GEN c = zero_F2v(n);
     395      124388 :         for (i=1; i<k; i++)
     396       95052 :           if (F2v_coeff(xk, d[i]))
     397       48227 :             F2v_set(c, i);
     398       29336 :         F2v_set(c, k);
     399       29336 :         return c;
     400             :       }
     401      485311 :       r++; d[k] = 0;
     402             :     }
     403             :     else
     404             :     {
     405     1841416 :       F2v_clear(c,j); d[k] = j;
     406     1841414 :       F2v_clear(xk, j);
     407   105501909 :       for (i=k+1; i<=n; i++)
     408             :       {
     409   103660495 :         GEN xi = gel(x,i);
     410   103660495 :         if (F2v_coeff(xi,j)) F2v_add_inplace(xi, xk);
     411             :       }
     412     1841414 :       F2v_set(xk, j);
     413             :     }
     414             :   }
     415      302077 :   if (deplin) return NULL;
     416             : 
     417      300642 :   y = zero_F2m_copy(n,r);
     418      785953 :   for (j=k=1; j<=r; j++,k++)
     419             :   {
     420      485311 :     GEN C = gel(y,j); while (d[k]) k++;
     421    11673507 :     for (i=1; i<k; i++)
     422    11188196 :       if (d[i] && F2m_coeff(x,d[i],k))
     423     3824432 :         F2v_set(C,i);
     424      485311 :     F2v_set(C, k);
     425             :   }
     426      300642 :   return y;
     427             : }
     428             : 
     429             : /* not memory clean */
     430             : GEN
     431       18762 : F2m_ker(GEN x) { return F2m_ker_sp(F2m_copy(x), 0); }
     432             : GEN
     433           0 : F2m_deplin(GEN x) { return F2m_ker_sp(F2m_copy(x), 1); }
     434             : 
     435             : ulong
     436        1631 : F2m_det_sp(GEN x) { return !F2m_ker_sp(x, 1); }
     437             : 
     438             : ulong
     439           0 : F2m_det(GEN x)
     440             : {
     441           0 :   pari_sp av = avma;
     442           0 :   ulong d = F2m_det_sp(F2m_copy(x));
     443           0 :   return gc_ulong(av, d);
     444             : }
     445             : 
     446             : /* Destroy x */
     447             : GEN
     448       44090 : F2m_gauss_pivot(GEN x, long *rr)
     449             : {
     450             :   GEN c, d;
     451             :   long i, j, k, r, m, n;
     452             : 
     453       44090 :   n = lg(x)-1; if (!n) { *rr=0; return NULL; }
     454       44090 :   m = mael(x,1,1); r=0;
     455             : 
     456       44090 :   d = cgetg(n+1, t_VECSMALL);
     457       44090 :   c = const_F2v(m);
     458      355861 :   for (k=1; k<=n; k++)
     459             :   {
     460      311771 :     GEN xk = gel(x,k);
     461      311771 :     j = F2v_find_nonzero(xk, c, m);
     462      311771 :     if (j>m) { r++; d[k] = 0; }
     463             :     else
     464             :     {
     465      194966 :       F2v_clear(c,j); d[k] = j;
     466     2706219 :       for (i=k+1; i<=n; i++)
     467             :       {
     468     2511253 :         GEN xi = gel(x,i);
     469     2511253 :         if (F2v_coeff(xi,j)) F2v_add_inplace(xi, xk);
     470             :       }
     471             :     }
     472             :   }
     473             : 
     474       44090 :   *rr = r; set_avma((pari_sp)d); return d;
     475             : }
     476             : 
     477             : long
     478          63 : F2m_rank(GEN x)
     479             : {
     480          63 :   pari_sp av = avma;
     481             :   long r;
     482          63 :   (void)F2m_gauss_pivot(F2m_copy(x),&r);
     483          63 :   return gc_long(av, lg(x)-1 - r);
     484             : }
     485             : 
     486             : static GEN
     487          14 : F2m_inv_upper_1_ind(GEN A, long index)
     488             : {
     489          14 :   pari_sp av = avma;
     490          14 :   long n = lg(A)-1, i = index, j;
     491          14 :   GEN u = const_vecsmall(n, 0);
     492          14 :   u[i] = 1;
     493          21 :   for (i--; i>0; i--)
     494             :   {
     495           7 :     ulong m = F2m_coeff(A,i,i+1) & uel(u,i+1); /* j = i+1 */
     496           7 :     for (j=i+2; j<=n; j++) m ^= F2m_coeff(A,i,j) & uel(u,j);
     497           7 :     u[i] = m & 1;
     498             :   }
     499          14 :   return gerepileuptoleaf(av, Flv_to_F2v(u));
     500             : }
     501             : static GEN
     502           7 : F2m_inv_upper_1(GEN A)
     503             : {
     504             :   long i, l;
     505           7 :   GEN B = cgetg_copy(A, &l);
     506           7 :   for (i = 1; i < l; i++) gel(B,i) = F2m_inv_upper_1_ind(A, i);
     507           7 :   return B;
     508             : }
     509             : 
     510             : static GEN
     511      141998 : F2_get_col(GEN b, GEN d, long li, long aco)
     512             : {
     513      141998 :   long i, l = nbits2lg(aco);
     514      141998 :   GEN u = cgetg(l, t_VECSMALL);
     515      141998 :   u[1] = aco;
     516     1906980 :   for (i = 1; i <= li; i++)
     517     1764982 :     if (d[i]) /* d[i] can still be 0 if li > aco */
     518             :     {
     519     1696144 :       if (F2v_coeff(b, i))
     520      545796 :         F2v_set(u, d[i]);
     521             :       else
     522     1150348 :         F2v_clear(u, d[i]);
     523             :     }
     524      141998 :   return u;
     525             : }
     526             : 
     527             : /* destroy a, b */
     528             : GEN
     529       22532 : F2m_gauss_sp(GEN a, GEN b)
     530             : {
     531       22532 :   long i, j, k, l, li, bco, aco = lg(a)-1;
     532             :   GEN u, d;
     533             : 
     534       22532 :   if (!aco) return cgetg(1,t_MAT);
     535       22532 :   li = gel(a,1)[1];
     536       22532 :   d = zero_Flv(li);
     537       22532 :   bco = lg(b)-1;
     538      155878 :   for (i=1; i<=aco; i++)
     539             :   {
     540      133367 :     GEN ai = vecsmall_copy(gel(a,i));
     541      133367 :     if (!d[i] && F2v_coeff(ai, i))
     542       67403 :       k = i;
     543             :     else
     544       65964 :       for (k = 1; k <= li; k++) if (!d[k] && F2v_coeff(ai,k)) break;
     545             :     /* found a pivot on row k */
     546      133367 :     if (k > li) return NULL;
     547      133346 :     d[k] = i;
     548             : 
     549             :     /* Clear k-th row but column-wise instead of line-wise */
     550             :     /*  a_ij -= a_i1*a1j/a_11
     551             :        line-wise grouping:  L_j -= a_1j/a_11*L_1
     552             :        column-wise:         C_i -= a_i1/a_11*C_1
     553             :     */
     554      133346 :     F2v_clear(ai,k);
     555     1812375 :     for (l=1; l<=aco; l++)
     556             :     {
     557     1679029 :       GEN al = gel(a,l);
     558     1679029 :       if (F2v_coeff(al,k)) F2v_add_inplace(al,ai);
     559             :     }
     560     1829749 :     for (l=1; l<=bco; l++)
     561             :     {
     562     1696403 :       GEN bl = gel(b,l);
     563     1696403 :       if (F2v_coeff(bl,k)) F2v_add_inplace(bl,ai);
     564             :     }
     565             :   }
     566       22511 :   u = cgetg(bco+1,t_MAT);
     567       22511 :   for (j = 1; j <= bco; j++) gel(u,j) = F2_get_col(gel(b,j), d, li, aco);
     568       22511 :   return u;
     569             : }
     570             : 
     571             : GEN
     572          35 : F2m_gauss(GEN a, GEN b)
     573             : {
     574          35 :   pari_sp av = avma;
     575          35 :   if (lg(a) == 1) return cgetg(1,t_MAT);
     576          35 :   return gerepileupto(av, F2m_gauss_sp(F2m_copy(a), F2m_copy(b)));
     577             : }
     578             : GEN
     579          14 : F2m_F2c_gauss(GEN a, GEN b)
     580             : {
     581          14 :   pari_sp av = avma;
     582          14 :   GEN z = F2m_gauss(a, mkmat(b));
     583          14 :   if (!z) return gc_NULL(av);
     584           7 :   if (lg(z) == 1) { set_avma(av); return cgetg(1,t_VECSMALL); }
     585           7 :   return gerepileuptoleaf(av, gel(z,1));
     586             : }
     587             : 
     588             : GEN
     589          35 : F2m_inv(GEN a)
     590             : {
     591          35 :   pari_sp av = avma;
     592          35 :   if (lg(a) == 1) return cgetg(1,t_MAT);
     593          35 :   return gerepileupto(av, F2m_gauss_sp(F2m_copy(a), matid_F2m(gel(a,1)[1])));
     594             : }
     595             : 
     596             : GEN
     597           7 : F2m_invimage_i(GEN A, GEN B)
     598             : {
     599             :   GEN d, x, X, Y;
     600           7 :   long i, j, nY, nA = lg(A)-1, nB = lg(B)-1;
     601           7 :   x = F2m_ker_sp(shallowconcat(A, B), 0);
     602             :   /* AX = BY, Y in strict upper echelon form with pivots = 1.
     603             :    * We must find T such that Y T = Id_nB then X T = Z. This exists iff
     604             :    * Y has at least nB columns and full rank */
     605           7 :   nY = lg(x)-1;
     606           7 :   if (nY < nB) return NULL;
     607             : 
     608             :   /* implicitly: Y = rowslice(x, nA+1, nA+nB), nB rows */
     609           7 :   d = cgetg(nB+1, t_VECSMALL);
     610          21 :   for (i = nB, j = nY; i >= 1; i--, j--)
     611             :   {
     612          14 :     for (; j>=1; j--)
     613          14 :       if (F2m_coeff(x,nA+i,j)) { d[i] = j; break; } /* Y[i,j] */
     614          14 :     if (!j) return NULL;
     615             :   }
     616           7 :   x = vecpermute(x, d);
     617             : 
     618           7 :   X = F2m_rowslice(x, 1, nA);
     619           7 :   Y = F2m_rowslice(x, nA+1, nA+nB);
     620           7 :   return F2m_mul(X, F2m_inv_upper_1(Y));
     621             : }
     622             : GEN
     623           0 : F2m_invimage(GEN A, GEN B)
     624             : {
     625           0 :   pari_sp av = avma;
     626           0 :   GEN X = F2m_invimage_i(A,B);
     627           0 :   if (!X) return gc_NULL(av);
     628           0 :   return gerepileupto(av, X);
     629             : }
     630             : 
     631             : GEN
     632       18704 : F2m_F2c_invimage(GEN A, GEN y)
     633             : {
     634       18704 :   pari_sp av = avma;
     635       18704 :   long i, l = lg(A);
     636             :   GEN M, x;
     637             : 
     638       18704 :   if (l==1) return NULL;
     639       18704 :   if (lg(y) != lgcols(A)) pari_err_DIM("F2m_F2c_invimage");
     640       18704 :   M = cgetg(l+1,t_MAT);
     641       18704 :   for (i=1; i<l; i++) gel(M,i) = gel(A,i);
     642       18704 :   gel(M,l) = y; M = F2m_ker(M);
     643       18704 :   i = lg(M)-1; if (!i) return gc_NULL(av);
     644             : 
     645       18704 :   x = gel(M,i);
     646       18704 :   if (!F2v_coeff(x,l)) return gc_NULL(av);
     647       18704 :   F2v_clear(x, x[1]); x[1]--; /* remove last coord */
     648       18704 :   return gerepileuptoleaf(av, x);
     649             : }

Generated by: LCOV version 1.13