aboutsummaryrefslogtreecommitdiff
path: root/src/utils
diff options
context:
space:
mode:
Diffstat (limited to 'src/utils')
-rw-r--r--src/utils/constants.h295
-rw-r--r--src/utils/dbg_log.h16
-rw-r--r--src/utils/math.h185
-rw-r--r--src/utils/utils.h3
4 files changed, 499 insertions, 0 deletions
diff --git a/src/utils/constants.h b/src/utils/constants.h
new file mode 100644
index 0000000..52e2810
--- /dev/null
+++ b/src/utils/constants.h
@@ -0,0 +1,295 @@
1#define _bit_u8(i) (UINT8_C(1) << (uint8_t)(i))
2#define _bit_u32(i) (UINT32_C(1) << (uint32_t)(i))
3#define _bit_u64(i) (UINT64_C(1) << (uint64_t)(i))
4
5#define _max_factorial INT64_C(12)
6
7#define _2p11 INT64_C(2048)
8#define _2p12 INT64_C(4096)
9#define _3p7 INT64_C(2187)
10#define _3p8 INT64_C(6561)
11#define _12f INT64_C(479001600)
12#define _8f INT64_C(40320)
13#define _12c4 INT64_C(495)
14#define _8c4 INT64_C(70)
15
16_static int64_t binomial[12][12] = {
17 {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
18 {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
19 {1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
20 {1, 3, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0},
21 {1, 4, 6, 4, 1, 0, 0, 0, 0, 0, 0, 0},
22 {1, 5, 10, 10, 5, 1, 0, 0, 0, 0, 0, 0},
23 {1, 6, 15, 20, 15, 6, 1, 0, 0, 0, 0, 0},
24 {1, 7, 21, 35, 35, 21, 7, 1, 0, 0, 0, 0},
25 {1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 0, 0},
26 {1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 0, 0},
27 {1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0},
28 {1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1},
29};
30
31#define _move_U UINT8_C(0)
32#define _move_U2 UINT8_C(1)
33#define _move_U3 UINT8_C(2)
34#define _move_D UINT8_C(3)
35#define _move_D2 UINT8_C(4)
36#define _move_D3 UINT8_C(5)
37#define _move_R UINT8_C(6)
38#define _move_R2 UINT8_C(7)
39#define _move_R3 UINT8_C(8)
40#define _move_L UINT8_C(9)
41#define _move_L2 UINT8_C(10)
42#define _move_L3 UINT8_C(11)
43#define _move_F UINT8_C(12)
44#define _move_F2 UINT8_C(13)
45#define _move_F3 UINT8_C(14)
46#define _move_B UINT8_C(15)
47#define _move_B2 UINT8_C(16)
48#define _move_B3 UINT8_C(17)
49
50#define _trans_UFr UINT8_C(0)
51#define _trans_ULr UINT8_C(1)
52#define _trans_UBr UINT8_C(2)
53#define _trans_URr UINT8_C(3)
54#define _trans_DFr UINT8_C(4)
55#define _trans_DLr UINT8_C(5)
56#define _trans_DBr UINT8_C(6)
57#define _trans_DRr UINT8_C(7)
58#define _trans_RUr UINT8_C(8)
59#define _trans_RFr UINT8_C(9)
60#define _trans_RDr UINT8_C(10)
61#define _trans_RBr UINT8_C(11)
62#define _trans_LUr UINT8_C(12)
63#define _trans_LFr UINT8_C(13)
64#define _trans_LDr UINT8_C(14)
65#define _trans_LBr UINT8_C(15)
66#define _trans_FUr UINT8_C(16)
67#define _trans_FRr UINT8_C(17)
68#define _trans_FDr UINT8_C(18)
69#define _trans_FLr UINT8_C(19)
70#define _trans_BUr UINT8_C(20)
71#define _trans_BRr UINT8_C(21)
72#define _trans_BDr UINT8_C(22)
73#define _trans_BLr UINT8_C(23)
74
75#define _trans_UFm UINT8_C(24)
76#define _trans_ULm UINT8_C(25)
77#define _trans_UBm UINT8_C(26)
78#define _trans_URm UINT8_C(27)
79#define _trans_DFm UINT8_C(28)
80#define _trans_DLm UINT8_C(29)
81#define _trans_DBm UINT8_C(30)
82#define _trans_DRm UINT8_C(31)
83#define _trans_RUm UINT8_C(32)
84#define _trans_RFm UINT8_C(33)
85#define _trans_RDm UINT8_C(34)
86#define _trans_RBm UINT8_C(35)
87#define _trans_LUm UINT8_C(36)
88#define _trans_LFm UINT8_C(37)
89#define _trans_LDm UINT8_C(38)
90#define _trans_LBm UINT8_C(39)
91#define _trans_FUm UINT8_C(40)
92#define _trans_FRm UINT8_C(41)
93#define _trans_FDm UINT8_C(42)
94#define _trans_FLm UINT8_C(43)
95#define _trans_BUm UINT8_C(44)
96#define _trans_BRm UINT8_C(45)
97#define _trans_BDm UINT8_C(46)
98#define _trans_BLm UINT8_C(47)
99
100#define _c_ufr UINT8_C(0)
101#define _c_ubl UINT8_C(1)
102#define _c_dfl UINT8_C(2)
103#define _c_dbr UINT8_C(3)
104#define _c_ufl UINT8_C(4)
105#define _c_ubr UINT8_C(5)
106#define _c_dfr UINT8_C(6)
107#define _c_dbl UINT8_C(7)
108
109#define _e_uf UINT8_C(0)
110#define _e_ub UINT8_C(1)
111#define _e_db UINT8_C(2)
112#define _e_df UINT8_C(3)
113#define _e_ur UINT8_C(4)
114#define _e_ul UINT8_C(5)
115#define _e_dl UINT8_C(6)
116#define _e_dr UINT8_C(7)
117#define _e_fr UINT8_C(8)
118#define _e_fl UINT8_C(9)
119#define _e_bl UINT8_C(10)
120#define _e_br UINT8_C(11)
121
122#define _eoshift UINT8_C(4)
123#define _coshift UINT8_C(5)
124
125#define _pbits UINT8_C(0xF)
126#define _esepbit1 UINT8_C(0x4)
127#define _esepbit2 UINT8_C(0x8)
128#define _csepbit UINT8_C(0x4)
129#define _eobit UINT8_C(0x10)
130#define _cobits UINT8_C(0xF0)
131#define _cobits2 UINT8_C(0x60)
132#define _ctwist_cw UINT8_C(0x20)
133#define _ctwist_ccw UINT8_C(0x40)
134#define _eflip UINT8_C(0x10)
135#define _error UINT8_C(0xFF)
136
137_static const char *cornerstr[] = {
138 [_c_ufr] = "UFR",
139 [_c_ubl] = "UBL",
140 [_c_dfl] = "DFL",
141 [_c_dbr] = "DBR",
142 [_c_ufl] = "UFL",
143 [_c_ubr] = "UBR",
144 [_c_dfr] = "DFR",
145 [_c_dbl] = "DBL"
146};
147
148_static const char *cornerstralt[] = {
149 [_c_ufr] = "URF",
150 [_c_ubl] = "ULB",
151 [_c_dfl] = "DLF",
152 [_c_dbr] = "DRB",
153 [_c_ufl] = "ULF",
154 [_c_ubr] = "URB",
155 [_c_dfr] = "DRF",
156 [_c_dbl] = "DLB"
157};
158
159_static const char *edgestr[] = {
160 [_e_uf] = "UF",
161 [_e_ub] = "UB",
162 [_e_db] = "DB",
163 [_e_df] = "DF",
164 [_e_ur] = "UR",
165 [_e_ul] = "UL",
166 [_e_dl] = "DL",
167 [_e_dr] = "DR",
168 [_e_fr] = "FR",
169 [_e_fl] = "FL",
170 [_e_bl] = "BL",
171 [_e_br] = "BR"
172};
173
174_static const char *movestr[] = {
175 [_move_U] = "U",
176 [_move_U2] = "U2",
177 [_move_U3] = "U'",
178 [_move_D] = "D",
179 [_move_D2] = "D2",
180 [_move_D3] = "D'",
181 [_move_R] = "R",
182 [_move_R2] = "R2",
183 [_move_R3] = "R'",
184 [_move_L] = "L",
185 [_move_L2] = "L2",
186 [_move_L3] = "L'",
187 [_move_F] = "F",
188 [_move_F2] = "F2",
189 [_move_F3] = "F'",
190 [_move_B] = "B",
191 [_move_B2] = "B2",
192 [_move_B3] = "B'",
193};
194
195_static const char *transstr[] = {
196 [_trans_UFr] = "rotation UF",
197 [_trans_UFm] = "mirrored UF",
198 [_trans_ULr] = "rotation UL",
199 [_trans_ULm] = "mirrored UL",
200 [_trans_UBr] = "rotation UB",
201 [_trans_UBm] = "mirrored UB",
202 [_trans_URr] = "rotation UR",
203 [_trans_URm] = "mirrored UR",
204 [_trans_DFr] = "rotation DF",
205 [_trans_DFm] = "mirrored DF",
206 [_trans_DLr] = "rotation DL",
207 [_trans_DLm] = "mirrored DL",
208 [_trans_DBr] = "rotation DB",
209 [_trans_DBm] = "mirrored DB",
210 [_trans_DRr] = "rotation DR",
211 [_trans_DRm] = "mirrored DR",
212 [_trans_RUr] = "rotation RU",
213 [_trans_RUm] = "mirrored RU",
214 [_trans_RFr] = "rotation RF",
215 [_trans_RFm] = "mirrored RF",
216 [_trans_RDr] = "rotation RD",
217 [_trans_RDm] = "mirrored RD",
218 [_trans_RBr] = "rotation RB",
219 [_trans_RBm] = "mirrored RB",
220 [_trans_LUr] = "rotation LU",
221 [_trans_LUm] = "mirrored LU",
222 [_trans_LFr] = "rotation LF",
223 [_trans_LFm] = "mirrored LF",
224 [_trans_LDr] = "rotation LD",
225 [_trans_LDm] = "mirrored LD",
226 [_trans_LBr] = "rotation LB",
227 [_trans_LBm] = "mirrored LB",
228 [_trans_FUr] = "rotation FU",
229 [_trans_FUm] = "mirrored FU",
230 [_trans_FRr] = "rotation FR",
231 [_trans_FRm] = "mirrored FR",
232 [_trans_FDr] = "rotation FD",
233 [_trans_FDm] = "mirrored FD",
234 [_trans_FLr] = "rotation FL",
235 [_trans_FLm] = "mirrored FL",
236 [_trans_BUr] = "rotation BU",
237 [_trans_BUm] = "mirrored BU",
238 [_trans_BRr] = "rotation BR",
239 [_trans_BRm] = "mirrored BR",
240 [_trans_BDr] = "rotation BD",
241 [_trans_BDm] = "mirrored BD",
242 [_trans_BLr] = "rotation BL",
243 [_trans_BLm] = "mirrored BL",
244};
245
246static uint8_t inverse_trans_table[48] = {
247 [_trans_UFr] = _trans_UFr,
248 [_trans_UFm] = _trans_UFm,
249 [_trans_ULr] = _trans_URr,
250 [_trans_ULm] = _trans_ULm,
251 [_trans_UBr] = _trans_UBr,
252 [_trans_UBm] = _trans_UBm,
253 [_trans_URr] = _trans_ULr,
254 [_trans_URm] = _trans_URm,
255 [_trans_DFr] = _trans_DFr,
256 [_trans_DFm] = _trans_DFm,
257 [_trans_DLr] = _trans_DLr,
258 [_trans_DLm] = _trans_DRm,
259 [_trans_DBr] = _trans_DBr,
260 [_trans_DBm] = _trans_DBm,
261 [_trans_DRr] = _trans_DRr,
262 [_trans_DRm] = _trans_DLm,
263 [_trans_RUr] = _trans_FRr,
264 [_trans_RUm] = _trans_FLm,
265 [_trans_RFr] = _trans_LFr,
266 [_trans_RFm] = _trans_RFm,
267 [_trans_RDr] = _trans_BLr,
268 [_trans_RDm] = _trans_BRm,
269 [_trans_RBr] = _trans_RBr,
270 [_trans_RBm] = _trans_LBm,
271 [_trans_LUr] = _trans_FLr,
272 [_trans_LUm] = _trans_FRm,
273 [_trans_LFr] = _trans_RFr,
274 [_trans_LFm] = _trans_LFm,
275 [_trans_LDr] = _trans_BRr,
276 [_trans_LDm] = _trans_BLm,
277 [_trans_LBr] = _trans_LBr,
278 [_trans_LBm] = _trans_RBm,
279 [_trans_FUr] = _trans_FUr,
280 [_trans_FUm] = _trans_FUm,
281 [_trans_FRr] = _trans_RUr,
282 [_trans_FRm] = _trans_LUm,
283 [_trans_FDr] = _trans_BUr,
284 [_trans_FDm] = _trans_BUm,
285 [_trans_FLr] = _trans_LUr,
286 [_trans_FLm] = _trans_RUm,
287 [_trans_BUr] = _trans_FDr,
288 [_trans_BUm] = _trans_FDm,
289 [_trans_BRr] = _trans_LDr,
290 [_trans_BRm] = _trans_RDm,
291 [_trans_BDr] = _trans_BDr,
292 [_trans_BDm] = _trans_BDm,
293 [_trans_BLr] = _trans_RDr,
294 [_trans_BLm] = _trans_LDm,
295};
diff --git a/src/utils/dbg_log.h b/src/utils/dbg_log.h
new file mode 100644
index 0000000..427eceb
--- /dev/null
+++ b/src/utils/dbg_log.h
@@ -0,0 +1,16 @@
1void (*nissy_log)(const char *, ...);
2
3#define LOG(...) if (nissy_log != NULL) nissy_log(__VA_ARGS__);
4
5#ifdef DEBUG
6#define _static
7#define _static_inline
8#define DBG_WARN(condition, ...) if (!(condition)) LOG(__VA_ARGS__);
9#define DBG_ASSERT(condition, retval, ...) \
10 if (!(condition)) { LOG(__VA_ARGS__); return retval; }
11#else
12#define _static static
13#define _static_inline static inline
14#define DBG_WARN(condition, ...)
15#define DBG_ASSERT(condition, retval, ...)
16#endif
diff --git a/src/utils/math.h b/src/utils/math.h
new file mode 100644
index 0000000..87402e6
--- /dev/null
+++ b/src/utils/math.h
@@ -0,0 +1,185 @@
1#define _swap(x, y) do { x ^= y; y ^= x; x ^= y; } while (0)
2#define _min(x, y) ((x) < (y) ? (x) : (y))
3#define _max(x, y) ((x) > (y) ? (x) : (y))
4
5_static int64_t factorial(int64_t);
6_static bool isperm(uint8_t *, int64_t);
7_static int64_t permtoindex(uint8_t *, int64_t);
8_static void indextoperm(int64_t, int64_t, uint8_t *);
9_static int permsign(uint8_t *, int64_t);
10_static int64_t digitstosumzero(uint8_t *, uint8_t, uint8_t);
11_static void sumzerotodigits(int64_t, uint8_t, uint8_t, uint8_t *);
12
13_static int64_t
14factorial(int64_t n)
15{
16 int64_t i, ret;
17
18 if (n > _max_factorial) {
19 LOG("Error: won't compute factorial for n=%" PRId64 " because"
20 " it is larger than %" PRId64 "\n", n, _max_factorial);
21 return -1;
22 }
23
24 if (n < 0)
25 return 0;
26
27 for (i = 1, ret = 1; i <= n; i++)
28 ret *= i;
29
30 return ret;
31}
32
33_static bool
34isperm(uint8_t *a, int64_t n)
35{
36 int64_t i;
37 bool aux[_max_factorial+1];
38
39 if (n > _max_factorial) {
40 LOG("Error: won't compute 'isperm()' for n=%" PRId64 " because"
41 " it is larger than %" PRId64 "\n", n, _max_factorial);
42 return false;
43 }
44
45 memset(aux, false, n);
46
47 for (i = 0; i < n; i++) {
48 if (a[i] >= n)
49 return false;
50 else
51 aux[a[i]] = true;
52 }
53
54 for (i = 0; i < n; i++)
55 if (!aux[i])
56 return false;
57
58 return true;
59}
60
61_static int64_t
62permtoindex(uint8_t *a, int64_t n)
63{
64 int64_t i, j, c, ret;
65
66 if (n > _max_factorial) {
67 LOG("Error: won't compute 'permtoindex()' for n=%" PRId64
68 " because it is larger than %" PRId64 "\n",
69 n, _max_factorial);
70 return -1;
71 }
72
73 if (!isperm(a, n))
74 return -1;
75
76 for (i = 0, ret = 0; i < n; i++) {
77 for (j = i+1, c = 0; j < n; j++)
78 c += (a[i] > a[j]) ? 1 : 0;
79 ret += factorial(n-i-1) * c;
80 }
81
82 return ret;
83}
84
85_static void
86indextoperm(int64_t p, int64_t n, uint8_t *r)
87{
88 int64_t i, j, c;
89 uint8_t a[_max_factorial+1];
90
91 if (n > _max_factorial) {
92 LOG("Error: won't compute 'permtoindex()' for n=%" PRId64
93 " because it is larger than %" PRId64 "\n",
94 n, _max_factorial);
95 goto indextoperm_error;
96 }
97
98 memset(a, 0, n);
99
100 if (p < 0 || p >= factorial(n))
101 goto indextoperm_error;
102
103 for (i = 0; i < n; i++) {
104 for (j = 0, c = 0; c <= p / factorial(n-i-1); j++)
105 c += a[j] ? 0 : 1;
106 r[i] = j-1;
107 a[j-1] = 1;
108 p %= factorial(n-i-1);
109 }
110
111 if (!isperm(r, n))
112 goto indextoperm_error;
113
114 return;
115
116indextoperm_error:
117 memset(r, _error, n);
118}
119
120_static int
121permsign(uint8_t *a, int64_t n)
122{
123 int i, j;
124 uint8_t ret;
125
126 for (i = 0, ret = 0; i < n; i++)
127 for (j = i+1; j < n; j++)
128 ret += a[i] > a[j] ? 1 : 0;
129
130 return ret % 2;
131}
132
133_static int64_t
134digitstosumzero(uint8_t *a, uint8_t n, uint8_t b)
135{
136 int64_t ret, p;
137 uint8_t i, sum;
138
139 if (!((n == 8 && b == 3 ) || (n == 12 && b == 2))) {
140 LOG("Won't compute 'sumzero' for n=%" PRIu8 "and b=%" PRIu8
141 " (use n=8 b=3 or n=12 b=2)\n", n, b);
142 return -1;
143 }
144
145 for (i = 1, ret = 0, p = 1, sum = 0; i < n; i++, p *= (int64_t)b) {
146 if (a[i] >= b) {
147 LOG("Error: digit %" PRIu8 " larger than maximum"
148 " (b=%" PRIu8 "\n", a[i], b);
149 return -1;
150 }
151 sum += a[i];
152 ret += p * (int64_t)a[i];
153 }
154
155 if ((sum + a[0]) % b != 0) {
156 LOG("Error: digits do not have sum zero modulo b\n");
157 return -1;
158 }
159
160 return ret;
161}
162
163_static void
164sumzerotodigits(int64_t d, uint8_t n, uint8_t b, uint8_t *a)
165{
166 uint8_t sum;
167 int64_t i;
168
169 if (!((n == 8 && b == 3 ) || (n == 12 && b == 2))) {
170 LOG("Won't compute 'digits' for n=%" PRIu8 "and b=%" PRIu8
171 " (use n=8 b=3 or n=12 b=2)\n");
172 goto digitstosumzero_error;
173 }
174
175 for (i = 1, sum = 0; i < n; i++, d /= (int64_t)b) {
176 a[i] = (uint8_t)(d % (int64_t)b);
177 sum += a[i];
178 }
179 a[0] = (b - (sum % b)) % b;
180
181 return;
182
183digitstosumzero_error:
184 memset(a, _error, n);
185}
diff --git a/src/utils/utils.h b/src/utils/utils.h
new file mode 100644
index 0000000..ce4355e
--- /dev/null
+++ b/src/utils/utils.h
@@ -0,0 +1,3 @@
1#include "dbg_log.h"
2#include "constants.h"
3#include "math.h"

Generated with cgit - Back to sebastiano.tronto.net