1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include "pszip.h"
/*
* Bit hack source:
* https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
*/
void pszip_iterate_bithack01(mpz_t w, const mpz_t v)
{
mpz_t vmo, t, tpo, ct, nct, act, actmo;
mp_limb_t *actmo_l;
size_t actmo_s;
mpz_inits(vmo, t, tpo, ct, nct, act, actmo, 0);
/* Gets v's least significant 0 bits set to 1.
* t = v | (v - 1); */
mpz_sub_ui(vmo, v, 1);
mpz_ior(t, v, vmo);
/* Next set to 1 the most significant bit to change,
* set to 0 the least significant ones, and add the necessary 1 bits.
* w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
* __builtin_ctz(v) -> mpz_scan1(v, 0) */
mpz_add_ui(tpo, t, 1);
mpz_com(ct, t);
mpz_neg(nct, ct);
mpz_and(act, ct, nct);
mpz_sub_ui(actmo, act, 1);
/* the bitshift requires obtaining direct memory access */
actmo_s = mpz_size(actmo);
actmo_l = mpz_limbs_modify(actmo, actmo_s);
mpn_rshift(actmo_l, actmo_l, actmo_s, (mpz_scan1(v, 0) + 1));
mpz_limbs_finish(actmo, actmo_s);
mpz_ior(w, tpo, actmo);
mpz_clears(vmo, t, tpo, ct, nct, act, actmo, 0);
}
|
