Code coverage tests

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

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

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

LCOV - code coverage report
Current view: top level - kernel/gmp - mp.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.18.1 lcov report (development 30365-beea1ff998) Lines: 688 719 95.7 %
Date: 2025-07-01 09:21:48 Functions: 54 56 96.4 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : #line 2 "../src/kernel/gmp/mp.c"
       2             : /* Copyright (C) 2002-2003  The PARI group.
       3             : 
       4             : This file is part of the PARI/GP package.
       5             : 
       6             : PARI/GP is free software; you can redistribute it and/or modify it under the
       7             : terms of the GNU General Public License as published by the Free Software
       8             : Foundation; either version 2 of the License, or (at your option) any later
       9             : version. It is distributed in the hope that it will be useful, but WITHOUT
      10             : ANY WARRANTY WHATSOEVER.
      11             : 
      12             : Check the License for details. You should have received a copy of it, along
      13             : with the package; see the file 'COPYING'. If not, write to the Free Software
      14             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      15             : 
      16             : /***********************************************************************/
      17             : /**                                                                   **/
      18             : /**                               GMP KERNEL                          **/
      19             : /** BA2002Sep24                                                       **/
      20             : /***********************************************************************/
      21             : /* GMP t_INT as just like normal t_INT, just the mantissa is the other way
      22             :  * round
      23             :  *
      24             :  *   `How would you like to live in Looking-glass House, Kitty?  I
      25             :  *   wonder if they'd give you milk in there?  Perhaps Looking-glass
      26             :  *   milk isn't good to drink--But oh, Kitty! now we come to the
      27             :  *   passage.  You can just see a little PEEP of the passage in
      28             :  *   Looking-glass House, if you leave the door of our drawing-room
      29             :  *   wide open:  and it's very like our passage as far as you can see,
      30             :  *   only you know it may be quite different on beyond.  Oh, Kitty!
      31             :  *   how nice it would be if we could only get through into Looking-
      32             :  *   glass House!  I'm sure it's got, oh! such beautiful things in it!
      33             :  *
      34             :  *  Through the Looking Glass,  Lewis Carrol
      35             :  *
      36             :  *  (pityful attempt to beat GN code/comments rate)
      37             :  *  */
      38             : 
      39             : #include <gmp.h>
      40             : #include "pari.h"
      41             : #include "paripriv.h"
      42             : #include "../src/kernel/none/tune-gen.h"
      43             : 
      44             : /*We need PARI invmod renamed to invmod_pari*/
      45             : #define INVMOD_PARI
      46             : 
      47           0 : static void *pari_gmp_realloc(void *ptr, size_t old_size, size_t new_size) {
      48           0 :   (void)old_size; return (void *) pari_realloc(ptr,new_size);
      49             : }
      50             : 
      51     1755950 : static void pari_gmp_free(void *ptr, size_t old_size){
      52     1755950 :   (void)old_size; pari_free(ptr);
      53     1755950 : }
      54             : 
      55             : static void *(*old_gmp_malloc)(size_t new_size);
      56             : static void *(*old_gmp_realloc)(void *ptr, size_t old_size, size_t new_size);
      57             : static void (*old_gmp_free)(void *ptr, size_t old_size);
      58             : 
      59             : void
      60        1112 : pari_kernel_init(void)
      61             : {
      62        1112 :   mp_get_memory_functions (&old_gmp_malloc, &old_gmp_realloc, &old_gmp_free);
      63        1112 :   mp_set_memory_functions((void *(*)(size_t)) pari_malloc, pari_gmp_realloc, pari_gmp_free);
      64        1112 : }
      65             : 
      66             : const char *
      67           4 : pari_kernel_version(void)
      68             : {
      69             : #ifdef gmp_version
      70           4 :   return gmp_version;
      71             : #else
      72             :   return "";
      73             : #endif
      74             : }
      75             : 
      76             : void
      77        1104 : pari_kernel_close(void)
      78             : {
      79             :   void *(*new_gmp_malloc)(size_t new_size);
      80             :   void *(*new_gmp_realloc)(void *ptr, size_t old_size, size_t new_size);
      81             :   void (*new_gmp_free)(void *ptr, size_t old_size);
      82        1104 :   mp_get_memory_functions (&new_gmp_malloc, &new_gmp_realloc, &new_gmp_free);
      83        1104 :   if (new_gmp_malloc==pari_malloc) new_gmp_malloc = old_gmp_malloc;
      84        1104 :   if (new_gmp_realloc==pari_gmp_realloc) new_gmp_realloc = old_gmp_realloc;
      85        1104 :   if (new_gmp_free==pari_gmp_free) new_gmp_free = old_gmp_free;
      86        1104 :   mp_set_memory_functions(new_gmp_malloc, new_gmp_realloc, new_gmp_free);
      87        1104 : }
      88             : 
      89             : #define LIMBS(x)  ((mp_limb_t *)((x)+2))
      90             : #define NLIMBS(x) (lgefint(x)-2)
      91             : /*This one is for t_REALs to emphasize they are not t_INTs*/
      92             : #define RLIMBS(x)  ((mp_limb_t *)((x)+2))
      93             : #define RNLIMBS(x) (lg(x)-2)
      94             : 
      95             : INLINE void
      96     6890087 : xmpn_copy(mp_limb_t *x, mp_limb_t *y, long n)
      97             : {
      98    57045537 :   while (--n >= 0) x[n]=y[n];
      99     6890087 : }
     100             : 
     101             : INLINE void
     102   587163097 : xmpn_mirror(mp_limb_t *x, long n)
     103             : {
     104             :   long i;
     105  3922674205 :   for(i=0;i<(n>>1);i++)
     106             :   {
     107  3335511108 :     ulong m=x[i];
     108  3335511108 :     x[i]=x[n-1-i];
     109  3335511108 :     x[n-1-i]=m;
     110             :   }
     111   587163097 : }
     112             : 
     113             : INLINE void
     114   718681539 : xmpn_mirrorcopy(mp_limb_t *z, mp_limb_t *x, long n)
     115             : {
     116             :   long i;
     117  9935891473 :   for(i=0;i<n;i++)
     118  9217209934 :     z[i]=x[n-1-i];
     119   718681539 : }
     120             : 
     121             : INLINE void
     122   237488159 : xmpn_zero(mp_ptr x, mp_size_t n)
     123             : {
     124  2075509410 :   while (--n >= 0) x[n]=0;
     125   237488159 : }
     126             : 
     127             : INLINE GEN
     128    41256378 : icopy_ef(GEN x, long l)
     129             : {
     130    41256378 :   long lx = lgefint(x);
     131    41256378 :   const GEN y = cgeti(l);
     132             : 
     133   294214700 :   while (--lx > 0) y[lx]=x[lx];
     134    41254936 :   return y;
     135             : }
     136             : 
     137             : /* NOTE: arguments of "spec" routines (muliispec, addiispec, etc.) aren't
     138             :  * GENs but pairs (long *a, long na) representing a list of digits (in basis
     139             :  * BITS_IN_LONG) : a[0], ..., a[na-1]. In order to facilitate splitting: no
     140             :  * need to reintroduce codewords. */
     141             : 
     142             : /***********************************************************************/
     143             : /**                                                                   **/
     144             : /**                     ADDITION / SUBTRACTION                        **/
     145             : /**                                                                   **/
     146             : /***********************************************************************/
     147             : 
     148             : GEN
     149     2997878 : setloop(GEN a)
     150             : {
     151     2997878 :   pari_sp av = avma - 2 * sizeof(long);
     152     2997878 :   (void)cgetg(lgefint(a) + 3, t_VECSMALL);
     153     2997879 :   return icopy_avma(a, av); /* two cells of extra space after a */
     154             : }
     155             : 
     156             : /* we had a = setloop(?), then some incloops. Reset a to b */
     157             : GEN
     158      174328 : resetloop(GEN a, GEN b) {
     159      174328 :   a[0] = evaltyp(t_INT) | evallg(lgefint(b));
     160      174328 :   affii(b, a); return a;
     161             : }
     162             : 
     163             : /* assume a > 0, initialized by setloop. Do a++ */
     164             : static GEN
     165   103276343 : incpos(GEN a)
     166             : {
     167   103276343 :   long i, l = lgefint(a);
     168   103276348 :   for (i=2; i<l; i++)
     169   103281053 :     if (++uel(a,i)) return a;
     170           3 :   a[l] = 1; l++;
     171           3 :   a[0]=evaltyp(t_INT) | _evallg(l);
     172           3 :   a[1]=evalsigne(1) | evallgefint(l);
     173           3 :   return a;
     174             : }
     175             : 
     176             : /* assume a < 0, initialized by setloop. Do a++ */
     177             : static GEN
     178       66684 : incneg(GEN a)
     179             : {
     180       66684 :   long i, l = lgefint(a)-1;
     181       66684 :   if (uel(a,2)--)
     182             :   {
     183       66680 :     if (!a[l]) /* implies l = 2 */
     184             :     {
     185        1980 :       a[0] = evaltyp(t_INT) | _evallg(2);
     186        1980 :       a[1] = evalsigne(0) | evallgefint(2);
     187             :     }
     188       66680 :     return a;
     189             :   }
     190           5 :   for (i=3; i<=l; i++)
     191           5 :     if (uel(a,i)--) break;
     192           4 :   if (!a[l])
     193             :   {
     194           4 :     a[0] = evaltyp(t_INT) | _evallg(l);
     195           4 :     a[1] = evalsigne(-1) | evallgefint(l);
     196             :   }
     197           4 :   return a;
     198             : }
     199             : 
     200             : /* assume a initialized by setloop. Do a++ */
     201             : GEN
     202   103677842 : incloop(GEN a)
     203             : {
     204   103677842 :   switch(signe(a))
     205             :   {
     206      336632 :     case 0:
     207      336632 :       a[0]=evaltyp(t_INT) | _evallg(3);
     208      336632 :       a[1]=evalsigne(1) | evallgefint(3);
     209      336632 :       a[2]=1; return a;
     210       66684 :     case -1: return incneg(a);
     211   103274526 :     default: return incpos(a);
     212             :   }
     213             : }
     214             : 
     215             : INLINE GEN
     216  2790867419 : adduispec(ulong s, GEN x, long nx)
     217             : {
     218             :   GEN  zd;
     219             :   long lz;
     220             : 
     221  2790867419 :   if (nx == 1) return adduu(uel(x,0), s);
     222   901352180 :   lz = nx+3; zd = cgeti(lz);
     223   904289062 :   if (mpn_add_1(LIMBS(zd),(mp_limb_t *)x,nx,s))
     224     5022236 :     zd[lz-1]=1;
     225             :   else
     226   899285876 :     lz--;
     227   904308112 :   zd[1] = evalsigne(1) | evallgefint(lz);
     228   904308112 :   return zd;
     229             : }
     230             : 
     231             : GEN
     232   766958890 : adduispec_offset(ulong s, GEN x, long offset, long nx)
     233             : {
     234   766958890 :   GEN xd=x+2+offset;
     235   998698280 :   while (nx && *(xd+nx-1)==0) nx--;
     236   766958890 :   if (!nx) return utoi(s);
     237   722245650 :   return adduispec(s,xd,nx);
     238             : }
     239             : 
     240             : INLINE GEN
     241  3334947238 : addiispec(GEN x, GEN y, long nx, long ny)
     242             : {
     243             :   GEN zd;
     244             :   long lz;
     245             : 
     246  3334947238 :   if (nx < ny) swapspec(x,y, nx,ny);
     247  3334947238 :   if (ny == 1) return adduispec(*y,x,nx);
     248  1356124528 :   lz = nx+3; zd = cgeti(lz);
     249             : 
     250  1356150827 :   if (mpn_add(LIMBS(zd),(mp_limb_t *)x,nx,(mp_limb_t *)y,ny))
     251    30430131 :     zd[lz-1]=1;
     252             :   else
     253  1326011359 :     lz--;
     254             : 
     255  1356441490 :   zd[1] = evalsigne(1) | evallgefint(lz);
     256  1356441490 :   return zd;
     257             : }
     258             : 
     259             : /* assume x >= y */
     260             : INLINE GEN
     261  1777286595 : subiuspec(GEN x, ulong s, long nx)
     262             : {
     263             :   GEN zd;
     264             :   long lz;
     265             : 
     266  1777286595 :   if (nx == 1) return utoi(x[0] - s);
     267             : 
     268   251654147 :   lz = nx + 2; zd = cgeti(lz);
     269   252125019 :   mpn_sub_1 (LIMBS(zd), (mp_limb_t *)x, nx, s);
     270   252125666 :   if (! zd[lz - 1]) { --lz; }
     271             : 
     272   252125666 :   zd[1] = evalsigne(1) | evallgefint(lz);
     273   252125666 :   return zd;
     274             : }
     275             : 
     276             : /* assume x > y */
     277             : INLINE GEN
     278  3019266990 : subiispec(GEN x, GEN y, long nx, long ny)
     279             : {
     280             :   GEN zd;
     281             :   long lz;
     282  3019266990 :   if (ny==1) return subiuspec(x,*y,nx);
     283  1272140979 :   lz = nx+2; zd = cgeti(lz);
     284             : 
     285  1269683864 :   mpn_sub (LIMBS(zd), (mp_limb_t *)x, nx, (mp_limb_t *)y, ny);
     286  1756442849 :   while (lz >= 3 && zd[lz - 1] == 0) { lz--; }
     287             : 
     288  1269973757 :   zd[1] = evalsigne(1) | evallgefint(lz);
     289  1269973757 :   return zd;
     290             : }
     291             : 
     292             : static void
     293   527211054 : roundr_up_ip(GEN x, long l)
     294             : {
     295   527211054 :   long i = l;
     296             :   for(;;)
     297             :   {
     298   529003727 :     if (++((ulong*)x)[--i]) break;
     299     2190444 :     if (i == 2) { x[2] = HIGHBIT; shiftr_inplace(x, 1); break; }
     300             :   }
     301   527256209 : }
     302             : 
     303             : void
     304   403728298 : affir(GEN x, GEN y)
     305             : {
     306   403728298 :   const long s = signe(x), ly = lg(y);
     307             :   long lx, sh, i;
     308             : 
     309   403728298 :   if (!s)
     310             :   {
     311    42166574 :     y[1] = evalexpo(-bit_accuracy(ly));
     312    42163127 :     return;
     313             :   }
     314   361561724 :   lx = lgefint(x); sh = bfffo(*int_MSW(x));
     315   361561724 :   y[1] = evalsigne(s) | evalexpo(bit_accuracy(lx)-sh-1);
     316   361782271 :   if (sh) {
     317   354130923 :     if (lx <= ly)
     318             :     {
     319   961124673 :       for (i=lx; i<ly; i++) y[i]=0;
     320   249206465 :       mpn_lshift(LIMBS(y),LIMBS(x),lx-2,sh);
     321   249321738 :       xmpn_mirror(LIMBS(y),lx-2);
     322   249682580 :       return;
     323             :     }
     324   104924458 :     mpn_lshift(LIMBS(y),LIMBS(x)+lx-ly,ly-2,sh);
     325   104925476 :     uel(y,2) |= uel(x,lx-ly+1) >> (BITS_IN_LONG-sh);
     326   104925476 :     xmpn_mirror(LIMBS(y),ly-2);
     327             :     /* lx > ly: round properly */
     328   104926940 :     if ((uel(x,lx-ly+1)<<sh) & HIGHBIT) roundr_up_ip(y, ly);
     329             :   }
     330             :   else {
     331     7651348 :     GEN xd=int_MSW(x);
     332     7651348 :     if (lx <= ly)
     333             :     {
     334     9515885 :       for (i=2; i<lx; i++,xd=int_precW(xd)) y[i]=*xd;
     335     5236291 :       for (   ; i<ly; i++) y[i]=0;
     336     2363056 :       return;
     337             :     }
     338    15117295 :     for (i=2; i<ly; i++,xd=int_precW(xd)) y[i]=*xd;
     339             :     /* lx > ly: round properly */
     340     5288292 :     if (uel(x,lx-ly+1) & HIGHBIT) roundr_up_ip(y, ly);
     341             :   }
     342             : }
     343             : 
     344             : INLINE GEN
     345   714627016 : shiftispec(GEN x, long nx, long n)
     346             : {
     347             :   long ny,m;
     348             :   GEN yd, y;
     349             : 
     350   714627016 :   if (!n) return icopyspec(x, nx);
     351             : 
     352   685334032 :   if (n > 0)
     353             :   {
     354   399639034 :     long d = dvmdsBIL(n, &m);
     355             :     long i;
     356             : 
     357   399479023 :     ny = nx + d + (m!=0);
     358   399479023 :     y = cgeti(ny + 2); yd = y + 2;
     359   553205489 :     for (i=0; i<d; i++) yd[i] = 0;
     360             : 
     361   398571687 :     if (!m) xmpn_copy((mp_limb_t *) (yd + d), (mp_limb_t *) x, nx);
     362             :     else
     363             :     {
     364   397029983 :       ulong carryd = mpn_lshift((mp_limb_t *) (yd + d), (mp_limb_t *) x, nx, m);
     365   397060469 :       if (carryd) yd[ny - 1] = carryd;
     366   373780989 :       else ny--;
     367             :     }
     368             :   }
     369             :   else
     370             :   {
     371   285694998 :     long d = dvmdsBIL(-n, &m);
     372             : 
     373   287503683 :     ny = nx - d;
     374   287503683 :     if (ny < 1) return gen_0;
     375   284495758 :     y = cgeti(ny + 2); yd = y + 2;
     376             : 
     377   284215209 :     if (!m) xmpn_copy((mp_limb_t *) yd, (mp_limb_t *) (x + d), nx - d);
     378             :     else
     379             :     {
     380   279551960 :       mpn_rshift((mp_limb_t *) yd, (mp_limb_t *) (x + d), nx - d, m);
     381   279564609 :       if (yd[ny - 1] == 0)
     382             :       {
     383    61014948 :         if (ny == 1) return gc_const((pari_sp)(yd + 1), gen_0);
     384    51399502 :         ny--;
     385             :       }
     386             :     }
     387             :   }
     388   671448032 :   y[1] = evalsigne(1)|evallgefint(ny + 2);
     389   671448032 :   return y;
     390             : }
     391             : 
     392             : GEN
     393   138184043 : mantissa2nr(GEN x, long n)
     394             : {
     395   138184043 :   long ly, i, m, s = signe(x), lx = lg(x);
     396             :   GEN y;
     397   138184043 :   if (!s) return gen_0;
     398   138182694 :   if (!n)
     399             :   {
     400    30682741 :     y = cgeti(lx);
     401    30679931 :     y[1] = evalsigne(s) | evallgefint(lx);
     402    30679931 :     xmpn_mirrorcopy(LIMBS(y),RLIMBS(x),lx-2);
     403    30679562 :     return y;
     404             :   }
     405   107499953 :   if (n > 0)
     406             :   {
     407      218419 :     GEN z = (GEN)avma;
     408      218419 :     long d = dvmdsBIL(n, &m);
     409             : 
     410      218419 :     ly = lx+d; y = new_chunk(ly);
     411      557533 :     for ( ; d; d--) *--z = 0;
     412      222851 :     if (!m) for (i=2; i<lx; i++) y[i]=x[i];
     413             :     else
     414             :     {
     415      216978 :       const ulong sh = BITS_IN_LONG - m;
     416      216978 :       shift_left(y,x, 2,lx-1, 0,m);
     417      216978 :       i = uel(x,2) >> sh;
     418             :       /* Extend y on the left? */
     419      216978 :       if (i) { ly++; y = new_chunk(1); y[2] = i; }
     420             :     }
     421             :   }
     422             :   else
     423             :   {
     424   107281534 :     ly = lx - dvmdsBIL(-n, &m);
     425   107274614 :     if (ly<3) return gen_0;
     426   107274614 :     y = new_chunk(ly);
     427   107238044 :     if (m) {
     428   106979611 :       shift_right(y,x, 2,ly, 0,m);
     429   107017071 :       if (y[2] == 0)
     430             :       {
     431           0 :         if (ly==3) return gc_const((pari_sp)(y+3), gen_0);
     432           0 :         ly--; set_avma((pari_sp)(++y));
     433             :       }
     434             :     } else {
     435      701608 :       for (i=2; i<ly; i++) y[i]=x[i];
     436             :     }
     437             :   }
     438   107493923 :   xmpn_mirror(LIMBS(y),ly-2);
     439   107541885 :   y[1] = evalsigne(s)|evallgefint(ly);
     440   107541885 :   y[0] = evaltyp(t_INT)|evallg(ly); return y;
     441             : }
     442             : 
     443             : GEN
     444     3625179 : truncr(GEN x)
     445             : {
     446             :   long s, e, d, m, i;
     447             :   GEN y;
     448     3625179 :   if ((s=signe(x)) == 0 || (e=expo(x)) < 0) return gen_0;
     449     1509997 :   d = nbits2lg(e+1); m = remsBIL(e);
     450     1509980 :   if (d > lg(x)) pari_err_PREC( "truncr (precision loss in truncation)");
     451             : 
     452     1509976 :   y=cgeti(d); y[1] = evalsigne(s) | evallgefint(d);
     453     1509896 :   if (++m == BITS_IN_LONG)
     454       95989 :     for (i=2; i<d; i++) y[d-i+1]=x[i];
     455             :   else
     456             :   {
     457     1462160 :     GEN z=cgeti(d);
     458     2990889 :     for (i=2; i<d; i++) z[d-i+1]=x[i];
     459     1462046 :     mpn_rshift(LIMBS(y),LIMBS(z),d-2,BITS_IN_LONG-m);
     460     1462048 :     set_avma((pari_sp)y);
     461             :   }
     462     1509768 :   return y;
     463             : }
     464             : 
     465             : /* integral part */
     466             : GEN
     467     7129823 : floorr(GEN x)
     468             : {
     469             :   long e, d, m, i, lx;
     470             :   GEN y;
     471     7129823 :   if (signe(x) >= 0) return truncr(x);
     472     4242333 :   if ((e=expo(x)) < 0) return gen_m1;
     473     3522983 :   d = nbits2lg(e+1); m = remsBIL(e);
     474     3520343 :   lx=lg(x); if (d>lx) pari_err_PREC( "floorr (precision loss in truncation)");
     475     3520343 :   y = cgeti(d+1);
     476     3510656 :   if (++m == BITS_IN_LONG)
     477             :   {
     478        3053 :     for (i=2; i<d; i++) y[d-i+1]=x[i];
     479        1450 :     i=d; while (i<lx && !x[i]) i++;
     480         906 :     if (i==lx) goto END;
     481             :   }
     482             :   else
     483             :   {
     484     3509750 :     GEN z=cgeti(d);
     485     7848751 :     for (i=2; i<d; i++) z[d-i+1]=x[i];
     486     3496250 :     mpn_rshift(LIMBS(y),LIMBS(z),d-2,BITS_IN_LONG-m);
     487     3496851 :     if (uel(x,d-1)<<m == 0)
     488             :     {
     489      521087 :       i=d; while (i<lx && !x[i]) i++;
     490      121242 :       if (i==lx) goto END;
     491             :     }
     492             :   }
     493     3419798 :   if (mpn_add_1(LIMBS(y),LIMBS(y),d-2,1))
     494           0 :     y[d++]=1;
     495     3419864 : END:
     496     3497823 :   y[1] = evalsigne(-1) | evallgefint(d);
     497     3497823 :   return y;
     498             : }
     499             : 
     500             : INLINE int
     501  3973424941 : cmpiispec(GEN x, GEN y, long lx, long ly)
     502             : {
     503  3973424941 :   if (lx < ly) return -1;
     504  3652973188 :   if (lx > ly) return  1;
     505  3503228134 :   return mpn_cmp((mp_limb_t*)x,(mp_limb_t*)y, lx);
     506             : }
     507             : 
     508             : INLINE int
     509   269581924 : equaliispec(GEN x, GEN y, long lx, long ly)
     510             : {
     511   269581924 :   if (lx != ly) return 0;
     512   269440704 :   return !mpn_cmp((mp_limb_t*)x,(mp_limb_t*)y, lx);
     513             : }
     514             : 
     515             : /***********************************************************************/
     516             : /**                                                                   **/
     517             : /**                          MULTIPLICATION                           **/
     518             : /**                                                                   **/
     519             : /***********************************************************************/
     520             : /* assume ny > 0 */
     521             : INLINE GEN
     522  5617986939 : muluispec(ulong x, GEN y, long ny)
     523             : {
     524  5617986939 :   if (ny == 1)
     525  4520312683 :     return muluu(x, *y);
     526             :   else
     527             :   {
     528  1097674256 :     long lz = ny+3;
     529  1097674256 :     GEN z = cgeti(lz);
     530  1106848648 :     ulong hi = mpn_mul_1 (LIMBS(z), (mp_limb_t *)y, ny, x);
     531  1108175317 :     if (hi) { z[lz - 1] = hi; } else lz--;
     532  1108175317 :     z[1] = evalsigne(1) | evallgefint(lz);
     533  1108175317 :     return z;
     534             :   }
     535             : }
     536             : 
     537             : /* a + b*|y| */
     538             : GEN
     539           0 : addumului(ulong a, ulong b, GEN y)
     540             : {
     541             :   GEN z;
     542             :   long i, lz;
     543             :   ulong hi;
     544           0 :   if (!b || !signe(y)) return utoi(a);
     545           0 :   lz = lgefint(y)+1;
     546           0 :   z = cgeti(lz);
     547           0 :   z[2]=a;
     548           0 :   for(i=3;i<lz;i++) z[i]=0;
     549           0 :   hi=mpn_addmul_1(LIMBS(z), LIMBS(y), NLIMBS(y), b);
     550           0 :   if (hi) z[lz-1]=hi; else lz--;
     551           0 :   z[1] = evalsigne(1) | evallgefint(lz);
     552           0 :   return gc_const((pari_sp)z, z);
     553             : }
     554             : 
     555             : /***********************************************************************/
     556             : /**                                                                   **/
     557             : /**                          DIVISION                                 **/
     558             : /**                                                                   **/
     559             : /***********************************************************************/
     560             : 
     561             : ulong
     562  1316254554 : umodiu(GEN y, ulong x)
     563             : {
     564  1316254554 :   long sy=signe(y);
     565             :   ulong hi;
     566  1316254554 :   if (!x) pari_err_INV("umodiu",gen_0);
     567  1317263374 :   if (!sy) return 0;
     568   908487030 :   hi = mpn_mod_1(LIMBS(y),NLIMBS(y),x);
     569   908487030 :   if (!hi) return 0;
     570   891931812 :   return (sy > 0)? hi: x - hi;
     571             : }
     572             : 
     573             : /* return |y| \/ x */
     574             : GEN
     575   110780051 : absdiviu_rem(GEN y, ulong x, ulong *rem)
     576             : {
     577             :   long ly;
     578             :   GEN z;
     579             : 
     580   110780051 :   if (!x) pari_err_INV("absdiviu_rem",gen_0);
     581   110785953 :   if (!signe(y)) { *rem = 0; return gen_0; }
     582             : 
     583    83853976 :   ly = lgefint(y);
     584    83853976 :   if (ly == 3 && (ulong)x > uel(y,2)) { *rem = uel(y,2); return gen_0; }
     585             : 
     586    69152790 :   z = cgeti(ly);
     587    69152754 :   *rem = mpn_divrem_1(LIMBS(z), 0, LIMBS(y), NLIMBS(y), x);
     588    69152660 :   if (z [ly - 1] == 0) ly--;
     589    69152660 :   z[1] = evallgefint(ly) | evalsigne(1);
     590    69152660 :   return z;
     591             : }
     592             : 
     593             : GEN
     594    86174758 : divis_rem(GEN y, long x, long *rem)
     595             : {
     596    86174758 :   long sy=signe(y),ly,s;
     597             :   GEN z;
     598             : 
     599    86174758 :   if (!x) pari_err_INV("divis_rem",gen_0);
     600    86185494 :   if (!sy) { *rem = 0; return gen_0; }
     601    60359087 :   if (x<0) { s = -sy; x = -x; } else s = sy;
     602             : 
     603    60359087 :   ly = lgefint(y);
     604    60359087 :   if (ly == 3 && (ulong)x > uel(y,2)) { *rem = itos(y); return gen_0; }
     605             : 
     606    41571920 :   z = cgeti(ly);
     607    41568175 :   *rem = mpn_divrem_1(LIMBS(z), 0, LIMBS(y), NLIMBS(y), x);
     608    41568355 :   if (sy<0) *rem = -  *rem;
     609    41568355 :   if (z[ly - 1] == 0) ly--;
     610    41568355 :   z[1] = evallgefint(ly) | evalsigne(s);
     611    41568355 :   return z;
     612             : }
     613             : 
     614             : GEN
     615     1006038 : divis(GEN y, long x)
     616             : {
     617     1006038 :   long sy=signe(y),ly,s;
     618             :   GEN z;
     619             : 
     620     1006038 :   if (!x) pari_err_INV("divis",gen_0);
     621     1006038 :   if (!sy) return gen_0;
     622     1005990 :   if (x<0) { s = -sy; x = -x; } else s=sy;
     623             : 
     624     1005990 :   ly = lgefint(y);
     625     1005990 :   if (ly == 3 && (ulong)x > uel(y,2)) return gen_0;
     626             : 
     627     1005678 :   z = cgeti(ly);
     628     1005675 :   (void)mpn_divrem_1(LIMBS(z), 0, LIMBS(y), NLIMBS(y), x);
     629     1005675 :   if (z[ly - 1] == 0) ly--;
     630     1005675 :   z[1] = evallgefint(ly) | evalsigne(s);
     631     1005675 :   return z;
     632             : }
     633             : 
     634             : /* We keep llx bits of x and lly bits of y*/
     635             : static GEN
     636    76129490 : divrr_with_gmp(GEN x, GEN y)
     637             : {
     638    76129490 :   long lx=RNLIMBS(x),ly=RNLIMBS(y);
     639    76129490 :   long lw=minss(lx,ly);
     640    76130613 :   long lly=minss(lw+1,ly);
     641    76131788 :   GEN  w = cgetg(lw+2, t_REAL);
     642    76113842 :   long lu=lw+lly;
     643    76113842 :   long llx=minss(lu,lx);
     644    76110894 :   mp_limb_t *u=(mp_limb_t *)new_chunk(lu);
     645    76090274 :   mp_limb_t *z=(mp_limb_t *)new_chunk(lly);
     646             :   mp_limb_t *q,*r;
     647    76059188 :   long e=expo(x)-expo(y);
     648    76059188 :   long sx=signe(x),sy=signe(y);
     649    76059188 :   xmpn_mirrorcopy(z,RLIMBS(y),lly);
     650    76074396 :   xmpn_mirrorcopy(u+lu-llx,RLIMBS(x),llx);
     651    76121178 :   xmpn_zero(u,lu-llx);
     652    76149056 :   q = (mp_limb_t *)new_chunk(lw+1);
     653    76132658 :   r = (mp_limb_t *)new_chunk(lly);
     654             : 
     655    76109753 :   mpn_tdiv_qr(q,r,0,u,lu,z,lly);
     656             : 
     657             :   /*Round up: This is not exactly correct we should test 2*r>z*/
     658    76158057 :   if (uel(r,lly-1) > (uel(z,lly-1)>>1))
     659    37774622 :     mpn_add_1(q,q,lw+1,1);
     660             : 
     661    76158214 :   xmpn_mirrorcopy(RLIMBS(w),q,lw);
     662             : 
     663    76156570 :   if (q[lw] == 0) e--;
     664    42025040 :   else if (q[lw] == 1) { shift_right(w,w, 2,lw+2, 1,1); }
     665           0 :   else { w[2] = HIGHBIT; e++; }
     666    76155283 :   if (sy < 0) sx = -sx;
     667    76155283 :   w[1] = evalsigne(sx) | evalexpo(e);
     668    76149454 :   return gc_const((pari_sp)w, w);
     669             : }
     670             : 
     671             : /* We keep llx bits of x and lly bits of y*/
     672             : static GEN
     673    35250567 : divri_with_gmp(GEN x, GEN y)
     674             : {
     675    35250567 :   long llx=RNLIMBS(x),ly=NLIMBS(y);
     676    35250567 :   long lly=minss(llx+1,ly);
     677    35250970 :   GEN  w = cgetg(llx+2, t_REAL);
     678    35246657 :   long lu=llx+lly, ld=ly-lly;
     679    35246657 :   mp_limb_t *u=(mp_limb_t *)new_chunk(lu);
     680    35243032 :   mp_limb_t *z=(mp_limb_t *)new_chunk(lly);
     681             :   mp_limb_t *q,*r;
     682    35237526 :   long sh=bfffo(y[ly+1]);
     683    35237526 :   long e=expo(x)-expi(y);
     684    35238136 :   long sx=signe(x),sy=signe(y);
     685    35238136 :   if (sh) mpn_lshift(z,LIMBS(y)+ld,lly,sh);
     686      685150 :   else xmpn_copy(z,LIMBS(y)+ld,lly);
     687    35239796 :   xmpn_mirrorcopy(u+lu-llx,RLIMBS(x),llx);
     688    35247120 :   xmpn_zero(u,lu-llx);
     689    35253013 :   q = (mp_limb_t *)new_chunk(llx+1);
     690    35251200 :   r = (mp_limb_t *)new_chunk(lly);
     691             : 
     692    35246659 :   mpn_tdiv_qr(q,r,0,u,lu,z,lly);
     693             : 
     694             :   /*Round up: This is not exactly correct we should test 2*r>z*/
     695    35256103 :   if (uel(r,lly-1) > (uel(z,lly-1)>>1))
     696    16045035 :     mpn_add_1(q,q,llx+1,1);
     697             : 
     698    35256111 :   xmpn_mirrorcopy(RLIMBS(w),q,llx);
     699             : 
     700    35255787 :   if (q[llx] == 0) e--;
     701    10628273 :   else if (q[llx] == 1) { shift_right(w,w, 2,llx+2, 1,1); }
     702           0 :   else { w[2] = HIGHBIT; e++; }
     703    35255636 :   if (sy < 0) sx = -sx;
     704    35255636 :   w[1] = evalsigne(sx) | evalexpo(e);
     705    35254586 :   return gc_const((pari_sp)w, w);
     706             : }
     707             : 
     708             : GEN
     709   151394749 : divri(GEN x, GEN y)
     710             : {
     711   151394749 :   long  s = signe(y);
     712             : 
     713   151394749 :   if (!s) pari_err_INV("divri",gen_0);
     714   151394898 :   if (!signe(x)) return real_0_bit(expo(x) - expi(y));
     715   151158322 :   if (!is_bigint(y)) {
     716   115913873 :     GEN z = divru(x, y[2]);
     717   115912453 :     if (s < 0) togglesign(z);
     718   115912468 :     return z;
     719             :   }
     720    35243827 :   return divri_with_gmp(x,y);
     721             : }
     722             : 
     723             : GEN
     724   142753561 : divrr(GEN x, GEN y)
     725             : {
     726   142753561 :   long sx=signe(x), sy=signe(y), lx,ly,lr,e,i,j;
     727             :   ulong y0,y1;
     728             :   GEN r, r1;
     729             : 
     730   142753561 :   if (!sy) pari_err_INV("divrr",y);
     731   142763464 :   e = expo(x) - expo(y);
     732   142763464 :   if (!sx) return real_0_bit(e);
     733   142257304 :   if (sy<0) sx = -sx;
     734             : 
     735   142257304 :   lx=lg(x); ly=lg(y);
     736   142257304 :   if (ly==3)
     737             :   {
     738    26334251 :     ulong k = x[2], l = (lx>3)? x[3]: 0;
     739             :     LOCAL_HIREMAINDER;
     740    26334251 :     if (k < uel(y,2)) e--;
     741             :     else
     742             :     {
     743     8290301 :       l >>= 1; if (k&1) l |= HIGHBIT;
     744     8290301 :       k >>= 1;
     745             :     }
     746    26334251 :     hiremainder = k; k = divll(l,y[2]);
     747    26334251 :     if (hiremainder > (uel(y,2) >> 1) && !++k) { k = HIGHBIT; e++; }
     748    26334251 :     r = cgetg(3, t_REAL);
     749    26335892 :     r[1] = evalsigne(sx) | evalexpo(e);
     750    26333590 :     r[2] = k; return r;
     751             :   }
     752             : 
     753   115923053 :   if (ly >= prec2lg(DIVRR_GMP_LIMIT))
     754    76129204 :     return divrr_with_gmp(x,y);
     755             : 
     756    39844877 :   lr = minss(lx,ly); r = new_chunk(lr);
     757    39852811 :   r1 = r-1;
     758   135485078 :   r1[1] = 0; for (i=2; i<lr; i++) r1[i]=x[i];
     759    39852811 :   r1[lr] = (lx>ly)? x[lr]: 0;
     760    39852811 :   y0 = y[2]; y1 = y[3];
     761   175292698 :   for (i=0; i<lr-1; i++)
     762             :   { /* r1 = r + (i-1), OK up to r1[2] (accesses at most r[lr]) */
     763             :     ulong k, qp;
     764             :     LOCAL_HIREMAINDER;
     765             :     LOCAL_OVERFLOW;
     766             : 
     767   135439887 :     if (uel(r1,1) == y0) { qp = ULONG_MAX; k = addll(y0,r1[2]); }
     768             :     else
     769             :     {
     770   135186882 :       if (uel(r1,1) > y0) /* can't happen if i=0 */
     771             :       {
     772           0 :         GEN y1 = y+1;
     773           0 :         j = lr-i; r1[j] = subll(r1[j],y1[j]);
     774           0 :         for (j--; j>0; j--) r1[j] = subllx(r1[j],y1[j]);
     775           0 :         j=i; do uel(r,--j)++; while (j && !r[j]);
     776             :       }
     777   135186882 :       hiremainder = r1[1]; overflow = 0;
     778   135186882 :       qp = divll(r1[2],y0); k = hiremainder;
     779             :     }
     780   135439887 :     j = lr-i+1;
     781   135439887 :     if (!overflow)
     782             :     {
     783             :       long k3, k4;
     784   135289496 :       k3 = mulll(qp,y1);
     785   135289496 :       if (j == 3) /* i = lr - 2 maximal, r1[3] undefined -> 0 */
     786    39905782 :         k4 = subll(hiremainder,k);
     787             :       else
     788             :       {
     789    95383714 :         k3 = subll(k3, r1[3]);
     790    95383714 :         k4 = subllx(hiremainder,k);
     791             :       }
     792   173698667 :       while (!overflow && k4) { qp--; k3=subll(k3,y1); k4=subllx(k4,y0); }
     793             :     }
     794   135439887 :     if (j<ly) (void)mulll(qp,y[j]); else { hiremainder = 0 ; j = ly; }
     795   402115905 :     for (j--; j>1; j--)
     796             :     {
     797   266676018 :       r1[j] = subll(r1[j], addmul(qp,y[j]));
     798   266676018 :       hiremainder += overflow;
     799             :     }
     800   135439887 :     if (uel(r1,1) != hiremainder)
     801             :     {
     802      187473 :       if (uel(r1,1) < hiremainder)
     803             :       {
     804      187473 :         qp--;
     805      187473 :         j = lr-i-(lr-i>=ly); r1[j] = addll(r1[j], y[j]);
     806      534270 :         for (j--; j>1; j--) r1[j] = addllx(r1[j], y[j]);
     807             :       }
     808             :       else
     809             :       {
     810           0 :         uel(r1,1) -= hiremainder;
     811           0 :         while (r1[1])
     812             :         {
     813           0 :           qp++; if (!qp) { j=i; do uel(r,--j)++; while (j && !r[j]); }
     814           0 :           j = lr-i-(lr-i>=ly); r1[j] = subll(r1[j],y[j]);
     815           0 :           for (j--; j>1; j--) r1[j] = subllx(r1[j],y[j]);
     816           0 :           uel(r1,1) -= overflow;
     817             :         }
     818             :       }
     819             :     }
     820   135439887 :     *++r1 = qp;
     821             :   }
     822             :   /* i = lr-1 */
     823             :   /* round correctly */
     824    39852811 :   if (uel(r1,1) > (y0>>1))
     825             :   {
     826    20131018 :     j=i; do uel(r,--j)++; while (j && !r[j]);
     827             :   }
     828   135659870 :   r1 = r-1; for (j=i; j>=2; j--) r[j]=r1[j];
     829    39852811 :   if (r[0] == 0) e--;
     830    14282488 :   else if (r[0] == 1) { shift_right(r,r, 2,lr, 1,1); }
     831             :   else { /* possible only when rounding up to 0x2 0x0 ... */
     832          18 :     r[2] = (long)HIGHBIT; e++;
     833             :   }
     834    39851474 :   r[0] = evaltyp(t_REAL)|evallg(lr);
     835    39905694 :   r[1] = evalsigne(sx) | evalexpo(e);
     836    39897903 :   return r;
     837             : }
     838             : 
     839             : /* Integer division x / y: such that sign(r) = sign(x)
     840             :  *   if z = ONLY_REM return remainder, otherwise return quotient
     841             :  *   if z != NULL set *z to remainder
     842             :  *   *z is the last object on stack and can be disposed of with cgiv
     843             :  * If *z is zero, we put gen_0 here and no copy.
     844             :  * space needed: lx + ly
     845             :  */
     846             : GEN
     847  2196813736 : dvmdii(GEN x, GEN y, GEN *z)
     848             : {
     849  2196813736 :   long sx=signe(x),sy=signe(y);
     850             :   long lx, ly, lq;
     851             :   pari_sp av;
     852             :   GEN r,q;
     853             : 
     854  2196813736 :   if (!sy) pari_err_INV("dvmdii",y);
     855  2197904944 :   if (!sx)
     856             :   {
     857    69914999 :     if (!z || z == ONLY_REM) return gen_0;
     858    41102639 :     *z=gen_0; return gen_0;
     859             :   }
     860  2127989945 :   lx=lgefint(x);
     861  2127989945 :   ly=lgefint(y); lq=lx-ly;
     862  2127989945 :   if (lq <= 0)
     863             :   {
     864  1261728781 :     if (lq == 0)
     865             :     {
     866  1073267502 :       long s=mpn_cmp(LIMBS(x),LIMBS(y),NLIMBS(x));
     867  1073267502 :       if (s>0) goto DIVIDE;
     868   369761509 :       if (s==0)
     869             :       {
     870    33466810 :         if (z == ONLY_REM) return gen_0;
     871    22327251 :         if (z) *z = gen_0;
     872    22327251 :         if (sx < 0) sy = -sy;
     873    22327251 :         return stoi(sy);
     874             :       }
     875             :     }
     876   524755978 :     if (z == ONLY_REM) return icopy(x);
     877    14332338 :     if (z) *z = icopy(x);
     878    14332338 :     return gen_0;
     879             :   }
     880   866261164 : DIVIDE: /* quotient is nonzero */
     881  1569767157 :   av=avma; if (sx<0) sy = -sy;
     882  1569767157 :   if (ly==3)
     883             :   {
     884   575399310 :     ulong lq = lx;
     885             :     ulong si;
     886   575399310 :     q  = cgeti(lq);
     887   574979921 :     si = mpn_divrem_1(LIMBS(q), 0, LIMBS(x), NLIMBS(x), y[2]);
     888   575534196 :     if (q[lq - 1] == 0) lq--;
     889   575534196 :     if (z == ONLY_REM)
     890             :     {
     891   335398842 :       if (!si) return gc_const(av, gen_0);
     892   289040244 :       set_avma(av); r = cgeti(3);
     893   288554445 :       r[1] = evalsigne(sx) | evallgefint(3);
     894   288554445 :       r[2] = si; return r;
     895             :     }
     896   240135354 :     q[1] = evalsigne(sy) | evallgefint(lq);
     897   240135354 :     if (!z) return q;
     898   236030910 :     if (!si) { *z=gen_0; return q; }
     899    64202423 :     r=cgeti(3);
     900    64226835 :     r[1] = evalsigne(sx) | evallgefint(3);
     901    64226835 :     r[2] = si; *z=r; return q;
     902             :   }
     903   994367847 :   if (z == ONLY_REM)
     904             :   {
     905   970789494 :     ulong lr = lgefint(y);
     906   970789494 :     ulong lq = lgefint(x)-lgefint(y)+3;
     907   970789494 :     GEN r = cgeti(lr);
     908   964604551 :     GEN q = cgeti(lq);
     909   957833801 :     mpn_tdiv_qr(LIMBS(q), LIMBS(r),0, LIMBS(x), NLIMBS(x), LIMBS(y), NLIMBS(y));
     910   972546993 :     if (!r[lr - 1])
     911             :     {
     912  1182417942 :       while(lr>2 && !r[lr - 1]) lr--;
     913   545339525 :       if (lr == 2) return gc_const(av, gen_0); /* exact division */
     914             :     }
     915   957613116 :     r[1] = evalsigne(sx) | evallgefint(lr);
     916   957613116 :     return gc_const((pari_sp)r, r);
     917             :   }
     918             :   else
     919             :   {
     920    23578353 :     ulong lq = lgefint(x)-lgefint(y)+3;
     921    23578353 :     ulong lr = lgefint(y);
     922    23578353 :     GEN q = cgeti(lq);
     923    28646689 :     GEN r = cgeti(lr);
     924    28632567 :     mpn_tdiv_qr(LIMBS(q), LIMBS(r),0, LIMBS(x), NLIMBS(x), LIMBS(y), NLIMBS(y));
     925    28661475 :     if (q[lq - 1] == 0) lq--;
     926    28661475 :     q[1] = evalsigne(sy) | evallgefint(lq);
     927    28661475 :     if (!z) return gc_const((pari_sp)q, q);
     928    24957590 :     if (!r[lr - 1])
     929             :     {
     930    38547882 :       while(lr>2 && !r[lr - 1]) lr--;
     931     6353993 :       if (lr == 2) { *z = gen_0; return gc_const((pari_sp)q, q); } /* exact */
     932             :     }
     933    20165831 :     r[1] = evalsigne(sx) | evallgefint(lr);
     934    20165831 :     *z = gc_const((pari_sp)r, r); return q;
     935             :   }
     936             : }
     937             : 
     938             : /* Montgomery reduction.
     939             :  * N has k words, assume T >= 0 has less than 2k.
     940             :  * Return res := T / B^k mod N, where B = 2^BIL
     941             :  * such that 0 <= res < T/B^k + N  and  res has less than k words */
     942             : GEN
     943    34944635 : red_montgomery(GEN T, GEN N, ulong inv)
     944             : {
     945             :   pari_sp av;
     946             :   GEN Te, Td, Ne, Nd, scratch;
     947    34944635 :   ulong i, j, m, t, d, k = NLIMBS(N);
     948             :   int carry;
     949             :   LOCAL_HIREMAINDER;
     950             :   LOCAL_OVERFLOW;
     951             : 
     952    34944635 :   if (k == 0) return gen_0;
     953    34944635 :   d = NLIMBS(T); /* <= 2*k */
     954    34944635 :   if (d == 0) return gen_0;
     955             : #ifdef DEBUG
     956             :   if (d > 2*k) pari_err_BUG("red_montgomery");
     957             : #endif
     958    34944626 :   if (k == 1)
     959             :   { /* as below, special cased for efficiency */
     960      163341 :     ulong n = uel(N,2);
     961      163341 :     if (d == 1) {
     962      163194 :       hiremainder = uel(T,2);
     963      163194 :       m = hiremainder * inv;
     964      163194 :       (void)addmul(m, n); /* t + m*n = 0 */
     965      163194 :       return utoi(hiremainder);
     966             :     } else { /* d = 2 */
     967         147 :       hiremainder = uel(T,2);
     968         147 :       m = hiremainder * inv;
     969         147 :       (void)addmul(m, n); /* t + m*n = 0 */
     970         147 :       t = addll(hiremainder, uel(T,3));
     971         147 :       if (overflow) t -= n; /* t > n doesn't fit in 1 word */
     972         147 :       return utoi(t);
     973             :     }
     974             :   }
     975             :   /* assume k >= 2 */
     976    34781285 :   av = avma; scratch = new_chunk(k<<1); /* >= k + 2: result fits */
     977             : 
     978             :   /* copy T to scratch space (pad with zeroes to 2k words) */
     979    34420628 :   Td = scratch;
     980    34420628 :   Te = T + 2;
     981   481429735 :   for (i=0; i < d     ; i++) *Td++ = *Te++;
     982    61588276 :   for (   ; i < (k<<1); i++) *Td++ = 0;
     983             : 
     984    34420628 :   Te = scratch - 1; /* 1 beyond end of current T mantissa (in scratch) */
     985    34420628 :   Ne = N + 1;       /* 1 beyond end of N mantissa */
     986             : 
     987    34420628 :   carry = 0;
     988   257400322 :   for (i=0; i<k; i++) /* set T := T/B nod N, k times */
     989             :   {
     990   222979694 :     Td = Te; /* one beyond end of (new) T mantissa */
     991   222979694 :     Nd = Ne;
     992   222979694 :     hiremainder = *++Td;
     993   222979694 :     m = hiremainder * inv; /* solve T + m N = O(B) */
     994             : 
     995             :     /* set T := (T + mN) / B */
     996   222979694 :     Te = Td;
     997   222979694 :     (void)addmul(m, *++Nd); /* = 0 */
     998  1934569610 :     for (j=1; j<k; j++)
     999             :     {
    1000  1711589916 :       t = addll(addmul(m, *++Nd), *++Td);
    1001  1711589916 :       *Td = t;
    1002  1711589916 :       hiremainder += overflow;
    1003             :     }
    1004   222979694 :     t = addll(hiremainder, *++Td); *Td = t + carry;
    1005   222979694 :     carry = (overflow || (carry && *Td == 0));
    1006             :   }
    1007    34420628 :   if (carry)
    1008             :   { /* Td > N overflows (k+1 words), set Td := Td - N */
    1009       76453 :     GEN NE = N + k+1;
    1010       76453 :     Td = Te;
    1011       76453 :     Nd = Ne;
    1012       76453 :     t = subll(*++Td, *++Nd); *Td = t;
    1013      770743 :     while (Nd < NE) { t = subllx(*++Td, *++Nd); *Td = t; }
    1014             :   }
    1015             : 
    1016             :   /* copy result */
    1017    34420628 :   Td = (GEN)av - 1; /* *Td = high word of final result */
    1018    38031333 :   while (*Td == 0 && Te < Td) Td--; /* strip leading 0s */
    1019    34420628 :   k = Td - Te; if (!k) return gc_const(av, gen_0);
    1020    34420628 :   Td = (GEN)av - k; /* will write mantissa there */
    1021    34420628 :   (void)memmove(Td, Te+1, k*sizeof(long));
    1022    34420628 :   Td -= 2;
    1023    34420628 :   Td[0] = evaltyp(t_INT) | evallg(k+2);
    1024    34820274 :   Td[1] = evalsigne(1) | evallgefint(k+2);
    1025             : #ifdef DEBUG
    1026             : {
    1027             :   long l = NLIMBS(N), s = BITS_IN_LONG*l;
    1028             :   GEN R = int2n(s);
    1029             :   GEN res = remii(mulii(T, Fp_inv(R, N)), N);
    1030             :   if (k > lgefint(N)
    1031             :     || !equalii(remii(Td,N),res)
    1032             :     || cmpii(Td, addii(shifti(T, -s), N)) >= 0) pari_err_BUG("red_montgomery");
    1033             : }
    1034             : #endif
    1035    34820274 :   return gc_const((pari_sp)Td, Td);
    1036             : }
    1037             : 
    1038             : /* EXACT INTEGER DIVISION */
    1039             : 
    1040             : /* use undocumented GMP interface */
    1041             : static void
    1042   115387756 : GEN2mpz(mpz_t X, GEN x)
    1043             : {
    1044   115387756 :   long l = lgefint(x)-2;
    1045   115387756 :   X->_mp_alloc = l;
    1046   115387756 :   X->_mp_size = signe(x) > 0? l: -l;
    1047   115387756 :   X->_mp_d = LIMBS(x);
    1048   115387756 : }
    1049             : static void
    1050    57695062 : mpz2GEN(GEN z, mpz_t Z)
    1051             : {
    1052    57695062 :   long l = Z->_mp_size;
    1053    57695062 :   z[1] = evalsigne(l > 0? 1: -1) | evallgefint(labs(l)+2);
    1054    57695062 : }
    1055             : 
    1056             : #ifdef mpn_divexact_1
    1057             : static GEN
    1058   420962611 : diviuexact_i(GEN x, ulong y)
    1059             : {
    1060   420962611 :   long l = lgefint(x);
    1061   420962611 :   GEN z = cgeti(l);
    1062   420523373 :   mpn_divexact_1(LIMBS(z), LIMBS(x), NLIMBS(x), y);
    1063   420579624 :   if (z[l-1] == 0) l--;
    1064   420579624 :   z[1] = evallgefint(l) | evalsigne(signe(x));
    1065   420579624 :   return z;
    1066             : }
    1067             : #elif 1 && !defined(_WIN64) /* mpz_divexact_ui is not LLP64 friendly   */
    1068             :                             /* assume y != 0 and the division is exact */
    1069             : static GEN
    1070             : diviuexact_i(GEN x, ulong y)
    1071             : {
    1072             :   long l = lgefint(x);
    1073             :   GEN z = cgeti(l);
    1074             :   mpz_t X, Z;
    1075             :   GEN2mpz(X, x);
    1076             :   Z->_mp_alloc = l-2;
    1077             :   Z->_mp_size  = l-2;
    1078             :   Z->_mp_d = LIMBS(z);
    1079             :   mpz_divexact_ui(Z, X, y);
    1080             :   mpz2GEN(z, Z); return z;
    1081             : }
    1082             : #else
    1083             : /* assume y != 0 and the division is exact */
    1084             : static GEN
    1085             : diviuexact_i(GEN x, ulong y)
    1086             : {
    1087             :   /*TODO: implement true exact division.*/
    1088             :   return divii(x,utoi(y));
    1089             : }
    1090             : #endif
    1091             : 
    1092             : GEN
    1093    39415959 : diviuexact(GEN x, ulong y)
    1094             : {
    1095             :   GEN z;
    1096    39415959 :   if (!signe(x)) return gen_0;
    1097    38287383 :   z = diviuexact_i(x, y);
    1098    38285793 :   if (lgefint(z) == 2) pari_err_OP("exact division", x, utoi(y));
    1099    38285881 :   return z;
    1100             : }
    1101             : 
    1102             : /* Find z such that x=y*z, knowing that y | x (unchecked) */
    1103             : GEN
    1104   533599355 : diviiexact(GEN x, GEN y)
    1105             : {
    1106             :   GEN z;
    1107   533599355 :   if (!signe(y)) pari_err_INV("diviiexact",y);
    1108   533765590 :   if (!signe(x)) return gen_0;
    1109   440542546 :   if (lgefint(y) == 3)
    1110             :   {
    1111   382867290 :     z = diviuexact_i(x, y[2]);
    1112   382478647 :     if (signe(y) < 0) togglesign(z);
    1113             :   }
    1114             :   else
    1115             :   {
    1116    57675256 :     long l = lgefint(x);
    1117             :     mpz_t X, Y, Z;
    1118    57675256 :     z = cgeti(l);
    1119    57694031 :     GEN2mpz(X, x);
    1120    57693957 :     GEN2mpz(Y, y);
    1121    57693839 :     Z->_mp_alloc = l-2;
    1122    57693839 :     Z->_mp_size  = l-2;
    1123    57693839 :     Z->_mp_d = LIMBS(z);
    1124    57693839 :     mpz_divexact(Z, X, Y);
    1125    57695086 :     mpz2GEN(z, Z);
    1126             :   }
    1127   440173683 :   if (lgefint(z) == 2) pari_err_OP("exact division", x, y);
    1128   440154291 :   return z;
    1129             : }
    1130             : 
    1131             : /* assume yz != and yz | x */
    1132             : GEN
    1133      200496 : diviuuexact(GEN x, ulong y, ulong z)
    1134             : {
    1135             :   long tmp[4];
    1136             :   ulong t;
    1137             :   LOCAL_HIREMAINDER;
    1138      200496 :   t = mulll(y, z);
    1139      200496 :   if (!hiremainder) return diviuexact(x, t);
    1140           1 :   tmp[0] = evaltyp(t_INT)|_evallg(4);
    1141           1 :   tmp[1] = evalsigne(1)|evallgefint(4);
    1142           1 :   tmp[2] = t;
    1143           1 :   tmp[3] = hiremainder;
    1144           1 :   return diviiexact(x, tmp);
    1145             : }
    1146             : 
    1147             : /********************************************************************/
    1148             : /**                                                                **/
    1149             : /**               INTEGER MULTIPLICATION                           **/
    1150             : /**                                                                **/
    1151             : /********************************************************************/
    1152             : 
    1153             : /* nx >= ny = num. of digits of x, y (not GEN, see mulii) */
    1154             : GEN
    1155  5954258086 : muliispec(GEN x, GEN y, long nx, long ny)
    1156             : {
    1157             :   GEN zd;
    1158             :   long lz;
    1159             :   ulong hi;
    1160             : 
    1161  5954258086 :   if (nx < ny) swapspec(x,y, nx,ny);
    1162  5954258086 :   if (!ny) return gen_0;
    1163  5954258086 :   if (ny == 1) return muluispec((ulong)*y, x, nx);
    1164             : 
    1165  1057598680 :   lz = nx+ny+2;
    1166  1057598680 :   zd = cgeti(lz);
    1167  1060634829 :   hi = mpn_mul(LIMBS(zd), (mp_limb_t *)x, nx, (mp_limb_t *)y, ny);
    1168  1067811781 :   if (!hi) lz--;
    1169             :   /*else zd[lz-1]=hi; GH tell me it is not necessary.*/
    1170             : 
    1171  1067811781 :   zd[1] = evalsigne(1) | evallgefint(lz);
    1172  1067811781 :   return zd;
    1173             : }
    1174             : GEN
    1175      222718 : muluui(ulong x, ulong y, GEN z)
    1176             : {
    1177      222718 :   long t, s = signe(z);
    1178             :   GEN r;
    1179             :   LOCAL_HIREMAINDER;
    1180             : 
    1181      222718 :   if (!x || !y || !signe(z)) return gen_0;
    1182      222337 :   t = mulll(x,y);
    1183      222337 :   if (!hiremainder)
    1184      222345 :     r = muluispec(t, z+2, lgefint(z)-2);
    1185             :   else
    1186             :   {
    1187             :     long tmp[2];
    1188           0 :     tmp[1] = hiremainder;
    1189           0 :     tmp[0] = t;
    1190           0 :     r = muliispec(z+2,tmp, lgefint(z)-2, 2);
    1191             :   }
    1192      222325 :   setsigne(r,s); return r;
    1193             : }
    1194             : 
    1195             : GEN
    1196  1026423557 : sqrispec(GEN x, long nx)
    1197             : {
    1198             :   GEN zd;
    1199             :   long lz;
    1200             : 
    1201  1026423557 :   if (!nx) return gen_0;
    1202   489568319 :   if (nx==1) return sqru(*x);
    1203             : 
    1204   278983150 :   lz = (nx<<1)+2;
    1205   278983150 :   zd = cgeti(lz);
    1206             : #ifdef mpn_sqr
    1207   275612753 :   mpn_sqr(LIMBS(zd), (mp_limb_t *)x, nx);
    1208             : #else
    1209             :   mpn_mul_n(LIMBS(zd), (mp_limb_t *)x, (mp_limb_t *)x, nx);
    1210             : #endif
    1211   279398998 :   if (zd[lz-1]==0) lz--;
    1212             : 
    1213   279398998 :   zd[1] = evalsigne(1) | evallgefint(lz);
    1214   279398998 :   return zd;
    1215             : }
    1216             : 
    1217             : INLINE GEN
    1218    41410076 : sqrispec_mirror(GEN x, long nx)
    1219             : {
    1220    41410076 :   GEN cx=new_chunk(nx);
    1221             :   GEN z;
    1222    41363653 :   xmpn_mirrorcopy((mp_limb_t *)cx,(mp_limb_t *)x,nx);
    1223    41469664 :   z=sqrispec(cx, nx);
    1224    41541262 :   xmpn_mirror(LIMBS(z), NLIMBS(z));
    1225    41539132 :   return z;
    1226             : }
    1227             : 
    1228             : /* leaves garbage on the stack. */
    1229             : INLINE GEN
    1230    85187139 : muliispec_mirror(GEN x, GEN y, long nx, long ny)
    1231             : {
    1232             :   GEN cx, cy, z;
    1233    85187139 :   long s = 0;
    1234   116328042 :   while (nx && x[nx-1]==0) { nx--; s++; }
    1235   122944624 :   while (ny && y[ny-1]==0) { ny--; s++; }
    1236    85187139 :   cx=new_chunk(nx); cy=new_chunk(ny);
    1237    84662069 :   xmpn_mirrorcopy((mp_limb_t *)cx,(mp_limb_t *)x,nx);
    1238    85519788 :   xmpn_mirrorcopy((mp_limb_t *)cy,(mp_limb_t *)y,ny);
    1239    86067191 :   z =  nx>=ny ? muliispec(cx, cy, nx, ny): muliispec(cy, cx, ny, nx);
    1240    86134334 :   if (s)
    1241             :   {
    1242     7856767 :     long i, lz = lgefint(z) + s;
    1243     7856767 :     (void)new_chunk(s);
    1244     7856767 :     z -= s;
    1245    76755150 :     for (i=0; i<s; i++) z[2+i]=0;
    1246     7856767 :     z[1] = evalsigne(1) | evallgefint(lz);
    1247     7856767 :     z[0] = evaltyp(t_INT) | evallg(lz);
    1248             :   }
    1249    86134335 :   xmpn_mirror(LIMBS(z), NLIMBS(z));
    1250    86642708 :   return z;
    1251             : }
    1252             : 
    1253             : /* x % (2^n), assuming n >= 0 */
    1254             : GEN
    1255    39052784 : remi2n(GEN x, long n)
    1256             : {
    1257             :   ulong hi;
    1258    39052784 :   long l, k, lx, ly, sx = signe(x);
    1259             :   GEN z, xd, zd;
    1260             : 
    1261    39052784 :   if (!sx || !n) return gen_0;
    1262             : 
    1263    38735644 :   k = dvmdsBIL(n, &l);
    1264    38745491 :   lx = lgefint(x);
    1265    38745491 :   if (lx < k+3) return icopy(x);
    1266             : 
    1267    37779334 :   xd = x + (2 + k);
    1268             :   /* x = |k|...|1|#|... : copy the last l bits of # and the first k words
    1269             :    *              ^--- initial xd  */
    1270    37779334 :   hi = ((ulong)*xd) & ((1UL<<l)-1); /* last l bits of # = top bits of result */
    1271    37779334 :   if (!hi)
    1272             :   { /* strip leading zeroes from result */
    1273     4267056 :     xd--; while (k && !*xd) { k--; xd--; }
    1274     4067617 :     if (!k) return gen_0;
    1275     2190534 :     ly = k+2;
    1276             :   }
    1277             :   else
    1278    33711717 :     ly = k+3;
    1279             : 
    1280    35902251 :   zd = z = cgeti(ly);
    1281    35864304 :   *++zd = evalsigne(sx) | evallgefint(ly);
    1282   535813026 :   xd = x+1; for ( ;k; k--) *++zd = *++xd;
    1283    35864304 :   if (hi) *++zd = hi;
    1284    35864304 :   return z;
    1285             : }
    1286             : 
    1287             : /********************************************************************/
    1288             : /**                                                                **/
    1289             : /**                      INTEGER SQUARE ROOT                       **/
    1290             : /**                                                                **/
    1291             : /********************************************************************/
    1292             : 
    1293             : /* Return S (and set R) s.t S^2 + R = N, 0 <= R <= 2S.
    1294             :  * As for dvmdii, R is last on stack and guaranteed to be gen_0 in case the
    1295             :  * remainder is 0. R = NULL is allowed. */
    1296             : GEN
    1297     5182309 : sqrtremi(GEN a, GEN *r)
    1298             : {
    1299     5182309 :   long l, na = NLIMBS(a);
    1300             :   mp_size_t nr;
    1301             :   GEN S;
    1302     5182309 :   if (!na) {
    1303         724 :     if (r) *r = gen_0;
    1304         724 :     return gen_0;
    1305             :   }
    1306     5181585 :   l = (na + 5) >> 1; /* 2 + ceil(na/2) */
    1307     5181585 :   S = cgetipos(l);
    1308     5181554 :   if (r) {
    1309     1310195 :     GEN R = cgeti(2 + na);
    1310     1310195 :     nr = mpn_sqrtrem(LIMBS(S), LIMBS(R), LIMBS(a), na);
    1311     1310195 :     if (nr) R[1] = evalsigne(1) | evallgefint(nr+2);
    1312       26516 :     else    { set_avma((pari_sp)S); R = gen_0; }
    1313     1310194 :     *r = R;
    1314             :   }
    1315             :   else
    1316     3871359 :     (void)mpn_sqrtrem(LIMBS(S), NULL, LIMBS(a), na);
    1317     5181559 :   return S;
    1318             : }
    1319             : 
    1320             : /* compute sqrt(|a|), assuming a != 0 */
    1321             : GEN
    1322   126383939 : sqrtr_abs(GEN a)
    1323             : {
    1324             :   GEN res;
    1325             :   mp_limb_t *b, *c;
    1326   126383939 :   long l = RNLIMBS(a), e = expo(a), er = e>>1;
    1327             :   long n;
    1328   126383939 :   res = cgetg(2 + l, t_REAL);
    1329   126299329 :   res[1] = evalsigne(1) | evalexpo(er);
    1330   126377978 :   if (e&1)
    1331             :   {
    1332    53328995 :     b = (mp_limb_t *) new_chunk(l<<1);
    1333    53313822 :     xmpn_zero(b,l);
    1334    53314654 :     xmpn_mirrorcopy(b+l, RLIMBS(a), l);
    1335    53327020 :     c = (mp_limb_t *) new_chunk(l);
    1336    53320706 :     n = mpn_sqrtrem(c,b,b,l<<1); /* c <- sqrt; b <- rem */
    1337    53357407 :     if (n>l || (n==l && mpn_cmp(b,c,l) > 0)) mpn_add_1(c,c,l,1);
    1338             :   }
    1339             :   else
    1340             :   {
    1341             :     ulong u;
    1342    73048983 :     b = (mp_limb_t *) mantissa2nr(a,-1);
    1343    73082338 :     b[1] = uel(a,l+1)<<(BITS_IN_LONG-1);
    1344    73082338 :     b = (mp_limb_t *) new_chunk(l);
    1345    73060161 :     xmpn_zero(b,l+1); /* overwrites the former b[0] */
    1346    73063497 :     c = (mp_limb_t *) new_chunk(l + 1);
    1347    73026335 :     n = mpn_sqrtrem(c,b,b,(l<<1)+2); /* c <- sqrt; b <- rem */
    1348    73125054 :     u = (ulong)*c++;
    1349    73125054 :     if ( u&HIGHBIT || (u == ~HIGHBIT &&
    1350           0 :              (n>l || (n==l && mpn_cmp(b,c,l)>0))))
    1351    36025571 :       mpn_add_1(c,c,l,1);
    1352             :   }
    1353   126492143 :   xmpn_mirrorcopy(RLIMBS(res),c,l);
    1354   126462509 :   return gc_const((pari_sp)res, res);
    1355             : }
    1356             : 
    1357             : /* Normalize a nonnegative integer */
    1358             : GEN
    1359   308776390 : int_normalize(GEN x, long known_zero_words)
    1360             : {
    1361   308776390 :   long i =  lgefint(x) - 1 - known_zero_words;
    1362  2778453013 :   for ( ; i > 1; i--)
    1363  2726235804 :     if (x[i]) { setlgefint(x, i+1); return x; }
    1364    52217209 :   x[1] = evalsigne(0) | evallgefint(2); return x;
    1365             : }
    1366             : 
    1367             : /********************************************************************
    1368             :  **                                                                **
    1369             :  **                           Base Conversion                      **
    1370             :  **                                                                **
    1371             :  ********************************************************************/
    1372             : 
    1373             : ulong *
    1374      438672 : convi(GEN x, long *l)
    1375             : {
    1376      438672 :   long n = nchar2nlong(2 + (long)(NLIMBS(x) * (BITS_IN_LONG * LOG10_2)));
    1377      438672 :   GEN str = cgetg(n+1, t_VECSMALL);
    1378      438672 :   unsigned char *res = (unsigned char*) GSTR(str);
    1379      438672 :   long llz = mpn_get_str(res, 10, LIMBS(icopy(x)), NLIMBS(x));
    1380             :   long lz;
    1381             :   ulong *z;
    1382             :   long i, j;
    1383             :   unsigned char *t;
    1384      438672 :   while (!*res) {res++; llz--;} /*Strip leading zeros*/
    1385      438672 :   lz  = (8+llz)/9;
    1386      438672 :   z = (ulong*)new_chunk(1+lz);
    1387      438672 :   t=res+llz+9;
    1388      870074 :   for(i=0;i<llz-8;i+=9)
    1389             :   {
    1390             :     ulong s;
    1391      431402 :     t-=18;
    1392      431402 :     s=*t++;
    1393     3882618 :     for (j=1; j<9;j++)
    1394     3451216 :       s=10*s+*t++;
    1395      431402 :     *z++=s;
    1396             :   }
    1397      438672 :   if (i<llz)
    1398             :   {
    1399      434689 :     unsigned char *t = res;
    1400      434689 :     ulong s=*t++;
    1401     1228754 :     for (j=i+1; j<llz;j++)
    1402      794065 :       s=10*s+*t++;
    1403      434689 :     *z++=s;
    1404             :   }
    1405      438672 :   *l = lz;
    1406      438672 :   return z;
    1407             : }

Generated by: LCOV version 1.16