aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/arch/arch.h3
-rw-r--r--src/nissy.c1
-rw-r--r--src/utils/math.h73
-rw-r--r--test/010_math_permtoindex/00_noperm.in4
-rw-r--r--test/010_math_permtoindex/00_noperm.out1
-rw-r--r--test/010_math_permtoindex/01_toobig.in16
-rw-r--r--test/010_math_permtoindex/01_toobig.out1
-rw-r--r--test/010_math_permtoindex/02_offrange.in4
-rw-r--r--test/010_math_permtoindex/02_offrange.out1
-rw-r--r--test/011_math_indextoperm/00_noperm.in2
-rw-r--r--test/011_math_indextoperm/00_noperm.out3
-rw-r--r--test/011_math_indextoperm/01_toobig.in2
-rw-r--r--test/011_math_indextoperm/01_toobig.out15
-rw-r--r--test/011_math_indextoperm/02_offrange.in2
-rw-r--r--test/011_math_indextoperm/02_offrange.out3
-rw-r--r--test/013_math_digitstosumzero/00_bad_n.in5
-rw-r--r--test/013_math_digitstosumzero/00_bad_n.out1
-rw-r--r--test/013_math_digitstosumzero/01_bad_b12.in14
-rw-r--r--test/013_math_digitstosumzero/01_bad_b12.out1
-rw-r--r--test/013_math_digitstosumzero/02_bad_b8.in10
-rw-r--r--test/013_math_digitstosumzero/02_bad_b8.out1
-rw-r--r--test/013_math_digitstosumzero/09_sumnonzero.in10
-rw-r--r--test/013_math_digitstosumzero/09_sumnonzero.out1
-rw-r--r--test/014_math_sumzerotodigits/00_bad_n.in3
-rw-r--r--test/014_math_sumzerotodigits/00_bad_n.out13
-rw-r--r--test/014_math_sumzerotodigits/01_bad_b12.in3
-rw-r--r--test/014_math_sumzerotodigits/01_bad_b12.out12
-rw-r--r--test/014_math_sumzerotodigits/02_bad_b8.in3
-rw-r--r--test/014_math_sumzerotodigits/02_bad_b8.out8
29 files changed, 21 insertions, 195 deletions
diff --git a/src/arch/arch.h b/src/arch/arch.h
index 2c418a6..d0ef20c 100644
--- a/src/arch/arch.h
+++ b/src/arch/arch.h
@@ -12,7 +12,6 @@ typedef __m256i cube_t;
12 12
13#elif defined(NEON) 13#elif defined(NEON)
14 14
15#include <stdlib.h>
16#include <arm_neon.h> 15#include <arm_neon.h>
17 16
18typedef struct { 17typedef struct {
@@ -28,8 +27,6 @@ typedef struct {
28 27
29#else 28#else
30 29
31#include <stdlib.h>
32
33typedef struct { 30typedef struct {
34 uint8_t corner[8]; 31 uint8_t corner[8];
35 uint8_t edge[12]; 32 uint8_t edge[12];
diff --git a/src/nissy.c b/src/nissy.c
index 3190e55..93a4841 100644
--- a/src/nissy.c
+++ b/src/nissy.c
@@ -1,3 +1,4 @@
1#include <stdlib.h>
1#include <inttypes.h> 2#include <inttypes.h>
2#include <limits.h> 3#include <limits.h>
3#include <pthread.h> 4#include <pthread.h>
diff --git a/src/utils/math.h b/src/utils/math.h
index 4b1da12..95ec0aa 100644
--- a/src/utils/math.h
+++ b/src/utils/math.h
@@ -3,7 +3,6 @@
3#define MAX(x, y) ((x) > (y) ? (x) : (y)) 3#define MAX(x, y) ((x) > (y) ? (x) : (y))
4#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d)) 4#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d))
5 5
6STATIC bool isperm(size_t, const uint8_t *);
7STATIC int64_t permtoindex(size_t, const uint8_t *); 6STATIC int64_t permtoindex(size_t, const uint8_t *);
8STATIC void indextoperm(int64_t, size_t, uint8_t *); 7STATIC void indextoperm(int64_t, size_t, uint8_t *);
9STATIC int permsign(size_t, const uint8_t *); 8STATIC int permsign(size_t, const uint8_t *);
@@ -11,18 +10,15 @@ STATIC int64_t digitstosumzero(size_t, const uint8_t *, uint8_t);
11STATIC void sumzerotodigits(int64_t, size_t, uint8_t, uint8_t *); 10STATIC void sumzerotodigits(int64_t, size_t, uint8_t, uint8_t *);
12STATIC double intpow(double, uint64_t); 11STATIC double intpow(double, uint64_t);
13 12
13/* This code is only used for assertions in debug mode */
14#ifdef DEBUG
15STATIC bool isperm(size_t, const uint8_t *);
14STATIC bool 16STATIC bool
15isperm(size_t n, const uint8_t *a) 17isperm(size_t n, const uint8_t *a)
16{ 18{
17 size_t i; 19 size_t i;
18 bool aux[FACTORIAL_MAX+1]; 20 bool aux[FACTORIAL_MAX+1];
19 21
20 if (n > (size_t)FACTORIAL_MAX) {
21 LOG("Error: won't compute 'isperm()' for n=%zu because"
22 " it is larger than %" PRId64 "\n", n, FACTORIAL_MAX);
23 return false;
24 }
25
26 memset(aux, false, n); 22 memset(aux, false, n);
27 23
28 for (i = 0; i < n; i++) { 24 for (i = 0; i < n; i++) {
@@ -38,6 +34,7 @@ isperm(size_t n, const uint8_t *a)
38 34
39 return true; 35 return true;
40} 36}
37#endif
41 38
42STATIC int64_t 39STATIC int64_t
43permtoindex(size_t n, const uint8_t *a) 40permtoindex(size_t n, const uint8_t *a)
@@ -45,14 +42,10 @@ permtoindex(size_t n, const uint8_t *a)
45 size_t i, j; 42 size_t i, j;
46 int64_t c, ret; 43 int64_t c, ret;
47 44
48 if (n > (size_t)FACTORIAL_MAX) { 45 DBG_ASSERT(n <= FACTORIAL_MAX, "Error: cannot compute permtoindex() "
49 LOG("Error: won't compute 'permtoindex()' for n=%zu because " 46 "for set of size %zu > %" PRId64 "\n", n, FACTORIAL_MAX);
50 "it is larger than %" PRId64 "\n", n, FACTORIAL_MAX); 47 DBG_ASSERT(isperm(n, a), "Error: cannot compute permtoindex() for "
51 return -1; 48 "invalid permutation\n");
52 }
53
54 if (!isperm(n, a))
55 return -1;
56 49
57 for (i = 0, ret = 0; i < n; i++) { 50 for (i = 0, ret = 0; i < n; i++) {
58 for (j = i+1, c = 0; j < n; j++) 51 for (j = i+1, c = 0; j < n; j++)
@@ -70,17 +63,12 @@ indextoperm(int64_t p, size_t n, uint8_t *r)
70 size_t i, j; 63 size_t i, j;
71 uint8_t a[FACTORIAL_MAX+1]; 64 uint8_t a[FACTORIAL_MAX+1];
72 65
73 if (n > FACTORIAL_MAX) { 66 DBG_ASSERT(n <= FACTORIAL_MAX, "Error: cannot compute indextoperm() "
74 LOG("Error: won't compute 'indextoperm()' for n=%zu because " 67 "for set of size %zu > %" PRId64 "\n", n, FACTORIAL_MAX);
75 "it is larger than %" PRId64 "\n", n, FACTORIAL_MAX); 68 DBG_ASSERT(p >= 0 && p < factorial[n], "Error: invalid permutation "
76 goto indextoperm_error; 69 "index %" PRId64 " for set of size %zu\n", p, n);
77 }
78 70
79 memset(a, 0, n); 71 memset(a, 0, n);
80
81 if (p < 0 || p >= factorial[n])
82 goto indextoperm_error;
83
84 for (i = 0; i < n; i++) { 72 for (i = 0; i < n; i++) {
85 for (j = 0, c = 0; c <= p / factorial[n-i-1]; j++) 73 for (j = 0, c = 0; c <= p / factorial[n-i-1]; j++)
86 c += a[j] ? 0 : 1; 74 c += a[j] ? 0 : 1;
@@ -89,13 +77,7 @@ indextoperm(int64_t p, size_t n, uint8_t *r)
89 p %= factorial[n-i-1]; 77 p %= factorial[n-i-1];
90 } 78 }
91 79
92 if (!isperm(n, r))
93 goto indextoperm_error;
94
95 return; 80 return;
96
97indextoperm_error:
98 memset(r, UINT8_ERROR, n);
99} 81}
100 82
101STATIC int 83STATIC int
@@ -116,27 +98,17 @@ digitstosumzero(size_t n, const uint8_t *a, uint8_t b)
116 int64_t ret, p; 98 int64_t ret, p;
117 size_t i, sum; 99 size_t i, sum;
118 100
119 if (!((n == 8 && b == 3 ) || (n == 12 && b == 2))) { 101 DBG_ASSERT((n == 8 && b == 3 ) || (n == 12 && b == 2),
120 LOG("Error: won't compute 'sumzero' for n=%zu and b=%" PRIu8 102 "Error: digitstosumzero() called with n=%zu and b=%" PRIu8
121 " (use n=8 b=3 or n=12 b=2)\n", n, b); 103 " (use n=8 b=3 or n=12 b=2)\n", n, b);
122 return -1;
123 }
124 104
125 for (i = 1, ret = 0, p = 1, sum = 0; i < n; i++, p *= (int64_t)b) { 105 for (i = 1, ret = 0, p = 1, sum = 0; i < n; i++, p *= (int64_t)b) {
126 if (a[i] >= b) { 106 DBG_ASSERT(a[i] < b, "Error: digit %" PRIu8
127 LOG("Error: digit %" PRIu8 " larger than maximum" 107 " > %" PRIu8 "in digitstosumzero()\n", a[i], b);
128 " (b=%" PRIu8 "\n", a[i], b);
129 return -1;
130 }
131 sum += a[i]; 108 sum += a[i];
132 ret += p * (int64_t)a[i]; 109 ret += p * (int64_t)a[i];
133 } 110 }
134 111
135 if ((sum + a[0]) % b != 0) {
136 LOG("Error: digits do not have sum zero modulo b\n");
137 return -1;
138 }
139
140 return ret; 112 return ret;
141} 113}
142 114
@@ -146,11 +118,9 @@ sumzerotodigits(int64_t d, size_t n, uint8_t b, uint8_t *a)
146 uint8_t sum; 118 uint8_t sum;
147 size_t i; 119 size_t i;
148 120
149 if (!((n == 8 && b == 3 ) || (n == 12 && b == 2))) { 121 DBG_ASSERT((n == 8 && b == 3 ) || (n == 12 && b == 2),
150 LOG("Error: won't compute 'digits' for n=%zu and b=%" PRIu8 122 "Error: sumzerotodigits() called with n=%zu and b=%" PRIu8
151 " (use n=8 b=3 or n=12 b=2)\n", n, b); 123 " (use n=8 b=3 or n=12 b=2)\n", n, b);
152 goto sumzerotodigits_error;
153 }
154 124
155 for (i = 1, sum = 0; i < n; i++, d /= (int64_t)b) { 125 for (i = 1, sum = 0; i < n; i++, d /= (int64_t)b) {
156 a[i] = (uint8_t)(d % (int64_t)b); 126 a[i] = (uint8_t)(d % (int64_t)b);
@@ -159,9 +129,6 @@ sumzerotodigits(int64_t d, size_t n, uint8_t b, uint8_t *a)
159 a[0] = (b - (sum % b)) % b; 129 a[0] = (b - (sum % b)) % b;
160 130
161 return; 131 return;
162
163sumzerotodigits_error:
164 memset(a, UINT8_ERROR, n);
165} 132}
166 133
167STATIC double 134STATIC double
diff --git a/test/010_math_permtoindex/00_noperm.in b/test/010_math_permtoindex/00_noperm.in
deleted file mode 100644
index f838f21..0000000
--- a/test/010_math_permtoindex/00_noperm.in
+++ /dev/null
@@ -1,4 +0,0 @@
13
20
31
41
diff --git a/test/010_math_permtoindex/00_noperm.out b/test/010_math_permtoindex/00_noperm.out
deleted file mode 100644
index 3a2e3f4..0000000
--- a/test/010_math_permtoindex/00_noperm.out
+++ /dev/null
@@ -1 +0,0 @@
1-1
diff --git a/test/010_math_permtoindex/01_toobig.in b/test/010_math_permtoindex/01_toobig.in
deleted file mode 100644
index a0fb28c..0000000
--- a/test/010_math_permtoindex/01_toobig.in
+++ /dev/null
@@ -1,16 +0,0 @@
115
20
31
42
53
64
75
86
97
108
119
1210
1311
1412
1513
1614
diff --git a/test/010_math_permtoindex/01_toobig.out b/test/010_math_permtoindex/01_toobig.out
deleted file mode 100644
index 3a2e3f4..0000000
--- a/test/010_math_permtoindex/01_toobig.out
+++ /dev/null
@@ -1 +0,0 @@
1-1
diff --git a/test/010_math_permtoindex/02_offrange.in b/test/010_math_permtoindex/02_offrange.in
deleted file mode 100644
index 66ec716..0000000
--- a/test/010_math_permtoindex/02_offrange.in
+++ /dev/null
@@ -1,4 +0,0 @@
13
20
34
41
diff --git a/test/010_math_permtoindex/02_offrange.out b/test/010_math_permtoindex/02_offrange.out
deleted file mode 100644
index 3a2e3f4..0000000
--- a/test/010_math_permtoindex/02_offrange.out
+++ /dev/null
@@ -1 +0,0 @@
1-1
diff --git a/test/011_math_indextoperm/00_noperm.in b/test/011_math_indextoperm/00_noperm.in
deleted file mode 100644
index 81d7aba..0000000
--- a/test/011_math_indextoperm/00_noperm.in
+++ /dev/null
@@ -1,2 +0,0 @@
13
2-1
diff --git a/test/011_math_indextoperm/00_noperm.out b/test/011_math_indextoperm/00_noperm.out
deleted file mode 100644
index c656952..0000000
--- a/test/011_math_indextoperm/00_noperm.out
+++ /dev/null
@@ -1,3 +0,0 @@
1255
2255
3255
diff --git a/test/011_math_indextoperm/01_toobig.in b/test/011_math_indextoperm/01_toobig.in
deleted file mode 100644
index 227eae2..0000000
--- a/test/011_math_indextoperm/01_toobig.in
+++ /dev/null
@@ -1,2 +0,0 @@
115
20
diff --git a/test/011_math_indextoperm/01_toobig.out b/test/011_math_indextoperm/01_toobig.out
deleted file mode 100644
index a4cc325..0000000
--- a/test/011_math_indextoperm/01_toobig.out
+++ /dev/null
@@ -1,15 +0,0 @@
1255
2255
3255
4255
5255
6255
7255
8255
9255
10255
11255
12255
13255
14255
15255
diff --git a/test/011_math_indextoperm/02_offrange.in b/test/011_math_indextoperm/02_offrange.in
deleted file mode 100644
index 47b5fdd..0000000
--- a/test/011_math_indextoperm/02_offrange.in
+++ /dev/null
@@ -1,2 +0,0 @@
13
210
diff --git a/test/011_math_indextoperm/02_offrange.out b/test/011_math_indextoperm/02_offrange.out
deleted file mode 100644
index c656952..0000000
--- a/test/011_math_indextoperm/02_offrange.out
+++ /dev/null
@@ -1,3 +0,0 @@
1255
2255
3255
diff --git a/test/013_math_digitstosumzero/00_bad_n.in b/test/013_math_digitstosumzero/00_bad_n.in
deleted file mode 100644
index edcdc1b..0000000
--- a/test/013_math_digitstosumzero/00_bad_n.in
+++ /dev/null
@@ -1,5 +0,0 @@
13
24
30
41
50
diff --git a/test/013_math_digitstosumzero/00_bad_n.out b/test/013_math_digitstosumzero/00_bad_n.out
deleted file mode 100644
index 3a2e3f4..0000000
--- a/test/013_math_digitstosumzero/00_bad_n.out
+++ /dev/null
@@ -1 +0,0 @@
1-1
diff --git a/test/013_math_digitstosumzero/01_bad_b12.in b/test/013_math_digitstosumzero/01_bad_b12.in
deleted file mode 100644
index 26bb819..0000000
--- a/test/013_math_digitstosumzero/01_bad_b12.in
+++ /dev/null
@@ -1,14 +0,0 @@
112
23
30
41
52
60
71
82
92
101
110
120
130
141
diff --git a/test/013_math_digitstosumzero/01_bad_b12.out b/test/013_math_digitstosumzero/01_bad_b12.out
deleted file mode 100644
index 3a2e3f4..0000000
--- a/test/013_math_digitstosumzero/01_bad_b12.out
+++ /dev/null
@@ -1 +0,0 @@
1-1
diff --git a/test/013_math_digitstosumzero/02_bad_b8.in b/test/013_math_digitstosumzero/02_bad_b8.in
deleted file mode 100644
index 146d291..0000000
--- a/test/013_math_digitstosumzero/02_bad_b8.in
+++ /dev/null
@@ -1,10 +0,0 @@
18
22
30
40
50
60
70
80
90
101
diff --git a/test/013_math_digitstosumzero/02_bad_b8.out b/test/013_math_digitstosumzero/02_bad_b8.out
deleted file mode 100644
index 3a2e3f4..0000000
--- a/test/013_math_digitstosumzero/02_bad_b8.out
+++ /dev/null
@@ -1 +0,0 @@
1-1
diff --git a/test/013_math_digitstosumzero/09_sumnonzero.in b/test/013_math_digitstosumzero/09_sumnonzero.in
deleted file mode 100644
index 9466f9a..0000000
--- a/test/013_math_digitstosumzero/09_sumnonzero.in
+++ /dev/null
@@ -1,10 +0,0 @@
18
23
31
42
51
61
71
81
92
102
diff --git a/test/013_math_digitstosumzero/09_sumnonzero.out b/test/013_math_digitstosumzero/09_sumnonzero.out
deleted file mode 100644
index 3a2e3f4..0000000
--- a/test/013_math_digitstosumzero/09_sumnonzero.out
+++ /dev/null
@@ -1 +0,0 @@
1-1
diff --git a/test/014_math_sumzerotodigits/00_bad_n.in b/test/014_math_sumzerotodigits/00_bad_n.in
deleted file mode 100644
index 5e34db5..0000000
--- a/test/014_math_sumzerotodigits/00_bad_n.in
+++ /dev/null
@@ -1,3 +0,0 @@
113
24
32
diff --git a/test/014_math_sumzerotodigits/00_bad_n.out b/test/014_math_sumzerotodigits/00_bad_n.out
deleted file mode 100644
index f9c0ae0..0000000
--- a/test/014_math_sumzerotodigits/00_bad_n.out
+++ /dev/null
@@ -1,13 +0,0 @@
1255
2255
3255
4255
5255
6255
7255
8255
9255
10255
11255
12255
13255
diff --git a/test/014_math_sumzerotodigits/01_bad_b12.in b/test/014_math_sumzerotodigits/01_bad_b12.in
deleted file mode 100644
index 8a6d31c..0000000
--- a/test/014_math_sumzerotodigits/01_bad_b12.in
+++ /dev/null
@@ -1,3 +0,0 @@
112
23
32
diff --git a/test/014_math_sumzerotodigits/01_bad_b12.out b/test/014_math_sumzerotodigits/01_bad_b12.out
deleted file mode 100644
index 32b57e3..0000000
--- a/test/014_math_sumzerotodigits/01_bad_b12.out
+++ /dev/null
@@ -1,12 +0,0 @@
1255
2255
3255
4255
5255
6255
7255
8255
9255
10255
11255
12255
diff --git a/test/014_math_sumzerotodigits/02_bad_b8.in b/test/014_math_sumzerotodigits/02_bad_b8.in
deleted file mode 100644
index b70bee9..0000000
--- a/test/014_math_sumzerotodigits/02_bad_b8.in
+++ /dev/null
@@ -1,3 +0,0 @@
18
27
30
diff --git a/test/014_math_sumzerotodigits/02_bad_b8.out b/test/014_math_sumzerotodigits/02_bad_b8.out
deleted file mode 100644
index 22d5f76..0000000
--- a/test/014_math_sumzerotodigits/02_bad_b8.out
+++ /dev/null
@@ -1,8 +0,0 @@
1255
2255
3255
4255
5255
6255
7255
8255

Generated with cgit - Back to sebastiano.tronto.net