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 : }
|
