2 files changed, 336 insertions, 0 deletions
diff --git a/src/solvers/h48/h48.h b/src/solvers/h48/h48.h
index 4edc5ac..ee865d9 100644
--- a/src/solvers/h48/h48.h
+++ b/src/solvers/h48/h48.h
@@ -3,3 +3,4 @@
 #include "gendata_cocsep.h"
 #include "gendata_h48.h"
 #include "solve.h"
+#include "thread.h"
diff --git a/src/solvers/h48/thread.h b/src/solvers/h48/thread.h
new file mode 100644
index 0000000..1eade29
--- /dev/null
+++ b/src/solvers/h48/thread.h
@@ -0,0 +1,335 @@
+#include <pthread.h>
+#include <stdatomic.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#define MAX_QUEUE_SIZE 500
+typedef struct
+{
+        dfsarg_solveh48_t *tasks[MAX_QUEUE_SIZE];
+        int front;
+        int rear;
+        int tasks_count;
+        pthread_mutex_t mutex;
+        pthread_cond_t cond;
+        atomic_int active_tasks;
+        pthread_mutex_t active_tasks_mutex;
+        pthread_cond_t active_tasks_cond;
+} task_queue_t;
+STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *, task_queue_t *);
+STATIC void init_queue(task_queue_t *);
+STATIC void submit_task(task_queue_t *, dfsarg_solveh48_t *);
+STATIC void copy_queue(task_queue_t *, task_queue_t *, int);
+STATIC dfsarg_solveh48_t *get_task(task_queue_t *);
+STATIC void *start_thread(void *);
+STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t *, task_queue_t *);
+STATIC int64_t solve_h48_single(dfsarg_solveh48_t *, task_queue_t *);
+STATIC int64_t solve_h48_parent(cube_t, int8_t, int8_t, int8_t, const void *, char *);
+STATIC void
+solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq){
+        pthread_mutex_lock(&tq->mutex);
+        int strl;
+        uint8_t invertedpremoves[MAXLEN];
+        char *solution = *arg->nextsol;
+        strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol);
+        *arg->nextsol += strl;
+        if (arg->npremoves)
+        {
+                **arg->nextsol = ' ';
+                (*arg->nextsol)++;
+                invertmoves(arg->premoves, arg->npremoves, invertedpremoves);
+                strl = writemoves(invertedpremoves, arg->npremoves, *arg->nextsol);
+                *arg->nextsol += strl;
+        }
+        LOG("Solution found: %s\n", solution);
+        **arg->nextsol = '\n';
+        (*arg->nextsol)++;
+        (*arg->nsols)++;
+        pthread_mutex_unlock(&tq->mutex);
+}
+STATIC void
+init_queue(task_queue_t *queue)
+{
+        queue->front = 0;
+        queue->rear = 0;
+        queue->tasks_count = 0;
+        pthread_mutex_init(&queue->mutex, NULL);
+        pthread_cond_init(&queue->cond, NULL);
+}
+STATIC void
+submit_task(task_queue_t *queue, dfsarg_solveh48_t *task)
+{
+        pthread_mutex_lock(&queue->mutex);
+        queue->tasks[queue->rear] = task;
+        queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
+        queue->tasks_count++;
+        pthread_cond_signal(&queue->cond);
+        pthread_mutex_unlock(&queue->mutex);
+}
+STATIC void
+copy_queue(task_queue_t *src, task_queue_t *dest, int depth)
+{
+        pthread_mutex_lock(&src->mutex);
+        pthread_mutex_lock(&dest->mutex);
+        for (int i = src->front; i != src->rear; i = (i + 1) % MAX_QUEUE_SIZE)
+        {
+                if (src->tasks[i] != NULL)
+                {
+                        dest->tasks[i] = src->tasks[i];
+                        dest->tasks[i]->depth = depth;
+                }
+        }
+        dest->front = src->front;
+        dest->rear = src->rear;
+        dest->tasks_count = src->tasks_count;
+        pthread_mutex_unlock(&src->mutex);
+        pthread_cond_signal(&dest->cond);
+        pthread_mutex_unlock(&dest->mutex);
+}
+STATIC dfsarg_solveh48_t *
+get_task(task_queue_t *queue)
+{
+        pthread_mutex_lock(&queue->mutex);
+        while (queue->tasks_count == 0)
+        {
+                pthread_cond_wait(&queue->cond, &queue->mutex);
+        }
+        dfsarg_solveh48_t *task = queue->tasks[queue->front];
+        queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
+        queue->tasks_count--;
+        pthread_mutex_unlock(&queue->mutex);
+        return task;
+}
+STATIC void *
+start_thread(void *arg)
+{
+        task_queue_t *queue = (task_queue_t *)arg;
+        while (true)
+        {
+                dfsarg_solveh48_t *task = get_task(queue);
+                if (task == NULL)
+                {
+                        break;
+                }
+                solve_h48_single(task, queue);
+                free(task);
+                pthread_mutex_lock(&queue->active_tasks_mutex);
+                atomic_fetch_sub(&queue->active_tasks, 1);
+                if (atomic_load(&queue->active_tasks) == 0)
+                {
+                        pthread_cond_signal(&queue->active_tasks_cond);
+                }
+                pthread_mutex_unlock(&queue->active_tasks_mutex);
+        }
+        return NULL;
+}
+STATIC int64_t
+solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq)
+{
+        dfsarg_solveh48_t queue[MAX_QUEUE_SIZE];
+        int front = 0, rear = 0;
+        dfsarg_solveh48_t nextarg;
+        int depth = 0;
+        int nodes_at_current_depth = 1;
+        int nodes_at_next_depth = 0;
+        queue[rear++] = *arg_zero;
+        while (front < rear)
+        {
+                dfsarg_solveh48_t arg = queue[front++];
+                nodes_at_current_depth--;
+                if (*arg.nsols == arg.maxsolutions)
+                        return 1;
+                if (issolved(arg.cube))
+                {
+                        if (arg.nmoves + arg.npremoves != arg.depth)
+                                continue;
+                        solve_h48_appendsolution(&arg);
+                        continue;
+                }
+                arg.nissbranch = MM_NORMAL;
+                uint32_t allowed = allowednextmove_h48(arg.moves, arg.nmoves, arg.nissbranch);
+                for (uint8_t m = 0; m < 18; m++)
+                {
+                        if (allowed & (1 << m))
+                        {
+                                nextarg = arg;
+                                nextarg.nmoves = arg.nmoves + 1;
+                                nextarg.moves[arg.nmoves] = m;
+                                nextarg.cube = move(arg.cube, m);
+                                nextarg.inverse = premove(arg.inverse, m);
+                                if (nextarg.nmoves == 2)
+                                {
+                                        dfsarg_solveh48_t *task = malloc(sizeof(dfsarg_solveh48_t));
+                                        *task = nextarg;
+                                        submit_task(tq, task);
+                                }
+                                else
+                                {
+                                        queue[rear++] = nextarg;
+                                        nodes_at_next_depth++;
+                                }
+                        }
+                }
+                if (nodes_at_current_depth == 0)
+                {
+                        depth++;
+                        nodes_at_current_depth = nodes_at_next_depth;
+                        nodes_at_next_depth = 0;
+                }
+                if (depth == 2)
+                {
+                        return 0;
+                }
+        }
+        return 0;
+}
+STATIC int64_t
+solve_h48_single(dfsarg_solveh48_t *arg, task_queue_t *tq)
+{
+        dfsarg_solveh48_t nextarg;
+        int64_t ret;
+        uint8_t m;
+        if (*arg->nsols == arg->maxsolutions)
+                return 0;
+        if (solve_h48_stop(arg))
+                return 0;
+        if (issolved(arg->cube))
+        {
+                if (arg->nmoves + arg->npremoves != arg->depth)
+                        return 0;
+                solve_h48_appendsolution_thread(arg, tq);
+                return 1;
+        }
+        nextarg = *arg;
+        ret = 0;
+        uint32_t allowed;
+        if (arg->nissbranch & MM_INVERSE)
+        {
+                allowed = allowednextmove_h48(arg->premoves, arg->npremoves, arg->nissbranch);
+                for (m = 0; m < 18; m++)
+                {
+                        if (allowed & (1 << m))
+                        {
+                                nextarg.npremoves = arg->npremoves + 1;
+                                nextarg.premoves[arg->npremoves] = m;
+                                nextarg.inverse = move(arg->inverse, m);
+                                nextarg.cube = premove(arg->cube, m);
+                                ret += solve_h48_single(&nextarg, tq);
+                        }
+                }
+        }
+        else
+        {
+                allowed = allowednextmove_h48(arg->moves, arg->nmoves, arg->nissbranch);
+                for (m = 0; m < 18; m++)
+                {
+                        if (allowed & (1 << m))
+                        {
+                                nextarg.nmoves = arg->nmoves + 1;
+                                nextarg.moves[arg->nmoves] = m;
+                                nextarg.cube = move(arg->cube, m);
+                                nextarg.inverse = premove(arg->inverse, m);
+                                ret += solve_h48_single(&nextarg, tq);
+                        }
+                }
+        }
+        return ret;
+}
+STATIC int64_t
+solve_h48_parent(
+        cube_t cube,
+        int8_t minmoves,
+        int8_t maxmoves,
+        int8_t maxsolutions,
+        const void *data,
+        char *solutions)
+{
+        int64_t nsols;
+        int p_depth = 0;
+        dfsarg_solveh48_t bfs_arg;
+        tableinfo_t info;
+        pthread_t threads[THREADS];
+        if (!readtableinfo_n(data, 2, &info))
+        {
+                LOG("solve_h48: error reading table\n");
+                return 0;
+        }
+        bfs_arg = (dfsarg_solveh48_t){
+                .cube = cube,
+                .inverse = inverse(cube),
+                .nsols = &nsols,
+                .maxsolutions = maxsolutions,
+                .h = info.h48h,
+                .k = info.bits,
+                .cocsepdata = get_cocsepdata_ptr(data),
+                .h48data = get_h48data_ptr(data),
+                .nextsol = &solutions};
+        task_queue_t q;
+        init_queue(&q);
+        if (solve_h48_bfs(&bfs_arg, &q))
+                return nsols;
+        task_queue_t nq;
+        init_queue(&nq);
+        atomic_store(&nq.active_tasks, 0);
+        pthread_mutex_init(&nq.active_tasks_mutex, NULL);
+        pthread_cond_init(&nq.active_tasks_cond, NULL);
+        for (int i = 0; i < THREADS; i++)
+        {
+                pthread_create(&threads[i], NULL, &start_thread, &nq);
+        }
+        nsols = 0;
+        for (p_depth = minmoves > 2 ? minmoves : 2;
+                 p_depth <= maxmoves && nsols < maxsolutions;
+                 p_depth++)
+        {
+                LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", nsols, p_depth);
+                copy_queue(&q, &nq, p_depth);
+                pthread_mutex_lock(&nq.active_tasks_mutex);
+                while (nq.active_tasks > 0)
+                {
+                        pthread_cond_wait(&nq.active_tasks_cond, &nq.active_tasks_mutex);
+                }
+                pthread_mutex_unlock(&nq.active_tasks_mutex);
+        }
+        for (int i = 0; i < THREADS; i++)
+        {
+                pthread_join(threads[i], NULL);
+        }
+        return nsols;
+}

diff --git a/src/solvers/h48/h48.h b/src/solvers/h48/h48.h index 4edc5ac..ee865d9 100644 --- a/src/solvers/h48/h48.h +++ b/src/solvers/h48/h48.h
@@ -3,3 +3,4 @@
3	#include "gendata_cocsep.h"	3	#include "gendata_cocsep.h"
4	#include "gendata_h48.h"	4	#include "gendata_h48.h"
5	#include "solve.h"	5	#include "solve.h"
		6	#include "thread.h"


diff --git a/src/solvers/h48/thread.h b/src/solvers/h48/thread.h new file mode 100644 index 0000000..1eade29 --- /dev/null +++ b/src/solvers/h48/thread.h
@@ -0,0 +1,335 @@
		1	#include <pthread.h>
		2	#include <stdatomic.h>
		3	#include <stdbool.h>
		4	#include <stdio.h>
		5	#include <stdlib.h>
		6
		7	#define MAX_QUEUE_SIZE 500
		8
		9	typedef struct
		10	{
		11	dfsarg_solveh48_t *tasks[MAX_QUEUE_SIZE];
		12	int front;
		13	int rear;
		14	int tasks_count;
		15	pthread_mutex_t mutex;
		16	pthread_cond_t cond;
		17	atomic_int active_tasks;
		18	pthread_mutex_t active_tasks_mutex;
		19	pthread_cond_t active_tasks_cond;
		20	} task_queue_t;
		21
		22	STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t , task_queue_t );
		23	STATIC void init_queue(task_queue_t *);
		24	STATIC void submit_task(task_queue_t , dfsarg_solveh48_t );
		25	STATIC void copy_queue(task_queue_t , task_queue_t , int);
		26	STATIC dfsarg_solveh48_t get_task(task_queue_t );
		27	STATIC void start_thread(void );
		28	STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t , task_queue_t );
		29	STATIC int64_t solve_h48_single(dfsarg_solveh48_t , task_queue_t );
		30	STATIC int64_t solve_h48_parent(cube_t, int8_t, int8_t, int8_t, const void , char );
		31
		32	STATIC void
		33	solve_h48_appendsolution_thread(dfsarg_solveh48_t arg, task_queue_t tq){
		34	pthread_mutex_lock(&tq->mutex);
		35	int strl;
		36	uint8_t invertedpremoves[MAXLEN];
		37	char solution = arg->nextsol;
		38
		39	strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol);
		40	*arg->nextsol += strl;
		41
		42	if (arg->npremoves)
		43	{
		44	**arg->nextsol = ' ';
		45	(*arg->nextsol)++;
		46
		47	invertmoves(arg->premoves, arg->npremoves, invertedpremoves);
		48	strl = writemoves(invertedpremoves, arg->npremoves, *arg->nextsol);
		49	*arg->nextsol += strl;
		50	}
		51	LOG("Solution found: %s\n", solution);
		52
		53	**arg->nextsol = '\n';
		54	(*arg->nextsol)++;
		55	(*arg->nsols)++;
		56	pthread_mutex_unlock(&tq->mutex);
		57	}
		58
		59	STATIC void
		60	init_queue(task_queue_t *queue)
		61	{
		62	queue->front = 0;
		63	queue->rear = 0;
		64	queue->tasks_count = 0;
		65	pthread_mutex_init(&queue->mutex, NULL);
		66	pthread_cond_init(&queue->cond, NULL);
		67	}
		68
		69	STATIC void
		70	submit_task(task_queue_t queue, dfsarg_solveh48_t task)
		71	{
		72	pthread_mutex_lock(&queue->mutex);
		73	queue->tasks[queue->rear] = task;
		74	queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
		75	queue->tasks_count++;
		76	pthread_cond_signal(&queue->cond);
		77	pthread_mutex_unlock(&queue->mutex);
		78	}
		79
		80	STATIC void
		81	copy_queue(task_queue_t src, task_queue_t dest, int depth)
		82	{
		83	pthread_mutex_lock(&src->mutex);
		84	pthread_mutex_lock(&dest->mutex);
		85	for (int i = src->front; i != src->rear; i = (i + 1) % MAX_QUEUE_SIZE)
		86	{
		87	if (src->tasks[i] != NULL)
		88	{
		89	dest->tasks[i] = src->tasks[i];
		90	dest->tasks[i]->depth = depth;
		91	}
		92	}
		93	dest->front = src->front;
		94	dest->rear = src->rear;
		95	dest->tasks_count = src->tasks_count;
		96	pthread_mutex_unlock(&src->mutex);
		97	pthread_cond_signal(&dest->cond);
		98	pthread_mutex_unlock(&dest->mutex);
		99	}
		100	STATIC dfsarg_solveh48_t *
		101	get_task(task_queue_t *queue)
		102	{
		103	pthread_mutex_lock(&queue->mutex);
		104	while (queue->tasks_count == 0)
		105	{
		106	pthread_cond_wait(&queue->cond, &queue->mutex);
		107	}
		108	dfsarg_solveh48_t *task = queue->tasks[queue->front];
		109	queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
		110	queue->tasks_count--;
		111	pthread_mutex_unlock(&queue->mutex);
		112	return task;
		113	}
		114
		115	STATIC void *
		116	start_thread(void *arg)
		117	{
		118	task_queue_t queue = (task_queue_t )arg;
		119	while (true)
		120	{
		121	dfsarg_solveh48_t *task = get_task(queue);
		122	if (task == NULL)
		123	{
		124	break;
		125	}
		126	solve_h48_single(task, queue);
		127	free(task);
		128
		129	pthread_mutex_lock(&queue->active_tasks_mutex);
		130	atomic_fetch_sub(&queue->active_tasks, 1);
		131	if (atomic_load(&queue->active_tasks) == 0)
		132	{
		133	pthread_cond_signal(&queue->active_tasks_cond);
		134	}
		135	pthread_mutex_unlock(&queue->active_tasks_mutex);
		136	}
		137	return NULL;
		138	}
		139
		140	STATIC int64_t
		141	solve_h48_bfs(dfsarg_solveh48_t arg_zero, task_queue_t tq)
		142	{
		143	dfsarg_solveh48_t queue[MAX_QUEUE_SIZE];
		144	int front = 0, rear = 0;
		145	dfsarg_solveh48_t nextarg;
		146	int depth = 0;
		147	int nodes_at_current_depth = 1;
		148	int nodes_at_next_depth = 0;
		149
		150	queue[rear++] = *arg_zero;
		151
		152	while (front < rear)
		153	{
		154	dfsarg_solveh48_t arg = queue[front++];
		155	nodes_at_current_depth--;
		156
		157	if (*arg.nsols == arg.maxsolutions)
		158	return 1;
		159
		160	if (issolved(arg.cube))
		161	{
		162	if (arg.nmoves + arg.npremoves != arg.depth)
		163	continue;
		164	solve_h48_appendsolution(&arg);
		165	continue;
		166	}
		167
		168	arg.nissbranch = MM_NORMAL;
		169	uint32_t allowed = allowednextmove_h48(arg.moves, arg.nmoves, arg.nissbranch);
		170
		171	for (uint8_t m = 0; m < 18; m++)
		172	{
		173	if (allowed & (1 << m))
		174	{
		175	nextarg = arg;
		176	nextarg.nmoves = arg.nmoves + 1;
		177	nextarg.moves[arg.nmoves] = m;
		178	nextarg.cube = move(arg.cube, m);
		179	nextarg.inverse = premove(arg.inverse, m);
		180
		181	if (nextarg.nmoves == 2)
		182	{
		183	dfsarg_solveh48_t *task = malloc(sizeof(dfsarg_solveh48_t));
		184	*task = nextarg;
		185	submit_task(tq, task);
		186	}
		187	else
		188	{
		189	queue[rear++] = nextarg;
		190	nodes_at_next_depth++;
		191	}
		192	}
		193	}
		194
		195	if (nodes_at_current_depth == 0)
		196	{
		197	depth++;
		198	nodes_at_current_depth = nodes_at_next_depth;
		199	nodes_at_next_depth = 0;
		200	}
		201	if (depth == 2)
		202	{
		203	return 0;
		204	}
		205	}
		206	return 0;
		207	}
		208
		209	STATIC int64_t
		210	solve_h48_single(dfsarg_solveh48_t arg, task_queue_t tq)
		211	{
		212	dfsarg_solveh48_t nextarg;
		213	int64_t ret;
		214	uint8_t m;
		215
		216	if (*arg->nsols == arg->maxsolutions)
		217	return 0;
		218
		219	if (solve_h48_stop(arg))
		220	return 0;
		221
		222	if (issolved(arg->cube))
		223	{
		224	if (arg->nmoves + arg->npremoves != arg->depth)
		225	return 0;
		226	solve_h48_appendsolution_thread(arg, tq);
		227	return 1;
		228	}
		229
		230	nextarg = *arg;
		231	ret = 0;
		232	uint32_t allowed;
		233	if (arg->nissbranch & MM_INVERSE)
		234	{
		235	allowed = allowednextmove_h48(arg->premoves, arg->npremoves, arg->nissbranch);
		236	for (m = 0; m < 18; m++)
		237	{
		238	if (allowed & (1 << m))
		239	{
		240	nextarg.npremoves = arg->npremoves + 1;
		241	nextarg.premoves[arg->npremoves] = m;
		242	nextarg.inverse = move(arg->inverse, m);
		243	nextarg.cube = premove(arg->cube, m);
		244	ret += solve_h48_single(&nextarg, tq);
		245	}
		246	}
		247	}
		248	else
		249	{
		250	allowed = allowednextmove_h48(arg->moves, arg->nmoves, arg->nissbranch);
		251	for (m = 0; m < 18; m++)
		252	{
		253	if (allowed & (1 << m))
		254	{
		255	nextarg.nmoves = arg->nmoves + 1;
		256	nextarg.moves[arg->nmoves] = m;
		257	nextarg.cube = move(arg->cube, m);
		258	nextarg.inverse = premove(arg->inverse, m);
		259	ret += solve_h48_single(&nextarg, tq);
		260	}
		261	}
		262	}
		263	return ret;
		264	}
		265
		266	STATIC int64_t
		267	solve_h48_parent(
		268	cube_t cube,
		269	int8_t minmoves,
		270	int8_t maxmoves,
		271	int8_t maxsolutions,
		272	const void *data,
		273	char *solutions)
		274	{
		275	int64_t nsols;
		276	int p_depth = 0;
		277	dfsarg_solveh48_t bfs_arg;
		278	tableinfo_t info;
		279	pthread_t threads[THREADS];
		280
		281	if (!readtableinfo_n(data, 2, &info))
		282	{
		283	LOG("solve_h48: error reading table\n");
		284	return 0;
		285	}
		286
		287	bfs_arg = (dfsarg_solveh48_t){
		288	.cube = cube,
		289	.inverse = inverse(cube),
		290	.nsols = &nsols,
		291	.maxsolutions = maxsolutions,
		292	.h = info.h48h,
		293	.k = info.bits,
		294	.cocsepdata = get_cocsepdata_ptr(data),
		295	.h48data = get_h48data_ptr(data),
		296	.nextsol = &solutions};
		297
		298	task_queue_t q;
		299	init_queue(&q);
		300	if (solve_h48_bfs(&bfs_arg, &q))
		301	return nsols;
		302
		303	task_queue_t nq;
		304	init_queue(&nq);
		305
		306	atomic_store(&nq.active_tasks, 0);
		307	pthread_mutex_init(&nq.active_tasks_mutex, NULL);
		308	pthread_cond_init(&nq.active_tasks_cond, NULL);
		309
		310	for (int i = 0; i < THREADS; i++)
		311	{
		312	pthread_create(&threads[i], NULL, &start_thread, &nq);
		313	}
		314
		315	nsols = 0;
		316	for (p_depth = minmoves > 2 ? minmoves : 2;
		317	p_depth <= maxmoves && nsols < maxsolutions;
		318	p_depth++)
		319	{
		320	LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", nsols, p_depth);
		321	copy_queue(&q, &nq, p_depth);
		322	pthread_mutex_lock(&nq.active_tasks_mutex);
		323	while (nq.active_tasks > 0)
		324	{
		325	pthread_cond_wait(&nq.active_tasks_cond, &nq.active_tasks_mutex);
		326	}
		327	pthread_mutex_unlock(&nq.active_tasks_mutex);
		328	}
		329	for (int i = 0; i < THREADS; i++)
		330	{
		331	pthread_join(threads[i], NULL);
		332	}
		333
		334	return nsols;
		335	}