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 30417-3115e90663) Lines: 430 444 96.8 %
Date: 2025-07-28 09:23:22 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   799273066 : int_set_bits(ulong a, long k, GEN *w, long *r)
     104             : {
     105   799273066 :   if (*r) {
     106   755983063 :     **w |= a << *r;
     107   755983063 :     a >>= BITS_IN_LONG - *r;
     108             :   } else {
     109    43290003 :     **w = a;
     110    43290003 :     a = 0;
     111             :   }
     112   799273066 :   *r += k;
     113   799273066 :   if (*r >= BITS_IN_LONG) {
     114   419270740 :     *w = int_nextW(*w);
     115   419270740 :     *r -= BITS_IN_LONG;
     116   552109855 :     for (; *r >= BITS_IN_LONG; *r -= BITS_IN_LONG) {
     117   132839115 :       **w = a;
     118   132839115 :       a = 0;
     119   132839115 :       *w = int_nextW(*w);
     120             :     }
     121   419270740 :     if (*r)
     122   392799956 :       **w = a;
     123             :   }
     124   799273066 : }
     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    17379918 : nv_fromdigits_2k(GEN x, long k)
     149             : {
     150    17379918 :   long l = lg(x) - 1, r;
     151             :   GEN w, z;
     152    17379918 :   if (k == 1) return bits_to_int(x, l);
     153    17379918 :   if (!l) return gen_0;
     154    17379918 :   z = cgetipos(nbits2lg(k * l));
     155    17396570 :   w = int_LSW(z);
     156    17396570 :   r = 0;
     157   816467683 :   for (; l; l--)
     158   799081786 :     int_set_bits(uel(x, l), k, &w, &r);
     159    17385897 :   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   847492597 : int_get_bits(long k, GEN *w, long *r)
     253             : {
     254   847492597 :   ulong mask = (1UL << k) - 1;
     255   847492597 :   ulong a = (((ulong) **w) >> *r) & mask;
     256   847492597 :   *r += k;
     257   847492597 :   if (*r >= BITS_IN_LONG) {
     258   257221849 :     *r -= BITS_IN_LONG;
     259   257221849 :     *w = int_nextW(*w);
     260   257221849 :     if (*r)
     261   225921916 :       a |= ((ulong)**w << (k - *r)) & mask;
     262             :   }
     263   847492597 :   return a;
     264             : }
     265             : 
     266             : /* extract BITS_IN_LONG bits starting at word *w plus *r bits */
     267             : INLINE ulong
     268   313051243 : int_get_ulong(GEN *w, long *r)
     269             : {
     270   313051243 :   ulong a = ((ulong) **w) >> *r;
     271   313051243 :   *w = int_nextW(*w);
     272   313051243 :   if (*r)
     273   295256886 :     a |= ((ulong)**w << (BITS_IN_LONG - *r));
     274   313051243 :   return a;
     275             : }
     276             : 
     277             : /* extract k bits (as t_INT) starting at word *w plus *r bits */
     278             : INLINE GEN
     279   229202277 : int_get_int(long k, GEN *w, long *r)
     280             : {
     281   229202277 :   GEN z = cgetipos(nbits2lg(k));
     282   229116975 :   GEN y = int_LSW(z);
     283   542173635 :   for (; k >= BITS_IN_LONG; k -= BITS_IN_LONG) {
     284   313053975 :     *y = int_get_ulong(w, r);
     285   313056660 :     y = int_nextW(y);
     286             :   }
     287   229119660 :   if (k)
     288   229028952 :     *y = int_get_bits(k, w, r);
     289   229145390 :   return int_normalize(z, 0);
     290             : }
     291             : 
     292             : /* assume k < BITS_IN_LONG */
     293             : GEN
     294     5683889 : binary_2k_nv(GEN x, long k)
     295             : {
     296             :   long l, n, r;
     297             :   GEN v, w;
     298     5683889 :   if (k == 1) return binary_zv(x);
     299     5683889 :   if (!signe(x)) return cgetg(1, t_VECSMALL);
     300     3957976 :   n = expi(x) + 1;
     301     3957903 :   l = (n + k - 1) / k;
     302     3957903 :   v = cgetg(l + 1, t_VECSMALL);
     303     3946425 :   w = int_LSW(x);
     304     3946425 :   r = 0;
     305   618533580 :   for (; l > 1; l--) {
     306   614575516 :     uel(v, l) = int_get_bits(k, &w, &r);
     307   614587155 :     n -= k;
     308             :   }
     309     3958064 :   uel(v, 1) = int_get_bits(n, &w, &r);
     310     3958061 :   return v;
     311             : }
     312             : 
     313             : GEN
     314     5578299 : binary_2k(GEN x, long k)
     315             : {
     316             :   long l, n;
     317             :   GEN v, w, y, z;
     318     5578299 :   if (k == 1) return binaire(x);
     319     5578299 :   if (!signe(x)) return cgetg(1, t_VEC);
     320     5576422 :   n = expi(x) + 1;
     321     5575563 :   l = (n + k - 1) / k;
     322     5575563 :   v = cgetg(l + 1, t_VEC);
     323     5575716 :   w = int_LSW(x);
     324     5575716 :   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     5575702 :     long r = 0;
     340   229260479 :     for (; l > 1; l--, n -= k)
     341   223700022 :       gel(v, l) = int_get_int(k, &w, &r);
     342     5560457 :     gel(v, 1) = int_get_int(n, &w, &r);
     343             :   }
     344     5575445 :   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 av = avma;
     356           7 :     long b = !int_bit(inegate(x),n);
     357           7 :     return gc_long(av, b);
     358             :   }
     359          84 :   return int_bit(x, n);
     360             : }
     361             : 
     362             : void
     363         210 : bitset(GEN x, long n)
     364             : {
     365         210 :   long r, q = dvmdsBIL(n, &r), e;
     366         210 :   if (typ(x) != t_INT) pari_err_TYPE("bitset",x);
     367         210 :   if (signe(x)==0) pari_err_DOMAIN("bitset","x","==",gen_0,x);
     368         203 :   if (n < 0) pari_err_DOMAIN("bitset","n","<",gen_0,stoi(n));
     369         203 :   e = expi(x);
     370         203 :   if (n > e) pari_err_DOMAIN("bitset","n",">",utoi(e),stoi(n));
     371         189 :   *int_W(x,q) |= 1UL<<r;
     372         189 : }
     373             : 
     374             : void
     375         721 : bitflip(GEN x, long n)
     376             : {
     377         721 :   long r, q = dvmdsBIL(n, &r), e;
     378         721 :   if (typ(x) != t_INT) pari_err_TYPE("bitflip",x);
     379         714 :   if (signe(x)==0) pari_err_DOMAIN("bitset","x","==",gen_0,x);
     380         714 :   if (n < 0) pari_err_DOMAIN("bitflip","n","<",gen_0,stoi(n));
     381         714 :   e = expi(x);
     382         714 :   if (n >= e) pari_err_DOMAIN("bitflip","n",">=",utoi(e),stoi(n));
     383         700 :   *int_W(x,q) ^= 1UL<<r;
     384         700 : }
     385             : 
     386             : void
     387         546 : bitclear(GEN x, long n)
     388             : {
     389         546 :   long r, q = dvmdsBIL(n, &r), e;
     390         546 :   if (typ(x) != t_INT) pari_err_TYPE("bitclear",x);
     391         539 :   if (signe(x)==0) pari_err_DOMAIN("bitset","x","==",gen_0,x);
     392         539 :   if (n < 0) pari_err_DOMAIN("bitclear","n","<",gen_0,stoi(n));
     393         539 :   e = expi(x);
     394         539 :   if (n >= e) pari_err_DOMAIN("bitclear","n",">=",utoi(e),stoi(n));
     395         525 :   *int_W(x,q) &= ~(1UL<<r);
     396         525 : }
     397             : 
     398             : GEN
     399          91 : gbittest(GEN x, long n) { return map_proto_lGL(bittest,x,n); }
     400             : 
     401             : /***********************************************************************/
     402             : /**                                                                   **/
     403             : /**                          BITMAP OPS                               **/
     404             : /** x & y (and), x | y (or), x ^ y (xor), ~x (neg), x & ~y (negimply) **/
     405             : /**                                                                   **/
     406             : /***********************************************************************/
     407             : /* Truncate a nonnegative integer to a number of bits.  */
     408             : static GEN
     409          35 : ibittrunc(GEN x, long bits)
     410             : {
     411          35 :   long lowbits, known_zero_words, xl = lgefint(x) - 2;
     412          35 :   long len_out = nbits2nlong(bits);
     413             : 
     414          35 :   if (xl < len_out)
     415           8 :     return x;
     416             :       /* Check whether mask is trivial */
     417          27 :   lowbits = bits & (BITS_IN_LONG-1);
     418          27 :   if (!lowbits) {
     419           6 :     if (xl == len_out)
     420           6 :       return x;
     421          21 :   } else if (len_out <= xl) {
     422          21 :     GEN xi = int_W(x, len_out-1);
     423             :     /* Non-trival mask is given by a formula, if x is not
     424             :        normalized, this works even in the exceptional case */
     425          21 :     *xi &= (1L << lowbits) - 1;
     426          21 :     if (*xi && xl == len_out) return x;
     427             :   }
     428             :   /* Normalize */
     429          21 :   known_zero_words = xl - len_out;
     430          21 :   if (known_zero_words < 0) known_zero_words = 0;
     431          21 :   return int_normalize(x, known_zero_words);
     432             : }
     433             : 
     434             : GEN
     435         112 : gbitneg(GEN x, long bits)
     436             : {
     437         112 :   const ulong uzero = 0;
     438             :   long lowbits, xl, len_out, i;
     439             : 
     440         112 :   if (typ(x) != t_INT) pari_err_TYPE("bitwise negation",x);
     441         105 :   if (bits < -1)
     442           7 :     pari_err_DOMAIN("bitwise negation","exponent","<",gen_m1,stoi(bits));
     443          98 :   if (bits == -1) return inegate(x);
     444          56 :   if (bits == 0) return gen_0;
     445          56 :   if (signe(x) < 0) { /* Consider as if mod big power of 2 */
     446          21 :     pari_sp ltop = avma;
     447          21 :     return gc_INT(ltop, ibittrunc(inegate(x), bits));
     448             :   }
     449          35 :   xl = lgefint(x);
     450          35 :   len_out = nbits2lg(bits);
     451          35 :   lowbits = bits & (BITS_IN_LONG-1);
     452          35 :   if (len_out > xl) /* Need to grow */
     453             :   {
     454          21 :     GEN out, outp, xp = int_MSW(x);
     455          21 :     out = cgetipos(len_out);
     456          21 :     outp = int_MSW(out);
     457          21 :     if (!lowbits)
     458           7 :       *outp = ~uzero;
     459             :     else
     460          14 :       *outp = (1L << lowbits) - 1;
     461          32 :     for (i = 3; i < len_out - xl + 2; i++)
     462             :     {
     463          11 :       outp = int_precW(outp); *outp = ~uzero;
     464             :     }
     465          35 :     for (     ; i < len_out; i++)
     466             :     {
     467          14 :       outp = int_precW(outp); *outp = ~*xp;
     468          14 :       xp   = int_precW(xp);
     469             :     }
     470          21 :     return out;
     471             :   }
     472          14 :   x = icopy(x);
     473          52 :   for (i = 2; i < xl; i++) x[i] = ~x[i];
     474          14 :   return ibittrunc(int_normalize(x,0), bits);
     475             : }
     476             : 
     477             : /* bitwise 'and' of two positive integers (any integers, but we ignore sign).
     478             :  * Inputs are not necessary normalized. */
     479             : GEN
     480    37267461 : ibitand(GEN x, GEN y)
     481             : {
     482             :   long lx, ly, lout;
     483             :   long *xp, *yp, *outp;
     484             :   GEN out;
     485             :   long i;
     486             : 
     487    37267461 :   if (!signe(x) || !signe(y)) return gen_0;
     488    37267419 :   lx=lgefint(x); ly=lgefint(y);
     489    37267419 :   lout = minss(lx,ly); /* > 2 */
     490    37267419 :   xp = int_LSW(x);
     491    37267419 :   yp = int_LSW(y);
     492    37267419 :   out = cgetipos(lout);
     493    37267419 :   outp = int_LSW(out);
     494    77129244 :   for (i=2; i<lout; i++)
     495             :   {
     496    39861825 :     *outp = (*xp) & (*yp);
     497    39861825 :     outp  = int_nextW(outp);
     498    39861825 :     xp    = int_nextW(xp);
     499    39861825 :     yp    = int_nextW(yp);
     500             :   }
     501    37267419 :   if ( !*int_MSW(out) ) out = int_normalize(out, 1);
     502    37267419 :   return out;
     503             : }
     504             : 
     505             : /* bitwise 'or' of absolute values of two integers */
     506             : GEN
     507         105 : ibitor(GEN x, GEN y)
     508             : {
     509             :   long lx, ly;
     510             :   long *xp, *yp, *outp;
     511             :   GEN  out;
     512             :   long i;
     513         105 :   if (!signe(x)) return absi(y);
     514          77 :   if (!signe(y)) return absi(x);
     515             : 
     516          77 :   lx = lgefint(x); xp = int_LSW(x);
     517          77 :   ly = lgefint(y); yp = int_LSW(y);
     518          77 :   if (lx < ly) swapspec(xp,yp,lx,ly);
     519             :   /* lx > 2 */
     520          77 :   out = cgetipos(lx);
     521          77 :   outp = int_LSW(out);
     522         202 :   for (i=2;i<ly;i++)
     523             :   {
     524         125 :     *outp = (*xp) | (*yp);
     525         125 :     outp  = int_nextW(outp);
     526         125 :     xp    = int_nextW(xp);
     527         125 :     yp    = int_nextW(yp);
     528             :   }
     529         149 :   for (   ;i<lx;i++)
     530             :   {
     531          72 :     *outp = *xp;
     532          72 :     outp  = int_nextW(outp);
     533          72 :     xp    = int_nextW(xp);
     534             :   }
     535             :   /* If input is normalized, this is not needed */
     536          77 :   if ( !*int_MSW(out) ) out = int_normalize(out, 1);
     537          77 :   return out;
     538             : }
     539             : 
     540             : /* bitwise 'xor' of absolute values of two integers */
     541             : GEN
     542         147 : ibitxor(GEN x, GEN y)
     543             : {
     544             :   long lx, ly;
     545             :   long *xp, *yp, *outp;
     546             :   GEN  out;
     547             :   long i;
     548         147 :   if (!signe(x)) return absi(y);
     549         105 :   if (!signe(y)) return absi(x);
     550             : 
     551         105 :   lx = lgefint(x); xp = int_LSW(x);
     552         105 :   ly = lgefint(y); yp = int_LSW(y);
     553         105 :   if (lx < ly) swapspec(xp,yp,lx,ly);
     554             :   /* lx > 2 */
     555         105 :   out = cgetipos(lx);
     556         105 :   outp = int_LSW(out);
     557         282 :   for (i=2;i<ly;i++)
     558             :   {
     559         177 :     *outp = (*xp) ^ (*yp);
     560         177 :     outp  = int_nextW(outp);
     561         177 :     xp    = int_nextW(xp);
     562         177 :     yp    = int_nextW(yp);
     563             :   }
     564         201 :   for (   ;i<lx;i++)
     565             :   {
     566          96 :     *outp = *xp;
     567          96 :     outp  = int_nextW(outp);
     568          96 :     xp    = int_nextW(xp);
     569             :   }
     570         105 :   if ( !*int_MSW(out) ) out = int_normalize(out, 1);
     571         105 :   return out;
     572             : }
     573             : 
     574             : /* bitwise 'negimply' of absolute values of two integers */
     575             : /* "negimply(x,y)" is ~(x => y) == ~(~x | y) == x & ~y   */
     576             : GEN
     577         203 : ibitnegimply(GEN x, GEN y)
     578             : {
     579             :   long lx, ly, lin;
     580             :   long *xp, *yp, *outp;
     581             :   GEN out;
     582             :   long i;
     583         203 :   if (!signe(x)) return gen_0;
     584         161 :   if (!signe(y)) return absi(x);
     585             : 
     586         147 :   lx = lgefint(x); xp = int_LSW(x);
     587         147 :   ly = lgefint(y); yp = int_LSW(y);
     588         147 :   lin = minss(lx,ly);
     589         147 :   out = cgetipos(lx);
     590         147 :   outp = int_LSW(out);
     591         390 :   for (i=2; i<lin; i++)
     592             :   {
     593         243 :     *outp = (*xp) & ~(*yp);
     594         243 :     outp  = int_nextW(outp);
     595         243 :     xp    = int_nextW(xp);
     596         243 :     yp    = int_nextW(yp);
     597             :   }
     598         211 :   for (   ;i<lx;i++)
     599             :   {
     600          64 :     *outp = *xp;
     601          64 :     outp  = int_nextW(outp);
     602          64 :     xp    = int_nextW(xp);
     603             :   }
     604         147 :   if ( !*int_MSW(out) ) out = int_normalize(out, 1);
     605         147 :   return out;
     606             : }
     607             : 
     608             : static int
     609    37267916 : signs(GEN x, GEN y) { return (((signe(x) >= 0) << 1) | (signe(y) >= 0)); }
     610             : static void
     611    37268112 : checkint2(const char *f,GEN x, GEN y)
     612    37268112 : { if (typ(x)!=t_INT || typ(y)!=t_INT) pari_err_TYPE2(f,x,y); }
     613             : 
     614             : GEN
     615         196 : gbitor(GEN x, GEN y)
     616             : {
     617         196 :   pari_sp ltop = avma;
     618             :   GEN z;
     619             : 
     620         196 :   checkint2("bitwise or",x,y);
     621         147 :   switch (signs(x, y))
     622             :   {
     623          70 :     case 3: /*1,1*/
     624          70 :       return ibitor(x,y);
     625          42 :     case 2: /*1,-1*/
     626          42 :       z = ibitnegimply(inegate(y),x);
     627          42 :       break;
     628          14 :     case 1: /*-1,1*/
     629          14 :       z = ibitnegimply(inegate(x),y);
     630          14 :       break;
     631          21 :     default: /*-1,-1*/
     632          21 :       z = ibitand(inegate(x),inegate(y));
     633          21 :       break;
     634             :   }
     635          77 :   return gc_INT(ltop, inegate(z));
     636             : }
     637             : 
     638             : GEN
     639    37267524 : gbitand(GEN x, GEN y)
     640             : {
     641    37267524 :   pari_sp ltop = avma;
     642             :   GEN z;
     643             : 
     644    37267524 :   checkint2("bitwise and",x,y);
     645    37267475 :   switch (signs(x, y))
     646             :   {
     647    37267398 :     case 3: /*1,1*/
     648    37267398 :       return ibitand(x,y);
     649          42 :     case 2: /*1,-1*/
     650          42 :       z = ibitnegimply(x,inegate(y));
     651          42 :       break;
     652          14 :     case 1: /*-1,1*/
     653          14 :       z = ibitnegimply(y,inegate(x));
     654          14 :       break;
     655          21 :     default: /*-1,-1*/
     656          21 :       z = inegate(ibitor(inegate(x),inegate(y)));
     657          21 :       break;
     658             :   }
     659          77 :   return gc_INT(ltop, z);
     660             : }
     661             : 
     662             : GEN
     663         196 : gbitxor(GEN x, GEN y)
     664             : {
     665         196 :   pari_sp ltop = avma;
     666             :   GEN z;
     667             : 
     668         196 :   checkint2("bitwise xor",x,y);
     669         147 :   switch (signs(x, y))
     670             :   {
     671          70 :     case 3: /*1,1*/
     672          70 :       return ibitxor(x,y);
     673          42 :     case 2: /*1,-1*/
     674          42 :       z = inegate(ibitxor(x,inegate(y)));
     675          42 :       break;
     676          14 :     case 1: /*-1,1*/
     677          14 :       z = inegate(ibitxor(inegate(x),y));
     678          14 :       break;
     679          21 :     default: /*-1,-1*/
     680          21 :       z = ibitxor(inegate(x),inegate(y));
     681          21 :       break;
     682             :   }
     683          77 :   return gc_INT(ltop,z);
     684             : }
     685             : 
     686             : /* x & ~y */
     687             : GEN
     688         196 : gbitnegimply(GEN x, GEN y)
     689             : {
     690         196 :   pari_sp ltop = avma;
     691             :   GEN z;
     692             : 
     693         196 :   checkint2("bitwise negated imply",x,y);
     694         147 :   switch (signs(x, y))
     695             :   {
     696          70 :     case 3: /*1,1*/
     697          70 :       return ibitnegimply(x,y);
     698          42 :     case 2: /*1,-1*/
     699          42 :       z = ibitand(x,inegate(y));
     700          42 :       break;
     701          14 :     case 1: /*-1,1*/
     702          14 :       z = inegate(ibitor(y,inegate(x)));
     703          14 :       break;
     704          21 :     default: /*-1,-1*/
     705          21 :       z = ibitnegimply(inegate(y),inegate(x));
     706          21 :       break;
     707             :   }
     708          77 :   return gc_INT(ltop,z);
     709             : }
     710             : 
     711             : /* number of nonzero entries among x[a], ..., x[b] */
     712             : static long
     713         714 : hamming_slice(GEN x, long a, long b)
     714             : {
     715         714 :   long i, nb = 0;
     716       71442 :   for (i = a; i <= b; i++)
     717       70728 :     if (!gequal0(gel(x,i))) nb++;
     718         714 :   return nb;
     719             : }
     720             : static long
     721           7 : hamming_mat(GEN x)
     722             : {
     723           7 :   long i, lx = lg(x), nb = 0;
     724         707 :   for (i = 1; i < lx; i++) nb += hammingweight(gel(x,i));
     725           7 :   return nb;
     726             : }
     727             : static long
     728         889 : hamming_vecsmall(GEN x)
     729             : {
     730         889 :   long i, lx = lg(x), nb = 0;
     731        2086 :   for (i = 1; i < lx; i++)
     732        1197 :     if (x[i]) nb++;
     733         889 :   return nb;
     734             : }
     735             : static long
     736          21 : hamming_int(GEN n)
     737             : {
     738          21 :   long lx = lgefint(n), i, sum;
     739          21 :   if (lx == 2) return 0;
     740          21 :   sum = hammingu(n[2]);
     741          21 :   for (i = 3; i < lx; i++) sum += hammingu(n[i]);
     742          21 :   return sum;
     743             : }
     744             : 
     745             : long
     746        1638 : hammingweight(GEN n)
     747             : {
     748        1638 :   switch(typ(n))
     749             :   {
     750          21 :     case t_INT: return hamming_int(n);
     751         707 :     case t_VEC:
     752         707 :     case t_COL: return hamming_slice(n, 1, lg(n)-1);
     753           7 :     case t_POL: return hamming_slice(n, 2, lg(n)-1);
     754         889 :     case t_VECSMALL: return hamming_vecsmall(n);
     755           7 :     case t_MAT: return hamming_mat(n);
     756             :   }
     757           7 :   pari_err_TYPE("hammingweight", n);
     758             :   return 0;/*LCOV_EXCL_LINE*/
     759             : }

Generated by: LCOV version 1.16