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

Generated by: LCOV version 1.16