nissy-core

The "engine" of nissy, including the H48 optimal solver.
git clone https://git.tronto.net/nissy-core
Download | Log | Files | Refs | README | LICENSE

gendata.h (8313B)


      1 STATIC size_t gendata_coord(const coord_t [static 1], unsigned char *);
      2 STATIC size_t gendata_multicoord(
      3     const multicoord_t [static 1], unsigned char *);
      4 STATIC long long gendata_coord_dispatch(const char *, unsigned long long,
      5     unsigned char *);
      6 STATIC tableinfo_t genptable_coord(
      7     const coord_t [static 1], const unsigned char *, unsigned char *);
      8 STATIC uint64_t genptable_coord_init_solved(
      9     const coord_t [static 1], const unsigned char *, unsigned char *);
     10 STATIC bool switch_to_fromnew(uint64_t, uint64_t, uint64_t);
     11 STATIC uint64_t genptable_coord_fillneighbors(const coord_t [static 1],
     12     const unsigned char *, uint64_t, uint8_t, unsigned char *);
     13 STATIC uint64_t genptable_coord_fillfromnew(const coord_t [static 1],
     14     const unsigned char *, uint64_t, uint8_t, unsigned char *);
     15 STATIC uint8_t get_coord_pval(
     16     const coord_t [static 1], const unsigned char *, uint64_t);
     17 STATIC void set_coord_pval(
     18     const coord_t [static 1], unsigned char *, uint64_t, uint8_t);
     19 
     20 STATIC long long
     21 gendata_coord_dispatch(
     22 	const char *coordstr,
     23 	unsigned long long bufsize,
     24 	unsigned char *buf
     25 )
     26 {
     27 	coord_t *coord;
     28 	multicoord_t *mcoord;
     29 
     30 	parse_coord_and_trans(coordstr, &coord, &mcoord, NULL);
     31 
     32 	if (coord != NULL)
     33 		return gendata_coord(coord, buf);
     34 
     35 	if (mcoord != NULL)
     36 		return gendata_multicoord(mcoord, buf);
     37 
     38 	LOG("Error: could not parse coordinate '%s'\n", coordstr);
     39 	return NISSY_ERROR_INVALID_SOLVER;
     40 }
     41 
     42 STATIC size_t
     43 gendata_coord(const coord_t coord[static 1], unsigned char *buf)
     44 {
     45 	uint64_t coord_dsize, tablesize, ninfo;
     46 	unsigned char *pruningbuf, *coord_data;
     47 	unsigned char *table;
     48 	tableinfo_t coord_data_info, pruning_info;
     49 
     50 	coord_data = buf == NULL ? NULL : buf + INFOSIZE;
     51 	coord_dsize = coord->gendata(coord_data);
     52 	if (coord_dsize == SIZE_MAX)
     53 		goto gendata_coord_error;
     54 
     55 	ninfo = coord_dsize == 0 ? 1 : 2;
     56 	tablesize = DIV_ROUND_UP(coord->max, 2);
     57 
     58 	if (buf == NULL)
     59 		goto gendata_coord_return_size;
     60 
     61 	if (ninfo == 2) {
     62 		coord_data_info = (tableinfo_t) {
     63 			.solver = "coord helper table for ",
     64 			.type = TABLETYPE_SPECIAL,
     65 			.infosize = INFOSIZE,
     66 			.fullsize = INFOSIZE + coord_dsize,
     67 			.hash = 0,
     68 			.next = INFOSIZE + coord_dsize,
     69 
     70 			/* Unknown / non-applicable values */
     71 			.entries = 0,
     72 			.classes = 0,
     73 			.bits = 0,
     74 			.base = 0,
     75 			.maxvalue = 0,
     76 		};
     77 
     78 		append_name(&coord_data_info, coord->name);
     79 		writetableinfo(&coord_data_info, INFOSIZE + coord_dsize, buf);
     80 
     81 		pruningbuf = buf + INFOSIZE + coord_dsize;
     82 	} else {
     83 		pruningbuf = buf;
     84 	}
     85 
     86 	table = pruningbuf + INFOSIZE;
     87 	pruning_info = genptable_coord(coord, coord_data, table);
     88 	writetableinfo(&pruning_info, INFOSIZE + tablesize, pruningbuf);
     89 
     90 gendata_coord_return_size:
     91 	return ninfo * INFOSIZE + coord_dsize + tablesize;
     92 
     93 gendata_coord_error:
     94 	LOG("Unexpected error generating coordinate data\n");
     95 	return 0;
     96 }
     97 
     98 STATIC size_t
     99 gendata_multicoord(const multicoord_t mcoord[static 1], unsigned char *buf)
    100 {
    101 	unsigned char *b;
    102 	size_t i, s, ret;
    103 	tableinfo_t info;
    104 
    105 	info = (tableinfo_t) {
    106 		.solver = "multicoordinate table for ",
    107 		.type = TABLETYPE_MULTI,
    108 		.infosize = INFOSIZE,
    109 		.fullsize = INFOSIZE,
    110 		.hash = 0,
    111 		.next = INFOSIZE,
    112 
    113 		/* Unknown / non-applicable values */
    114 		.entries = 0,
    115 		.classes = 0,
    116 		.bits = 0,
    117 		.base = 0,
    118 		.maxvalue = 0,
    119 	};
    120 
    121 	append_name(&info, mcoord->name);
    122 	if (buf != NULL)
    123 		writetableinfo(&info, INFOSIZE, buf);
    124 	ret = INFOSIZE;
    125 
    126 	for (i = 0; mcoord->coordinates[i] != NULL; i++) {
    127 		b = buf == NULL ? NULL : buf + ret;
    128 		s = gendata_coord(mcoord->coordinates[i], b);
    129 		if (s == 0)
    130 			return 0;
    131 
    132 		ret += s;
    133 
    134 		/* Pad so that each coordinate's table is 8-byte aligned */
    135 		while (ret % 8 != 0)
    136 			buf[ret++] = 0;
    137 	}
    138 
    139 	return ret;
    140 }
    141 
    142 STATIC tableinfo_t
    143 genptable_coord(
    144 	const coord_t coord[static 1],
    145 	const unsigned char *data,
    146 	unsigned char *table
    147 )
    148 {
    149 	uint64_t tablesize, i, d, tot, t, nm;
    150 	tableinfo_t info;
    151 
    152 	tablesize = DIV_ROUND_UP(coord->max, 2);
    153 	info = (tableinfo_t) {
    154 		.solver = "coordinate solver for ",
    155 		.type = TABLETYPE_PRUNING,
    156 		.infosize = INFOSIZE,
    157 		.fullsize = INFOSIZE + tablesize,
    158 		.hash = 0,
    159 		.entries = coord->max,
    160 		.classes = 0,
    161 		.bits = 4,
    162 		.base = 0,
    163 		.maxvalue = 0,
    164 		.next = 0
    165 	};
    166 
    167 	memset(table, 0xFF, tablesize);
    168 	memset(info.distribution, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
    169 	append_name(&info, coord->name);
    170 
    171 	tot = info.distribution[0] =
    172 	    genptable_coord_init_solved(coord, data, table);
    173 	nm = popcount_u32(coord->moves_mask_gendata);
    174 	for (d = 1; tot < coord->max && d < 15; d++) {
    175 		t = 0;
    176 		if (switch_to_fromnew(tot, coord->max, nm)) {
    177 			for (i = 0; i < coord->max; i++)
    178 				if (get_coord_pval(coord, table, i) > d)
    179 					t += genptable_coord_fillfromnew(
    180 					    coord, data, i, d, table);
    181 		} else {
    182 			for (i = 0; i < coord->max; i++)
    183 				if (get_coord_pval(coord, table, i) == d-1)
    184 					t += genptable_coord_fillneighbors(
    185 					    coord, data, i, d, table);
    186 		}
    187 		tot += t;
    188 		info.distribution[d] = t;
    189 		LOG("[%s gendata] Depth %" PRIu64 ": found %" PRIu64 " (%"
    190 		    PRIu64 " of %" PRIu64 ")\n",
    191 		    coord->name, d, t, tot, coord->max);
    192 	}
    193 	if (tot == coord->max) {
    194 		info.maxvalue = d-1;
    195 	} else {
    196 		LOG("[%s gendata] Depth >= 15: %" PRIu64 " remaining\n",
    197 		    coord->name, coord->max - tot);
    198 		info.distribution[d] = coord->max - tot;
    199 		info.maxvalue = 15;
    200 	}
    201 
    202 	return info;
    203 }
    204 
    205 STATIC uint64_t
    206 genptable_coord_init_solved(
    207 	const coord_t coord[static 1],
    208 	const unsigned char *coord_data,
    209 	unsigned char *table
    210 )
    211 {
    212 	uint64_t i, max_solved, ret;
    213 
    214 	max_solved = coord->is_solved == NULL ? 1 : coord->max;
    215 
    216 	for (i = 0, ret = 0; i < max_solved; i++) {
    217 		if (coord_is_solved(coord, i, coord_data)) {
    218 			set_coord_pval(coord, table, i, 0);
    219 			ret++;
    220 		}
    221 	}
    222 
    223 	return ret;
    224 }
    225 
    226 STATIC bool
    227 switch_to_fromnew(uint64_t done, uint64_t max, uint64_t nm)
    228 {
    229 	/*
    230 	Heuristic to determine if it is more conveniente to loop over
    231       	done coordinates and fill the new discovered, or to loop from new
    232 	coordinates and fill them if they have a done neighbor.
    233 	*/
    234 
    235 	double r = (double)done / (double)max;
    236 	return 1.0 - intpow(1.0-r, nm) > nm * (1.0-r);
    237 }
    238 
    239 STATIC uint64_t
    240 genptable_coord_fillneighbors(
    241 	const coord_t coord[static 1],
    242 	const unsigned char *data,
    243 	uint64_t i, 
    244 	uint8_t d,
    245 	unsigned char *table
    246 )
    247 {
    248 	bool isnasty;
    249 	uint8_t m;
    250 	uint64_t ii, j, t, tot;
    251 	cube_t c, moved;
    252 
    253 	c = coord->cube(i, data);
    254 	tot = 0;
    255 	for (m = 0; m < NMOVES; m++) {
    256 		if (!((UINT32_C(1) << (uint32_t)m) &
    257 		    coord->moves_mask_gendata))
    258 			continue;
    259 		moved = move(c, m);
    260 		ii = coord->coord(moved, data);
    261 		isnasty = coord->isnasty(ii, data);
    262 		for (t = 0; t < NTRANS && (t == 0 || isnasty); t++) {
    263 			if (!((UINT64_C(1) << t) & coord->trans_mask))
    264 				continue;
    265 
    266 			j = coord->coord(transform(moved, t), data);
    267 			if (get_coord_pval(coord, table, j) > d) {
    268 				set_coord_pval(coord, table, j, d);
    269 				tot++;
    270 			}
    271 		}
    272 	}
    273 
    274 	return tot;
    275 }
    276 
    277 STATIC uint64_t
    278 genptable_coord_fillfromnew(
    279 	const coord_t coord[static 1],
    280 	const unsigned char *data,
    281 	uint64_t i,
    282 	uint8_t d,
    283 	unsigned char *table
    284 )
    285 {
    286 	bool found;
    287 	uint8_t m;
    288 	uint64_t tot, t, ii, j, nsim, sim[NTRANS];
    289 	cube_t c;
    290 
    291 	tot = 0;
    292 	c = coord->cube(i, data);
    293 
    294 	for (t = 0, nsim = 0; t < NTRANS; t++) {
    295 		if (!((UINT64_C(1) << t) & coord->trans_mask))
    296 			continue;
    297 
    298 		ii = coord->coord(transform(c, t), data);
    299 		for (j = 0, found = false; j < nsim && !found; j++)
    300 			found = sim[j] == ii;
    301 		if (!found)
    302 			sim[nsim++] = ii;
    303 	}
    304 
    305 	for (j = 0, found = false; j < nsim && !found; j++) {
    306 		c = coord->cube(sim[j], data);
    307 		for (m = 0; m < NMOVES; m++) {
    308 			if (!((UINT32_C(1) << (uint32_t)m) &
    309 			    coord->moves_mask_gendata))
    310 				continue;
    311 			ii = coord->coord(move(c, m), data);
    312 			if (get_coord_pval(coord, table, ii) < d) {
    313 				found = true;
    314 				break;
    315 			}
    316 		}
    317 	}
    318 
    319 	tot = 0;
    320 	if (found) {
    321 		for (j = 0; j < nsim; j++) {
    322 			if (get_coord_pval(coord, table, sim[j]) > d) {
    323 				set_coord_pval(coord, table, sim[j], d);
    324 				tot++;
    325 			}
    326 		}
    327 	}
    328 
    329 	return tot;
    330 }
    331 
    332 STATIC uint8_t
    333 get_coord_pval(
    334 	const coord_t coord[static 1],
    335 	const unsigned char *table,
    336 	uint64_t i
    337 )
    338 {
    339 	return (table[COORD_INDEX(i)] & COORD_MASK(i)) >> COORD_SHIFT(i);
    340 }
    341 
    342 STATIC void
    343 set_coord_pval(
    344 	const coord_t coord[static 1],
    345 	unsigned char *table,
    346 	uint64_t i,
    347 	uint8_t val
    348 )
    349 {
    350 	table[COORD_INDEX(i)] = (table[COORD_INDEX(i)] & (~COORD_MASK(i)))
    351 	    | (val << COORD_SHIFT(i));
    352 }