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 (13846B)


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