fn_engine.c

filter: Statementstmt 100% 298 / 298 Branchbran 90.3% 244 / 270 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 95.4% 542 / 568 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« fn_search.c ↑ Summary bin/fanorona »
1 /* fn_engine.c - the fanorona board, and nothing that judges a move.
2 *
3 * PERL-FREE by design: see include/fn_abi.h. This file compiles into the XS,
4 * into a plain program, or to wasm, and knows nothing about any of them.
5 *
6 * THIS FILE'S SCOPE. The grid, the padded index, the lines, put and lift, the
7 * side to move, the zobrist key, the position string in and out, and the three
8 * fields of the chain as plain state.
9 */
10  
11 #include <stdlib.h>
12 #include <string.h>
13 #include "fn_abi.h"
14  
15 /* ---- the position ---------------------------------------------------------
16 *
17 * A flat 77-cell array, the size of the board inside it, the side to move, the
18 * stones of each colour, and a key maintained incrementally. No pointers, so a
19 * copy is a struct assignment and two boards never share anything.
20 */
21  
22 struct fn_board {
23 unsigned char cell[FN_CELLS];
24 int cols;
25 int rows;
26 int side;
27 int stones[FN_BLACK + 1];
28 unsigned long long key;
29 int chain_at; /* -1 when no chain is open */
30 int chain_dir;
31 unsigned long long chain_seen; /* a bit a point, by point_bit */
32 };
33  
34 /* Boards handed out and not yet dropped. It exists so a test can show that a
35 * destructor ran exactly once; it is a plain int and is not synchronised. */
36 static int FN_LIVE = 0;
37  
38 /* ---- the zobrist table -----------------------------------------------------
39 *
40 * DERIVED, NOT COMMITTED. A fixed function of a fixed seed is the same in every
41 * process and on every machine, and cannot suffer the transcription error a
42 * hand-pasted array can. splitmix64 is published and has no weak seeds.
43 *
44 * CHANGING THIS GENERATOR, ITS SEED OR THE ORDER THE TABLE IS FILLED IN
45 * CHANGES EVERY KEY. t/02-position.t pins values so that is a red test.
46 */
47  
48 static unsigned long long ZOB[FN_BLACK + 1][FN_CELLS];
49 static unsigned long long ZOB_SIDE;
50 static unsigned long long ZOB_SIZE[FN_COLS_MAX + 1][FN_ROWS_MAX + 1];
51 static int ZOB_READY = 0;
52  
53 12556 static unsigned long long splitmix64(unsigned long long *state)
54 {
55 unsigned long long z;
56 12556 *state += 0x9E3779B97F4A7C15ULL;
57 12556 z = *state;
58 12556 z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
59 12556 z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
60 12556 return z ^ (z >> 31);
61 }
62  
63 105513567 static void zob_init(void)
64 {
65 105513567 unsigned long long s = 0x66616E6F726F6E61ULL; /* "fanorona" */
66 int p, c, r;
67 105513567 ▶ if (ZOB_READY) return;
Branch: 1 branch
BranchTrueFalseTotal
if (ZOB_READY) return; 105513524 43 105513567
68 172 ▶ for (p = 0; p <= FN_BLACK; p++)
Branch: 1 branch
BranchTrueFalseTotal
for (p = 0; p <= FN_BLACK; p++) 129 43 172
69 10062 ▶ for (c = 0; c < FN_CELLS; c++)
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < FN_CELLS; c++) 9933 129 10062
70 9933 ZOB[p][c] = splitmix64(&s);
71 43 ZOB_SIDE = splitmix64(&s);
72 473 ▶ for (c = 0; c <= FN_COLS_MAX; c++)
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c <= FN_COLS_MAX; c++) 430 43 473
73 3010 ▶ for (r = 0; r <= FN_ROWS_MAX; r++)
Branch: 1 branch
BranchTrueFalseTotal
for (r = 0; r <= FN_ROWS_MAX; r++) 2580 430 3010
74 2580 ZOB_SIZE[c][r] = splitmix64(&s);
75 43 ZOB_READY = 1;
76 }
77  
78 /* ---- geometry that does not depend on the size ------------------------------ */
79  
80 1 static int fn_stride(void) { return FN_STRIDE; }
81  
82 /* Odd widths 3 to 9, heights 3 and 5. An even side has no centre point. */
83 2820669 static int fn_size_ok(int cols, int rows)
84 {
85 2820669 ▶ if (cols < 3 || cols > FN_COLS_MAX || cols % 2 == 0) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (cols < 3 || cols > FN_COLS_MAX || cols % 2 == 0) return 0; 2820663 6 2820669
if (cols < 3 || cols > FN_COLS_MAX || cols % 2 == 0) return 0; 2820661 2 2820663
if (cols < 3 || cols > FN_COLS_MAX || cols % 2 == 0) return 0; 8 2820653 2820661
86 2820653 ▶ if (rows != 3 && rows != 5) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (rows != 3 && rows != 5) return 0; 2806685 13968 2820653
if (rows != 3 && rows != 5) return 0; 8 2806677 2806685
87 2820645 return 1;
88 }
89  
90 1771530482 static int fn_square_of(int file, int rank)
91 {
92 1771530482 ▶ if (file < 0 || file >= FN_COLS_MAX || rank < 0 || rank >= FN_ROWS_MAX) return -1;
Branch: 4 branches
BranchTrueFalseTotal
if (file < 0 || file >= FN_COLS_MAX || rank < 0 || rank >= FN_ROWS_MAX) return -1; 1771530481 1 1771530482
if (file < 0 || file >= FN_COLS_MAX || rank < 0 || rank >= FN_ROWS_MAX) return -1; 1771530480 1 1771530481
if (file < 0 || file >= FN_COLS_MAX || rank < 0 || rank >= FN_ROWS_MAX) return -1; 1771530480 0 1771530480
if (file < 0 || file >= FN_COLS_MAX || rank < 0 || rank >= FN_ROWS_MAX) return -1; 1 1771530479 1771530480
93 1771530479 return (rank + 1) * FN_STRIDE + (file + 1);
94 }
95  
96 15271028161 static int in_grid(int sq)
97 {
98 int f, r;
99 15271028161 ▶ if (sq < 0 || sq >= FN_CELLS) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (sq < 0 || sq >= FN_CELLS) return 0; 15271028158 3 15271028161
if (sq < 0 || sq >= FN_CELLS) return 0; 5 15271028153 15271028158
100 15271028153 f = sq % FN_STRIDE;
101 15271028153 r = sq / FN_STRIDE;
102 15271028153 ▶ return f >= 1 && f <= FN_COLS_MAX && r >= 1 && r <= FN_ROWS_MAX;
Branch: 4 branches
BranchTrueFalseTotal
return f >= 1 && f <= FN_COLS_MAX && r >= 1 && r <= FN_ROWS_MAX; 15237486065 33542088 15271028153
return f >= 1 && f <= FN_COLS_MAX && r >= 1 && r <= FN_ROWS_MAX; 15198235753 39250312 15237486065
return f >= 1 && f <= FN_COLS_MAX && r >= 1 && r <= FN_ROWS_MAX; 15142734605 55501148 15198235753
return f >= 1 && f <= FN_COLS_MAX && r >= 1 && r <= FN_ROWS_MAX; 15080459273 62275332 15142734605
103 }
104  
105 5003422095 static int fn_file_of(int sq)
106 {
107 5003422095 ▶ if (!in_grid(sq)) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!in_grid(sq)) return -1; 2 5003422093 5003422095
108 5003422093 return (sq % FN_STRIDE) - 1;
109 }
110  
111 5003244831 static int fn_rank_of(int sq)
112 {
113 5003244831 ▶ if (!in_grid(sq)) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!in_grid(sq)) return -1; 1 5003244830 5003244831
114 5003244830 return (sq / FN_STRIDE) - 1;
115 }
116  
117 /* A STRONG POINT HAS DIAGONALS, and this is the one place that says which. */
118 453991278 static int fn_is_strong(int sq)
119 {
120 453991278 ▶ if (!in_grid(sq)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!in_grid(sq)) return 0; 1 453991277 453991278
121 453991277 return (fn_file_of(sq) + fn_rank_of(sq)) % 2 == 0;
122 }
123  
124 static const int DIR_OFFSET[FN_DIRS] = {
125 FN_STRIDE, FN_STRIDE + 1, 1, -FN_STRIDE + 1,
126 -FN_STRIDE, -FN_STRIDE - 1, -1, FN_STRIDE - 1
127 };
128  
129 225 static int fn_dir_opposite(int dir)
130 {
131 225 ▶ if (dir < 0 || dir >= FN_DIRS) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (dir < 0 || dir >= FN_DIRS) return -1; 225 0 225
if (dir < 0 || dir >= FN_DIRS) return -1; 1 224 225
132 224 return (dir + 4) % FN_DIRS;
133 }
134  
135 1116504531 static int fn_dir_is_diagonal(int dir)
136 {
137 1116504531 ▶ if (dir < 0 || dir >= FN_DIRS) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (dir < 0 || dir >= FN_DIRS) return 0; 1116504531 0 1116504531
if (dir < 0 || dir >= FN_DIRS) return 0; 0 1116504531 1116504531
138 1116504531 return dir % 2 == 1;
139 }
140  
141 /* ---- the size of one board ---------------------------------------------------- */
142  
143 1673186790 static int fn_cols(const struct fn_board *b) { return b->cols; }
144 202750979 static int fn_rows(const struct fn_board *b) { return b->rows; }
145 4 static int fn_points(const struct fn_board *b) { return b->cols * b->rows; }
146  
147 38 static int fn_centre(const struct fn_board *b)
148 {
149 38 return fn_square_of(b->cols / 2, b->rows / 2);
150 }
151  
152 4732681918 static int fn_on_board(const struct fn_board *b, int sq)
153 {
154 4732681918 ▶ if (!in_grid(sq)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!in_grid(sq)) return 0; 190568883 4542113035 4732681918
155 4542113035 ▶ return fn_file_of(sq) < b->cols && fn_rank_of(sq) < b->rows;
Branch: 2 branches
BranchTrueFalseTotal
return fn_file_of(sq) < b->cols && fn_rank_of(sq) < b->rows; 4541935892 177143 4542113035
return fn_file_of(sq) < b->cols && fn_rank_of(sq) < b->rows; 4541827081 108811 4541935892
156 }
157  
158 /* ---- the lines ---------------------------------------------------------------- */
159  
160 1116504318 static int fn_next(const struct fn_board *b, int sq, int dir)
161 {
162 int to;
163 1116504318 ▶ if (dir < 0 || dir >= FN_DIRS) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (dir < 0 || dir >= FN_DIRS) return -1; 1116504317 1 1116504318
if (dir < 0 || dir >= FN_DIRS) return -1; 1 1116504316 1116504317
164 1116504316 ▶ if (!fn_on_board(b, sq)) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!fn_on_board(b, sq)) return -1; 9 1116504307 1116504316
165 1116504307 ▶ if (fn_dir_is_diagonal(dir) && !fn_is_strong(sq)) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (fn_dir_is_diagonal(dir) && !fn_is_strong(sq)) return -1; 453990983 662513324 1116504307
if (fn_dir_is_diagonal(dir) && !fn_is_strong(sq)) return -1; 117921757 336069226 453990983
166 998582550 to = sq + DIR_OFFSET[dir];
167 998582550 ▶ return fn_on_board(b, to) ? to : -1;
Branch: 1 branch
BranchTrueFalseTotal
return fn_on_board(b, to) ? to : -1; 807728301 190854249 998582550
168 }
169  
170 12 static int fn_degree(const struct fn_board *b, int sq)
171 {
172 12 int d, n = 0;
173 108 ▶ for (d = 0; d < FN_DIRS; d++)
Branch: 1 branch
BranchTrueFalseTotal
for (d = 0; d < FN_DIRS; d++) 96 12 108
174 96 ▶ if (fn_next(b, sq, d) >= 0) n++;
Branch: 1 branch
BranchTrueFalseTotal
if (fn_next(b, sq, d) >= 0) n++; 61 35 96
175 12 return n;
176 }
177  
178 /* Each segment is found from its LOWER end, which is the end the four
179 * directions N, NE, E and NW climb or advance away from. SE is left out
180 * because a diagonal that descends is found from its other end as NW. */
181 12 static int fn_segments(const struct fn_board *b, int *out, int max)
182 {
183 static const int forward[4] = { FN_N, FN_NE, FN_E, FN_NW };
184 12 int rank, file, i, n = 0;
185 62 ▶ for (rank = 0; rank < b->rows; rank++) {
Branch: 1 branch
BranchTrueFalseTotal
for (rank = 0; rank < b->rows; rank++) { 50 12 62
186 366 ▶ for (file = 0; file < b->cols; file++) {
Branch: 1 branch
BranchTrueFalseTotal
for (file = 0; file < b->cols; file++) { 316 50 366
187 316 int sq = fn_square_of(file, rank);
188 1580 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 1264 316 1580
189 1264 int to = fn_next(b, sq, forward[i]);
190 1264 ▶ if (to < 0) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (to < 0) continue; 552 712 1264
191 712 ▶ if (out && n < max) {
Branch: 2 branches
BranchTrueFalseTotal
if (out && n < max) { 712 0 712
if (out && n < max) { 712 0 712
192 712 out[2 * n] = sq < to ? sq : to;
193 712 out[2 * n + 1] = sq < to ? to : sq;
194 }
195 712 n++;
196 }
197 }
198 }
199 12 return n;
200 }
201  
202 /* ---- the key ----------------------------------------------------------------
203 *
204 * The key covers the size of the board, the stones, their points, and the side
205 * to move, and NOTHING else, so a position repeating is a position repeating.
206 */
207  
208 70370665 static unsigned long long fn_zobrist(int stone, int sq)
209 {
210 70370665 zob_init();
211 70370665 ▶ if (!FN_IS_STONE(stone)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!FN_IS_STONE(stone)) return 0; 31899092 38471573 70370665
if (!FN_IS_STONE(stone)) return 0; 2 31899090 31899092
212 70370663 ▶ if (!in_grid(sq)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!in_grid(sq)) return 0; 1 70370662 70370663
213 70370662 return ZOB[stone][sq];
214 }
215  
216 34197887 static unsigned long long fn_zobrist_side(void)
217 {
218 34197887 zob_init();
219 34197887 return ZOB_SIDE;
220 }
221  
222 944972 static unsigned long long fn_zobrist_size(int cols, int rows)
223 {
224 944972 zob_init();
225 944972 ▶ if (!fn_size_ok(cols, rows)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!fn_size_ok(cols, rows)) return 0; 1 944971 944972
226 944971 return ZOB_SIZE[cols][rows];
227 }
228  
229 /* ---- structure, judging nothing ------------------------------------------------ */
230  
231 936962 static struct fn_board *fn_board_empty(int cols, int rows)
232 {
233 struct fn_board *b;
234 int rank, file;
235 936962 ▶ if (!fn_size_ok(cols, rows)) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!fn_size_ok(cols, rows)) return NULL; 0 936962 936962
236 936962 b = (struct fn_board *) malloc(sizeof(struct fn_board));
237 936962 ▶ if (!b) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return NULL; 0 936962 936962
238 936962 memset(b, 0, sizeof(struct fn_board));
239 936962 memset(b->cell, FN_BORDER, sizeof(b->cell));
240 936962 b->cols = cols;
241 936962 b->rows = rows;
242 5612690 ▶ for (rank = 0; rank < rows; rank++)
Branch: 1 branch
BranchTrueFalseTotal
for (rank = 0; rank < rows; rank++) 4675728 936962 5612690
243 46654622 ▶ for (file = 0; file < cols; file++)
Branch: 1 branch
BranchTrueFalseTotal
for (file = 0; file < cols; file++) 41978894 4675728 46654622
244 41978894 b->cell[fn_square_of(file, rank)] = FN_EMPTY;
245 936962 b->side = FN_WHITE;
246 936962 b->key = fn_zobrist_size(cols, rows);
247 936962 b->chain_at = -1;
248 936962 b->chain_dir = -1;
249 936962 FN_LIVE++;
250 936962 return b;
251 }
252  
253 70206730 static void fn_put(struct fn_board *b, int sq, int stone)
254 {
255 int old;
256 70206730 ▶ if (!fn_on_board(b, sq)) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!fn_on_board(b, sq)) return; 171 70206559 70206730
257 70206559 ▶ if (stone != FN_EMPTY && !FN_IS_STONE(stone)) return;
Branch: 3 branches
BranchTrueFalseTotal
if (stone != FN_EMPTY && !FN_IS_STONE(stone)) return; 36626425 33580134 70206559
if (stone != FN_EMPTY && !FN_IS_STONE(stone)) return; 16629354 19997071 36626425
if (stone != FN_EMPTY && !FN_IS_STONE(stone)) return; 2 16629352 16629354
258 70206557 old = b->cell[sq];
259 70206557 ▶ if (old != FN_EMPTY) {
Branch: 1 branch
BranchTrueFalseTotal
if (old != FN_EMPTY) { 33580824 36625733 70206557
260 33580824 b->key ^= fn_zobrist(old, sq);
261 33580824 b->stones[old]--;
262 }
263 70206557 b->cell[sq] = (unsigned char) stone;
264 70206557 ▶ if (stone != FN_EMPTY) {
Branch: 1 branch
BranchTrueFalseTotal
if (stone != FN_EMPTY) { 36626423 33580134 70206557
265 36626423 b->key ^= fn_zobrist(stone, sq);
266 36626423 b->stones[stone]++;
267 }
268 }
269  
270 33578215 static void fn_lift(struct fn_board *b, int sq)
271 {
272 33578215 fn_put(b, sq, FN_EMPTY);
273 33578215 }
274  
275 2533541713 static int fn_at(const struct fn_board *b, int sq)
276 {
277 2533541713 ▶ if (!fn_on_board(b, sq)) return FN_BORDER;
Branch: 1 branch
BranchTrueFalseTotal
if (!fn_on_board(b, sq)) return FN_BORDER; 204 2533541509 2533541713
278 2533541509 return b->cell[sq];
279 }
280  
281 82505009 static int fn_side(const struct fn_board *b) { return b->side; }
282  
283 35448871 static void fn_set_side(struct fn_board *b, int side)
284 {
285 35448871 ▶ if (!FN_IS_STONE(side)) return;
Branch: 2 branches
BranchTrueFalseTotal
if (!FN_IS_STONE(side)) return; 17638743 17810128 35448871
if (!FN_IS_STONE(side)) return; 1 17638742 17638743
286 35448870 ▶ if (side == b->side) return;
Branch: 1 branch
BranchTrueFalseTotal
if (side == b->side) return; 1254941 34193929 35448870
287 34193929 b->side = side;
288 34193929 b->key ^= fn_zobrist_side();
289 }
290  
291 15649611 static int fn_count(const struct fn_board *b, int stone)
292 {
293 15649611 ▶ if (!FN_IS_STONE(stone)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!FN_IS_STONE(stone)) return 0; 7878961 7770650 15649611
if (!FN_IS_STONE(stone)) return 0; 0 7878961 7878961
294 15649611 return b->stones[stone];
295 }
296  
297 25145421 static unsigned long long fn_key(const struct fn_board *b) { return b->key; }
298  
299 /* The key from nothing. A test holds the maintained key to it after every
300 * kind of change, which is the only way a missed update shows. */
301 8007 static unsigned long long fn_key_full(const struct fn_board *b)
302 {
303 8007 unsigned long long k = fn_zobrist_size(b->cols, b->rows);
304 int rank, file;
305 48042 ▶ for (rank = 0; rank < b->rows; rank++) {
Branch: 1 branch
BranchTrueFalseTotal
for (rank = 0; rank < b->rows; rank++) { 40035 8007 48042
306 400350 ▶ for (file = 0; file < b->cols; file++) {
Branch: 1 branch
BranchTrueFalseTotal
for (file = 0; file < b->cols; file++) { 360315 40035 400350
307 360315 int sq = fn_square_of(file, rank);
308 360315 int p = b->cell[sq];
309 360315 ▶ if (p != FN_EMPTY) k ^= fn_zobrist(p, sq);
Branch: 1 branch
BranchTrueFalseTotal
if (p != FN_EMPTY) k ^= fn_zobrist(p, sq); 163412 196903 360315
310 }
311 }
312 8007 ▶ if (b->side == FN_BLACK) k ^= fn_zobrist_side();
Branch: 1 branch
BranchTrueFalseTotal
if (b->side == FN_BLACK) k ^= fn_zobrist_side(); 3957 4050 8007
313 8007 return k;
314 }
315  
316 /* ---- the chain ------------------------------------------------------------------
317 *
318 * Which stone is in the middle of its move, the way it last went, and where it
319 * has stood. THE KEY DOES NOT COVER IT: a position is compared between moves,
320 * and between moves there is no chain. The rules that read it are fn_moves.c's;
321 * here it is three fields set together.
322 */
323  
324 7317376 static int fn_point_bit(int sq)
325 {
326 7317376 ▶ if (!in_grid(sq)) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!in_grid(sq)) return -1; 0 7317376 7317376
327 7317376 return fn_rank_of(sq) * FN_COLS_MAX + fn_file_of(sq);
328 }
329  
330 92309944 static int fn_chain_at(const struct fn_board *b) { return b->chain_at; }
331 18844873 ▶static int fn_chain_dir(const struct fn_board *b) { return b->chain_at < 0 ? -1 : b->chain_dir; }
Branch: 1 branch
BranchTrueFalseTotal
static int fn_chain_dir(const struct fn_board *b) { return b->chain_at < 0 ? -1 : b->chain_dir; } 4533461 14311412 18844873
332  
333 15196066 static unsigned long long fn_chain_mask(const struct fn_board *b)
334 {
335 15196066 ▶ return b->chain_at < 0 ? 0 : b->chain_seen;
Branch: 1 branch
BranchTrueFalseTotal
return b->chain_at < 0 ? 0 : b->chain_seen; 884656 14311410 15196066
336 }
337  
338 3118082 static int fn_chain_seen(const struct fn_board *b, int sq)
339 {
340 3118082 int bit = fn_point_bit(sq);
341 3118082 ▶ if (bit < 0 || b->chain_at < 0) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (bit < 0 || b->chain_at < 0) return 0; 3118082 0 3118082
if (bit < 0 || b->chain_at < 0) return 0; 90 3117992 3118082
342 3117992 return (int) ((b->chain_seen >> bit) & 1ULL);
343 }
344  
345 32460562 static void fn_chain_set(struct fn_board *b, int at, int dir, unsigned long long mask)
346 {
347 32460562 ▶ if (at < 0 || !fn_on_board(b, at)) {
Branch: 2 branches
BranchTrueFalseTotal
if (at < 0 || !fn_on_board(b, at)) { 3354017 29106545 32460562
if (at < 0 || !fn_on_board(b, at)) { 0 3354017 3354017
348 29106545 b->chain_at = -1;
349 29106545 b->chain_dir = -1;
350 29106545 b->chain_seen = 0;
351 29106545 return;
352 }
353 3354017 b->chain_at = at;
354 3354017 ▶ b->chain_dir = (dir >= 0 && dir < FN_DIRS) ? dir : -1;
Branch: 2 branches
BranchTrueFalseTotal
b->chain_dir = (dir >= 0 && dir < FN_DIRS) ? dir : -1; 3354017 0 3354017
b->chain_dir = (dir >= 0 && dir < FN_DIRS) ? dir : -1; 3354017 0 3354017
355 3354017 b->chain_seen = mask;
356 }
357  
358 /* ---- the set-up ---------------------------------------------------------------
359 *
360 * The rows below the middle are White's and the rows above it Black's. The
361 * middle row alternates OUTWARD from the centre, which is empty: the point
362 * directly left of the centre is White and the point directly right of it is
363 * Black. On the nine by five that is b w b w . b w b w.
364 */
365  
366 77807 static int setup_stone(int cols, int rows, int file, int rank)
367 {
368 77807 int mid_rank = rows / 2, mid_file = cols / 2, away;
369 77807 ▶ if (rank < mid_rank) return FN_WHITE;
Branch: 1 branch
BranchTrueFalseTotal
if (rank < mid_rank) return FN_WHITE; 30973 46834 77807
370 46834 ▶ if (rank > mid_rank) return FN_BLACK;
Branch: 1 branch
BranchTrueFalseTotal
if (rank > mid_rank) return FN_BLACK; 30973 15861 46834
371 15861 ▶ if (file == mid_file) return FN_EMPTY;
Branch: 1 branch
BranchTrueFalseTotal
if (file == mid_file) return FN_EMPTY; 1919 13942 15861
372 13942 ▶ if (file < mid_file) {
Branch: 1 branch
BranchTrueFalseTotal
if (file < mid_file) { 6971 6971 13942
373 6971 away = mid_file - file;
374 6971 ▶ return away % 2 == 1 ? FN_WHITE : FN_BLACK;
Branch: 1 branch
BranchTrueFalseTotal
return away % 2 == 1 ? FN_WHITE : FN_BLACK; 3593 3378 6971
375 }
376 6971 away = file - mid_file;
377 6971 ▶ return away % 2 == 1 ? FN_BLACK : FN_WHITE;
Branch: 1 branch
BranchTrueFalseTotal
return away % 2 == 1 ? FN_BLACK : FN_WHITE; 3593 3378 6971
378 }
379  
380 1919 static struct fn_board *fn_board_new(int cols, int rows)
381 {
382 1919 struct fn_board *b = fn_board_empty(cols, rows);
383 int rank, file;
384 1919 ▶ if (!b) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return NULL; 0 1919 1919
385 11160 ▶ for (rank = 0; rank < rows; rank++)
Branch: 1 branch
BranchTrueFalseTotal
for (rank = 0; rank < rows; rank++) 9241 1919 11160
386 87048 ▶ for (file = 0; file < cols; file++)
Branch: 1 branch
BranchTrueFalseTotal
for (file = 0; file < cols; file++) 77807 9241 87048
387 77807 fn_put(b, fn_square_of(file, rank), setup_stone(cols, rows, file, rank));
388 1919 return b;
389 }
390  
391 498352 static struct fn_board *fn_board_copy(const struct fn_board *b)
392 {
393 struct fn_board *n;
394 498352 ▶ if (!b) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return NULL; 0 498352 498352
395 498352 n = (struct fn_board *) malloc(sizeof(struct fn_board));
396 498352 ▶ if (!n) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return NULL; 0 498352 498352
397 498352 *n = *b;
398 498352 FN_LIVE++;
399 498352 return n;
400 }
401  
402 1435314 static void fn_board_drop(struct fn_board *b)
403 {
404 1435314 ▶ if (!b) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return; 0 1435314 1435314
405 1435314 FN_LIVE--;
406 1435314 free(b);
407 }
408  
409 12 static int fn_live(void) { return FN_LIVE; }
410  
411 /* ---- the position string ------------------------------------------------------
412 *
413 * bbbbbbbbb/bbbbbbbbb/bwbw1bwbw/wwwwwwwww/wwwwwwwww w
414 *
415 * Rows from the TOP rank down, `w` and `b`, a digit 1 to 9 for a run of empty
416 * points, `/` between rows, one space, and the side to move. The size of the
417 * board is read from the string: the number of rows and their width.
418 */
419  
420 938172 static struct fn_board *fn_board_of_string(const char *str, int *err)
421 {
422 struct fn_board *b;
423 const char *s, *end;
424 int width[FN_ROWS_MAX + 1];
425 938172 int nrows = 1, i, rank, file, cols, side;
426 938172 int code = FN_OK;
427 size_t len;
428  
429 938172 ▶ if (err) *err = FN_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = FN_OK; 938172 0 938172
430 938172 ▶ if (!str || !*str) { code = FN_POS_NULL; goto refused; }
Branch: 2 branches
BranchTrueFalseTotal
if (!str || !*str) { code = FN_POS_NULL; goto refused; } 938172 0 938172
if (!str || !*str) { code = FN_POS_NULL; goto refused; } 2 938170 938172
431 938170 len = strlen(str);
432 938170 ▶ if (len >= FN_POS_MAX) { code = FN_POS_LONG; goto refused; }
Branch: 1 branch
BranchTrueFalseTotal
if (len >= FN_POS_MAX) { code = FN_POS_LONG; goto refused; } 1 938169 938170
433  
434 14471708 ▶ for (end = str; *end && *end != ' '; end++) {
Branch: 2 branches
BranchTrueFalseTotal
for (end = str; *end && *end != ' '; end++) { 14471625 83 14471708
for (end = str; *end && *end != ' '; end++) { 13534753 936872 14471625
435 13534753 char c = *end;
436 13534753 ▶ if (c != 'w' && c != 'b' && c != '/' && !(c >= '1' && c <= '9')) {
Branch: 5 branches
BranchTrueFalseTotal
if (c != 'w' && c != 'b' && c != '/' && !(c >= '1' && c <= '9')) { 11914584 1620169 13534753
if (c != 'w' && c != 'b' && c != '/' && !(c >= '1' && c <= '9')) { 10451985 1462599 11914584
if (c != 'w' && c != 'b' && c != '/' && !(c >= '1' && c <= '9')) { 6713853 3738132 10451985
if (c != 'w' && c != 'b' && c != '/' && !(c >= '1' && c <= '9')) { 6713457 396 6713853
if (c != 'w' && c != 'b' && c != '/' && !(c >= '1' && c <= '9')) { 818 6712639 6713457
437 1214 code = FN_POS_LETTER;
438 1214 goto refused;
439 }
440 }
441  
442 14457395 ▶ for (s = str; s < end; s++)
Branch: 1 branch
BranchTrueFalseTotal
for (s = str; s < end; s++) 13520440 936955 14457395
443 13520440 ▶ if (*s == '/') nrows++;
Branch: 1 branch
BranchTrueFalseTotal
if (*s == '/') nrows++; 3736349 9784091 13520440
444 936955 ▶ if (nrows != 3 && nrows != 5) { code = FN_POS_ROWS; goto refused; }
Branch: 2 branches
BranchTrueFalseTotal
if (nrows != 3 && nrows != 5) { code = FN_POS_ROWS; goto refused; } 931771 5184 936955
if (nrows != 3 && nrows != 5) { code = FN_POS_ROWS; goto refused; } 749 931022 931771
445  
446 6553442 ▶ for (i = 0; i <= FN_ROWS_MAX; i++) width[i] = 0;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i <= FN_ROWS_MAX; i++) width[i] = 0; 5617236 936206 6553442
447 14443896 ▶ for (s = str, i = 0; s < end; s++) {
Branch: 1 branch
BranchTrueFalseTotal
for (s = str, i = 0; s < end; s++) { 13507690 936206 14443896
448 13507690 ▶ if (*s == '/') { i++; continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (*s == '/') { i++; continue; } 3734456 9773234 13507690
449 9773234 ▶ width[i] += (*s >= '1' && *s <= '9') ? (*s - '0') : 1;
Branch: 2 branches
BranchTrueFalseTotal
width[i] += (*s >= '1' && *s <= '9') ? (*s - '0') : 1; 9773234 0 9773234
width[i] += (*s >= '1' && *s <= '9') ? (*s - '0') : 1; 6708415 3064819 9773234
450 }
451 936206 cols = width[0];
452 4667314 ▶ for (i = 1; i < nrows; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i < nrows; i++) 3732544 934770 4667314
453 3732544 ▶ if (width[i] != cols) { code = FN_POS_WIDTH; goto refused; }
Branch: 1 branch
BranchTrueFalseTotal
if (width[i] != cols) { code = FN_POS_WIDTH; goto refused; } 1436 3731108 3732544
454 934770 ▶ if (!fn_size_ok(cols, nrows)) { code = FN_POS_WIDTH; goto refused; }
Branch: 1 branch
BranchTrueFalseTotal
if (!fn_size_ok(cols, nrows)) { code = FN_POS_WIDTH; goto refused; } 2 934768 934770
455  
456 934768 ▶ if (end[0] != ' ' || (end[1] != 'w' && end[1] != 'b') || end[2] != '\0') {
Branch: 4 branches
BranchTrueFalseTotal
if (end[0] != ' ' || (end[1] != 'w' && end[1] != 'b') || end[2] != '\0') { 934767 1 934768
if (end[0] != ' ' || (end[1] != 'w' && end[1] != 'b') || end[2] != '\0') { 454995 479772 934767
if (end[0] != ' ' || (end[1] != 'w' && end[1] != 'b') || end[2] != '\0') { 454848 147 454995
if (end[0] != ' ' || (end[1] != 'w' && end[1] != 'b') || end[2] != '\0') { 170 934450 934620
457 318 code = FN_POS_SIDE;
458 318 goto refused;
459 }
460 934450 ▶ side = end[1] == 'w' ? FN_WHITE : FN_BLACK;
Branch: 1 branch
BranchTrueFalseTotal
side = end[1] == 'w' ? FN_WHITE : FN_BLACK; 479636 454814 934450
461  
462 934450 b = fn_board_empty(cols, nrows);
463 934450 ▶ if (!b) { code = FN_POS_NULL; goto refused; }
Branch: 1 branch
BranchTrueFalseTotal
if (!b) { code = FN_POS_NULL; goto refused; } 0 934450 934450
464 934450 rank = nrows - 1;
465 934450 file = 0;
466 14404804 ▶ for (s = str; s < end; s++) {
Branch: 1 branch
BranchTrueFalseTotal
for (s = str; s < end; s++) { 13470354 934450 14404804
467 13470354 ▶ if (*s == '/') { rank--; file = 0; continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (*s == '/') { rank--; file = 0; continue; } 3729074 9741280 13470354
468 9741280 ▶ if (*s >= '1' && *s <= '9') { file += *s - '0'; continue; }
Branch: 2 branches
BranchTrueFalseTotal
if (*s >= '1' && *s <= '9') { file += *s - '0'; continue; } 9741280 0 9741280
if (*s >= '1' && *s <= '9') { file += *s - '0'; continue; } 6701929 3039351 9741280
469 3039351 ▶ fn_put(b, fn_square_of(file, rank), *s == 'w' ? FN_WHITE : FN_BLACK);
Branch: 1 branch
BranchTrueFalseTotal
fn_put(b, fn_square_of(file, rank), *s == 'w' ? FN_WHITE : FN_BLACK); 1601010 1438341 3039351
470 3039351 file++;
471 }
472 934450 fn_set_side(b, side);
473 934450 return b;
474  
475 3722 refused:
476 3722 ▶ if (err) *err = code;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = code; 3722 0 3722
477 3722 return NULL;
478 }
479  
480 /* Writes the string and returns its length, or -1 when `len` cannot hold it. */
481 2900443 static int fn_to_string(const struct fn_board *b, char *buf, int len)
482 {
483 char tmp[FN_POS_MAX];
484 2900443 int n = 0, rank, file, run;
485 17388644 ▶ for (rank = b->rows - 1; rank >= 0; rank--) {
Branch: 1 branch
BranchTrueFalseTotal
for (rank = b->rows - 1; rank >= 0; rank--) { 14488201 2900443 17388644
486 14488201 run = 0;
487 144725392 ▶ for (file = 0; file < b->cols; file++) {
Branch: 1 branch
BranchTrueFalseTotal
for (file = 0; file < b->cols; file++) { 130237191 14488201 144725392
488 130237191 int p = b->cell[fn_square_of(file, rank)];
489 130237191 ▶ if (p == FN_EMPTY) { run++; continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (p == FN_EMPTY) { run++; continue; } 121161217 9075974 130237191
490 9075974 ▶ if (run) { tmp[n++] = (char) ('0' + run); run = 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (run) { tmp[n++] = (char) ('0' + run); run = 0; } 7386133 1689841 9075974
491 9075974 ▶ tmp[n++] = p == FN_WHITE ? 'w' : 'b';
Branch: 1 branch
BranchTrueFalseTotal
tmp[n++] = p == FN_WHITE ? 'w' : 'b'; 4795955 4280019 9075974
492 }
493 14488201 ▶ if (run) tmp[n++] = (char) ('0' + run);
Branch: 1 branch
BranchTrueFalseTotal
if (run) tmp[n++] = (char) ('0' + run); 13486473 1001728 14488201
494 14488201 ▶ if (rank > 0) tmp[n++] = '/';
Branch: 1 branch
BranchTrueFalseTotal
if (rank > 0) tmp[n++] = '/'; 11587758 2900443 14488201
495 }
496 2900443 tmp[n++] = ' ';
497 2900443 ▶ tmp[n++] = b->side == FN_WHITE ? 'w' : 'b';
Branch: 1 branch
BranchTrueFalseTotal
tmp[n++] = b->side == FN_WHITE ? 'w' : 'b'; 1459763 1440680 2900443
498 2900443 ▶ if (!buf || len < n + 1) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (!buf || len < n + 1) return -1; 2900443 0 2900443
if (!buf || len < n + 1) return -1; 0 2900443 2900443
499 2900443 memcpy(buf, tmp, (size_t) n);
500 2900443 buf[n] = '\0';
501 2900443 return n;
502 }
503  
504 /* ---- the table ----------------------------------------------------------------
505 *
506 * fn_moves.c, fn_rules.c and fn_search.c install themselves into the table here. The two files call into each
507 * other and it terminates: FN_TABLE_READY is set before the installer runs, and
508 * fn_moves.c only reaches fn_abi_table from inside a function the installer
509 * has already handed over.
510 */
511  
512 static struct fn_abi FN_TABLE;
513 static int FN_TABLE_READY = 0;
514  
515 void fn_moves_install(struct fn_abi *t);
516 void fn_rules_install(struct fn_abi *t);
517 void fn_search_install(struct fn_abi *t);
518  
519 3661360168 const struct fn_abi *fn_abi_table(void)
520 {
521 3661360168 ▶ if (!FN_TABLE_READY) {
Branch: 1 branch
BranchTrueFalseTotal
if (!FN_TABLE_READY) { 43 3661360125 3661360168
522 43 zob_init();
523 43 FN_TABLE.abi_version = FN_ABI_VERSION;
524  
525 43 FN_TABLE.board_new = fn_board_new;
526 43 FN_TABLE.board_empty = fn_board_empty;
527 43 FN_TABLE.board_of_string = fn_board_of_string;
528 43 FN_TABLE.board_copy = fn_board_copy;
529 43 FN_TABLE.board_drop = fn_board_drop;
530 43 FN_TABLE.live = fn_live;
531  
532 43 FN_TABLE.at = fn_at;
533 43 FN_TABLE.put = fn_put;
534 43 FN_TABLE.lift = fn_lift;
535 43 FN_TABLE.side = fn_side;
536 43 FN_TABLE.set_side = fn_set_side;
537 43 FN_TABLE.count = fn_count;
538  
539 43 FN_TABLE.cols = fn_cols;
540 43 FN_TABLE.rows = fn_rows;
541 43 FN_TABLE.points = fn_points;
542 43 FN_TABLE.centre = fn_centre;
543 43 FN_TABLE.on_board = fn_on_board;
544  
545 43 FN_TABLE.key = fn_key;
546 43 FN_TABLE.key_full = fn_key_full;
547 43 FN_TABLE.zobrist = fn_zobrist;
548 43 FN_TABLE.zobrist_side = fn_zobrist_side;
549 43 FN_TABLE.zobrist_size = fn_zobrist_size;
550 43 FN_TABLE.to_string = fn_to_string;
551  
552 43 FN_TABLE.size_ok = fn_size_ok;
553 43 FN_TABLE.stride = fn_stride;
554 43 FN_TABLE.square_of = fn_square_of;
555 43 FN_TABLE.file_of = fn_file_of;
556 43 FN_TABLE.rank_of = fn_rank_of;
557 43 FN_TABLE.is_strong = fn_is_strong;
558 43 FN_TABLE.dir_opposite = fn_dir_opposite;
559 43 FN_TABLE.dir_is_diagonal = fn_dir_is_diagonal;
560  
561 43 FN_TABLE.next = fn_next;
562 43 FN_TABLE.degree = fn_degree;
563 43 FN_TABLE.segments = fn_segments;
564  
565 43 FN_TABLE.chain_at = fn_chain_at;
566 43 FN_TABLE.chain_dir = fn_chain_dir;
567 43 FN_TABLE.chain_seen = fn_chain_seen;
568 43 FN_TABLE.chain_mask = fn_chain_mask;
569 43 FN_TABLE.chain_set = fn_chain_set;
570 43 FN_TABLE.point_bit = fn_point_bit;
571  
572 43 FN_TABLE_READY = 1; /* before the installer, or it recurses */
573 43 fn_moves_install(&FN_TABLE);
574 43 fn_rules_install(&FN_TABLE);
575 43 fn_search_install(&FN_TABLE);
576 }
577 3661360168 return &FN_TABLE;
578 }
« fn_search.c ↑ Summary bin/fanorona »