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.14.0 lcov report (development 27775-aca467eab2) Lines: 162 174 93.1 %
Date: 2022-07-03 07:33:15 Functions: 23 23 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     3963126 : set_vexp(GEN v, long l)
      24             : {
      25             :   long m;
      26     3963126 :   if (v[l]) return;
      27     1143832 :   v[l] = 1; m = l>>1;
      28     1143832 :   set_vexp(v, m);
      29     1143832 :   set_vexp(v, l-m);
      30             : }
      31             : 
      32             : /* return all needed B^i for DAC algorithm, for lz digits */
      33             : static GEN
      34     1675462 : get_vB(GEN T, long lz, void *E, struct bb_ring *r)
      35             : {
      36     1675462 :   GEN vB, vexp = const_vecsmall(lz, 0);
      37     1675462 :   long i, l = (lz+1) >> 1;
      38     1675462 :   vexp[1] = 1;
      39     1675462 :   vexp[2] = 1;
      40     1675462 :   set_vexp(vexp, lz);
      41     1675462 :   vB = zerovec(lz); /* unneeded entries remain = 0 */
      42     1675462 :   gel(vB, 1) = T;
      43     2978533 :   for (i = 2; i <= l; i++)
      44     1303071 :     if (vexp[i])
      45             :     {
      46     1143832 :       long j = i >> 1;
      47     1143832 :       GEN B2j = r->sqr(E, gel(vB,j));
      48     1143832 :       gel(vB,i) = odd(i)? r->mul(E, B2j, T): B2j;
      49             :     }
      50     1675462 :   return vB;
      51             : }
      52             : 
      53             : static void
      54      342333 : 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      342333 :   long m = l>>1;
      59      342333 :   if (l==1) { *z=x; return; }
      60      163179 :   q = div(E, x, gel(vB,m), &r);
      61      163179 :   gen_digits_dac(r, vB, m, z, E, div);
      62      163179 :   gen_digits_dac(q, vB, l-m, z+m, E, div);
      63             : }
      64             : 
      65             : static GEN
      66       51177 : 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       51177 :   long m = l>>1;
      72       51177 :   if (l==1) return gel(x,i);
      73       23128 :   a = gen_fromdigits_dac(x, vB, i, m, E, add, mul);
      74       23128 :   b = gen_fromdigits_dac(x, vB, i+m, l-m, E, add, mul);
      75       23128 :   return add(E, a, mul(E, b, gel(vB, m)));
      76             : }
      77             : 
      78             : static GEN
      79       16570 : 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       16570 :   if (n==1) retmkvec(gcopy(x));
      84       15975 :   vB = get_vB(B, n, E, r);
      85       15975 :   z = cgetg(n+1, t_VEC);
      86       15975 :   gen_digits_dac(x, vB, n, (GEN*)(z+1), E, div);
      87       15975 :   return z;
      88             : }
      89             : 
      90             : GEN
      91       16513 : 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       16513 :   pari_sp av = avma;
      95       16513 :   return gerepilecopy(av, gen_digits_i(x, B, n, E, r, div));
      96             : }
      97             : 
      98             : GEN
      99        4921 : gen_fromdigits(GEN x, GEN B, void *E, struct bb_ring *r)
     100             : {
     101        4921 :   pari_sp av = avma;
     102        4921 :   long n = lg(x)-1;
     103        4921 :   GEN vB = get_vB(B, n, E, r);
     104        4921 :   GEN z = gen_fromdigits_dac(x, vB, 1, n, E, r->add, r->mul);
     105        4921 :   return gerepilecopy(av, z);
     106             : }
     107             : 
     108             : static GEN
     109        1897 : _addii(void *data /* ignored */, GEN x, GEN y)
     110        1897 : { (void)data; return addii(x,y); }
     111             : static GEN
     112     1086712 : _sqri(void *data /* ignored */, GEN x) { (void)data; return sqri(x); }
     113             : static GEN
     114      319737 : _mulii(void *data /* ignored */, GEN x, GEN y)
     115      319737 :  { (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         350 : check_basis(GEN B)
     125             : {
     126         350 :   if (!B) return utoipos(10);
     127         329 :   if (typ(B)!=t_INT) pari_err_TYPE("digits",B);
     128         329 :   if (abscmpiu(B,2)<0) pari_err_DOMAIN("digits","B","<",gen_2,B);
     129         329 :   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        3110 : digits_dacsmall(GEN x, GEN vB, long l, ulong* z)
     135             : {
     136        3110 :   pari_sp av = avma;
     137             :   GEN q,r;
     138             :   long m;
     139        3110 :   if (l==1) { *z=itou(x); return; }
     140        1538 :   m=l>>1;
     141        1538 :   q = dvmdii(x, gel(vB,m), &r);
     142        1538 :   digits_dacsmall(q,vB,l-m,z);
     143        1538 :   digits_dacsmall(r,vB,m,z+l-m);
     144        1538 :   set_avma(av);
     145             : }
     146             : 
     147             : /* x t_INT */
     148             : static GEN
     149          70 : digits_i(GEN x, GEN B)
     150             : {
     151          70 :   pari_sp av = avma;
     152             :   long lz;
     153             :   GEN z;
     154          70 :   B = check_basis(B);
     155          70 :   if (signe(B) < 0) pari_err_DOMAIN("digits","B","<",gen_0,B);
     156          70 :   if (!signe(x))       {set_avma(av); return cgetg(1,t_VEC); }
     157          63 :   if (abscmpii(x,B)<0) {set_avma(av); retmkvec(absi(x)); }
     158          56 :   if (Z_ispow2(B))
     159             :   {
     160          14 :     long k = expi(B);
     161          14 :     if (k == 1) return binaire(x);
     162           7 :     if (k >= BITS_IN_LONG) return binary_2k(x, k);
     163           0 :     (void)new_chunk(4*(expi(x) + 2)); /* HACK */
     164           0 :     z = binary_2k_nv(x, k);
     165           0 :     set_avma(av); return Flv_to_ZV(z);
     166             :   }
     167          42 :   x = absi_shallow(x);
     168          42 :   lz = logint(x,B) + 1;
     169          42 :   if (lgefint(B) > 3)
     170             :   {
     171           8 :     z = gerepileupto(av, gen_digits_i(x, B, lz, NULL, &Z_ring, _dvmdii));
     172           8 :     vecreverse_inplace(z); return z;
     173             :   }
     174             :   else
     175             :   {
     176          34 :     GEN vB = get_vB(B, lz, NULL, &Z_ring);
     177          34 :     (void)new_chunk(3*lz); /* HACK */
     178          34 :     z = zero_zv(lz);
     179          34 :     digits_dacsmall(x,vB,lz,(ulong*)(z+1));
     180          34 :     set_avma(av); return Flv_to_ZV(z);
     181             :   }
     182             : }
     183             : GEN
     184          91 : digits(GEN x, GEN B)
     185             : {
     186          91 :   pari_sp av = avma;
     187          91 :   long v = 0;
     188          91 :   if (typ(x) == t_INT) return digits_i(x, B);
     189          35 :   if (typ(x) != t_PADIC || (v = valp(x)) < 0 || (B && !gequal(B, gel(x,2))))
     190           7 :     pari_err_TYPE("digits",x);
     191          28 :   if (!signe(gel(x, 4))) return cgetg(1, t_VEC);
     192          14 :   x = digits_i(gel(x, 4), gel(x, 2));
     193          14 :   vecreverse_inplace(x);
     194          14 :   if (!v) return x;
     195           0 :   return gerepileupto(av, concat(zerovec(v), x));
     196             : }
     197             : 
     198             : static GEN
     199     4303672 : fromdigitsu_dac(GEN x, GEN vB, long i, long l)
     200             : {
     201             :   GEN a, b;
     202     4303672 :   long m = l>>1;
     203     4303672 :   if (l==1) return utoi(uel(x,i));
     204     3558352 :   if (l==2) return addumului(uel(x,i), uel(x,i+1), gel(vB, m));
     205     1324570 :   a = fromdigitsu_dac(x, vB, i, m);
     206     1324570 :   b = fromdigitsu_dac(x, vB, i+m, l-m);
     207     1324570 :   return addii(a, mulii(b, gel(vB, m)));
     208             : }
     209             : 
     210             : GEN
     211     1654532 : fromdigitsu(GEN x, GEN B)
     212             : {
     213     1654532 :   pari_sp av = avma;
     214     1654532 :   long n = lg(x)-1;
     215             :   GEN vB, z;
     216     1654532 :   if (n==0) return gen_0;
     217     1654532 :   vB = get_vB(B, n, NULL, &Z_ring);
     218     1654532 :   z = fromdigitsu_dac(x, vB, 1, n);
     219     1654532 :   return gerepileuptoint(av, z);
     220             : }
     221             : 
     222             : static int
     223          21 : ZV_in_range(GEN v, GEN B)
     224             : {
     225          21 :   long i, l = lg(v);
     226        1687 :   for(i=1; i < l; i++)
     227             :   {
     228        1673 :     GEN vi = gel(v, i);
     229        1673 :     if (signe(vi) < 0 || cmpii(vi, B) >= 0) return 0;
     230             :   }
     231          14 :   return 1;
     232             : }
     233             : 
     234             : GEN
     235         189 : fromdigits(GEN x, GEN B)
     236             : {
     237         189 :   pari_sp av = avma;
     238         189 :   if (typ(x)!=t_VEC || !RgV_is_ZV(x)) pari_err_TYPE("fromdigits",x);
     239         189 :   if (lg(x)==1) return gen_0;
     240         182 :   B = check_basis(B);
     241         182 :   if (Z_ispow2(B) && ZV_in_range(x, B)) return fromdigits_2k(x, expi(B));
     242         168 :   x = vecreverse(x);
     243         168 :   return gerepileuptoint(av, gen_fromdigits(x, B, NULL, &Z_ring));
     244             : }
     245             : 
     246             : static const ulong digsum[] ={
     247             :   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,
     248             :   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,
     249             :   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,
     250             :   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,
     251             :   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,
     252             :   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,
     253             :   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,
     254             :   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,
     255             :   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,
     256             :   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,
     257             :   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,
     258             :   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,
     259             :   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,
     260             :   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,
     261             :   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,
     262             :   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,
     263             :   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,
     264             :   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,
     265             :   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,
     266             :   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,
     267             :   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,
     268             :   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,
     269             :   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,
     270             :   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,
     271             :   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,
     272             :   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,
     273             :   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,
     274             :   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,
     275             :   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,
     276             :   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,
     277             :   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,
     278             :   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,
     279             :   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,
     280             :   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,
     281             :   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,
     282             :   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,
     283             :   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,
     284             :   25,26,27
     285             : };
     286             : 
     287             : ulong
     288      355152 : sumdigitsu(ulong n)
     289             : {
     290      355152 :   ulong s = 0;
     291     1361843 :   while (n) { s += digsum[n % 1000]; n /= 1000; }
     292      355152 :   return s;
     293             : }
     294             : 
     295             : /* res=array of 9-digits integers, return sum_{0 <= i < l} sumdigits(res[i]) */
     296             : static ulong
     297          14 : sumdigits_block(ulong *res, long l)
     298             : {
     299          14 :   ulong s = sumdigitsu(*--res);
     300      355138 :   while (--l > 0) s += sumdigitsu(*--res);
     301          14 :   return s;
     302             : }
     303             : 
     304             : GEN
     305          35 : sumdigits(GEN n)
     306             : {
     307          35 :   const long L = (long)(ULONG_MAX / 81);
     308          35 :   pari_sp av = avma;
     309             :   ulong *res;
     310             :   long l;
     311             : 
     312          35 :   if (typ(n) != t_INT) pari_err_TYPE("sumdigits", n);
     313          35 :   switch(lgefint(n))
     314             :   {
     315           7 :     case 2: return gen_0;
     316          14 :     case 3: return utoipos(sumdigitsu(n[2]));
     317             :   }
     318          14 :   res = convi(n, &l);
     319          14 :   if (l < L)
     320             :   {
     321          14 :     ulong s = sumdigits_block(res, l);
     322          14 :     set_avma(av); return utoipos(s);
     323             :   }
     324             :   else /* Huge. Overflows ulong */
     325             :   {
     326           0 :     GEN S = gen_0;
     327           0 :     while (l > L)
     328             :     {
     329           0 :       S = addiu(S, sumdigits_block(res, L));
     330           0 :       res += L; l -= L;
     331             :     }
     332           0 :     if (l)
     333           0 :       S = addiu(S, sumdigits_block(res, l));
     334           0 :     return gerepileuptoint(av, S);
     335             :   }
     336             : }
     337             : 
     338             : GEN
     339         126 : sumdigits0(GEN x, GEN B)
     340             : {
     341         126 :   pari_sp av = avma;
     342             :   GEN z;
     343             :   long lz;
     344             : 
     345         126 :   if (!B) return sumdigits(x);
     346          98 :   if (typ(x) != t_INT) pari_err_TYPE("sumdigits", x);
     347          98 :   B = check_basis(B);
     348          98 :   if (Z_ispow2(B))
     349             :   {
     350          35 :     long k = expi(B);
     351          35 :     if (k == 1) { set_avma(av); return utoi(hammingweight(x)); }
     352          21 :     if (k < BITS_IN_LONG)
     353             :     {
     354          14 :       GEN z = binary_2k_nv(x, k);
     355          14 :       if (lg(z)-1 > 1L<<(BITS_IN_LONG-k)) /* may overflow */
     356           0 :         return gerepileuptoint(av, ZV_sum(Flv_to_ZV(z)));
     357          14 :       set_avma(av); return utoi(zv_sum(z));
     358             :     }
     359           7 :     return gerepileuptoint(av, ZV_sum(binary_2k(x, k)));
     360             :   }
     361          63 :   if (!signe(x))       { set_avma(av); return gen_0; }
     362          63 :   if (abscmpii(x,B)<0) { set_avma(av); return absi(x); }
     363          56 :   if (absequaliu(B,10))   { set_avma(av); return sumdigits(x); }
     364          49 :   x = absi_shallow(x); lz = logint(x,B) + 1;
     365          49 :   z = gen_digits_i(x, B, lz, NULL, &Z_ring, _dvmdii);
     366          49 :   return gerepileuptoint(av, ZV_sum(z));
     367             : }

Generated by: LCOV version 1.13