h48

A prototype for an optimal Rubik's cube solver, work in progress.
git clone https://git.tronto.net/h48
Download | Log | Files | Refs | README | LICENSE

nissy.c (12491B)


      1 #include <inttypes.h>
      2 #include <limits.h>
      3 #include <pthread.h>
      4 #include <stdatomic.h>
      5 #include <stdarg.h>
      6 #include <stdbool.h>
      7 #include <string.h>
      8 
      9 #include "nissy.h"
     10 #include "utils/utils.h"
     11 #include "arch/arch.h"
     12 #include "core/core.h"
     13 #include "solvers/solvers.h"
     14 
     15 long long parse_h48_solver(
     16     const char *, uint8_t [static 1], uint8_t [static 1]);
     17 STATIC bool checkdata(const char *, const tableinfo_t *);
     18 STATIC bool distribution_equal(const uint64_t [static INFO_DISTRIBUTION_LEN],
     19     const uint64_t [static INFO_DISTRIBUTION_LEN], uint8_t);
     20 STATIC long long write_result(cube_t, char [static NISSY_SIZE_B32]);
     21 STATIC size_t my_strnlen(const char *, size_t); 
     22 STATIC long long nissy_gendata_unsafe(
     23     const char *, unsigned long long, char *);
     24 
     25 #define GETCUBE_OPTIONS(S, F) { .option = S, .fix = F }
     26 struct {
     27 	char *option;
     28 	void (*fix)(long long *, long long *, long long *, long long *);
     29 } getcube_options[] = {
     30 	GETCUBE_OPTIONS("fix", getcube_fix),
     31 	GETCUBE_OPTIONS(NULL, NULL)
     32 };
     33 
     34 long long
     35 parse_h48_solver(const char *buf, uint8_t h[static 1], uint8_t k[static 1])
     36 {
     37 	const char *fullbuf = buf;
     38 
     39 	buf += 3;
     40 
     41 	if (*buf != 'h')
     42 		goto parse_h48_solver_error;
     43 	buf++;
     44 
     45 	*h = atoi(buf);
     46 
     47 	for ( ; *buf >= 0 + '0' && *buf <= 9 + '0'; buf++)
     48 		if (*buf == 0)
     49 			goto parse_h48_solver_error;
     50 
     51 	if (*buf != 'k')
     52 		goto parse_h48_solver_error;
     53 	buf++;
     54 
     55 	*k = atoi(buf);
     56 
     57 	return *h < 12 && (*k == 2 || (*k == 4 && *h == 0)) ? 0 : 1;
     58 
     59 parse_h48_solver_error:
     60 	*h = 0;
     61 	*k = 0;
     62 	LOG("Error parsing solver: must be in \"h48h*k*\" format,"
     63 	    " but got %s\n", fullbuf);
     64 	return NISSY_ERROR_INVALID_SOLVER;
     65 }
     66 
     67 STATIC bool
     68 checkdata(const char *buf, const tableinfo_t *info)
     69 {
     70 	uint64_t distr[INFO_DISTRIBUTION_LEN];
     71 
     72 	if (info == NULL || my_strnlen(info->solver, INFO_SOLVER_STRLEN)
     73 	    == INFO_SOLVER_STRLEN) {
     74 		LOG("checkdata: error reading table info\n");
     75 		return false;
     76 	} else if (!strncmp(info->solver, "cocsep", 6)) {
     77 		getdistribution_cocsep(
     78 		    (uint32_t *)((char *)buf + INFOSIZE), distr);
     79 	} else if (!strncmp(info->solver, "h48", 3)) {
     80 		getdistribution_h48((uint8_t *)buf + INFOSIZE, distr,
     81 		    info->h48h, info->bits);
     82 	} else if (!strncmp(info->solver, "eoesep data for h48", 19)) {
     83 		return true;
     84 	} else {
     85 		LOG("checkdata: unknown solver %s\n", info->solver);
     86 		return false;
     87 	}
     88 
     89 	return distribution_equal(info->distribution, distr, info->maxvalue);
     90 }
     91 
     92 STATIC bool
     93 distribution_equal(
     94 	const uint64_t expected[static INFO_DISTRIBUTION_LEN],
     95 	const uint64_t actual[static INFO_DISTRIBUTION_LEN],
     96 	uint8_t maxvalue
     97 )
     98 {
     99 	int wrong;
    100 	uint8_t i;
    101 
    102 	for (i = 0, wrong = 0; i <= MAX(maxvalue, 20); i++) {
    103 		if (expected[i] != actual[i]) {
    104 			wrong++;
    105 			LOG("Value %" PRIu8 ": expected %" PRIu64 ", found %"
    106 			    PRIu64 "\n", i, expected[i], actual[i]);
    107 		}
    108 	}
    109 
    110 	return wrong == 0;
    111 }
    112 
    113 STATIC long long
    114 write_result(cube_t cube, char result[static NISSY_SIZE_B32])
    115 {
    116 	writecube("B32", cube, NISSY_SIZE_B32, result);
    117 
    118 	if (!issolvable(cube)) {
    119 		LOG("Warning: resulting cube is not solvable\n");
    120 		return NISSY_WARNING_UNSOLVABLE;
    121 	}
    122 
    123 	return NISSY_OK;
    124 }
    125 
    126 STATIC size_t
    127 my_strnlen(const char *str, size_t maxlen)
    128 {
    129 	size_t i;
    130 
    131 	for (i = 0; i < maxlen; i++)
    132 		if (str[i] == '\0')
    133 			return i;
    134 
    135 	return maxlen;
    136 }
    137 
    138 long long
    139 nissy_compose(
    140 	const char cube[static NISSY_SIZE_B32],
    141 	const char permutation[static NISSY_SIZE_B32],
    142 	char result[static NISSY_SIZE_B32]
    143 )
    144 {
    145 	cube_t c, p, res;
    146 	long long err;
    147 
    148 	c = readcube("B32", cube);
    149 
    150 	if (!isconsistent(c)) {
    151 		LOG("Error in nissy_compose: given cube is invalid\n");
    152 		err = NISSY_ERROR_INVALID_CUBE;
    153 		goto nissy_compose_error;
    154 	}
    155 
    156 	p = readcube("B32", permutation);
    157 
    158 	if (!isconsistent(p)) {
    159 		LOG("Error in nissy_compose: given permutation is invalid\n");
    160 		err = NISSY_ERROR_INVALID_CUBE;
    161 		goto nissy_compose_error;
    162 	}
    163 
    164 	res = compose(c, p);
    165 
    166 	if (!isconsistent(res)) {
    167 		LOG("Unknown error: resulting cube is invalid\n");
    168 		err = NISSY_ERROR_UNKNOWN;
    169 		goto nissy_compose_error;
    170 	}
    171 
    172 	return write_result(res, result);
    173 
    174 nissy_compose_error:
    175 	writecube("B32", ZERO_CUBE, NISSY_SIZE_B32, result);
    176 	return err;
    177 }
    178 
    179 long long
    180 nissy_inverse(
    181 	const char cube[static NISSY_SIZE_B32],
    182 	char result[static NISSY_SIZE_B32]
    183 )
    184 {
    185 	cube_t c, res;
    186 	long long err;
    187 
    188 	c = readcube("B32", cube);
    189 
    190 	if (iserror(c)) {
    191 		LOG("Error in nissy_inverse: given cube is invalid\n");
    192 		err = NISSY_ERROR_INVALID_CUBE;
    193 		goto nissy_inverse_error;
    194 	}
    195 
    196 	res = inverse(c);
    197 
    198 	if (!isconsistent(res)) {
    199 		LOG("Unknown error: inverted cube is invalid\n");
    200 		err = NISSY_ERROR_UNKNOWN;
    201 		goto nissy_inverse_error;
    202 	}
    203 
    204 	return write_result(res, result);
    205 
    206 nissy_inverse_error:
    207 	writecube("B32", ZERO_CUBE, NISSY_SIZE_B32, result);
    208 	return err;
    209 }
    210 
    211 long long
    212 nissy_applymoves(
    213 	const char cube[static NISSY_SIZE_B32],
    214 	const char *moves,
    215 	char result[static NISSY_SIZE_B32]
    216 )
    217 {
    218 	cube_t c, res;
    219 	long long err;
    220 
    221 	if (moves == NULL) {
    222 		LOG("Error: 'moves' argument is NULL\n");
    223 		err = NISSY_ERROR_NULL_POINTER;
    224 		goto nissy_applymoves_error;
    225 	}
    226 
    227 	c = readcube("B32", cube);
    228 
    229 	if (!isconsistent(c)) {
    230 		LOG("Error in nissy_applymoves: given cube is invalid\n");
    231 		err = NISSY_ERROR_INVALID_CUBE;
    232 		goto nissy_applymoves_error;
    233 	}
    234 
    235 	res = applymoves(c, moves);
    236 
    237 	if (!isconsistent(res)) {
    238 		/* Assume we got a reasonable error message from applymoves */
    239 		err = NISSY_ERROR_INVALID_MOVES;
    240 		goto nissy_applymoves_error;
    241 	}
    242 
    243 	return write_result(res, result);
    244 
    245 nissy_applymoves_error:
    246 	writecube("B32", ZERO_CUBE, NISSY_SIZE_B32, result);
    247 	return err;
    248 }
    249 
    250 long long
    251 nissy_applytrans(
    252 	const char cube[static NISSY_SIZE_B32],
    253 	const char transformation[static NISSY_SIZE_TRANSFORMATION],
    254 	char result[static NISSY_SIZE_B32]
    255 )
    256 {
    257 	cube_t c, res;
    258 	long long err;
    259 
    260 	c = readcube("B32", cube);
    261 
    262 	if (!isconsistent(c)) {
    263 		LOG("Error in nissy_applytrans: given cube is invalid\n");
    264 		err = NISSY_ERROR_INVALID_CUBE;
    265 		goto nissy_applytrans_error;
    266 	}
    267 
    268 	res = applytrans(c, transformation);
    269 
    270 	if (!isconsistent(res)) {
    271 		/* Assume we got a reasonable error message from applytrans */
    272 		err = NISSY_ERROR_INVALID_TRANS;
    273 		goto nissy_applytrans_error;
    274 	}
    275 
    276 	return write_result(res, result);
    277 
    278 nissy_applytrans_error:
    279 	writecube("B32", ZERO_CUBE, NISSY_SIZE_B32, result);
    280 	return err;
    281 }
    282 
    283 long long
    284 nissy_convert(
    285 	const char *format_in,
    286 	const char *format_out,
    287 	const char *cube_string,
    288         unsigned result_size,
    289 	char result[result_size]
    290 )
    291 {
    292 	cube_t c;
    293 	long long err;
    294 
    295 	if (format_in == NULL) {
    296 		LOG("Error: 'format_in' argument is NULL\n");
    297 		err = NISSY_ERROR_NULL_POINTER;
    298 		goto nissy_convert_error;
    299 	}
    300 
    301 	if (format_out == NULL) {
    302 		LOG("Error: 'format_out' argument is NULL\n");
    303 		err = NISSY_ERROR_NULL_POINTER;
    304 		goto nissy_convert_error;
    305 	}
    306 
    307 	if (cube_string == NULL) {
    308 		LOG("Error: 'cube_string' argument is NULL\n");
    309 		err = NISSY_ERROR_NULL_POINTER;
    310 		goto nissy_convert_error;
    311 	}
    312 
    313 	c = readcube(format_in, cube_string);
    314 
    315 	if (!isconsistent(c)) {
    316 		err = NISSY_ERROR_INVALID_CUBE;
    317 		goto nissy_convert_error;
    318 	}
    319 
    320 	return writecube(format_out, c, result_size, result);
    321 
    322 nissy_convert_error:
    323 	result[0] = '\0';
    324 	return err;
    325 }
    326 
    327 long long
    328 nissy_getcube(
    329 	long long ep,
    330 	long long eo,
    331 	long long cp,
    332 	long long co,
    333 	const char *options,
    334 	char result[static NISSY_SIZE_B32]
    335 )
    336 {
    337 	int i;
    338 	cube_t c;
    339 
    340 	if (options == NULL) {
    341 		LOG("Error: 'options' argument is NULL\n");
    342 		return NISSY_ERROR_NULL_POINTER;
    343 	}
    344 
    345 	for (i = 0; getcube_options[i].option != NULL; i++)
    346 		if (!strcmp(options, getcube_options[i].option))
    347 			getcube_options[i].fix(&ep, &eo, &cp, &co);
    348 
    349 	c = getcube(ep, eo, cp, co);
    350 
    351 	if (!isconsistent(c)) {
    352 		LOG("Error: could not get cube with ep=%" PRId64 ", eo=%"
    353 		    PRId64 ", cp=%" PRId64 ", co=%" PRId64 ".\n",
    354 		    ep, eo, cp, co);
    355 		return NISSY_ERROR_OPTIONS;
    356 	}
    357 
    358 	return write_result(c, result);
    359 }
    360 
    361 long long
    362 nissy_datainfo(
    363         uint64_t data_size,
    364 	const char data[data_size],
    365 	void (*write)(const char *, ...)
    366 )
    367 {
    368 	uint8_t i;
    369 	tableinfo_t info;
    370 	long long ret;
    371 
    372 	if ((size_t)data % 8 != 0) {
    373 		LOG("nissy_datainfo: buffere is not 8-byte aligned\n");
    374 		return NISSY_ERROR_DATA;
    375 	}
    376 
    377 	ret = readtableinfo(data_size, data, &info);
    378 	if (ret != 0)
    379 		return ret;
    380 
    381 	write("\n---------\n\n");
    382 	write("Table information for '%s'\n", info.solver);
    383 	write("\n");
    384 	write("Size:      %" PRIu64 " bytes\n", info.fullsize);
    385 	write("Entries:   %" PRIu64 " (%" PRIu8 " bits per entry)",
    386 	    info.entries, info.bits);
    387 	write("\n");
    388 
    389 	switch (info.type) {
    390 	case TABLETYPE_PRUNING:
    391 		write("\n");
    392 		write("Table distribution:\nValue\tPositions\n");
    393 		for (i = 0; i <= info.maxvalue; i++) {
    394 			write("%" PRIu8 "\t%" PRIu64 "\n",
    395 			    i + info.base, info.distribution[i]);
    396 		}
    397 		break;
    398 	case TABLETYPE_SPECIAL:
    399 		write("This is an ad-hoc table\n");
    400 		break;
    401 	default:
    402 		LOG("datainfo: unknown table type\n");
    403 		return NISSY_ERROR_DATA;
    404 	}
    405 
    406 	if (info.next != 0)
    407 		return nissy_datainfo(
    408 		    data_size - info.next, (char *)data + info.next, write);
    409 
    410 	write("\n---------\n");
    411 
    412 	return NISSY_OK;
    413 }
    414 
    415 long long
    416 nissy_datasize(
    417 	const char *solver
    418 )
    419 {
    420 	/* gendata() handles a NULL *data as a "dryrun" request */
    421 	return nissy_gendata_unsafe(solver, 0, NULL);
    422 }
    423 
    424 long long
    425 nissy_gendata(
    426 	const char *solver,
    427 	unsigned long long data_size,
    428 	char data[data_size]
    429 )
    430 {
    431 	return nissy_gendata_unsafe(solver, data_size, data);
    432 }
    433 
    434 STATIC long long
    435 nissy_gendata_unsafe(
    436 	const char *solver,
    437 	unsigned long long data_size,
    438 	char *data
    439 )
    440 {
    441 	long long parse_ret;
    442 	gendata_h48_arg_t arg;
    443 
    444 	if (solver == NULL) {
    445 		LOG("Error: 'solver' argument is NULL\n");
    446 		return NISSY_ERROR_NULL_POINTER;
    447 	}
    448 
    449 	if ((size_t)data % 8 != 0) {
    450 		LOG("nissy_datainfo: buffere is not 8-byte aligned\n");
    451 		return NISSY_ERROR_DATA;
    452 	}
    453 
    454 	arg.buf_size = data_size;
    455 	arg.buf = data;
    456 	if (!strncmp(solver, "h48", 3)) {
    457 		parse_ret = parse_h48_solver(solver, &arg.h, &arg.k);
    458 		arg.maxdepth = 20;
    459 		if (parse_ret != NISSY_OK)
    460 			return parse_ret;
    461 		return gendata_h48(&arg);
    462 	} else {
    463 		LOG("gendata: unknown solver %s\n", solver);
    464 		return NISSY_ERROR_INVALID_SOLVER;
    465 	}
    466 }
    467 
    468 long long
    469 nissy_checkdata(
    470 	unsigned long long data_size,
    471 	const char data[data_size]
    472 )
    473 {
    474 	char *buf;
    475 	tableinfo_t info;
    476 	int64_t err;
    477 
    478 	if ((size_t)data % 8 != 0) {
    479 		LOG("nissy_datainfo: buffere is not 8-byte aligned\n");
    480 		return NISSY_ERROR_DATA;
    481 	}
    482 
    483 	for (buf = (char *)data;
    484 	     (err = readtableinfo(data_size, buf, &info)) == NISSY_OK;
    485 	     buf += info.next, data_size -= info.next)
    486 	{
    487 		if (!checkdata(buf, &info)) {
    488 			LOG("Error: data for solver '%s' is corrupted!\n",
    489 			    info.solver);
    490 			return NISSY_ERROR_DATA;
    491 		}
    492 
    493 		if (info.next == 0)
    494 			break;
    495 	}
    496 
    497 	return err;
    498 }
    499 
    500 long long
    501 nissy_solve(
    502 	const char cube[static NISSY_SIZE_B32],
    503 	const char *solver, 
    504 	unsigned nissflag,
    505 	unsigned minmoves,
    506 	unsigned maxmoves,
    507 	unsigned maxsols,
    508 	int optimal,
    509 	int threads,
    510 	unsigned long long data_size,
    511 	const char data[data_size],
    512 	unsigned sols_size,
    513 	char sols[sols_size],
    514 	long long stats[static NISSY_SIZE_SOLVE_STATS]
    515 )
    516 {
    517 	cube_t c;
    518 	long long parse_ret;
    519 	uint8_t h, k;
    520 	int t, opt;
    521 
    522 	if (solver == NULL) {
    523 		LOG("Error: 'solver' argument is NULL\n");
    524 		return NISSY_ERROR_NULL_POINTER;
    525 	}
    526 
    527 	c = readcube_B32(cube);
    528 
    529 	if (!isconsistent(c)) {
    530 		LOG("solve: cube is invalid\n");
    531 		return NISSY_ERROR_INVALID_CUBE;
    532 	}
    533 
    534 	if (!issolvable(c)) {
    535 		LOG("solve: cube is not solvable\n");
    536 		return NISSY_ERROR_UNSOLVABLE_CUBE;
    537 	}
    538 
    539 	if (maxsols == 0) {
    540 		LOG("solve: 'maxsols' is 0, returning no solution\n");
    541 		return 0;
    542 	}
    543 
    544 	opt = optimal < 0 ? MAXLEN : optimal;
    545 
    546 	t = threads == 0 ? THREADS : threads;
    547 	if (t < 0) {
    548 		LOG("solve: 'threads' is negative. Please provide a "
    549 		    "number of threads between 1 and %d\n", THREADS);
    550 		return NISSY_ERROR_OPTIONS;
    551 	} 
    552 	if (t > THREADS) {
    553 		LOG("solve: 'threads' is above the maximum value of %d\n",
    554 		    THREADS);
    555 		return NISSY_ERROR_OPTIONS;
    556 	}
    557 
    558 	if ((size_t)data % 8 != 0) {
    559 		LOG("nissy_datainfo: buffere is not 8-byte aligned\n");
    560 		return NISSY_ERROR_DATA;
    561 	}
    562 
    563 	if (!strncmp(solver, "h48", 3)) {
    564 		parse_ret = parse_h48_solver(solver, &h, &k);
    565 		if (parse_ret == NISSY_OK)
    566 			return solve_h48(c, minmoves, maxmoves, maxsols, opt,
    567 				t, data_size, data, sols_size, sols, stats);
    568 		else
    569 			return parse_ret;
    570 	} else {
    571 		LOG("solve: unknown solver '%s'\n", solver);
    572 		return NISSY_ERROR_INVALID_SOLVER;
    573 	}
    574 }
    575 
    576 long long
    577 nissy_countmoves(
    578 	const char *moves
    579 )
    580 {
    581 	if (moves == NULL)
    582 		return NISSY_ERROR_NULL_POINTER;
    583 
    584 	return readmoves(moves, INT_MAX, NULL);
    585 }
    586 
    587 long long
    588 nissy_setlogger(
    589 	void (*log)(const char *, ...)
    590 )
    591 {
    592 	nissy_log = log;
    593 	return NISSY_OK;
    594 }