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 875610988 : int_set_bits(ulong a, long k, GEN *w, long *r)
104 : {
105 875610988 : if (*r) {
106 828746233 : **w |= a << *r;
107 828746233 : a >>= BITS_IN_LONG - *r;
108 : } else {
109 46864755 : **w = a;
110 46864755 : a = 0;
111 : }
112 875610988 : *r += k;
113 875610988 : if (*r >= BITS_IN_LONG) {
114 461207852 : *w = int_nextW(*w);
115 461207852 : *r -= BITS_IN_LONG;
116 598557604 : for (; *r >= BITS_IN_LONG; *r -= BITS_IN_LONG) {
117 137349752 : **w = a;
118 137349752 : a = 0;
119 137349752 : *w = int_nextW(*w);
120 : }
121 461207852 : if (*r)
122 432373592 : **w = a;
123 : }
124 875610988 : }
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 18593101 : nv_fromdigits_2k(GEN x, long k)
149 : {
150 18593101 : long l = lg(x) - 1, r;
151 : GEN w, z;
152 18593101 : if (k == 1) return bits_to_int(x, l);
153 18593101 : if (!l) return gen_0;
154 18593101 : z = cgetipos(nbits2lg(k * l));
155 18593101 : w = int_LSW(z);
156 18593101 : r = 0;
157 894011326 : for (; l; l--)
158 875418225 : int_set_bits(uel(x, l), k, &w, &r);
159 18593101 : 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 928146183 : int_get_bits(long k, GEN *w, long *r)
253 : {
254 928146183 : ulong mask = (1UL << k) - 1;
255 928146183 : ulong a = (((ulong) **w) >> *r) & mask;
256 928146183 : *r += k;
257 928146183 : if (*r >= BITS_IN_LONG) {
258 289304694 : *r -= BITS_IN_LONG;
259 289304694 : *w = int_nextW(*w);
260 289304694 : if (*r)
261 255296884 : a |= ((ulong)**w << (k - *r)) & mask;
262 : }
263 928146183 : return a;
264 : }
265 :
266 : /* extract BITS_IN_LONG bits starting at word *w plus *r bits */
267 : INLINE ulong
268 332409272 : int_get_ulong(GEN *w, long *r)
269 : {
270 332409272 : ulong a = ((ulong) **w) >> *r;
271 332409272 : *w = int_nextW(*w);
272 332409272 : if (*r)
273 313351706 : a |= ((ulong)**w << (BITS_IN_LONG - *r));
274 332409272 : return a;
275 : }
276 :
277 : /* extract k bits (as t_INT) starting at word *w plus *r bits */
278 : INLINE GEN
279 247073924 : int_get_int(long k, GEN *w, long *r)
280 : {
281 247073924 : GEN z = cgetipos(nbits2lg(k));
282 247073924 : GEN y = int_LSW(z);
283 579483196 : for (; k >= BITS_IN_LONG; k -= BITS_IN_LONG) {
284 332409272 : *y = int_get_ulong(w, r);
285 332409272 : y = int_nextW(y);
286 : }
287 247073924 : if (k)
288 246962551 : *y = int_get_bits(k, w, r);
289 247073924 : return int_normalize(z, 0);
290 : }
291 :
292 : /* assume k < BITS_IN_LONG */
293 : GEN
294 6474075 : binary_2k_nv(GEN x, long k)
295 : {
296 : long l, n, r;
297 : GEN v, w;
298 6474075 : if (k == 1) return binary_zv(x);
299 6474075 : if (!signe(x)) return cgetg(1, t_VECSMALL);
300 4367514 : n = expi(x) + 1;
301 4367514 : l = (n + k - 1) / k;
302 4367514 : v = cgetg(l + 1, t_VECSMALL);
303 4367514 : w = int_LSW(x);
304 4367514 : r = 0;
305 681183632 : for (; l > 1; l--) {
306 676816118 : uel(v, l) = int_get_bits(k, &w, &r);
307 676816118 : n -= k;
308 : }
309 4367514 : uel(v, 1) = int_get_bits(n, &w, &r);
310 4367514 : return v;
311 : }
312 :
313 : GEN
314 5981010 : binary_2k(GEN x, long k)
315 : {
316 : long l, n;
317 : GEN v, w, y, z;
318 5981010 : if (k == 1) return binaire(x);
319 5981010 : if (!signe(x)) return cgetg(1, t_VEC);
320 5978790 : n = expi(x) + 1;
321 5978790 : l = (n + k - 1) / k;
322 5978790 : v = cgetg(l + 1, t_VEC);
323 5978790 : w = int_LSW(x);
324 5978790 : if (!(k & (BITS_IN_LONG - 1))) {
325 938 : long m, t = k >> TWOPOTBITS_IN_LONG, u = lgefint(x) - 2;
326 9905 : for (; l; l--) {
327 8967 : m = minss(t, u);
328 8967 : z = cgetipos(m + 2);
329 8967 : y = int_LSW(z);
330 19085 : for (; m; m--) {
331 10118 : *y = *w;
332 10118 : y = int_nextW(y);
333 10118 : w = int_nextW(w);
334 : }
335 8967 : gel(v, l) = int_normalize(z, 0);
336 8967 : u -= t;
337 : }
338 : } else {
339 5977852 : long r = 0;
340 247073924 : for (; l > 1; l--, n -= k)
341 241096072 : gel(v, l) = int_get_int(k, &w, &r);
342 5977852 : gel(v, 1) = int_get_int(n, &w, &r);
343 : }
344 5978790 : 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 966 : hamming_slice(GEN x, long a, long b)
714 : {
715 966 : long i, nb = 0;
716 73178 : for (i = a; i <= b; i++)
717 72212 : if (!gequal0(gel(x,i))) nb++;
718 966 : 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 1890 : hammingweight(GEN n)
747 : {
748 1890 : switch(typ(n))
749 : {
750 21 : case t_INT: return hamming_int(n);
751 959 : case t_VEC:
752 959 : 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 : }
|
