From f1a44b273147c92cbfd4264093354e04486efec8 Mon Sep 17 00:00:00 2001
From: Malfurious <m@lfurio.us>
Date: Sat, 28 Aug 2021 15:40:35 -0400
Subject: Add new C bit iterator

This is an implementation of the linked hack for libgmp.  An
arithmetic-based solution seems ideal for performance.  However, due to
the potential size of our output (entire files), a big-integer library
is needed for the base type.

Signed-off-by: Malfurious <m@lfurio.us>
---
 iterations.c | 40 ++++++++++++++++++++++++++++++++++++++++
 pszip.h      |  5 +++++
 2 files changed, 45 insertions(+)
 create mode 100644 iterations.c
 create mode 100644 pszip.h

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);
+}
diff --git a/pszip.h b/pszip.h
new file mode 100644
index 0000000..9d07e49
--- /dev/null
+++ b/pszip.h
@@ -0,0 +1,5 @@
+#pragma once
+
+#include <gmp.h>
+
+void pszip_iterate_bithack01(mpz_t, const mpz_t);
-- 
cgit v1.2.3