1 /* $NetBSD: pickmove.c,v 1.68 2022/05/29 22:03:29 rillig Exp $ */
2
3 /*
4 * Copyright (c) 1994
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Ralph Campbell.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35 #include <sys/cdefs.h>
36 /* @(#)pickmove.c 8.2 (Berkeley) 5/3/95 */
37 __RCSID("$NetBSD: pickmove.c,v 1.68 2022/05/29 22:03:29 rillig Exp $");
38
39 #include <stdlib.h>
40 #include <string.h>
41 #include <curses.h>
42 #include <limits.h>
43
44 #include "gomoku.h"
45
46 #define BITS_PER_INT (sizeof(int) * CHAR_BIT)
47 #define MAPSZ (BAREA / BITS_PER_INT)
48
49 #define BIT_SET(a, b) ((a)[(b)/BITS_PER_INT] |= (1U << ((b) % BITS_PER_INT)))
50 #define BIT_TEST(a, b) (((a)[(b)/BITS_PER_INT] & (1U << ((b) % BITS_PER_INT))) != 0)
51
52 /*
53 * This structure is used to store overlap information between frames.
54 */
55 struct overlap_info {
56 spot_index o_intersect; /* intersection spot */
57 u_char o_off; /* offset in frame of intersection */
58 u_char o_frameindex; /* intersection frame index */
59 };
60
61 static struct combostr *hashcombos[FAREA];/* hash list for finding duplicates */
62 static struct combostr *sortcombos; /* combos at higher levels */
63 static int combolen; /* number of combos in sortcombos */
64 static player_color nextcolor; /* color of next move */
65 static int elistcnt; /* count of struct elist allocated */
66 static int combocnt; /* count of struct combostr allocated */
67 static unsigned int forcemap[MAPSZ]; /* map for blocking <1,x> combos */
68 static unsigned int tmpmap[MAPSZ]; /* map for blocking <1,x> combos */
69 static int nforce; /* count of opponent <1,x> combos */
70
71 static bool better(spot_index, spot_index, player_color);
72 static void scanframes(player_color);
73 static void makecombo2(struct combostr *, struct spotstr *, u_char, u_short);
74 static void addframes(unsigned int);
75 static void makecombo(struct combostr *, struct spotstr *, u_char, u_short);
76 static void appendcombo(struct combostr *);
77 static void updatecombo(struct combostr *, player_color);
78 static void makeempty(struct combostr *);
79 static int checkframes(struct combostr *, struct combostr *, struct spotstr *,
80 u_short, struct overlap_info *);
81 static bool sortcombo(struct combostr **, struct combostr **, struct combostr *);
82 #if !defined(DEBUG)
83 static void printcombo(struct combostr *, char *, size_t);
84 #endif
85
86 spot_index
pickmove(player_color us)87 pickmove(player_color us)
88 {
89
90 /* first move is easy */
91 if (game.nmoves == 0)
92 return PT((BSZ + 1) / 2, (BSZ + 1) / 2);
93
94 /* initialize all the board values */
95 for (spot_index s = PT(BSZ, BSZ) + 1; s-- > PT(1, 1); ) {
96 struct spotstr *sp = &board[s];
97 sp->s_combo[BLACK].s = 0x601;
98 sp->s_combo[WHITE].s = 0x601;
99 sp->s_level[BLACK] = 255;
100 sp->s_level[WHITE] = 255;
101 sp->s_nforce[BLACK] = 0;
102 sp->s_nforce[WHITE] = 0;
103 sp->s_flags &= ~(FFLAGALL | MFLAGALL);
104 }
105
106 nforce = 0;
107 memset(forcemap, 0, sizeof(forcemap));
108
109 /* compute new values */
110 player_color them = us != BLACK ? BLACK : WHITE;
111 nextcolor = us;
112 /*
113 * TODO: Scanning for both frames misses that after loading the game
114 * K10 J9 M10 J10 O10 J11 Q10 J8 and playing K9, there are 2
115 * immediate winning moves J12 and J7. Finding the winning move
116 * takes too long.
117 */
118 scanframes(BLACK);
119 scanframes(WHITE);
120
121 /* find the spot with the highest value */
122 spot_index os = PT(BSZ, BSZ); /* our spot */
123 spot_index ts = PT(BSZ, BSZ); /* their spot */
124 for (spot_index s = PT(BSZ, BSZ); s-- > PT(1, 1); ) {
125 const struct spotstr *sp = &board[s];
126 if (sp->s_occ != EMPTY)
127 continue;
128
129 if (debug > 0 &&
130 (sp->s_combo[BLACK].cv_force == 1 ||
131 sp->s_combo[WHITE].cv_force == 1)) {
132 debuglog("- %s %x/%d %d %x/%d %d %d",
133 stoc(s),
134 sp->s_combo[BLACK].s, sp->s_level[BLACK],
135 sp->s_nforce[BLACK],
136 sp->s_combo[WHITE].s, sp->s_level[WHITE],
137 sp->s_nforce[WHITE],
138 sp->s_wval);
139 }
140
141 if (better(s, os, us)) /* pick our best move */
142 os = s;
143 if (better(s, ts, them)) /* pick their best move */
144 ts = s;
145 }
146
147 if (debug > 0) {
148 spot_index bs = us == BLACK ? os : ts;
149 spot_index ws = us == BLACK ? ts : os;
150 const struct spotstr *bsp = &board[bs];
151 const struct spotstr *wsp = &board[ws];
152
153 debuglog("B %s %x/%d %d %x/%d %d %d",
154 stoc(bs),
155 bsp->s_combo[BLACK].s, bsp->s_level[BLACK],
156 bsp->s_nforce[BLACK],
157 bsp->s_combo[WHITE].s, bsp->s_level[WHITE],
158 bsp->s_nforce[WHITE], bsp->s_wval);
159 debuglog("W %s %x/%d %d %x/%d %d %d",
160 stoc(ws),
161 wsp->s_combo[WHITE].s, wsp->s_level[WHITE],
162 wsp->s_nforce[WHITE],
163 wsp->s_combo[BLACK].s, wsp->s_level[BLACK],
164 wsp->s_nforce[BLACK], wsp->s_wval);
165
166 /*
167 * Check for more than one force that can't all be blocked
168 * with one move.
169 */
170 if (board[ts].s_combo[them].cv_force == 1 &&
171 !BIT_TEST(forcemap, ts))
172 debuglog("*** Can't be blocked");
173 }
174
175 union comboval ocv = board[os].s_combo[us];
176 union comboval tcv = board[ts].s_combo[them];
177
178 /*
179 * Block their combo only if we have to (i.e., if they are one move
180 * away from completing a force, and we don't have a force that
181 * we can complete which takes fewer moves to win).
182 */
183 if (tcv.cv_force <= 1 &&
184 !(ocv.cv_force <= 1 &&
185 tcv.cv_force + tcv.cv_win >= ocv.cv_force + ocv.cv_win))
186 return ts;
187 return os;
188 }
189
190 /*
191 * Return true if spot 'as' is better than spot 'bs' for color 'us'.
192 */
193 static bool
better(spot_index as,spot_index bs,player_color us)194 better(spot_index as, spot_index bs, player_color us)
195 {
196 const struct spotstr *asp = &board[as];
197 const struct spotstr *bsp = &board[bs];
198
199 if (/* .... */ asp->s_combo[us].s != bsp->s_combo[us].s)
200 return asp->s_combo[us].s < bsp->s_combo[us].s;
201 if (/* .... */ asp->s_level[us] != bsp->s_level[us])
202 return asp->s_level[us] < bsp->s_level[us];
203 if (/* .... */ asp->s_nforce[us] != bsp->s_nforce[us])
204 return asp->s_nforce[us] > bsp->s_nforce[us];
205
206 player_color them = us != BLACK ? BLACK : WHITE;
207 if (BIT_TEST(forcemap, as) != BIT_TEST(forcemap, bs))
208 return BIT_TEST(forcemap, as);
209
210 if (/* .... */ asp->s_combo[them].s != bsp->s_combo[them].s)
211 return asp->s_combo[them].s < bsp->s_combo[them].s;
212 if (/* .... */ asp->s_level[them] != bsp->s_level[them])
213 return asp->s_level[them] < bsp->s_level[them];
214 if (/* .... */ asp->s_nforce[them] != bsp->s_nforce[them])
215 return asp->s_nforce[them] > bsp->s_nforce[them];
216
217 if (/* .... */ asp->s_wval != bsp->s_wval)
218 return asp->s_wval > bsp->s_wval;
219
220 return (random() & 1) != 0;
221 }
222
223 static player_color curcolor; /* implicit parameter to makecombo() */
224 static unsigned int curlevel; /* implicit parameter to makecombo() */
225
226 static bool
four_in_a_row(player_color color,spot_index s,direction r)227 four_in_a_row(player_color color, spot_index s, direction r)
228 {
229
230 struct spotstr *sp = &board[s];
231 union comboval cb = { .s = sp->s_fval[color][r].s };
232 if (cb.s >= 0x101)
233 return false;
234
235 for (int off = 5 + cb.cv_win, d = dd[r]; off-- > 0; sp += d) {
236 if (sp->s_occ != EMPTY)
237 continue;
238 sp->s_combo[color].s = cb.s;
239 sp->s_level[color] = 1;
240 }
241 return true;
242 }
243
244 /*
245 * Scan the sorted list of non-empty frames and
246 * update the minimum combo values for each empty spot.
247 * Also, try to combine frames to find more complex (chained) moves.
248 */
249 static void
scanframes(player_color color)250 scanframes(player_color color)
251 {
252 struct combostr *ecbp;
253 struct spotstr *sp;
254 union comboval *cp;
255 struct elist *nep;
256 int r, n;
257 union comboval cb;
258
259 curcolor = color;
260
261 /* check for empty list of frames */
262 struct combostr *cbp = sortframes[color];
263 if (cbp == NULL)
264 return;
265
266 if (four_in_a_row(color, cbp->c_vertex, cbp->c_dir))
267 return;
268
269 /*
270 * Update the minimum combo value for each spot in the frame
271 * and try making all combinations of two frames intersecting at
272 * an empty spot.
273 */
274 n = combolen;
275 ecbp = cbp;
276 do {
277 sp = &board[cbp->c_vertex];
278 cp = &sp->s_fval[color][r = cbp->c_dir];
279 int delta = dd[r];
280
281 u_char off;
282 if (cp->cv_win != 0) {
283 /*
284 * Since this is the first spot of an open-ended
285 * frame, we treat it as a closed frame.
286 */
287 cb.cv_force = cp->cv_force + 1;
288 cb.cv_win = 0;
289 if (cb.s < sp->s_combo[color].s) {
290 sp->s_combo[color].s = cb.s;
291 sp->s_level[color] = 1;
292 }
293 /*
294 * Try combining other frames that intersect
295 * at this spot.
296 */
297 makecombo2(cbp, sp, 0, cb.s);
298 if (cp->s != 0x101)
299 cb.s = cp->s;
300 else if (color != nextcolor)
301 memset(tmpmap, 0, sizeof(tmpmap));
302 sp += delta;
303 off = 1;
304 } else {
305 cb.s = cp->s;
306 off = 0;
307 }
308
309 for (; off < 5; off++, sp += delta) { /* for each spot */
310 if (sp->s_occ != EMPTY)
311 continue;
312 if (cp->s < sp->s_combo[color].s) {
313 sp->s_combo[color].s = cp->s;
314 sp->s_level[color] = 1;
315 }
316 if (cp->s == 0x101) {
317 sp->s_nforce[color]++;
318 if (color != nextcolor) {
319 /* XXX: suspicious use of 'n' */
320 n = (spot_index)(sp - board);
321 BIT_SET(tmpmap, (spot_index)n);
322 }
323 }
324 /*
325 * Try combining other frames that intersect
326 * at this spot.
327 */
328 makecombo2(cbp, sp, off, cb.s);
329 }
330
331 if (cp->s == 0x101 && color != nextcolor) {
332 if (nforce == 0)
333 memcpy(forcemap, tmpmap, sizeof(tmpmap));
334 else {
335 for (int i = 0; (unsigned int)i < MAPSZ; i++)
336 forcemap[i] &= tmpmap[i];
337 }
338 }
339
340 /* mark frame as having been processed */
341 board[cbp->c_vertex].s_flags |= MFLAG << r;
342 } while ((cbp = cbp->c_next) != ecbp);
343
344 /*
345 * Try to make new 3rd level combos, 4th level, etc.
346 * Limit the search depth early in the game.
347 */
348 for (unsigned int level = 2;
349 level <= 1 + game.nmoves / 2 && combolen > n; level++) {
350 if (level >= 9)
351 break; /* Do not think too long. */
352 if (debug > 0) {
353 debuglog("%cL%u %d %d %d", "BW"[color],
354 level, combolen - n, combocnt, elistcnt);
355 refresh();
356 }
357 n = combolen;
358 addframes(level);
359 }
360
361 /* scan for combos at empty spots */
362 for (spot_index s = PT(BSZ, BSZ) + 1; s-- > PT(1, 1); ) {
363 sp = &board[s];
364
365 for (struct elist *ep = sp->s_empty; ep != NULL; ep = nep) {
366 cbp = ep->e_combo;
367 if (cbp->c_combo.s <= sp->s_combo[color].s) {
368 if (cbp->c_combo.s != sp->s_combo[color].s) {
369 sp->s_combo[color].s = cbp->c_combo.s;
370 sp->s_level[color] = cbp->c_nframes;
371 } else if (cbp->c_nframes < sp->s_level[color])
372 sp->s_level[color] = cbp->c_nframes;
373 }
374 nep = ep->e_next;
375 free(ep);
376 elistcnt--;
377 }
378 sp->s_empty = NULL;
379
380 for (struct elist *ep = sp->s_nempty; ep != NULL; ep = nep) {
381 cbp = ep->e_combo;
382 if (cbp->c_combo.s <= sp->s_combo[color].s) {
383 if (cbp->c_combo.s != sp->s_combo[color].s) {
384 sp->s_combo[color].s = cbp->c_combo.s;
385 sp->s_level[color] = cbp->c_nframes;
386 } else if (cbp->c_nframes < sp->s_level[color])
387 sp->s_level[color] = cbp->c_nframes;
388 }
389 nep = ep->e_next;
390 free(ep);
391 elistcnt--;
392 }
393 sp->s_nempty = NULL;
394 }
395
396 /* remove old combos */
397 if ((cbp = sortcombos) != NULL) {
398 struct combostr *ncbp;
399
400 /* scan the list */
401 ecbp = cbp;
402 do {
403 ncbp = cbp->c_next;
404 free(cbp);
405 combocnt--;
406 } while ((cbp = ncbp) != ecbp);
407 sortcombos = NULL;
408 }
409 combolen = 0;
410
411 #ifdef DEBUG
412 if (combocnt != 0) {
413 debuglog("scanframes: %c combocnt %d", "BW"[color],
414 combocnt);
415 whatsup(0);
416 }
417 if (elistcnt != 0) {
418 debuglog("scanframes: %c elistcnt %d", "BW"[color],
419 elistcnt);
420 whatsup(0);
421 }
422 #endif
423 }
424
425 /*
426 * Compute all level 2 combos of frames intersecting spot 'osp'
427 * within the frame 'ocbp' and combo value 'cv'.
428 */
429 static void
makecombo2(struct combostr * ocbp,struct spotstr * osp,u_char off,u_short cv)430 makecombo2(struct combostr *ocbp, struct spotstr *osp, u_char off, u_short cv)
431 {
432 struct combostr *ncbp;
433 int baseB, fcnt, emask;
434 union comboval ocb, fcb;
435 struct combostr **scbpp, *fcbp;
436 char tmp[128];
437
438 /* try to combine a new frame with those found so far */
439 ocb.s = cv;
440 baseB = ocb.cv_force + ocb.cv_win - 1;
441 fcnt = ocb.cv_force - 2;
442 emask = fcnt != 0 ? ((ocb.cv_win != 0 ? 0x1E : 0x1F) & ~(1 << off)) : 0;
443
444 for (direction r = 4; r-- > 0; ) {
445 /* don't include frames that overlap in the same direction */
446 if (r == ocbp->c_dir)
447 continue;
448
449 int d = dd[r];
450 /*
451 * Frame A combined with B is the same value as B combined with A
452 * so skip frames that have already been processed (MFLAG).
453 * Also skip blocked frames (BFLAG) and frames that are <1,x>
454 * since combining another frame with it isn't valid.
455 */
456 int bmask = (BFLAG | FFLAG | MFLAG) << r;
457 struct spotstr *fsp = osp;
458
459 for (u_char f = 0; f < 5; f++, fsp -= d) { /* for each frame */
460 if (fsp->s_occ == BORDER)
461 break;
462 if ((fsp->s_flags & bmask) != 0)
463 continue;
464
465 /* don't include frames of the wrong color */
466 fcb.s = fsp->s_fval[curcolor][r].s;
467 if (fcb.cv_force >= 6)
468 continue;
469
470 /*
471 * Get the combo value for this frame.
472 * If this is the end point of the frame,
473 * use the closed ended value for the frame.
474 */
475 if ((f == 0 && fcb.cv_win != 0) || fcb.s == 0x101) {
476 fcb.cv_force++;
477 fcb.cv_win = 0;
478 }
479
480 /* compute combo value */
481 int c = fcb.cv_force + ocb.cv_force - 3;
482 if (c > 4)
483 continue;
484 int n = fcb.cv_force + fcb.cv_win - 1;
485 if (baseB < n)
486 n = baseB;
487
488 /* make a new combo! */
489 ncbp = (struct combostr *)malloc(sizeof(struct combostr) +
490 2 * sizeof(struct combostr *));
491 if (ncbp == NULL)
492 panic("Out of memory!");
493 scbpp = (void *)(ncbp + 1);
494
495 fcbp = &frames[fsp->s_frame[r]];
496 if (ocbp < fcbp) {
497 scbpp[0] = ocbp;
498 scbpp[1] = fcbp;
499 } else {
500 scbpp[0] = fcbp;
501 scbpp[1] = ocbp;
502 }
503
504 ncbp->c_combo.cv_force = c;
505 ncbp->c_combo.cv_win = n;
506 ncbp->c_link[0] = ocbp;
507 ncbp->c_link[1] = fcbp;
508 ncbp->c_linkv[0].s = ocb.s;
509 ncbp->c_linkv[1].s = fcb.s;
510 ncbp->c_voff[0] = off;
511 ncbp->c_voff[1] = f;
512 ncbp->c_vertex = (spot_index)(osp - board);
513 ncbp->c_nframes = 2;
514 ncbp->c_dir = 0;
515 ncbp->c_frameindex = 0;
516 ncbp->c_flags = ocb.cv_win != 0 ? C_OPEN_0 : 0;
517 if (fcb.cv_win != 0)
518 ncbp->c_flags |= C_OPEN_1;
519 ncbp->c_framecnt[0] = fcnt;
520 ncbp->c_emask[0] = emask;
521 ncbp->c_framecnt[1] = fcb.cv_force - 2;
522 ncbp->c_emask[1] = ncbp->c_framecnt[1] != 0 ?
523 ((fcb.cv_win != 0 ? 0x1E : 0x1F) & ~(1 << f)) : 0;
524 combocnt++;
525
526 if ((c == 1 && debug > 1) || debug > 3) {
527 debuglog("%c c %d %d m %x %x o %d %d",
528 "bw"[curcolor],
529 ncbp->c_framecnt[0], ncbp->c_framecnt[1],
530 ncbp->c_emask[0], ncbp->c_emask[1],
531 ncbp->c_voff[0], ncbp->c_voff[1]);
532 printcombo(ncbp, tmp, sizeof(tmp));
533 debuglog("%s", tmp);
534 }
535
536 if (c > 1) {
537 /* record the empty spots that will complete this combo */
538 makeempty(ncbp);
539
540 /* add the new combo to the end of the list */
541 appendcombo(ncbp);
542 } else {
543 updatecombo(ncbp, curcolor);
544 free(ncbp);
545 combocnt--;
546 }
547 #ifdef DEBUG
548 if ((c == 1 && debug > 1) || debug > 5) {
549 markcombo(ncbp);
550 bdisp();
551 whatsup(0);
552 clearcombo(ncbp, 0);
553 }
554 #endif /* DEBUG */
555 }
556 }
557 }
558
559 /*
560 * Scan the sorted list of frames and try to add a frame to
561 * combinations of 'level' number of frames.
562 */
563 static void
addframes(unsigned int level)564 addframes(unsigned int level)
565 {
566 struct combostr *cbp, *ecbp;
567 struct spotstr *fsp;
568 struct elist *nep;
569 int r;
570 struct combostr **cbpp, *pcbp;
571 union comboval fcb, cb;
572
573 curlevel = level;
574
575 /* scan for combos at empty spots */
576 player_color c = curcolor;
577 for (spot_index s = PT(BSZ, BSZ) + 1; s-- > PT(1, 1); ) {
578 struct spotstr *sp = &board[s];
579 for (struct elist *ep = sp->s_empty; ep != NULL; ep = nep) {
580 cbp = ep->e_combo;
581 if (cbp->c_combo.s <= sp->s_combo[c].s) {
582 if (cbp->c_combo.s != sp->s_combo[c].s) {
583 sp->s_combo[c].s = cbp->c_combo.s;
584 sp->s_level[c] = cbp->c_nframes;
585 } else if (cbp->c_nframes < sp->s_level[c])
586 sp->s_level[c] = cbp->c_nframes;
587 }
588 nep = ep->e_next;
589 free(ep);
590 elistcnt--;
591 }
592 sp->s_empty = sp->s_nempty;
593 sp->s_nempty = NULL;
594 }
595
596 /* try to add frames to the uncompleted combos at level curlevel */
597 cbp = ecbp = sortframes[curcolor];
598 do {
599 fsp = &board[cbp->c_vertex];
600 r = cbp->c_dir;
601 /* skip frames that are part of a <1,x> combo */
602 if ((fsp->s_flags & (FFLAG << r)) != 0)
603 continue;
604
605 /*
606 * Don't include <1,x> combo frames,
607 * treat it as a closed three in a row instead.
608 */
609 fcb.s = fsp->s_fval[curcolor][r].s;
610 if (fcb.s == 0x101)
611 fcb.s = 0x200;
612
613 /*
614 * If this is an open-ended frame, use
615 * the combo value with the end closed.
616 */
617 if (fsp->s_occ == EMPTY) {
618 if (fcb.cv_win != 0) {
619 cb.cv_force = fcb.cv_force + 1;
620 cb.cv_win = 0;
621 } else
622 cb.s = fcb.s;
623 makecombo(cbp, fsp, 0, cb.s);
624 }
625
626 /*
627 * The next four spots are handled the same for both
628 * open and closed ended frames.
629 */
630 int d = dd[r];
631 struct spotstr *sp = fsp + d;
632 for (u_char off = 1; off < 5; off++, sp += d) {
633 if (sp->s_occ != EMPTY)
634 continue;
635 makecombo(cbp, sp, off, fcb.s);
636 }
637 } while ((cbp = cbp->c_next) != ecbp);
638
639 /* put all the combos in the hash list on the sorted list */
640 cbpp = &hashcombos[FAREA];
641 do {
642 cbp = *--cbpp;
643 if (cbp == NULL)
644 continue;
645 *cbpp = NULL;
646 ecbp = sortcombos;
647 if (ecbp == NULL)
648 sortcombos = cbp;
649 else {
650 /* append to sort list */
651 pcbp = ecbp->c_prev;
652 pcbp->c_next = cbp;
653 ecbp->c_prev = cbp->c_prev;
654 cbp->c_prev->c_next = ecbp;
655 cbp->c_prev = pcbp;
656 }
657 } while (cbpp != hashcombos);
658 }
659
660 /*
661 * Compute all level N combos of frames intersecting spot 'osp'
662 * within the frame 'ocbp' and combo value 'cv'.
663 */
664 static void
makecombo(struct combostr * ocbp,struct spotstr * osp,u_char off,u_short cv)665 makecombo(struct combostr *ocbp, struct spotstr *osp, u_char off, u_short cv)
666 {
667 struct combostr *cbp;
668 struct spotstr *sp;
669 struct combostr **scbpp;
670 int baseB, fcnt, emask, verts;
671 union comboval ocb;
672 struct overlap_info ovi;
673 char tmp[128];
674
675 ocb.s = cv;
676 baseB = ocb.cv_force + ocb.cv_win - 1;
677 fcnt = ocb.cv_force - 2;
678 emask = fcnt != 0 ? ((ocb.cv_win != 0 ? 0x1E : 0x1F) & ~(1 << off)) : 0;
679 for (struct elist *ep = osp->s_empty; ep != NULL; ep = ep->e_next) {
680 /* check for various kinds of overlap */
681 cbp = ep->e_combo;
682 verts = checkframes(cbp, ocbp, osp, cv, &ovi);
683 if (verts < 0)
684 continue;
685
686 /* check to see if this frame forms a valid loop */
687 if (verts > 0) {
688 sp = &board[ovi.o_intersect];
689 #ifdef DEBUG
690 if (sp->s_occ != EMPTY) {
691 debuglog("loop: %c %s", "BW"[curcolor],
692 stoc((spot_index)(sp - board)));
693 whatsup(0);
694 }
695 #endif
696 /*
697 * It is a valid loop if the intersection spot
698 * of the frame we are trying to attach is one
699 * of the completion spots of the combostr
700 * we are trying to attach the frame to.
701 */
702 for (struct elist *nep = sp->s_empty;
703 nep != NULL; nep = nep->e_next) {
704 if (nep->e_combo == cbp)
705 goto fnd;
706 if (nep->e_combo->c_nframes < cbp->c_nframes)
707 break;
708 }
709 /* frame overlaps but not at a valid spot */
710 continue;
711 fnd:
712 ;
713 }
714
715 /* compute the first half of the combo value */
716 int c = cbp->c_combo.cv_force + ocb.cv_force - verts - 3;
717 if (c > 4)
718 continue;
719
720 /* compute the second half of the combo value */
721 int n = ep->e_fval.cv_force + ep->e_fval.cv_win - 1;
722 if (baseB < n)
723 n = baseB;
724
725 /* make a new combo! */
726 struct combostr *ncbp = malloc(sizeof(struct combostr) +
727 (cbp->c_nframes + 1) * sizeof(struct combostr *));
728 if (ncbp == NULL)
729 panic("Out of memory!");
730 scbpp = (void *)(ncbp + 1);
731 if (sortcombo(scbpp, (void *)(cbp + 1), ocbp)) {
732 free(ncbp);
733 continue;
734 }
735 combocnt++;
736
737 ncbp->c_combo.cv_force = c;
738 ncbp->c_combo.cv_win = n;
739 ncbp->c_link[0] = cbp;
740 ncbp->c_link[1] = ocbp;
741 ncbp->c_linkv[1].s = ocb.s;
742 ncbp->c_voff[1] = off;
743 ncbp->c_vertex = (spot_index)(osp - board);
744 ncbp->c_nframes = cbp->c_nframes + 1;
745 ncbp->c_flags = ocb.cv_win != 0 ? C_OPEN_1 : 0;
746 ncbp->c_frameindex = ep->e_frameindex;
747 /*
748 * Update the completion spot mask of the frame we
749 * are attaching 'ocbp' to so the intersection isn't
750 * listed twice.
751 */
752 ncbp->c_framecnt[0] = ep->e_framecnt;
753 ncbp->c_emask[0] = ep->e_emask;
754 if (verts != 0) {
755 ncbp->c_flags |= C_LOOP;
756 ncbp->c_dir = ovi.o_frameindex;
757 ncbp->c_framecnt[1] = fcnt - 1;
758 if (ncbp->c_framecnt[1] != 0) {
759 n = (ovi.o_intersect - ocbp->c_vertex) / dd[ocbp->c_dir];
760 ncbp->c_emask[1] = emask & ~(1 << n);
761 } else
762 ncbp->c_emask[1] = 0;
763 ncbp->c_voff[0] = ovi.o_off;
764 } else {
765 ncbp->c_dir = 0;
766 ncbp->c_framecnt[1] = fcnt;
767 ncbp->c_emask[1] = emask;
768 ncbp->c_voff[0] = ep->e_off;
769 }
770
771 if ((c == 1 && debug > 1) || debug > 3) {
772 debuglog("%c v%d i%d d%d c %d %d m %x %x o %d %d",
773 "bw"[curcolor], verts, ncbp->c_frameindex, ncbp->c_dir,
774 ncbp->c_framecnt[0], ncbp->c_framecnt[1],
775 ncbp->c_emask[0], ncbp->c_emask[1],
776 ncbp->c_voff[0], ncbp->c_voff[1]);
777 printcombo(ncbp, tmp, sizeof(tmp));
778 debuglog("%s", tmp);
779 }
780 if (c > 1) {
781 /* record the empty spots that will complete this combo */
782 makeempty(ncbp);
783 combolen++;
784 } else {
785 /* update board values */
786 updatecombo(ncbp, curcolor);
787 }
788 #ifdef DEBUG
789 if ((c == 1 && debug > 1) || debug > 4) {
790 markcombo(ncbp);
791 bdisp();
792 whatsup(0);
793 clearcombo(ncbp, 0);
794 }
795 #endif /* DEBUG */
796 }
797 }
798
799 #define MAXDEPTH 100
800 static struct elist einfo[MAXDEPTH];
801 static struct combostr *ecombo[MAXDEPTH]; /* separate from elist to save space */
802
803 /*
804 * Add the combostr 'ocbp' to the empty spots list for each empty spot
805 * in 'ocbp' that will complete the combo.
806 */
807 static void
makeempty(struct combostr * ocbp)808 makeempty(struct combostr *ocbp)
809 {
810 struct combostr *cbp, **cbpp;
811 struct elist *ep, *nep;
812 struct spotstr *sp;
813 int d, emask, i;
814 int nframes;
815 char tmp[128];
816
817 if (debug > 2) {
818 printcombo(ocbp, tmp, sizeof(tmp));
819 debuglog("E%c %s", "bw"[curcolor], tmp);
820 }
821
822 /* should never happen but check anyway */
823 if ((nframes = ocbp->c_nframes) >= MAXDEPTH)
824 return;
825
826 /*
827 * The lower level combo can be pointed to by more than one
828 * higher level 'struct combostr' so we can't modify the
829 * lower level. Therefore, higher level combos store the
830 * real mask of the lower level frame in c_emask[0] and the
831 * frame number in c_frameindex.
832 *
833 * First we traverse the tree from top to bottom and save the
834 * connection info. Then we traverse the tree from bottom to
835 * top overwriting lower levels with the newer emask information.
836 */
837 ep = &einfo[nframes];
838 cbpp = &ecombo[nframes];
839 for (cbp = ocbp; cbp->c_link[1] != NULL; cbp = cbp->c_link[0]) {
840 ep--;
841 ep->e_combo = cbp;
842 *--cbpp = cbp->c_link[1];
843 ep->e_off = cbp->c_voff[1];
844 ep->e_frameindex = cbp->c_frameindex;
845 ep->e_fval.s = cbp->c_linkv[1].s;
846 ep->e_framecnt = cbp->c_framecnt[1];
847 ep->e_emask = cbp->c_emask[1];
848 }
849 cbp = ep->e_combo;
850 ep--;
851 ep->e_combo = cbp;
852 *--cbpp = cbp->c_link[0];
853 ep->e_off = cbp->c_voff[0];
854 ep->e_frameindex = 0;
855 ep->e_fval.s = cbp->c_linkv[0].s;
856 ep->e_framecnt = cbp->c_framecnt[0];
857 ep->e_emask = cbp->c_emask[0];
858
859 /* now update the emask info */
860 int n = 0;
861 for (i = 2, ep += 2; i < nframes; i++, ep++) {
862 cbp = ep->e_combo;
863 nep = &einfo[ep->e_frameindex];
864 nep->e_framecnt = cbp->c_framecnt[0];
865 nep->e_emask = cbp->c_emask[0];
866
867 if ((cbp->c_flags & C_LOOP) != 0) {
868 n++;
869 /*
870 * Account for the fact that this frame connects
871 * to a previous one (thus forming a loop).
872 */
873 nep = &einfo[cbp->c_dir];
874 if (--nep->e_framecnt != 0)
875 nep->e_emask &= ~(1 << cbp->c_voff[0]);
876 else
877 nep->e_emask = 0;
878 }
879 }
880
881 /*
882 * We only need to update the emask values of "complete" loops
883 * to include the intersection spots.
884 */
885 if (n != 0 && ocbp->c_combo.cv_force == 2) {
886 /* process loops from the top down */
887 ep = &einfo[nframes];
888 do {
889 ep--;
890 cbp = ep->e_combo;
891 if ((cbp->c_flags & C_LOOP) == 0)
892 continue;
893
894 /*
895 * Update the emask values to include the
896 * intersection spots.
897 */
898 nep = &einfo[cbp->c_dir];
899 nep->e_framecnt = 1;
900 nep->e_emask = 1 << cbp->c_voff[0];
901 ep->e_framecnt = 1;
902 ep->e_emask = 1 << ep->e_off;
903 ep = &einfo[ep->e_frameindex];
904 do {
905 ep->e_framecnt = 1;
906 ep->e_emask = 1 << ep->e_off;
907 ep = &einfo[ep->e_frameindex];
908 } while (ep > nep);
909 } while (ep != einfo);
910 }
911
912 /* check all the frames for completion spots */
913 for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) {
914 /* skip this frame if there are no incomplete spots in it */
915 if ((emask = ep->e_emask) == 0)
916 continue;
917 cbp = *cbpp;
918 sp = &board[cbp->c_vertex];
919 d = dd[cbp->c_dir];
920 for (int off = 0, m = 1; off < 5; off++, sp += d, m <<= 1) {
921 if (sp->s_occ != EMPTY || (emask & m) == 0)
922 continue;
923
924 /* add the combo to the list of empty spots */
925 nep = (struct elist *)malloc(sizeof(struct elist));
926 if (nep == NULL)
927 panic("Out of memory!");
928 nep->e_combo = ocbp;
929 nep->e_off = off;
930 nep->e_frameindex = i;
931 if (ep->e_framecnt > 1) {
932 nep->e_framecnt = ep->e_framecnt - 1;
933 nep->e_emask = emask & ~m;
934 } else {
935 nep->e_framecnt = 0;
936 nep->e_emask = 0;
937 }
938 nep->e_fval.s = ep->e_fval.s;
939 if (debug > 2) {
940 debuglog("e %s o%d i%d c%d m%x %x",
941 stoc((spot_index)(sp - board)),
942 nep->e_off,
943 nep->e_frameindex,
944 nep->e_framecnt,
945 nep->e_emask,
946 nep->e_fval.s);
947 }
948
949 /* sort by the number of frames in the combo */
950 nep->e_next = sp->s_nempty;
951 sp->s_nempty = nep;
952 elistcnt++;
953 }
954 }
955 }
956
957 /*
958 * Update the board value based on the combostr.
959 * This is called only if 'cbp' is a <1,x> combo.
960 * We handle things differently depending on whether the next move
961 * would be trying to "complete" the combo or trying to block it.
962 */
963 static void
updatecombo(struct combostr * cbp,player_color color)964 updatecombo(struct combostr *cbp, player_color color)
965 {
966 struct combostr *tcbp;
967 union comboval cb;
968
969 int flags = 0;
970 /* save the top level value for the whole combo */
971 cb.cv_force = cbp->c_combo.cv_force;
972 u_char nframes = cbp->c_nframes;
973
974 if (color != nextcolor)
975 memset(tmpmap, 0, sizeof(tmpmap));
976
977 for (; (tcbp = cbp->c_link[1]) != NULL; cbp = cbp->c_link[0]) {
978 flags = cbp->c_flags;
979 cb.cv_win = cbp->c_combo.cv_win;
980 if (color == nextcolor) {
981 /* update the board value for the vertex */
982 struct spotstr *sp = &board[cbp->c_vertex];
983 sp->s_nforce[color]++;
984 if (cb.s <= sp->s_combo[color].s) {
985 if (cb.s != sp->s_combo[color].s) {
986 sp->s_combo[color].s = cb.s;
987 sp->s_level[color] = nframes;
988 } else if (nframes < sp->s_level[color])
989 sp->s_level[color] = nframes;
990 }
991 } else {
992 /* update the board values for each spot in frame */
993 spot_index s = tcbp->c_vertex;
994 struct spotstr *sp = &board[s];
995 int d = dd[tcbp->c_dir];
996 int off = (flags & C_OPEN_1) != 0 ? 6 : 5;
997 for (; --off >= 0; sp += d, s += d) {
998 if (sp->s_occ != EMPTY)
999 continue;
1000 sp->s_nforce[color]++;
1001 if (cb.s <= sp->s_combo[color].s) {
1002 if (cb.s != sp->s_combo[color].s) {
1003 sp->s_combo[color].s = cb.s;
1004 sp->s_level[color] = nframes;
1005 } else if (nframes < sp->s_level[color])
1006 sp->s_level[color] = nframes;
1007 }
1008 BIT_SET(tmpmap, s);
1009 }
1010 }
1011
1012 /* mark the frame as being part of a <1,x> combo */
1013 board[tcbp->c_vertex].s_flags |= FFLAG << tcbp->c_dir;
1014 }
1015
1016 if (color != nextcolor) {
1017 /* update the board values for each spot in frame */
1018 spot_index s = cbp->c_vertex;
1019 struct spotstr *sp = &board[s];
1020 int d = dd[cbp->c_dir];
1021 int off = (flags & C_OPEN_0) != 0 ? 6 : 5;
1022 for (; --off >= 0; sp += d, s += d) {
1023 if (sp->s_occ != EMPTY)
1024 continue;
1025 sp->s_nforce[color]++;
1026 if (cb.s <= sp->s_combo[color].s) {
1027 if (cb.s != sp->s_combo[color].s) {
1028 sp->s_combo[color].s = cb.s;
1029 sp->s_level[color] = nframes;
1030 } else if (nframes < sp->s_level[color])
1031 sp->s_level[color] = nframes;
1032 }
1033 BIT_SET(tmpmap, s);
1034 }
1035 if (nforce == 0)
1036 memcpy(forcemap, tmpmap, sizeof(tmpmap));
1037 else {
1038 for (int i = 0; (unsigned int)i < MAPSZ; i++)
1039 forcemap[i] &= tmpmap[i];
1040 }
1041 nforce++;
1042 }
1043
1044 /* mark the frame as being part of a <1,x> combo */
1045 board[cbp->c_vertex].s_flags |= FFLAG << cbp->c_dir;
1046 }
1047
1048 /*
1049 * Add combo to the end of the list.
1050 */
1051 static void
appendcombo(struct combostr * cbp)1052 appendcombo(struct combostr *cbp)
1053 {
1054 struct combostr *pcbp, *ncbp;
1055
1056 combolen++;
1057 ncbp = sortcombos;
1058 if (ncbp == NULL) {
1059 sortcombos = cbp;
1060 cbp->c_next = cbp;
1061 cbp->c_prev = cbp;
1062 return;
1063 }
1064 pcbp = ncbp->c_prev;
1065 cbp->c_next = ncbp;
1066 cbp->c_prev = pcbp;
1067 ncbp->c_prev = cbp;
1068 pcbp->c_next = cbp;
1069 }
1070
1071 /*
1072 * Return zero if it is valid to combine frame 'fcbp' with the frames
1073 * in 'cbp' and forms a linked chain of frames (i.e., a tree; no loops).
1074 * Return positive if combining frame 'fcbp' to the frames in 'cbp'
1075 * would form some kind of valid loop. Also return the intersection spot
1076 * in 'ovi' beside the known intersection at spot 'osp'.
1077 * Return -1 if 'fcbp' should not be combined with 'cbp'.
1078 * 'cv' is the combo value for frame 'fcbp'.
1079 */
1080 static int
checkframes(struct combostr * cbp,struct combostr * fcbp,struct spotstr * osp,u_short cv,struct overlap_info * ovi)1081 checkframes(struct combostr *cbp, struct combostr *fcbp, struct spotstr *osp,
1082 u_short cv, struct overlap_info *ovi)
1083 {
1084 struct combostr *tcbp, *lcbp;
1085 int ovbit, n, mask, flags, fcnt;
1086 union comboval cb;
1087 u_char *str;
1088
1089 lcbp = NULL;
1090 flags = 0;
1091
1092 cb.s = cv;
1093 fcnt = cb.cv_force - 2;
1094 int verts = 0;
1095 u_char myindex = cbp->c_nframes;
1096 n = (frame_index)(fcbp - frames) * FAREA;
1097 str = &overlap[n];
1098 spot_index *ip = &intersect[n];
1099 /*
1100 * ovbit == which overlap bit to test based on whether 'fcbp' is
1101 * an open or closed frame.
1102 */
1103 ovbit = cb.cv_win != 0 ? 2 : 0;
1104 for (; (tcbp = cbp->c_link[1]) != NULL;
1105 lcbp = cbp, cbp = cbp->c_link[0]) {
1106 if (tcbp == fcbp)
1107 return -1; /* fcbp is already included */
1108
1109 /* check for intersection of 'tcbp' with 'fcbp' */
1110 myindex--;
1111 mask = str[tcbp - frames];
1112 flags = cbp->c_flags;
1113 n = ovbit + ((flags & C_OPEN_1) != 0 ? 1 : 0);
1114 if ((mask & (1 << n)) != 0) {
1115 /*
1116 * The two frames are not independent if they
1117 * both lie in the same line and intersect at
1118 * more than one point.
1119 */
1120 if (tcbp->c_dir == fcbp->c_dir &&
1121 (mask & (0x10 << n)) != 0)
1122 return -1;
1123 /*
1124 * If this is not the spot we are attaching
1125 * 'fcbp' to, and it is a reasonable intersection
1126 * spot, then there might be a loop.
1127 */
1128 spot_index s = ip[tcbp - frames];
1129 if (osp != &board[s]) {
1130 /* check to see if this is a valid loop */
1131 if (verts != 0)
1132 return -1;
1133 if (fcnt == 0 || cbp->c_framecnt[1] == 0)
1134 return -1;
1135 /*
1136 * Check to be sure the intersection is not
1137 * one of the end points if it is an
1138 * open-ended frame.
1139 */
1140 if ((flags & C_OPEN_1) != 0 &&
1141 (s == tcbp->c_vertex ||
1142 s == tcbp->c_vertex + 5 * dd[tcbp->c_dir]))
1143 return -1; /* invalid overlap */
1144 if (cb.cv_win != 0 &&
1145 (s == fcbp->c_vertex ||
1146 s == fcbp->c_vertex + 5 * dd[fcbp->c_dir]))
1147 return -1; /* invalid overlap */
1148
1149 ovi->o_intersect = s;
1150 ovi->o_off =
1151 (s - tcbp->c_vertex) / dd[tcbp->c_dir];
1152 ovi->o_frameindex = myindex;
1153 verts++;
1154 }
1155 }
1156 n = ovbit + ((flags & C_OPEN_0) != 0 ? 1 : 0);
1157 }
1158 if (cbp == fcbp)
1159 return -1; /* fcbp is already included */
1160
1161 /* check for intersection of 'cbp' with 'fcbp' */
1162 mask = str[cbp - frames];
1163 if ((mask & (1 << n)) != 0) {
1164 /*
1165 * The two frames are not independent if they
1166 * both lie in the same line and intersect at
1167 * more than one point.
1168 */
1169 if (cbp->c_dir == fcbp->c_dir && (mask & (0x10 << n)) != 0)
1170 return -1;
1171 /*
1172 * If this is not the spot we are attaching
1173 * 'fcbp' to, and it is a reasonable intersection
1174 * spot, then there might be a loop.
1175 */
1176 spot_index s = ip[cbp - frames];
1177 if (osp != &board[s]) {
1178 /* check to see if this is a valid loop */
1179 if (verts != 0)
1180 return -1;
1181 if (fcnt == 0 || lcbp->c_framecnt[0] == 0)
1182 return -1;
1183 /*
1184 * Check to be sure the intersection is not
1185 * one of the end points if it is an open-ended
1186 * frame.
1187 */
1188 if ((flags & C_OPEN_0) != 0 &&
1189 (s == cbp->c_vertex ||
1190 s == cbp->c_vertex + 5 * dd[cbp->c_dir]))
1191 return -1; /* invalid overlap */
1192 if (cb.cv_win != 0 &&
1193 (s == fcbp->c_vertex ||
1194 s == fcbp->c_vertex + 5 * dd[fcbp->c_dir]))
1195 return -1; /* invalid overlap */
1196
1197 ovi->o_intersect = s;
1198 ovi->o_off = (s - cbp->c_vertex) / dd[cbp->c_dir];
1199 ovi->o_frameindex = 0;
1200 verts++;
1201 }
1202 }
1203 return verts;
1204 }
1205
1206 /*
1207 * Merge sort the frame 'fcbp' and the sorted list of frames 'cbpp' and
1208 * store the result in 'scbpp'. 'curlevel' is the size of the 'cbpp' array.
1209 * Return true if this list of frames is already in the hash list.
1210 * Otherwise, add the new combo to the hash list.
1211 */
1212 static bool
sortcombo(struct combostr ** scbpp,struct combostr ** cbpp,struct combostr * fcbp)1213 sortcombo(struct combostr **scbpp, struct combostr **cbpp,
1214 struct combostr *fcbp)
1215 {
1216 struct combostr **spp, **cpp;
1217 struct combostr *cbp, *ecbp;
1218 int inx;
1219
1220 #ifdef DEBUG
1221 if (debug > 3) {
1222 char buf[128];
1223 size_t pos;
1224
1225 debuglog("sortc: %s%c l%u", stoc(fcbp->c_vertex),
1226 pdir[fcbp->c_dir], curlevel);
1227 pos = 0;
1228 for (cpp = cbpp; cpp < cbpp + curlevel; cpp++) {
1229 snprintf(buf + pos, sizeof(buf) - pos, " %s%c",
1230 stoc((*cpp)->c_vertex), pdir[(*cpp)->c_dir]);
1231 pos += strlen(buf + pos);
1232 }
1233 debuglog("%s", buf);
1234 }
1235 #endif /* DEBUG */
1236
1237 /* first build the new sorted list */
1238 unsigned int n = curlevel + 1;
1239 spp = scbpp + n;
1240 cpp = cbpp + curlevel;
1241 do {
1242 cpp--;
1243 if (fcbp > *cpp) {
1244 *--spp = fcbp;
1245 do {
1246 *--spp = *cpp;
1247 } while (cpp-- != cbpp);
1248 goto inserted;
1249 }
1250 *--spp = *cpp;
1251 } while (cpp != cbpp);
1252 *--spp = fcbp;
1253 inserted:
1254
1255 /* now check to see if this list of frames has already been seen */
1256 cbp = hashcombos[inx = (frame_index)(*scbpp - frames)];
1257 if (cbp == NULL) {
1258 /*
1259 * Easy case, this list hasn't been seen.
1260 * Add it to the hash list.
1261 */
1262 fcbp = (void *)((char *)scbpp - sizeof(struct combostr));
1263 hashcombos[inx] = fcbp;
1264 fcbp->c_next = fcbp->c_prev = fcbp;
1265 return false;
1266 }
1267 ecbp = cbp;
1268 do {
1269 cbpp = (void *)(cbp + 1);
1270 cpp = cbpp + n;
1271 spp = scbpp + n;
1272 cbpp++; /* first frame is always the same */
1273 do {
1274 if (*--spp != *--cpp)
1275 goto next;
1276 } while (cpp != cbpp);
1277 /* we found a match */
1278 #ifdef DEBUG
1279 if (debug > 3) {
1280 char buf[128];
1281 size_t pos;
1282
1283 debuglog("sort1: n%u", n);
1284 pos = 0;
1285 for (cpp = scbpp; cpp < scbpp + n; cpp++) {
1286 snprintf(buf + pos, sizeof(buf) - pos, " %s%c",
1287 stoc((*cpp)->c_vertex),
1288 pdir[(*cpp)->c_dir]);
1289 pos += strlen(buf + pos);
1290 }
1291 debuglog("%s", buf);
1292 printcombo(cbp, buf, sizeof(buf));
1293 debuglog("%s", buf);
1294 cbpp--;
1295 pos = 0;
1296 for (cpp = cbpp; cpp < cbpp + n; cpp++) {
1297 snprintf(buf + pos, sizeof(buf) - pos, " %s%c",
1298 stoc((*cpp)->c_vertex),
1299 pdir[(*cpp)->c_dir]);
1300 pos += strlen(buf + pos);
1301 }
1302 debuglog("%s", buf);
1303 }
1304 #endif /* DEBUG */
1305 return true;
1306 next:
1307 ;
1308 } while ((cbp = cbp->c_next) != ecbp);
1309 /*
1310 * This list of frames hasn't been seen.
1311 * Add it to the hash list.
1312 */
1313 ecbp = cbp->c_prev;
1314 fcbp = (void *)((char *)scbpp - sizeof(struct combostr));
1315 fcbp->c_next = cbp;
1316 fcbp->c_prev = ecbp;
1317 cbp->c_prev = fcbp;
1318 ecbp->c_next = fcbp;
1319 return false;
1320 }
1321
1322 /*
1323 * Print the combo into string buffer 'buf'.
1324 */
1325 #if !defined(DEBUG)
1326 static
1327 #endif
1328 void
printcombo(struct combostr * cbp,char * buf,size_t max)1329 printcombo(struct combostr *cbp, char *buf, size_t max)
1330 {
1331 struct combostr *tcbp;
1332 size_t pos = 0;
1333
1334 snprintf(buf + pos, max - pos, "%x/%d",
1335 cbp->c_combo.s, cbp->c_nframes);
1336 pos += strlen(buf + pos);
1337
1338 for (; (tcbp = cbp->c_link[1]) != NULL; cbp = cbp->c_link[0]) {
1339 snprintf(buf + pos, max - pos, " %s%c%x",
1340 stoc(tcbp->c_vertex), pdir[tcbp->c_dir], cbp->c_flags);
1341 pos += strlen(buf + pos);
1342 }
1343 snprintf(buf + pos, max - pos, " %s%c",
1344 stoc(cbp->c_vertex), pdir[cbp->c_dir]);
1345 }
1346
1347 #ifdef DEBUG
1348 void
markcombo(struct combostr * ocbp)1349 markcombo(struct combostr *ocbp)
1350 {
1351 struct combostr *cbp, **cbpp;
1352 struct elist *ep, *nep;
1353 struct spotstr *sp;
1354 int d, m, i;
1355 int nframes;
1356 int cmask, omask;
1357
1358 /* should never happen but check anyway */
1359 if ((nframes = ocbp->c_nframes) >= MAXDEPTH)
1360 return;
1361
1362 /*
1363 * The lower level combo can be pointed to by more than one
1364 * higher level 'struct combostr' so we can't modify the
1365 * lower level. Therefore, higher level combos store the
1366 * real mask of the lower level frame in c_emask[0] and the
1367 * frame number in c_frameindex.
1368 *
1369 * First we traverse the tree from top to bottom and save the
1370 * connection info. Then we traverse the tree from bottom to
1371 * top overwriting lower levels with the newer emask information.
1372 */
1373 ep = &einfo[nframes];
1374 cbpp = &ecombo[nframes];
1375 for (cbp = ocbp; cbp->c_link[1] != NULL; cbp = cbp->c_link[0]) {
1376 ep--;
1377 ep->e_combo = cbp;
1378 *--cbpp = cbp->c_link[1];
1379 ep->e_off = cbp->c_voff[1];
1380 ep->e_frameindex = cbp->c_frameindex;
1381 ep->e_fval.s = cbp->c_linkv[1].s;
1382 ep->e_framecnt = cbp->c_framecnt[1];
1383 ep->e_emask = cbp->c_emask[1];
1384 }
1385 cbp = ep->e_combo;
1386 ep--;
1387 ep->e_combo = cbp;
1388 *--cbpp = cbp->c_link[0];
1389 ep->e_off = cbp->c_voff[0];
1390 ep->e_frameindex = 0;
1391 ep->e_fval.s = cbp->c_linkv[0].s;
1392 ep->e_framecnt = cbp->c_framecnt[0];
1393 ep->e_emask = cbp->c_emask[0];
1394
1395 /* now update the emask info */
1396 int n = 0;
1397 for (i = 2, ep += 2; i < nframes; i++, ep++) {
1398 cbp = ep->e_combo;
1399 nep = &einfo[ep->e_frameindex];
1400 nep->e_framecnt = cbp->c_framecnt[0];
1401 nep->e_emask = cbp->c_emask[0];
1402
1403 if ((cbp->c_flags & C_LOOP) != 0) {
1404 n++;
1405 /*
1406 * Account for the fact that this frame connects
1407 * to a previous one (thus forming a loop).
1408 */
1409 nep = &einfo[cbp->c_dir];
1410 if (--nep->e_framecnt != 0)
1411 nep->e_emask &= ~(1 << cbp->c_voff[0]);
1412 else
1413 nep->e_emask = 0;
1414 }
1415 }
1416
1417 /*
1418 * We only need to update the emask values of "complete" loops
1419 * to include the intersection spots.
1420 */
1421 if (n != 0 && ocbp->c_combo.cv_force == 2) {
1422 /* process loops from the top down */
1423 ep = &einfo[nframes];
1424 do {
1425 ep--;
1426 cbp = ep->e_combo;
1427 if ((cbp->c_flags & C_LOOP) == 0)
1428 continue;
1429
1430 /*
1431 * Update the emask values to include the
1432 * intersection spots.
1433 */
1434 nep = &einfo[cbp->c_dir];
1435 nep->e_framecnt = 1;
1436 nep->e_emask = 1 << cbp->c_voff[0];
1437 ep->e_framecnt = 1;
1438 ep->e_emask = 1 << ep->e_off;
1439 ep = &einfo[ep->e_frameindex];
1440 do {
1441 ep->e_framecnt = 1;
1442 ep->e_emask = 1 << ep->e_off;
1443 ep = &einfo[ep->e_frameindex];
1444 } while (ep > nep);
1445 } while (ep != einfo);
1446 }
1447
1448 /* mark all the frames with the completion spots */
1449 for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) {
1450 m = ep->e_emask;
1451 cbp = *cbpp;
1452 sp = &board[cbp->c_vertex];
1453 d = dd[cbp->c_dir];
1454 cmask = CFLAG << cbp->c_dir;
1455 omask = (IFLAG | CFLAG) << cbp->c_dir;
1456 int off = ep->e_fval.cv_win != 0 ? 6 : 5;
1457 /* LINTED 117: bitwise '>>' on signed value possibly nonportable */
1458 for (; --off >= 0; sp += d, m >>= 1)
1459 sp->s_flags |= (m & 1) != 0 ? omask : cmask;
1460 }
1461 }
1462
1463 void
clearcombo(struct combostr * cbp,int open)1464 clearcombo(struct combostr *cbp, int open)
1465 {
1466 struct combostr *tcbp;
1467
1468 for (; (tcbp = cbp->c_link[1]) != NULL; cbp = cbp->c_link[0]) {
1469 clearcombo(tcbp, cbp->c_flags & C_OPEN_1);
1470 open = cbp->c_flags & C_OPEN_0;
1471 }
1472
1473 struct spotstr *sp = &board[cbp->c_vertex];
1474 int d = dd[cbp->c_dir];
1475 int mask = ~((IFLAG | CFLAG) << cbp->c_dir);
1476 int n = open != 0 ? 6 : 5;
1477 for (; --n >= 0; sp += d)
1478 sp->s_flags &= mask;
1479 }
1480 #endif /* DEBUG */
1481