diff options
| -rw-r--r-- | iterations.c | 40 | ||||
| -rw-r--r-- | pszip.h | 5 |
2 files changed, 45 insertions, 0 deletions
diff --git a/iterations.c b/iterations.c new file mode 100644 index 0000000..517bcaa --- /dev/null +++ b/iterations.c @@ -0,0 +1,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); +} @@ -0,0 +1,5 @@ +#pragma once + +#include <gmp.h> + +void pszip_iterate_bithack01(mpz_t, const mpz_t); |