commit 849edbb69700a9f7520e159d94333ef5b798685b
parent 1573b0d3077aade290f03482b1620b2295d2c58c
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Wed, 8 Dec 2021 21:50:35 +0100
Just refortmatting and added one type
Diffstat:
4 files changed, 191 insertions(+), 170 deletions(-)
diff --git a/nissy b/nissy
Binary files differ.
diff --git a/src/cubetypes.h b/src/cubetypes.h
@@ -72,24 +72,25 @@ trans
/* Typedefs ******************************************************************/
-typedef struct alg Alg;
-typedef struct alglist AlgList;
-typedef struct alglistnode AlgListNode;
-typedef struct block Block;
-typedef struct command Command;
-typedef struct commandargs CommandArgs;
-typedef struct coordinate Coordinate;
-typedef struct cube Cube;
-typedef struct cubearray CubeArray;
-typedef struct dfsdata DfsData;
-typedef struct estimatedata EstimateData;
-typedef struct localinfo LocalInfo;
-typedef struct piecefilter PieceFilter;
-typedef struct prunedata PruneData;
-typedef struct solveoptions SolveOptions;
-typedef struct step Step;
-typedef struct symdata SymData;
-typedef struct threaddata ThreadData;
+typedef struct alg Alg;
+typedef struct alglist AlgList;
+typedef struct alglistnode AlgListNode;
+typedef struct block Block;
+typedef struct command Command;
+typedef struct commandargs CommandArgs;
+typedef struct coordinate Coordinate;
+typedef struct cube Cube;
+typedef struct cubearray CubeArray;
+typedef struct dfsdata DfsData;
+typedef struct estimatedata EstimateData;
+typedef struct localinfo LocalInfo;
+typedef struct piecefilter PieceFilter;
+typedef struct prunedata PruneData;
+typedef struct solveoptions SolveOptions;
+typedef struct step Step;
+typedef struct symdata SymData;
+typedef struct threaddatasolve ThreadDataSolve;
+typedef struct threaddatagenpt ThreadDataGenpt;
typedef Cube (*AntiIndexer) (uint64_t);
typedef bool (*Checker) (Cube);
@@ -108,221 +109,233 @@ typedef int (*TransFinder) (uint64_t, Trans *);
struct
alg
{
- Move * move;
- bool * inv;
- int len;
- int allocated;
+ Move * move;
+ bool * inv;
+ int len;
+ int allocated;
};
struct
alglist
{
- AlgListNode * first;
- AlgListNode * last;
- int len;
+ AlgListNode * first;
+ AlgListNode * last;
+ int len;
};
struct
alglistnode
{
- Alg * alg;
- AlgListNode * next;
+ Alg * alg;
+ AlgListNode * next;
};
struct
block
{
- bool edge[12];
- bool corner[8];
- bool center[6];
+ bool edge[12];
+ bool corner[8];
+ bool center[6];
};
struct
command
{
- char * name;
- char * usage;
- char * description;
- ArgParser parse_args;
- Exec exec;
+ char * name;
+ char * usage;
+ char * description;
+ ArgParser parse_args;
+ Exec exec;
};
struct
commandargs
{
- bool success;
- Alg * scramble;
- SolveOptions * opts;
- Step * step;
- Command * command; /* For help */
+ bool success;
+ Alg * scramble;
+ SolveOptions * opts;
+ Step * step;
+ Command * command; /* For help */
};
struct
coordinate
{
- Indexer index;
- AntiIndexer cube;
- uint64_t max;
- TransFinder trans;
+ Indexer index;
+ AntiIndexer cube;
+ uint64_t max;
+ TransFinder trans;
};
struct
cube
{
- int epose;
- int eposs;
- int eposm;
- int eofb;
- int eorl;
- int eoud;
- int cp;
- int coud;
- int cofb;
- int corl;
- int cpos;
+ int epose;
+ int eposs;
+ int eposm;
+ int eofb;
+ int eorl;
+ int eoud;
+ int cp;
+ int coud;
+ int cofb;
+ int corl;
+ int cpos;
};
struct
cubearray
{
- int * ep;
- int * eofb;
- int * eorl;
- int * eoud;
- int * cp;
- int * coud;
- int * corl;
- int * cofb;
- int * cpos;
+ int * ep;
+ int * eofb;
+ int * eorl;
+ int * eoud;
+ int * cp;
+ int * coud;
+ int * corl;
+ int * cofb;
+ int * cpos;
};
struct
dfsdata
{
- int d;
- int m;
- int lb;
- bool niss;
- Move last1;
- Move last2;
- EstimateData * ed;
- AlgList * sols;
- pthread_mutex_t * sols_mutex;
- Alg * current_alg;
- Move * sorted_moves;
- int * move_position;
- uint8_t * visited;
+ int d;
+ int m;
+ int lb;
+ bool niss;
+ Move last1;
+ Move last2;
+ EstimateData * ed;
+ AlgList * sols;
+ pthread_mutex_t * sols_mutex;
+ Alg * current_alg;
+ Move * sorted_moves;
+ int * move_position;
+ uint8_t * visited;
};
struct
estimatedata
{
- Cube cube;
- int target;
- Move lastmove;
- uint64_t movebitmask;
- LocalInfo * li;
+ Cube cube;
+ int target;
+ Move lastmove;
+ uint64_t movebitmask;
+ LocalInfo * li;
};
struct
localinfo
{
- int corners;
- int normal_ud;
- int normal_fb;
- int normal_rl;
- int inverse_ud;
- int inverse_fb;
- int inverse_rl;
- int prev_ret;
+ int corners;
+ int normal_ud;
+ int normal_fb;
+ int normal_rl;
+ int inverse_ud;
+ int inverse_fb;
+ int inverse_rl;
+ int prev_ret;
};
struct
piecefilter
{
- bool epose;
- bool eposs;
- bool eposm;
- bool eofb;
- bool eorl;
- bool eoud;
- bool cp;
- bool coud;
- bool cofb;
- bool corl;
- bool cpos;
+ bool epose;
+ bool eposs;
+ bool eposm;
+ bool eofb;
+ bool eorl;
+ bool eoud;
+ bool cp;
+ bool coud;
+ bool cofb;
+ bool corl;
+ bool cpos;
};
struct
prunedata
{
- char * filename;
- uint8_t * ptable;
- bool generated;
- uint64_t n;
- Coordinate * coord;
- Moveset moveset;
+ char * filename;
+ uint8_t * ptable;
+ bool generated;
+ uint64_t n;
+ Coordinate * coord;
+ Moveset moveset;
};
struct
solveoptions
{
- int min_moves;
- int max_moves;
- int max_solutions;
- int nthreads;
- bool optimal_only;
- bool can_niss;
- bool verbose;
- bool all;
- bool print_number;
+ int min_moves;
+ int max_moves;
+ int max_solutions;
+ int nthreads;
+ bool optimal_only;
+ bool can_niss;
+ bool verbose;
+ bool all;
+ bool print_number;
};
struct
step
{
- char * shortname;
- char * name;
- Estimator estimate;
- Checker ready;
- char * ready_msg;
- Validator is_valid;
- Moveset moveset;
- Trans pre_trans;
- TransDetector detect;
- int ntables;
- PruneData * tables[10];
+ char * shortname;
+ char * name;
+ Estimator estimate;
+ Checker ready;
+ char * ready_msg;
+ Validator is_valid;
+ Moveset moveset;
+ Trans pre_trans;
+ TransDetector detect;
+ int ntables;
+ PruneData * tables[10];
};
struct
symdata
{
- char * filename;
- bool generated;
- Coordinate * coord;
- Coordinate * sym_coord;
- int ntrans;
- Trans * trans;
- uint64_t * class;
- Cube * rep;
- Trans * transtorep;
+ char * filename;
+ bool generated;
+ Coordinate * coord;
+ Coordinate * sym_coord;
+ int ntrans;
+ Trans * trans;
+ uint64_t * class;
+ Cube * rep;
+ Trans * transtorep;
};
struct
-threaddata
+threaddatasolve
{
- int thid;
- Cube cube;
- Step * step;
- int depth;
- Move * sorted_moves;
- int * move_position;
- SolveOptions * opts;
- AlgList * start;
- AlgListNode ** node;
- AlgList * sols;
- pthread_mutex_t * start_mutex;
- pthread_mutex_t * sols_mutex;
+ int thid;
+ Cube cube;
+ Step * step;
+ int depth;
+ Move * sorted_moves;
+ int * move_position;
+ SolveOptions * opts;
+ AlgList * start;
+ AlgListNode ** node;
+ AlgList * sols;
+ pthread_mutex_t * start_mutex;
+ pthread_mutex_t * sols_mutex;
+};
+
+struct
+threaddatagenpt
+{
+ int thid;
+ PruneData * pd;
+ int d;
+ uint64_t rangemin;
+ uint64_t rangemax;
+ int nchunks;
+ pthread_mutex_t ** mutex;
};
#endif
diff --git a/src/pruning.c b/src/pruning.c
@@ -2,6 +2,7 @@
static void genptable_bfs(PruneData *pd, int d, Move *ms);
static void genptable_branch(PruneData *pd,uint64_t ind,int d,Move *ms);
+static void genptable_fixnasty(PruneData *pd, int d);
static void ptable_update(PruneData *pd, Cube cube, int m);
static void ptable_update_index(PruneData *pd, uint64_t ind, int m);
static int ptableval_index(PruneData *pd, uint64_t ind);
@@ -114,6 +115,7 @@ genptable(PruneData *pd)
0, pd->n - oldn, pd->n, pd->coord->max);
oldn = 1;
for (d = 0; d < 15 && pd->n < pd->coord->max; d++) {
+ genptable_fixnasty(pd, d);
genptable_bfs(pd, d, ms);
fprintf(stderr, "Depth %d done, generated %"
PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n",
@@ -131,25 +133,7 @@ genptable(PruneData *pd)
static void
genptable_bfs(PruneData *pd, int d, Move *ms)
{
- int j, n;
uint64_t i;
- Cube c, cc;
- Trans t[NTRANS];
-
- for (i = 0; i < pd->coord->max; i++) {
- if (ptableval_index(pd, i) == d) {
- n = pd->coord->trans(i, t);
- if (n == 1)
- continue;
-
- c = pd->coord->cube(i);
- for (j = 0; j < n; j++) {
- cc = apply_trans(t[j], c);
- if (ptableval(pd, cc) > d)
- ptable_update(pd, cc, d);
- }
- }
- }
for (i = 0; i < pd->coord->max; i++)
if (ptableval_index(pd, i) == d)
@@ -171,6 +155,30 @@ genptable_branch(PruneData *pd, uint64_t ind, int d, Move *ms)
}
}
+static void
+genptable_fixnasty(PruneData *pd, int d)
+{
+ uint64_t i;
+ int j, n;
+ Cube c, cc;
+ Trans t[NTRANS];
+
+ for (i = 0; i < pd->coord->max; i++) {
+ if (ptableval_index(pd, i) == d) {
+ n = pd->coord->trans(i, t);
+ if (n == 1)
+ continue;
+
+ c = pd->coord->cube(i);
+ for (j = 0; j < n; j++) {
+ cc = apply_trans(t[j], c);
+ if (ptableval(pd, cc) > d)
+ ptable_update(pd, cc, d);
+ }
+ }
+ }
+}
+
void
print_ptable(PruneData *pd)
{
diff --git a/src/solve.c b/src/solve.c
@@ -156,11 +156,11 @@ instance_thread(void *arg)
{
bool b;
Cube c;
- ThreadData *td;
+ ThreadDataSolve *td;
AlgListNode *node;
DfsData dd;
- td = (ThreadData *)arg;
+ td = (ThreadDataSolve *)arg;
while (1) {
b = false;
@@ -215,7 +215,7 @@ multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
AlgList *start;
AlgListNode **node;
pthread_t t[opts->nthreads];
- ThreadData td[opts->nthreads];
+ ThreadDataSolve td[opts->nthreads];
pthread_mutex_t *start_mutex, *sols_mutex;
move_position = malloc(NMOVES * sizeof(int));
