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 - lll.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 16741-1378b1c) Lines: 446 486 91.8 %
Date: 2014-08-17 Functions: 30 31 96.8 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 312 390 80.0 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2008  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                 :            : /* default quality ratio for LLL */
      18                 :            : static const double LLLDFT = 0.99;
      19                 :            : 
      20                 :            : /* assume flag & (LLL_KER|LLL_IM|LLL_ALL). LLL_INPLACE implies LLL_IM */
      21                 :            : static GEN
      22                 :       1740 : lll_trivial(GEN x, long flag)
      23                 :            : {
      24                 :            :   GEN y;
      25         [ +  + ]:       1740 :   if (lg(x) == 1)
      26                 :            :   { /* dim x = 0 */
      27         [ +  + ]:        215 :     if (! (flag & LLL_ALL)) return cgetg(1,t_MAT);
      28                 :         20 :     y=cgetg(3,t_VEC);
      29                 :         20 :     gel(y,1) = cgetg(1,t_MAT);
      30                 :         20 :     gel(y,2) = cgetg(1,t_MAT); return y;
      31                 :            :   }
      32                 :            :   /* dim x = 1 */
      33         [ +  + ]:       1525 :   if (gequal0(gel(x,1)))
      34                 :            :   {
      35         [ -  + ]:         45 :     if (flag & LLL_KER) return matid(1);
      36         [ +  + ]:         45 :     if (flag & (LLL_IM|LLL_INPLACE)) return cgetg(1,t_MAT);
      37                 :         20 :     y = cgetg(3,t_VEC);
      38                 :         20 :     gel(y,1) = matid(1);
      39                 :         20 :     gel(y,2) = cgetg(1,t_MAT); return y;
      40                 :            :   }
      41         [ +  + ]:       1480 :   if (flag & LLL_INPLACE) return gcopy(x);
      42         [ -  + ]:       1270 :   if (flag & LLL_KER) return cgetg(1,t_MAT);
      43         [ +  + ]:       1270 :   if (flag & LLL_IM)  return matid(1);
      44                 :         20 :   y=cgetg(3,t_VEC);
      45                 :         20 :   gel(y,1) = cgetg(1,t_MAT);
      46         [ +  + ]:         20 :   gel(y,2) = (flag & LLL_GRAM)? gcopy(x): matid(1);
      47                 :       1740 :   return y;
      48                 :            : }
      49                 :            : 
      50                 :            : /* vecslice(h,#h-k,#h) in place. Works for t_MAT, t_VEC/t_COL */
      51                 :            : static GEN
      52                 :     672062 : lll_get_im(GEN h, long k)
      53                 :            : {
      54                 :     672062 :   ulong mask = h[0] & ~LGBITS;
      55                 :     672062 :   long l = lg(h) - k;
      56                 :     672062 :   h += k; h[0] = mask | evallg(l);
      57                 :     672062 :   return h;
      58                 :            : }
      59                 :            : 
      60                 :            : /* k = dim Kernel */
      61                 :            : static GEN
      62                 :     672092 : lll_finish(GEN h, long k, long flag)
      63                 :            : {
      64                 :            :   GEN g;
      65         [ +  + ]:     672092 :   if (flag & LLL_KER) { setlg(h,k+1); return h; }
      66         [ +  + ]:     672062 :   if (flag & LLL_IM) return lll_get_im(h, k);
      67                 :         60 :   g = vecslice(h,1,k);
      68                 :     672092 :   return mkvec2(g, lll_get_im(h, k));
      69                 :            : }
      70                 :            : 
      71                 :            : /********************************************************************/
      72                 :            : /**                                                                **/
      73                 :            : /**                   FPLLL (adapted from D. Stehle's code)        **/
      74                 :            : /**                                                                **/
      75                 :            : /********************************************************************/
      76                 :            : /* Babai() and fplll() are a conversion to libpari API and data types
      77                 :            :    of the file proved.c in fplll-1.3 by Damien Stehle'.
      78                 :            : 
      79                 :            :   Copyright 2005, 2006 Damien Stehle'.
      80                 :            : 
      81                 :            :   This program is free software; you can redistribute it and/or modify it
      82                 :            :   under the terms of the GNU General Public License as published by the
      83                 :            :   Free Software Foundation; either version 2 of the License, or (at your
      84                 :            :   option) any later version.
      85                 :            : 
      86                 :            :   This program implements ideas from the paper "Floating-point LLL Revisited",
      87                 :            :   by Phong Nguyen and Damien Stehle', in the Proceedings of Eurocrypt'2005,
      88                 :            :   Springer-Verlag; and was partly inspired by Shoup's NTL library:
      89                 :            :   http://www.shoup.net/ntl/
      90                 :            : */
      91                 :            : 
      92                 :            : /***********************************************/
      93                 :            : /* Babai's Nearest Plane algorithm (iterative) */
      94                 :            : /***********************************************/
      95                 :            : /* Size-reduces b_kappa using mu_{i,j} and r_{i,j} for j<=i <kappa
      96                 :            : Updates B (kappa); computes mu_{kappa,j}, r_{kappa,j} for j<=kappa, and s(kappa)
      97                 :            : mu, r, s updated in place (affrr).
      98                 :            : */
      99                 :            : static long
     100                 :   11242754 : Babai(pari_sp av, long kappa, GEN *pG, GEN *pB, GEN *pU, GEN mu, GEN r, GEN s,
     101                 :            :       long a, long zeros, long maxG, long n, GEN eta, GEN halfplus1, long prec)
     102                 :            : {
     103                 :   11242754 :   const pari_sp lim = stack_lim(av,2);
     104                 :   11242754 :   GEN B = *pB, G = *pG, U = *pU, tmp, rtmp, ztmp;
     105         [ +  + ]:   11242754 :   long k, aa = (a > zeros)? a : zeros+1;
     106                 :   11242754 :   GEN maxmu = gen_0, max2mu = gen_0;
     107                 :            :   /* N.B: we set d = 0 (resp. n = 0) to avoid updating U (resp. B) */
     108         [ +  + ]:   11242754 :   const long d = U ? lg(U)-1: 0;
     109                 :            : 
     110                 :            :   for (;;) {
     111                 :   17150754 :     int go_on = 0;
     112                 :            :     GEN max3mu;
     113                 :            :     long i, j;
     114                 :            : 
     115         [ +  + ]:   17150754 :     if (low_stack(lim, stack_lim(av,2)))
     116                 :            :     {
     117         [ -  + ]:        538 :       if(DEBUGMEM>1) pari_warn(warnmem,"Babai[1], a=%ld", aa);
     118         [ +  + ]:        538 :       gerepileall(av,U?5:4,&B,&G,&maxmu,&max2mu,&U);
     119                 :            :     }
     120                 :            :     /* Step2: compute the GSO for stage kappa */
     121                 :   17150754 :     max3mu = max2mu;
     122                 :   17150754 :     max2mu = maxmu;
     123                 :   17150754 :     maxmu = real_0(prec);
     124         [ +  + ]:   94846844 :     for (j=aa; j<kappa; j++)
     125                 :            :     {
     126                 :   77696090 :       pari_sp btop = avma;
     127                 :   77696090 :       k = zeros+1;
     128         [ +  + ]:   77696090 :       if (j > k)
     129                 :            :       {
     130                 :   66390844 :         tmp  = mulrr(gmael(mu,j,k), gmael(r,kappa,k));
     131                 :   66390844 :         rtmp = subir(gmael(G,kappa,j), tmp);
     132         [ +  + ]:  715419613 :         for (k++; k<j; k++)
     133                 :            :         {
     134                 :  649028769 :           tmp  = mulrr(gmael(mu,j,k), gmael(r,kappa,k));
     135                 :  649028769 :           rtmp = subrr(rtmp,tmp);
     136                 :            :         }
     137                 :   66390844 :         affrr(rtmp, gmael(r,kappa,j));
     138                 :            :       }
     139                 :            :       else
     140                 :   11305246 :         affir(gmael(G,kappa,j), gmael(r,kappa,j));
     141                 :   77696090 :       affrr(divrr(gmael(r,kappa,j), gmael(r,j,j)), gmael(mu,kappa,j));
     142         [ +  + ]:   77696090 :       if (absr_cmp(maxmu, gmael(mu,kappa,j))<0)
     143                 :   29121157 :         maxmu = gmael(mu,kappa,j);
     144                 :   77696090 :       avma = btop;
     145                 :            :     }
     146                 :   17150754 :     maxmu = absr(maxmu);
     147 [ +  + ][ -  + ]:   17150754 :     if (typ(max3mu)==t_REAL && absr_cmp(max3mu, shiftr(max2mu, 5))<=0)
     148                 :            :     {
     149                 :          0 :       *pB = B; *pG = G; *pU = U;
     150         [ #  # ]:          0 :       if (DEBUGLEVEL>5) err_printf("prec too low\n");
     151                 :          0 :       return kappa;
     152                 :            :     }
     153                 :            : 
     154                 :            :     /* Step3--5: compute the X_j's  */
     155         [ +  + ]:  146929246 :     for (j=kappa-1; j>zeros; j--)
     156                 :            :     {
     157                 :  129778492 :       tmp = gmael(mu,kappa,j);
     158         [ +  + ]:  129778492 :       if (absr_cmp(tmp, eta) <= 0) continue; /* (essentially) size-reduced */
     159                 :            : 
     160         [ +  + ]:   21209858 :       if (low_stack(lim, stack_lim(av,2)))
     161                 :            :       {
     162         [ -  + ]:       3947 :         if(DEBUGMEM>1) pari_warn(warnmem,"Babai[2], a=%ld, j=%ld", aa,j);
     163         [ +  + ]:       3947 :         gerepileall(av,U?5:4,&B,&G,&maxmu,&max2mu,&U);
     164                 :            :       }
     165                 :   21209858 :       go_on = 1;
     166                 :            :       /* we consider separately the case |X| = 1 */
     167         [ +  + ]:   21209858 :       if (absr_cmp(tmp, halfplus1) <= 0)
     168                 :            :       {
     169         [ +  + ]:   15301882 :         if (signe(tmp) > 0) { /* in this case, X = 1 */
     170                 :    7836980 :           pari_sp btop = avma;
     171         [ +  + ]:   77949078 :           for (k=zeros+1; k<j; k++)
     172                 :   70112098 :             affrr(subrr(gmael(mu,kappa,k), gmael(mu,j,k)), gmael(mu,kappa,k));
     173                 :    7836980 :           avma = btop;
     174                 :            : 
     175         [ +  + ]:  256238779 :           for (i=1; i<=n; i++)
     176                 :  248401799 :             gmael(B,kappa,i) = subii(gmael(B,kappa,i), gmael(B,j,i));
     177         [ +  + ]:   63349545 :           for (i=1; i<=d; i++)
     178                 :   55512565 :             gmael(U,kappa,i) = subii(gmael(U,kappa,i), gmael(U,j,i));
     179                 :    7836980 :           btop = avma;
     180                 :    7836980 :           ztmp = subii(gmael(G,j,j), shifti(gmael(G,kappa,j), 1));
     181                 :    7836980 :           ztmp = addii(gmael(G,kappa,kappa), ztmp);
     182                 :    7836980 :           gmael(G,kappa,kappa) = gerepileuptoint(btop, ztmp);
     183         [ +  + ]:   85916578 :           for (i=1; i<=j; i++)
     184                 :   78079598 :             gmael(G,kappa,i) = subii(gmael(G,kappa,i), gmael(G,j,i));
     185         [ +  + ]:   80488125 :           for (i=j+1; i<kappa; i++)
     186                 :   72651145 :             gmael(G,kappa,i) = subii(gmael(G,kappa,i), gmael(G,i,j));
     187         [ +  + ]:   67273013 :           for (i=kappa+1; i<=maxG; i++)
     188                 :   59436033 :             gmael(G,i,kappa) = subii(gmael(G,i,kappa), gmael(G,i,j));
     189                 :            :         } else { /* otherwise X = -1 */
     190                 :    7464902 :           pari_sp btop = avma;
     191         [ +  + ]:   77446458 :           for (k=zeros+1; k<j; k++)
     192                 :   69981556 :             affrr(addrr(gmael(mu,kappa,k), gmael(mu,j,k)), gmael(mu,kappa,k));
     193                 :    7464902 :           avma = btop;
     194                 :            : 
     195         [ +  + ]:  254776161 :           for (i=1; i<=n; i++)
     196                 :  247311259 :             gmael(B,kappa,i) = addii(gmael(B,kappa,i), gmael(B,j,i));
     197         [ +  + ]:   61752743 :           for (i=1; i<=d; i++)
     198                 :   54287841 :             gmael(U,kappa,i) = addii(gmael(U,kappa,i),gmael(U,j,i));
     199                 :    7464902 :           btop = avma;
     200                 :    7464902 :           ztmp = addii(gmael(G,j,j), shifti(gmael(G,kappa,j), 1));
     201                 :    7464902 :           ztmp = addii(gmael(G,kappa,kappa), ztmp);
     202                 :    7464902 :           gmael(G,kappa,kappa) = gerepileuptoint(btop, ztmp);
     203         [ +  + ]:   84987720 :           for (i=1; i<=j; i++)
     204                 :   77522818 :             gmael(G,kappa,i) = addii(gmael(G,kappa,i), gmael(G,j,i));
     205         [ +  + ]:   79959449 :           for (i=j+1; i<kappa; i++)
     206                 :   72494547 :             gmael(G,kappa,i) = addii(gmael(G,kappa,i), gmael(G,i,j));
     207         [ +  + ]:   66966407 :           for (i=kappa+1; i<=maxG; i++)
     208                 :   59501505 :             gmael(G,i,kappa) = addii(gmael(G,i,kappa), gmael(G,i,j));
     209                 :            :         }
     210                 :   15301882 :         continue;
     211                 :            :       }
     212                 :            :       /* we have |X| >= 2 */
     213                 :    5907976 :       ztmp = roundr_safe(tmp);
     214         [ +  + ]:    5907976 :       if (lgefint(ztmp) == 3)
     215                 :            :       {
     216                 :    5456782 :         pari_sp btop = avma;
     217                 :    5456782 :         ulong xx = ztmp[2]; /* X fits in an ulong */
     218         [ +  + ]:    5456782 :         if (signe(ztmp) > 0) /* = xx */
     219                 :            :         {
     220         [ +  + ]:   17509495 :           for (k=zeros+1; k<j; k++)
     221                 :            :           {
     222                 :   14773387 :             rtmp = subrr(gmael(mu,kappa,k), mulur(xx, gmael(mu,j,k)));
     223                 :   14773387 :             affrr(rtmp, gmael(mu,kappa,k));
     224                 :            :           }
     225                 :    2736108 :           avma = btop;
     226         [ +  + ]:   86892382 :           for (i=1; i<=n; i++)
     227                 :   84156274 :             gmael(B,kappa,i) = submuliu_inplace(gmael(B,kappa,i), gmael(B,j,i), xx);
     228         [ +  + ]:   15950703 :           for (i=1; i<=d; i++)
     229                 :   13214595 :             gmael(U,kappa,i) = submuliu_inplace(gmael(U,kappa,i), gmael(U,j,i), xx);
     230                 :    2736108 :           btop = avma;
     231                 :    2736108 :           ztmp = shifti(muliu(gmael(G,kappa,j), xx), 1);
     232                 :    2736108 :           ztmp = subii(mulii(gmael(G,j,j), sqru(xx)), ztmp);
     233                 :    2736108 :           ztmp = addii(gmael(G,kappa,kappa), ztmp);
     234                 :    2736108 :           gmael(G,kappa,kappa) = gerepileuptoint(btop, ztmp);
     235         [ +  + ]:   20419983 :           for (i=1; i<=j; i++)
     236                 :   17683875 :             gmael(G,kappa,i) = submuliu_inplace(gmael(G,kappa,i), gmael(G,j,i), xx);
     237         [ +  + ]:   41675046 :           for (i=j+1; i<kappa; i++)
     238                 :   38938938 :             gmael(G,kappa,i) = submuliu_inplace(gmael(G,kappa,i), gmael(G,i,j), xx);
     239         [ +  + ]:   16174257 :           for (i=kappa+1; i<=maxG; i++)
     240                 :   13438149 :             gmael(G,i,kappa) = submuliu_inplace(gmael(G,i,kappa), gmael(G,i,j), xx);
     241                 :            :         }
     242                 :            :         else /* = -xx */
     243                 :            :         {
     244         [ +  + ]:   17508449 :           for (k=zeros+1; k<j; k++)
     245                 :            :           {
     246                 :   14787775 :             rtmp = addrr(gmael(mu,kappa,k), mulur(xx, gmael(mu,j,k)));
     247                 :   14787775 :             affrr(rtmp, gmael(mu,kappa,k));
     248                 :            :           }
     249                 :    2720674 :           avma = btop;
     250         [ +  + ]:   87125404 :           for (i=1; i<=n; i++)
     251                 :   84404730 :             gmael(B,kappa,i) = addmuliu_inplace(gmael(B,kappa,i), gmael(B,j,i), xx);
     252         [ +  + ]:   15586266 :           for (i=1; i<=d; i++)
     253                 :   12865592 :             gmael(U,kappa,i) = addmuliu_inplace(gmael(U,kappa,i), gmael(U,j,i), xx);
     254                 :    2720674 :           btop = avma;
     255                 :    2720674 :           ztmp = shifti(muliu(gmael(G,kappa,j), xx), 1);
     256                 :    2720674 :           ztmp = addii(mulii(gmael(G,j,j), sqru(xx)), ztmp);
     257                 :    2720674 :           ztmp = addii(gmael(G,kappa,kappa), ztmp);
     258                 :    2720674 :           gmael(G,kappa,kappa) = gerepileuptoint(btop, ztmp);
     259         [ +  + ]:   20304678 :           for (i=1; i<=j; i++)
     260                 :   17584004 :             gmael(G,kappa,i) = addmuliu_inplace(gmael(G,kappa,i), gmael(G,j,i), xx);
     261         [ +  + ]:   41756374 :           for (i=j+1; i<kappa; i++)
     262                 :   39035700 :             gmael(G,kappa,i) = addmuliu_inplace(gmael(G,kappa,i), gmael(G,i,j), xx);
     263         [ +  + ]:   16026489 :           for (i=kappa+1; i<=maxG; i++)
     264                 :   13305815 :             gmael(G,i,kappa) = addmuliu_inplace(gmael(G,i,kappa), gmael(G,i,j), xx);
     265                 :            :         }
     266                 :            :       }
     267                 :            :       else
     268                 :            :       {
     269                 :     451194 :         GEN tmp2  = itor(ztmp,prec);
     270                 :     451194 :         long e = expo(tmp2)-prec2nbits(prec);
     271                 :     451194 :         GEN X = shifti(trunc2nr(tmp2, -e), e);
     272                 :     451194 :         pari_sp btop = avma;
     273                 :            : 
     274         [ +  + ]:    5850186 :         for (k=zeros+1; k<j; k++)
     275                 :            :         {
     276                 :    5398992 :           rtmp = subrr(gmael(mu,kappa,k), mulir(ztmp, gmael(mu,j,k)));
     277                 :    5398992 :           affrr(rtmp, gmael(mu,kappa,k));
     278                 :            :         }
     279                 :     451194 :         avma = btop;
     280         [ +  + ]:   15780325 :         for (i=1; i<=n; i++)
     281                 :   15329131 :           gmael(B,kappa,i) = submulii(gmael(B,kappa,i), gmael(B,j,i), X);
     282         [ +  + ]:    1115954 :         for (i=1; i<=d; i++)
     283                 :     664760 :           gmael(U,kappa,i) = submulii(gmael(U,kappa,i), gmael(U,j,i), X);
     284                 :     451194 :         btop = avma;
     285                 :     451194 :         ztmp = shifti(mulii(gmael(G,kappa,j), X), 1);
     286                 :     451194 :         ztmp = subii(mulii(gmael(G,j,j), sqri(X)), ztmp);
     287                 :     451194 :         ztmp = addii(gmael(G,kappa,kappa), ztmp);
     288                 :     451194 :         gmael(G,kappa,kappa) = gerepileuptoint(btop, ztmp);
     289         [ +  + ]:    6301380 :         for (i=1; i<=j; i++)
     290                 :    5850186 :           gmael(G,kappa,i) = submulii(gmael(G,kappa,i), gmael(G,j,i), X);
     291         [ +  + ]:    5915132 :         for (   ; i<kappa; i++)
     292                 :    5463938 :           gmael(G,kappa,i) = submulii(gmael(G,kappa,i), gmael(G,i,j), X);
     293         [ +  + ]:     511545 :         for (i=kappa+1; i<=maxG; i++)
     294                 :      60351 :           gmael(G,i,kappa) = submulii(gmael(G,i,kappa), gmael(G,i,j), X);
     295                 :            :       }
     296                 :            :     }
     297         [ +  + ]:   17150754 :     if (!go_on) break; /* Anything happened? */
     298                 :    5908000 :     aa = zeros+1;
     299                 :    5908000 :   }
     300                 :            : 
     301                 :   11242754 :   affir(gmael(G,kappa,kappa), gel(s,zeros+1));
     302                 :            :   /* the last s[kappa-1]=r[kappa][kappa] is computed only if kappa increases */
     303                 :   11242754 :   av = avma;
     304         [ +  + ]:   88414542 :   for (k=zeros+1; k<=kappa-2; k++)
     305                 :            :   {
     306                 :   77171788 :     tmp = subrr(gel(s,k), mulrr(gmael(mu,kappa,k), gmael(r,kappa,k)));
     307                 :   77171788 :     affrr(tmp, gel(s,k+1));
     308                 :            :   }
     309                 :   11242754 :   *pB = B; *pG = G; *pU = U; avma = av;
     310                 :   11242754 :   return 0;
     311                 :            : }
     312                 :            : 
     313                 :            : static void
     314                 :   13869225 : rotate(GEN mu, long kappa2, long kappa, long d)
     315                 :            : {
     316                 :            :   long i, j;
     317                 :   13869225 :   pari_sp av = avma;
     318                 :   13869225 :   GEN mutmp = leafcopy(gel(mu,kappa2));
     319         [ +  + ]:   46553884 :   for (i=kappa2; i>kappa; i--)
     320         [ +  + ]:  660397137 :     for (j=1;j<=d;j++) gmael(mu,i,j) = gmael(mu,i-1,j);
     321         [ +  + ]:  212077058 :   for (j=1;j<=d;j++)   gmael(mu,kappa,j) = gel(mutmp,j);
     322                 :   13869225 :   avma = av;
     323                 :   13869225 : }
     324                 :            : 
     325                 :            : /* ****************** */
     326                 :            : /* The LLL Algorithm  */
     327                 :            : /* ****************** */
     328                 :            : 
     329                 :            : /* LLL-reduces the integer matrix(ces) (G,B,U)? "in place" */
     330                 :            : static GEN
     331                 :     881692 : fplll(GEN *ptrB, GEN *ptrU, GEN *ptrr, double DELTA, double ETA, long flag, long prec)
     332                 :            : {
     333                 :     881692 :   const long gram = flag & LLL_GRAM; /*Gram matrix*/
     334                 :     881692 :   const long keepfirst = flag & LLL_KEEP_FIRST; /*never swap with first vector*/
     335                 :            :   pari_sp av, av2;
     336                 :            :   long kappa, kappa2, d, n, i, j, zeros, kappamax, maxG, bab;
     337                 :            :   GEN G, mu, r, s, tmp, SPtmp, alpha;
     338                 :     881692 :   GEN delta = dbltor(DELTA), eta = dbltor(ETA), halfplus1 = dbltor(1.5);
     339                 :     881692 :   const long triangular = 0;
     340                 :            :   pari_timer T;
     341                 :     881692 :   GEN B = *ptrB, U;
     342                 :     881692 :   long cnt = 0;
     343                 :            : 
     344                 :     881692 :   d = lg(B)-1;
     345         [ +  + ]:     881692 :   if (gram)
     346                 :            :   {
     347                 :      14016 :     G = B;
     348                 :      14016 :     n = d;
     349                 :      14016 :     B = cgetg(1, t_VECSMALL); /* dummy */
     350                 :            :   }
     351                 :            :   else
     352                 :            :   {
     353                 :     867676 :     G = zeromatcopy(d,d);
     354                 :     867676 :     n = nbrows(B);
     355                 :            :   }
     356                 :     881692 :   U = *ptrU; /* NULL if inplace */
     357                 :            : 
     358         [ -  + ]:     881692 :   if(DEBUGLEVEL>=4)
     359                 :            :   {
     360                 :          0 :     timer_start(&T);
     361                 :          0 :     err_printf("Entering L^2: LLL-parameters (%P.3f,%.3Pf), working precision %d words\n",delta,eta, prec);
     362                 :            :   }
     363                 :            : 
     364                 :     881692 :   mu = cgetg(d+1, t_MAT);
     365                 :     881692 :   r  = cgetg(d+1, t_MAT);
     366                 :     881692 :   s  = cgetg(d+1, t_VEC);
     367         [ +  + ]:    3484292 :   for (j = 1; j <= d; j++)
     368                 :            :   {
     369                 :    2602600 :     GEN M = cgetg(d+1, t_COL), R = cgetg(d+1, t_COL);
     370                 :    2602600 :     gel(mu,j)= M;
     371                 :    2602600 :     gel(r,j) = R;
     372                 :    2602600 :     gel(s,j) = cgetr(prec);
     373         [ +  + ]:   12702410 :     for (i = 1; i <= d; i++) {
     374                 :   10099810 :       gel(R,i) = cgetr(prec);
     375                 :   10099810 :       gel(M,i) = cgetr(prec);
     376                 :            :     }
     377                 :            :   }
     378                 :     881692 :   SPtmp = zerovec(d+1);
     379                 :     881692 :   alpha = cgetg(d+1, t_VECSMALL);
     380                 :     881692 :   av = avma;
     381                 :            : 
     382                 :            :   /* Step2: Initializing the main loop */
     383                 :     881692 :   kappamax = 1;
     384                 :     881692 :   i = 1;
     385                 :     881692 :   maxG = d; /* later updated to kappamax if (!gram) */
     386                 :            : 
     387                 :            :   do {
     388         [ +  + ]:     883652 :     if (!gram) gmael(G,i,i) = ZV_dotsquare(gel(B,i));
     389                 :     883652 :     affir(gmael(G,i,i), gmael(r,i,i));
     390 [ +  + ][ +  - ]:     883652 :   } while (signe(gmael(G,i,i)) == 0 && (++i <=d));
     391                 :     881692 :   zeros = i-1; /* all vectors B[i] with i <= zeros are zero vectors */
     392                 :     881692 :   kappa = i;
     393         [ +  - ]:     881692 :   if (zeros < d) affir(gmael(G,zeros+1,zeros+1), gmael(r,zeros+1,zeros+1));
     394         [ +  + ]:    3482332 :   for (i=zeros+1; i<=d; i++) alpha[i]=1;
     395                 :            : 
     396         [ +  + ]:   12124446 :   while (++kappa <= d)
     397                 :            :   {
     398         [ +  + ]:   11242754 :     if (kappa>kappamax)
     399                 :            :     {
     400         [ -  + ]:    1718948 :       if (DEBUGLEVEL>=4) err_printf("K%ld ",kappa);
     401                 :    1718948 :       kappamax = kappa;
     402         [ +  + ]:    1718948 :       if (!gram) {
     403         [ +  + ]:    6678269 :         for (i=zeros+1; i<=kappa; i++)
     404                 :    5028108 :           gmael(G,kappa,i) = ZV_dotproduct(gel(B,kappa), gel(B,i));
     405                 :    1650161 :         maxG = kappamax;
     406                 :            :       }
     407                 :            :     }
     408                 :            :     /* Step3: Call to the Babai algorithm, mu,r,s updated in place */
     409         [ +  + ]:   21088165 :     bab = Babai(av, kappa, &G,&B,&U, mu,r,s, alpha[kappa], zeros, maxG,
     410 [ -  + ][ #  # ]:    9845411 :       gram? 0 : ((triangular && kappamax <= n) ? kappamax: n),
     411                 :            :       eta, halfplus1, prec);
     412 [ -  + ][ #  # ]:   11242754 :     if (bab) {*ptrB=(gram?G:B); *ptrU=U; return NULL; }
     413                 :            : 
     414                 :   11242754 :     av2 = avma;
     415         [ +  + ]:   22483248 :     if ((keepfirst && kappa == 2) ||
           [ +  +  +  + ]
     416                 :   11240494 :         cmprr(mulrr(gmael(r,kappa-1,kappa-1), delta), gel(s,kappa-1)) <= 0)
     417                 :            :     { /* Step4: Success of Lovasz's condition */
     418                 :    7275699 :       alpha[kappa] = kappa;
     419                 :    7275699 :       tmp = mulrr(gmael(mu,kappa,kappa-1), gmael(r,kappa,kappa-1));
     420                 :    7275699 :       affrr(subrr(gel(s,kappa-1), tmp), gmael(r,kappa,kappa));
     421                 :    7275699 :       avma = av2;
     422                 :            :     }
     423                 :            :     else
     424                 :            :     { /* Step5: Find the right insertion index kappa, kappa2 = initial kappa */
     425 [ -  + ][ #  # ]:    3967055 :       if (DEBUGLEVEL>=4 && kappa==kappamax && signe(gel(s,kappa-1)))
                 [ #  # ]
     426         [ #  # ]:          0 :         if (++cnt > 20) { cnt = 0; err_printf("(%ld) ", expo(gel(s,1))); }
     427                 :    3967055 :       kappa2 = kappa;
     428                 :            :       do {
     429                 :    9537996 :         kappa--;
     430 [ +  + ][ +  + ]:    9537996 :         if (kappa<zeros+2 + (keepfirst ? 1: 0)) break;
     431                 :    7786128 :         tmp = mulrr(gmael(r,kappa-1,kappa-1), delta);
     432         [ +  + ]:    7786128 :       } while (cmprr(gel(s,kappa-1), tmp) <=0 );
     433                 :    3967055 :       avma = av2;
     434                 :            : 
     435         [ +  + ]:   13505051 :       for (i=kappa; i<kappa2; i++)
     436         [ +  + ]:    9537996 :         if (kappa <= alpha[i]) alpha[i] = kappa;
     437         [ +  + ]:   13505051 :       for (i=kappa2; i>kappa; i--) alpha[i] = alpha[i-1];
     438         [ +  + ]:   17299856 :       for (i=kappa2+1; i<=kappamax; i++)
     439         [ +  + ]:   13332801 :         if (kappa < alpha[i]) alpha[i] = kappa;
     440                 :    3967055 :       alpha[kappa] = kappa;
     441                 :            : 
     442                 :            :       /* Step6: Update the mu's and r's */
     443                 :    3967055 :       rotate(mu,kappa2,kappa,d);
     444                 :    3967055 :       rotate(r,kappa2,kappa,d);
     445                 :    3967055 :       affrr(gel(s,kappa), gmael(r,kappa,kappa));
     446                 :            : 
     447                 :            :       /* Step7: Update B, G, U */
     448         [ +  + ]:    3967055 :       if (!gram) rotate(B,kappa2,kappa,n);
     449         [ +  + ]:    3967055 :       if (U) rotate(U,kappa2,kappa,d);
     450                 :            : 
     451         [ +  + ]:   37264424 :       for (i=1; i<=kappa2; i++) gel(SPtmp,i) = gmael(G,kappa2,i);
     452         [ +  + ]:   17755494 :       for (i=kappa2+1; i<=maxG; i++) gel(SPtmp,i) = gmael(G,i,kappa2);
     453         [ +  + ]:   13505051 :       for (i=kappa2; i>kappa; i--)
     454                 :            :       {
     455         [ +  + ]:   63767861 :         for (j=1; j<kappa; j++) gmael(G,i,j) = gmael(G,i-1,j);
     456                 :    9537996 :         gmael(G,i,kappa) = gel(SPtmp,i-1);
     457         [ +  + ]:   40801188 :         for (j=kappa+1; j<=i; j++) gmael(G,i,j) = gmael(G,i-1,j-1);
     458         [ +  + ]:   45121861 :         for (j=kappa2+1; j<=maxG; j++) gmael(G,j,i) = gmael(G,j,i-1);
     459                 :            :       }
     460         [ +  + ]:   23759373 :       for (i=1; i<kappa; i++) gmael(G,kappa,i) = gel(SPtmp,i);
     461                 :    3967055 :       gmael(G,kappa,kappa) = gel(SPtmp,kappa2);
     462         [ +  + ]:   17755494 :       for (i=kappa2+1; i<=maxG; i++) gmael(G,i,kappa) = gel(SPtmp,i);
     463                 :            : 
     464                 :            :       /* Step8: Prepare the next loop iteration */
     465 [ +  + ][ +  + ]:    3967055 :       if (kappa == zeros+1 && !signe(gmael(G,kappa,kappa)))
     466                 :            :       {
     467                 :      14190 :         zeros++; kappa++;
     468                 :      14190 :         affir(gmael(G,kappa,kappa), gmael(r,kappa,kappa));
     469                 :            :       }
     470                 :            :     }
     471                 :            :   }
     472                 :            : 
     473         [ -  + ]:     881692 :   if (DEBUGLEVEL>=4) timer_printf(&T,"LLL");
     474         [ +  + ]:     881692 :   if (ptrr) *ptrr = RgM_diagonal_shallow(r);
     475         [ +  + ]:     881692 :   if (!U)
     476                 :            :   {
     477         [ -  + ]:     207748 :     if (zeros) {
     478         [ #  # ]:          0 :       if (gram) {
     479                 :          0 :         G = lll_get_im(G, zeros);
     480                 :          0 :         d -= zeros;
     481         [ #  # ]:          0 :         for (i = 1; i <= d; i++) gel(G,i) = lll_get_im(gel(G,i), zeros);
     482                 :            :       }
     483                 :            :       else
     484                 :          0 :         B = lll_get_im(B, zeros);
     485                 :            :     }
     486                 :            :   }
     487         [ +  + ]:     673944 :   else if (flag & (LLL_IM|LLL_KER|LLL_ALL))
     488                 :     672047 :     U = lll_finish(U, zeros, flag);
     489         [ +  + ]:     881692 :   if (gram)
     490                 :            :   {
     491         [ +  - ]:      14016 :     if (U) return U;
     492         [ #  # ]:          0 :     for (i = 1; i <= d; i++)
     493         [ #  # ]:          0 :       for (j = i+1; j <= d; j++) gmael(G,i,j) = gmael(G,j,i);
     494                 :          0 :     return G;
     495                 :            :   }
     496         [ +  + ]:     881692 :   return U? U: B;
     497                 :            : }
     498                 :            : 
     499                 :            : /* Assume x a ZM, if ptB != NULL, set it to Gram-Schmidt (squared) norms */
     500                 :            : GEN
     501                 :     882797 : ZM_lll_norms(GEN x, double DELTA, long flag, GEN *B)
     502                 :            : {
     503                 :     882797 :   pari_sp ltop = avma;
     504                 :     882797 :   const long compat = flag & LLL_COMPATIBLE;
     505                 :     882797 :   const double ETA = 0.51;
     506                 :     882797 :   long p, n = lg(x)-1;
     507                 :            :   GEN U;
     508         [ +  + ]:     882797 :   if (n <= 1) return lll_trivial(x, flag);
     509                 :     881692 :   x = RgM_shallowcopy(x);
     510         [ +  + ]:     881692 :   U = (flag & LLL_INPLACE)? NULL: matid(n);
     511         [ +  + ]:     881692 :   for (p = compat? DEFAULTPREC: LOWDEFAULTPREC;;)
     512                 :            :   {
     513                 :     881692 :     GEN m = fplll(&x, &U, B, DELTA, ETA, flag, p);
     514         [ +  - ]:     881692 :     if (m) return m;
     515         [ #  # ]:          0 :     if (compat)
     516                 :          0 :       p += DEFAULTPREC-2;
     517                 :            :     else
     518                 :          0 :       incrprec(p);
     519         [ #  # ]:          0 :     gerepileall(ltop, U? 2: 1, &x, &U);
     520                 :     882797 :   }
     521                 :            :   return NULL; /* NOT REACHED */
     522                 :            : }
     523                 :            : 
     524                 :            : /********************************************************************/
     525                 :            : /**                                                                **/
     526                 :            : /**                        LLL OVER K[X]                           **/
     527                 :            : /**                                                                **/
     528                 :            : /********************************************************************/
     529                 :            : static int
     530                 :        270 : pslg(GEN x)
     531                 :            : {
     532                 :            :   long tx;
     533         [ +  + ]:        270 :   if (gequal0(x)) return 2;
     534         [ +  + ]:        270 :   tx = typ(x); return is_scalar_t(tx)? 3: lg(x);
     535                 :            : }
     536                 :            : 
     537                 :            : static int
     538                 :        105 : REDgen(long k, long l, GEN h, GEN L, GEN B)
     539                 :            : {
     540                 :        105 :   GEN q, u = gcoeff(L,k,l);
     541                 :            :   long i;
     542                 :            : 
     543         [ +  + ]:        105 :   if (pslg(u) < pslg(B)) return 0;
     544                 :            : 
     545                 :         75 :   q = gneg(gdeuc(u,B));
     546                 :         75 :   gel(h,k) = gadd(gel(h,k), gmul(q,gel(h,l)));
     547         [ -  + ]:         75 :   for (i=1; i<l; i++) gcoeff(L,k,i) = gadd(gcoeff(L,k,i), gmul(q,gcoeff(L,l,i)));
     548                 :        105 :   gcoeff(L,k,l) = gadd(gcoeff(L,k,l), gmul(q,B)); return 1;
     549                 :            : }
     550                 :            : 
     551                 :            : static int
     552                 :        105 : do_SWAPgen(GEN h, GEN L, GEN B, long k, GEN fl, int *flc)
     553                 :            : {
     554                 :            :   GEN p1, la, la2, Bk;
     555                 :            :   long ps1, ps2, i, j, lx;
     556                 :            : 
     557         [ +  + ]:        105 :   if (!fl[k-1]) return 0;
     558                 :            : 
     559                 :         75 :   la = gcoeff(L,k,k-1); la2 = gsqr(la);
     560                 :         75 :   Bk = gel(B,k);
     561         [ +  + ]:         75 :   if (fl[k])
     562                 :            :   {
     563                 :         30 :     GEN q = gadd(la2, gmul(gel(B,k-1),gel(B,k+1)));
     564                 :         30 :     ps1 = pslg(gsqr(Bk));
     565                 :         30 :     ps2 = pslg(q);
     566 [ +  + ][ -  + ]:         30 :     if (ps1 <= ps2 && (ps1 < ps2 || !*flc)) return 0;
                 [ #  # ]
     567                 :         15 :     *flc = (ps1 != ps2);
     568                 :         15 :     gel(B,k) = gdiv(q, Bk);
     569                 :            :   }
     570                 :            : 
     571                 :         60 :   swap(gel(h,k-1), gel(h,k)); lx = lg(L);
     572         [ -  + ]:         60 :   for (j=1; j<k-1; j++) swap(gcoeff(L,k-1,j), gcoeff(L,k,j));
     573         [ +  + ]:         60 :   if (fl[k])
     574                 :            :   {
     575         [ -  + ]:         15 :     for (i=k+1; i<lx; i++)
     576                 :            :     {
     577                 :          0 :       GEN t = gcoeff(L,i,k);
     578                 :          0 :       p1 = gsub(gmul(gel(B,k+1),gcoeff(L,i,k-1)), gmul(la,t));
     579                 :          0 :       gcoeff(L,i,k) = gdiv(p1, Bk);
     580                 :          0 :       p1 = gadd(gmul(la,gcoeff(L,i,k-1)), gmul(gel(B,k-1),t));
     581                 :          0 :       gcoeff(L,i,k-1) = gdiv(p1, Bk);
     582                 :            :     }
     583                 :            :   }
     584         [ +  + ]:         45 :   else if (!gequal0(la))
     585                 :            :   {
     586                 :         15 :     p1 = gdiv(la2, Bk);
     587                 :         15 :     gel(B,k+1) = gel(B,k) = p1;
     588         [ -  + ]:         15 :     for (i=k+2; i<=lx; i++) gel(B,i) = gdiv(gmul(p1,gel(B,i)),Bk);
     589         [ -  + ]:         15 :     for (i=k+1; i<lx; i++)
     590                 :          0 :       gcoeff(L,i,k-1) = gdiv(gmul(la,gcoeff(L,i,k-1)), Bk);
     591         [ -  + ]:         15 :     for (j=k+1; j<lx-1; j++)
     592         [ #  # ]:          0 :       for (i=j+1; i<lx; i++)
     593                 :          0 :         gcoeff(L,i,j) = gdiv(gmul(p1,gcoeff(L,i,j)), Bk);
     594                 :            :   }
     595                 :            :   else
     596                 :            :   {
     597                 :         30 :     gcoeff(L,k,k-1) = gen_0;
     598         [ -  + ]:         30 :     for (i=k+1; i<lx; i++)
     599                 :            :     {
     600                 :          0 :       gcoeff(L,i,k) = gcoeff(L,i,k-1);
     601                 :          0 :       gcoeff(L,i,k-1) = gen_0;
     602                 :            :     }
     603                 :         30 :     B[k] = B[k-1]; fl[k] = 1; fl[k-1] = 0;
     604                 :            :   }
     605                 :        105 :   return 1;
     606                 :            : }
     607                 :            : 
     608                 :            : static void
     609                 :         90 : incrementalGSgen(GEN x, GEN L, GEN B, long k, GEN fl)
     610                 :            : {
     611                 :         90 :   GEN u = NULL; /* gcc -Wall */
     612                 :            :   long i, j, tu;
     613         [ +  + ]:        225 :   for (j=1; j<=k; j++)
     614 [ +  + ][ +  - ]:        135 :     if (j==k || fl[j])
     615                 :            :     {
     616                 :        135 :       u = gcoeff(x,k,j); tu = typ(u);
     617         [ -  + ]:        135 :       if (! is_extscalar_t(tu)) pari_err_TYPE("incrementalGSgen",u);
     618         [ +  + ]:        180 :       for (i=1; i<j; i++)
     619         [ +  - ]:         45 :         if (fl[i])
     620                 :            :         {
     621                 :         45 :           u = gsub(gmul(gel(B,i+1),u), gmul(gcoeff(L,k,i),gcoeff(L,j,i)));
     622                 :         45 :           u = gdiv(u, gel(B,i));
     623                 :            :         }
     624                 :        135 :       gcoeff(L,k,j) = u;
     625                 :            :     }
     626         [ +  + ]:         90 :   if (gequal0(u)) B[k+1] = B[k];
     627                 :            :   else
     628                 :            :   {
     629                 :         60 :     gel(B,k+1) = gcoeff(L,k,k); gcoeff(L,k,k) = gen_1; fl[k] = 1;
     630                 :            :   }
     631                 :         90 : }
     632                 :            : 
     633                 :            : static GEN
     634                 :         90 : lllgramallgen(GEN x, long flag)
     635                 :            : {
     636                 :         90 :   long lx = lg(x), i, j, k, l, n;
     637                 :            :   pari_sp av, lim;
     638                 :            :   GEN B, L, h, fl;
     639                 :            :   int flc;
     640                 :            : 
     641         [ +  + ]:         90 :   n = lx-1; if (n<=1) return lll_trivial(x,flag);
     642         [ -  + ]:         45 :   if (lgcols(x) != lx) pari_err_DIM("lllgramallgen");
     643                 :            : 
     644                 :         45 :   fl = cgetg(lx, t_VECSMALL);
     645                 :            : 
     646                 :         45 :   av = avma; lim = stack_lim(av,1);
     647                 :         45 :   B = scalarcol_shallow(gen_1, lx);
     648                 :         45 :   L = cgetg(lx,t_MAT);
     649         [ +  + ]:        135 :   for (j=1; j<lx; j++) { gel(L,j) = zerocol(n); fl[j] = 0; }
     650                 :            : 
     651                 :         45 :   h = matid(n);
     652         [ +  + ]:        135 :   for (i=1; i<lx; i++)
     653                 :         90 :     incrementalGSgen(x, L, B, i, fl);
     654                 :         45 :   flc = 0;
     655                 :         45 :   for(k=2;;)
     656                 :            :   {
     657         [ +  + ]:        105 :     if (REDgen(k, k-1, h, L, gel(B,k))) flc = 1;
     658 [ +  + ][ -  + ]:        105 :     if (do_SWAPgen(h, L, B, k, fl, &flc)) { if (k > 2) k--; }
     659                 :            :     else
     660                 :            :     {
     661         [ -  + ]:         45 :       for (l=k-2; l>=1; l--)
     662         [ #  # ]:          0 :         if (REDgen(k, l, h, L, gel(B,l+1))) flc = 1;
     663         [ +  - ]:         45 :       if (++k > n) break;
     664                 :            :     }
     665         [ -  + ]:         60 :     if (low_stack(lim, stack_lim(av,1)))
     666                 :            :     {
     667         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"lllgramallgen");
     668                 :          0 :       gerepileall(av,3,&B,&L,&h);
     669                 :            :     }
     670                 :         60 :   }
     671 [ +  - ][ +  + ]:         75 :   k=1; while (k<lx && !fl[k]) k++;
     672                 :         90 :   return lll_finish(h,k-1,flag);
     673                 :            : }
     674                 :            : 
     675                 :            : static GEN
     676                 :         90 : lllallgen(GEN x, long flag)
     677                 :            : {
     678                 :         90 :   pari_sp av = avma;
     679         [ +  + ]:         90 :   if ((flag & LLL_GRAM) == 0) x = gram_matrix(x);
     680                 :         90 :   return gerepilecopy(av, lllgramallgen(x, flag));
     681                 :            : }
     682                 :            : GEN
     683                 :         30 : lllgen(GEN x) { return lllallgen(x, LLL_IM); }
     684                 :            : GEN
     685                 :         30 : lllkerimgen(GEN x) { return lllallgen(x, LLL_ALL); }
     686                 :            : GEN
     687                 :          0 : lllgramgen(GEN x)  { return lllallgen(x, LLL_IM|LLL_GRAM); }
     688                 :            : GEN
     689                 :         30 : lllgramkerimgen(GEN x)  { return lllallgen(x, LLL_ALL|LLL_GRAM); }
     690                 :            : 
     691                 :            : static GEN
     692                 :      17794 : lllall(GEN x, long flag)
     693                 :            : {
     694                 :      17794 :   pari_sp av = avma;
     695                 :      17794 :   return gerepilecopy(av, ZM_lll(x, LLLDFT, flag));
     696                 :            : }
     697                 :            : GEN
     698                 :       4865 : lllint(GEN x) { return lllall(x, LLL_IM); }
     699                 :            : GEN
     700                 :         30 : lllkerim(GEN x) { return lllall(x, LLL_ALL); }
     701                 :            : GEN
     702                 :      12869 : lllgramint(GEN x) { return lllall(x, LLL_IM | LLL_GRAM); }
     703                 :            : GEN
     704                 :         30 : lllgramkerim(GEN x) { return lllall(x, LLL_ALL | LLL_GRAM); }
     705                 :            : 
     706                 :            : static GEN
     707                 :     158230 : rescale_to_int(GEN x)
     708                 :            : {
     709                 :            :   long e, i,j, lx, hx, emin;
     710                 :     158230 :   GEN D = gen_1;
     711                 :     158230 :   int exact = 1;
     712                 :            : 
     713         [ -  + ]:     158230 :   lx = lg(x); if (lx == 1) return x;
     714                 :     158230 :   hx = lgcols(x);
     715                 :     158230 :   emin = HIGHEXPOBIT;
     716         [ +  + ]:     604449 :   for (j = 1; j < lx; j++)
     717         [ +  + ]:    1829337 :     for (i = 1; i < hx; i++)
     718                 :            :     {
     719                 :    1383118 :       GEN c = gcoeff(x,i,j);
     720   [ +  +  -  + ]:    1383118 :       switch(typ(c))
     721                 :            :       {
     722                 :            :         case t_REAL:
     723                 :     929637 :           exact = 0;
     724         [ +  + ]:     929637 :           if (!signe(c)) continue;
     725                 :     924095 :           e = expo(c) - bit_prec(c);
     726                 :     924095 :           break;
     727                 :            :         case t_INT:
     728         [ +  + ]:     453461 :           if (!signe(c)) continue;
     729                 :     165843 :           e = expi(c) + 32;
     730                 :     165843 :           break;
     731                 :            :         case t_FRAC:
     732                 :          0 :           e = expi(gel(c,1)) - expi(gel(c,2)) + 32;
     733         [ #  # ]:          0 :           if (exact) D = lcmii(D, gel(c,2));
     734                 :          0 :           break;
     735                 :            :         default:
     736                 :         20 :           pari_err_TYPE("rescale_to_int",c);
     737                 :          0 :           return NULL; /* not reached */
     738                 :            :       }
     739         [ +  + ]:    1089938 :       if (e < emin) emin = e;
     740                 :            :     }
     741 [ +  + ][ -  + ]:     158210 :   if (exact) return D == gen_1 ? x: Q_muli_to_int(x, D);
     742                 :     158210 :   return grndtoi(gmul2n(x, -emin), &e);
     743                 :            : }
     744                 :            : 
     745                 :            : GEN
     746                 :     158820 : lllfp(GEN x, double D, long flag)
     747                 :            : {
     748                 :     158820 :   long n = lg(x)-1;
     749                 :     158820 :   pari_sp av = avma;
     750                 :            :   GEN h;
     751         [ +  + ]:     158820 :   if (n <= 1) return lll_trivial(x,flag);
     752                 :     158230 :   h = ZM_lll(rescale_to_int(x), D, flag);
     753                 :     158800 :   return gerepilecopy(av, h);
     754                 :            : }
     755                 :            : 
     756                 :            : GEN
     757                 :         45 : lllgram(GEN x) { return lllfp(x,LLLDFT,LLL_GRAM|LLL_IM); }
     758                 :            : GEN
     759                 :     156878 : lll(GEN x) { return lllfp(x,LLLDFT,LLL_IM); }
     760                 :            : 
     761                 :            : GEN
     762                 :        210 : qflll0(GEN x, long flag)
     763                 :            : {
     764         [ -  + ]:        210 :   if (typ(x) != t_MAT) pari_err_TYPE("qflll",x);
     765   [ +  +  +  +  :        210 :   switch(flag)
                +  +  - ]
     766                 :            :   {
     767                 :         35 :     case 0: return lll(x);
     768                 :         45 :     case 1: RgM_check_ZM(x,"qflll"); return lllint(x);
     769                 :         35 :     case 2: RgM_check_ZM(x,"qflll"); return lllintpartial(x);
     770                 :         35 :     case 4: RgM_check_ZM(x,"qflll"); return lllkerim(x);
     771                 :         30 :     case 5: return lllkerimgen(x);
     772                 :         30 :     case 8: return lllgen(x);
     773                 :          0 :     default: pari_err_FLAG("qflll");
     774                 :            :   }
     775                 :        160 :   return NULL; /* not reached */
     776                 :            : }
     777                 :            : 
     778                 :            : GEN
     779                 :        140 : qflllgram0(GEN x, long flag)
     780                 :            : {
     781         [ -  + ]:        140 :   if (typ(x) != t_MAT) pari_err_TYPE("qflllgram",x);
     782   [ +  +  +  +  :        140 :   switch(flag)
                   -  - ]
     783                 :            :   {
     784                 :         40 :     case 0: return lllgram(x);
     785                 :         35 :     case 1: RgM_check_ZM(x,"qflllgram"); return lllgramint(x);
     786                 :         35 :     case 4: RgM_check_ZM(x,"qflllgram"); return lllgramkerim(x);
     787                 :         30 :     case 5: return lllgramkerimgen(x);
     788                 :          0 :     case 8: return lllgramgen(x);
     789                 :          0 :     default: pari_err_FLAG("qflllgram");
     790                 :            :   }
     791                 :        110 :   return NULL; /* not reached */
     792                 :            : }
     793                 :            : 
     794                 :            : /********************************************************************/
     795                 :            : /**                                                                **/
     796                 :            : /**                   INTEGRAL KERNEL (LLL REDUCED)                **/
     797                 :            : /**                                                                **/
     798                 :            : /********************************************************************/
     799                 :            : /* Horribly slow (coeff explosion in small dimension): never use this */
     800                 :            : static GEN
     801                 :         10 : kerint1(GEN x)
     802                 :            : {
     803                 :         10 :   pari_sp av = avma;
     804                 :         10 :   return gerepilecopy(av, ZM_lll(QM_ImQ_hnf(ker(x)), LLLDFT, LLL_INPLACE));
     805                 :            : }
     806                 :            : /* Mostly useless: use ZM_lll(x, 0.99, LLL_KER) directly */
     807                 :            : GEN
     808                 :         15 : kerint(GEN x)
     809                 :            : {
     810                 :         15 :   pari_sp av = avma;
     811                 :         15 :   GEN h = ZM_lll(x, LLLDFT, LLL_KER);
     812         [ -  + ]:         15 :   if (lg(h)==1) { avma = av; return cgetg(1, t_MAT); }
     813                 :         15 :   return gerepilecopy(av, ZM_lll(h, LLLDFT, LLL_INPLACE));
     814                 :            : }
     815                 :            : 
     816                 :            : GEN
     817                 :         25 : matkerint0(GEN x, long flag)
     818                 :            : {
     819         [ -  + ]:         25 :   if (typ(x) != t_MAT) pari_err_TYPE("matkerint",x);
     820                 :         25 :   RgM_check_ZM(x, "kerint");
     821      [ +  +  - ]:         25 :   switch(flag)
     822                 :            :   {
     823                 :         15 :     case 0: return kerint(x);
     824                 :         10 :     case 1: return kerint1(x);
     825                 :          0 :     default: pari_err_FLAG("matkerint");
     826                 :            :   }
     827                 :         25 :   return NULL; /* not reached */
     828                 :            : }

Generated by: LCOV version 1.9