Added multi-threading support to invalid curve generation

Invalid curve generation now supports multi-threading via pthreads,
use the --threads= option.

- Changed some function params to const, where possible.
- Added *_new_copy, *_clone and *_new_clone functions to
   curve_t*, point_t* and point_t**
- Made cfg->bits unsigned long
- Made order_any gcopy the generated order(as it can be a clone and
   screw up stuff later)

4 files changed, 253 insertions, 40 deletions

diff --git a/src/invalid/invalid.c b/src/invalid/invalid.c
index b495958..1dd4fee 100644
--- a/src/invalid/invalid.c
+++ b/src/invalid/invalid.c
@@ -4,6 +4,7 @@
  */
 #include "invalid.h"
 #include "exhaustive/exhaustive.h"
+#include "invalid_thread.h"
 #include "io/output.h"
 #include "math/curve.h"
 #include "math/equation.h"
@@ -12,7 +13,7 @@
 #include "math/order.h"
 #include "math/point.h"
 
-static void invalid_ginit(gen_t *generators, config_t *cfg) {
+static void invalid_original_ginit(gen_t *generators, const config_t *cfg) {
 	generators[OFFSET_SEED] = &gen_skip;
 	if (cfg->random) {
 		generators[OFFSET_FIELD] = &field_random;
@@ -28,6 +29,20 @@ static void invalid_ginit(gen_t *generators, config_t *cfg) {
 	generators[OFFSET_ORDER] = &order_any;
 }
 
+static void invalid_invalid_ginit(gen_t *generators, const config_t *cfg) {
+	generators[OFFSET_FIELD] = &gen_skip;
+	generators[OFFSET_A] = &gen_skip;
+	generators[OFFSET_B] = &b_random;
+	generators[OFFSET_CURVE] = &curve_nonzero;
+	generators[OFFSET_ORDER] = &order_any;
+	if (cfg->unique) {
+		generators[OFFSET_GENERATORS] = &gens_one;
+	} else {
+		generators[OFFSET_GENERATORS] = &gens_any;
+	}
+	generators[OFFSET_POINTS] = &points_trial;
+}
+
 static size_t invalid_primes(GEN order, pari_ulong **primes) {
 	pari_sp ltop = avma;
 
@@ -71,30 +86,10 @@ static size_t invalid_primes(GEN order, pari_ulong **primes) {
 }
 
 static size_t invalid_curves(curve_t *curve, config_t *cfg, pari_ulong *primes,
-                             size_t nprimes, curve_t ***curves) {
-	gen_t invalid_gen[OFFSET_END];
-	invalid_gen[OFFSET_FIELD] = &gen_skip;
-	invalid_gen[OFFSET_A] = &gen_skip;
-	invalid_gen[OFFSET_B] = &b_random;
-	invalid_gen[OFFSET_CURVE] = &curve_nonzero;
-	invalid_gen[OFFSET_ORDER] = &order_any;
-	if (cfg->unique) {
-		invalid_gen[OFFSET_GENERATORS] = &gens_one;
-	} else {
-		invalid_gen[OFFSET_GENERATORS] = &gens_any;
-	}
-	invalid_gen[OFFSET_POINTS] = &points_trial;
-
+                             size_t nprimes, curve_t **curves,
+                             gen_t invalid_gen[OFFSET_END]) {
 	arg_t *invalid_argss[OFFSET_END];
 
-	// We will have nprimes curves in the end
-	*curves = pari_malloc(nprimes * sizeof(curve_t *));
-	if (!(*curves)) {
-		perror("Couldn't malloc.");
-		return 0;
-	}
-	memset(*curves, 0, nprimes * sizeof(curve_t *));
-
 	// Alloc a curve, and only alloc a new one when this pointer is saved into
 	// **curves
 	curve_t *invalid = curve_new();
@@ -113,7 +108,7 @@ static size_t invalid_curves(curve_t *curve, config_t *cfg, pari_ulong *primes,
 		// if so how many?
 		size_t total = 0;
 		for (size_t i = nprimes; i-- > 0;) {
-			if ((*curves)[i] == NULL && dvdis(invalid->order, primes[i])) {
+			if (curves[i] == NULL && dvdis(invalid->order, primes[i])) {
 				// whoo we have a new invalid curve
 				if (!total && cfg->verbose) {
 					fprintf(
@@ -132,7 +127,7 @@ static size_t invalid_curves(curve_t *curve, config_t *cfg, pari_ulong *primes,
 			size_t j = 0;
 			pari_ulong dprimes[total];
 			for (size_t i = 0; i < nprimes; ++i) {
-				if ((*curves)[i] == NULL && dvdis(invalid->order, primes[i])) {
+				if (curves[i] == NULL && dvdis(invalid->order, primes[i])) {
 					if (cfg->verbose) {
 						fprintf(debug, "prime %lu divides curve order.\n",
 						        primes[i]);
@@ -150,16 +145,15 @@ static size_t invalid_curves(curve_t *curve, config_t *cfg, pari_ulong *primes,
 
 			size_t count = 0;
 			for (size_t i = nprimes; i-- > 0;) {
-				if ((*curves)[i] == NULL && dvdis(invalid->order, primes[i])) {
+				if (curves[i] == NULL && dvdis(invalid->order, primes[i])) {
 					if (count == 0) {
 						// save a copy on first prime divisor from range
-						(*curves)[i] = invalid;
+						curves[i] = invalid;
 					} else {
 						// copy if pointer already assigned
-						(*curves)[i] = curve_new();
-						(*curves)[i] = curve_copy(invalid, (*curves)[i]);
+						curves[i] = curve_new_copy(invalid);
 					}
-					output_o((*curves)[i], cfg);
+					output_o(curves[i], cfg);
 					ncurves++;
 					count++;
 				}
@@ -194,14 +188,71 @@ static size_t invalid_curves(curve_t *curve, config_t *cfg, pari_ulong *primes,
 	return ncurves;
 }
 
+static size_t invalid_curves_threaded(curve_t *curve, config_t *cfg,
+                                      pari_ulong *primes, size_t nprimes,
+                                      curve_t **curves,
+                                      gen_t invalid_gen[OFFSET_END]) {
+	pthread_t pthreads[cfg->threads];
+	thread_t threads[cfg->threads];
+	struct pari_thread pari_threads[cfg->threads];
+	pari_thread_sync();
+
+	size_t generated = 0;
+	state_e states[nprimes];
+	curve_t *local_curves[nprimes];
+	for (size_t i = 0; i < nprimes; ++i) {
+		states[i] = STATE_FREE;
+	}
+	pthread_mutex_t state_mutex = PTHREAD_MUTEX_INITIALIZER;
+	pthread_mutex_t curves_mutex = PTHREAD_MUTEX_INITIALIZER;
+	pthread_cond_t generated_cond = PTHREAD_COND_INITIALIZER;
+
+	for (size_t i = 0; i < cfg->threads; ++i) {
+		threads[i].original_curve = curve;
+		threads[i].nprimes = nprimes;
+		threads[i].primes = primes;
+		threads[i].states = states;
+		threads[i].curves = local_curves;
+		threads[i].generated = &generated;
+		threads[i].mutex_state = &state_mutex;
+		threads[i].mutex_curves = &curves_mutex;
+		threads[i].cond_generated = &generated_cond;
+		threads[i].cfg = cfg;
+		threads[i].gens = invalid_gen;
+
+		pari_thread_alloc(&pari_threads[i], cfg->thread_memory,
+		                  (GEN)&threads[i]);
+	}
+
+	for (size_t i = 0; i < cfg->threads; ++i) {
+		pthread_create(&pthreads[i], NULL, &invalid_thread,
+		               (void *)&pari_threads[i]);
+	}
+
+	for (size_t i = 0; i < cfg->threads; ++i) {
+		pthread_join(pthreads[i], NULL);
+	}
+
+	for (size_t i = 0; i < nprimes; ++i) {
+		curves[i] = curve_new_copy(local_curves[i]);
+		curve_free(&local_curves[i]);
+	}
+
+	for (size_t i = 0; i < cfg->threads; ++i) {
+		pari_thread_free(&pari_threads[i]);
+	}
+
+	return generated;
+}
+
 int invalid_do(config_t *cfg) {
-	// create the curve to invalidate
-	// Either from input or random with -r
-	curve_t *curve = curve_new();
 	gen_t gen[OFFSET_END];
 	arg_t *argss[OFFSET_END];
-	invalid_ginit(gen, cfg);
+	invalid_original_ginit(gen, cfg);
 
+	// create the curve to invalidate
+	// Either from input or random with -
+	curve_t *curve = curve_new();
 	// actually generate the curve
 	if (!exhaustive_gen_retry(curve, cfg, gen, argss, OFFSET_FIELD,
 	                          OFFSET_POINTS, 1)) {
@@ -213,14 +264,32 @@ int invalid_do(config_t *cfg) {
 	// now, generate primes upto order^2
 	pari_ulong *primes;
 	size_t nprimes = invalid_primes(curve->order, &primes);
-
 	if (cfg->verbose) {
 		fprintf(debug, "primes upto: p_max = %lu, n = %lu\n",
 		        primes[nprimes - 1], nprimes);
 	}
 
-	curve_t **curves;
-	size_t ncurves = invalid_curves(curve, cfg, primes, nprimes, &curves);
+	// Alloc enough curves
+	curve_t **curves = pari_malloc(nprimes * sizeof(curve_t *));
+	if (!(curves)) {
+		perror("Couldn't malloc.");
+		return 0;
+	}
+	memset(curves, 0, nprimes * sizeof(curve_t *));
+
+	// init the invalid curve gen_t
+	gen_t invalid_gen[OFFSET_END];
+	invalid_invalid_ginit(invalid_gen, cfg);
+
+	// now, generate the invalid curves for all primes
+	size_t ncurves;
+	if (cfg->threads == 1) {
+		ncurves =
+		    invalid_curves(curve, cfg, primes, nprimes, curves, invalid_gen);
+	} else {
+		ncurves = invalid_curves_threaded(curve, cfg, primes, nprimes, curves,
+		                                  invalid_gen);
+	}
 
 	for (size_t i = 0; i < ncurves; ++i) {
 		curve_free(&curves[i]);
diff --git a/src/invalid/invalid.h b/src/invalid/invalid.h
index e98f6e4..43de25a 100644
--- a/src/invalid/invalid.h
+++ b/src/invalid/invalid.h
@@ -5,12 +5,12 @@
 /**
  * @file invalid.h
  */
-#include "io/cli.h"
-#include "io/config.h"
-
 #ifndef ECGEN_INVALID_H
 #define ECGEN_INVALID_H
 
+#include "io/cli.h"
+#include "io/config.h"
+
 /**
  *
  * @param cfg
diff --git a/src/invalid/invalid_thread.c b/src/invalid/invalid_thread.c
new file mode 100644
index 0000000..40b52ec
--- /dev/null
+++ b/src/invalid/invalid_thread.c
@@ -0,0 +1,106 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+
+#include "invalid_thread.h"
+#include "exhaustive/exhaustive.h"
+#include "io/output.h"
+#include "math/curve.h"
+#include "math/random.h"
+
+void *invalid_thread(void *arg) {
+	struct pari_thread *pthread = (struct pari_thread *)arg;
+	// TODO: This is dodgy ... as its really a GEN (so a long*)
+	thread_t *thread = (thread_t *)pari_thread_start(pthread);
+	random_init();
+	arg_t *invalid_argss[OFFSET_END];
+
+	curve_t *invalid = curve_new();
+	invalid->field = gcopy(thread->original_curve->field);
+	invalid->a = gcopy(thread->original_curve->a);
+
+	while (*thread->generated < thread->nprimes) {
+		pari_sp btop = avma;
+		exhaustive_gen(invalid, thread->cfg, thread->gens, NULL, OFFSET_B,
+		               OFFSET_GENERATORS);
+		size_t ndivides = 0;
+		for (size_t i = thread->nprimes; i-- > 0;) {
+			if (dvdis(invalid->order, thread->primes[i])) {
+				// whoo we have a new invalid curve
+				ndivides++;
+			}
+		}
+#ifdef DEBUG
+		printf("ndivides = %lu\n", ndivides);
+#endif
+		if (ndivides > 0) {
+			pthread_mutex_lock(thread->mutex_state);
+			size_t nfree = 0;
+			// can be up to ndivides, but also lower...
+			pari_ulong primes[ndivides];
+			size_t nprimes = 0;
+			for (size_t i = thread->nprimes; i-- > 0;) {
+				if (dvdis(invalid->order, thread->primes[i]) &&
+				    thread->states[i] == STATE_FREE) {
+					thread->states[i] = STATE_GENERATING;
+					primes[nprimes++] = thread->primes[i];
+					nfree++;
+				}
+			}
+#ifdef DEBUG
+			printf("nfree = %lu\n", nfree);
+#endif
+			pthread_mutex_unlock(thread->mutex_state);
+
+			if (nfree > 0) {
+				arg_t prime_divisors = {primes, nprimes};
+				invalid_argss[OFFSET_POINTS] = &prime_divisors;
+				exhaustive_gen(invalid, thread->cfg, thread->gens,
+				               invalid_argss, OFFSET_GENERATORS, OFFSET_END);
+
+				pthread_mutex_lock(thread->mutex_curves);
+				pthread_mutex_lock(thread->mutex_state);
+				size_t count = 0;
+				for (size_t i = thread->nprimes; i-- > 0;) {
+					if (count < nprimes && primes[count] == thread->primes[i]) {
+#ifdef DEBUG
+						printf("[i] = %lu, prime = %lu\n", i, primes[count]);
+						printf("state = %i\n", thread->states[i]);
+#endif
+						thread->states[i] = STATE_GENERATED;
+						thread->curves[i] = curve_new_copy(invalid);
+
+						output_o(thread->curves[i], thread->cfg);
+						count++;
+					}
+				}
+#ifdef DEBUG
+				printf("count = %lu, generated = %lu\n", count,
+				       *(thread->generated));
+#endif
+				*(thread->generated) += count;
+#ifdef DEBUG
+				printf("generated = %lu\n", *(thread->generated));
+#endif
+				// pthread_cond_signal(thread->cond_generated);
+				pthread_mutex_unlock(thread->mutex_state);
+				pthread_mutex_unlock(thread->mutex_curves);
+
+				invalid = curve_new();
+				invalid->field = gcopy(thread->original_curve->field);
+				invalid->a = gcopy(thread->original_curve->a);
+			} else {
+				obj_free(invalid->curve);  // necessary to free the ellinit
+				avma = btop;
+			}
+		} else {
+			obj_free(invalid->curve);  // necessary to free the ellinit
+			avma = btop;
+		}
+	}
+	curve_free(&invalid);
+
+	pari_thread_close();
+	return NULL;
+}
\ No newline at end of file
diff --git a/src/invalid/invalid_thread.h b/src/invalid/invalid_thread.h
new file mode 100644
index 0000000..1ee4cf7
--- /dev/null
+++ b/src/invalid/invalid_thread.h
@@ -0,0 +1,38 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+/**
+ * @file invalid_thread.h
+ */
+#ifndef ECGEN_INVALID_THREAD_H
+#define ECGEN_INVALID_THREAD_H
+
+#include <pari/pari.h>
+#include <pthread.h>
+#include "math/types.h"
+
+typedef enum { STATE_FREE, STATE_GENERATING, STATE_GENERATED } state_e;
+
+typedef struct {
+	curve_t *original_curve;
+	size_t nprimes;
+	pari_ulong *primes;
+	state_e *states;
+	curve_t **curves;
+	size_t *generated;
+	pthread_mutex_t *mutex_state;
+	pthread_mutex_t *mutex_curves;
+	pthread_cond_t *cond_generated;
+	config_t *cfg;
+	gen_t *gens;
+} thread_t;
+
+/**
+ *
+ * @param arg
+ * @return
+ */
+void *invalid_thread(void *arg);
+
+#endif  // ECGEN_INVALID_THREAD_H