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