diff options
Diffstat (limited to 'src/solvers/h48')
| -rw-r--r-- | src/solvers/h48/gendata_cocsep.h | 16 | ||||
| -rw-r--r-- | src/solvers/h48/gendata_h48.h | 86 | ||||
| -rw-r--r-- | src/solvers/h48/gendata_types_macros.h | 8 | ||||
| -rw-r--r-- | src/solvers/h48/h48.h | 1 | ||||
| -rw-r--r-- | src/solvers/h48/solve.h | 34 | ||||
| -rw-r--r-- | src/solvers/h48/utils.h | 66 |
6 files changed, 125 insertions, 86 deletions
diff --git a/src/solvers/h48/gendata_cocsep.h b/src/solvers/h48/gendata_cocsep.h index 2eac383..3117a8e 100644 --- a/src/solvers/h48/gendata_cocsep.h +++ b/src/solvers/h48/gendata_cocsep.h | |||
| @@ -1,7 +1,5 @@ | |||
| 1 | STATIC size_t gendata_cocsep(unsigned char *, uint64_t *, cube_t *); | 1 | STATIC size_t gendata_cocsep(unsigned char *, uint64_t *, cube_t *); |
| 2 | STATIC uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t [static 1]); | 2 | STATIC uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t [static 1]); |
| 3 | STATIC void getdistribution_cocsep( | ||
| 4 | const uint32_t [static COCSEP_TABLESIZE], uint64_t [static 21]); | ||
| 5 | 3 | ||
| 6 | STATIC_INLINE bool gendata_cocsep_get_visited( | 4 | STATIC_INLINE bool gendata_cocsep_get_visited( |
| 7 | const uint8_t [static COCSEP_VISITEDSIZE], int64_t); | 5 | const uint8_t [static COCSEP_VISITEDSIZE], int64_t); |
| @@ -136,20 +134,6 @@ gendata_cocsep_dfs(cocsep_dfs_arg_t arg[static 1]) | |||
| 136 | return cc; | 134 | return cc; |
| 137 | } | 135 | } |
| 138 | 136 | ||
| 139 | STATIC void | ||
| 140 | getdistribution_cocsep( | ||
| 141 | const uint32_t table[static COCSEP_TABLESIZE], | ||
| 142 | uint64_t distr[static 21] | ||
| 143 | ) | ||
| 144 | { | ||
| 145 | size_t i; | ||
| 146 | |||
| 147 | memset(distr, 0, 21 * sizeof(uint64_t)); | ||
| 148 | |||
| 149 | for (i = 0; i < COCSEP_TABLESIZE; i++) | ||
| 150 | distr[CBOUND(table[i])]++; | ||
| 151 | } | ||
| 152 | |||
| 153 | STATIC_INLINE bool | 137 | STATIC_INLINE bool |
| 154 | gendata_cocsep_get_visited( | 138 | gendata_cocsep_get_visited( |
| 155 | const uint8_t a[static COCSEP_VISITEDSIZE], | 139 | const uint8_t a[static COCSEP_VISITEDSIZE], |
diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h index c1a9ced..644ddc2 100644 --- a/src/solvers/h48/gendata_h48.h +++ b/src/solvers/h48/gendata_h48.h | |||
| @@ -1,3 +1,5 @@ | |||
| 1 | STATIC long long gendata_h48_dispatch( | ||
| 2 | const char *, unsigned long long, unsigned char *); | ||
| 1 | STATIC uint64_t gendata_h48short(gendata_h48short_arg_t [static 1]); | 3 | STATIC uint64_t gendata_h48short(gendata_h48short_arg_t [static 1]); |
| 2 | STATIC int64_t gendata_h48(gendata_h48_arg_t [static 1]); | 4 | STATIC int64_t gendata_h48(gendata_h48_arg_t [static 1]); |
| 3 | STATIC void gendata_h48h0k4(gendata_h48_arg_t [static 1]); | 5 | STATIC void gendata_h48h0k4(gendata_h48_arg_t [static 1]); |
| @@ -12,9 +14,6 @@ STATIC_INLINE bool gendata_h48k2_dfs_stop( | |||
| 12 | cube_t, int8_t, h48k2_dfs_arg_t [static 1]); | 14 | cube_t, int8_t, h48k2_dfs_arg_t [static 1]); |
| 13 | STATIC void gendata_h48k2_dfs(h48k2_dfs_arg_t [static 1]); | 15 | STATIC void gendata_h48k2_dfs(h48k2_dfs_arg_t [static 1]); |
| 14 | STATIC tableinfo_t makeinfo_h48k2(gendata_h48_arg_t [static 1]); | 16 | STATIC tableinfo_t makeinfo_h48k2(gendata_h48_arg_t [static 1]); |
| 15 | STATIC void *getdistribution_h48_runthread(void *); | ||
| 16 | STATIC void getdistribution_h48(const unsigned char *, | ||
| 17 | uint64_t [static INFO_DISTRIBUTION_LEN], uint8_t, uint8_t); | ||
| 18 | 17 | ||
| 19 | STATIC const uint32_t *get_cocsepdata_constptr(const unsigned char *); | 18 | STATIC const uint32_t *get_cocsepdata_constptr(const unsigned char *); |
| 20 | STATIC const unsigned char *get_h48data_constptr(const unsigned char *); | 19 | STATIC const unsigned char *get_h48data_constptr(const unsigned char *); |
| @@ -28,6 +27,27 @@ STATIC_INLINE void set_h48_pval_atomic( | |||
| 28 | 27 | ||
| 29 | size_t gendata_h48_derive(uint8_t, const unsigned char *, unsigned char *); | 28 | size_t gendata_h48_derive(uint8_t, const unsigned char *, unsigned char *); |
| 30 | 29 | ||
| 30 | STATIC long long | ||
| 31 | gendata_h48_dispatch( | ||
| 32 | const char *solver, | ||
| 33 | unsigned long long data_size, | ||
| 34 | unsigned char *data | ||
| 35 | ) | ||
| 36 | { | ||
| 37 | long long err; | ||
| 38 | gendata_h48_arg_t arg; | ||
| 39 | |||
| 40 | err = parse_h48_hk(solver, &arg.h, &arg.k); | ||
| 41 | if (err != NISSY_OK) | ||
| 42 | return err; | ||
| 43 | |||
| 44 | arg.buf_size = data_size; | ||
| 45 | arg.buf = data; | ||
| 46 | arg.maxdepth = 20; | ||
| 47 | |||
| 48 | return gendata_h48(&arg); | ||
| 49 | } | ||
| 50 | |||
| 31 | STATIC uint64_t | 51 | STATIC uint64_t |
| 32 | gendata_h48short(gendata_h48short_arg_t arg[static 1]) | 52 | gendata_h48short(gendata_h48short_arg_t arg[static 1]) |
| 33 | { | 53 | { |
| @@ -649,64 +669,6 @@ makeinfo_h48k2(gendata_h48_arg_t arg[static 1]) | |||
| 649 | return info; | 669 | return info; |
| 650 | } | 670 | } |
| 651 | 671 | ||
| 652 | STATIC void * | ||
| 653 | getdistribution_h48_runthread(void *arg) | ||
| 654 | { | ||
| 655 | getdistribution_h48_data_t *data = (getdistribution_h48_data_t *)arg; | ||
| 656 | const unsigned char *table; | ||
| 657 | uint8_t j, k, m; | ||
| 658 | int64_t i; | ||
| 659 | |||
| 660 | memset(data->distr, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t)); | ||
| 661 | |||
| 662 | k = data->k; | ||
| 663 | table = data->table; | ||
| 664 | m = H48_MASK(0, k); | ||
| 665 | for (i = data->min; i < data->max; i++) | ||
| 666 | for (j = 0; j < H48_DIV(k); j++) | ||
| 667 | data->distr[(table[i] & (m << (j*k))) >> (j*k)]++; | ||
| 668 | |||
| 669 | return NULL; | ||
| 670 | } | ||
| 671 | |||
| 672 | STATIC void | ||
| 673 | getdistribution_h48( | ||
| 674 | const unsigned char *table, | ||
| 675 | uint64_t distr[static INFO_DISTRIBUTION_LEN], | ||
| 676 | uint8_t h, | ||
| 677 | uint8_t k | ||
| 678 | ) { | ||
| 679 | getdistribution_h48_data_t targ[THREADS]; | ||
| 680 | pthread_t thread[THREADS]; | ||
| 681 | uint64_t local_distr[THREADS][INFO_DISTRIBUTION_LEN]; | ||
| 682 | int64_t i, j, nbytes, sz; | ||
| 683 | |||
| 684 | nbytes = H48_COORDMAX(h) / H48_DIV(k); | ||
| 685 | sz = nbytes / THREADS; | ||
| 686 | for (i = 0; i < THREADS; i++) { | ||
| 687 | targ[i] = (getdistribution_h48_data_t) { | ||
| 688 | .min = i * sz, | ||
| 689 | .max = i == THREADS - 1 ? nbytes : (i+1) * sz, | ||
| 690 | .k = k, | ||
| 691 | .distr = local_distr[i], | ||
| 692 | .table = table, | ||
| 693 | }; | ||
| 694 | pthread_create(&thread[i], NULL, | ||
| 695 | getdistribution_h48_runthread, &targ[i]); | ||
| 696 | } | ||
| 697 | |||
| 698 | for (i = 0; i < THREADS; i++) | ||
| 699 | pthread_join(thread[i], NULL); | ||
| 700 | |||
| 701 | memset(distr, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t)); | ||
| 702 | for (i = 0; i < THREADS; i++) | ||
| 703 | for (j = 0; j < INFO_DISTRIBUTION_LEN; j++) | ||
| 704 | distr[j] += local_distr[i][j]; | ||
| 705 | |||
| 706 | for (i = nbytes * H48_DIV(k); i < H48_COORDMAX(h); i++) | ||
| 707 | distr[get_h48_pval(table, i, k)]++; | ||
| 708 | } | ||
| 709 | |||
| 710 | STATIC const uint32_t * | 672 | STATIC const uint32_t * |
| 711 | get_cocsepdata_constptr(const unsigned char *data) | 673 | get_cocsepdata_constptr(const unsigned char *data) |
| 712 | { | 674 | { |
| @@ -821,7 +783,7 @@ gendata_h48_derive(uint8_t h, const unsigned char *fulltable, unsigned char *buf | |||
| 821 | h48derive, j, arg.k, MIN(val_full, val_derive)); | 783 | h48derive, j, arg.k, MIN(val_full, val_derive)); |
| 822 | } | 784 | } |
| 823 | 785 | ||
| 824 | getdistribution_h48(h48derive, arg.info.distribution, h, arg.k); | 786 | getdistribution(h48derive, arg.info.distribution, &arg.info); |
| 825 | 787 | ||
| 826 | bufsize = arg.buf_size - COCSEP_FULLSIZE - INFOSIZE; | 788 | bufsize = arg.buf_size - COCSEP_FULLSIZE - INFOSIZE; |
| 827 | if (writetableinfo(&arg.info, bufsize, (unsigned char *)arg.h48buf) | 789 | if (writetableinfo(&arg.info, bufsize, (unsigned char *)arg.h48buf) |
diff --git a/src/solvers/h48/gendata_types_macros.h b/src/solvers/h48/gendata_types_macros.h index c4b1b5a..b0592c2 100644 --- a/src/solvers/h48/gendata_types_macros.h +++ b/src/solvers/h48/gendata_types_macros.h | |||
| @@ -121,11 +121,3 @@ typedef struct { | |||
| 121 | _Atomic unsigned char *table_atomic; | 121 | _Atomic unsigned char *table_atomic; |
| 122 | pthread_mutex_t **table_mutex; | 122 | pthread_mutex_t **table_mutex; |
| 123 | } gendata_h48_mark_t; | 123 | } gendata_h48_mark_t; |
| 124 | |||
| 125 | typedef struct { | ||
| 126 | int64_t min; | ||
| 127 | int64_t max; | ||
| 128 | uint8_t k; | ||
| 129 | uint64_t *distr; | ||
| 130 | const unsigned char *table; | ||
| 131 | } getdistribution_h48_data_t; | ||
diff --git a/src/solvers/h48/h48.h b/src/solvers/h48/h48.h index 0cfa773..79d2583 100644 --- a/src/solvers/h48/h48.h +++ b/src/solvers/h48/h48.h | |||
| @@ -1,3 +1,4 @@ | |||
| 1 | #include "utils.h" | ||
| 1 | #include "coordinate_types_macros.h" | 2 | #include "coordinate_types_macros.h" |
| 2 | #include "map_types_macros.h" | 3 | #include "map_types_macros.h" |
| 3 | #include "gendata_types_macros.h" | 4 | #include "gendata_types_macros.h" |
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index f2967ed..2818c09 100644 --- a/src/solvers/h48/solve.h +++ b/src/solvers/h48/solve.h | |||
| @@ -50,6 +50,10 @@ typedef struct { | |||
| 50 | int8_t *shortest_sol; | 50 | int8_t *shortest_sol; |
| 51 | } dfsarg_solve_h48_maketasks_t; | 51 | } dfsarg_solve_h48_maketasks_t; |
| 52 | 52 | ||
| 53 | STATIC long long solve_h48_dispatch(oriented_cube_t, const char *, unsigned, | ||
| 54 | unsigned, unsigned, unsigned, unsigned, unsigned, unsigned long long n, | ||
| 55 | const unsigned char [n], unsigned m, char [m], | ||
| 56 | long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); | ||
| 53 | STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t [static 1]); | 57 | STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t [static 1]); |
| 54 | STATIC int64_t solve_h48_maketasks( | 58 | STATIC int64_t solve_h48_maketasks( |
| 55 | dfsarg_solve_h48_t [static 1], dfsarg_solve_h48_maketasks_t [static 1], | 59 | dfsarg_solve_h48_t [static 1], dfsarg_solve_h48_maketasks_t [static 1], |
| @@ -61,6 +65,36 @@ STATIC int64_t solve_h48(oriented_cube_t, uint8_t, uint8_t, uint8_t, uint8_t, | |||
| 61 | uint8_t, uint64_t, const unsigned char *, size_t n, char [n], | 65 | uint8_t, uint64_t, const unsigned char *, size_t n, char [n], |
| 62 | long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); | 66 | long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); |
| 63 | 67 | ||
| 68 | STATIC long long solve_h48_dispatch( | ||
| 69 | oriented_cube_t oc, | ||
| 70 | const char *solver, | ||
| 71 | unsigned nissflag, | ||
| 72 | unsigned minmoves, | ||
| 73 | unsigned maxmoves, | ||
| 74 | unsigned maxsols, | ||
| 75 | unsigned optimal, | ||
| 76 | unsigned threads, | ||
| 77 | unsigned long long data_size, | ||
| 78 | const unsigned char data[data_size], | ||
| 79 | unsigned sols_size, | ||
| 80 | char sols[sols_size], | ||
| 81 | long long stats[static NISSY_SIZE_SOLVE_STATS], | ||
| 82 | int (*poll_status)(void *), | ||
| 83 | void *poll_status_data | ||
| 84 | ) | ||
| 85 | { | ||
| 86 | uint8_t h, k; | ||
| 87 | long long err; | ||
| 88 | |||
| 89 | err = parse_h48_hk(solver, &h, &k); | ||
| 90 | if (err != NISSY_OK) | ||
| 91 | return err; | ||
| 92 | |||
| 93 | return solve_h48(oc, minmoves, maxmoves, maxsols, optimal, threads, | ||
| 94 | data_size, data, sols_size, sols, stats, | ||
| 95 | poll_status, poll_status_data); | ||
| 96 | } | ||
| 97 | |||
| 64 | STATIC_INLINE bool | 98 | STATIC_INLINE bool |
| 65 | solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) | 99 | solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) |
| 66 | { | 100 | { |
diff --git a/src/solvers/h48/utils.h b/src/solvers/h48/utils.h new file mode 100644 index 0000000..b266c66 --- /dev/null +++ b/src/solvers/h48/utils.h | |||
| @@ -0,0 +1,66 @@ | |||
| 1 | long long parse_h48_hk( | ||
| 2 | const char *, uint8_t [static 1], uint8_t [static 1]); | ||
| 3 | STATIC long long dataid_h48(const char *, char [static NISSY_SIZE_DATAID]); | ||
| 4 | |||
| 5 | long long | ||
| 6 | parse_h48_hk(const char *buf, uint8_t h[static 1], uint8_t k[static 1]) | ||
| 7 | { | ||
| 8 | char format_error_msg[100]; | ||
| 9 | sprintf(format_error_msg, "[H48] Error parsing H48 solver: must be in " | ||
| 10 | "'h48h*k*' format, but got '%s'\n", buf); | ||
| 11 | |||
| 12 | buf += 3; | ||
| 13 | |||
| 14 | if (*buf != 'h') { | ||
| 15 | LOG(format_error_msg); | ||
| 16 | goto parse_h48_hk_error; | ||
| 17 | } | ||
| 18 | buf++; | ||
| 19 | |||
| 20 | *h = atoi(buf); | ||
| 21 | if (*h > 11) { | ||
| 22 | LOG("[H48] Invalid value %" PRIu8 " for parameter h\n", *h); | ||
| 23 | goto parse_h48_hk_error; | ||
| 24 | } | ||
| 25 | |||
| 26 | for ( ; *buf >= 0 + '0' && *buf <= 9 + '0'; buf++) { | ||
| 27 | if (*buf == 0) { | ||
| 28 | LOG(format_error_msg); | ||
| 29 | goto parse_h48_hk_error; | ||
| 30 | } | ||
| 31 | } | ||
| 32 | |||
| 33 | if (*buf != 'k') { | ||
| 34 | LOG(format_error_msg); | ||
| 35 | goto parse_h48_hk_error; | ||
| 36 | } | ||
| 37 | buf++; | ||
| 38 | |||
| 39 | *k = atoi(buf); | ||
| 40 | if (!(*k == 2 || (*k == 4 && *h == 0))) { | ||
| 41 | LOG("[H48] Invalid combinations of values h=%" PRIu8 " and k=%" | ||
| 42 | PRIu8 " for parameters h and k\n", *h, *k); | ||
| 43 | goto parse_h48_hk_error; | ||
| 44 | } | ||
| 45 | |||
| 46 | return NISSY_OK; | ||
| 47 | |||
| 48 | parse_h48_hk_error: | ||
| 49 | *h = 0; | ||
| 50 | *k = 0; | ||
| 51 | return NISSY_ERROR_INVALID_SOLVER; | ||
| 52 | } | ||
| 53 | |||
| 54 | STATIC long long | ||
| 55 | dataid_h48(const char *hk, char buf[static NISSY_SIZE_DATAID]) | ||
| 56 | { | ||
| 57 | uint8_t h, k; | ||
| 58 | long long err; | ||
| 59 | |||
| 60 | err = parse_h48_hk(hk, &h, &k); | ||
| 61 | if (err < 0) | ||
| 62 | return err; | ||
| 63 | |||
| 64 | sprintf(buf, "h48h%" PRIu8 "k%" PRIu8, h, k); | ||
| 65 | return NISSY_OK; | ||
| 66 | } | ||
