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 - bit.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.1 lcov report (development 25406-bf255ab81b) Lines: 408 422 96.7 %
Date: 2020-06-04 05:59:24 Functions: 34 36 94.4 %
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. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : #include "pari.h"
      15             : #include "paripriv.h"
      16             : /*********************************************************************/
      17             : /**                                                                 **/
      18             : /**                       BINARY DECOMPOSITION                      **/
      19             : /**                                                                 **/
      20             : /*********************************************************************/
      21             : 
      22             : INLINE GEN
      23         630 : inegate(GEN z) { return subsi(-1,z); }
      24             : 
      25             : GEN
      26        7231 : binary_zv(GEN x)
      27             : {
      28             :   GEN xp, z;
      29             :   long i, k, lx;
      30        7231 :   if (!signe(x)) return cgetg(1,t_VECSMALL);
      31        7217 :   xp = int_LSW(x);
      32        7217 :   lx = lgefint(x);
      33        7217 :   k = expi(x)+2;
      34        7217 :   z = cgetg(k, t_VECSMALL);
      35        7217 :   k--;
      36        7363 :   for(i = 2; i < lx; i++)
      37             :   {
      38        7363 :     ulong u = *xp;
      39             :     long j;
      40       80842 :     for (j=0; j<BITS_IN_LONG && k; j++) z[k--] = (u>>j)&1UL;
      41        7363 :     if (!k) break;
      42         146 :     xp = int_nextW(xp);
      43             :   }
      44        7217 :   return z;
      45             : }
      46             : static GEN
      47          42 : F2v_to_ZV_inplace(GEN v)
      48             : {
      49          42 :   long i, l = lg(v);
      50          42 :   v[0] = evaltyp(t_VEC) | _evallg(l);
      51        8813 :   for (i = 1; i < l; i++) gel(v,i) = v[i]? gen_1: gen_0;
      52          42 :   return v;
      53             : }
      54             : /* "vector" of l bits (possibly no code word) to non-negative t_INT */
      55             : GEN
      56           0 : bits_to_int(GEN x, long l)
      57             : {
      58             :   long i, j, lz;
      59             :   GEN z, zp;
      60             : 
      61           0 :   if (!l) return gen_0;
      62           0 :   lz = nbits2lg(l);
      63           0 :   z = cgetg(lz, t_INT);
      64           0 :   z[1] = evalsigne(1) | evallgefint(lz);
      65           0 :   zp = int_LSW(z); *zp = 0;
      66           0 :   for(i=l,j=0; i; i--,j++)
      67             :   {
      68           0 :     if (j==BITS_IN_LONG) { j=0; zp = int_nextW(zp); *zp = 0; }
      69           0 :     if (x[i]) *zp |= 1UL<<j;
      70             :   }
      71           0 :   return int_normalize(z, 0);
      72             : }
      73             : /* "vector" of l < BITS_IN_LONG bits (possibly no code word) to non-negative
      74             :  * ulong */
      75             : ulong
      76           0 : bits_to_u(GEN v, long l)
      77             : {
      78           0 :   ulong u = 0;
      79             :   long i;
      80           0 :   for (i = 1; i <= l; i++) u = (u <<1) | v[i];
      81           0 :   return u;
      82             : }
      83             : 
      84             : /* set BITS_IN_LONG bits starting at word *w plus *r bits,
      85             :  * clearing subsequent bits in the last word touched */
      86             : INLINE void
      87          24 : int_set_ulong(ulong a, GEN *w, long *r)
      88             : {
      89          24 :   if (*r) {
      90          12 :     **w |= (a << *r);
      91          12 :     *w = int_nextW(*w);
      92          12 :     **w = (a >> (BITS_IN_LONG - *r));
      93             :   } else {
      94          12 :     **w = a;
      95          12 :     *w = int_nextW(*w);
      96             :   }
      97          24 : }
      98             : 
      99             : /* set k bits starting at word *w plus *r bits,
     100             :  * clearing subsequent bits in the last word touched */
     101             : INLINE void
     102   504015033 : int_set_bits(ulong a, long k, GEN *w, long *r)
     103             : {
     104   504015033 :   if (*r) {
     105   476180897 :     **w |= a << *r;
     106   476180897 :     a >>= BITS_IN_LONG - *r;
     107             :   } else {
     108    27834136 :     **w = a;
     109    27834136 :     a = 0;
     110             :   }
     111   504015033 :   *r += k;
     112   504015033 :   if (*r >= BITS_IN_LONG) {
     113   251784307 :     *w = int_nextW(*w);
     114   251784307 :     *r -= BITS_IN_LONG;
     115   317820709 :     for (; *r >= BITS_IN_LONG; *r -= BITS_IN_LONG) {
     116    66036402 :       **w = a;
     117    66036402 :       a = 0;
     118    66036402 :       *w = int_nextW(*w);
     119             :     }
     120   251784307 :     if (*r)
     121   234210889 :       **w = a;
     122             :   }
     123   504015033 : }
     124             : 
     125             : /* set k bits from z (t_INT) starting at word *w plus *r bits,
     126             :  * clearing subsequent bits in the last word touched */
     127             : INLINE void
     128        1649 : int_set_int(GEN z, long k, GEN *w, long *r)
     129             : {
     130        1649 :   long l = lgefint(z) - 2;
     131             :   GEN y;
     132        1649 :   if (!l) {
     133         896 :     int_set_bits(0, k, w, r);
     134         896 :     return;
     135             :   }
     136         753 :   y = int_LSW(z);
     137         777 :   for (; l > 1; l--) {
     138          24 :     int_set_ulong((ulong) *y, w, r);
     139          24 :     y = int_nextW(y);
     140          24 :     k -= BITS_IN_LONG;
     141             :   }
     142         753 :   if (k)
     143         753 :     int_set_bits((ulong) *y, k, w, r);
     144             : }
     145             : 
     146             : GEN
     147    10794929 : nv_fromdigits_2k(GEN x, long k)
     148             : {
     149    10794929 :   long l = lg(x) - 1, r;
     150             :   GEN w, z;
     151    10794929 :   if (k == 1) return bits_to_int(x, l);
     152    10794929 :   if (!l) return gen_0;
     153    10794929 :   z = cgetipos(nbits2lg(k * l));
     154    10801357 :   w = int_LSW(z);
     155    10801357 :   r = 0;
     156   514825507 :   for (; l; l--)
     157   504031602 :     int_set_bits(uel(x, l), k, &w, &r);
     158    10793905 :   return int_normalize(z, 0);
     159             : }
     160             : 
     161             : GEN
     162          14 : fromdigits_2k(GEN x, long k)
     163             : {
     164             :   long l, m;
     165             :   GEN w, y, z;
     166          14 :   for (l = lg(x) - 1; l && !signe(gel(x, 1)); x++, l--);
     167          14 :   if (!l) return gen_0;
     168          14 :   m = expi(gel(x, 1)) + 1;
     169          14 :   z = cgetipos(nbits2lg(k * (l - 1) + m));
     170          14 :   w = int_LSW(z);
     171          14 :   if (!(k & (BITS_IN_LONG - 1)))
     172             :   {
     173           1 :     long i, j, t = k >> TWOPOTBITS_IN_LONG;
     174           4 :     for (; l; l--)
     175             :     {
     176           3 :       j = lgefint(gel(x, l)) - 2;
     177           3 :       y = int_LSW(gel(x, l));
     178          14 :       for (i = 0; i < j; i++, y = int_nextW(y), w = int_nextW(w)) *w = *y;
     179           3 :       if (l > 1) for (; i < t; i++, w = int_nextW(w)) *w = 0;
     180             :     }
     181             :   }
     182             :   else
     183             :   {
     184          13 :     long r = 0;
     185        1649 :     for (; l > 1; l--) int_set_int(gel(x, l), k, &w, &r);
     186          13 :     int_set_int(gel(x,1), m, &w, &r);
     187             :   }
     188          14 :   return int_normalize(z, 0);
     189             : }
     190             : 
     191             : GEN
     192          77 : binaire(GEN x)
     193             : {
     194             :   ulong m,u;
     195          77 :   long i,lx,ex,ly,tx=typ(x);
     196             :   GEN y,p1,p2;
     197             : 
     198          77 :   switch(tx)
     199             :   {
     200          42 :     case t_INT:
     201          42 :       return F2v_to_ZV_inplace( binary_zv(x) );
     202          21 :     case t_REAL:
     203          21 :       ex = expo(x);
     204          21 :       if (!signe(x)) return zerovec(maxss(-ex,0));
     205             : 
     206          14 :       lx=lg(x); y=cgetg(3,t_VEC);
     207          14 :       if (ex > bit_prec(x)) pari_err_PREC("binary");
     208          14 :       p1 = cgetg(maxss(ex,0)+2,t_VEC);
     209          14 :       p2 = cgetg(bit_prec(x)-ex,t_VEC);
     210          14 :       gel(y,1) = p1;
     211          14 :       gel(y,2) = p2;
     212          14 :       ly = -ex; ex++; m = HIGHBIT;
     213          14 :       if (ex<=0)
     214             :       {
     215          56 :         gel(p1,1) = gen_0; for (i=1; i <= -ex; i++) gel(p2,i) = gen_0;
     216           7 :         i=2;
     217             :       }
     218             :       else
     219             :       {
     220           7 :         ly=1;
     221          14 :         for (i=2; i<lx && ly<=ex; i++)
     222             :         {
     223           7 :           m=HIGHBIT; u=x[i];
     224             :           do
     225           7 :             { gel(p1,ly) = (m & u) ? gen_1 : gen_0; ly++; }
     226           7 :           while ((m>>=1) && ly<=ex);
     227             :         }
     228           7 :         ly=1;
     229           7 :         if (m) i--; else m=HIGHBIT;
     230             :       }
     231          46 :       for (; i<lx; i++)
     232             :       {
     233          32 :         u=x[i];
     234        1785 :         do { gel(p2,ly) = m & u ? gen_1 : gen_0; ly++; } while (m>>=1);
     235          32 :         m=HIGHBIT;
     236             :       }
     237          14 :       break;
     238             : 
     239           7 :     case t_VEC: case t_COL: case t_MAT:
     240           7 :       y = cgetg_copy(x, &lx);
     241          21 :       for (i=1; i<lx; i++) gel(y,i) = binaire(gel(x,i));
     242           7 :       break;
     243           7 :     default: pari_err_TYPE("binary",x);
     244             :       return NULL; /* LCOV_EXCL_LINE */
     245             :   }
     246          21 :   return y;
     247             : }
     248             : 
     249             : /* extract k bits (as ulong) starting at word *w plus *r bits */
     250             : INLINE ulong
     251   538874986 : int_get_bits(long k, GEN *w, long *r)
     252             : {
     253   538874986 :   ulong mask = (1UL << k) - 1;
     254   538874986 :   ulong a = (((ulong) **w) >> *r) & mask;
     255   538874986 :   *r += k;
     256   538874986 :   if (*r >= BITS_IN_LONG) {
     257   165173416 :     *r -= BITS_IN_LONG;
     258   165173416 :     *w = int_nextW(*w);
     259   165173416 :     if (*r)
     260   144572713 :       a |= ((ulong)**w << (k - *r)) & mask;
     261             :   }
     262   538874986 :   return a;
     263             : }
     264             : 
     265             : /* extract BITS_IN_LONG bits starting at word *w plus *r bits */
     266             : INLINE ulong
     267   169734749 : int_get_ulong(GEN *w, long *r)
     268             : {
     269   169734749 :   ulong a = ((ulong) **w) >> *r;
     270   169734749 :   *w = int_nextW(*w);
     271   169734749 :   if (*r)
     272   159522192 :     a |= ((ulong)**w << (BITS_IN_LONG - *r));
     273   169734749 :   return a;
     274             : }
     275             : 
     276             : /* extract k bits (as t_INT) starting at word *w plus *r bits */
     277             : INLINE GEN
     278   133465838 : int_get_int(long k, GEN *w, long *r)
     279             : {
     280   133465838 :   GEN z = cgetipos(nbits2lg(k));
     281   133419517 :   GEN y = int_LSW(z);
     282   303112297 :   for (; k >= BITS_IN_LONG; k -= BITS_IN_LONG) {
     283   169727916 :     *y = int_get_ulong(w, r);
     284   169692780 :     y = int_nextW(y);
     285             :   }
     286   133384381 :   if (k)
     287   133346879 :     *y = int_get_bits(k, w, r);
     288   133438266 :   return int_normalize(z, 0);
     289             : }
     290             : 
     291             : /* assume k < BITS_IN_LONG */
     292             : GEN
     293     4332910 : binary_2k_nv(GEN x, long k)
     294             : {
     295             :   long l, n, r;
     296             :   GEN v, w;
     297     4332910 :   if (k == 1) return binary_zv(x);
     298     4332910 :   if (!signe(x)) return cgetg(1, t_VECSMALL);
     299     2669216 :   n = expi(x) + 1;
     300     2669112 :   l = (n + k - 1) / k;
     301     2669112 :   v = cgetg(l + 1, t_VECSMALL);
     302     2708958 :   w = int_LSW(x);
     303     2708958 :   r = 0;
     304   405829282 :   for (; l > 1; l--) {
     305   403159911 :     uel(v, l) = int_get_bits(k, &w, &r);
     306   403120324 :     n -= k;
     307             :   }
     308     2669371 :   uel(v, 1) = int_get_bits(n, &w, &r);
     309     2669263 :   return v;
     310             : }
     311             : 
     312             : GEN
     313     3234338 : binary_2k(GEN x, long k)
     314             : {
     315             :   long l, n;
     316             :   GEN v, w, y, z;
     317     3234338 :   if (k == 1) return binaire(x);
     318     3234338 :   if (!signe(x)) return cgetg(1, t_VEC);
     319     3233393 :   n = expi(x) + 1;
     320     3235018 :   l = (n + k - 1) / k;
     321     3235018 :   v = cgetg(l + 1, t_VEC);
     322     3233787 :   w = int_LSW(x);
     323     3233787 :   if (!(k & (BITS_IN_LONG - 1))) {
     324          14 :     long m, t = k >> TWOPOTBITS_IN_LONG, u = lgefint(x) - 2;
     325          56 :     for (; l; l--) {
     326          42 :       m = minss(t, u);
     327          42 :       z = cgetipos(m + 2);
     328          42 :       y = int_LSW(z);
     329          88 :       for (; m; m--) {
     330          46 :         *y = *w;
     331          46 :         y = int_nextW(y);
     332          46 :         w = int_nextW(w);
     333             :       }
     334          42 :       gel(v, l) = int_normalize(z, 0);
     335          42 :       u -= t;
     336             :     }
     337             :   } else {
     338     3233773 :     long r = 0;
     339   133522514 :     for (; l > 1; l--, n -= k)
     340   130334140 :       gel(v, l) = int_get_int(k, &w, &r);
     341     3188374 :     gel(v, 1) = int_get_int(n, &w, &r);
     342             :   }
     343     3233112 :   return v;
     344             : }
     345             : 
     346             : /* return 1 if bit n of x is set, 0 otherwise */
     347             : long
     348          91 : bittest(GEN x, long n)
     349             : {
     350          91 :   if (typ(x) != t_INT) pari_err_TYPE("bittest",x);
     351          91 :   if (!signe(x) || n < 0) return 0;
     352          91 :   if (signe(x) < 0)
     353             :   {
     354           7 :     pari_sp ltop=avma;
     355           7 :     long b = !int_bit(inegate(x),n);
     356           7 :     set_avma(ltop);
     357           7 :     return b;
     358             :   }
     359          84 :   return int_bit(x, n);
     360             : }
     361             : 
     362             : GEN
     363          91 : gbittest(GEN x, long n) { return map_proto_lGL(bittest,x,n); }
     364             : 
     365             : /***********************************************************************/
     366             : /**                                                                   **/
     367             : /**                          BITMAP OPS                               **/
     368             : /** x & y (and), x | y (or), x ^ y (xor), ~x (neg), x & ~y (negimply) **/
     369             : /**                                                                   **/
     370             : /***********************************************************************/
     371             : /* Truncate a non-negative integer to a number of bits.  */
     372             : static GEN
     373          35 : ibittrunc(GEN x, long bits)
     374             : {
     375          35 :   long lowbits, known_zero_words, xl = lgefint(x) - 2;
     376          35 :   long len_out = nbits2nlong(bits);
     377             : 
     378          35 :   if (xl < len_out)
     379           8 :     return x;
     380             :       /* Check whether mask is trivial */
     381          27 :   lowbits = bits & (BITS_IN_LONG-1);
     382          27 :   if (!lowbits) {
     383           6 :     if (xl == len_out)
     384           6 :       return x;
     385          21 :   } else if (len_out <= xl) {
     386          21 :     GEN xi = int_W(x, len_out-1);
     387             :     /* Non-trival mask is given by a formula, if x is not
     388             :        normalized, this works even in the exceptional case */
     389          21 :     *xi &= (1L << lowbits) - 1;
     390          21 :     if (*xi && xl == len_out) return x;
     391             :   }
     392             :   /* Normalize */
     393          21 :   known_zero_words = xl - len_out;
     394          21 :   if (known_zero_words < 0) known_zero_words = 0;
     395          21 :   return int_normalize(x, known_zero_words);
     396             : }
     397             : 
     398             : GEN
     399         112 : gbitneg(GEN x, long bits)
     400             : {
     401         112 :   const ulong uzero = 0;
     402             :   long lowbits, xl, len_out, i;
     403             : 
     404         112 :   if (typ(x) != t_INT) pari_err_TYPE("bitwise negation",x);
     405         105 :   if (bits < -1)
     406           7 :     pari_err_DOMAIN("bitwise negation","exponent","<",gen_m1,stoi(bits));
     407          98 :   if (bits == -1) return inegate(x);
     408          56 :   if (bits == 0) return gen_0;
     409          56 :   if (signe(x) < 0) { /* Consider as if mod big power of 2 */
     410          21 :     pari_sp ltop = avma;
     411          21 :     return gerepileuptoint(ltop, ibittrunc(inegate(x), bits));
     412             :   }
     413          35 :   xl = lgefint(x);
     414          35 :   len_out = nbits2lg(bits);
     415          35 :   lowbits = bits & (BITS_IN_LONG-1);
     416          35 :   if (len_out > xl) /* Need to grow */
     417             :   {
     418          21 :     GEN out, outp, xp = int_MSW(x);
     419          21 :     out = cgetipos(len_out);
     420          21 :     outp = int_MSW(out);
     421          21 :     if (!lowbits)
     422           7 :       *outp = ~uzero;
     423             :     else
     424          14 :       *outp = (1L << lowbits) - 1;
     425          32 :     for (i = 3; i < len_out - xl + 2; i++)
     426             :     {
     427          11 :       outp = int_precW(outp); *outp = ~uzero;
     428             :     }
     429          35 :     for (     ; i < len_out; i++)
     430             :     {
     431          14 :       outp = int_precW(outp); *outp = ~*xp;
     432          14 :       xp   = int_precW(xp);
     433             :     }
     434          21 :     return out;
     435             :   }
     436          14 :   x = icopy(x);
     437          52 :   for (i = 2; i < xl; i++) x[i] = ~x[i];
     438          14 :   return ibittrunc(int_normalize(x,0), bits);
     439             : }
     440             : 
     441             : /* bitwise 'and' of two positive integers (any integers, but we ignore sign).
     442             :  * Inputs are not necessary normalized. */
     443             : GEN
     444    35870632 : ibitand(GEN x, GEN y)
     445             : {
     446             :   long lx, ly, lout;
     447             :   long *xp, *yp, *outp;
     448             :   GEN out;
     449             :   long i;
     450             : 
     451    35870632 :   if (!signe(x) || !signe(y)) return gen_0;
     452    35870590 :   lx=lgefint(x); ly=lgefint(y);
     453    35870590 :   lout = minss(lx,ly); /* > 2 */
     454    35870590 :   xp = int_LSW(x);
     455    35870590 :   yp = int_LSW(y);
     456    35870590 :   out = cgetipos(lout);
     457    35870590 :   outp = int_LSW(out);
     458    74236777 :   for (i=2; i<lout; i++)
     459             :   {
     460    38366187 :     *outp = (*xp) & (*yp);
     461    38366187 :     outp  = int_nextW(outp);
     462    38366187 :     xp    = int_nextW(xp);
     463    38366187 :     yp    = int_nextW(yp);
     464             :   }
     465    35870590 :   if ( !*int_MSW(out) ) out = int_normalize(out, 1);
     466    35870590 :   return out;
     467             : }
     468             : 
     469             : /* bitwise 'or' of absolute values of two integers */
     470             : GEN
     471         105 : ibitor(GEN x, GEN y)
     472             : {
     473             :   long lx, ly;
     474             :   long *xp, *yp, *outp;
     475             :   GEN  out;
     476             :   long i;
     477         105 :   if (!signe(x)) return absi(y);
     478          77 :   if (!signe(y)) return absi(x);
     479             : 
     480          77 :   lx = lgefint(x); xp = int_LSW(x);
     481          77 :   ly = lgefint(y); yp = int_LSW(y);
     482          77 :   if (lx < ly) swapspec(xp,yp,lx,ly);
     483             :   /* lx > 2 */
     484          77 :   out = cgetipos(lx);
     485          77 :   outp = int_LSW(out);
     486         202 :   for (i=2;i<ly;i++)
     487             :   {
     488         125 :     *outp = (*xp) | (*yp);
     489         125 :     outp  = int_nextW(outp);
     490         125 :     xp    = int_nextW(xp);
     491         125 :     yp    = int_nextW(yp);
     492             :   }
     493         149 :   for (   ;i<lx;i++)
     494             :   {
     495          72 :     *outp = *xp;
     496          72 :     outp  = int_nextW(outp);
     497          72 :     xp    = int_nextW(xp);
     498             :   }
     499             :   /* If input is normalized, this is not needed */
     500          77 :   if ( !*int_MSW(out) ) out = int_normalize(out, 1);
     501          77 :   return out;
     502             : }
     503             : 
     504             : /* bitwise 'xor' of absolute values of two integers */
     505             : GEN
     506         147 : ibitxor(GEN x, GEN y)
     507             : {
     508             :   long lx, ly;
     509             :   long *xp, *yp, *outp;
     510             :   GEN  out;
     511             :   long i;
     512         147 :   if (!signe(x)) return absi(y);
     513         105 :   if (!signe(y)) return absi(x);
     514             : 
     515         105 :   lx = lgefint(x); xp = int_LSW(x);
     516         105 :   ly = lgefint(y); yp = int_LSW(y);
     517         105 :   if (lx < ly) swapspec(xp,yp,lx,ly);
     518             :   /* lx > 2 */
     519         105 :   out = cgetipos(lx);
     520         105 :   outp = int_LSW(out);
     521         282 :   for (i=2;i<ly;i++)
     522             :   {
     523         177 :     *outp = (*xp) ^ (*yp);
     524         177 :     outp  = int_nextW(outp);
     525         177 :     xp    = int_nextW(xp);
     526         177 :     yp    = int_nextW(yp);
     527             :   }
     528         201 :   for (   ;i<lx;i++)
     529             :   {
     530          96 :     *outp = *xp;
     531          96 :     outp  = int_nextW(outp);
     532          96 :     xp    = int_nextW(xp);
     533             :   }
     534         105 :   if ( !*int_MSW(out) ) out = int_normalize(out, 1);
     535         105 :   return out;
     536             : }
     537             : 
     538             : /* bitwise 'negimply' of absolute values of two integers */
     539             : /* "negimply(x,y)" is ~(x => y) == ~(~x | y) == x & ~y   */
     540             : GEN
     541         203 : ibitnegimply(GEN x, GEN y)
     542             : {
     543             :   long lx, ly, lin;
     544             :   long *xp, *yp, *outp;
     545             :   GEN out;
     546             :   long i;
     547         203 :   if (!signe(x)) return gen_0;
     548         161 :   if (!signe(y)) return absi(x);
     549             : 
     550         147 :   lx = lgefint(x); xp = int_LSW(x);
     551         147 :   ly = lgefint(y); yp = int_LSW(y);
     552         147 :   lin = minss(lx,ly);
     553         147 :   out = cgetipos(lx);
     554         147 :   outp = int_LSW(out);
     555         390 :   for (i=2; i<lin; i++)
     556             :   {
     557         243 :     *outp = (*xp) & ~(*yp);
     558         243 :     outp  = int_nextW(outp);
     559         243 :     xp    = int_nextW(xp);
     560         243 :     yp    = int_nextW(yp);
     561             :   }
     562         211 :   for (   ;i<lx;i++)
     563             :   {
     564          64 :     *outp = *xp;
     565          64 :     outp  = int_nextW(outp);
     566          64 :     xp    = int_nextW(xp);
     567             :   }
     568         147 :   if ( !*int_MSW(out) ) out = int_normalize(out, 1);
     569         147 :   return out;
     570             : }
     571             : 
     572             : static int
     573    35871087 : signs(GEN x, GEN y) { return (((signe(x) >= 0) << 1) | (signe(y) >= 0)); }
     574             : static void
     575    35871283 : checkint2(const char *f,GEN x, GEN y)
     576    35871283 : { if (typ(x)!=t_INT || typ(y)!=t_INT) pari_err_TYPE2(f,x,y); }
     577             : 
     578             : GEN
     579         196 : gbitor(GEN x, GEN y)
     580             : {
     581         196 :   pari_sp ltop = avma;
     582             :   GEN z;
     583             : 
     584         196 :   checkint2("bitwise or",x,y);
     585         147 :   switch (signs(x, y))
     586             :   {
     587          70 :     case 3: /*1,1*/
     588          70 :       return ibitor(x,y);
     589          42 :     case 2: /*1,-1*/
     590          42 :       z = ibitnegimply(inegate(y),x);
     591          42 :       break;
     592          14 :     case 1: /*-1,1*/
     593          14 :       z = ibitnegimply(inegate(x),y);
     594          14 :       break;
     595          21 :     default: /*-1,-1*/
     596          21 :       z = ibitand(inegate(x),inegate(y));
     597          21 :       break;
     598             :   }
     599          77 :   return gerepileuptoint(ltop, inegate(z));
     600             : }
     601             : 
     602             : GEN
     603    35870695 : gbitand(GEN x, GEN y)
     604             : {
     605    35870695 :   pari_sp ltop = avma;
     606             :   GEN z;
     607             : 
     608    35870695 :   checkint2("bitwise and",x,y);
     609    35870646 :   switch (signs(x, y))
     610             :   {
     611    35870569 :     case 3: /*1,1*/
     612    35870569 :       return ibitand(x,y);
     613          42 :     case 2: /*1,-1*/
     614          42 :       z = ibitnegimply(x,inegate(y));
     615          42 :       break;
     616          14 :     case 1: /*-1,1*/
     617          14 :       z = ibitnegimply(y,inegate(x));
     618          14 :       break;
     619          21 :     default: /*-1,-1*/
     620          21 :       z = inegate(ibitor(inegate(x),inegate(y)));
     621          21 :       break;
     622             :   }
     623          77 :   return gerepileuptoint(ltop, z);
     624             : }
     625             : 
     626             : GEN
     627         196 : gbitxor(GEN x, GEN y)
     628             : {
     629         196 :   pari_sp ltop = avma;
     630             :   GEN z;
     631             : 
     632         196 :   checkint2("bitwise xor",x,y);
     633         147 :   switch (signs(x, y))
     634             :   {
     635          70 :     case 3: /*1,1*/
     636          70 :       return ibitxor(x,y);
     637          42 :     case 2: /*1,-1*/
     638          42 :       z = inegate(ibitxor(x,inegate(y)));
     639          42 :       break;
     640          14 :     case 1: /*-1,1*/
     641          14 :       z = inegate(ibitxor(inegate(x),y));
     642          14 :       break;
     643          21 :     default: /*-1,-1*/
     644          21 :       z = ibitxor(inegate(x),inegate(y));
     645          21 :       break;
     646             :   }
     647          77 :   return gerepileuptoint(ltop,z);
     648             : }
     649             : 
     650             : /* x & ~y */
     651             : GEN
     652         196 : gbitnegimply(GEN x, GEN y)
     653             : {
     654         196 :   pari_sp ltop = avma;
     655             :   GEN z;
     656             : 
     657         196 :   checkint2("bitwise negated imply",x,y);
     658         147 :   switch (signs(x, y))
     659             :   {
     660          70 :     case 3: /*1,1*/
     661          70 :       return ibitnegimply(x,y);
     662          42 :     case 2: /*1,-1*/
     663          42 :       z = ibitand(x,inegate(y));
     664          42 :       break;
     665          14 :     case 1: /*-1,1*/
     666          14 :       z = inegate(ibitor(y,inegate(x)));
     667          14 :       break;
     668          21 :     default: /*-1,-1*/
     669          21 :       z = ibitnegimply(inegate(y),inegate(x));
     670          21 :       break;
     671             :   }
     672          77 :   return gerepileuptoint(ltop,z);
     673             : }
     674             : 
     675             : long
     676    22556440 : hammingl(ulong w)
     677             : {
     678             : #if 0
     679             :   return __builtin_popcountl(w);
     680             : #endif
     681             :   static long byte_weight[] = {
     682             :     0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
     683             :     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
     684             :     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
     685             :     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
     686             :     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
     687             :     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
     688             :     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
     689             :     3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
     690             :   };
     691    22556440 :   long sum = 0;
     692    87780439 :   while (w) { sum += byte_weight[w & 255]; w >>= 8; }
     693    22556440 :   return sum;
     694             : }
     695             : 
     696             : /* number of non-zero entries among x[a], ..., x[b] */
     697             : static long
     698         714 : hamming_slice(GEN x, long a, long b)
     699             : {
     700         714 :   long i, nb = 0;
     701       71442 :   for (i = a; i <= b; i++)
     702       70728 :     if (!gequal0(gel(x,i))) nb++;
     703         714 :   return nb;
     704             : }
     705             : static long
     706           7 : hamming_mat(GEN x)
     707             : {
     708           7 :   long i, lx = lg(x), nb = 0;
     709         707 :   for (i = 1; i < lx; i++) nb += hammingweight(gel(x,i));
     710           7 :   return nb;
     711             : }
     712             : static long
     713         791 : hamming_vecsmall(GEN x)
     714             : {
     715         791 :   long i, lx = lg(x), nb = 0;
     716        1855 :   for (i = 1; i < lx; i++)
     717        1064 :     if (x[i]) nb++;
     718         791 :   return nb;
     719             : }
     720             : static long
     721      165871 : hamming_int(GEN n)
     722             : {
     723      165871 :   long lx = lgefint(n), i, sum;
     724      165871 :   if (lx == 2) return 0;
     725      165871 :   sum = hammingl(n[2]);
     726      166017 :   for (i = 3; i < lx; i++) sum += hammingl(n[i]);
     727      165871 :   return sum;
     728             : }
     729             : 
     730             : long
     731      167390 : hammingweight(GEN n)
     732             : {
     733      167390 :   switch(typ(n))
     734             :   {
     735      165871 :     case t_INT: return hamming_int(n);
     736         707 :     case t_VEC:
     737         707 :     case t_COL: return hamming_slice(n, 1, lg(n)-1);
     738           7 :     case t_POL: return hamming_slice(n, 2, lg(n)-1);
     739         791 :     case t_VECSMALL: return hamming_vecsmall(n);
     740           7 :     case t_MAT: return hamming_mat(n);
     741             :   }
     742           7 :   pari_err_TYPE("hammingweight", n);
     743             :   return 0;/*LCOV_EXCL_LINE*/
     744             : }

Generated by: LCOV version 1.13