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