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 - basemath - subgroup.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 16746-c2cb716) Lines: 317 360 88.1 %
Date: 2014-08-31 Functions: 20 22 90.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 224 273 82.1 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2000  The PARI group.
       2                 :            : 
       3                 :            : This file is part of the PARI/GP package.
       4                 :            : 
       5                 :            : PARI/GP is free software; you can redistribute it and/or modify it under the
       6                 :            : terms of the GNU General Public License as published by the Free Software
       7                 :            : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8                 :            : ANY WARRANTY WHATSOEVER.
       9                 :            : 
      10                 :            : Check the License for details. You should have received a copy of it, along
      11                 :            : with the package; see the file 'COPYING'. If not, write to the Free Software
      12                 :            : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13                 :            : 
      14                 :            : #include "pari.h"
      15                 :            : #include "paripriv.h"
      16                 :            : 
      17                 :            : typedef struct slist {
      18                 :            :   struct slist *next;
      19                 :            :   long *data;
      20                 :            :   long prec;
      21                 :            : } slist;
      22                 :            : 
      23                 :            : typedef struct {
      24                 :            :   GEN cyc, gen;
      25                 :            :   ulong count;
      26                 :            :   slist *list;
      27                 :            : } sublist_t;
      28                 :            : 
      29                 :            : /* SUBGROUPS
      30                 :            :  * G = Gp x I, with Gp a p-Sylow (I assumed small).
      31                 :            :  * Compute subgroups of I by recursive calls
      32                 :            :  * Loop through subgroups Hp of Gp using Birkhoff's algorithm.
      33                 :            :  * If (I is non trivial)
      34                 :            :  *   lift Hp to G (mul by exponent of I)
      35                 :            :  *   for each subgp of I, lift it to G (mult by exponent of Gp)
      36                 :            :  *   consider the group generated by the two subgroups (concat)
      37                 :            :  *
      38                 :            :  * type(H) = mu --> H = Z/p^mu[1] x ... x Z/p^mu[len(mu)] */
      39                 :            : typedef struct subgp_iter {
      40                 :            :   long *M, *L; /* mu = p-subgroup type, lambda = p-group type */
      41                 :            :   GEN *powlist; /* [i] = p^i, i = 0.. */
      42                 :            :   long *c, *maxc;
      43                 :            :   GEN *a, *maxa, **g, **maxg;
      44                 :            :   long *available;
      45                 :            :   GEN **H; /* p-subgroup of type mu, in matrix form */
      46                 :            :   GEN cyc; /* cyclic factors of G */
      47                 :            :   GEN subq;/* subgrouplist(I) */
      48                 :            :   GEN subqpart; /* J in subq s.t [I:J][Gp:Hp] <= indexbound */
      49                 :            :   GEN bound; /* if != NULL, impose a "bound" on [G:H] (see boundtype) */
      50                 :            :   long boundtype;
      51                 :            :   long countsub; /* number of subgroups of type M (so far) */
      52                 :            :   long count; /* number of p-subgroups so far [updated when M completed] */
      53                 :            :   GEN expoI; /* exponent of I */
      54                 :            : 
      55                 :            :   long(*fun)(void*, GEN); /* callback applied to each subgroup */
      56                 :            :   void *fundata; /* data for fun */
      57                 :            :   long stop;
      58                 :            : } subgp_iter;
      59                 :            : 
      60                 :            : /* MAX: [G:H] <= bound, EXACT: [G:H] = bound, TYPE: type(H) = bound */
      61                 :            : enum { b_NONE, b_MAX, b_EXACT, b_TYPE };
      62                 :            : 
      63                 :            : #define len(x)      (x)[0]
      64                 :            : #define setlen(x,l) len(x)=(l)
      65                 :            : 
      66                 :            : static void
      67                 :          0 : printtyp(const long *typ) /*Used only for ddebugging */
      68                 :            : {
      69                 :          0 :   long i, l = len(typ);
      70         [ #  # ]:          0 :   for (i=1; i<=l; i++) err_printf(" %ld ",typ[i]);
      71                 :          0 :   err_printf("\n");
      72                 :          0 : }
      73                 :            : 
      74                 :            : /* compute conjugate partition of typ */
      75                 :            : static long*
      76                 :          0 : conjugate(long *typ)
      77                 :            : {
      78                 :          0 :   long *t, i, k = len(typ), l, last;
      79                 :            : 
      80         [ #  # ]:          0 :   if (!k) { t = new_chunk(1); setlen(t,0); return t; }
      81                 :          0 :   l = typ[1]; t = new_chunk(l+2);
      82                 :          0 :   t[1] = k; last = k;
      83         [ #  # ]:          0 :   for (i=2; i<=l; i++)
      84                 :            :   {
      85         [ #  # ]:          0 :     while (typ[last] < i) last--;
      86                 :          0 :     t[i] = last;
      87                 :            :   }
      88                 :          0 :   t[i] = 0; setlen(t,l);
      89                 :          0 :   return t;
      90                 :            : }
      91                 :            : /* ----subgp_iter 'fun' associated to subgrouplist ------------- */
      92                 :            : static void
      93                 :       5015 : addcell(sublist_t *S, GEN H)
      94                 :            : {
      95                 :       5015 :   long *pt,i,j,L, n = lg(H)-1;
      96                 :            :   slist *cell;
      97                 :            : 
      98                 :       5015 :   L = 3;
      99         [ +  + ]:      13760 :   for (j=1; j<=n; j++)
     100                 :            :   { /* H in HNF, largest entries are on diagonal */
     101                 :       8745 :     long l = lgefint(gcoeff(H,j,j));
     102         [ -  + ]:       8745 :     if (l > L) L = l;
     103                 :            :   }
     104                 :       5015 :   L -= 2;
     105                 :       5015 :   cell = (slist*) pari_malloc(sizeof(slist)
     106                 :       6018 :                               + ((n*(n+1)) >> 1) * sizeof(long) * L);
     107                 :       5015 :   S->list->next = cell; cell->data = pt = (long*) (cell + 1);
     108                 :       5015 :   cell->prec = L;
     109         [ +  + ]:      13760 :   for (j=1; j<=n; j++)
     110         [ +  + ]:      22750 :     for(i=1; i<=j; i++) {
     111                 :      14005 :       GEN z = gcoeff(H,i,j);
     112                 :      14005 :       long h, lz = lgefint(z) - 2;
     113         [ +  + ]:      17905 :       for (h = 0; h < L - lz; h++) *pt++ = 0;
     114         [ +  + ]:      24110 :       for (h = 0; h < lz; h++) *pt++ = z[h+2];
     115                 :            :     }
     116                 :       5015 :   S->list = cell;
     117                 :       5015 :   S->count++;
     118                 :       5015 : }
     119                 :            : 
     120                 :            : static long
     121                 :       5265 : list_fun(void *E, GEN x)
     122                 :            : {
     123                 :       5265 :   sublist_t *S = (sublist_t*)E;
     124                 :       5265 :   GEN H = ZM_hnfmodid(x, S->cyc);
     125 [ +  + ][ +  + ]:       5265 :   if (!S->gen || subgroup_conductor_ok(H, S->gen)) addcell(S, H);
     126                 :       5265 :   return 0;
     127                 :            : }
     128                 :            : /* -------------------------------------------------------------- */
     129                 :            : 
     130                 :            : /* treat subgroup Hp (not in HNF, T->fun should do it if desired) */
     131                 :            : static void
     132                 :       4290 : treatsub(subgp_iter *T, GEN H)
     133                 :            : {
     134                 :            :   long i;
     135         [ +  + ]:       4290 :   if (!T->subq) {T->stop = T->fun(T->fundata, H); T->countsub++; }
     136                 :            :   else
     137                 :            :   { /* not a p group, add the trivial part */
     138                 :       1615 :     GEN Hp = gmul(T->expoI, H); /* lift H to G */
     139                 :       1615 :     long n = lg(T->subqpart)-1;
     140         [ +  + ]:       4215 :     for (i=1; i<=n; i++)
     141         [ -  + ]:       2600 :       if (T->fun(T->fundata, shallowconcat(Hp, gel(T->subqpart,i))))
     142                 :          0 :         { T->stop = 1; break; }
     143                 :       1615 :     T->countsub += n;
     144                 :            :   }
     145                 :       4290 : }
     146                 :            : 
     147                 :            : /* x a t_INT, x++. Could be optimized... */
     148                 :            : static void
     149                 :       3275 : inc(GEN x) { affii(addis(x,1), x); }
     150                 :            : 
     151                 :            : /* assume t>0 and l>1 */
     152                 :            : static void
     153                 :       1010 : dogroup(subgp_iter *T)
     154                 :            : {
     155                 :       1010 :   const GEN *powlist = T->powlist;
     156                 :       1010 :   long *M = T->M;
     157                 :       1010 :   long *L = T->L;
     158                 :       1010 :   long *c = T->c;
     159                 :       1010 :   GEN *a = T->a,  *maxa = T->maxa;
     160                 :       1010 :   GEN **g = T->g, **maxg = T->maxg;
     161                 :       1010 :   GEN **H = T->H;
     162                 :            :   pari_sp av;
     163                 :       1010 :   long i,j,k,r,n,t2,ind, t = len(M), l = len(L);
     164                 :            : 
     165         [ +  + ]:       1010 :   t2 = (l==t)? t-1: t;
     166                 :       1010 :   n = t2 * l - (t2*(t2+1))/2; /* number of gamma_ij */
     167                 :       1010 :   for (i=1, r=t+1; ; i++)
     168                 :            :   {
     169         [ +  + ]:       1595 :     if (T->available[i]) c[r++] = i;
     170         [ +  + ]:       1595 :     if (r > l) break;
     171                 :        585 :   }
     172         [ -  + ]:       1010 :   if (DEBUGLEVEL>6) { err_printf("    column selection:"); printtyp(c); }
     173                 :            :   /* a/g and maxa/maxg access the same data indexed differently */
     174         [ +  + ]:       2645 :   for (ind=0,i=1; i<=t; ind+=(l-i),i++)
     175                 :            :   {
     176                 :       1635 :     maxg[i] = maxa + (ind - (i+1)); /* only access maxg[i][i+1..l] */
     177                 :       1635 :     g[i] = a + (ind - (i+1));
     178         [ +  + ]:       3340 :     for (r=i+1; r<=l; r++)
     179         [ +  + ]:       1705 :       if (c[r] < c[i])         maxg[i][r] = powlist[M[i]-M[r]-1];
     180         [ +  + ]:       1310 :       else if (L[c[r]] < M[i]) maxg[i][r] = powlist[L[c[r]]-M[r]];
     181                 :        925 :       else                     maxg[i][r] = powlist[M[i]-M[r]];
     182                 :            :   }
     183                 :            :   /* allocate correct lg */
     184         [ +  + ]:       2715 :   for (i = 0; i<= n-1; i++) a[i] = icopy(maxa[i]);
     185         [ +  + ]:       1705 :   affui(0, a[n-1]); for (i=0; i<n-1; i++) affui(1, a[i]);
     186                 :       1010 :   av = avma;
     187         [ +  - ]:       2970 :   for(;!T->stop;)
     188                 :            :   {
     189                 :       2970 :     inc(a[n-1]);
     190         [ +  + ]:       2970 :     if (cmpii(a[n-1], maxa[n-1]) > 0)
     191                 :            :     {
     192 [ +  + ][ +  + ]:       2140 :       j=n-2; while (j>=0 && equalii(a[j], maxa[j])) j--;
     193         [ +  + ]:       1315 :       if (j < 0) return;
     194                 :            : 
     195                 :        305 :       inc(a[j]);
     196         [ +  + ]:        740 :       for (k=j+1; k<n; k++) affsi(1, a[k]);
     197                 :            :     }
     198         [ +  + ]:       5480 :     for (i=1; i<=t; i++)
     199                 :            :     {
     200         [ +  + ]:       5595 :       for (r=1; r<i; r++) H[i][c[r]] = gen_0;
     201                 :       3520 :       H[i][c[r]] = powlist[L[c[r]] - M[r]];
     202         [ +  + ]:       8470 :       for (r=i+1; r<=l; r++)
     203                 :            :       {
     204                 :       4950 :         GEN e = g[i][r];
     205                 :       4950 :         long d = L[c[r]] - M[i];
     206         [ +  + ]:       4950 :         if (c[r] < c[i])
     207                 :        580 :           e = mulii(e, powlist[d+1]);
     208         [ +  + ]:       4370 :         else if (d > 0)
     209                 :         15 :           e = mulii(e, powlist[d]);
     210                 :       4950 :         H[i][c[r]] = e;
     211                 :            :       }
     212                 :            :     }
     213                 :       1960 :     treatsub(T, (GEN)H); avma = av;
     214                 :            :   }
     215                 :            : }
     216                 :            : 
     217                 :            : /* T->c[1],...,T->c[r-1] filled */
     218                 :            : static void
     219                 :       2745 : loop(subgp_iter *T, long r)
     220                 :            : {
     221                 :            :   long j;
     222                 :            : 
     223         [ +  + ]:       2745 :   if (r > len(T->M)) {
     224                 :       1010 :     pari_sp av = avma; dogroup(T); avma = av;
     225                 :       2745 :     return;
     226                 :            :   }
     227                 :            : 
     228 [ +  + ][ +  + ]:       1735 :   if (r!=1 && (T->M[r-1] == T->M[r])) j = T->c[r-1]+1; else j = 1;
     229         [ +  + ]:       3990 :   for (  ; j<=T->maxc[r]; j++)
     230         [ +  + ]:       2255 :     if (T->available[j])
     231                 :            :     {
     232                 :       2055 :       T->c[r] = j;  T->available[j] = 0;
     233                 :       2055 :       loop(T, r+1); T->available[j] = 1;
     234                 :            :     }
     235                 :            : }
     236                 :            : 
     237                 :            : static void
     238                 :       3020 : dopsubtyp(subgp_iter *T)
     239                 :            : {
     240                 :       3020 :   pari_sp av = avma;
     241                 :       3020 :   long i,r, l = len(T->L), t = len(T->M);
     242                 :            : 
     243         [ +  + ]:       3020 :   if (!t) { treatsub(T, mkmat( zerocol(l) )); avma = av; return; }
     244         [ +  + ]:       1690 :   if (l==1) /* imply t = 1 */
     245                 :            :   {
     246                 :       1000 :     GEN p1 = gtomat(T->powlist[T->L[1]-T->M[1]]);
     247                 :       1000 :     treatsub(T, p1); avma = av; return;
     248                 :            :   }
     249                 :        690 :   T->c         = new_chunk(l+1); setlen(T->c, l);
     250                 :        690 :   T->maxc      = new_chunk(l+1);
     251                 :        690 :   T->available = new_chunk(l+1);
     252                 :        690 :   T->a   = (GEN*)new_chunk(l*(t+1));
     253                 :        690 :   T->maxa= (GEN*)new_chunk(l*(t+1));
     254                 :        690 :   T->g    = (GEN**)new_chunk(t+1);
     255                 :        690 :   T->maxg = (GEN**)new_chunk(t+1);
     256                 :            : 
     257         [ -  + ]:        690 :   if (DEBUGLEVEL>4) { err_printf("  subgroup:"); printtyp(T->M); }
     258         [ +  + ]:       1875 :   for (i=1; i<=t; i++)
     259                 :            :   {
     260         [ +  + ]:       3690 :     for (r=1; r<=l; r++)
     261         [ +  + ]:       2785 :       if (T->M[i] > T->L[r]) break;
     262                 :       1185 :     T->maxc[i] = r-1;
     263                 :            :   }
     264                 :        690 :   T->H = (GEN**)cgetg(t+1, t_MAT);
     265         [ +  + ]:       1875 :   for (i=1; i<=t; i++) T->H[i] = (GEN*)cgetg(l+1, t_COL);
     266         [ +  + ]:       2260 :   for (i=1; i<=l; i++) T->available[i]=1;
     267         [ +  + ]:       1875 :   for (i=1; i<=t; i++) T->c[i]=0;
     268                 :            :   /* go through all column selections */
     269                 :       3020 :   loop(T, 1); avma = av; return;
     270                 :            : }
     271                 :            : 
     272                 :            : static long
     273                 :       7305 : weight(long *typ)
     274                 :            : {
     275                 :       7305 :   long i, l = len(typ), w = 0;
     276         [ +  + ]:      13885 :   for (i=1; i<=l; i++) w += typ[i];
     277                 :       7305 :   return w;
     278                 :            : }
     279                 :            : 
     280                 :            : static void
     281                 :       2050 : dopsub(subgp_iter *T, GEN p, GEN indexsubq)
     282                 :            : {
     283                 :       2050 :   long *M, *L = T->L;
     284                 :       2050 :   long w,i,j,k,lsubq, wG = weight(L), wmin = 0, wmax = wG, n = len(L);
     285                 :            : 
     286         [ -  + ]:       2050 :   if (DEBUGLEVEL>4) { err_printf("\ngroup:"); printtyp(L); }
     287                 :       2050 :   T->count = 0;
     288      [ +  +  + ]:       2050 :   switch(T->boundtype)
     289                 :            :   {
     290                 :            :   case b_MAX: /* upper bound */
     291                 :         50 :     wmin = (long) (wG - (log(gtodouble(T->bound)) / log(gtodouble(p))));
     292         [ +  + ]:         50 :     if (cmpii(powiu(p, wG - wmin), T->bound) > 0) wmin++;
     293                 :         50 :     break;
     294                 :            :   case b_EXACT: /* exact value */
     295                 :       1480 :     wmin = wmax = wG - Z_pval(T->bound, p);
     296                 :       1480 :     break;
     297                 :            :   }
     298                 :       2050 :   T->M = M = new_chunk(n+1);
     299         [ +  + ]:       2050 :   if (T->subq)
     300                 :            :   {
     301                 :        480 :     lsubq = lg(T->subq);
     302         [ +  + ]:        480 :     T->subqpart = T->bound? cgetg(lsubq, t_VEC): T->subq;
     303                 :            :   }
     304                 :            :   else
     305                 :       1570 :     lsubq = 0; /* -Wall */
     306         [ +  + ]:       2485 :   M[1] = -1; for (i=2; i<=n; i++) M[i]=0;
     307         [ +  - ]:       7305 :   for(;!T->stop;) /* go through all vectors mu_{i+1} <= mu_i <= lam_i */
     308                 :            :   {
     309                 :       7305 :     M[1]++;
     310         [ +  + ]:       7305 :     if (M[1] > L[1])
     311                 :            :     {
     312         [ +  + ]:       3020 :       for (j=2; j<=n; j++)
     313 [ +  + ][ +  - ]:        970 :         if (M[j] < L[j] && M[j] < M[j-1]) break;
     314         [ +  + ]:       2510 :       if (j > n) return;
     315                 :            : 
     316         [ +  + ]:        995 :       M[j]++; for (k=1; k<j; k++) M[k]=M[j];
     317                 :            :     }
     318         [ +  + ]:       9350 :     for (j=1; j<=n; j++)
     319         [ +  + ]:       6850 :       if (!M[j]) break;
     320                 :       5255 :     setlen(M, j-1); w = weight(M);
     321 [ +  + ][ +  + ]:       5255 :     if (w >= wmin && w <= wmax)
     322                 :            :     {
     323                 :       3020 :       GEN p1 = gen_1;
     324                 :            : 
     325 [ +  + ][ +  + ]:       3020 :       if (T->subq && T->bound) /* G not a p-group */
     326                 :            :       {
     327                 :        280 :         pari_sp av = avma;
     328                 :        280 :         GEN indexH = powiu(p, wG - w);
     329                 :        280 :         GEN B = divii(T->bound, indexH);
     330                 :        280 :         k = 1;
     331         [ +  + ]:        700 :         for (i=1; i<lsubq; i++)
     332         [ +  + ]:        420 :           if (cmpii(gel(indexsubq,i), B) <= 0)
     333                 :        350 :             T->subqpart[k++] = T->subq[i];
     334                 :        280 :         setlg(T->subqpart, k); avma = av;
     335                 :            :       }
     336         [ -  + ]:       3020 :       if (DEBUGLEVEL>4)
     337                 :            :       {
     338                 :          0 :         long *Lp = conjugate(L);
     339                 :          0 :         long *Mp = conjugate(M);
     340                 :          0 :         GEN BINMAT = matqpascal(len(L)+1, p);
     341                 :            : 
     342         [ #  # ]:          0 :         if (DEBUGLEVEL>7)
     343                 :            :         {
     344                 :          0 :           err_printf("    lambda = "); printtyp(L);
     345                 :          0 :           err_printf("    lambda'= "); printtyp(Lp);
     346                 :          0 :           err_printf("    mu = "); printtyp(M);
     347                 :          0 :           err_printf("    mu'= "); printtyp(Mp);
     348                 :            :         }
     349         [ #  # ]:          0 :         for (j=1; j<=len(Mp); j++)
     350                 :            :         {
     351                 :          0 :           p1 = mulii(p1, powiu(p, Mp[j+1]*(Lp[j]-Mp[j])));
     352                 :          0 :           p1 = mulii(p1, gcoeff(BINMAT, Lp[j]-Mp[j+1]+1, Mp[j]-Mp[j+1]+1));
     353                 :            :         }
     354                 :          0 :         err_printf("  alpha_lambda(mu,p) = %Ps\n",p1);
     355                 :            :       }
     356                 :            : 
     357                 :       3020 :       T->countsub = 0; dopsubtyp(T);
     358                 :       3020 :       T->count += T->countsub;
     359                 :            : 
     360         [ -  + ]:       3020 :       if (DEBUGLEVEL>4)
     361                 :            :       {
     362                 :          0 :         err_printf("  countsub = %ld\n", T->countsub);
     363         [ #  # ]:          0 :         if (T->subq) p1 = muliu(p1,lg(T->subqpart)-1);
     364         [ #  # ]:          0 :         if (!equaliu(p1,T->countsub))
     365                 :            :         {
     366                 :          0 :           err_printf("  alpha = %Ps\n",p1);
     367                 :          0 :           pari_err_BUG("forsubgroup (alpha != countsub)");
     368                 :            :         }
     369                 :            :       }
     370                 :            :     }
     371                 :            :   }
     372                 :            : }
     373                 :            : 
     374                 :            : static void
     375                 :       2115 : parse_bound(subgp_iter *T)
     376                 :            : {
     377                 :       2115 :   GEN b, B = T->bound;
     378         [ +  + ]:       3710 :   if (!B) { T->boundtype = b_NONE; return; }
     379   [ +  +  -  - ]:       1595 :   switch(typ(B))
     380                 :            :   {
     381                 :            :   case t_INT: /* upper bound */
     382                 :         60 :     T->boundtype = b_MAX;
     383                 :         60 :     break;
     384                 :            :   case t_VEC: /* exact value */
     385                 :       1535 :     b = gel(B,1);
     386 [ +  - ][ -  + ]:       1535 :     if (lg(B) != 2 || typ(b) != t_INT) pari_err_TYPE("subgroup", B);
     387                 :       1535 :     T->boundtype = b_EXACT;
     388                 :       1535 :     T->bound = b;
     389                 :       1535 :     break;
     390                 :            :   case t_COL: /* exact type */
     391                 :          0 :     pari_err_IMPL("exact type in subgrouplist");
     392         [ #  # ]:          0 :     if (lg(B) > len(T->L)+1) pari_err_TYPE("subgroup",B);
     393                 :          0 :     T->boundtype = b_TYPE;
     394                 :          0 :     break;
     395                 :          0 :   default: pari_err_TYPE("subgroup",B);
     396                 :            :   }
     397         [ -  + ]:       1595 :   if (signe(T->bound) <= 0)
     398                 :          0 :     pari_err_DOMAIN("subgroup", "index bound", "<=", gen_0, T->bound);
     399                 :            : }
     400                 :            : 
     401                 :            : static GEN
     402                 :        800 : expand_sub(GEN x, long n)
     403                 :            : {
     404                 :        800 :   long i,j, m = lg(x);
     405                 :        800 :   GEN p = matid(n-1), q,c;
     406                 :            : 
     407         [ +  + ]:       1760 :   for (i=1; i<m; i++)
     408                 :            :   {
     409                 :        960 :     q = gel(p,i); c = gel(x,i);
     410         [ +  + ]:       2400 :     for (j=1; j<m; j++) gel(q,j) = gel(c,j);
     411         [ +  + ]:       1395 :     for (   ; j<n; j++) gel(q,j) = gen_0;
     412                 :            :   }
     413                 :        800 :   return p;
     414                 :            : }
     415                 :            : 
     416                 :            : static GEN
     417                 :       2095 : init_powlist(long k, GEN p)
     418                 :            : {
     419                 :       2095 :   GEN z = new_chunk(k+1);
     420                 :            :   long i;
     421                 :       2095 :   gel(z,0) = gen_1; gel(z,1) = p;
     422         [ +  + ]:       2525 :   for (i=2; i<=k; i++) gel(z,i) = mulii(p, gel(z,i-1));
     423                 :       2095 :   return z;
     424                 :            : }
     425                 :            : 
     426                 :            : static GEN subgrouplist_i(GEN cyc, GEN bound, GEN expoI, GEN gen);
     427                 :            : static void
     428                 :       2120 : subgroup_engine(subgp_iter *T)
     429                 :            : {
     430                 :       2120 :   pari_sp av = avma;
     431                 :       2120 :   GEN B,L,fa,primlist,p,listL,indexsubq = NULL;
     432                 :       2120 :   GEN cyc = T->cyc;
     433                 :       2120 :   long i,j,k,imax,lprim, n = lg(cyc);
     434                 :            : 
     435         [ -  + ]:       2120 :   if (typ(cyc) != t_VEC)
     436                 :            :   {
     437         [ #  # ]:          0 :     if (typ(cyc) != t_MAT) pari_err_TYPE("forsubgroup",cyc);
     438                 :          0 :     cyc = RgM_diagonal_shallow(cyc);
     439                 :            :   }
     440         [ +  + ]:       2595 :   for (i=1; i<n-1; i++)
     441         [ +  + ]:        480 :     if (!dvdii(gel(cyc,i), gel(cyc,i+1)))
     442                 :          5 :       pari_err_TYPE("forsubgroup [not a group]", cyc);
     443         [ +  + ]:       2115 :   if (n == 1) {
     444                 :         20 :     parse_bound(T);
     445         [ +  + ]:         20 :     switch(T->boundtype)
     446                 :            :     {
     447         [ +  + ]:         10 :       case b_EXACT: if (!is_pm1(T->bound)) break;
     448                 :         15 :       default: T->fun(T->fundata, cyc);
     449                 :            :     }
     450                 :         20 :     avma = av; return;
     451                 :            :   }
     452         [ -  + ]:       2095 :   if (!signe(gel(cyc,1))) pari_err_TYPE("forsubgroup [infinite group]", cyc);
     453                 :       2095 :   fa = Z_factor(gel(cyc,1)); primlist = gel(fa,1);
     454                 :       2095 :   listL = cgetg_copy(primlist, &lprim);
     455                 :       2095 :   imax = k = 0;
     456         [ +  + ]:       4930 :   for (i=1; i<lprim; i++)
     457                 :            :   {
     458                 :       2835 :     L = new_chunk(n); p = gel(primlist,i);
     459         [ +  + ]:       6165 :     for (j=1; j<n; j++)
     460                 :            :     {
     461                 :       3550 :       L[j] = Z_pval(gel(cyc,j), p);
     462         [ +  + ]:       3550 :       if (!L[j]) break;
     463                 :            :     }
     464                 :       2835 :     j--; setlen(L, j);
     465         [ +  + ]:       2835 :     if (j > k) { k = j; imax = i; }
     466                 :       2835 :     gel(listL,i) = L;
     467                 :            :   }
     468                 :       2095 :   L = gel(listL,imax); p = gel(primlist,imax);
     469                 :       2095 :   k = L[1];
     470                 :       2095 :   T->L = L;
     471                 :       2095 :   T->powlist = (GEN*)init_powlist(k, p);
     472                 :       2095 :   B = T->bound;
     473                 :       2095 :   parse_bound(T);
     474                 :            : 
     475         [ +  + ]:       2095 :   if (lprim == 2)
     476                 :            :   {
     477                 :       1615 :     T->subq = NULL;
     478         [ +  + ]:       1615 :     if (T->boundtype == b_EXACT)
     479                 :            :     {
     480                 :       1305 :       (void)Z_pvalrem(T->bound,p,&B);
     481         [ +  + ]:       1305 :       if (!is_pm1(B)) { avma = av; return; }
     482                 :            :     }
     483                 :            :   }
     484                 :            :   else
     485                 :            :   { /* not a p-group */
     486                 :        480 :     GEN cycI = leafcopy(cyc);
     487                 :            :     long lsubq;
     488         [ +  + ]:        980 :     for (i=1; i<n; i++)
     489                 :            :     {
     490                 :        610 :       gel(cycI,i) = divii(gel(cycI,i), T->powlist[L[i]]);
     491         [ +  + ]:        610 :       if (is_pm1(gel(cycI,i))) break;
     492                 :            :     }
     493                 :        480 :     setlg(cycI, i); /* cyclic factors of I */
     494         [ +  + ]:        480 :     if (T->boundtype == b_EXACT)
     495                 :            :     {
     496                 :        220 :       (void)Z_pvalrem(T->bound,p,&B);
     497                 :        220 :       B = mkvec(B);
     498                 :            :     }
     499                 :        480 :     T->expoI = gel(cycI,1);
     500                 :        480 :     T->subq = subgrouplist_i(cycI, B, T->expoI, NULL);
     501                 :            : 
     502                 :        480 :     lsubq = lg(T->subq);
     503         [ +  + ]:       1280 :     for (i=1; i<lsubq; i++)
     504                 :        800 :       gel(T->subq,i) = expand_sub(gel(T->subq,i), n);
     505         [ +  + ]:        480 :     if (T->bound)
     506                 :            :     {
     507                 :        250 :       indexsubq = cgetg(lsubq,t_VEC);
     508         [ +  + ]:        570 :       for (i=1; i<lsubq; i++)
     509                 :        320 :         gel(indexsubq,i) = ZM_det_triangular(gel(T->subq,i));
     510                 :            :     }
     511                 :            :     /* lift subgroups of I to G */
     512         [ +  + ]:       1280 :     for (i=1; i<lsubq; i++)
     513                 :        800 :       gel(T->subq,i) = gmul(T->powlist[k],gel(T->subq,i));
     514         [ -  + ]:        480 :     if (DEBUGLEVEL>6)
     515                 :          0 :       err_printf("(lifted) subgp of prime to %Ps part:\n%Ps\n",p, T->subq);
     516                 :            :   }
     517                 :       2050 :   dopsub(T, p,indexsubq);
     518         [ -  + ]:       2050 :   if (DEBUGLEVEL>4) err_printf("nb subgroup = %ld\n",T->count);
     519                 :       2115 :   avma = av;
     520                 :            : }
     521                 :            : 
     522                 :            : static GEN
     523                 :       2120 : get_snf(GEN x, long *N)
     524                 :            : {
     525                 :            :   GEN cyc;
     526                 :            :   long n;
     527   [ +  +  -  - ]:       2120 :   switch(typ(x))
     528                 :            :   {
     529                 :            :     case t_MAT:
     530         [ -  + ]:          5 :       if (!RgM_isdiagonal(x)) return NULL;
     531                 :          5 :       cyc = RgM_diagonal_shallow(x); break;
     532 [ +  + ][ -  + ]:       2115 :     case t_VEC: if (lg(x) == 4 && typ(gel(x,2)) == t_VEC) x = gel(x,2);
     533                 :       2115 :     case t_COL: cyc = leafcopy(x); break;
     534                 :          0 :     default: return NULL;
     535                 :            :   }
     536                 :       2120 :   *N = lg(cyc)-1;
     537         [ +  + ]:       2300 :   for (n = *N; n > 0; n--) /* take care of trailing 1s */
     538                 :            :   {
     539                 :       2280 :     GEN c = gel(cyc,n);
     540 [ +  - ][ -  + ]:       2280 :     if (typ(c) != t_INT || signe(c) <= 0) return NULL;
     541         [ +  + ]:       2280 :     if (!is_pm1(c)) break;
     542                 :            :   }
     543                 :       2120 :   setlg(cyc, n+1);
     544         [ +  + ]:       4700 :   for ( ; n > 0; n--)
     545                 :            :   {
     546                 :       2580 :     GEN c = gel(cyc,n);
     547 [ +  - ][ -  + ]:       2580 :     if (typ(c) != t_INT || signe(c) <= 0) return NULL;
     548                 :            :   }
     549                 :       2120 :   return cyc;
     550                 :            : }
     551                 :            : 
     552                 :            : void
     553                 :         35 : forsubgroup(void *E, long call(void*, GEN), GEN cyc, GEN bound)
     554                 :            : {
     555                 :            :   subgp_iter T;
     556                 :            :   long N;
     557                 :            : 
     558                 :         35 :   T.fun = call;
     559         [ -  + ]:         35 :   T.cyc = get_snf(cyc,&N); if (!T.cyc) pari_err_TYPE("forsubgroup",cyc);
     560                 :         35 :   T.bound = bound;
     561                 :         35 :   T.fundata = E;
     562                 :         35 :   T.stop = 0;
     563                 :         35 :   subgroup_engine(&T);
     564                 :         30 : }
     565                 :            : 
     566                 :            : void
     567                 :         35 : forsubgroup0(GEN cyc, GEN bound, GEN code)
     568                 :            : {
     569                 :         35 :   push_lex(gen_0, code);
     570                 :         35 :   forsubgroup((void*)code, &gp_evalvoid, cyc, bound);
     571                 :         30 :   pop_lex(1);
     572                 :         30 : }
     573                 :            : 
     574                 :            : static GEN
     575                 :      14005 : packtoi(long *pt, long L)
     576                 :            : {
     577                 :            :   long i, l;
     578                 :            :   GEN z;
     579         [ +  + ]:      17905 :   for (i=0; i<L; i++, pt++)
     580         [ +  + ]:      14005 :     if (*pt) break;
     581                 :      14005 :   L -= i;
     582         [ +  + ]:      14005 :   if (!L) return gen_0;
     583                 :      10105 :   l = L+2; z = cgeti(l);
     584                 :      10105 :   z[1] = evalsigne(1) | evallgefint(l);
     585         [ +  + ]:      20210 :   for (i = 2; i<l; i++) z[i] = *pt++;
     586                 :      14005 :   return z;
     587                 :            : }
     588                 :            : 
     589                 :            : static GEN
     590                 :       2085 : subgrouplist_i(GEN CYC, GEN bound, GEN expoI, GEN gen)
     591                 :            : {
     592                 :       2085 :   pari_sp av = avma;
     593                 :            :   subgp_iter T;
     594                 :            :   sublist_t S;
     595                 :            :   slist *list, *sublist;
     596                 :       2085 :   long ii,i,j,nbsub,n,N = 0; /* -Wall */
     597                 :            :   GEN z, H, cyc;
     598                 :            : 
     599                 :       2085 :   cyc = get_snf(CYC, &N);
     600         [ -  + ]:       2085 :   if (!cyc) pari_err_TYPE("subgrouplist",CYC);
     601                 :       2085 :   n = lg(cyc)-1; /* not necessarily = N */
     602                 :            : 
     603                 :       2085 :   S.list = sublist = (slist*) pari_malloc(sizeof(slist));
     604                 :       2085 :   S.cyc = cyc;
     605                 :       2085 :   S.gen = gen;
     606                 :       2085 :   S.count = 0;
     607                 :       2085 :   T.fun = &list_fun;
     608                 :       2085 :   T.fundata = (void*)&S;
     609                 :       2085 :   T.stop = 0;
     610                 :            : 
     611                 :       2085 :   T.cyc = cyc;
     612                 :       2085 :   T.bound = bound;
     613                 :       2085 :   T.expoI = expoI;
     614                 :            : 
     615                 :       2085 :   subgroup_engine(&T);
     616                 :            : 
     617                 :       2085 :   nbsub = (long)S.count;
     618                 :       2085 :   avma = av;
     619                 :       2085 :   z = cgetg(nbsub+1,t_VEC);
     620         [ +  + ]:       7100 :   for (ii=1; ii<=nbsub; ii++)
     621                 :            :   {
     622                 :            :     long *pt, L;
     623                 :       5015 :     list = sublist; sublist = list->next; pari_free(list);
     624                 :       5015 :     pt = sublist->data;
     625                 :       5015 :     L = sublist->prec;
     626                 :       5015 :     H = cgetg(N+1,t_MAT); gel(z,ii) = H;
     627         [ +  + ]:      13760 :     for (j=1; j<=n; j++)
     628                 :            :     {
     629                 :       8745 :       gel(H,j) = cgetg(N+1, t_COL);
     630         [ +  + ]:      22750 :       for (i=1; i<=j; i++) { gcoeff(H,i,j) = packtoi(pt, L); pt += L; }
     631         [ +  + ]:      14725 :       for (   ; i<=N; i++) gcoeff(H,i,j) = gen_0;
     632                 :            :     }
     633         [ +  + ]:       5385 :     for (   ; j<=N; j++) gel(H,j) = col_ei(N, j);
     634                 :            :   }
     635                 :       2085 :   pari_free(sublist); return z;
     636                 :            : }
     637                 :            : 
     638                 :            : GEN
     639                 :       1580 : subgrouplist(GEN cyc, GEN bound)
     640                 :            : {
     641                 :       1580 :   return subgrouplist_i(cyc,bound,NULL,NULL);
     642                 :            : }
     643                 :            : 
     644                 :            : GEN
     645                 :         25 : subgroupcondlist(GEN cyc, GEN bound, GEN L)
     646                 :            : {
     647                 :         25 :   return subgrouplist_i(cyc,bound,NULL,L);
     648                 :            : }

Generated by: LCOV version 1.9