From ce3f1cc0ef9f46d70ab5387b1458e9098b40711d Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sat, 22 Mar 2025 06:43:11 +0100 Subject: Some safety with move arrays, small refactor appendchar --- src/solvers/coord/common.h | 25 ++++++++------ src/solvers/coord/gendata.h | 4 +-- src/solvers/coord/solve.h | 61 +++++++++++++--------------------- src/solvers/coord/types_macros.h | 2 +- src/solvers/h48/gendata_h48.h | 4 +-- src/solvers/h48/gendata_types_macros.h | 1 - src/solvers/h48/solve.h | 48 +++++++++++--------------- src/solvers/solutions.h | 14 ++++++++ src/solvers/solvers.h | 1 + 9 files changed, 77 insertions(+), 83 deletions(-) create mode 100644 src/solvers/solutions.h (limited to 'src/solvers') diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h index d570b6d..8553658 100644 --- a/src/solvers/coord/common.h +++ b/src/solvers/coord/common.h @@ -4,9 +4,9 @@ coord_t *all_coordinates[] = { }; STATIC void append_coord_name(const coord_t *, char *); -STATIC coord_t *parse_coord(const char *, int); -STATIC uint8_t parse_axis(const char *, int); -STATIC void parse_coord_and_axis(const char *, int, coord_t **, uint8_t *); +STATIC coord_t *parse_coord(size_t n, const char [n]); +STATIC uint8_t parse_axis(size_t n, const char [n]); +STATIC void parse_coord_and_axis(size_t n, const char [n], coord_t **, uint8_t *); STATIC int64_t dataid_coord(const char *, char [static NISSY_DATAID_SIZE]); STATIC void @@ -22,7 +22,7 @@ append_coord_name(const coord_t *coord, char *str) } STATIC coord_t * -parse_coord(const char *coord, int n) +parse_coord(size_t n, const char coord[n]) { int i; @@ -34,7 +34,7 @@ parse_coord(const char *coord, int n) } STATIC uint8_t -parse_axis(const char *axis, int n) +parse_axis(size_t n, const char axis[n]) { if (!strncmp(axis, "UD", n) || !strncmp(axis, "DU", n)) { return AXIS_UD; @@ -48,19 +48,24 @@ parse_axis(const char *axis, int n) } STATIC void -parse_coord_and_axis(const char *str, int n, coord_t **coord, uint8_t *axis) +parse_coord_and_axis( + size_t n, + const char str[n], + coord_t **coord, + uint8_t *axis +) { - int i; + size_t i; for (i = 0; i < n; i++) if (str[i] == '_') break; if (coord != NULL) - *coord = parse_coord(str, i); + *coord = parse_coord(i, str); if (axis != NULL) - *axis = i == n ? UINT8_ERROR : parse_axis(str+i+1, n-i-1); + *axis = i == n ? UINT8_ERROR : parse_axis(n-i-1, str+i+1); } STATIC int64_t @@ -68,7 +73,7 @@ dataid_coord(const char *ca, char dataid[static NISSY_DATAID_SIZE]) { coord_t *c; - parse_coord_and_axis(ca, strlen(ca), &c, NULL); + parse_coord_and_axis(strlen(ca), ca, &c, NULL); if (c == NULL) { LOG("dataid_coord: cannot parse coordinate from '%s'\n", ca); diff --git a/src/solvers/coord/gendata.h b/src/solvers/coord/gendata.h index 93ffc65..5819608 100644 --- a/src/solvers/coord/gendata.h +++ b/src/solvers/coord/gendata.h @@ -11,7 +11,7 @@ gendata_coord_dispatch(const char *coordstr, void *buf) { coord_t *coord; - parse_coord_and_axis(coordstr, strlen(coordstr), &coord, NULL); + parse_coord_and_axis(strlen(coordstr), coordstr, &coord, NULL); if (coord == NULL) { LOG("Could not parse coordinate '%s'\n", coord); @@ -137,7 +137,7 @@ getdistribution_coord( memset(distr, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t)); - if((c = parse_coord(coord, strlen(coord))) == NULL) + if((c = parse_coord(strlen(coord), coord)) == NULL) return; for (i = 0; i < c->max; i++) { diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h index 6903d1e..fa160f8 100644 --- a/src/solvers/coord/solve.h +++ b/src/solvers/coord/solve.h @@ -1,10 +1,8 @@ -#define MAXLEN_COORDSOL 20 - typedef struct { cube_t cube; uint8_t depth; uint8_t nmoves; - uint8_t moves[MAXLEN_COORDSOL]; + uint8_t moves[MAXLEN]; coord_t *coord; const void *coord_data; const uint8_t *ptable; @@ -13,23 +11,22 @@ typedef struct { int64_t maxsolutions; int optimal; uint8_t *shortest_sol; - uint64_t solutions_size; - uint64_t *solutions_used; + size_t solutions_size; + size_t *solutions_used; char **solutions; } dfsarg_solve_coord_t; STATIC int64_t solve_coord(cube_t, coord_t *, uint8_t, uint8_t, uint8_t, - uint8_t, uint64_t, int, int, uint64_t, const void *, uint64_t, char *); + uint8_t, uint64_t, int, int, uint64_t, const void *, size_t, char *); STATIC int64_t solve_coord_dispatch(cube_t, const char *, uint8_t, uint8_t, - uint8_t, uint64_t, int, int, uint64_t, const void *, uint64_t, char *); -STATIC bool solve_coord_appendchar(char *, uint64_t, uint64_t *, char); + uint8_t, uint64_t, int, int, uint64_t, const void *, size_t, char *); STATIC int64_t solve_coord_appendsolution(dfsarg_solve_coord_t *); STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t *); STATIC int64_t solve_coord_appendsolution(dfsarg_solve_coord_t *arg) { - uint8_t i, t, tmoves[MAXLEN_COORDSOL]; + uint8_t i, t, tmoves[MAXLEN]; int64_t strl; uint64_t l; char *m; @@ -44,18 +41,18 @@ solve_coord_appendsolution(dfsarg_solve_coord_t *arg) for (i = 0; i < arg->nmoves; i++) tmoves[i] = transform_move(arg->moves[i], t); - sortparallel(tmoves, arg->nmoves); + sortparallel(arg->nmoves, tmoves); l = arg->solutions_size - *arg->solutions_used; m = *arg->solutions + *arg->solutions_used; - strl = writemoves(tmoves, arg->nmoves, l, m); + strl = writemoves(arg->nmoves, tmoves, l, m); if (strl < 0) goto solve_coord_appendsolution_error; *arg->solutions_used += MAX(0, strl-1); - if (!solve_coord_appendchar( - *arg->solutions, arg->solutions_size, arg->solutions_used, '\n')) + if (!appendchar( + arg->solutions_size, *arg->solutions, arg->solutions_used, '\n')) goto solve_coord_appendsolution_error; (*arg->nsols)++; @@ -68,18 +65,6 @@ solve_coord_appendsolution_error: return NISSY_ERROR_BUFFER_SIZE; } -STATIC bool -solve_coord_appendchar(char *s, uint64_t s_size, uint64_t *s_used, char c) -{ - if (s_size == *s_used) - return false; - - s[*s_used] = c; - (*s_used)++; - - return true; -} - STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t *arg) { @@ -104,7 +89,7 @@ solve_coord_dfs(dfsarg_solve_coord_t *arg) backup_cube = arg->cube; ret = 0; - mm = allowednextmove_mask(arg->moves, arg->nmoves); + mm = allowednextmove_mask(arg->nmoves, arg->moves); arg->nmoves++; for (m = 0; m < 18; m++) { if (!(mm & (1 << m))) @@ -135,7 +120,7 @@ solve_coord_dispatch( int threads, uint64_t data_size, const void *data, - uint64_t sols_size, + size_t solutions_size, char *sols ) { @@ -143,7 +128,7 @@ solve_coord_dispatch( uint8_t axis; parse_coord_and_axis( - coord_and_axis, strlen(coord_and_axis), &coord, &axis); + strlen(coord_and_axis), coord_and_axis, &coord, &axis); if (coord == NULL) { LOG("Could not parse coordinate from '%s'\n", coord_and_axis); @@ -156,7 +141,8 @@ solve_coord_dispatch( } return solve_coord(cube, coord, axis, nissflag, minmoves, maxmoves, - maxsolutions, optimal, threads, data_size, data, sols_size, sols); + maxsolutions, optimal, threads, data_size, data, + solutions_size, sols); } STATIC int64_t @@ -172,14 +158,14 @@ solve_coord( int threads, uint64_t data_size, const void *data, - uint64_t sols_size, + size_t solutions_size, char *sols ) { int8_t d; uint8_t t, shortest_sol; int64_t nsols, ndepth; - uint64_t sols_used; + size_t solutions_used; cube_t c; const void *coord_data; const uint8_t *ptable; @@ -200,8 +186,8 @@ solve_coord( } nsols = 0; - sols_used = 0; - shortest_sol = MAXLEN_COORDSOL + 1; + solutions_used = 0; + shortest_sol = MAXLEN + 1; t = coord->axistrans[axis]; c = transform(cube, t); @@ -215,16 +201,15 @@ solve_coord( .maxsolutions = (int64_t)maxsolutions, .optimal = optimal, .shortest_sol = &shortest_sol, - .solutions_size = sols_size, - .solutions_used = &sols_used, + .solutions_size = solutions_size, + .solutions_used = &solutions_used, .solutions = &sols, }; if (coord->coord(c, coord_data) == 0) { if (minmoves == 0) { nsols = 1; - if (!solve_coord_appendchar( - sols, sols_size, &sols_used, '\n')) + if (!appendchar(solutions_size, sols, &solutions_used, '\n')) goto solve_coord_error_buffer; } goto solve_coord_done; @@ -254,7 +239,7 @@ solve_coord( } solve_coord_done: - if (!solve_coord_appendchar(sols, sols_size, &sols_used, '\0')) + if (!appendchar(solutions_size, sols, &solutions_used, '\0')) goto solve_coord_error_buffer; return nsols; diff --git a/src/solvers/coord/types_macros.h b/src/solvers/coord/types_macros.h index 2309efc..f2d436c 100644 --- a/src/solvers/coord/types_macros.h +++ b/src/solvers/coord/types_macros.h @@ -11,5 +11,5 @@ typedef struct { uint32_t moves_mask; uint64_t trans_mask; uint8_t axistrans[3]; - bool (*is_admissible)(int n, uint8_t [n]); + bool (*is_admissible)(size_t n, uint8_t [n]); } coord_t; diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h index 55db1be..2d9a9f7 100644 --- a/src/solvers/h48/gendata_h48.h +++ b/src/solvers/h48/gendata_h48.h @@ -533,7 +533,7 @@ gendata_h48k2_dfs(h48k2_dfs_arg_t *arg) /* Depth d+3 */ for (m[2] = 0; m[2] < 18; m[2]++) { markarg.depth = d+3; - if (!allowednextmove(m, 3)) { + if (!allowednextmove(3, m)) { m[2] += 2; continue; } @@ -548,7 +548,7 @@ gendata_h48k2_dfs(h48k2_dfs_arg_t *arg) /* Depth d+4 */ for (m[3] = 0; m[3] < 18; m[3]++) { markarg.depth = d+4; - if (!allowednextmove(m, 4)) { + if (!allowednextmove(4, m)) { m[3] += 2; continue; } diff --git a/src/solvers/h48/gendata_types_macros.h b/src/solvers/h48/gendata_types_macros.h index a2026b2..ec6576a 100644 --- a/src/solvers/h48/gendata_types_macros.h +++ b/src/solvers/h48/gendata_types_macros.h @@ -28,7 +28,6 @@ #define H48_SHIFT(i, k) ((uint8_t)(k) * (uint8_t)((i) % H48_COEFF(k))) #define H48_MASK(i, k) ((UINT8_BIT(k) - UINT8_C(1)) << H48_SHIFT(i, k)) -#define MAXLEN 20 #define CHUNKS COCSEP_CLASSES /* diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index 182beee..f7565d5 100644 --- a/src/solvers/h48/solve.h +++ b/src/solvers/h48/solve.h @@ -32,8 +32,8 @@ typedef struct { const uint8_t *h48data; const uint8_t *h48data_fallback_h0k4; const void *h48data_fallback_eoesep; - uint64_t solutions_size; - uint64_t *solutions_used; + size_t solutions_size; + size_t *solutions_used; char **solutions; uint32_t movemask_normal; uint32_t movemask_inverse; @@ -58,7 +58,6 @@ typedef struct { STATIC int64_t solve_h48_appendsolution(dfsarg_solve_h48_t *); STATIC int64_t solve_h48_appendallsym(dfsarg_solve_h48_t *); -STATIC bool solve_h48_appendchar(dfsarg_solve_h48_t *, char); STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t *); STATIC int64_t solve_h48_maketasks( dfsarg_solve_h48_t *, dfsarg_solve_h48_maketasks_t *, @@ -66,7 +65,7 @@ STATIC int64_t solve_h48_maketasks( STATIC void *solve_h48_runthread(void *); STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t *); STATIC int64_t solve_h48(cube_t, int8_t, int8_t, uint64_t, int8_t, int8_t, - uint64_t, const void *, uint64_t, char *, + uint64_t, const void *, size_t, char *, long long [static NISSY_SIZE_SOLVE_STATS]); STATIC int64_t @@ -76,15 +75,15 @@ solve_h48_appendsolution(dfsarg_solve_h48_t *arg) arg->nmoves + arg->npremoves > *arg->shortest_sol + arg->optimal) return 0; - invertmoves(arg->premoves, arg->npremoves, arg->moves + arg->nmoves); + invertmoves(arg->npremoves, arg->premoves, arg->moves + arg->nmoves); /* Sort parallel moves for consistency */ - sortparallel(arg->moves, arg->nmoves + arg->npremoves); + sortparallel(arg->nmoves + arg->npremoves, arg->moves); /* Do not append the solution in case premoves cancel with normal */ - if (arg->npremoves > 0 && !allowednextmove(arg->moves, arg->nmoves+1)) + if (arg->npremoves > 0 && !allowednextmove(arg->nmoves+1, arg->moves)) return 0; - if (arg->npremoves > 1 && !allowednextmove(arg->moves, arg->nmoves+2)) + if (arg->npremoves > 1 && !allowednextmove(arg->nmoves+2, arg->moves)) return 0; return solve_h48_appendallsym(arg); @@ -109,7 +108,7 @@ solve_h48_appendallsym(dfsarg_solve_h48_t *arg) all[j][i] = transform_move(arg->moves[i], t); /* Sort parallel moves for consistency */ - sortparallel(all[j], n); + sortparallel(n, all[j]); /* Check for duplicate solutions */ for (k = 0; k < j; k++) { @@ -133,7 +132,7 @@ solve_h48_appendallsym(dfsarg_solve_h48_t *arg) for (k = 0; k < j && *arg->nsols < arg->maxsolutions; k++) { l = arg->solutions_size - *arg->solutions_used; m = *arg->solutions + *arg->solutions_used; - strl = writemoves(all[k], n, l, m); + strl = writemoves(n, all[k], l, m); if (strl < 0) goto solve_h48_appendallsym_error; @@ -141,7 +140,8 @@ solve_h48_appendallsym(dfsarg_solve_h48_t *arg) *arg->solutions_used += MAX(0, strl-1); - if (!solve_h48_appendchar(arg, '\n')) + if (!appendchar(arg->solutions_size, + *arg->solutions, arg->solutions_used, '\n')) goto solve_h48_appendallsym_error; (*arg->nsols)++; @@ -156,18 +156,6 @@ solve_h48_appendallsym_error: return NISSY_ERROR_BUFFER_SIZE; } -STATIC bool -solve_h48_appendchar(dfsarg_solve_h48_t *arg, char c) -{ - if (arg->solutions_size <= *arg->solutions_used) - return false; - - *(*arg->solutions + *arg->solutions_used) = c; - (*arg->solutions_used)++; - - return true; -} - STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t *arg) { @@ -283,9 +271,9 @@ solve_h48_dfs(dfsarg_solve_h48_t *arg) ulbi = arg->use_lb_inverse; ret = 0; - mm_normal = allowednextmove_mask(arg->moves, arg->nmoves) & + mm_normal = allowednextmove_mask(arg->nmoves, arg->moves) & arg->movemask_normal; - mm_inverse = allowednextmove_mask(arg->premoves, arg->npremoves) & + mm_inverse = allowednextmove_mask(arg->npremoves, arg->premoves) & arg->movemask_inverse; if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) { arg->nmoves++; @@ -397,7 +385,7 @@ solve_h48_maketasks( return NISSY_OK; } - mm = allowednextmove_mask(maketasks_arg->moves, maketasks_arg->nmoves); + mm = allowednextmove_mask(maketasks_arg->nmoves, maketasks_arg->moves); maketasks_arg->nmoves++; backup_cube = maketasks_arg->cube; @@ -435,7 +423,7 @@ solve_h48( int8_t threads, uint64_t data_size, const void *data, - uint64_t solutions_size, + size_t solutions_size, char *solutions, long long stats[static NISSY_SIZE_SOLVE_STATS] ) @@ -447,7 +435,8 @@ solve_h48( solve_h48_task_t tasks[STARTING_CUBES]; dfsarg_solve_h48_maketasks_t maketasks_arg; long double fallback_rate, lookups_per_node; - uint64_t solutions_used, symmask, offset; + uint64_t symmask, offset; + size_t solutions_used; int64_t nodes_visited, table_lookups, table_fallbacks; tableinfo_t info, fbinfo, fbinfo2; const uint32_t *cocsepdata; @@ -561,7 +550,8 @@ solve_h48( } solve_h48_done: - if (!solve_h48_appendchar(&arg[0], '\0')) + if (!appendchar(arg[0].solutions_size, *arg[0].solutions, + arg[0].solutions_used, '\0')) goto solve_h48_error_solutions_buffer; nodes_visited = table_lookups = table_fallbacks = 0; diff --git a/src/solvers/solutions.h b/src/solvers/solutions.h new file mode 100644 index 0000000..1396210 --- /dev/null +++ b/src/solvers/solutions.h @@ -0,0 +1,14 @@ +#define MAXLEN 20 + +STATIC bool appendchar(size_t n, char [n], size_t *, char); + +STATIC bool +appendchar(size_t n, char s[n], size_t *used, char c) +{ + if (n <= *used) + return false; + + s[(*used)++] = c; + + return true; +} diff --git a/src/solvers/solvers.h b/src/solvers/solvers.h index 7ef1746..42184b9 100644 --- a/src/solvers/solvers.h +++ b/src/solvers/solvers.h @@ -1,3 +1,4 @@ +#include "solutions.h" #include "tables.h" #include "h48/h48.h" #include "coord/coord.h" -- cgit v1.3