ru_engine.c

filter: Statementstmt 100% 264 / 264 Branchbran 85.3% 239 / 280 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 92.4% 503 / 544 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« ru_search.c ↑ Summary bin/royalur »
1 /* ru_engine.c - the board of the Royal Game of Ur, and nothing that judges a move.
2 *
3 * PERL-FREE by design: see include/ru_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 twenty cells, the hands and the homes, the side to
7 * move, the two routes, the key, the position string in and out, and the
8 * chance of each roll. What a roll allows is ru_moves.c, which appends to the
9 * table.
10 */
11  
12 #include <stdlib.h>
13 #include <string.h>
14 #include "ru_abi.h"
15  
16 /* ---- the position ---------------------------------------------------------
17 *
18 * No pointers, so a copy is a struct assignment and two boards never share
19 * anything. THE HANDS ARE STORED AND NOT DERIVED: seven less the pieces on the
20 * board and at home would be right for a legal position and would make an
21 * illegal one impossible to build, and a test needs to build them.
22 */
23  
24 struct ru_board {
25 unsigned char cell[RU_CELLS];
26 int hand[2];
27 int home[2];
28 int side;
29 int ply;
30 };
31  
32 /* Boards handed out and not yet dropped. It exists so a test can show that a
33 * destructor ran exactly once; it is a plain int and is not synchronised. */
34 static int RU_LIVE = 0;
35  
36 /* ---- geometry ---------------------------------------------------------------
37 *
38 * Three rows of eight with four squares missing. The index is row by row and
39 * skips the gaps, and it is OPAQUE: nothing outside this file may rely on it.
40 */
41  
42 static const signed char CELL_AT[RU_ROWS][RU_FILES] = {
43 { 0, 1, 2, 3, -1, -1, 4, 5 },
44 { 6, 7, 8, 9, 10, 11, 12, 13 },
45 { 14, 15, 16, 17, -1, -1, 18, 19 }
46 };
47  
48 static const signed char FILE_AT[RU_CELLS] = {
49 0, 1, 2, 3, 6, 7,
50 0, 1, 2, 3, 4, 5, 6, 7,
51 0, 1, 2, 3, 6, 7
52 };
53  
54 static const signed char ROW_AT[RU_CELLS] = {
55 0, 0, 0, 0, 0, 0,
56 1, 1, 1, 1, 1, 1, 1, 1,
57 2, 2, 2, 2, 2, 2
58 };
59  
60 1869184 static int ru_cell_of(int file, int row)
61 {
62 1869184 ▶ if (file < 0 || file >= RU_FILES || row < 0 || row >= RU_ROWS) return -1;
Branch: 4 branches
BranchTrueFalseTotal
if (file < 0 || file >= RU_FILES || row < 0 || row >= RU_ROWS) return -1; 1869183 1 1869184
if (file < 0 || file >= RU_FILES || row < 0 || row >= RU_ROWS) return -1; 1869182 1 1869183
if (file < 0 || file >= RU_FILES || row < 0 || row >= RU_ROWS) return -1; 1869181 1 1869182
if (file < 0 || file >= RU_FILES || row < 0 || row >= RU_ROWS) return -1; 1 1869180 1869181
63 1869180 return CELL_AT[row][file];
64 }
65  
66 46444011 static int ru_file_of(int cell)
67 {
68 46444011 ▶ if (cell < 0 || cell >= RU_CELLS) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (cell < 0 || cell >= RU_CELLS) return -1; 46444010 1 46444011
if (cell < 0 || cell >= RU_CELLS) return -1; 2 46444008 46444010
69 46444008 return FILE_AT[cell];
70 }
71  
72 46444011 static int ru_row_of(int cell)
73 {
74 46444011 ▶ if (cell < 0 || cell >= RU_CELLS) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (cell < 0 || cell >= RU_CELLS) return -1; 46444009 2 46444011
if (cell < 0 || cell >= RU_CELLS) return -1; 1 46444008 46444009
75 46444008 return ROW_AT[cell];
76 }
77  
78 /* Five of them: the first and the seventh file of each outer row, and the
79 * fourth file of the middle row. */
80 43151759 static int ru_is_rosette(int cell)
81 {
82 43151759 int f = ru_file_of(cell), r = ru_row_of(cell);
83 43151759 ▶ if (f < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (f < 0) return 0; 2 43151757 43151759
84 43151757 ▶ if (r == 1) return f == 3;
Branch: 1 branch
BranchTrueFalseTotal
if (r == 1) return f == 3; 25190348 17961409 43151757
85 17961409 ▶ return f == 0 || f == 6;
Branch: 2 branches
BranchTrueFalseTotal
return f == 0 || f == 6; 13836526 4124883 17961409
return f == 0 || f == 6; 1764297 12072229 13836526
86 }
87  
88 /* ---- the routes ---------------------------------------------------------------
89 *
90 * LIGHT'S ROUTE IS WRITTEN OUT, as file and row, and dark's is light's with
91 * rows 1 and 3 exchanged, computed once and not typed twice. Both enter on the
92 * fourth file of their own row and walk toward the corner.
93 */
94  
95 static const signed char SHORT_LIGHT[14][2] = {
96 {3,0}, {2,0}, {1,0}, {0,0},
97 {0,1}, {1,1}, {2,1}, {3,1}, {4,1}, {5,1}, {6,1}, {7,1},
98 {7,0}, {6,0}
99 };
100  
101 static const signed char LONG_LIGHT[16][2] = {
102 {3,0}, {2,0}, {1,0}, {0,0},
103 {0,1}, {1,1}, {2,1}, {3,1}, {4,1}, {5,1}, {6,1},
104 {6,2}, {7,2}, {7,1}, {7,0}, {6,0}
105 };
106  
107 static int ROUTE_CELL[2][2][RU_ROUTE_MAX + 1];
108 static int ROUTE_STEP[2][2][RU_CELLS];
109 static int ROUTES_READY = 0;
110  
111 566578062 static int ru_route_len(int route)
112 {
113 566578062 ▶ if (route == RU_ROUTE_SHORT) return 14;
Branch: 1 branch
BranchTrueFalseTotal
if (route == RU_ROUTE_SHORT) return 14; 347588133 218989929 566578062
114 218989929 ▶ if (route == RU_ROUTE_LONG) return 16;
Branch: 1 branch
BranchTrueFalseTotal
if (route == RU_ROUTE_LONG) return 16; 218989927 2 218989929
115 2 return -1;
116 }
117  
118 1330645435 static void routes_init(void)
119 {
120 int route, side, step, c;
121 1330645435 ▶ if (ROUTES_READY) return;
Branch: 1 branch
BranchTrueFalseTotal
if (ROUTES_READY) return; 1330645362 73 1330645435
122 219 ▶ for (route = 0; route < 2; route++) {
Branch: 1 branch
BranchTrueFalseTotal
for (route = 0; route < 2; route++) { 146 73 219
123 146 ▶ const signed char (*light)[2] = (route == RU_ROUTE_LONG) ? LONG_LIGHT : SHORT_LIGHT;
Branch: 1 branch
BranchTrueFalseTotal
const signed char (*light)[2] = (route == RU_ROUTE_LONG) ? LONG_LIGHT : SHORT_LIGHT; 73 73 146
124 146 int len = ru_route_len(route);
125 438 ▶ for (side = 0; side < 2; side++) {
Branch: 1 branch
BranchTrueFalseTotal
for (side = 0; side < 2; side++) { 292 146 438
126 5256 ▶ for (step = 0; step <= RU_ROUTE_MAX; step++) ROUTE_CELL[route][side][step] = -1;
Branch: 1 branch
BranchTrueFalseTotal
for (step = 0; step <= RU_ROUTE_MAX; step++) ROUTE_CELL[route][side][step] = -1; 4964 292 5256
127 6132 ▶ for (c = 0; c < RU_CELLS; c++) ROUTE_STEP[route][side][c] = 0;
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < RU_CELLS; c++) ROUTE_STEP[route][side][c] = 0; 5840 292 6132
128 4672 ▶ for (step = 1; step <= len; step++) {
Branch: 1 branch
BranchTrueFalseTotal
for (step = 1; step <= len; step++) { 4380 292 4672
129 4380 int file = light[step - 1][0];
130 4380 int row = light[step - 1][1];
131 int cell;
132 4380 ▶ if (side == RU_SIDE_DARK) row = RU_ROWS - 1 - row;
Branch: 1 branch
BranchTrueFalseTotal
if (side == RU_SIDE_DARK) row = RU_ROWS - 1 - row; 2190 2190 4380
133 4380 cell = ru_cell_of(file, row);
134 4380 ROUTE_CELL[route][side][step] = cell;
135 4380 ▶ if (cell >= 0) ROUTE_STEP[route][side][cell] = step;
Branch: 1 branch
BranchTrueFalseTotal
if (cell >= 0) ROUTE_STEP[route][side][cell] = step; 4380 0 4380
136 }
137 }
138 }
139 73 ROUTES_READY = 1;
140 }
141  
142 524078401 static int ru_route_cell(int route, int side, int step)
143 {
144 524078401 routes_init();
145 524078401 ▶ if (route < 0 || route > 1 || side < 0 || side > 1) return -1;
Branch: 4 branches
BranchTrueFalseTotal
if (route < 0 || route > 1 || side < 0 || side > 1) return -1; 524078401 0 524078401
if (route < 0 || route > 1 || side < 0 || side > 1) return -1; 524078400 1 524078401
if (route < 0 || route > 1 || side < 0 || side > 1) return -1; 524078400 0 524078400
if (route < 0 || route > 1 || side < 0 || side > 1) return -1; 1 524078399 524078400
146 524078399 ▶ if (step < 1 || step > ru_route_len(route)) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (step < 1 || step > ru_route_len(route)) return -1; 524078391 8 524078399
if (step < 1 || step > ru_route_len(route)) return -1; 9 524078382 524078391
147 524078382 return ROUTE_CELL[route][side][step];
148 }
149  
150 /* The step a cell is FOR THAT SIDE, or 0 when the side's route does not visit
151 * it. On the long route the answer for one cell differs between the sides. */
152 806546126 static int ru_route_step(int route, int side, int cell)
153 {
154 806546126 routes_init();
155 806546126 ▶ if (route < 0 || route > 1 || side < 0 || side > 1) return 0;
Branch: 4 branches
BranchTrueFalseTotal
if (route < 0 || route > 1 || side < 0 || side > 1) return 0; 806546126 0 806546126
if (route < 0 || route > 1 || side < 0 || side > 1) return 0; 806546125 1 806546126
if (route < 0 || route > 1 || side < 0 || side > 1) return 0; 806546125 0 806546125
if (route < 0 || route > 1 || side < 0 || side > 1) return 0; 0 806546125 806546125
156 806546125 ▶ if (cell < 0 || cell >= RU_CELLS) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (cell < 0 || cell >= RU_CELLS) return 0; 806546123 2 806546125
if (cell < 0 || cell >= RU_CELLS) return 0; 1 806546122 806546123
157 806546122 return ROUTE_STEP[route][side][cell];
158 }
159  
160 /* On both sides' routes. NOT "the middle row": that is true of the short route
161 * and false of the long one, whose last five steps run through the far row. */
162 36837043 static int ru_route_shared(int route, int cell)
163 {
164 36837043 return ru_route_step(route, RU_SIDE_LIGHT, cell) > 0
165 36837043 ▶ && ru_route_step(route, RU_SIDE_DARK, cell) > 0;
Branch: 2 branches
BranchTrueFalseTotal
&& ru_route_step(route, RU_SIDE_DARK, cell) > 0; 25760946 11076097 36837043
&& ru_route_step(route, RU_SIDE_DARK, cell) > 0; 15883062 9877884 25760946
166 }
167  
168 /* ---- the board ------------------------------------------------------------- */
169  
170 20835 static int clamp_pieces(int n)
171 {
172 20835 ▶ if (n < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n < 0) return 0; 0 20835 20835
173 20835 ▶ if (n > RU_PIECES_MAX) return RU_PIECES_MAX;
Branch: 1 branch
BranchTrueFalseTotal
if (n > RU_PIECES_MAX) return RU_PIECES_MAX; 0 20835 20835
174 20835 return n;
175 }
176  
177 20835 static struct ru_board *ru_board_new(int pieces)
178 {
179 struct ru_board *b;
180 20835 routes_init();
181 20835 b = (struct ru_board *) malloc(sizeof(struct ru_board));
182 20835 ▶ if (!b) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return NULL; 0 20835 20835
183 20835 memset(b, 0, sizeof(*b));
184 20835 b->hand[RU_SIDE_LIGHT] = b->hand[RU_SIDE_DARK] = clamp_pieces(pieces);
185 20835 b->side = RU_SIDE_LIGHT;
186 20835 RU_LIVE++;
187 20835 return b;
188 }
189  
190 64400 static struct ru_board *ru_board_copy(const struct ru_board *b)
191 {
192 struct ru_board *n;
193 64400 ▶ if (!b) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return NULL; 0 64400 64400
194 64400 n = (struct ru_board *) malloc(sizeof(struct ru_board));
195 64400 ▶ if (!n) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return NULL; 0 64400 64400
196 64400 *n = *b;
197 64400 RU_LIVE++;
198 64400 return n;
199 }
200  
201 85235 static void ru_board_drop(struct ru_board *b)
202 {
203 85235 ▶ if (!b) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return; 0 85235 85235
204 85235 RU_LIVE--;
205 85235 free(b);
206 }
207  
208 12 static int ru_live(void) { return RU_LIVE; }
209  
210 528251085 static int ru_at(const struct ru_board *b, int cell)
211 {
212 528251085 ▶ if (cell < 0 || cell >= RU_CELLS) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (cell < 0 || cell >= RU_CELLS) return -1; 528251084 1 528251085
if (cell < 0 || cell >= RU_CELLS) return -1; 1 528251083 528251084
213 528251083 return b->cell[cell];
214 }
215  
216 /* A value that is not a piece or RU_EMPTY is ignored, and so is a cell that is
217 * not one. */
218 24251400 static void ru_put(struct ru_board *b, int cell, int piece)
219 {
220 24251400 ▶ if (cell < 0 || cell >= RU_CELLS) return;
Branch: 2 branches
BranchTrueFalseTotal
if (cell < 0 || cell >= RU_CELLS) return; 24251399 1 24251400
if (cell < 0 || cell >= RU_CELLS) return; 1 24251398 24251399
221 24251398 ▶ if (piece != RU_EMPTY && !RU_IS_PIECE(piece)) return;
Branch: 3 branches
BranchTrueFalseTotal
if (piece != RU_EMPTY && !RU_IS_PIECE(piece)) return; 12997993 11253405 24251398
if (piece != RU_EMPTY && !RU_IS_PIECE(piece)) return; 6571370 6426623 12997993
if (piece != RU_EMPTY && !RU_IS_PIECE(piece)) return; 2 6571368 6571370
222 24251396 b->cell[cell] = (unsigned char) piece;
223 }
224  
225 11246702 static void ru_lift(struct ru_board *b, int cell)
226 {
227 11246702 ru_put(b, cell, RU_EMPTY);
228 11246702 }
229  
230 15334874 static int ru_hand(const struct ru_board *b, int side)
231 {
232 15334874 ▶ if (side < 0 || side > 1) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (side < 0 || side > 1) return -1; 15334874 0 15334874
if (side < 0 || side > 1) return -1; 1 15334873 15334874
233 15334873 return b->hand[side];
234 }
235  
236 4714311 static void ru_set_hand(struct ru_board *b, int side, int n)
237 {
238 4714311 ▶ if (side < 0 || side > 1) return;
Branch: 2 branches
BranchTrueFalseTotal
if (side < 0 || side > 1) return; 4714311 0 4714311
if (side < 0 || side > 1) return; 1 4714310 4714311
239 4714310 ▶ if (n < 0 || n > RU_PIECES_MAX) return;
Branch: 2 branches
BranchTrueFalseTotal
if (n < 0 || n > RU_PIECES_MAX) return; 4714309 1 4714310
if (n < 0 || n > RU_PIECES_MAX) return; 1 4714308 4714309
240 4714308 b->hand[side] = n;
241 }
242  
243 40576427 static int ru_home(const struct ru_board *b, int side)
244 {
245 40576427 ▶ if (side < 0 || side > 1) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (side < 0 || side > 1) return -1; 40576426 1 40576427
if (side < 0 || side > 1) return -1; 0 40576426 40576426
246 40576426 return b->home[side];
247 }
248  
249 615640 static void ru_set_home(struct ru_board *b, int side, int n)
250 {
251 615640 ▶ if (side < 0 || side > 1) return;
Branch: 2 branches
BranchTrueFalseTotal
if (side < 0 || side > 1) return; 615640 0 615640
if (side < 0 || side > 1) return; 0 615640 615640
252 615640 ▶ if (n < 0 || n > RU_PIECES_MAX) return;
Branch: 2 branches
BranchTrueFalseTotal
if (n < 0 || n > RU_PIECES_MAX) return; 615640 0 615640
if (n < 0 || n > RU_PIECES_MAX) return; 1 615639 615640
253 615639 b->home[side] = n;
254 }
255  
256 13848395 static int ru_side(const struct ru_board *b) { return b->side; }
257  
258 13161095 static void ru_set_side(struct ru_board *b, int side)
259 {
260 13161095 ▶ if (side != RU_SIDE_LIGHT && side != RU_SIDE_DARK) return;
Branch: 2 branches
BranchTrueFalseTotal
if (side != RU_SIDE_LIGHT && side != RU_SIDE_DARK) return; 6561375 6599720 13161095
if (side != RU_SIDE_LIGHT && side != RU_SIDE_DARK) return; 1 6561374 6561375
261 13161094 b->side = side;
262 }
263  
264 /* The plies made to reach the position. It is carried by the board and is not
265 * part of the position: two boards that differ only in it have one key. */
266 16025407 static int ru_ply(const struct ru_board *b) { return b->ply; }
267  
268 14596936 static void ru_set_ply(struct ru_board *b, int ply)
269 {
270 14596936 ▶ if (ply < 0) return;
Branch: 1 branch
BranchTrueFalseTotal
if (ply < 0) return; 1 14596935 14596936
271 14596935 b->ply = ply;
272 }
273  
274 42739 static int ru_count(const struct ru_board *b, int side)
275 {
276 42739 int c, n = 0;
277 42739 ▶ if (side < 0 || side > 1) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (side < 0 || side > 1) return -1; 42739 0 42739
if (side < 0 || side > 1) return -1; 1 42738 42739
278 897498 ▶ for (c = 0; c < RU_CELLS; c++)
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < RU_CELLS; c++) 854760 42738 897498
279 854760 ▶ if (b->cell[c] == RU_PIECE_OF(side)) n++;
Branch: 1 branch
BranchTrueFalseTotal
if (b->cell[c] == RU_PIECE_OF(side)) n++; 131079 723681 854760
280 42738 return n;
281 }
282  
283 21367 static int ru_consistent(const struct ru_board *b, int n)
284 {
285 int side;
286 64091 ▶ for (side = 0; side < 2; side++)
Branch: 1 branch
BranchTrueFalseTotal
for (side = 0; side < 2; side++) 42730 21361 64091
287 42730 ▶ if (b->hand[side] + b->home[side] + ru_count(b, side) != n) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (b->hand[side] + b->home[side] + ru_count(b, side) != n) return 0; 6 42724 42730
288 21361 return 1;
289 }
290  
291 /* ---- the key ----------------------------------------------------------------
292 *
293 * EXACT, and recomputed every time: twenty cells at two bits, two homes at
294 * three, and the side to move. Forty-seven bits, no table and no collision.
295 * The hands are left out on purpose; see ru_abi.h.
296 */
297  
298 66820 static unsigned long long ru_key(const struct ru_board *b)
299 {
300 66820 unsigned long long k = 0;
301 int c;
302 1403220 ▶ for (c = 0; c < RU_CELLS; c++)
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < RU_CELLS; c++) 1336400 66820 1403220
303 1336400 k |= ((unsigned long long) (b->cell[c] & 3)) << (2 * c);
304 66820 k |= ((unsigned long long) (b->home[RU_SIDE_LIGHT] & 7)) << 40;
305 66820 k |= ((unsigned long long) (b->home[RU_SIDE_DARK] & 7)) << 43;
306 66820 k |= ((unsigned long long) (b->side & 1)) << 46;
307 66820 return k;
308 }
309  
310 /* ---- the position string ------------------------------------------------------
311 *
312 * Three rows, row 3 first, a slash between rows, a digit for a run of empty
313 * squares, an x for each square that does not exist, then the side to move,
314 * light's hand and home, and dark's hand and home:
315 *
316 * 4xx2/8/4xx2 l 7 0 7 0
317 *
318 * l is a light piece and d a dark one; the side is l or d.
319 *
320 * EVERY FIELD IS REQUIRED. Defaulting one would turn a string cut short into a
321 * position with a player to move and a full hand.
322 */
323  
324 43975 static int letter_piece(char c)
325 {
326 43975 switch (c) {
327 21539 case 'l': return RU_LIGHT;
328 22425 case 'd': return RU_DARK;
329 11 default: return -1;
330 }
331 }
332  
333 89 static struct ru_board *refuse(struct ru_board *b, int *err, int code)
334 {
335 89 ▶ if (err) *err = code;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = code; 89 0 89
336 89 ru_board_drop(b);
337 89 return NULL;
338 }
339  
340 8013 static struct ru_board *ru_board_of_string(const char *str, int *err)
341 {
342 struct ru_board *b;
343 8013 int row = RU_ROWS - 1, file = 0, field;
344 int value[4];
345 8013 const char *s = str;
346 size_t n;
347  
348 8013 ▶ if (err) *err = RU_OK;
Branch: 1 branch
BranchTrueFalseTotal
if (err) *err = RU_OK; 8013 0 8013
349 8013 ▶ if (!str) { if (err) *err = RU_POS_NULL; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!str) { if (err) *err = RU_POS_NULL; return NULL; } 0 8013 8013
if (!str) { if (err) *err = RU_POS_NULL; return NULL; } 0 0 0
350 8013 n = strlen(str);
351 8013 ▶ if (n == 0) { if (err) *err = RU_POS_NULL; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (n == 0) { if (err) *err = RU_POS_NULL; return NULL; } 3 8010 8013
if (n == 0) { if (err) *err = RU_POS_NULL; return NULL; } 3 0 3
352 8010 ▶ if (n >= RU_POS_MAX) { if (err) *err = RU_POS_LONG; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (n >= RU_POS_MAX) { if (err) *err = RU_POS_LONG; return NULL; } 2 8008 8010
if (n >= RU_POS_MAX) { if (err) *err = RU_POS_LONG; return NULL; } 2 0 2
353  
354 8008 b = ru_board_new(0);
355 8008 ▶ if (!b) { if (err) *err = RU_POS_NULL; return NULL; }
Branch: 2 branches
BranchTrueFalseTotal
if (!b) { if (err) *err = RU_POS_NULL; return NULL; } 0 8008 8008
if (!b) { if (err) *err = RU_POS_NULL; return NULL; } 0 0 0
356  
357 150477 ▶ for (; *s && *s != ' '; s++) {
Branch: 2 branches
BranchTrueFalseTotal
for (; *s && *s != ' '; s++) { 150473 4 150477
for (; *s && *s != ' '; s++) { 142513 7960 150473
358 142513 ▶ if (*s == '/') {
Branch: 1 branch
BranchTrueFalseTotal
if (*s == '/') { 15962 126551 142513
359 15962 ▶ if (file != RU_FILES) return refuse(b, err, RU_POS_WIDTH);
Branch: 1 branch
BranchTrueFalseTotal
if (file != RU_FILES) return refuse(b, err, RU_POS_WIDTH); 7 15955 15962
360 15955 ▶ if (row == 0) return refuse(b, err, RU_POS_ROWS);
Branch: 1 branch
BranchTrueFalseTotal
if (row == 0) return refuse(b, err, RU_POS_ROWS); 2 15953 15955
361 15953 row--; file = 0;
362 15953 continue;
363 }
364 126551 ▶ if (*s >= '1' && *s <= '8') {
Branch: 2 branches
BranchTrueFalseTotal
if (*s >= '1' && *s <= '8') { 126550 1 126551
if (*s >= '1' && *s <= '8') { 50668 75882 126550
365 50668 int run = *s - '0';
366 166264 ▶ while (run-- > 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (run-- > 0) { 115607 50657 166264
367 115607 ▶ if (file >= RU_FILES) return refuse(b, err, RU_POS_WIDTH);
Branch: 1 branch
BranchTrueFalseTotal
if (file >= RU_FILES) return refuse(b, err, RU_POS_WIDTH); 4 115603 115607
368 115603 ▶ if (ru_cell_of(file, row) < 0) return refuse(b, err, RU_POS_GAP);
Branch: 1 branch
BranchTrueFalseTotal
if (ru_cell_of(file, row) < 0) return refuse(b, err, RU_POS_GAP); 7 115596 115603
369 115596 file++;
370 }
371 50657 continue;
372 }
373 75883 ▶ if (*s == 'x') {
Branch: 1 branch
BranchTrueFalseTotal
if (*s == 'x') { 31908 43975 75883
374 31908 ▶ if (file >= RU_FILES) return refuse(b, err, RU_POS_WIDTH);
Branch: 1 branch
BranchTrueFalseTotal
if (file >= RU_FILES) return refuse(b, err, RU_POS_WIDTH); 0 31908 31908
375 31908 ▶ if (ru_cell_of(file, row) >= 0) return refuse(b, err, RU_POS_X);
Branch: 1 branch
BranchTrueFalseTotal
if (ru_cell_of(file, row) >= 0) return refuse(b, err, RU_POS_X); 7 31901 31908
376 31901 file++;
377 31901 continue;
378 }
379 {
380 43975 int piece = letter_piece(*s);
381 43975 ▶ if (piece < 0) return refuse(b, err, RU_POS_LETTER);
Branch: 1 branch
BranchTrueFalseTotal
if (piece < 0) return refuse(b, err, RU_POS_LETTER); 11 43964 43975
382 43964 ▶ if (file >= RU_FILES) return refuse(b, err, RU_POS_WIDTH);
Branch: 1 branch
BranchTrueFalseTotal
if (file >= RU_FILES) return refuse(b, err, RU_POS_WIDTH); 2 43962 43964
383 43962 ▶ if (ru_cell_of(file, row) < 0) return refuse(b, err, RU_POS_GAP);
Branch: 1 branch
BranchTrueFalseTotal
if (ru_cell_of(file, row) < 0) return refuse(b, err, RU_POS_GAP); 4 43958 43962
384 43958 ru_put(b, ru_cell_of(file, row), piece);
385 43958 file++;
386 }
387 }
388 7964 ▶ if (row != 0) return refuse(b, err, RU_POS_ROWS);
Branch: 1 branch
BranchTrueFalseTotal
if (row != 0) return refuse(b, err, RU_POS_ROWS); 6 7958 7964
389 7958 ▶ if (file != RU_FILES) return refuse(b, err, RU_POS_WIDTH);
Branch: 1 branch
BranchTrueFalseTotal
if (file != RU_FILES) return refuse(b, err, RU_POS_WIDTH); 1 7957 7958
390  
391 7957 ▶ if (*s != ' ') return refuse(b, err, RU_POS_FIELD);
Branch: 1 branch
BranchTrueFalseTotal
if (*s != ' ') return refuse(b, err, RU_POS_FIELD); 2 7955 7957
392 7955 s++;
393 7955 ▶ if (*s == 'l') ru_set_side(b, RU_SIDE_LIGHT);
Branch: 1 branch
BranchTrueFalseTotal
if (*s == 'l') ru_set_side(b, RU_SIDE_LIGHT); 4016 3939 7955
394 3939 ▶ else if (*s == 'd') ru_set_side(b, RU_SIDE_DARK);
Branch: 1 branch
BranchTrueFalseTotal
else if (*s == 'd') ru_set_side(b, RU_SIDE_DARK); 3932 7 3939
395 7 else return refuse(b, err, RU_POS_SIDE);
396 7948 s++;
397  
398 39670 ▶ for (field = 0; field < 4; field++) {
Branch: 1 branch
BranchTrueFalseTotal
for (field = 0; field < 4; field++) { 31747 7923 39670
399 31747 ▶ if (*s != ' ') return refuse(b, err, RU_POS_FIELD);
Branch: 1 branch
BranchTrueFalseTotal
if (*s != ' ') return refuse(b, err, RU_POS_FIELD); 10 31737 31747
400 31737 s++;
401 31737 ▶ if (*s == '\0') return refuse(b, err, RU_POS_FIELD);
Branch: 1 branch
BranchTrueFalseTotal
if (*s == '\0') return refuse(b, err, RU_POS_FIELD); 2 31735 31737
402 31735 ▶ if (*s < '0' || *s > '0' + RU_PIECES_MAX) return refuse(b, err, RU_POS_COUNT);
Branch: 2 branches
BranchTrueFalseTotal
if (*s < '0' || *s > '0' + RU_PIECES_MAX) return refuse(b, err, RU_POS_COUNT); 31732 3 31735
if (*s < '0' || *s > '0' + RU_PIECES_MAX) return refuse(b, err, RU_POS_COUNT); 5 31727 31732
403 31727 value[field] = *s - '0';
404 31727 s++;
405 31727 ▶ if (*s && *s != ' ') return refuse(b, err, RU_POS_COUNT);
Branch: 2 branches
BranchTrueFalseTotal
if (*s && *s != ' ') return refuse(b, err, RU_POS_COUNT); 23803 7924 31727
if (*s && *s != ' ') return refuse(b, err, RU_POS_COUNT); 5 23798 23803
406 }
407 7923 ▶ if (*s) return refuse(b, err, RU_POS_FIELD);
Branch: 1 branch
BranchTrueFalseTotal
if (*s) return refuse(b, err, RU_POS_FIELD); 4 7919 7923
408  
409 7919 ru_set_hand(b, RU_SIDE_LIGHT, value[0]);
410 7919 ru_set_home(b, RU_SIDE_LIGHT, value[1]);
411 7919 ru_set_hand(b, RU_SIDE_DARK, value[2]);
412 7919 ru_set_home(b, RU_SIDE_DARK, value[3]);
413  
414 7919 return b;
415 }
416  
417 64889 static int ru_to_string(const struct ru_board *b, char *buf, int len)
418 {
419 64889 int row, file, i = 0, run, side;
420 64889 ▶ if (!b || !buf || len < RU_POS_MAX) return -1;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || !buf || len < RU_POS_MAX) return -1; 64889 0 64889
if (!b || !buf || len < RU_POS_MAX) return -1; 64889 0 64889
if (!b || !buf || len < RU_POS_MAX) return -1; 0 64889 64889
421 259556 ▶ for (row = RU_ROWS - 1; row >= 0; row--) {
Branch: 1 branch
BranchTrueFalseTotal
for (row = RU_ROWS - 1; row >= 0; row--) { 194667 64889 259556
422 194667 run = 0;
423 1752003 ▶ for (file = 0; file < RU_FILES; file++) {
Branch: 1 branch
BranchTrueFalseTotal
for (file = 0; file < RU_FILES; file++) { 1557336 194667 1752003
424 1557336 int cell = ru_cell_of(file, row);
425 1557336 ▶ int piece = cell < 0 ? -1 : b->cell[cell];
Branch: 1 branch
BranchTrueFalseTotal
int piece = cell < 0 ? -1 : b->cell[cell]; 1297780 259556 1557336
426 1557336 ▶ if (piece == RU_EMPTY) { run++; continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (piece == RU_EMPTY) { run++; continue; } 919858 637478 1557336
427 637478 ▶ if (run) { buf[i++] = (char) ('0' + run); run = 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (run) { buf[i++] = (char) ('0' + run); run = 0; } 284511 352967 637478
428 637478 ▶ buf[i++] = piece < 0 ? 'x' : piece == RU_LIGHT ? 'l' : 'd';
Branch: 2 branches
BranchTrueFalseTotal
buf[i++] = piece < 0 ? 'x' : piece == RU_LIGHT ? 'l' : 'd'; 377922 259556 637478
buf[i++] = piece < 0 ? 'x' : piece == RU_LIGHT ? 'l' : 'd'; 188359 189563 377922
429 }
430 194667 ▶ if (run) buf[i++] = (char) ('0' + run);
Branch: 1 branch
BranchTrueFalseTotal
if (run) buf[i++] = (char) ('0' + run); 141889 52778 194667
431 194667 ▶ if (row) buf[i++] = '/';
Branch: 1 branch
BranchTrueFalseTotal
if (row) buf[i++] = '/'; 129778 64889 194667
432 }
433 64889 buf[i++] = ' ';
434 64889 ▶ buf[i++] = (b->side == RU_SIDE_DARK) ? 'd' : 'l';
Branch: 1 branch
BranchTrueFalseTotal
buf[i++] = (b->side == RU_SIDE_DARK) ? 'd' : 'l'; 32203 32686 64889
435 194667 ▶ for (side = 0; side < 2; side++) {
Branch: 1 branch
BranchTrueFalseTotal
for (side = 0; side < 2; side++) { 129778 64889 194667
436 129778 buf[i++] = ' ';
437 129778 buf[i++] = (char) ('0' + b->hand[side]);
438 129778 buf[i++] = ' ';
439 129778 buf[i++] = (char) ('0' + b->home[side]);
440 }
441 64889 buf[i] = '\0';
442 64889 return i;
443 }
444  
445 /* ---- the chance of a roll -----------------------------------------------------
446 *
447 * Each die is marked or not with equal chance, so the count of marked dice is
448 * binomial. A roll is the count, except that a count of nothing is worth
449 * `zero_rolls`. WHERE THAT IS FOUR AND THERE ARE FOUR DICE, a roll of four comes
450 * up two ways, from nothing marked and from everything marked, and its weight
451 * is 2.
452 *
453 * NOTHING HERE THROWS A DIE. These are the odds a search weighs.
454 */
455  
456 struct ru_chance { int roll; int weight; };
457  
458 static const struct ru_chance FOUR_ZERO_NOTHING[] = { {0,1}, {1,4}, {2,6}, {3,4}, {4,1} };
459 static const struct ru_chance FOUR_ZERO_FOUR[] = { {1,4}, {2,6}, {3,4}, {4,2} };
460 static const struct ru_chance THREE_ZERO_NOTHING[] = { {0,1}, {1,3}, {2,3}, {3,1} };
461 static const struct ru_chance THREE_ZERO_FOUR[] = { {1,3}, {2,3}, {3,1}, {4,1} };
462  
463 60386760 static const struct ru_chance *chance_table(int dice, int zero_rolls, int *count, int *denominator)
464 {
465 60386760 ▶ if (dice == 4 && zero_rolls == 0) { *count = 5; *denominator = 16; return FOUR_ZERO_NOTHING; }
Branch: 2 branches
BranchTrueFalseTotal
if (dice == 4 && zero_rolls == 0) { *count = 5; *denominator = 16; return FOUR_ZERO_NOTHING; } 38663550 21723210 60386760
if (dice == 4 && zero_rolls == 0) { *count = 5; *denominator = 16; return FOUR_ZERO_NOTHING; } 38663544 6 38663550
466 21723216 ▶ if (dice == 4 && zero_rolls == 4) { *count = 4; *denominator = 16; return FOUR_ZERO_FOUR; }
Branch: 2 branches
BranchTrueFalseTotal
if (dice == 4 && zero_rolls == 4) { *count = 4; *denominator = 16; return FOUR_ZERO_FOUR; } 6 21723210 21723216
if (dice == 4 && zero_rolls == 4) { *count = 4; *denominator = 16; return FOUR_ZERO_FOUR; } 5 1 6
467 21723211 ▶ if (dice == 3 && zero_rolls == 0) { *count = 4; *denominator = 8; return THREE_ZERO_NOTHING; }
Branch: 2 branches
BranchTrueFalseTotal
if (dice == 3 && zero_rolls == 0) { *count = 4; *denominator = 8; return THREE_ZERO_NOTHING; } 21723208 3 21723211
if (dice == 3 && zero_rolls == 0) { *count = 4; *denominator = 8; return THREE_ZERO_NOTHING; } 5 21723203 21723208
468 21723206 ▶ if (dice == 3 && zero_rolls == 4) { *count = 4; *denominator = 8; return THREE_ZERO_FOUR; }
Branch: 2 branches
BranchTrueFalseTotal
if (dice == 3 && zero_rolls == 4) { *count = 4; *denominator = 8; return THREE_ZERO_FOUR; } 21723203 3 21723206
if (dice == 3 && zero_rolls == 4) { *count = 4; *denominator = 8; return THREE_ZERO_FOUR; } 21723203 0 21723203
469 3 *count = 0; *denominator = 0;
470 3 return NULL;
471 }
472  
473 14121069 static int ru_chance_count(int dice, int zero_rolls)
474 {
475 int count, denominator;
476 14121069 chance_table(dice, zero_rolls, &count, &denominator);
477 14121069 return count;
478 }
479  
480 46265691 static int ru_chance(int dice, int zero_rolls, int i, int *roll, int *weight, int *denominator)
481 {
482 int count, den;
483 46265691 const struct ru_chance *table = chance_table(dice, zero_rolls, &count, &den);
484 46265691 ▶ if (!table || i < 0 || i >= count) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (!table || i < 0 || i >= count) return 0; 46265691 0 46265691
if (!table || i < 0 || i >= count) return 0; 46265691 0 46265691
if (!table || i < 0 || i >= count) return 0; 0 46265691 46265691
485 46265691 ▶ if (roll) *roll = table[i].roll;
Branch: 1 branch
BranchTrueFalseTotal
if (roll) *roll = table[i].roll; 46265691 0 46265691
486 46265691 ▶ if (weight) *weight = table[i].weight;
Branch: 1 branch
BranchTrueFalseTotal
if (weight) *weight = table[i].weight; 46265691 0 46265691
487 46265691 ▶ if (denominator) *denominator = den;
Branch: 1 branch
BranchTrueFalseTotal
if (denominator) *denominator = den; 46265691 0 46265691
488 46265691 return 1;
489 }
490  
491 /* ---- the table -------------------------------------------------------------- */
492  
493 static struct ru_abi RU_TABLE;
494 static int RU_TABLE_READY = 0;
495  
496 /* ru_moves.c installs itself into the table here. It reaches the board through
497 * the table and through nothing else. */
498 void ru_moves_install(struct ru_abi *t);
499 void ru_search_install(struct ru_abi *t);
500  
501 73 const struct ru_abi *ru_abi_table(void)
502 {
503 73 ▶ if (!RU_TABLE_READY) {
Branch: 1 branch
BranchTrueFalseTotal
if (!RU_TABLE_READY) { 73 0 73
504 73 routes_init();
505 73 RU_TABLE.abi_version = RU_ABI_VERSION;
506  
507 73 RU_TABLE.board_new = ru_board_new;
508 73 RU_TABLE.board_of_string = ru_board_of_string;
509 73 RU_TABLE.board_copy = ru_board_copy;
510 73 RU_TABLE.board_drop = ru_board_drop;
511 73 RU_TABLE.live = ru_live;
512  
513 73 RU_TABLE.at = ru_at;
514 73 RU_TABLE.put = ru_put;
515 73 RU_TABLE.lift = ru_lift;
516 73 RU_TABLE.hand = ru_hand;
517 73 RU_TABLE.set_hand = ru_set_hand;
518 73 RU_TABLE.home = ru_home;
519 73 RU_TABLE.set_home = ru_set_home;
520 73 RU_TABLE.side = ru_side;
521 73 RU_TABLE.set_side = ru_set_side;
522 73 RU_TABLE.count = ru_count;
523 73 RU_TABLE.consistent = ru_consistent;
524  
525 73 RU_TABLE.key = ru_key;
526 73 RU_TABLE.to_string = ru_to_string;
527  
528 73 RU_TABLE.cell_of = ru_cell_of;
529 73 RU_TABLE.file_of = ru_file_of;
530 73 RU_TABLE.row_of = ru_row_of;
531 73 RU_TABLE.is_rosette = ru_is_rosette;
532  
533 73 RU_TABLE.route_len = ru_route_len;
534 73 RU_TABLE.route_cell = ru_route_cell;
535 73 RU_TABLE.route_step = ru_route_step;
536 73 RU_TABLE.route_shared = ru_route_shared;
537  
538 73 RU_TABLE.chance_count = ru_chance_count;
539 73 RU_TABLE.chance = ru_chance;
540  
541 73 RU_TABLE.ply = ru_ply;
542 73 RU_TABLE.set_ply = ru_set_ply;
543  
544 73 RU_TABLE_READY = 1; /* before the installer, or it recurses */
545 73 ru_moves_install(&RU_TABLE);
546 73 ru_search_install(&RU_TABLE);
547 }
548 73 return &RU_TABLE;
549 }
« ru_search.c ↑ Summary bin/royalur »