Fix discriminant iteration in CM with composite order.

The prime impl is still broken. The family gen is as well.

17 files changed, 215 insertions, 79 deletions

diff --git a/src/cm/cm.c b/src/cm/cm.c
index 9dffc1d..79e0e0e 100644
--- a/src/cm/cm.c
+++ b/src/cm/cm.c
@@ -74,7 +74,7 @@ static void cm_ginit(gen_f *generators, bool prime) {
 		}
 		generators[OFFSET_ORDER] = &cm_gen_order;
 	} else if (cfg->method == METHOD_ANOMALOUS) {
-		GET(random); // Used within the method.
+		GET(random);  // Used within the method.
 		generators[OFFSET_FIELD] = &anomalous_gen_field;
 		generators[OFFSET_A] = &gen_skip;
 		generators[OFFSET_B] = &anomalous_gen_equation;
@@ -226,6 +226,7 @@ static void cm_quit(exhaustive_t *setup) {
 	if (cfg->method == METHOD_ANOMALOUS) {
 		anomalous_quit();
 	}
+	cm_any_quit();
 	exhaustive_clear(setup);
 }
 
diff --git a/src/cm/cm_any.c b/src/cm/cm_any.c
index f948ac1..a0cd475 100644
--- a/src/cm/cm_any.c
+++ b/src/cm/cm_any.c
@@ -16,17 +16,22 @@
  */
 static void good_qdisc_minimal(cm_any_qdisc_t *qdisc, GEN order) {
 	pari_sp ltop = avma;
-	GEN d = stoi(2);
-	size_t j = 0;
+	GEN d;
+	if (qdisc->d) {
+		d = negi(subis(qdisc->d, 1));
+	} else {
+		d = stoi(2);
+	}
+	size_t j = 1;
 	while (true) {
 		++j;
+		if (j % 100 == 0) {
+			debug_log("d: %Ps", d);
+		}
 		if (!issquarefree(d)) {
 			d = addis(d, 1);
 			continue;
 		}
-		if (j % 100 == 0) {
-			debug_log("D: %Ps", d);
-		}
 		GEN D = quaddisc(negi(d));
 		GEN K = Buchall(quadpoly(D), 0, DEFAULTPREC);
 		GEN alphas = bnfisintnorm(K, order);
@@ -52,7 +57,7 @@ static void good_qdisc_minimal(cm_any_qdisc_t *qdisc, GEN order) {
 	}
 }
 
-/**
+/*
  * @brief Find a fundamental quadratic discriminant < d_range, start looking
  *        at the sides of the inverted Hasse interval around order, upto p_range
  *
@@ -114,9 +119,9 @@ static cm_any_qdisc_t *good_qdisc_brute_range(GEN order, GEN p_range, GEN d_rang
 		return result;
 	};
 }
-
 */
-/**
+/*
+ *
  * @brief Find a fundamental quadratic discriminant < order^beta, start looking
  * 		  at the sides of the inverted Hasse interval around order, upto
  * order^alpha width.
@@ -124,33 +129,60 @@ static cm_any_qdisc_t *good_qdisc_brute_range(GEN order, GEN p_range, GEN d_rang
  * @param alpha
  * @param beta
  * @return
- *//*
-
+ *
 static cm_any_qdisc_t *good_qdisc_brute(GEN order, GEN alpha, GEN beta) {
-	GEN ord_a = ground(gpow(order, alpha, DEFAULTPREC));
-	GEN ord_b = ground(gpow(order, beta, DEFAULTPREC));
-	return good_qdisc_brute_range(order, ord_a, ord_b);
+    GEN ord_a = ground(gpow(order, alpha, DEFAULTPREC));
+    GEN ord_b = ground(gpow(order, beta, DEFAULTPREC));
+    return good_qdisc_brute_range(order, ord_a, ord_b);
 }
 */
 
-GEN cm_construct_curve(GEN order, GEN d, GEN p, bool ord_prime) {
+void cm_update_roots(GEN d, GEN p, cm_any_roots_t *roots) {
+	pari_sp ltop = avma;
+	GEN H = polclass(d, 0, 0);
+	GEN raw = FpX_roots(H, p);
+	if (roots->roots && isclone(roots->roots)) {
+		gunclone(roots->roots);
+	}
+	roots->roots = gclone(raw);
+	roots->total = glength(raw);
+	roots->used = 0;
+	avma = ltop;
+}
+
+cm_any_roots_t *cm_make_roots(GEN d, GEN p) {
+	debug_log("Making roots, d = %Pi, p = %Pi", d, p);
+	cm_any_roots_t *roots = try_calloc(sizeof(cm_any_roots_t));
+	cm_update_roots(d, p, roots);
+	return roots;
+}
+
+void cm_free_roots(cm_any_roots_t *roots) {
+	if (roots) {
+		if (roots->roots && isclone(roots->roots)) {
+			gunclone(roots->roots);
+		}
+		try_free(roots);
+	}
+}
+
+GEN cm_construct_curve(GEN order, GEN d, GEN p, cm_any_roots_t *roots,
+                       bool ord_prime) {
 	debug_log("Constructing a curve with N = %Pi, d = %Pi, p = %Pi", order, d,
 	          p);
 	pari_sp ltop = avma;
-	GEN H = polclass(d, 0, 0);
-	debug_log("H = %Ps", H);
 
-	GEN r = FpX_roots(H, p);
-	debug_log("roots = %Ps", r);
-	if (gequal(r, gtovec(gen_0))) {
+	debug_log("roots(%li/%li) = %Ps", roots->used, roots->total, roots->roots);
+	if (roots->total == 0 || roots->used == roots->total ||
+	    gequal(roots->roots, gtovec(gen_0))) {
 		avma = ltop;
 		return NULL;
 	}
 
-	long rlen = glength(r);
-	for (long i = 1; i <= rlen; ++i) {
-		GEN root = gel(r, i);
-		debug_log("trying root = %Pi", root);
+	for (long i = roots->used; i < roots->total; ++i) {
+		roots->used = i + 1;
+		GEN root = gel(roots->roots, i + 1);
+		debug_log("trying root[%i] = %Pi", i + 1, root);
 
 		GEN e = ellinit(ellfromj(mkintmod(root, p)), p, 0);
 		pari_CATCH(e_TYPE) { continue; }
@@ -211,28 +243,28 @@ GEN cm_construct_curve(GEN order, GEN d, GEN p, bool ord_prime) {
 	return NULL;
 }
 
-GEN cm_construct_curve_subgroup(GEN r, GEN d, GEN p) {
-	debug_log("Constructing a curve with r = %Pi, d = %Pi, p = %Pi", r, d,
-	          p);
+GEN cm_construct_curve_subgroup(GEN r, GEN d, GEN p, cm_any_roots_t *roots) {
+	debug_log("Constructing a curve with r = %Pi, d = %Pi, p = %Pi", r, d, p);
 	pari_sp ltop = avma;
-	GEN H = polclass(d, 0, 0);
-	debug_log("H = %Ps", H);
 
-	GEN roots = FpX_roots(H, p);
-	debug_log("roots = %Ps", roots);
-	if (gequal(roots, gtovec(gen_0))) {
+	debug_log("roots(%li/%li) = %Ps", roots->used, roots->total, roots->roots);
+	if (roots->total == 0 || roots->used == roots->total ||
+	    gequal(roots->roots, gtovec(gen_0))) {
 		avma = ltop;
 		return NULL;
 	}
 
-	long rlen = glength(roots);
 	pari_sp btop = avma;
-	for (long i = 1; i <= rlen; ++i) {
-		GEN root = gel(roots, i);
-		debug_log("trying root = %Pi", root);
+	for (long i = roots->used; i < roots->total; ++i) {
+		roots->used = i + 1;
+		GEN root = gel(roots->roots, i + 1);
+		debug_log("trying root[%i] = %Pi", i + 1, root);
 
 		GEN e = ellinit(ellfromj(mkintmod(root, p)), p, 0);
-		pari_CATCH(e_TYPE) { avma = btop; continue; }
+		pari_CATCH(e_TYPE) {
+			avma = btop;
+			continue;
+		}
 		pari_TRY { checkell(e); };
 		pari_ENDCATCH{};
 
@@ -247,21 +279,68 @@ GEN cm_construct_curve_subgroup(GEN r, GEN d, GEN p) {
 	return NULL;
 }
 
+static cm_any_qdisc_t *min_d = NULL;
+static cm_any_roots_t *min_roots = NULL;
+static curve_t *min_curve = NULL;
+
 GENERATOR(cm_gen_curve_any) {
 	HAS_ARG(args);
 	pari_sp ltop = avma;
 	const char *order_s = (const char *)args->args;
 	GEN order = strtoi(order_s);
-	cm_any_qdisc_t min_disc = {0};
-	good_qdisc_minimal(&min_disc, order);
-	debug_log("Got min D = %Pi", min_disc.d);
-	GEN e = cm_construct_curve(order, min_disc.d, min_disc.p, false);
+	GEN e;
+	if (min_d && min_roots && min_curve == curve &&
+	    min_roots->used < min_roots->total) {
+		debug_log("Reusing roots.");
+		// We can just use the roots we have stored and take some out.
+		e = cm_construct_curve(order, min_d->d, min_d->p, min_roots, false);
+	} else if (min_d && min_curve == curve) {
+		debug_log("Reusing min D = %Pi", min_d->d);
+		// We just have the discriminant but no roots (or they are used up), we
+		// need to continue
+		if (min_d->d && isclone(min_d->d)) {
+			gunclone(min_d->d);
+		}
+		if (min_d->p && isclone(min_d->p)) {
+			gunclone(min_d->p);
+		}
+		good_qdisc_minimal(min_d, order);
+		min_d->d = gclone(min_d->d);
+		min_d->p = gclone(min_d->p);
+		debug_log("Got min D = %Pi", min_d->d);
+		if (min_roots) {
+			cm_update_roots(min_d->d, min_d->p, min_roots);
+		} else {
+			min_roots = cm_make_roots(min_d->d, min_d->p);
+		}
+		e = cm_construct_curve(order, min_d->d, min_d->p, min_roots, false);
+	} else {
+		// We have nothing. Start fresh.
+		debug_log("Fresh start.");
+		if (!min_d) {
+			min_d = try_calloc(sizeof(cm_any_qdisc_t));
+		}
+		if (min_d->d && isclone(min_d->d)) {
+			gunclone(min_d->d);
+		}
+		if (min_d->p && isclone(min_d->p)) {
+			gunclone(min_d->p);
+		}
+		good_qdisc_minimal(min_d, order);
+		min_d->d = gclone(min_d->d);
+		min_d->p = gclone(min_d->p);
+		debug_log("Got min D = %Pi", min_d->d);
+		min_roots = cm_make_roots(min_d->d, min_d->p);
+		min_curve = curve;
+		e = cm_construct_curve(order, min_d->d, min_d->p, min_roots, false);
+	}
+
 	if (e == NULL) {
 		fprintf(err, "Could not construct curve.");
 		avma = ltop;
 		return -3;
 	}
-	curve->field = min_disc.p;
+	curve->field = min_d->p;
 	curve->a = ell_get_a4(e);
 	curve->b = ell_get_a6(e);
 	curve->curve = e;
@@ -273,4 +352,13 @@ GENERATOR(cm_gen_order) {
 	const char *order_s = (const char *)args->args;
 	curve->order = strtoi(order_s);
 	return 1;
+}
+
+void cm_any_quit() {
+	if (min_d) {
+		try_free(min_d);
+	}
+	if (min_roots) {
+		cm_free_roots(min_roots);
+	}
 }
\ No newline at end of file
diff --git a/src/cm/cm_any.h b/src/cm/cm_any.h
index a49fd7f..c5407cb 100644
--- a/src/cm/cm_any.h
+++ b/src/cm/cm_any.h
@@ -12,22 +12,53 @@ typedef struct {
 	GEN d;
 } cm_any_qdisc_t;
 
+typedef struct {
+	GEN roots;
+	long used;
+	long total;
+} cm_any_roots_t;
+
+/**
+ *
+ * @param d
+ * @param p
+ * @param roots
+ */
+void cm_update_roots(GEN d, GEN p, cm_any_roots_t *roots);
+
+/**
+ *
+ * @param d
+ * @param p
+ * @return
+ */
+cm_any_roots_t *cm_make_roots(GEN d, GEN p);
+
+void cm_free_roots(cm_any_roots_t *roots);
+
 /**
  * @brief Construct an elliptic curve given its order, CM discriminant and field
  * order.
  * @param order
  * @param d
  * @param p
+ * @param roots
  * @param ord_prime
  * @return
  */
-GEN cm_construct_curve(GEN order, GEN d, GEN p, bool ord_prime);
+GEN cm_construct_curve(GEN order, GEN d, GEN p, cm_any_roots_t *roots,
+                       bool ord_prime);
 
 /**
  * @brief Construct an elliptic curve given a factor of its order, CM
  * discriminant and field order.
+ *
+ * @param r
+ * @param d
+ * @param p
+ * @param roots
  */
-GEN cm_construct_curve_subgroup(GEN r, GEN d, GEN p);
+GEN cm_construct_curve_subgroup(GEN r, GEN d, GEN p, cm_any_roots_t *roots);
 
 /**
  * @brief
@@ -47,4 +78,9 @@ GENERATOR(cm_gen_curve_any);
  */
 GENERATOR(cm_gen_order);
 
+/**
+ * @brief Deinitialize.
+ */
+void cm_any_quit();
+
 #endif  // ECGEN_CM_ANY_H
diff --git a/src/cm/cm_prime.c b/src/cm/cm_prime.c
index 33d2a12..64ba72e 100644
--- a/src/cm/cm_prime.c
+++ b/src/cm/cm_prime.c
@@ -146,11 +146,14 @@ GENERATOR(cm_gen_curve_prime) {
 
 	cm_prime_qdisc_t qdisc = {0};
 	qdisc_init(&qdisc, order);
+	cm_any_roots_t *roots = try_calloc(sizeof(cm_any_roots_t));
 	do {
 		qdisc_next(&qdisc);
-		e = cm_construct_curve(order, qdisc.D, qdisc.p, true);
+		cm_update_roots(qdisc.D, qdisc.p, roots);
+		e = cm_construct_curve(order, qdisc.D, qdisc.p, roots, true);
 	} while (e == NULL);
 	qdisc_free(&qdisc);
+	cm_free_roots(roots);
 
 	curve->field = qdisc.p;
 	curve->a = ell_get_a4(e);
diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c
index e8870f8..243754c 100644
--- a/src/exhaustive/exhaustive.c
+++ b/src/exhaustive/exhaustive.c
@@ -7,9 +7,8 @@
 #include "arg.h"
 #include "brainpool.h"
 #include "brainpool_rfc.h"
-#include "nums.h"
-#include "family.h"
 #include "check.h"
+#include "family.h"
 #include "gen/curve.h"
 #include "gen/equation.h"
 #include "gen/field.h"
@@ -21,6 +20,7 @@
 #include "gen/seed.h"
 #include "io/output.h"
 #include "misc/config.h"
+#include "nums.h"
 #include "obj/curve.h"
 #include "util/memory.h"
 #include "util/timeout.h"
@@ -129,7 +129,8 @@ static void exhaustive_ginit(gen_f *generators) {
 				generators[OFFSET_SEED] = &gen_skip;
 				generators[OFFSET_FIELD] = &nums_gen_field;
 				generators[OFFSET_A] = &nums_gen_a;
-				generators[OFFSET_B] = &nums_gen_b;  // TODO: Missing transformation from b -> -b.
+				generators[OFFSET_B] =
+				    &nums_gen_b;  // TODO: Missing transformation from b -> -b.
 				generators[OFFSET_ORDER] = &nums_gen_order;
 				generators[OFFSET_GENERATORS] = &nums_gen_gens;
 			} break;
@@ -144,7 +145,6 @@ static void exhaustive_ginit(gen_f *generators) {
 			generators[OFFSET_SEED] = &family_gen_seed_random;
 		} else {
 			generators[OFFSET_SEED] = &family_gen_seed_input;
-
 		}
 		generators[OFFSET_FIELD] = &family_gen_field;
 		generators[OFFSET_A] = &gen_skip;
@@ -154,7 +154,7 @@ static void exhaustive_ginit(gen_f *generators) {
 			generators[OFFSET_B] = &family_gen_equation_iter;
 		}
 
-		//TODO make the prime check optional, based on cfg->prime.
+		// TODO make the prime check optional, based on cfg->prime.
 		generators[OFFSET_ORDER] = &family_gen_order;
 		generators[OFFSET_GENERATORS] = &gens_gen_any;
 	} else {
diff --git a/src/exhaustive/family.c b/src/exhaustive/family.c
index 08505b6..05433f7 100644
--- a/src/exhaustive/family.c
+++ b/src/exhaustive/family.c
@@ -6,10 +6,10 @@
 #include "family.h"
 #include "cm/cm_any.h"
 #include "gen/seed.h"
+#include "io/output.h"
 #include "misc/config.h"
 #include "util/bits.h"
 #include "util/random.h"
-#include "io/output.h"
 
 #define FAMILIES (FAMILY_KSS40 + 1)
 
@@ -143,7 +143,9 @@ GENERATOR(family_gen_equation_cm) {
 	GEN n = closure_callgen1(nz_store[cfg->family], curve->seed->family.z);
 	GEN rz = closure_callgen1(rz_store[cfg->family], n);
 	GEN D = D_store[cfg->family];
-	GEN e = cm_construct_curve_subgroup(rz, D, curve->field);
+	cm_any_roots_t *roots = cm_make_roots(D, curve->field);
+	GEN e = cm_construct_curve_subgroup(rz, D, curve->field, roots);
+	cm_free_roots(roots);
 	if (e) {
 		curve->a = ell_get_a4(e);
 		curve->b = ell_get_a6(e);
diff --git a/src/exhaustive/family.h b/src/exhaustive/family.h
index 9b7deaa..11e9104 100644
--- a/src/exhaustive/family.h
+++ b/src/exhaustive/family.h
@@ -26,5 +26,4 @@ void family_init();
 
 void family_quit();
 
-
-#endif //ECGEN_EXHAUSTIVE_FAMILY_H
+#endif  // ECGEN_EXHAUSTIVE_FAMILY_H
diff --git a/src/exhaustive/nums.c b/src/exhaustive/nums.c
index 7e41938..0db8d75 100644
--- a/src/exhaustive/nums.c
+++ b/src/exhaustive/nums.c
@@ -22,7 +22,7 @@ GENERATOR(nums_gen_field) {
 }
 
 GENERATOR(nums_gen_a) {
-	curve-> a = gmodulo(stoi(-3), curve->field);
+	curve->a = gmodulo(stoi(-3), curve->field);
 	return 1;
 }
 
@@ -103,7 +103,6 @@ GENERATOR(nums_gen_gens) {
 	return 1;
 }
 
-
 void nums_quit(void) {
 	if (b && isclone(b)) {
 		gunclone(b);
diff --git a/src/gen/gens.c b/src/gen/gens.c
index 1c3a6c6..a32f8b8 100644
--- a/src/gen/gens.c
+++ b/src/gen/gens.c
@@ -5,9 +5,9 @@
 #include "gens.h"
 #include "exhaustive/arg.h"
 #include "math/subgroup.h"
+#include "misc/compat.h"
 #include "obj/point.h"
 #include "obj/subgroup.h"
-#include "misc/compat.h"
 
 static subgroup_t *gens_point(GEN point, const curve_t *curve) {
 	subgroup_t *sub = subgroup_new();
@@ -42,7 +42,7 @@ GENERATOR(gens_gen_one) {
 	if (len == 2) {
 		avma = ltop;
 		return -5;
-    }
+	}
 	GEN generators = ellff_get_gens(curve->curve);
 	len = glength(generators);
 	if (len == 2) {
diff --git a/src/gen/metadata.c b/src/gen/metadata.c
index b857ec7..7d455ef 100644
--- a/src/gen/metadata.c
+++ b/src/gen/metadata.c
@@ -28,7 +28,8 @@ GENERATOR(metadata_gen) {
 		GEN d_f = coredisc2(subii(sqri(frobenius), mulis(q, 4)));
 		cm_disc = gcopy(gel(d_f, 1));
 		conductor = gcopy(gel(d_f, 2));
-		gerepileall(ltop, 6, &j, &disc, &embedding_degree, &frobenius, &cm_disc, &conductor);
+		gerepileall(ltop, 6, &j, &disc, &embedding_degree, &frobenius, &cm_disc,
+		            &conductor);
 	} else if (typ(curve->field) == t_FFELT) {
 		cm_disc = NULL;
 		conductor = NULL;
diff --git a/src/invalid/invalid.c b/src/invalid/invalid.c
index 3679c6b..e7870a5 100644
--- a/src/invalid/invalid.c
+++ b/src/invalid/invalid.c
@@ -289,8 +289,7 @@ static size_t invalid_curves_threaded(const curve_t *curve, pari_ulong *primes,
 			}
 		}
 
-		if (*generated == nprimes)
-			break;
+		if (*generated == nprimes) break;
 	}
 	pthread_mutex_unlock(&state_mutex);
 
diff --git a/src/io/output.c b/src/io/output.c
index c4704c1..4984515 100644
--- a/src/io/output.c
+++ b/src/io/output.c
@@ -165,8 +165,7 @@ static JSON_Value *output_jjson(curve_t *curve) {
 		}
 		if (curve->meta.conductor != NULL) {
 			char *conductor = pari_sprintf("%Pi", curve->meta.conductor);
-			json_object_dotset_string(root_object, "meta.conductor",
-			                          conductor);
+			json_object_dotset_string(root_object, "meta.conductor", conductor);
 			pari_free(conductor);
 		}
 	}
diff --git a/src/misc/compat.h b/src/misc/compat.h
index 7e3d4e8..ccacb2e 100644
--- a/src/misc/compat.h
+++ b/src/misc/compat.h
@@ -12,17 +12,24 @@
 #define PARI_VERSION_MINOR (((PARI_VERSION_CODE) >> 8) & 0xff)
 #define PARI_VERSION_MAJOR (PARI_VERSION_CODE >> 16)
 
-#define PARI_VERSION_GT(a,b,c) ((PARI_VERSION_MAJOR == a && PARI_VERSION_MINOR == b && PARI_VERSION_PATCH > c) || (PARI_VERSION_MAJOR == a && PARI_VERSION_MINOR > b) || (PARI_VERSION_MAJOR > a))
-#define PARI_VERSION_EQ(a,b,c) (PARI_VERSION_MAJOR == a && PARI_VERSION_MINOR == b && PARI_VERSION_PATCH == c)
-#define PARI_VERSION_GE(a,b,c) (PARI_VERSION_GT(a,b,c) || PARI_VERSION_EQ(a,b,c))
-#define PARI_VERSION_LT(a,b,c) !(PARI_VERSION_GE(a,b,c))
-#define PARI_VERSION_LE(a,b,c) !(PARI_VERSION_GT(a,b,c))
+#define PARI_VERSION_GT(a, b, c)                            \
+	((PARI_VERSION_MAJOR == a && PARI_VERSION_MINOR == b && \
+	  PARI_VERSION_PATCH > c) ||                            \
+	 (PARI_VERSION_MAJOR == a && PARI_VERSION_MINOR > b) || \
+	 (PARI_VERSION_MAJOR > a))
+#define PARI_VERSION_EQ(a, b, c)                           \
+	(PARI_VERSION_MAJOR == a && PARI_VERSION_MINOR == b && \
+	 PARI_VERSION_PATCH == c)
+#define PARI_VERSION_GE(a, b, c) \
+	(PARI_VERSION_GT(a, b, c) || PARI_VERSION_EQ(a, b, c))
+#define PARI_VERSION_LT(a, b, c) !(PARI_VERSION_GE(a, b, c))
+#define PARI_VERSION_LE(a, b, c) !(PARI_VERSION_GT(a, b, c))
 
-#if PARI_VERSION_LT(2,12,1)
+#if PARI_VERSION_LT(2, 12, 1)
 #define polisirreducible isirreducible
 #endif
 
-#if PARI_VERSION_LT(2,15,0)
+#if PARI_VERSION_LT(2, 15, 0)
 #define znorder(x, o) order(x);
 #endif
 
diff --git a/src/util/bits.c b/src/util/bits.c
index 0d60c26..b73a55d 100644
--- a/src/util/bits.c
+++ b/src/util/bits.c
@@ -174,16 +174,18 @@ char *bits_to_hex(const bits_t *bits) {
 	// else
 	// 0 0 | a b | c d | e
 	//  ^-----^ (8-offset zero bits, offset bits from first byte)
-	//        ^-----^ (8-offset bits from first byte, offset bits from second byte)
+	//        ^-----^ (8-offset bits from first byte, offset bits from second
+	//        byte)
 	//           ....
-	//              ^-----^ (8-offset bits from second to last byte, offset bits from last byte)
+	//              ^-----^ (8-offset bits from second to last byte, offset bits
+	//              from last byte)
 	for (size_t i = 0; i < BYTE_LEN(bits->bitlen); ++i) {
 		size_t pos = (i * 2) + (bits->sign ? 1 : 0);
 		unsigned char value;
 		if (offset) {
 			value = bits->bits[i] >> (8 - offset);
 			if (i != 0) {
-				value |= (bits->bits[i-1] & ~(1 << (8 - offset))) << offset;
+				value |= (bits->bits[i - 1] & ~(1 << (8 - offset))) << offset;
 			}
 		} else {
 			value = bits->bits[i];
diff --git a/src/util/random.c b/src/util/random.c
index b88bb50..844e0f6 100644
--- a/src/util/random.c
+++ b/src/util/random.c
@@ -5,8 +5,8 @@
 #define _POSIX_C_SOURCE 200809L
 
 #include "random.h"
-#include <time.h>
 #include <stdint.h>
+#include <time.h>
 
 void random_reseed(void) {
 	pari_ulong seed = 0;
@@ -15,7 +15,8 @@ void random_reseed(void) {
 	if (rand) {
 		size_t read = 0;
 		while (read < sizeof(pari_ulong)) {
-			read += fread(((uint8_t*) &seed) + read, 1, sizeof(pari_ulong) - read, rand);
+			read += fread(((uint8_t *)&seed) + read, 1,
+			              sizeof(pari_ulong) - read, rand);
 		}
 
 		fclose(rand);
diff --git a/src/util/str.c b/src/util/str.c
index ff075f2..ade97a9 100644
--- a/src/util/str.c
+++ b/src/util/str.c
@@ -68,7 +68,6 @@ char *str_concat(char **strings, size_t len) {
 
 size_t str_cnt(const char *str, const char c) {
 	size_t result = 0;
-	for (; str[result]; str[result] == c ? result++ : *str++)
-		;
+	for (; str[result]; str[result] == c ? result++ : *str++);
 	return result;
 }
diff --git a/test/src/util/test_bits.c b/test/src/util/test_bits.c
index 269d1f6..e5a2f73 100644
--- a/test/src/util/test_bits.c
+++ b/test/src/util/test_bits.c
@@ -243,14 +243,14 @@ Test(bits, test_bits_or) {
 	bits_t *other_bits = bits_new(6);
 	other_bits->bits[0] = 0b10000000;
 
-	bits_t * or = bits_or(bits, other_bits);
+	bits_t *or = bits_or(bits, other_bits);
 	cr_assert_not_null(or, );
 	cr_assert_eq(or->bitlen, 10, );
 	cr_assert_eq(or->bits[0], 0b00001000, );
 	cr_assert_eq(or->bits[1], 0b11000000, );
 	bits_free(&bits);
 	bits_free(&other_bits);
-	bits_free(& or);
+	bits_free(&or);
 }
 
 Test(bits, test_bits_and) {