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 - basemath - digits.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.16.2 lcov report (development 29115-f22e516b23) Lines: 195 204 95.6 %
Date: 2024-04-22 08:08:03 Functions: 27 27 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation; either version 2 of the License, or (at your option) any later
       8             : version. It is distributed in the hope that it will be useful, but WITHOUT
       9             : ANY WARRANTY WHATSOEVER.
      10             : 
      11             : Check the License for details. You should have received a copy of it, along
      12             : with the package; see the file 'COPYING'. If not, write to the Free Software
      13             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      14             : 
      15             : /*********************************************************************/
      16             : /**                    DIGITS / SUM OF DIGITS                       **/
      17             : /*********************************************************************/
      18             : #include "pari.h"
      19             : #include "paripriv.h"
      20             : 
      21             : /* set v[i] = 1 iff B^i is needed in the digits_dac algorithm */
      22             : static void
      23     3850773 : set_vexp(GEN v, long l)
      24             : {
      25             :   long m;
      26     3850773 :   if (v[l]) return;
      27     1407545 :   v[l] = 1; m = l>>1;
      28     1407545 :   set_vexp(v, m);
      29     1407545 :   set_vexp(v, l-m);
      30             : }
      31             : 
      32             : /* return all needed B^i for DAC algorithm, for lz digits */
      33             : static GEN
      34     1035683 : get_vB(GEN T, long lz, void *E, struct bb_ring *r)
      35             : {
      36     1035683 :   GEN vB, vexp = const_vecsmall(lz, 0);
      37     1035683 :   long i, l = (lz+1) >> 1;
      38     1035683 :   vexp[1] = 1;
      39     1035683 :   vexp[2] = 1;
      40     1035683 :   set_vexp(vexp, lz);
      41     1035683 :   vB = zerovec(lz); /* unneeded entries remain = 0 */
      42     1035683 :   gel(vB, 1) = T;
      43     2620139 :   for (i = 2; i <= l; i++)
      44     1584456 :     if (vexp[i])
      45             :     {
      46     1407545 :       long j = i >> 1;
      47     1407545 :       GEN B2j = r->sqr(E, gel(vB,j));
      48     1407545 :       gel(vB,i) = odd(i)? r->mul(E, B2j, T): B2j;
      49             :     }
      50     1035683 :   return vB;
      51             : }
      52             : 
      53             : static void
      54      369458 : gen_digits_dac(GEN x, GEN vB, long l, GEN *z,
      55             :                void *E, GEN div(void *E, GEN a, GEN b, GEN *r))
      56             : {
      57             :   GEN q, r;
      58      369458 :   long m = l>>1;
      59      369458 :   if (l==1) { *z=x; return; }
      60      175527 :   q = div(E, x, gel(vB,m), &r);
      61      175527 :   gen_digits_dac(r, vB, m, z, E, div);
      62      175527 :   gen_digits_dac(q, vB, l-m, z+m, E, div);
      63             : }
      64             : 
      65             : static GEN
      66      972580 : gen_fromdigits_dac(GEN x, GEN vB, long i, long l, void *E,
      67             :                    GEN add(void *E, GEN a, GEN b),
      68             :                    GEN mul(void *E, GEN a, GEN b))
      69             : {
      70             :   GEN a, b;
      71      972580 :   long m = l>>1;
      72      972580 :   if (l==1) return gel(x,i);
      73      441826 :   a = gen_fromdigits_dac(x, vB, i, m, E, add, mul);
      74      441826 :   b = gen_fromdigits_dac(x, vB, i+m, l-m, E, add, mul);
      75      441826 :   return add(E, a, mul(E, b, gel(vB, m)));
      76             : }
      77             : 
      78             : static GEN
      79       19006 : gen_digits_i(GEN x, GEN B, long n, void *E, struct bb_ring *r,
      80             :                           GEN (*div)(void *E, GEN x, GEN y, GEN *r))
      81             : {
      82             :   GEN z, vB;
      83       19006 :   if (n==1) retmkvec(gcopy(x));
      84       18404 :   vB = get_vB(B, n, E, r);
      85       18404 :   z = cgetg(n+1, t_VEC);
      86       18404 :   gen_digits_dac(x, vB, n, (GEN*)(z+1), E, div);
      87       18404 :   return z;
      88             : }
      89             : 
      90             : GEN
      91       18949 : gen_digits(GEN x, GEN B, long n, void *E, struct bb_ring *r,
      92             :                           GEN (*div)(void *E, GEN x, GEN y, GEN *r))
      93             : {
      94       18949 :   pari_sp av = avma;
      95       18949 :   return gerepilecopy(av, gen_digits_i(x, B, n, E, r, div));
      96             : }
      97             : 
      98             : GEN
      99       88928 : gen_fromdigits(GEN x, GEN B, void *E, struct bb_ring *r)
     100             : {
     101       88928 :   pari_sp av = avma;
     102       88928 :   long n = lg(x)-1;
     103       88928 :   GEN vB = get_vB(B, n, E, r);
     104       88928 :   GEN z = gen_fromdigits_dac(x, vB, 1, n, E, r->add, r->mul);
     105       88928 :   return gerepilecopy(av, z);
     106             : }
     107             : 
     108             : static GEN
     109      420595 : _addii(void *data /* ignored */, GEN x, GEN y)
     110      420595 : { (void)data; return addii(x,y); }
     111             : static GEN
     112     1345350 : _sqri(void *data /* ignored */, GEN x) { (void)data; return sqri(x); }
     113             : static GEN
     114      827664 : _mulii(void *data /* ignored */, GEN x, GEN y)
     115      827664 :  { (void)data; return mulii(x,y); }
     116             : static GEN
     117         443 : _dvmdii(void *data /* ignored */, GEN x, GEN y, GEN *r)
     118         443 :  { (void)data; return dvmdii(x,y,r); }
     119             : 
     120             : static struct bb_ring Z_ring = { _addii, _mulii, _sqri };
     121             : 
     122             : /* does not affect stack unless B = NULL */
     123             : static GEN
     124      224469 : check_basis(GEN B)
     125             : {
     126      224469 :   if (!B) return utoipos(10);
     127      224441 :   if (typ(B)!=t_INT) pari_err_TYPE("digits",B);
     128      224441 :   if (abscmpiu(B,2)<0) pari_err_DOMAIN("digits","abs(B)","<",gen_2,B);
     129      224427 :   return B;
     130             : }
     131             : 
     132             : /* x has l digits in base B, write them to z[0..l-1], vB[i] = B^i */
     133             : static void
     134      479894 : digits_dacsmall(GEN x, GEN vB, long l, ulong* z)
     135             : {
     136      479894 :   pari_sp av = avma;
     137             :   GEN q,r;
     138             :   long m;
     139      479894 :   if (l==1) { *z=itou(x); return; }
     140      212042 :   m=l>>1;
     141      212042 :   q = dvmdii(x, gel(vB,m), &r);
     142      212042 :   digits_dacsmall(q,vB,l-m,z);
     143      212042 :   digits_dacsmall(r,vB,m,z+l-m);
     144      212042 :   set_avma(av);
     145             : }
     146             : 
     147             : /* x t_INT */
     148             : static GEN
     149      112091 : digits_pos(GEN x, GEN B)
     150             : {
     151             :   long lz;
     152             :   GEN z;
     153      112091 :   if (abscmpii(x,B)<0) retmkvec(absi(x));
     154      111748 :   if (Z_ispow2(B))
     155             :   {
     156       55930 :     pari_sp av = avma;
     157       55930 :     long k = expi(B);
     158       55930 :     if (k == 1) return binaire(x);
     159       27923 :     if (k >= BITS_IN_LONG) return binary_2k(x, k);
     160       27916 :     (void)new_chunk(4*(expi(x) + 2)); /* HACK */
     161       27916 :     z = binary_2k_nv(x, k);
     162       27916 :     set_avma(av); return Flv_to_ZV(z);
     163             :   }
     164       55818 :   x = absi_shallow(x);
     165       55818 :   lz = logint(x,B) + 1;
     166       55818 :   if (lgefint(B) > 3)
     167             :   {
     168           8 :     z = gen_digits_i(x, B, lz, NULL, &Z_ring, _dvmdii);
     169           8 :     vecreverse_inplace(z); return z;
     170             :   }
     171             :   else
     172             :   {
     173       55810 :     pari_sp av = avma;
     174       55810 :     GEN vB = get_vB(B, lz, NULL, &Z_ring);
     175       55810 :     (void)new_chunk(3*lz); /* HACK */
     176       55810 :     z = zero_zv(lz);
     177       55810 :     digits_dacsmall(x,vB,lz,(ulong*)(z+1));
     178       55810 :     set_avma(av); return Flv_to_ZV(z);
     179             :   }
     180             : }
     181             : 
     182             : static GEN
     183       56028 : digits_neg(GEN n, GEN B)
     184             : {
     185       56028 :   GEN V = digits_pos(n,B);
     186       56028 :   long i, l = lg(V), carry = 0, s = signe(n)==-1;
     187      380478 :   for (i = 1; i < l; i++)
     188             :   {
     189      324450 :     GEN u = odd(i+s) ? addsi(carry, gel(V, l-i)): subsi(carry,gel(V, l-i));
     190      324450 :     if   (signe(u) < 0) { u = addii(u, B); carry=1; }
     191             :     else
     192      203721 :       if (cmpii(u, B) >= 0) { u = subii(u, B); carry=-1; }
     193             :     else
     194      170457 :       carry = 0;
     195      324450 :     gel(V,l-i) = u;
     196             :   }
     197       56028 :   if (carry > 0)
     198       28014 :     V = vec_prepend(V, stoi(carry));
     199       28014 :   else if (carry < 0)
     200        8533 :     V = shallowconcat(mkvec2(gen_1,addsi(carry, B)),V);
     201       56028 :   return V;
     202             : }
     203             : 
     204             : /* x t_INT */
     205             : static GEN
     206      112154 : digits_i(GEN x, GEN B)
     207             : {
     208      112154 :   pari_sp av = avma;
     209      112154 :   B = check_basis(B);
     210      112140 :   if (!signe(x))       {set_avma(av); return cgetg(1,t_VEC); }
     211      112077 :   if (signe(B) > 0) return gerepilecopy(av, digits_pos(x, B));
     212       56014 :   return gerepilecopy(av, digits_neg(x, negi(B)));
     213             : }
     214             : 
     215             : GEN
     216      112175 : digits(GEN x, GEN B)
     217             : {
     218      112175 :   pari_sp av = avma;
     219      112175 :   long v = 0;
     220      112175 :   if (typ(x) == t_INT) return digits_i(x, B);
     221          35 :   if (typ(x) != t_PADIC || (v = valp(x)) < 0 || (B && !gequal(B, gel(x,2))))
     222           7 :     pari_err_TYPE("digits",x);
     223          28 :   if (!signe(gel(x, 4))) return cgetg(1, t_VEC);
     224          14 :   x = digits_i(gel(x, 4), gel(x, 2));
     225          14 :   vecreverse_inplace(x);
     226          14 :   if (!v) return x;
     227           0 :   return gerepileupto(av, concat(zerovec(v), x));
     228             : }
     229             : 
     230             : static GEN
     231     3524843 : fromdigitsu_dac(GEN x, GEN vB, long i, long l)
     232             : {
     233             :   GEN a, b;
     234     3524843 :   long m = l>>1;
     235     3524843 :   if (l==1) return utoi(uel(x,i));
     236     2917607 :   if (l==2) return addui(uel(x,i), mului(uel(x,i+1), gel(vB, m)));
     237     1326151 :   a = fromdigitsu_dac(x, vB, i, m);
     238     1326151 :   b = fromdigitsu_dac(x, vB, i+m, l-m);
     239     1326151 :   return addii(a, mulii(b, gel(vB, m)));
     240             : }
     241             : 
     242             : static GEN
     243      872541 : fromdigitsu_i(GEN x, GEN B)
     244             : {
     245      872541 :   long n = lg(x)-1;
     246             :   GEN vB;
     247      872541 :   if (n == 0) return gen_0;
     248      872541 :   vB = get_vB(B, n, NULL, &Z_ring);
     249      872541 :   return fromdigitsu_dac(x, vB, 1, n);
     250             : }
     251             : GEN
     252      872527 : fromdigitsu(GEN x, GEN B)
     253      872527 : { pari_sp av = avma; return gerepileuptoint(av, fromdigitsu_i(x, B)); }
     254             : 
     255             : static int
     256       28028 : ZV_in_range(GEN v, GEN B)
     257             : {
     258       28028 :   long i, l = lg(v);
     259      220822 :   for (i = 1; i < l; i++)
     260             :   {
     261      192808 :     GEN vi = gel(v, i);
     262      192808 :     if (signe(vi) < 0 || cmpii(vi, B) >= 0) return 0;
     263             :   }
     264       28014 :   return 1;
     265             : }
     266             : static int
     267          21 : zv_nonnegative(GEN v)
     268             : {
     269          21 :   long i, l = lg(v);
     270         763 :   for (i = 1; i < l; i++) if (v[i] < 0) return 0;
     271          14 :   return 1;
     272             : }
     273             : 
     274             : GEN
     275      112273 : fromdigits(GEN x, GEN B)
     276             : {
     277      112273 :   pari_sp av = avma;
     278      112273 :   long tx = typ(x);
     279      112273 :   if (tx == t_VECSMALL)
     280             :   {
     281          28 :     if (lg(x)==1) return gen_0;
     282          21 :     if (zv_nonnegative(x))
     283             :     {
     284          14 :       B = check_basis(B); x = vecsmall_reverse(x);
     285          14 :       return gerepileuptoint(av, fromdigitsu_i(x, B));
     286             :     }
     287           7 :     x = zv_to_ZV(x);
     288             :   }
     289      112245 :   else if (!is_vec_t(tx) || !RgV_is_ZV(x)) pari_err_TYPE("fromdigits",x);
     290      112252 :   if (lg(x) == 1) return gen_0;
     291      112189 :   B = check_basis(B);
     292      112189 :   if (Z_ispow2(B) && ZV_in_range(x, B)) return fromdigits_2k(x, expi(B));
     293       84175 :   x = vecreverse(x);
     294       84175 :   return gerepileuptoint(av, gen_fromdigits(x, B, NULL, &Z_ring));
     295             : }
     296             : 
     297             : static const ulong digsum[] ={
     298             :   0,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,10,2,3,4,5,6,7,8,9,10,11,3,4,5,6,7,8,
     299             :   9,10,11,12,4,5,6,7,8,9,10,11,12,13,5,6,7,8,9,10,11,12,13,14,6,7,8,9,10,11,
     300             :   12,13,14,15,7,8,9,10,11,12,13,14,15,16,8,9,10,11,12,13,14,15,16,17,9,10,11,
     301             :   12,13,14,15,16,17,18,1,2,3,4,5,6,7,8,9,10,2,3,4,5,6,7,8,9,10,11,3,4,5,6,7,8,
     302             :   9,10,11,12,4,5,6,7,8,9,10,11,12,13,5,6,7,8,9,10,11,12,13,14,6,7,8,9,10,11,
     303             :   12,13,14,15,7,8,9,10,11,12,13,14,15,16,8,9,10,11,12,13,14,15,16,17,9,10,11,
     304             :   12,13,14,15,16,17,18,10,11,12,13,14,15,16,17,18,19,2,3,4,5,6,7,8,9,10,11,3,
     305             :   4,5,6,7,8,9,10,11,12,4,5,6,7,8,9,10,11,12,13,5,6,7,8,9,10,11,12,13,14,6,7,8,
     306             :   9,10,11,12,13,14,15,7,8,9,10,11,12,13,14,15,16,8,9,10,11,12,13,14,15,16,17,
     307             :   9,10,11,12,13,14,15,16,17,18,10,11,12,13,14,15,16,17,18,19,11,12,13,14,15,
     308             :   16,17,18,19,20,3,4,5,6,7,8,9,10,11,12,4,5,6,7,8,9,10,11,12,13,5,6,7,8,9,10,
     309             :   11,12,13,14,6,7,8,9,10,11,12,13,14,15,7,8,9,10,11,12,13,14,15,16,8,9,10,11,
     310             :   12,13,14,15,16,17,9,10,11,12,13,14,15,16,17,18,10,11,12,13,14,15,16,17,18,
     311             :   19,11,12,13,14,15,16,17,18,19,20,12,13,14,15,16,17,18,19,20,21,4,5,6,7,8,9,
     312             :   10,11,12,13,5,6,7,8,9,10,11,12,13,14,6,7,8,9,10,11,12,13,14,15,7,8,9,10,11,
     313             :   12,13,14,15,16,8,9,10,11,12,13,14,15,16,17,9,10,11,12,13,14,15,16,17,18,10,
     314             :   11,12,13,14,15,16,17,18,19,11,12,13,14,15,16,17,18,19,20,12,13,14,15,16,17,
     315             :   18,19,20,21,13,14,15,16,17,18,19,20,21,22,5,6,7,8,9,10,11,12,13,14,6,7,8,9,
     316             :   10,11,12,13,14,15,7,8,9,10,11,12,13,14,15,16,8,9,10,11,12,13,14,15,16,17,9,
     317             :   10,11,12,13,14,15,16,17,18,10,11,12,13,14,15,16,17,18,19,11,12,13,14,15,16,
     318             :   17,18,19,20,12,13,14,15,16,17,18,19,20,21,13,14,15,16,17,18,19,20,21,22,14,
     319             :   15,16,17,18,19,20,21,22,23,6,7,8,9,10,11,12,13,14,15,7,8,9,10,11,12,13,14,
     320             :   15,16,8,9,10,11,12,13,14,15,16,17,9,10,11,12,13,14,15,16,17,18,10,11,12,13,
     321             :   14,15,16,17,18,19,11,12,13,14,15,16,17,18,19,20,12,13,14,15,16,17,18,19,20,
     322             :   21,13,14,15,16,17,18,19,20,21,22,14,15,16,17,18,19,20,21,22,23,15,16,17,18,
     323             :   19,20,21,22,23,24,7,8,9,10,11,12,13,14,15,16,8,9,10,11,12,13,14,15,16,17,9,
     324             :   10,11,12,13,14,15,16,17,18,10,11,12,13,14,15,16,17,18,19,11,12,13,14,15,16,
     325             :   17,18,19,20,12,13,14,15,16,17,18,19,20,21,13,14,15,16,17,18,19,20,21,22,14,
     326             :   15,16,17,18,19,20,21,22,23,15,16,17,18,19,20,21,22,23,24,16,17,18,19,20,21,
     327             :   22,23,24,25,8,9,10,11,12,13,14,15,16,17,9,10,11,12,13,14,15,16,17,18,10,11,
     328             :   12,13,14,15,16,17,18,19,11,12,13,14,15,16,17,18,19,20,12,13,14,15,16,17,18,
     329             :   19,20,21,13,14,15,16,17,18,19,20,21,22,14,15,16,17,18,19,20,21,22,23,15,16,
     330             :   17,18,19,20,21,22,23,24,16,17,18,19,20,21,22,23,24,25,17,18,19,20,21,22,23,
     331             :   24,25,26,9,10,11,12,13,14,15,16,17,18,10,11,12,13,14,15,16,17,18,19,11,12,
     332             :   13,14,15,16,17,18,19,20,12,13,14,15,16,17,18,19,20,21,13,14,15,16,17,18,19,
     333             :   20,21,22,14,15,16,17,18,19,20,21,22,23,15,16,17,18,19,20,21,22,23,24,16,17,
     334             :   18,19,20,21,22,23,24,25,17,18,19,20,21,22,23,24,25,26,18,19,20,21,22,23,24,
     335             :   25,26,27
     336             : };
     337             : 
     338             : ulong
     339      355152 : sumdigitsu(ulong n)
     340             : {
     341      355152 :   ulong s = 0;
     342     1361843 :   while (n) { s += digsum[n % 1000]; n /= 1000; }
     343      355152 :   return s;
     344             : }
     345             : 
     346             : /* res=array of 9-digits integers, return sum_{0 <= i < l} sumdigits(res[i]) */
     347             : static ulong
     348          14 : sumdigits_block(ulong *res, long l)
     349             : {
     350          14 :   ulong s = sumdigitsu(*--res);
     351      355138 :   while (--l > 0) s += sumdigitsu(*--res);
     352          14 :   return s;
     353             : }
     354             : 
     355             : GEN
     356          35 : sumdigits(GEN n)
     357             : {
     358          35 :   const long L = (long)(ULONG_MAX / 81);
     359          35 :   pari_sp av = avma;
     360             :   ulong *res;
     361             :   long l;
     362             : 
     363          35 :   if (typ(n) != t_INT) pari_err_TYPE("sumdigits", n);
     364          35 :   switch(lgefint(n))
     365             :   {
     366           7 :     case 2: return gen_0;
     367          14 :     case 3: return utoipos(sumdigitsu(n[2]));
     368             :   }
     369          14 :   res = convi(n, &l);
     370          14 :   if (l < L)
     371             :   {
     372          14 :     ulong s = sumdigits_block(res, l);
     373          14 :     return gc_utoipos(av, s);
     374             :   }
     375             :   else /* Huge. Overflows ulong */
     376             :   {
     377           0 :     GEN S = gen_0;
     378           0 :     while (l > L)
     379             :     {
     380           0 :       S = addiu(S, sumdigits_block(res, L));
     381           0 :       res += L; l -= L;
     382             :     }
     383           0 :     if (l)
     384           0 :       S = addiu(S, sumdigits_block(res, l));
     385           0 :     return gerepileuptoint(av, S);
     386             :   }
     387             : }
     388             : 
     389             : GEN
     390         140 : sumdigits0(GEN x, GEN B)
     391             : {
     392         140 :   pari_sp av = avma;
     393             :   GEN z;
     394             :   long lz;
     395             : 
     396         140 :   if (!B) return sumdigits(x);
     397         112 :   if (typ(x) != t_INT) pari_err_TYPE("sumdigits", x);
     398         112 :   B = check_basis(B);
     399         112 :   if (signe(B)<0) return gerepileuptoint(av, ZV_sum(digits_neg(x,negi(B))));
     400          98 :   if (Z_ispow2(B))
     401             :   {
     402          35 :     long k = expi(B);
     403          35 :     if (k == 1) return gc_utoi(av,hammingweight(x));
     404          21 :     if (k < BITS_IN_LONG)
     405             :     {
     406          14 :       GEN z = binary_2k_nv(x, k);
     407          14 :       if (lg(z)-1 > 1L<<(BITS_IN_LONG-k)) /* may overflow */
     408           0 :         return gerepileuptoint(av, ZV_sum(Flv_to_ZV(z)));
     409          14 :       return gc_utoi(av,zv_sum(z));
     410             :     }
     411           7 :     return gerepileuptoint(av, ZV_sum(binary_2k(x, k)));
     412             :   }
     413          63 :   if (!signe(x))       { set_avma(av); return gen_0; }
     414          63 :   if (abscmpii(x,B)<0) { set_avma(av); return absi(x); }
     415          56 :   if (absequaliu(B,10))   { set_avma(av); return sumdigits(x); }
     416          49 :   x = absi_shallow(x); lz = logint(x,B) + 1;
     417          49 :   z = gen_digits_i(x, B, lz, NULL, &Z_ring, _dvmdii);
     418          49 :   return gerepileuptoint(av, ZV_sum(z));
     419             : }

Generated by: LCOV version 1.14