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 - hyperell.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 16781-61614ca) Lines: 312 335 93.1 %
Date: 2014-09-14 Functions: 25 26 96.2 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 103 164 62.8 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2014  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                 :            : /********************************************************************/
      15                 :            : /**                                                                **/
      16                 :            : /**                     HYPERELLIPTIC CURVES                       **/
      17                 :            : /**                                                                **/
      18                 :            : /********************************************************************/
      19                 :            : #include "pari.h"
      20                 :            : #include "paripriv.h"
      21                 :            : 
      22                 :            : static GEN
      23                 :       7749 : FpXXQ_red(GEN S, GEN T, GEN p)
      24                 :            : {
      25                 :       7749 :   pari_sp av = avma;
      26                 :       7749 :   long dS = degpol(S);
      27                 :       7749 :   GEN A = cgetg(dS+3, t_POL);
      28                 :       7749 :   GEN C = pol_0(varn(T));
      29                 :            :   long i;
      30         [ +  + ]:     730415 :   for(i=dS; i>0; i--)
      31                 :            :   {
      32                 :     722666 :     GEN Si = FpX_add(C, gel(S,i+2), p);
      33                 :     722666 :     GEN R, Q = FpX_divrem(Si, T, p, &R);
      34                 :     722666 :     gel(A,i+2) = R;
      35                 :     722666 :     C = Q;
      36                 :            :   }
      37                 :       7749 :   gel(A,2) = FpX_add(C, gel(S,2), p);
      38                 :       7749 :   A[1] = S[1];
      39                 :       7749 :   return gerepilecopy(av, FpXX_renormalize(A,dS+3));
      40                 :            : }
      41                 :            : 
      42                 :            : static GEN
      43                 :       1617 : FpXXQ_sqr(GEN x, GEN T, GEN p)
      44                 :            : {
      45                 :       1617 :   pari_sp av = avma;
      46                 :            :   GEN z, kx;
      47                 :       1617 :   long n = degpol(T);
      48                 :       1617 :   kx = ZXX_to_Kronecker(x, n);
      49                 :       1617 :   z = Kronecker_to_ZXX(FpX_sqr(kx, p), n, varn(T));
      50                 :       1617 :   return gerepileupto(av, FpXXQ_red(z, T, p));
      51                 :            : }
      52                 :            : 
      53                 :            : static GEN
      54                 :       6132 : FpXXQ_mul(GEN x, GEN y, GEN T, GEN p)
      55                 :            : {
      56                 :       6132 :   pari_sp av = avma;
      57                 :            :   GEN z, kx, ky;
      58                 :       6132 :   long n = degpol(T);
      59                 :       6132 :   kx = ZXX_to_Kronecker(x, n);
      60                 :       6132 :   ky = ZXX_to_Kronecker(y, n);
      61                 :       6132 :   z = Kronecker_to_ZXX(FpX_mul(ky,kx,p), n, varn(T));
      62                 :       6132 :   return gerepileupto(av, FpXXQ_red(z, T, p));
      63                 :            : }
      64                 :            : 
      65                 :            : static GEN
      66                 :        469 : ZpXXQ_invsqrt(GEN S, GEN T, ulong p, long e)
      67                 :            : {
      68                 :        469 :   pari_sp av = avma, av2, lim;
      69                 :            :   ulong mask;
      70                 :        469 :   long v = varn(S), n=1;
      71                 :        469 :   GEN a = pol_1(v);
      72         [ -  + ]:        469 :   if (e <= 1) return gerepilecopy(av, a);
      73                 :        469 :   mask = quadratic_prec_mask(e);
      74                 :        469 :   av2 = avma; lim = stack_lim(av2, 1);
      75         [ +  + ]:       2086 :   for (;mask>1;)
      76                 :            :   {
      77                 :            :     GEN q, q2, q22, f, fq, afq;
      78                 :       1617 :     long n2 = n;
      79         [ +  + ]:       1617 :     n<<=1; if (mask & 1) n--;
      80                 :       1617 :     mask >>= 1;
      81                 :       1617 :     q = powuu(p,n), q2 = powuu(p,n2);
      82                 :       1617 :     f = RgX_sub(FpXXQ_mul(S, FpXXQ_sqr(a, T, q), T, q), pol_1(v));
      83                 :       1617 :     fq = ZXX_Z_divexact(f, q2);
      84                 :       1617 :     q22 = shifti(addis(q2,1),-1);
      85                 :       1617 :     afq = FpXX_Fp_mul(FpXXQ_mul(a, fq, T, q2), q22, q2);
      86                 :       1617 :     a = RgX_sub(a, ZXX_Z_mul(afq, q2));
      87         [ -  + ]:       1617 :     if (low_stack(lim, stack_lim(av2,1)))
      88                 :            :     {
      89         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_invsqrt, e = %ld", n);
      90                 :          0 :       a = gerepileupto(av2, a);
      91                 :            :     }
      92                 :            :   }
      93                 :        469 :   return gerepileupto(av, a);
      94                 :            : }
      95                 :            : 
      96                 :            : static GEN
      97         [ +  + ]:       1232 : to_ZX(GEN a, long v) { return typ(a)==t_INT? scalarpol(a,v): a; }
      98                 :            : 
      99                 :            : static void
     100                 :          0 : is_sing(GEN H, ulong p)
     101                 :            : {
     102                 :          0 :   pari_err_DOMAIN("hyperellpadicfrobenius","H","is singular at",utoi(p),H);
     103                 :          0 : }
     104                 :            : 
     105                 :            : static void
     106                 :        469 : get_UV(GEN *U, GEN *V, GEN T, ulong p, long e)
     107                 :            : {
     108                 :        469 :   GEN q = powuu(p,e), d;
     109                 :        469 :   GEN dT = FpX_deriv(T, q);
     110                 :        469 :   GEN R = polresultantext(T, dT);
     111                 :        469 :   long v = varn(T);
     112         [ -  + ]:        469 :   if (dvdiu(gel(R,3),p)) is_sing(T, p);
     113                 :        469 :   d = Fp_inv(gel(R,3), q);
     114                 :        469 :   *U = FpX_Fp_mul(FpX_red(to_ZX(gel(R,1),v),q),d,q);
     115                 :        469 :   *V = FpX_Fp_mul(FpX_red(to_ZX(gel(R,2),v),q),d,q);
     116                 :        469 : }
     117                 :            : 
     118                 :            : static GEN
     119                 :      34062 : frac_to_Fp(GEN a, GEN b, GEN p)
     120                 :            : {
     121                 :      34062 :   GEN d = gcdii(a, b);
     122                 :      34062 :   return Fp_div(diviiexact(a, d), diviiexact(b, d), p);
     123                 :            : }
     124                 :            : 
     125                 :            : static GEN
     126                 :       2898 : ZpXXQ_frob(GEN S, GEN U, GEN V, GEN T, ulong p, long e)
     127                 :            : {
     128                 :       2898 :   pari_sp av = avma, av2, lim;
     129                 :       2898 :   long i, pr = degpol(S), dT = degpol(T);
     130                 :       2898 :   GEN q = powuu(p,e);
     131                 :       2898 :   GEN Tp = FpX_deriv(T, q), Tp1 = RgX_shift_shallow(Tp, 1);
     132                 :       2898 :   GEN M = gel(S,pr+2), R;
     133                 :       2898 :   av2 = avma; lim = stack_lim(av2, 1);
     134         [ +  + ]:     409794 :   for(i = pr-1; i>=0; i--)
     135                 :            :   {
     136                 :            :     GEN A, B, H, Bc;
     137                 :            :     ulong v, r;
     138                 :     406896 :     H = FpX_divrem(FpX_mul(V,M,q), T, q, &B);
     139                 :     406896 :     A = FpX_add(FpX_mul(U,M,q), FpX_mul(H, Tp, q),q);
     140                 :     406896 :     v = u_lvalrem(2*i+1,p,&r);
     141                 :     406896 :     Bc = FpX_deriv(B, q);
     142                 :     406896 :     Bc = FpX_Fp_mul(ZX_Z_divexact(Bc,powuu(p,v)),Fp_div(gen_2, utoi(r), q), q);
     143                 :     406896 :     M = FpX_add(gel(S,i+2), FpX_add(A, Bc, q), q);
     144         [ -  + ]:     406896 :     if (low_stack(lim, stack_lim(av2,1)))
     145                 :            :     {
     146         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 1, i = %ld", i);
     147                 :          0 :       M = gerepileupto(av2, M);
     148                 :            :     }
     149                 :            :   }
     150         [ +  + ]:       2898 :   if (degpol(M)<dT-1)
     151                 :       1449 :     return gerepileupto(av, M);
     152                 :       1449 :   R = RgX_shift_shallow(M,dT-degpol(M)-2);
     153                 :       1449 :   av2 = avma; lim = stack_lim(av2, 1);
     154         [ +  + ]:      55937 :   for(i = degpol(M)-dT+2; i>=1; i--)
     155                 :            :   {
     156                 :            :     GEN B, c;
     157                 :      54488 :     R = RgX_shift_shallow(R, 1);
     158                 :      54488 :     gel(R,2) = gel(M, i+1);
     159         [ +  + ]:      54488 :     if (degpol(R) < dT) continue;
     160                 :      33019 :     B = FpX_add(FpX_mulu(T, 2*i, q), Tp1, q);
     161                 :      33019 :     c = frac_to_Fp(leading_term(R), leading_term(B), q);
     162                 :      33019 :     R = FpX_sub(R, FpX_Fp_mul(B, c, q), q);
     163         [ -  + ]:      33019 :     if (low_stack(lim, stack_lim(av2,1)))
     164                 :            :     {
     165         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 2, i = %ld", i);
     166                 :          0 :       R = gerepileupto(av2, R);
     167                 :            :     }
     168                 :            :   }
     169         [ +  + ]:       1449 :   if (degpol(R)==dT-1)
     170                 :            :   {
     171                 :       1043 :     GEN c = frac_to_Fp(leading_term(R), leading_term(Tp), q);
     172                 :       1043 :     R = FpX_sub(R, FpX_Fp_mul(Tp, c, q), q);
     173                 :       1043 :     return gerepileupto(av, R);
     174                 :            :   } else
     175                 :       2898 :     return gerepilecopy(av, R);
     176                 :            : }
     177                 :            : 
     178                 :            : static GEN
     179                 :       3430 : revdigits(GEN v)
     180                 :            : {
     181                 :       3430 :   long i, n = lg(v)-1;
     182                 :       3430 :   GEN w = cgetg(n+2, t_POL);
     183                 :       3430 :   w[1] = evalsigne(1)|evalvarn(0);
     184         [ +  + ]:      41545 :   for (i=0; i<n; i++)
     185                 :      38115 :     gel(w,i+2) = gel(v,n-i);
     186                 :       3430 :   return FpXX_renormalize(w, n+2);
     187                 :            : }
     188                 :            : 
     189                 :            : static GEN
     190                 :       2898 : diff_red(GEN s, GEN A, long m, GEN T, GEN p)
     191                 :            : {
     192                 :            :   long v, n;
     193                 :            :   GEN Q, sQ, qS;
     194                 :            :   pari_timer ti;
     195         [ -  + ]:       2898 :   if (DEBUGLEVEL>1) timer_start(&ti);
     196                 :       2898 :   Q = revdigits(FpX_digits(A,T,p));
     197                 :       2898 :   n = degpol(Q);
     198         [ -  + ]:       2898 :   if (DEBUGLEVEL>1) timer_printf(&ti,"reddigits");
     199                 :       2898 :   sQ = FpXXQ_mul(s,Q,T,p);
     200         [ -  + ]:       2898 :   if (DEBUGLEVEL>1) timer_printf(&ti,"redmul");
     201                 :       2898 :   qS = RgX_shift_shallow(sQ,m-n);
     202                 :       2898 :   v = ZX_val(sQ);
     203         [ +  + ]:       2898 :   if (n > m + v)
     204                 :            :   {
     205                 :       1428 :     long i, l = n-m-v;
     206                 :       1428 :     GEN rS = cgetg(l+1,t_VEC);
     207         [ +  + ]:       7378 :     for (i = l-1; i >=0 ; i--)
     208                 :       5950 :       gel(rS,i+1) = gel(sQ, 1+v+l-i);
     209                 :       1428 :     rS = FpX_fromdigits(rS,T,p);
     210                 :       1428 :     gel(qS,2) = FpX_add(FpX_mul(rS, T, p), gel(qS, 2), p);
     211         [ -  + ]:       1428 :     if (DEBUGLEVEL>1) timer_printf(&ti,"redadd");
     212                 :            :   }
     213                 :       2898 :   return qS;
     214                 :            : }
     215                 :            : 
     216                 :            : static GEN
     217                 :       2898 : topad(GEN P, long g, GEN q)
     218                 :            : {
     219                 :       2898 :   long i, d = lgpol(P);
     220                 :       2898 :   GEN V = cgetg(g+1,t_COL);
     221         [ +  + ]:      28196 :   for(i = 1; i <= d; i++)
     222                 :      25298 :     gel(V, i) = gadd(gel(P, i+1), q);
     223         [ +  + ]:       2996 :   for(     ; i <= g; i++)
     224                 :         98 :     gel(V, i) = gcopy(q);
     225                 :       2898 :   return V;
     226                 :            : }
     227                 :            : 
     228                 :            : GEN
     229                 :        469 : hyperellpadicfrobenius(GEN H, ulong p, long n)
     230                 :            : {
     231                 :        469 :   pari_sp av = avma;
     232                 :            :   long N, i, d, g;
     233                 :            :   GEN F, s, q, Q, pN1, U, V;
     234                 :            :   pari_timer ti;
     235         [ -  + ]:        469 :   if (typ(H) != t_POL) pari_err_TYPE("hyperellpadicfrobenius",H);
     236         [ -  + ]:        469 :   if (p == 2) is_sing(H, 2);
     237                 :        469 :   d = degpol(H); g = ((d-1)>>1)*2;
     238 [ +  - ][ -  + ]:        469 :   if (d < 0 || !odd(d))
     239                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","H","degree % 2 = ", gen_0, H);
     240         [ -  + ]:        469 :   if (p < (ulong) d)
     241                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","p","<", utoi(d), utoi(p));
     242         [ -  + ]:        469 :   if (n < 1)
     243                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","n","<", gen_1, utoi(n));
     244                 :        469 :   N = n + logint0(stoi(2*n), stoi(p), NULL);
     245                 :        469 :   q = zeropadic(utoi(p),n); pN1 = powuu(p,N+1);
     246                 :        469 :   Q = RgX_to_FpX(H, pN1);
     247         [ -  + ]:        469 :   if (dvdiu(leading_term(Q),p)) is_sing(H, p);
     248                 :        469 :   setvarn(Q,1);
     249         [ -  + ]:        469 :   if (DEBUGLEVEL>1) timer_start(&ti);
     250                 :        469 :   s = revdigits(FpX_digits(RgX_inflate(Q, p), Q, pN1));
     251         [ -  + ]:        469 :   if (DEBUGLEVEL>1) timer_printf(&ti,"s1");
     252                 :        469 :   s = ZpXXQ_invsqrt(s, Q, p, N);
     253         [ -  + ]:        469 :   if (DEBUGLEVEL>1) timer_printf(&ti,"invsqrt");
     254                 :        469 :   get_UV(&U, &V, Q, p, N+1);
     255                 :        469 :   F = cgetg(1+g, t_MAT);
     256         [ +  + ]:       3367 :   for (i = 1; i <= g; i++)
     257                 :            :   {
     258                 :       2898 :     pari_sp av2 = avma;
     259                 :            :     GEN M, D;
     260                 :       2898 :     D = diff_red(s, monomial(utoi(p),p*i-1,1),p>>1, Q, pN1);
     261         [ -  + ]:       2898 :     if (DEBUGLEVEL>1) timer_printf(&ti,"red");
     262                 :       2898 :     M = ZpXXQ_frob(D, U, V, Q, p, N + 1);
     263         [ -  + ]:       2898 :     if (DEBUGLEVEL>1) timer_printf(&ti,"frob");
     264                 :       2898 :     gel(F, i) = gerepilecopy(av2, topad(M, g, q));
     265                 :            :   }
     266                 :        469 :   return gerepileupto(av, F);
     267                 :            : }
     268                 :            : 
     269                 :            : INLINE GEN
     270                 :        210 : FpXXX_renormalize(GEN x, long lx)  { return ZXX_renormalize(x,lx); }
     271                 :            : 
     272                 :            : static GEN
     273                 :        168 : FpXQXXQ_red(GEN F, GEN S, GEN T, GEN p)
     274                 :            : {
     275                 :        168 :   pari_sp av = avma;
     276                 :        168 :   long dF = degpol(F);
     277                 :        168 :   GEN A = cgetg(dF+3, t_POL);
     278                 :        168 :   GEN C = pol_0(varn(S));
     279                 :            :   long i;
     280         [ +  + ]:       6748 :   for(i=dF; i>0; i--)
     281                 :            :   {
     282                 :       6580 :     GEN Fi = FpXX_add(C, gel(F,i+2), p);
     283                 :       6580 :     GEN R, Q = FpXQX_divrem(Fi, S, T, p, &R);
     284                 :       6580 :     gel(A,i+2) = R;
     285                 :       6580 :     C = Q;
     286                 :            :   }
     287                 :        168 :   gel(A,2) = FpXX_add(C, gel(F,2), p);
     288                 :        168 :   A[1] = F[1];
     289                 :        168 :   return gerepilecopy(av, FpXXX_renormalize(A,dF+3));
     290                 :            : }
     291                 :            : 
     292                 :            : static GEN
     293                 :         42 : FpXQXXQ_sqr(GEN x, GEN S, GEN T, GEN p)
     294                 :            : {
     295                 :         42 :   pari_sp av = avma;
     296                 :            :   GEN z, kx;
     297                 :         42 :   long n = degpol(S);
     298                 :         42 :   kx = ZXX_to_Kronecker(x, n);
     299                 :         42 :   z = Kronecker_to_ZXX(FpXQX_sqr(kx, T, p), n, varn(S));
     300                 :         42 :   return gerepileupto(av, FpXQXXQ_red(z, S, T, p));
     301                 :            : }
     302                 :            : 
     303                 :            : static GEN
     304                 :        126 : FpXQXXQ_mul(GEN x, GEN y, GEN S, GEN T, GEN p)
     305                 :            : {
     306                 :        126 :   pari_sp av = avma;
     307                 :            :   GEN z, kx, ky;
     308                 :        126 :   long n = degpol(S);
     309                 :        126 :   kx = ZXX_to_Kronecker(x, n);
     310                 :        126 :   ky = ZXX_to_Kronecker(y, n);
     311                 :        126 :   z = Kronecker_to_ZXX(FpXQX_mul(ky, kx, T, p), n, varn(S));
     312                 :        126 :   return gerepileupto(av, FpXQXXQ_red(z, S, T, p));
     313                 :            : }
     314                 :            : 
     315                 :            : static GEN
     316                 :         42 : FpXXX_red(GEN z, GEN p)
     317                 :            : {
     318                 :            :   GEN res;
     319                 :         42 :   long i, l = lg(z);
     320                 :         42 :   res = cgetg(l,t_POL); res[1] = z[1];
     321         [ +  + ]:       1743 :   for (i=2; i<l; i++)
     322                 :            :   {
     323                 :       1701 :     GEN zi = gel(z,i);
     324         [ -  + ]:       1701 :     if (typ(zi)==t_INT)
     325                 :          0 :       gel(res,i) = modii(zi,p);
     326                 :            :     else
     327                 :       1701 :      gel(res,i) = FpXX_red(zi,p);
     328                 :            :   }
     329                 :         42 :   return FpXXX_renormalize(res,lg(res));
     330                 :            : }
     331                 :            : 
     332                 :            : static GEN
     333                 :         42 : FpXXX_Fp_mul(GEN z, GEN a, GEN p)
     334                 :            : {
     335                 :         42 :   return FpXXX_red(RgX_Rg_mul(z, a), p);
     336                 :            : }
     337                 :            : 
     338                 :            : static GEN
     339                 :         21 : ZpXQXXQ_invsqrt(GEN F, GEN S, GEN T, ulong p, long e)
     340                 :            : {
     341                 :         21 :   pari_sp av = avma, av2, lim;
     342                 :            :   ulong mask;
     343                 :         21 :   long v = varn(F), n=1;
     344                 :            :   pari_timer ti;
     345                 :         21 :   GEN a = pol_1(v);
     346         [ -  + ]:         21 :   if (DEBUGLEVEL>1) timer_start(&ti);
     347         [ -  + ]:         21 :   if (e <= 1) return gerepilecopy(av, a);
     348                 :         21 :   mask = quadratic_prec_mask(e);
     349                 :         21 :   av2 = avma; lim = stack_lim(av2, 1);
     350         [ +  + ]:         63 :   for (;mask>1;)
     351                 :            :   {
     352                 :            :     GEN q, q2, q22, f, fq, afq;
     353                 :         42 :     long n2 = n;
     354         [ +  + ]:         42 :     n<<=1; if (mask & 1) n--;
     355                 :         42 :     mask >>= 1;
     356                 :         42 :     q = powuu(p,n), q2 = powuu(p,n2);
     357                 :         42 :     f = RgX_sub(FpXQXXQ_mul(F, FpXQXXQ_sqr(a, S, T, q), S, T, q), pol_1(v));
     358                 :         42 :     fq = RgX_Rg_divexact(f, q2);
     359                 :         42 :     q22 = shifti(addis(q2,1),-1);
     360                 :         42 :     afq = FpXXX_Fp_mul(FpXQXXQ_mul(a, fq, S, T, q2), q22, q2);
     361                 :         42 :     a = RgX_sub(a, RgX_Rg_mul(afq, q2));
     362         [ -  + ]:         42 :     if (low_stack(lim, stack_lim(av2,1)))
     363                 :            :     {
     364         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXQXXQ_invsqrt, e = %ld", n);
     365                 :          0 :       a = gerepileupto(av2, a);
     366                 :            :     }
     367                 :            :   }
     368                 :         21 :   return gerepileupto(av, a);
     369                 :            : }
     370                 :            : 
     371                 :            : static GEN
     372                 :        105 : frac_to_Fq(GEN a, GEN b, GEN T, GEN p)
     373                 :            : {
     374                 :        105 :   GEN d = gcdii(ZX_content(a), ZX_content(b));
     375                 :        105 :   return FpXQ_div(ZX_Z_divexact(a, d), ZX_Z_divexact(b, d), T, p);
     376                 :            : }
     377                 :            : 
     378                 :            : static GEN
     379                 :         42 : ZpXQXXQ_frob(GEN F, GEN U, GEN V, GEN S, GEN T, ulong p, long e)
     380                 :            : {
     381                 :         42 :   pari_sp av = avma, av2, lim;
     382                 :         42 :   long i, pr = degpol(F), dS = degpol(S), v = varn(T);
     383                 :         42 :   GEN q = powuu(p,e);
     384                 :         42 :   GEN Sp = RgX_deriv(S), Sp1 = RgX_shift_shallow(Sp, 1);
     385                 :         42 :   GEN M = gel(F,pr+2), R;
     386                 :         42 :   av2 = avma; lim = stack_lim(av2, 1);
     387         [ +  + ]:       2072 :   for(i = pr-1; i>=0; i--)
     388                 :            :   {
     389                 :            :     GEN A, B, H, Bc;
     390                 :            :     ulong v, r;
     391                 :       2030 :     H = FpXQX_divrem(FpXQX_mul(V, M, T, q), S, T, q, &B);
     392                 :       2030 :     A = FpXX_add(FpXQX_mul(U, M, T, q), FpXQX_mul(H, Sp, T, q),q);
     393                 :       2030 :     v = u_lvalrem(2*i+1,p,&r);
     394                 :       2030 :     Bc = RgX_deriv(B);
     395                 :       2030 :     Bc = FpXX_Fp_mul(ZXX_Z_divexact(Bc,powuu(p,v)), Fp_div(gen_2, utoi(r), q), q);
     396                 :       2030 :     M = FpXX_add(gel(F,i+2), FpXX_add(A, Bc, q), q);
     397         [ -  + ]:       2030 :     if (low_stack(lim, stack_lim(av2,1)))
     398                 :            :     {
     399         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXQXXQ_frob, step 1, i = %ld", i);
     400                 :          0 :       M = gerepileupto(av2, M);
     401                 :            :     }
     402                 :            :   }
     403         [ +  + ]:         42 :   if (degpol(M)<dS-1)
     404                 :         21 :     return gerepileupto(av, M);
     405                 :         21 :   R = RgX_shift_shallow(M,dS-degpol(M)-2);
     406                 :         21 :   av2 = avma; lim = stack_lim(av2, 1);
     407         [ +  + ]:        147 :   for(i = degpol(M)-dS+2; i>=1; i--)
     408                 :            :   {
     409                 :            :     GEN B, c;
     410                 :        126 :     R = RgX_shift_shallow(R, 1);
     411                 :        126 :     gel(R,2) = gel(M, i+1);
     412         [ +  + ]:        126 :     if (degpol(R) < dS) continue;
     413                 :         84 :     B = FpXX_add(FpXX_mulu(S, 2*i, q), Sp1, q);
     414                 :         84 :     c = frac_to_Fq(to_ZX(leading_term(R),v), to_ZX(leading_term(B),v), T, q);
     415                 :         84 :     R = FpXX_sub(R, FpXQX_FpXQ_mul(B, c, T, q), q);
     416         [ -  + ]:         84 :     if (low_stack(lim, stack_lim(av2,1)))
     417                 :            :     {
     418         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZpXXQ_frob, step 2, i = %ld", i);
     419                 :          0 :       R = gerepileupto(av2, R);
     420                 :            :     }
     421                 :            :   }
     422         [ +  - ]:         21 :   if (degpol(R)==dS-1)
     423                 :            :   {
     424                 :         21 :     GEN c = frac_to_Fq(to_ZX(leading_term(R),v), to_ZX(leading_term(Sp),v), T, q);
     425                 :         21 :     R = FpXX_sub(R, FpXQX_FpXQ_mul(Sp, c, T, q), q);
     426                 :         21 :     return gerepileupto(av, R);
     427                 :            :   } else
     428                 :         42 :     return gerepilecopy(av, R);
     429                 :            : }
     430                 :            : 
     431                 :            : 
     432                 :            : static GEN
     433                 :         42 : Fq_diff_red(GEN s, GEN A, long m, GEN S, GEN T, GEN p)
     434                 :            : {
     435                 :            :   long v, n;
     436                 :            :   GEN Q, sQ, qS;
     437                 :            :   pari_timer ti;
     438         [ -  + ]:         42 :   if (DEBUGLEVEL>1) timer_start(&ti);
     439                 :         42 :   Q = revdigits(FpXQX_digits(A, S, T, p));
     440                 :         42 :   n = degpol(Q);
     441         [ -  + ]:         42 :   if (DEBUGLEVEL>1) timer_printf(&ti,"reddigits");
     442                 :         42 :   sQ = FpXQXXQ_mul(s,Q,S,T,p);
     443         [ -  + ]:         42 :   if (DEBUGLEVEL>1) timer_printf(&ti,"redmul");
     444                 :         42 :   qS = RgX_shift_shallow(sQ,m-n);
     445                 :         42 :   v = ZX_val(sQ);
     446         [ +  + ]:         42 :   if (n > m + v)
     447                 :            :   {
     448                 :         21 :     long i, l = n-m-v;
     449                 :         21 :     GEN rS = cgetg(l+1,t_VEC);
     450         [ +  + ]:         70 :     for (i = l-1; i >=0 ; i--)
     451                 :         49 :       gel(rS,i+1) = gel(sQ, 1+v+l-i);
     452                 :         21 :     rS = FpXQX_fromdigits(rS,S,T,p);
     453                 :         21 :     gel(qS,2) = FpXX_add(FpXQX_mul(rS, S, T, p), gel(qS, 2), p);
     454         [ -  + ]:         21 :     if (DEBUGLEVEL>1) timer_printf(&ti,"redadd");
     455                 :            :   }
     456                 :         42 :   return qS;
     457                 :            : }
     458                 :            : 
     459                 :            : static void
     460                 :         21 : Fq_get_UV(GEN *U, GEN *V, GEN S, GEN T, ulong p, long e)
     461                 :            : {
     462                 :         21 :   GEN q = powuu(p, e), d;
     463                 :         21 :   GEN dS = RgX_deriv(S);
     464                 :         21 :   GEN R  = polresultantext(S, dS), C;
     465                 :         21 :   long v = varn(S);
     466         [ -  + ]:         21 :   if (signe(FpX_red(to_ZX(gel(R,3),v),utoi(p)))==0) is_sing(S, p);
     467                 :         21 :   C = FpXQ_red(gel(R, 3), T, q);
     468                 :         21 :   d = ZpXQ_inv(C, T, utoi(p), e);
     469                 :         21 :   *U = FpXQX_FpXQ_mul(FpXQX_red(to_ZX(gel(R,1),v),T,q),d,T,q);
     470                 :         21 :   *V = FpXQX_FpXQ_mul(FpXQX_red(to_ZX(gel(R,2),v),T,q),d,T,q);
     471                 :         21 : }
     472                 :            : 
     473                 :            : static GEN
     474                 :         42 : ZXX_to_FpXC(GEN x, long N, GEN p, long v)
     475                 :            : {
     476                 :            :   long i, l;
     477                 :            :   GEN z;
     478                 :         42 :   l = lg(x)-1; x++;
     479         [ -  + ]:         42 :   if (l > N+1) l = N+1; /* truncate higher degree terms */
     480                 :         42 :   z = cgetg(N+1,t_COL);
     481         [ +  + ]:        126 :   for (i=1; i<l ; i++)
     482                 :            :   {
     483                 :         84 :     GEN xi = gel(x, i);
     484         [ -  + ]:         84 :     gel(z,i) = typ(xi)==t_INT? scalarpol(Fp_red(xi, p), v): FpX_red(xi, p);
     485                 :            :   }
     486         [ -  + ]:         42 :   for (   ; i<l ; i++)
     487                 :          0 :     gel(z,i) = pol_0(v);
     488                 :         42 :   return z;
     489                 :            : }
     490                 :            : 
     491                 :            : GEN
     492                 :         21 : ZlXQX_hyperellpadicfrobenius(GEN H, GEN T, ulong p, long n)
     493                 :            : {
     494                 :         21 :   pari_sp av = avma;
     495                 :            :   long N, i, d, g;
     496                 :            :   GEN xp, F, s, q, Q, pN1, U, V;
     497                 :            :   pari_timer ti;
     498         [ -  + ]:         21 :   if (typ(H) != t_POL) pari_err_TYPE("hyperellpadicfrobenius",H);
     499         [ -  + ]:         21 :   if (p == 2) is_sing(H, 2);
     500                 :         21 :   d = degpol(H); g = ((d-1)>>1)*2;
     501 [ +  - ][ -  + ]:         21 :   if (d < 0 || !odd(d))
     502                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","H","degree % 2 = ", gen_0, H);
     503         [ -  + ]:         21 :   if (p < (ulong) d)
     504                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","p","<", utoi(d), utoi(p));
     505         [ -  + ]:         21 :   if (n < 1)
     506                 :          0 :     pari_err_DOMAIN("hyperellpadicfrobenius","n","<", gen_1, utoi(n));
     507                 :         21 :   N = n + logint0(stoi(2*n), stoi(p), NULL);
     508                 :         21 :   q = powuu(p,n); pN1 = powuu(p,N+1); T = FpX_get_red(T, pN1);
     509                 :         21 :   Q = RgX_to_FqX(H, T, pN1);
     510         [ -  + ]:         21 :   if (signe(FpX_red(to_ZX(leading_term(Q),varn(Q)),utoi(p)))==0) is_sing(H, p);
     511         [ -  + ]:         21 :   if (DEBUGLEVEL>1) timer_start(&ti);
     512                 :         21 :   xp = ZpX_Frobenius(T, utoi(p), N+1);
     513                 :         21 :   s = RgX_inflate(FpXY_FpXQ_evalx(Q, xp, T, pN1), p);
     514                 :         21 :   s = revdigits(FpXQX_digits(s, Q, T, pN1));
     515         [ -  + ]:         21 :   if (DEBUGLEVEL>1) timer_printf(&ti,"s1");
     516                 :         21 :   s = ZpXQXXQ_invsqrt(s, Q, T, p, N);
     517         [ -  + ]:         21 :   if (DEBUGLEVEL>1) timer_printf(&ti,"invsqrt");
     518                 :         21 :   Fq_get_UV(&U, &V, Q, T, p, N+1);
     519         [ -  + ]:         21 :   if (DEBUGLEVEL>1) timer_printf(&ti,"get_UV");
     520                 :         21 :   F = cgetg(1+g, t_MAT);
     521         [ +  + ]:         63 :   for (i = 1; i <= g; i++)
     522                 :            :   {
     523                 :         42 :     pari_sp av2 = avma;
     524                 :            :     GEN M, D;
     525                 :         42 :     D = Fq_diff_red(s, monomial(utoi(p),p*i-1,1),p>>1, Q, T, pN1);
     526         [ -  + ]:         42 :     if (DEBUGLEVEL>1) timer_printf(&ti,"red");
     527                 :         42 :     M = ZpXQXXQ_frob(D, U, V, Q, T, p, N + 1);
     528         [ -  + ]:         42 :     if (DEBUGLEVEL>1) timer_printf(&ti,"frob");
     529                 :         42 :     gel(F, i) = gerepileupto(av2, ZXX_to_FpXC(M, g, q, varn(T)));
     530                 :            :   }
     531                 :         21 :   return gerepileupto(av, F);
     532                 :            : }

Generated by: LCOV version 1.9