Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - subgroup.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 19191-d7615ef) Lines: 345 362 95.3 %
Date: 2016-07-23 07:10:28 Functions: 22 22 100.0 %
Legend: Lines: hit not hit

          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          35 : printtyp(const long *typ) /*Used only for ddebugging */
      68             : {
      69          35 :   long i, l = len(typ);
      70          35 :   for (i=1; i<=l; i++) err_printf(" %ld ",typ[i]);
      71          35 :   err_printf("\n");
      72          35 : }
      73             : 
      74             : /* compute conjugate partition of typ */
      75             : static long*
      76          70 : conjugate(long *typ)
      77             : {
      78          70 :   long *t, i, k = len(typ), l, last;
      79             : 
      80          70 :   if (!k) { t = new_chunk(1); setlen(t,0); return t; }
      81          63 :   l = typ[1]; t = new_chunk(l+2);
      82          63 :   t[1] = k; last = k;
      83          63 :   for (i=2; i<=l; i++)
      84             :   {
      85           0 :     while (typ[last] < i) last--;
      86           0 :     t[i] = last;
      87             :   }
      88          63 :   t[i] = 0; setlen(t,l);
      89          63 :   return t;
      90             : }
      91             : /* ----subgp_iter 'fun' attached to subgrouplist ------------- */
      92             : static void
      93        4718 : addcell(sublist_t *S, GEN H)
      94             : {
      95        4718 :   long *pt,i,j,L, n = lg(H)-1;
      96             :   slist *cell;
      97             : 
      98        4718 :   L = 3;
      99       14686 :   for (j=1; j<=n; j++)
     100             :   { /* H in HNF, largest entries are on diagonal */
     101        9968 :     long l = lgefint(gcoeff(H,j,j));
     102        9968 :     if (l > L) L = l;
     103             :   }
     104        4718 :   L -= 2;
     105        5392 :   cell = (slist*) pari_malloc(sizeof(slist)
     106        5392 :                               + ((n*(n+1)) >> 1) * sizeof(long) * L);
     107        4718 :   S->list->next = cell; cell->data = pt = (long*) (cell + 1);
     108        4718 :   cell->prec = L;
     109       14686 :   for (j=1; j<=n; j++)
     110       28511 :     for(i=1; i<=j; i++) {
     111       18543 :       GEN z = gcoeff(H,i,j);
     112       18543 :       long h, lz = lgefint(z) - 2;
     113       18543 :       for (h = 0; h < L - lz; h++) *pt++ = 0;
     114       18543 :       for (h = 0; h < lz; h++) *pt++ = z[h+2];
     115             :     }
     116        4718 :   S->list = cell;
     117        4718 :   S->count++;
     118        4718 : }
     119             : 
     120             : static long
     121        5068 : list_fun(void *E, GEN x)
     122             : {
     123        5068 :   sublist_t *S = (sublist_t*)E;
     124        5068 :   GEN H = ZM_hnfmodid(x, S->cyc);
     125        5068 :   if (!S->gen || subgroup_conductor_ok(H, S->gen)) addcell(S, H);
     126        5068 :   return 0;
     127             : }
     128             : /* -------------------------------------------------------------- */
     129             : 
     130             : /* treat subgroup Hp (not in HNF, T->fun should do it if desired) */
     131             : static void
     132        4823 : treatsub(subgp_iter *T, GEN H)
     133             : {
     134             :   long i;
     135        4823 :   if (!T->subq) {T->stop = T->fun(T->fundata, H); T->countsub++; }
     136             :   else
     137             :   { /* not a p group, add the trivial part */
     138        1183 :     GEN Hp = gmul(T->expoI, H); /* lift H to G */
     139        1183 :     long n = lg(T->subqpart)-1;
     140        2625 :     for (i=1; i<=n; i++)
     141        1442 :       if (T->fun(T->fundata, shallowconcat(Hp, gel(T->subqpart,i))))
     142           0 :         { T->stop = 1; break; }
     143        1183 :     T->countsub += n;
     144             :   }
     145        4823 : }
     146             : 
     147             : /* x a t_INT, x++. Could be optimized... */
     148             : static void
     149        4522 : inc(GEN x) { affii(addis(x,1), x); }
     150             : 
     151             : /* assume t>0 and l>1 */
     152             : static void
     153        1204 : dogroup(subgp_iter *T)
     154             : {
     155        1204 :   const GEN *powlist = T->powlist;
     156        1204 :   long *M = T->M;
     157        1204 :   long *L = T->L;
     158        1204 :   long *c = T->c;
     159        1204 :   GEN *a = T->a,  *maxa = T->maxa;
     160        1204 :   GEN **g = T->g, **maxg = T->maxg;
     161        1204 :   GEN **H = T->H;
     162             :   pari_sp av;
     163        1204 :   long i,j,k,r,n,t2,ind, t = len(M), l = len(L);
     164             : 
     165        1204 :   t2 = (l==t)? t-1: t;
     166        1204 :   n = t2 * l - (t2*(t2+1))/2; /* number of gamma_ij */
     167        2079 :   for (i=1, r=t+1; ; i++)
     168             :   {
     169        2079 :     if (T->available[i]) c[r++] = i;
     170        2079 :     if (r > l) break;
     171         875 :   }
     172        1204 :   if (DEBUGLEVEL>6) { err_printf("    column selection:"); printtyp(c); }
     173             :   /* a/g and maxa/maxg access the same data indexed differently */
     174        3255 :   for (ind=0,i=1; i<=t; ind+=(l-i),i++)
     175             :   {
     176        2051 :     maxg[i] = maxa + (ind - (i+1)); /* only access maxg[i][i+1..l] */
     177        2051 :     g[i] = a + (ind - (i+1));
     178        4550 :     for (r=i+1; r<=l; r++)
     179        2499 :       if (c[r] < c[i])         maxg[i][r] = powlist[M[i]-M[r]-1];
     180        1869 :       else if (L[c[r]] < M[i]) maxg[i][r] = powlist[L[c[r]]-M[r]];
     181        1442 :       else                     maxg[i][r] = powlist[M[i]-M[r]];
     182             :   }
     183             :   /* allocate correct lg */
     184        1204 :   for (i = 0; i<= n-1; i++) a[i] = icopy(maxa[i]);
     185        1204 :   affui(0, a[n-1]); for (i=0; i<n-1; i++) affui(1, a[i]);
     186        1204 :   av = avma;
     187        5138 :   for(;!T->stop;)
     188             :   {
     189        3934 :     inc(a[n-1]);
     190        3934 :     if (cmpii(a[n-1], maxa[n-1]) > 0)
     191             :     {
     192        1792 :       j=n-2; while (j>=0 && equalii(a[j], maxa[j])) j--;
     193        2996 :       if (j < 0) return;
     194             : 
     195         588 :       inc(a[j]);
     196         588 :       for (k=j+1; k<n; k++) affsi(1, a[k]);
     197             :     }
     198        7945 :     for (i=1; i<=t; i++)
     199             :     {
     200        5215 :       for (r=1; r<i; r++) H[i][c[r]] = gen_0;
     201        5215 :       H[i][c[r]] = powlist[L[c[r]] - M[r]];
     202       13720 :       for (r=i+1; r<=l; r++)
     203             :       {
     204        8505 :         GEN e = g[i][r];
     205        8505 :         long d = L[c[r]] - M[i];
     206        8505 :         if (c[r] < c[i])
     207        1099 :           e = mulii(e, powlist[d+1]);
     208        7406 :         else if (d > 0)
     209          21 :           e = mulii(e, powlist[d]);
     210        8505 :         H[i][c[r]] = e;
     211             :       }
     212             :     }
     213        2730 :     treatsub(T, (GEN)H); avma = av;
     214             :   }
     215             : }
     216             : 
     217             : /* T->c[1],...,T->c[r-1] filled */
     218             : static void
     219        3388 : loop(subgp_iter *T, long r)
     220             : {
     221             :   long j;
     222             : 
     223        3388 :   if (r > len(T->M)) {
     224        1204 :     pari_sp av = avma; dogroup(T); avma = av;
     225        4592 :     return;
     226             :   }
     227             : 
     228        2184 :   if (r!=1 && (T->M[r-1] == T->M[r])) j = T->c[r-1]+1; else j = 1;
     229        5040 :   for (  ; j<=T->maxc[r]; j++)
     230        2856 :     if (T->available[j])
     231             :     {
     232        2632 :       T->c[r] = j;  T->available[j] = 0;
     233        2632 :       loop(T, r+1); T->available[j] = 1;
     234             :     }
     235             : }
     236             : 
     237             : static void
     238        2849 : dopsubtyp(subgp_iter *T)
     239             : {
     240        2849 :   pari_sp av = avma;
     241        2849 :   long i,r, l = len(T->L), t = len(T->M);
     242             : 
     243        2849 :   if (!t) { treatsub(T, mkmat( zerocol(l) )); avma = av; return; }
     244        1610 :   if (l==1) /* imply t = 1 */
     245             :   {
     246         854 :     GEN p1 = gtomat(T->powlist[T->L[1]-T->M[1]]);
     247         854 :     treatsub(T, p1); avma = av; return;
     248             :   }
     249         756 :   T->c         = new_chunk(l+1); setlen(T->c, l);
     250         756 :   T->maxc      = new_chunk(l+1);
     251         756 :   T->available = new_chunk(l+1);
     252         756 :   T->a   = (GEN*)new_chunk(l*(t+1));
     253         756 :   T->maxa= (GEN*)new_chunk(l*(t+1));
     254         756 :   T->g    = (GEN**)new_chunk(t+1);
     255         756 :   T->maxg = (GEN**)new_chunk(t+1);
     256             : 
     257         756 :   if (DEBUGLEVEL>4) { err_printf("  subgroup:"); printtyp(T->M); }
     258        2114 :   for (i=1; i<=t; i++)
     259             :   {
     260        4473 :     for (r=1; r<=l; r++)
     261        3395 :       if (T->M[i] > T->L[r]) break;
     262        1358 :     T->maxc[i] = r-1;
     263             :   }
     264         756 :   T->H = (GEN**)cgetg(t+1, t_MAT);
     265         756 :   for (i=1; i<=t; i++) T->H[i] = (GEN*)cgetg(l+1, t_COL);
     266         756 :   for (i=1; i<=l; i++) T->available[i]=1;
     267         756 :   for (i=1; i<=t; i++) T->c[i]=0;
     268             :   /* go through all column selections */
     269         756 :   loop(T, 1); avma = av; return;
     270             : }
     271             : 
     272             : static long
     273        8456 : weight(long *typ)
     274             : {
     275        8456 :   long i, l = len(typ), w = 0;
     276        8456 :   for (i=1; i<=l; i++) w += typ[i];
     277        8456 :   return w;
     278             : }
     279             : 
     280             : static void
     281        2338 : dopsub(subgp_iter *T, GEN p, GEN indexsubq)
     282             : {
     283        2338 :   long *M, *L = T->L;
     284        2338 :   long w,i,j,k,lsubq, wG = weight(L), wmin = 0, wmax = wG, n = len(L);
     285             : 
     286        2338 :   if (DEBUGLEVEL>4) { err_printf("\ngroup:"); printtyp(L); }
     287        2338 :   T->count = 0;
     288        2338 :   switch(T->boundtype)
     289             :   {
     290             :   case b_MAX: /* upper bound */
     291          70 :     wmin = (long) (wG - (log(gtodouble(T->bound)) / log(gtodouble(p))));
     292          70 :     if (cmpii(powiu(p, wG - wmin), T->bound) > 0) wmin++;
     293          70 :     break;
     294             :   case b_EXACT: /* exact value */
     295        2135 :     wmin = wmax = wG - Z_pval(T->bound, p);
     296        2135 :     break;
     297             :   }
     298        2338 :   T->M = M = new_chunk(n+1);
     299        2338 :   if (T->subq)
     300             :   {
     301         364 :     lsubq = lg(T->subq);
     302         364 :     T->subqpart = T->bound? cgetg(lsubq, t_VEC): T->subq;
     303             :   }
     304             :   else
     305        1974 :     lsubq = 0; /* -Wall */
     306        2338 :   M[1] = -1; for (i=2; i<=n; i++) M[i]=0;
     307       10794 :   for(;!T->stop;) /* go through all vectors mu_{i+1} <= mu_i <= lam_i */
     308             :   {
     309        8456 :     M[1]++;
     310        8456 :     if (M[1] > L[1])
     311             :     {
     312        3626 :       for (j=2; j<=n; j++)
     313        1288 :         if (M[j] < L[j] && M[j] < M[j-1]) break;
     314        5278 :       if (j > n) return;
     315             : 
     316         602 :       M[j]++; for (k=1; k<j; k++) M[k]=M[j];
     317             :     }
     318       11060 :     for (j=1; j<=n; j++)
     319        8169 :       if (!M[j]) break;
     320        6118 :     setlen(M, j-1); w = weight(M);
     321        6118 :     if (w >= wmin && w <= wmax)
     322             :     {
     323        2849 :       GEN p1 = gen_1;
     324             : 
     325        2849 :       if (T->subq && T->bound) /* G not a p-group */
     326             :       {
     327         378 :         pari_sp av = avma;
     328         378 :         GEN indexH = powiu(p, wG - w);
     329         378 :         GEN B = divii(T->bound, indexH);
     330         378 :         k = 1;
     331         952 :         for (i=1; i<lsubq; i++)
     332         574 :           if (cmpii(gel(indexsubq,i), B) <= 0)
     333         476 :             T->subqpart[k++] = T->subq[i];
     334         378 :         setlg(T->subqpart, k); avma = av;
     335             :       }
     336        2849 :       if (DEBUGLEVEL>4)
     337             :       {
     338          35 :         long *Lp = conjugate(L);
     339          35 :         long *Mp = conjugate(M);
     340          35 :         GEN BINMAT = matqpascal(len(L)+1, p);
     341             : 
     342          35 :         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          63 :         for (j=1; j<=len(Mp); j++)
     350             :         {
     351          28 :           p1 = mulii(p1, powiu(p, Mp[j+1]*(Lp[j]-Mp[j])));
     352          28 :           p1 = mulii(p1, gcoeff(BINMAT, Lp[j]-Mp[j+1]+1, Mp[j]-Mp[j+1]+1));
     353             :         }
     354          35 :         err_printf("  alpha_lambda(mu,p) = %Ps\n",p1);
     355             :       }
     356             : 
     357        2849 :       T->countsub = 0; dopsubtyp(T);
     358        2849 :       T->count += T->countsub;
     359             : 
     360        2849 :       if (DEBUGLEVEL>4)
     361             :       {
     362          35 :         err_printf("  countsub = %ld\n", T->countsub);
     363          35 :         if (T->subq) p1 = muliu(p1,lg(T->subqpart)-1);
     364          35 :         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        2443 : parse_bound(subgp_iter *T)
     376             : {
     377        2443 :   GEN b, B = T->bound;
     378        4872 :   if (!B) { T->boundtype = b_NONE; return; }
     379        2310 :   switch(typ(B))
     380             :   {
     381             :   case t_INT: /* upper bound */
     382          91 :     T->boundtype = b_MAX;
     383          91 :     break;
     384             :   case t_VEC: /* exact value */
     385        2212 :     b = gel(B,1);
     386        2212 :     if (lg(B) != 2 || typ(b) != t_INT) pari_err_TYPE("subgroup", B);
     387        2212 :     T->boundtype = b_EXACT;
     388        2212 :     T->bound = b;
     389        2212 :     break;
     390             :   case t_COL: /* exact type */
     391           7 :     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        2303 :   if (signe(T->bound) <= 0)
     398           7 :     pari_err_DOMAIN("subgroup", "index bound", "<=", gen_0, T->bound);
     399             : }
     400             : 
     401             : static GEN
     402         490 : expand_sub(GEN x, long n)
     403             : {
     404         490 :   long i,j, m = lg(x);
     405         490 :   GEN p = matid(n-1), q,c;
     406             : 
     407        1204 :   for (i=1; i<m; i++)
     408             :   {
     409         714 :     q = gel(p,i); c = gel(x,i);
     410         714 :     for (j=1; j<m; j++) gel(q,j) = gel(c,j);
     411         714 :     for (   ; j<n; j++) gel(q,j) = gen_0;
     412             :   }
     413         490 :   return p;
     414             : }
     415             : 
     416             : static GEN
     417        2415 : init_powlist(long k, GEN p)
     418             : {
     419        2415 :   GEN z = new_chunk(k+1);
     420             :   long i;
     421        2415 :   gel(z,0) = gen_1; gel(z,1) = p;
     422        2415 :   for (i=2; i<=k; i++) gel(z,i) = mulii(p, gel(z,i-1));
     423        2415 :   return z;
     424             : }
     425             : 
     426             : static GEN subgrouplist_i(GEN cyc, GEN bound, GEN expoI, GEN gen);
     427             : static void
     428        2450 : subgroup_engine(subgp_iter *T)
     429             : {
     430        2450 :   pari_sp av = avma;
     431        2450 :   GEN B,L,fa,primlist,p,listL,indexsubq = NULL;
     432        2450 :   GEN cyc = T->cyc;
     433        2450 :   long i,j,k,imax,lprim, n = lg(cyc);
     434             : 
     435        2450 :   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        3087 :   for (i=1; i<n-1; i++)
     441         644 :     if (!dvdii(gel(cyc,i), gel(cyc,i+1)))
     442           7 :       pari_err_TYPE("forsubgroup [not a group]", cyc);
     443        2443 :   if (n == 1) {
     444          28 :     parse_bound(T);
     445          28 :     switch(T->boundtype)
     446             :     {
     447          14 :       case b_EXACT: if (!is_pm1(T->bound)) break;
     448          21 :       default: T->fun(T->fundata, cyc);
     449             :     }
     450         119 :     avma = av; return;
     451             :   }
     452        2415 :   if (!signe(gel(cyc,1))) pari_err_TYPE("forsubgroup [infinite group]", cyc);
     453        2415 :   fa = Z_factor(gel(cyc,1)); primlist = gel(fa,1);
     454        2415 :   listL = cgetg_copy(primlist, &lprim);
     455        2415 :   imax = k = 0;
     456        5558 :   for (i=1; i<lprim; i++)
     457             :   {
     458        3143 :     L = new_chunk(n); p = gel(primlist,i);
     459        6951 :     for (j=1; j<n; j++)
     460             :     {
     461        4046 :       L[j] = Z_pval(gel(cyc,j), p);
     462        4046 :       if (!L[j]) break;
     463             :     }
     464        3143 :     j--; setlen(L, j);
     465        3143 :     if (j > k) { k = j; imax = i; }
     466        3143 :     gel(listL,i) = L;
     467             :   }
     468        2415 :   L = gel(listL,imax); p = gel(primlist,imax);
     469        2415 :   k = L[1];
     470        2415 :   T->L = L;
     471        2415 :   T->powlist = (GEN*)init_powlist(k, p);
     472        2415 :   B = T->bound;
     473        2415 :   parse_bound(T);
     474             : 
     475        2401 :   if (lprim == 2)
     476             :   {
     477        2037 :     T->subq = NULL;
     478        2037 :     if (T->boundtype == b_EXACT)
     479             :     {
     480        1904 :       (void)Z_pvalrem(T->bound,p,&B);
     481        1904 :       if (!is_pm1(B)) { avma = av; return; }
     482             :     }
     483             :   }
     484             :   else
     485             :   { /* not a p-group */
     486         364 :     GEN cycI = leafcopy(cyc);
     487             :     long lsubq;
     488         756 :     for (i=1; i<n; i++)
     489             :     {
     490         476 :       gel(cycI,i) = divii(gel(cycI,i), T->powlist[L[i]]);
     491         476 :       if (is_pm1(gel(cycI,i))) break;
     492             :     }
     493         364 :     setlg(cycI, i); /* cyclic factors of I */
     494         364 :     if (T->boundtype == b_EXACT)
     495             :     {
     496         294 :       (void)Z_pvalrem(T->bound,p,&B);
     497         294 :       B = mkvec(B);
     498             :     }
     499         364 :     T->expoI = gel(cycI,1);
     500         364 :     T->subq = subgrouplist_i(cycI, B, T->expoI, NULL);
     501             : 
     502         364 :     lsubq = lg(T->subq);
     503         854 :     for (i=1; i<lsubq; i++)
     504         490 :       gel(T->subq,i) = expand_sub(gel(T->subq,i), n);
     505         364 :     if (T->bound)
     506             :     {
     507         336 :       indexsubq = cgetg(lsubq,t_VEC);
     508         770 :       for (i=1; i<lsubq; i++)
     509         434 :         gel(indexsubq,i) = ZM_det_triangular(gel(T->subq,i));
     510             :     }
     511             :     /* lift subgroups of I to G */
     512         854 :     for (i=1; i<lsubq; i++)
     513         490 :       gel(T->subq,i) = gmul(T->powlist[k],gel(T->subq,i));
     514         364 :     if (DEBUGLEVEL>6)
     515           0 :       err_printf("(lifted) subgp of prime to %Ps part:\n%Ps\n",p, T->subq);
     516             :   }
     517        2338 :   dopsub(T, p,indexsubq);
     518        2338 :   if (DEBUGLEVEL>4) {
     519           7 :     err_printf("nb subgroup = %ld\n",T->count);
     520           7 :     err_flush();
     521             :   }
     522        2338 :   avma = av;
     523             : }
     524             : 
     525             : static GEN
     526        2450 : get_snf(GEN x, long *N)
     527             : {
     528             :   GEN cyc;
     529             :   long n;
     530        2450 :   switch(typ(x))
     531             :   {
     532             :     case t_MAT:
     533           7 :       if (!RgM_isdiagonal(x)) return NULL;
     534           7 :       cyc = RgM_diagonal_shallow(x); break;
     535        2443 :     case t_VEC: if (lg(x) == 4 && typ(gel(x,2)) == t_VEC) x = gel(x,2);
     536        2443 :     case t_COL: cyc = leafcopy(x); break;
     537           0 :     default: return NULL;
     538             :   }
     539        2450 :   *N = lg(cyc)-1;
     540        2625 :   for (n = *N; n > 0; n--) /* take care of trailing 1s */
     541             :   {
     542        2597 :     GEN c = gel(cyc,n);
     543        2597 :     if (typ(c) != t_INT || signe(c) <= 0) return NULL;
     544        2597 :     if (!is_pm1(c)) break;
     545             :   }
     546        2450 :   setlg(cyc, n+1);
     547        5516 :   for ( ; n > 0; n--)
     548             :   {
     549        3066 :     GEN c = gel(cyc,n);
     550        3066 :     if (typ(c) != t_INT || signe(c) <= 0) return NULL;
     551             :   }
     552        2450 :   return cyc;
     553             : }
     554             : 
     555             : void
     556          49 : forsubgroup(void *E, long call(void*, GEN), GEN cyc, GEN bound)
     557             : {
     558             :   subgp_iter T;
     559             :   long N;
     560             : 
     561          49 :   T.fun = call;
     562          49 :   T.cyc = get_snf(cyc,&N); if (!T.cyc) pari_err_TYPE("forsubgroup",cyc);
     563          49 :   T.bound = bound;
     564          49 :   T.fundata = E;
     565          49 :   T.stop = 0;
     566          49 :   subgroup_engine(&T);
     567          42 : }
     568             : 
     569             : void
     570          49 : forsubgroup0(GEN cyc, GEN bound, GEN code)
     571             : {
     572          49 :   push_lex(gen_0, code);
     573          49 :   forsubgroup((void*)code, &gp_evalvoid, cyc, bound);
     574          42 :   pop_lex(1);
     575          42 : }
     576             : 
     577             : static GEN
     578       18543 : packtoi(long *pt, long L)
     579             : {
     580             :   long i, l;
     581             :   GEN z;
     582       24976 :   for (i=0; i<L; i++, pt++)
     583       18543 :     if (*pt) break;
     584       18543 :   L -= i;
     585       18543 :   if (!L) return gen_0;
     586       12110 :   l = L+2; z = cgeti(l);
     587       12110 :   z[1] = evalsigne(1) | evallgefint(l);
     588       12110 :   for (i = 2; i<l; i++) z[i] = *pt++;
     589       12110 :   return z;
     590             : }
     591             : 
     592             : static GEN
     593        2401 : subgrouplist_i(GEN CYC, GEN bound, GEN expoI, GEN gen)
     594             : {
     595        2401 :   pari_sp av = avma;
     596             :   subgp_iter T;
     597             :   sublist_t S;
     598             :   slist *list, *sublist;
     599        2401 :   long ii,i,j,nbsub,n,N = 0; /* -Wall */
     600             :   GEN z, H, cyc;
     601             : 
     602        2401 :   cyc = get_snf(CYC, &N);
     603        2401 :   if (!cyc) pari_err_TYPE("subgrouplist",CYC);
     604        2401 :   n = lg(cyc)-1; /* not necessarily = N */
     605             : 
     606        2401 :   S.list = sublist = (slist*) pari_malloc(sizeof(slist));
     607        2401 :   S.cyc = cyc;
     608        2401 :   S.gen = gen;
     609        2401 :   S.count = 0;
     610        2401 :   T.fun = &list_fun;
     611        2401 :   T.fundata = (void*)&S;
     612        2401 :   T.stop = 0;
     613             : 
     614        2401 :   T.cyc = cyc;
     615        2401 :   T.bound = bound;
     616        2401 :   T.expoI = expoI;
     617             : 
     618        2401 :   subgroup_engine(&T);
     619             : 
     620        2387 :   nbsub = (long)S.count;
     621        2387 :   avma = av;
     622        2387 :   z = cgetg(nbsub+1,t_VEC);
     623        7105 :   for (ii=1; ii<=nbsub; ii++)
     624             :   {
     625             :     long *pt, L;
     626        4718 :     list = sublist; sublist = list->next; pari_free(list);
     627        4718 :     pt = sublist->data;
     628        4718 :     L = sublist->prec;
     629        4718 :     H = cgetg(N+1,t_MAT); gel(z,ii) = H;
     630       14686 :     for (j=1; j<=n; j++)
     631             :     {
     632        9968 :       gel(H,j) = cgetg(N+1, t_COL);
     633        9968 :       for (i=1; i<=j; i++) { gcoeff(H,i,j) = packtoi(pt, L); pt += L; }
     634        9968 :       for (   ; i<=N; i++) gcoeff(H,i,j) = gen_0;
     635             :     }
     636        4718 :     for (   ; j<=N; j++) gel(H,j) = col_ei(N, j);
     637             :   }
     638        2387 :   pari_free(sublist); return z;
     639             : }
     640             : 
     641             : GEN
     642        2002 : subgrouplist(GEN cyc, GEN bound)
     643             : {
     644        2002 :   return subgrouplist_i(cyc,bound,NULL,NULL);
     645             : }
     646             : 
     647             : GEN
     648          35 : subgroupcondlist(GEN cyc, GEN bound, GEN L)
     649             : {
     650          35 :   return subgrouplist_i(cyc,bound,NULL,L);
     651             : }

Generated by: LCOV version 1.11