18af5b582Smckusick /*
28af5b582Smckusick * Copyright (c) 1994
38af5b582Smckusick * The Regents of the University of California. All rights reserved.
48af5b582Smckusick *
58af5b582Smckusick * This code is derived from software contributed to Berkeley by
68af5b582Smckusick * Ralph Campbell.
78af5b582Smckusick *
88af5b582Smckusick * %sccs.include.redist.c%
98af5b582Smckusick */
108af5b582Smckusick
118af5b582Smckusick #ifndef lint
12*ff46cf54Smckusick static char sccsid[] = "@(#)pickmove.c 8.2 (Berkeley) 05/03/95";
138af5b582Smckusick #endif /* not lint */
148af5b582Smckusick
158af5b582Smckusick #include <stdio.h>
168af5b582Smckusick #include <curses.h>
17*ff46cf54Smckusick #include <machine/limits.h>
188af5b582Smckusick
198af5b582Smckusick #include "gomoku.h"
208af5b582Smckusick
21*ff46cf54Smckusick #define BITS_PER_INT (sizeof(int) * CHAR_BIT)
22*ff46cf54Smckusick #define MAPSZ (BAREA / BITS_PER_INT)
238af5b582Smckusick
24*ff46cf54Smckusick #define BIT_SET(a, b) ((a)[(b)/BITS_PER_INT] |= (1 << ((b) % BITS_PER_INT)))
25*ff46cf54Smckusick #define BIT_CLR(a, b) ((a)[(b)/BITS_PER_INT] &= ~(1 << ((b) % BITS_PER_INT)))
26*ff46cf54Smckusick #define BIT_TEST(a, b) ((a)[(b)/BITS_PER_INT] & (1 << ((b) % BITS_PER_INT)))
27*ff46cf54Smckusick
28*ff46cf54Smckusick struct combostr *hashcombos[FAREA]; /* hash list for finding duplicates */
29*ff46cf54Smckusick struct combostr *sortcombos; /* combos at higher levels */
30*ff46cf54Smckusick int combolen; /* number of combos in sortcombos */
31*ff46cf54Smckusick int nextcolor; /* color of next move */
32*ff46cf54Smckusick int elistcnt; /* count of struct elist allocated */
33*ff46cf54Smckusick int combocnt; /* count of struct combostr allocated */
34*ff46cf54Smckusick int forcemap[MAPSZ]; /* map for blocking <1,x> combos */
35*ff46cf54Smckusick int tmpmap[MAPSZ]; /* map for blocking <1,x> combos */
36*ff46cf54Smckusick int nforce; /* count of opponent <1,x> combos */
378af5b582Smckusick
pickmove(us)388af5b582Smckusick pickmove(us)
398af5b582Smckusick int us;
408af5b582Smckusick {
418af5b582Smckusick register struct spotstr *sp, *sp1, *sp2;
42*ff46cf54Smckusick register union comboval *Ocp, *Tcp;
43*ff46cf54Smckusick char *str;
44*ff46cf54Smckusick int i, j, m;
458af5b582Smckusick
468af5b582Smckusick /* first move is easy */
478af5b582Smckusick if (movenum == 1)
488af5b582Smckusick return (PT(K,10));
498af5b582Smckusick
508af5b582Smckusick /* initialize all the board values */
518af5b582Smckusick for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
52*ff46cf54Smckusick sp->s_combo[BLACK].s = MAXCOMBO + 1;
53*ff46cf54Smckusick sp->s_combo[WHITE].s = MAXCOMBO + 1;
548af5b582Smckusick sp->s_level[BLACK] = 255;
558af5b582Smckusick sp->s_level[WHITE] = 255;
568af5b582Smckusick sp->s_nforce[BLACK] = 0;
578af5b582Smckusick sp->s_nforce[WHITE] = 0;
588af5b582Smckusick sp->s_flg &= ~(FFLAGALL | MFLAGALL);
598af5b582Smckusick }
60*ff46cf54Smckusick nforce = 0;
61*ff46cf54Smckusick memset(forcemap, 0, sizeof(forcemap));
628af5b582Smckusick
638af5b582Smckusick /* compute new values */
648af5b582Smckusick nextcolor = us;
658af5b582Smckusick scanframes(BLACK);
668af5b582Smckusick scanframes(WHITE);
678af5b582Smckusick
688af5b582Smckusick /* find the spot with the highest value */
698af5b582Smckusick for (sp = sp1 = sp2 = &board[PT(T,19)]; --sp >= &board[PT(A,1)]; ) {
708af5b582Smckusick if (sp->s_occ != EMPTY)
718af5b582Smckusick continue;
72*ff46cf54Smckusick if (debug && (sp->s_combo[BLACK].c.a == 1 ||
73*ff46cf54Smckusick sp->s_combo[WHITE].c.a == 1)) {
748af5b582Smckusick sprintf(fmtbuf, "- %s %x/%d %d %x/%d %d %d", stoc(sp - board),
758af5b582Smckusick sp->s_combo[BLACK].s, sp->s_level[BLACK],
768af5b582Smckusick sp->s_nforce[BLACK],
778af5b582Smckusick sp->s_combo[WHITE].s, sp->s_level[WHITE],
788af5b582Smckusick sp->s_nforce[WHITE],
798af5b582Smckusick sp->s_wval);
808af5b582Smckusick dlog(fmtbuf);
818af5b582Smckusick }
828af5b582Smckusick /* pick the best black move */
838af5b582Smckusick if (better(sp, sp1, BLACK))
848af5b582Smckusick sp1 = sp;
858af5b582Smckusick /* pick the best white move */
868af5b582Smckusick if (better(sp, sp2, WHITE))
878af5b582Smckusick sp2 = sp;
888af5b582Smckusick }
89*ff46cf54Smckusick
908af5b582Smckusick if (debug) {
918af5b582Smckusick sprintf(fmtbuf, "B %s %x/%d %d %x/%d %d %d %d",
928af5b582Smckusick stoc(sp1 - board),
938af5b582Smckusick sp1->s_combo[BLACK].s, sp1->s_level[BLACK],
948af5b582Smckusick sp1->s_nforce[BLACK],
958af5b582Smckusick sp1->s_combo[WHITE].s, sp1->s_level[WHITE],
96*ff46cf54Smckusick sp1->s_nforce[WHITE], sp1->s_wval);
978af5b582Smckusick dlog(fmtbuf);
988af5b582Smckusick sprintf(fmtbuf, "W %s %x/%d %d %x/%d %d %d %d",
998af5b582Smckusick stoc(sp2 - board),
1008af5b582Smckusick sp2->s_combo[WHITE].s, sp2->s_level[WHITE],
1018af5b582Smckusick sp2->s_nforce[WHITE],
1028af5b582Smckusick sp2->s_combo[BLACK].s, sp2->s_level[BLACK],
103*ff46cf54Smckusick sp2->s_nforce[BLACK], sp2->s_wval);
1048af5b582Smckusick dlog(fmtbuf);
105*ff46cf54Smckusick /*
106*ff46cf54Smckusick * Check for more than one force that can't
107*ff46cf54Smckusick * all be blocked with one move.
108*ff46cf54Smckusick */
109*ff46cf54Smckusick sp = (us == BLACK) ? sp2 : sp1;
110*ff46cf54Smckusick m = sp - board;
111*ff46cf54Smckusick if (sp->s_combo[!us].c.a == 1 && !BIT_TEST(forcemap, m))
112*ff46cf54Smckusick dlog("*** Can't be blocked");
1138af5b582Smckusick }
1148af5b582Smckusick if (us == BLACK) {
1158af5b582Smckusick Ocp = &sp1->s_combo[BLACK];
1168af5b582Smckusick Tcp = &sp2->s_combo[WHITE];
1178af5b582Smckusick } else {
1188af5b582Smckusick Tcp = &sp1->s_combo[BLACK];
1198af5b582Smckusick Ocp = &sp2->s_combo[WHITE];
1208af5b582Smckusick sp = sp1;
1218af5b582Smckusick sp1 = sp2;
1228af5b582Smckusick sp2 = sp;
1238af5b582Smckusick }
1248af5b582Smckusick /*
1258af5b582Smckusick * Block their combo only if we have to (i.e., if they are one move
1268af5b582Smckusick * away from completing a force and we don't have a force that
1278af5b582Smckusick * we can complete which takes fewer moves to win).
1288af5b582Smckusick */
1298af5b582Smckusick if (Tcp->c.a <= 1 && (Ocp->c.a > 1 ||
1308af5b582Smckusick Tcp->c.a + Tcp->c.b < Ocp->c.a + Ocp->c.b))
1318af5b582Smckusick return (sp2 - board);
1328af5b582Smckusick return (sp1 - board);
1338af5b582Smckusick }
1348af5b582Smckusick
1358af5b582Smckusick /*
1368af5b582Smckusick * Return true if spot 'sp' is better than spot 'sp1' for color 'us'.
1378af5b582Smckusick */
1388af5b582Smckusick better(sp, sp1, us)
1398af5b582Smckusick struct spotstr *sp;
1408af5b582Smckusick struct spotstr *sp1;
1418af5b582Smckusick int us;
1428af5b582Smckusick {
143*ff46cf54Smckusick int them, s, s1;
1448af5b582Smckusick
1458af5b582Smckusick if (sp->s_combo[us].s < sp1->s_combo[us].s)
1468af5b582Smckusick return (1);
1478af5b582Smckusick if (sp->s_combo[us].s != sp1->s_combo[us].s)
1488af5b582Smckusick return (0);
1498af5b582Smckusick if (sp->s_level[us] < sp1->s_level[us])
1508af5b582Smckusick return (1);
1518af5b582Smckusick if (sp->s_level[us] != sp1->s_level[us])
1528af5b582Smckusick return (0);
1538af5b582Smckusick if (sp->s_nforce[us] > sp1->s_nforce[us])
1548af5b582Smckusick return (1);
1558af5b582Smckusick if (sp->s_nforce[us] != sp1->s_nforce[us])
1568af5b582Smckusick return (0);
1578af5b582Smckusick
1588af5b582Smckusick them = !us;
159*ff46cf54Smckusick s = sp - board;
160*ff46cf54Smckusick s1 = sp1 - board;
161*ff46cf54Smckusick if (BIT_TEST(forcemap, s) && !BIT_TEST(forcemap, s1))
162*ff46cf54Smckusick return (1);
163*ff46cf54Smckusick if (!BIT_TEST(forcemap, s) && BIT_TEST(forcemap, s1))
164*ff46cf54Smckusick return (0);
1658af5b582Smckusick if (sp->s_combo[them].s < sp1->s_combo[them].s)
1668af5b582Smckusick return (1);
1678af5b582Smckusick if (sp->s_combo[them].s != sp1->s_combo[them].s)
1688af5b582Smckusick return (0);
1698af5b582Smckusick if (sp->s_level[them] < sp1->s_level[them])
1708af5b582Smckusick return (1);
1718af5b582Smckusick if (sp->s_level[them] != sp1->s_level[them])
1728af5b582Smckusick return (0);
1738af5b582Smckusick if (sp->s_nforce[them] > sp1->s_nforce[them])
1748af5b582Smckusick return (1);
1758af5b582Smckusick if (sp->s_nforce[them] != sp1->s_nforce[them])
1768af5b582Smckusick return (0);
1778af5b582Smckusick
1788af5b582Smckusick if (sp->s_wval > sp1->s_wval)
1798af5b582Smckusick return (1);
1808af5b582Smckusick if (sp->s_wval != sp1->s_wval)
1818af5b582Smckusick return (0);
1828af5b582Smckusick
1838af5b582Smckusick #ifdef SVR4
1848af5b582Smckusick return (rand() & 1);
1858af5b582Smckusick #else
1868af5b582Smckusick return (random() & 1);
1878af5b582Smckusick #endif
1888af5b582Smckusick }
1898af5b582Smckusick
1908af5b582Smckusick int curcolor; /* implicit parameter to makecombo() */
1918af5b582Smckusick int curlevel; /* implicit parameter to makecombo() */
1928af5b582Smckusick
1938af5b582Smckusick /*
194*ff46cf54Smckusick * Scan the sorted list of non-empty frames and
195*ff46cf54Smckusick * update the minimum combo values for each empty spot.
196*ff46cf54Smckusick * Also, try to combine frames to find more complex (chained) moves.
1978af5b582Smckusick */
scanframes(color)1988af5b582Smckusick scanframes(color)
1998af5b582Smckusick int color;
2008af5b582Smckusick {
2018af5b582Smckusick register struct combostr *cbp, *ecbp;
2028af5b582Smckusick register struct spotstr *sp;
203*ff46cf54Smckusick register union comboval *cp;
204*ff46cf54Smckusick register struct elist *ep, *nep;
2058af5b582Smckusick register int i, r, d, n;
206*ff46cf54Smckusick union comboval cb;
2078af5b582Smckusick
2088af5b582Smckusick curcolor = color;
2098af5b582Smckusick
2108af5b582Smckusick /* check for empty list of frames */
2118af5b582Smckusick cbp = sortframes[color];
2128af5b582Smckusick if (cbp == (struct combostr *)0)
2138af5b582Smckusick return;
2148af5b582Smckusick
2158af5b582Smckusick /* quick check for four in a row */
2168af5b582Smckusick sp = &board[cbp->c_vertex];
2178af5b582Smckusick cb.s = sp->s_fval[color][d = cbp->c_dir].s;
2188af5b582Smckusick if (cb.s < 0x101) {
2198af5b582Smckusick d = dd[d];
2208af5b582Smckusick for (i = 5 + cb.c.b; --i >= 0; sp += d) {
2218af5b582Smckusick if (sp->s_occ != EMPTY)
2228af5b582Smckusick continue;
2238af5b582Smckusick sp->s_combo[color].s = cb.s;
2248af5b582Smckusick sp->s_level[color] = 1;
2258af5b582Smckusick }
2268af5b582Smckusick return;
2278af5b582Smckusick }
2288af5b582Smckusick
229*ff46cf54Smckusick /*
230*ff46cf54Smckusick * Update the minimum combo value for each spot in the frame
231*ff46cf54Smckusick * and try making all combinations of two frames intersecting at
232*ff46cf54Smckusick * an empty spot.
233*ff46cf54Smckusick */
234*ff46cf54Smckusick n = combolen;
2358af5b582Smckusick ecbp = cbp;
2368af5b582Smckusick do {
2378af5b582Smckusick sp = &board[cbp->c_vertex];
2388af5b582Smckusick cp = &sp->s_fval[color][r = cbp->c_dir];
2398af5b582Smckusick d = dd[r];
2408af5b582Smckusick if (cp->c.b) {
241*ff46cf54Smckusick /*
242*ff46cf54Smckusick * Since this is the first spot of an open ended
243*ff46cf54Smckusick * frame, we treat it as a closed frame.
244*ff46cf54Smckusick */
2458af5b582Smckusick cb.c.a = cp->c.a + 1;
2468af5b582Smckusick cb.c.b = 0;
2478af5b582Smckusick if (cb.s < sp->s_combo[color].s) {
2488af5b582Smckusick sp->s_combo[color].s = cb.s;
2498af5b582Smckusick sp->s_level[color] = 1;
2508af5b582Smckusick }
251*ff46cf54Smckusick /*
252*ff46cf54Smckusick * Try combining other frames that intersect
253*ff46cf54Smckusick * at this spot.
254*ff46cf54Smckusick */
255*ff46cf54Smckusick makecombo2(cbp, sp, 0, cb.s);
2568af5b582Smckusick if (cp->s != 0x101)
2578af5b582Smckusick cb.s = cp->s;
258*ff46cf54Smckusick else if (color != nextcolor)
259*ff46cf54Smckusick memset(tmpmap, 0, sizeof(tmpmap));
2608af5b582Smckusick sp += d;
261*ff46cf54Smckusick i = 1;
2628af5b582Smckusick } else {
2638af5b582Smckusick cb.s = cp->s;
264*ff46cf54Smckusick i = 0;
2658af5b582Smckusick }
266*ff46cf54Smckusick for (; i < 5; i++, sp += d) { /* for each spot */
2678af5b582Smckusick if (sp->s_occ != EMPTY)
2688af5b582Smckusick continue;
2698af5b582Smckusick if (cp->s < sp->s_combo[color].s) {
2708af5b582Smckusick sp->s_combo[color].s = cp->s;
2718af5b582Smckusick sp->s_level[color] = 1;
2728af5b582Smckusick }
273*ff46cf54Smckusick if (cp->s == 0x101) {
2748af5b582Smckusick sp->s_nforce[color]++;
275*ff46cf54Smckusick if (color != nextcolor) {
276*ff46cf54Smckusick n = sp - board;
277*ff46cf54Smckusick BIT_SET(tmpmap, n);
278*ff46cf54Smckusick }
279*ff46cf54Smckusick }
280*ff46cf54Smckusick /*
281*ff46cf54Smckusick * Try combining other frames that intersect
282*ff46cf54Smckusick * at this spot.
283*ff46cf54Smckusick */
284*ff46cf54Smckusick makecombo2(cbp, sp, i, cb.s);
285*ff46cf54Smckusick }
286*ff46cf54Smckusick if (cp->s == 0x101 && color != nextcolor) {
287*ff46cf54Smckusick if (nforce == 0)
288*ff46cf54Smckusick memcpy(forcemap, tmpmap, sizeof(tmpmap));
289*ff46cf54Smckusick else {
290*ff46cf54Smckusick for (i = 0; i < MAPSZ; i++)
291*ff46cf54Smckusick forcemap[i] &= tmpmap[i];
292*ff46cf54Smckusick }
2938af5b582Smckusick }
2948af5b582Smckusick /* mark frame as having been processed */
2958af5b582Smckusick board[cbp->c_vertex].s_flg |= MFLAG << r;
2968af5b582Smckusick } while ((cbp = cbp->c_next) != ecbp);
2978af5b582Smckusick
298*ff46cf54Smckusick /*
299*ff46cf54Smckusick * Try to make new 3rd level combos, 4th level, etc.
300*ff46cf54Smckusick * Limit the search depth early in the game.
301*ff46cf54Smckusick */
3028af5b582Smckusick d = 2;
303*ff46cf54Smckusick while (d <= ((movenum + 1) >> 1) && combolen > n) {
3048af5b582Smckusick if (debug) {
305*ff46cf54Smckusick sprintf(fmtbuf, "%cL%d %d %d %d", "BW"[color],
306*ff46cf54Smckusick d, combolen - n, combocnt, elistcnt);
3078af5b582Smckusick dlog(fmtbuf);
3088af5b582Smckusick refresh();
3098af5b582Smckusick }
310*ff46cf54Smckusick n = combolen;
3118af5b582Smckusick addframes(d);
3128af5b582Smckusick d++;
3138af5b582Smckusick }
3148af5b582Smckusick
3158af5b582Smckusick /* scan for combos at empty spots */
3168af5b582Smckusick for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
317*ff46cf54Smckusick for (ep = sp->s_empty; ep; ep = nep) {
3188af5b582Smckusick cbp = ep->e_combo;
319*ff46cf54Smckusick if (cbp->c_combo.s <= sp->s_combo[color].s) {
320*ff46cf54Smckusick if (cbp->c_combo.s != sp->s_combo[color].s) {
3218af5b582Smckusick sp->s_combo[color].s = cbp->c_combo.s;
3228af5b582Smckusick sp->s_level[color] = cbp->c_nframes;
323*ff46cf54Smckusick } else if (cbp->c_nframes < sp->s_level[color])
3248af5b582Smckusick sp->s_level[color] = cbp->c_nframes;
3258af5b582Smckusick }
326*ff46cf54Smckusick nep = ep->e_next;
327*ff46cf54Smckusick free(ep);
328*ff46cf54Smckusick elistcnt--;
3298af5b582Smckusick }
330*ff46cf54Smckusick sp->s_empty = (struct elist *)0;
331*ff46cf54Smckusick for (ep = sp->s_nempty; ep; ep = nep) {
332*ff46cf54Smckusick cbp = ep->e_combo;
333*ff46cf54Smckusick if (cbp->c_combo.s <= sp->s_combo[color].s) {
334*ff46cf54Smckusick if (cbp->c_combo.s != sp->s_combo[color].s) {
335*ff46cf54Smckusick sp->s_combo[color].s = cbp->c_combo.s;
336*ff46cf54Smckusick sp->s_level[color] = cbp->c_nframes;
337*ff46cf54Smckusick } else if (cbp->c_nframes < sp->s_level[color])
338*ff46cf54Smckusick sp->s_level[color] = cbp->c_nframes;
339*ff46cf54Smckusick }
340*ff46cf54Smckusick nep = ep->e_next;
341*ff46cf54Smckusick free(ep);
342*ff46cf54Smckusick elistcnt--;
343*ff46cf54Smckusick }
344*ff46cf54Smckusick sp->s_nempty = (struct elist *)0;
345*ff46cf54Smckusick }
346*ff46cf54Smckusick
347*ff46cf54Smckusick /* remove old combos */
348*ff46cf54Smckusick if ((cbp = sortcombos) != (struct combostr *)0) {
349*ff46cf54Smckusick struct combostr *ncbp;
350*ff46cf54Smckusick
351*ff46cf54Smckusick /* scan the list */
352*ff46cf54Smckusick ecbp = cbp;
353*ff46cf54Smckusick do {
354*ff46cf54Smckusick ncbp = cbp->c_next;
355*ff46cf54Smckusick free(cbp);
356*ff46cf54Smckusick combocnt--;
357*ff46cf54Smckusick } while ((cbp = ncbp) != ecbp);
358*ff46cf54Smckusick sortcombos = (struct combostr *)0;
359*ff46cf54Smckusick }
360*ff46cf54Smckusick combolen = 0;
361*ff46cf54Smckusick
362*ff46cf54Smckusick #ifdef DEBUG
363*ff46cf54Smckusick if (combocnt) {
364*ff46cf54Smckusick sprintf(fmtbuf, "scanframes: %c combocnt %d", "BW"[color],
365*ff46cf54Smckusick combocnt);
366*ff46cf54Smckusick dlog(fmtbuf);
367*ff46cf54Smckusick whatsup(0);
368*ff46cf54Smckusick }
369*ff46cf54Smckusick if (elistcnt) {
370*ff46cf54Smckusick sprintf(fmtbuf, "scanframes: %c elistcnt %d", "BW"[color],
371*ff46cf54Smckusick elistcnt);
372*ff46cf54Smckusick dlog(fmtbuf);
373*ff46cf54Smckusick whatsup(0);
374*ff46cf54Smckusick }
375*ff46cf54Smckusick #endif
3768af5b582Smckusick }
3778af5b582Smckusick
3788af5b582Smckusick /*
3798af5b582Smckusick * Compute all level 2 combos of frames intersecting spot 'osp'
3808af5b582Smckusick * within the frame 'ocbp' and combo value 's'.
3818af5b582Smckusick */
382*ff46cf54Smckusick makecombo2(ocbp, osp, off, s)
3838af5b582Smckusick struct combostr *ocbp;
3848af5b582Smckusick struct spotstr *osp;
385*ff46cf54Smckusick int off;
3868af5b582Smckusick int s;
3878af5b582Smckusick {
3888af5b582Smckusick register struct spotstr *sp, *fsp;
389*ff46cf54Smckusick register struct combostr *ncbp;
3908af5b582Smckusick register int f, r, d, c;
391*ff46cf54Smckusick int baseB, fcnt, emask, bmask, n;
392*ff46cf54Smckusick union comboval ocb, fcb;
393*ff46cf54Smckusick struct combostr **scbpp, *fcbp;
3948af5b582Smckusick
3958af5b582Smckusick /* try to combine a new frame with those found so far */
3968af5b582Smckusick ocb.s = s;
3978af5b582Smckusick baseB = ocb.c.a + ocb.c.b - 1;
398*ff46cf54Smckusick fcnt = ocb.c.a - 2;
399*ff46cf54Smckusick emask = fcnt ? ((ocb.c.b ? 0x1E : 0x1F) & ~(1 << off)) : 0;
4008af5b582Smckusick for (r = 4; --r >= 0; ) { /* for each direction */
401*ff46cf54Smckusick /* don't include frames that overlap in the same direction */
4028af5b582Smckusick if (r == ocbp->c_dir)
4038af5b582Smckusick continue;
4048af5b582Smckusick d = dd[r];
405*ff46cf54Smckusick /*
406*ff46cf54Smckusick * Frame A combined with B is the same value as B combined with A
407*ff46cf54Smckusick * so skip frames that have already been processed (MFLAG).
408*ff46cf54Smckusick * Also skip blocked frames (BFLAG) and frames that are <1,x>
409*ff46cf54Smckusick * since combining another frame with it isn't valid.
410*ff46cf54Smckusick */
4118af5b582Smckusick bmask = (BFLAG | FFLAG | MFLAG) << r;
4128af5b582Smckusick fsp = osp;
413*ff46cf54Smckusick for (f = 0; f < 5; f++, fsp -= d) { /* for each frame */
4148af5b582Smckusick if (fsp->s_occ == BORDER)
4158af5b582Smckusick break;
4168af5b582Smckusick if (fsp->s_flg & bmask)
4178af5b582Smckusick continue;
4188af5b582Smckusick
4198af5b582Smckusick /* don't include frames of the wrong color */
4208af5b582Smckusick fcb.s = fsp->s_fval[curcolor][r].s;
4218af5b582Smckusick if (fcb.c.a >= MAXA)
4228af5b582Smckusick continue;
4238af5b582Smckusick
4248af5b582Smckusick /*
4258af5b582Smckusick * Get the combo value for this frame.
4268af5b582Smckusick * If this is the end point of the frame,
4278af5b582Smckusick * use the closed ended value for the frame.
4288af5b582Smckusick */
429*ff46cf54Smckusick if (f == 0 && fcb.c.b || fcb.s == 0x101) {
4308af5b582Smckusick fcb.c.a++;
4318af5b582Smckusick fcb.c.b = 0;
4328af5b582Smckusick }
4338af5b582Smckusick
4348af5b582Smckusick /* compute combo value */
4358af5b582Smckusick c = fcb.c.a + ocb.c.a - 3;
436*ff46cf54Smckusick if (c > 4)
4378af5b582Smckusick continue;
4388af5b582Smckusick n = fcb.c.a + fcb.c.b - 1;
4398af5b582Smckusick if (baseB < n)
4408af5b582Smckusick n = baseB;
4418af5b582Smckusick
4428af5b582Smckusick /* make a new combo! */
443*ff46cf54Smckusick ncbp = (struct combostr *)malloc(sizeof(struct combostr) +
444*ff46cf54Smckusick 2 * sizeof(struct combostr *));
445*ff46cf54Smckusick scbpp = (struct combostr **)(ncbp + 1);
446*ff46cf54Smckusick fcbp = fsp->s_frame[r];
447*ff46cf54Smckusick if (ocbp < fcbp) {
448*ff46cf54Smckusick scbpp[0] = ocbp;
449*ff46cf54Smckusick scbpp[1] = fcbp;
450*ff46cf54Smckusick } else {
451*ff46cf54Smckusick scbpp[0] = fcbp;
452*ff46cf54Smckusick scbpp[1] = ocbp;
453*ff46cf54Smckusick }
454*ff46cf54Smckusick ncbp->c_combo.c.a = c;
455*ff46cf54Smckusick ncbp->c_combo.c.b = n;
456*ff46cf54Smckusick ncbp->c_link[0] = ocbp;
457*ff46cf54Smckusick ncbp->c_link[1] = fcbp;
458*ff46cf54Smckusick ncbp->c_linkv[0].s = ocb.s;
459*ff46cf54Smckusick ncbp->c_linkv[1].s = fcb.s;
460*ff46cf54Smckusick ncbp->c_voff[0] = off;
461*ff46cf54Smckusick ncbp->c_voff[1] = f;
462*ff46cf54Smckusick ncbp->c_vertex = osp - board;
463*ff46cf54Smckusick ncbp->c_nframes = 2;
464*ff46cf54Smckusick ncbp->c_dir = 0;
465*ff46cf54Smckusick ncbp->c_frameindex = 0;
466*ff46cf54Smckusick ncbp->c_flg = (ocb.c.b) ? C_OPEN_0 : 0;
467*ff46cf54Smckusick if (fcb.c.b)
468*ff46cf54Smckusick ncbp->c_flg |= C_OPEN_1;
469*ff46cf54Smckusick ncbp->c_framecnt[0] = fcnt;
470*ff46cf54Smckusick ncbp->c_emask[0] = emask;
471*ff46cf54Smckusick ncbp->c_framecnt[1] = fcb.c.a - 2;
472*ff46cf54Smckusick ncbp->c_emask[1] = ncbp->c_framecnt[1] ?
473*ff46cf54Smckusick ((fcb.c.b ? 0x1E : 0x1F) & ~(1 << f)) : 0;
474*ff46cf54Smckusick combocnt++;
4758af5b582Smckusick
4768af5b582Smckusick if (c == 1 && debug > 1 || debug > 3) {
477*ff46cf54Smckusick sprintf(fmtbuf, "%c c %d %d m %x %x o %d %d",
478*ff46cf54Smckusick "bw"[curcolor],
479*ff46cf54Smckusick ncbp->c_framecnt[0], ncbp->c_framecnt[1],
480*ff46cf54Smckusick ncbp->c_emask[0], ncbp->c_emask[1],
481*ff46cf54Smckusick ncbp->c_voff[0], ncbp->c_voff[1]);
4828af5b582Smckusick dlog(fmtbuf);
483*ff46cf54Smckusick printcombo(ncbp, fmtbuf);
484*ff46cf54Smckusick dlog(fmtbuf);
4858af5b582Smckusick }
4868af5b582Smckusick if (c > 1) {
487*ff46cf54Smckusick /* record the empty spots that will complete this combo */
488*ff46cf54Smckusick makeempty(ncbp);
4898af5b582Smckusick
4908af5b582Smckusick /* add the new combo to the end of the list */
491*ff46cf54Smckusick appendcombo(ncbp, curcolor);
4928af5b582Smckusick } else {
493*ff46cf54Smckusick updatecombo(ncbp, curcolor);
494*ff46cf54Smckusick free(ncbp);
495*ff46cf54Smckusick combocnt--;
4968af5b582Smckusick }
497*ff46cf54Smckusick #ifdef DEBUG
498*ff46cf54Smckusick if (c == 1 && debug > 1 || debug > 5) {
499*ff46cf54Smckusick markcombo(ncbp);
500*ff46cf54Smckusick bdisp();
501*ff46cf54Smckusick whatsup(0);
502*ff46cf54Smckusick clearcombo(ncbp, 0);
503*ff46cf54Smckusick }
504*ff46cf54Smckusick #endif /* DEBUG */
5058af5b582Smckusick }
5068af5b582Smckusick }
5078af5b582Smckusick }
5088af5b582Smckusick
5098af5b582Smckusick /*
510*ff46cf54Smckusick * Scan the sorted list of frames and try to add a frame to
511*ff46cf54Smckusick * combinations of 'level' number of frames.
5128af5b582Smckusick */
addframes(level)5138af5b582Smckusick addframes(level)
5148af5b582Smckusick int level;
5158af5b582Smckusick {
5168af5b582Smckusick register struct combostr *cbp, *ecbp;
5178af5b582Smckusick register struct spotstr *sp, *fsp;
518*ff46cf54Smckusick register struct elist *ep, *nep;
5198af5b582Smckusick register int i, r, d;
520*ff46cf54Smckusick struct combostr **cbpp, *pcbp;
521*ff46cf54Smckusick union comboval fcb, cb;
5228af5b582Smckusick
5238af5b582Smckusick curlevel = level;
5248af5b582Smckusick
525*ff46cf54Smckusick /* scan for combos at empty spots */
526*ff46cf54Smckusick i = curcolor;
527*ff46cf54Smckusick for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
528*ff46cf54Smckusick for (ep = sp->s_empty; ep; ep = nep) {
529*ff46cf54Smckusick cbp = ep->e_combo;
530*ff46cf54Smckusick if (cbp->c_combo.s <= sp->s_combo[i].s) {
531*ff46cf54Smckusick if (cbp->c_combo.s != sp->s_combo[i].s) {
532*ff46cf54Smckusick sp->s_combo[i].s = cbp->c_combo.s;
533*ff46cf54Smckusick sp->s_level[i] = cbp->c_nframes;
534*ff46cf54Smckusick } else if (cbp->c_nframes < sp->s_level[i])
535*ff46cf54Smckusick sp->s_level[i] = cbp->c_nframes;
536*ff46cf54Smckusick }
537*ff46cf54Smckusick nep = ep->e_next;
538*ff46cf54Smckusick free(ep);
539*ff46cf54Smckusick elistcnt--;
540*ff46cf54Smckusick }
541*ff46cf54Smckusick sp->s_empty = sp->s_nempty;
542*ff46cf54Smckusick sp->s_nempty = (struct elist *)0;
543*ff46cf54Smckusick }
5448af5b582Smckusick
545*ff46cf54Smckusick /* try to add frames to the uncompleted combos at level curlevel */
546*ff46cf54Smckusick cbp = ecbp = sortframes[curcolor];
5478af5b582Smckusick do {
5488af5b582Smckusick fsp = &board[cbp->c_vertex];
5498af5b582Smckusick r = cbp->c_dir;
5508af5b582Smckusick /* skip frames that are part of a <1,x> combo */
5518af5b582Smckusick if (fsp->s_flg & (FFLAG << r))
5528af5b582Smckusick continue;
5538af5b582Smckusick
5548af5b582Smckusick /*
5558af5b582Smckusick * Don't include <1,x> combo frames,
556*ff46cf54Smckusick * treat it as a closed three in a row instead.
5578af5b582Smckusick */
5588af5b582Smckusick fcb.s = fsp->s_fval[curcolor][r].s;
5598af5b582Smckusick if (fcb.s == 0x101)
5608af5b582Smckusick fcb.s = 0x200;
5618af5b582Smckusick
5628af5b582Smckusick /*
5638af5b582Smckusick * If this is an open ended frame, use
5648af5b582Smckusick * the combo value with the end closed.
5658af5b582Smckusick */
5668af5b582Smckusick if (fsp->s_occ == EMPTY) {
5678af5b582Smckusick if (fcb.c.b) {
5688af5b582Smckusick cb.c.a = fcb.c.a + 1;
5698af5b582Smckusick cb.c.b = 0;
5708af5b582Smckusick } else
5718af5b582Smckusick cb.s = fcb.s;
572*ff46cf54Smckusick makecombo(cbp, fsp, 0, cb.s);
5738af5b582Smckusick }
5748af5b582Smckusick
5758af5b582Smckusick /*
5768af5b582Smckusick * The next four spots are handled the same for both
5778af5b582Smckusick * open and closed ended frames.
5788af5b582Smckusick */
5798af5b582Smckusick d = dd[r];
5808af5b582Smckusick sp = fsp + d;
581*ff46cf54Smckusick for (i = 1; i < 5; i++, sp += d) {
5828af5b582Smckusick if (sp->s_occ != EMPTY)
5838af5b582Smckusick continue;
584*ff46cf54Smckusick makecombo(cbp, sp, i, fcb.s);
5858af5b582Smckusick }
5868af5b582Smckusick } while ((cbp = cbp->c_next) != ecbp);
587*ff46cf54Smckusick
588*ff46cf54Smckusick /* put all the combos in the hash list on the sorted list */
589*ff46cf54Smckusick cbpp = &hashcombos[FAREA];
590*ff46cf54Smckusick do {
591*ff46cf54Smckusick cbp = *--cbpp;
592*ff46cf54Smckusick if (cbp == (struct combostr *)0)
593*ff46cf54Smckusick continue;
594*ff46cf54Smckusick *cbpp = (struct combostr *)0;
595*ff46cf54Smckusick ecbp = sortcombos;
596*ff46cf54Smckusick if (ecbp == (struct combostr *)0)
597*ff46cf54Smckusick sortcombos = cbp;
598*ff46cf54Smckusick else {
599*ff46cf54Smckusick /* append to sort list */
600*ff46cf54Smckusick pcbp = ecbp->c_prev;
601*ff46cf54Smckusick pcbp->c_next = cbp;
602*ff46cf54Smckusick ecbp->c_prev = cbp->c_prev;
603*ff46cf54Smckusick cbp->c_prev->c_next = ecbp;
604*ff46cf54Smckusick cbp->c_prev = pcbp;
605*ff46cf54Smckusick }
606*ff46cf54Smckusick } while (cbpp != hashcombos);
6078af5b582Smckusick }
6088af5b582Smckusick
6098af5b582Smckusick /*
6108af5b582Smckusick * Compute all level N combos of frames intersecting spot 'osp'
6118af5b582Smckusick * within the frame 'ocbp' and combo value 's'.
6128af5b582Smckusick */
613*ff46cf54Smckusick makecombo(ocbp, osp, off, s)
6148af5b582Smckusick struct combostr *ocbp;
6158af5b582Smckusick struct spotstr *osp;
616*ff46cf54Smckusick int off;
6178af5b582Smckusick int s;
6188af5b582Smckusick {
6198af5b582Smckusick register struct combostr *cbp, *ncbp;
6208af5b582Smckusick register struct spotstr *sp;
6218af5b582Smckusick register struct elist *ep;
6228af5b582Smckusick register int n, c;
6238af5b582Smckusick struct elist *nep, **epp;
624*ff46cf54Smckusick struct combostr **scbpp;
625*ff46cf54Smckusick int baseB, fcnt, emask, verts, d;
626*ff46cf54Smckusick union comboval ocb, cb;
627*ff46cf54Smckusick struct ovlp_info vertices[1];
6288af5b582Smckusick
6298af5b582Smckusick ocb.s = s;
6308af5b582Smckusick baseB = ocb.c.a + ocb.c.b - 1;
631*ff46cf54Smckusick fcnt = ocb.c.a - 2;
632*ff46cf54Smckusick emask = fcnt ? ((ocb.c.b ? 0x1E : 0x1F) & ~(1 << off)) : 0;
633*ff46cf54Smckusick for (ep = osp->s_empty; ep; ep = ep->e_next) {
634*ff46cf54Smckusick /* check for various kinds of overlap */
6358af5b582Smckusick cbp = ep->e_combo;
636*ff46cf54Smckusick verts = checkframes(cbp, ocbp, osp, s, vertices);
637*ff46cf54Smckusick if (verts < 0)
6388af5b582Smckusick continue;
6398af5b582Smckusick
6408af5b582Smckusick /* check to see if this frame forms a valid loop */
641*ff46cf54Smckusick if (verts) {
642*ff46cf54Smckusick sp = &board[vertices[0].o_intersect];
643*ff46cf54Smckusick #ifdef DEBUG
644*ff46cf54Smckusick if (sp->s_occ != EMPTY) {
645*ff46cf54Smckusick sprintf(fmtbuf, "loop: %c %s", "BW"[curcolor],
646*ff46cf54Smckusick stoc(sp - board));
647*ff46cf54Smckusick dlog(fmtbuf);
648*ff46cf54Smckusick whatsup(0);
6498af5b582Smckusick }
650*ff46cf54Smckusick #endif
651*ff46cf54Smckusick /*
652*ff46cf54Smckusick * It is a valid loop if the intersection spot
653*ff46cf54Smckusick * of the frame we are trying to attach is one
654*ff46cf54Smckusick * of the completion spots of the combostr
655*ff46cf54Smckusick * we are trying to attach the frame to.
656*ff46cf54Smckusick */
657*ff46cf54Smckusick for (nep = sp->s_empty; nep; nep = nep->e_next) {
658*ff46cf54Smckusick if (nep->e_combo == cbp)
659*ff46cf54Smckusick goto fnd;
6608af5b582Smckusick if (nep->e_combo->c_nframes < cbp->c_nframes)
6618af5b582Smckusick break;
6628af5b582Smckusick }
6638af5b582Smckusick /* frame overlaps but not at a valid spot */
6648af5b582Smckusick continue;
665*ff46cf54Smckusick fnd:
666*ff46cf54Smckusick ;
6678af5b582Smckusick }
6688af5b582Smckusick
669*ff46cf54Smckusick /* compute the first half of the combo value */
670*ff46cf54Smckusick c = cbp->c_combo.c.a + ocb.c.a - verts - 3;
671*ff46cf54Smckusick if (c > 4)
672*ff46cf54Smckusick continue;
673*ff46cf54Smckusick
674*ff46cf54Smckusick /* compute the second half of the combo value */
675*ff46cf54Smckusick n = ep->e_fval.c.a + ep->e_fval.c.b - 1;
6768af5b582Smckusick if (baseB < n)
6778af5b582Smckusick n = baseB;
6788af5b582Smckusick
6798af5b582Smckusick /* make a new combo! */
680*ff46cf54Smckusick ncbp = (struct combostr *)malloc(sizeof(struct combostr) +
681*ff46cf54Smckusick (cbp->c_nframes + 1) * sizeof(struct combostr *));
682*ff46cf54Smckusick scbpp = (struct combostr **)(ncbp + 1);
683*ff46cf54Smckusick if (sortcombo(scbpp, (struct combostr **)(cbp + 1), ocbp)) {
684*ff46cf54Smckusick free(ncbp);
685*ff46cf54Smckusick continue;
686*ff46cf54Smckusick }
687*ff46cf54Smckusick combocnt++;
688*ff46cf54Smckusick
6898af5b582Smckusick ncbp->c_combo.c.a = c;
6908af5b582Smckusick ncbp->c_combo.c.b = n;
6918af5b582Smckusick ncbp->c_link[0] = cbp;
6928af5b582Smckusick ncbp->c_link[1] = ocbp;
693*ff46cf54Smckusick ncbp->c_linkv[1].s = ocb.s;
694*ff46cf54Smckusick ncbp->c_voff[1] = off;
6958af5b582Smckusick ncbp->c_vertex = osp - board;
6968af5b582Smckusick ncbp->c_nframes = cbp->c_nframes + 1;
697*ff46cf54Smckusick ncbp->c_flg = ocb.c.b ? C_OPEN_1 : 0;
698*ff46cf54Smckusick ncbp->c_frameindex = ep->e_frameindex;
699*ff46cf54Smckusick /*
700*ff46cf54Smckusick * Update the completion spot mask of the frame we
701*ff46cf54Smckusick * are attaching 'ocbp' to so the intersection isn't
702*ff46cf54Smckusick * listed twice.
703*ff46cf54Smckusick */
704*ff46cf54Smckusick ncbp->c_framecnt[0] = ep->e_framecnt;
705*ff46cf54Smckusick ncbp->c_emask[0] = ep->e_emask;
7068af5b582Smckusick if (verts) {
707*ff46cf54Smckusick ncbp->c_flg |= C_LOOP;
708*ff46cf54Smckusick ncbp->c_dir = vertices[0].o_frameindex;
709*ff46cf54Smckusick ncbp->c_framecnt[1] = fcnt - 1;
710*ff46cf54Smckusick if (ncbp->c_framecnt[1]) {
711*ff46cf54Smckusick n = (vertices[0].o_intersect - ocbp->c_vertex) /
712*ff46cf54Smckusick dd[ocbp->c_dir];
713*ff46cf54Smckusick ncbp->c_emask[1] = emask & ~(1 << n);
714*ff46cf54Smckusick } else
715*ff46cf54Smckusick ncbp->c_emask[1] = 0;
716*ff46cf54Smckusick ncbp->c_voff[0] = vertices[0].o_off;
7178af5b582Smckusick } else {
7188af5b582Smckusick ncbp->c_dir = 0;
719*ff46cf54Smckusick ncbp->c_framecnt[1] = fcnt;
720*ff46cf54Smckusick ncbp->c_emask[1] = emask;
721*ff46cf54Smckusick ncbp->c_voff[0] = ep->e_off;
7228af5b582Smckusick }
7238af5b582Smckusick
724*ff46cf54Smckusick if (c == 1 && debug > 1 || debug > 3) {
725*ff46cf54Smckusick sprintf(fmtbuf, "%c v%d i%d d%d c %d %d m %x %x o %d %d",
726*ff46cf54Smckusick "bw"[curcolor], verts, ncbp->c_frameindex, ncbp->c_dir,
727*ff46cf54Smckusick ncbp->c_framecnt[0], ncbp->c_framecnt[1],
728*ff46cf54Smckusick ncbp->c_emask[0], ncbp->c_emask[1],
729*ff46cf54Smckusick ncbp->c_voff[0], ncbp->c_voff[1]);
7308af5b582Smckusick dlog(fmtbuf);
731*ff46cf54Smckusick printcombo(ncbp, fmtbuf);
7328af5b582Smckusick dlog(fmtbuf);
7338af5b582Smckusick }
7348af5b582Smckusick if (c > 1) {
735*ff46cf54Smckusick /* record the empty spots that will complete this combo */
736*ff46cf54Smckusick makeempty(ncbp);
737*ff46cf54Smckusick combolen++;
7388af5b582Smckusick } else {
739*ff46cf54Smckusick /* update board values */
7408af5b582Smckusick updatecombo(ncbp, curcolor);
7418af5b582Smckusick }
742*ff46cf54Smckusick #ifdef DEBUG
743*ff46cf54Smckusick if (c == 1 && debug > 1 || debug > 4) {
744*ff46cf54Smckusick markcombo(ncbp);
745*ff46cf54Smckusick bdisp();
746*ff46cf54Smckusick whatsup(0);
747*ff46cf54Smckusick clearcombo(ncbp, 0);
748*ff46cf54Smckusick }
749*ff46cf54Smckusick #endif /* DEBUG */
750*ff46cf54Smckusick }
751*ff46cf54Smckusick }
752*ff46cf54Smckusick
753*ff46cf54Smckusick #define MAXDEPTH 100
754*ff46cf54Smckusick struct elist einfo[MAXDEPTH];
755*ff46cf54Smckusick struct combostr *ecombo[MAXDEPTH]; /* separate from elist to save space */
756*ff46cf54Smckusick
757*ff46cf54Smckusick /*
758*ff46cf54Smckusick * Add the combostr 'ocbp' to the empty spots list for each empty spot
759*ff46cf54Smckusick * in 'ocbp' that will complete the combo.
760*ff46cf54Smckusick */
761*ff46cf54Smckusick makeempty(ocbp)
762*ff46cf54Smckusick struct combostr *ocbp;
763*ff46cf54Smckusick {
764*ff46cf54Smckusick struct combostr *cbp, *tcbp, **cbpp;
765*ff46cf54Smckusick struct elist *ep, *nep, **epp;
766*ff46cf54Smckusick struct spotstr *sp;
767*ff46cf54Smckusick int s, d, m, emask, i;
768*ff46cf54Smckusick int nframes;
769*ff46cf54Smckusick
770*ff46cf54Smckusick if (debug > 2) {
771*ff46cf54Smckusick sprintf(fmtbuf, "E%c ", "bw"[curcolor]);
772*ff46cf54Smckusick printcombo(ocbp, fmtbuf + 3);
773*ff46cf54Smckusick dlog(fmtbuf);
774*ff46cf54Smckusick }
775*ff46cf54Smckusick
776*ff46cf54Smckusick /* should never happen but check anyway */
777*ff46cf54Smckusick if ((nframes = ocbp->c_nframes) >= MAXDEPTH)
778*ff46cf54Smckusick return;
779*ff46cf54Smckusick
780*ff46cf54Smckusick /*
781*ff46cf54Smckusick * The lower level combo can be pointed to by more than one
782*ff46cf54Smckusick * higher level 'struct combostr' so we can't modify the
783*ff46cf54Smckusick * lower level. Therefore, higher level combos store the
784*ff46cf54Smckusick * real mask of the lower level frame in c_emask[0] and the
785*ff46cf54Smckusick * frame number in c_frameindex.
786*ff46cf54Smckusick *
787*ff46cf54Smckusick * First we traverse the tree from top to bottom and save the
788*ff46cf54Smckusick * connection info. Then we traverse the tree from bottom to
789*ff46cf54Smckusick * top overwriting lower levels with the newer emask information.
790*ff46cf54Smckusick */
791*ff46cf54Smckusick ep = &einfo[nframes];
792*ff46cf54Smckusick cbpp = &ecombo[nframes];
793*ff46cf54Smckusick for (cbp = ocbp; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
794*ff46cf54Smckusick ep--;
795*ff46cf54Smckusick ep->e_combo = cbp;
796*ff46cf54Smckusick *--cbpp = cbp->c_link[1];
797*ff46cf54Smckusick ep->e_off = cbp->c_voff[1];
798*ff46cf54Smckusick ep->e_frameindex = cbp->c_frameindex;
799*ff46cf54Smckusick ep->e_fval.s = cbp->c_linkv[1].s;
800*ff46cf54Smckusick ep->e_framecnt = cbp->c_framecnt[1];
801*ff46cf54Smckusick ep->e_emask = cbp->c_emask[1];
802*ff46cf54Smckusick }
803*ff46cf54Smckusick cbp = ep->e_combo;
804*ff46cf54Smckusick ep--;
805*ff46cf54Smckusick ep->e_combo = cbp;
806*ff46cf54Smckusick *--cbpp = cbp->c_link[0];
807*ff46cf54Smckusick ep->e_off = cbp->c_voff[0];
808*ff46cf54Smckusick ep->e_frameindex = 0;
809*ff46cf54Smckusick ep->e_fval.s = cbp->c_linkv[0].s;
810*ff46cf54Smckusick ep->e_framecnt = cbp->c_framecnt[0];
811*ff46cf54Smckusick ep->e_emask = cbp->c_emask[0];
812*ff46cf54Smckusick
813*ff46cf54Smckusick /* now update the emask info */
814*ff46cf54Smckusick s = 0;
815*ff46cf54Smckusick for (i = 2, ep += 2; i < nframes; i++, ep++) {
816*ff46cf54Smckusick cbp = ep->e_combo;
817*ff46cf54Smckusick nep = &einfo[ep->e_frameindex];
818*ff46cf54Smckusick nep->e_framecnt = cbp->c_framecnt[0];
819*ff46cf54Smckusick nep->e_emask = cbp->c_emask[0];
820*ff46cf54Smckusick
821*ff46cf54Smckusick if (cbp->c_flg & C_LOOP) {
822*ff46cf54Smckusick s++;
823*ff46cf54Smckusick /*
824*ff46cf54Smckusick * Account for the fact that this frame connects
825*ff46cf54Smckusick * to a previous one (thus forming a loop).
826*ff46cf54Smckusick */
827*ff46cf54Smckusick nep = &einfo[cbp->c_dir];
828*ff46cf54Smckusick if (--nep->e_framecnt)
829*ff46cf54Smckusick nep->e_emask &= ~(1 << cbp->c_voff[0]);
830*ff46cf54Smckusick else
831*ff46cf54Smckusick nep->e_emask = 0;
8328af5b582Smckusick }
8338af5b582Smckusick }
8348af5b582Smckusick
8358af5b582Smckusick /*
836*ff46cf54Smckusick * We only need to update the emask values of "complete" loops
837*ff46cf54Smckusick * to include the intersection spots.
8388af5b582Smckusick */
839*ff46cf54Smckusick if (s && ocbp->c_combo.c.a == 2) {
840*ff46cf54Smckusick /* process loops from the top down */
841*ff46cf54Smckusick ep = &einfo[nframes];
842*ff46cf54Smckusick do {
843*ff46cf54Smckusick ep--;
844*ff46cf54Smckusick cbp = ep->e_combo;
845*ff46cf54Smckusick if (!(cbp->c_flg & C_LOOP))
846*ff46cf54Smckusick continue;
8478af5b582Smckusick
848*ff46cf54Smckusick /*
849*ff46cf54Smckusick * Update the emask values to include the
850*ff46cf54Smckusick * intersection spots.
851*ff46cf54Smckusick */
852*ff46cf54Smckusick nep = &einfo[cbp->c_dir];
853*ff46cf54Smckusick nep->e_framecnt = 1;
854*ff46cf54Smckusick nep->e_emask = 1 << cbp->c_voff[0];
855*ff46cf54Smckusick ep->e_framecnt = 1;
856*ff46cf54Smckusick ep->e_emask = 1 << ep->e_off;
857*ff46cf54Smckusick ep = &einfo[ep->e_frameindex];
858*ff46cf54Smckusick do {
859*ff46cf54Smckusick ep->e_framecnt = 1;
860*ff46cf54Smckusick ep->e_emask = 1 << ep->e_off;
861*ff46cf54Smckusick ep = &einfo[ep->e_frameindex];
862*ff46cf54Smckusick } while (ep > nep);
863*ff46cf54Smckusick } while (ep != einfo);
8648af5b582Smckusick }
865*ff46cf54Smckusick
866*ff46cf54Smckusick /* check all the frames for completion spots */
867*ff46cf54Smckusick for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) {
868*ff46cf54Smckusick /* skip this frame if there are no incomplete spots in it */
869*ff46cf54Smckusick if ((emask = ep->e_emask) == 0)
870*ff46cf54Smckusick continue;
871*ff46cf54Smckusick cbp = *cbpp;
872*ff46cf54Smckusick sp = &board[cbp->c_vertex];
873*ff46cf54Smckusick d = dd[cbp->c_dir];
874*ff46cf54Smckusick for (s = 0, m = 1; s < 5; s++, sp += d, m <<= 1) {
875*ff46cf54Smckusick if (sp->s_occ != EMPTY || !(emask & m))
8768af5b582Smckusick continue;
8778af5b582Smckusick
8788af5b582Smckusick /* add the combo to the list of empty spots */
879*ff46cf54Smckusick nep = (struct elist *)malloc(sizeof(struct elist));
880*ff46cf54Smckusick nep->e_combo = ocbp;
881*ff46cf54Smckusick nep->e_off = s;
882*ff46cf54Smckusick nep->e_frameindex = i;
883*ff46cf54Smckusick if (ep->e_framecnt > 1) {
884*ff46cf54Smckusick nep->e_framecnt = ep->e_framecnt - 1;
885*ff46cf54Smckusick nep->e_emask = emask & ~m;
886*ff46cf54Smckusick } else {
887*ff46cf54Smckusick nep->e_framecnt = 0;
888*ff46cf54Smckusick nep->e_emask = 0;
889*ff46cf54Smckusick }
890*ff46cf54Smckusick nep->e_fval.s = ep->e_fval.s;
8918af5b582Smckusick if (debug > 2) {
892*ff46cf54Smckusick sprintf(fmtbuf, "e %s o%d i%d c%d m%x %x",
893*ff46cf54Smckusick stoc(sp - board),
894*ff46cf54Smckusick nep->e_off,
895*ff46cf54Smckusick nep->e_frameindex,
896*ff46cf54Smckusick nep->e_framecnt,
897*ff46cf54Smckusick nep->e_emask,
898*ff46cf54Smckusick nep->e_fval.s);
8998af5b582Smckusick dlog(fmtbuf);
9008af5b582Smckusick }
9018af5b582Smckusick
9028af5b582Smckusick /* sort by the number of frames in the combo */
903*ff46cf54Smckusick nep->e_next = sp->s_nempty;
904*ff46cf54Smckusick sp->s_nempty = nep;
905*ff46cf54Smckusick elistcnt++;
9068af5b582Smckusick }
9078af5b582Smckusick }
9088af5b582Smckusick }
9098af5b582Smckusick
9108af5b582Smckusick /*
9118af5b582Smckusick * Update the board value based on the combostr.
9128af5b582Smckusick * This is called only if 'cbp' is a <1,x> combo.
9138af5b582Smckusick * We handle things differently depending on whether the next move
9148af5b582Smckusick * would be trying to "complete" the combo or trying to block it.
9158af5b582Smckusick */
9168af5b582Smckusick updatecombo(cbp, color)
9178af5b582Smckusick struct combostr *cbp;
9188af5b582Smckusick int color;
9198af5b582Smckusick {
9208af5b582Smckusick register struct framestr *fp;
9218af5b582Smckusick register struct spotstr *sp;
9228af5b582Smckusick register struct combostr *tcbp;
9238af5b582Smckusick register int i, d;
924*ff46cf54Smckusick int nframes, flg, s;
925*ff46cf54Smckusick union comboval cb;
926*ff46cf54Smckusick
927*ff46cf54Smckusick /* save the top level value for the whole combo */
928*ff46cf54Smckusick cb.c.a = cbp->c_combo.c.a;
929*ff46cf54Smckusick nframes = cbp->c_nframes;
930*ff46cf54Smckusick
931*ff46cf54Smckusick if (color != nextcolor)
932*ff46cf54Smckusick memset(tmpmap, 0, sizeof(tmpmap));
9338af5b582Smckusick
9348af5b582Smckusick for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
935*ff46cf54Smckusick flg = cbp->c_flg;
936*ff46cf54Smckusick cb.c.b = cbp->c_combo.c.b;
9378af5b582Smckusick if (color == nextcolor) {
9388af5b582Smckusick /* update the board value for the vertex */
9398af5b582Smckusick sp = &board[cbp->c_vertex];
9408af5b582Smckusick sp->s_nforce[color]++;
941*ff46cf54Smckusick if (cb.s <= sp->s_combo[color].s) {
942*ff46cf54Smckusick if (cb.s != sp->s_combo[color].s) {
9438af5b582Smckusick sp->s_combo[color].s = cb.s;
9448af5b582Smckusick sp->s_level[color] = nframes;
945*ff46cf54Smckusick } else if (nframes < sp->s_level[color])
9468af5b582Smckusick sp->s_level[color] = nframes;
9478af5b582Smckusick }
948*ff46cf54Smckusick } else {
949*ff46cf54Smckusick /* update the board values for each spot in frame */
950*ff46cf54Smckusick sp = &board[s = tcbp->c_vertex];
951*ff46cf54Smckusick d = dd[tcbp->c_dir];
952*ff46cf54Smckusick i = (flg & C_OPEN_1) ? 6 : 5;
953*ff46cf54Smckusick for (; --i >= 0; sp += d, s += d) {
954*ff46cf54Smckusick if (sp->s_occ != EMPTY)
955*ff46cf54Smckusick continue;
956*ff46cf54Smckusick sp->s_nforce[color]++;
957*ff46cf54Smckusick if (cb.s <= sp->s_combo[color].s) {
958*ff46cf54Smckusick if (cb.s != sp->s_combo[color].s) {
959*ff46cf54Smckusick sp->s_combo[color].s = cb.s;
960*ff46cf54Smckusick sp->s_level[color] = nframes;
961*ff46cf54Smckusick } else if (nframes < sp->s_level[color])
962*ff46cf54Smckusick sp->s_level[color] = nframes;
963*ff46cf54Smckusick }
964*ff46cf54Smckusick BIT_SET(tmpmap, s);
965*ff46cf54Smckusick }
9668af5b582Smckusick }
9678af5b582Smckusick
9688af5b582Smckusick /* mark the frame as being part of a <1,x> combo */
9698af5b582Smckusick board[tcbp->c_vertex].s_flg |= FFLAG << tcbp->c_dir;
9708af5b582Smckusick }
9718af5b582Smckusick
9728af5b582Smckusick if (color != nextcolor) {
9738af5b582Smckusick /* update the board values for each spot in frame */
974*ff46cf54Smckusick sp = &board[s = cbp->c_vertex];
9758af5b582Smckusick d = dd[cbp->c_dir];
976*ff46cf54Smckusick i = (flg & C_OPEN_0) ? 6 : 5;
977*ff46cf54Smckusick for (; --i >= 0; sp += d, s += d) {
978*ff46cf54Smckusick if (sp->s_occ != EMPTY)
979*ff46cf54Smckusick continue;
9808af5b582Smckusick sp->s_nforce[color]++;
981*ff46cf54Smckusick if (cb.s <= sp->s_combo[color].s) {
982*ff46cf54Smckusick if (cb.s != sp->s_combo[color].s) {
9838af5b582Smckusick sp->s_combo[color].s = cb.s;
9848af5b582Smckusick sp->s_level[color] = nframes;
985*ff46cf54Smckusick } else if (nframes < sp->s_level[color])
9868af5b582Smckusick sp->s_level[color] = nframes;
9878af5b582Smckusick }
988*ff46cf54Smckusick BIT_SET(tmpmap, s);
989*ff46cf54Smckusick }
990*ff46cf54Smckusick if (nforce == 0)
991*ff46cf54Smckusick memcpy(forcemap, tmpmap, sizeof(tmpmap));
992*ff46cf54Smckusick else {
993*ff46cf54Smckusick for (i = 0; i < MAPSZ; i++)
994*ff46cf54Smckusick forcemap[i] &= tmpmap[i];
995*ff46cf54Smckusick }
996*ff46cf54Smckusick nforce++;
9978af5b582Smckusick }
9988af5b582Smckusick
9998af5b582Smckusick /* mark the frame as being part of a <1,x> combo */
10008af5b582Smckusick board[cbp->c_vertex].s_flg |= FFLAG << cbp->c_dir;
10018af5b582Smckusick }
10028af5b582Smckusick
10038af5b582Smckusick /*
10048af5b582Smckusick * Add combo to the end of the list.
10058af5b582Smckusick */
10068af5b582Smckusick appendcombo(cbp, color)
10078af5b582Smckusick struct combostr *cbp;
10088af5b582Smckusick int color;
10098af5b582Smckusick {
10108af5b582Smckusick struct combostr *pcbp, *ncbp;
10118af5b582Smckusick
1012*ff46cf54Smckusick combolen++;
1013*ff46cf54Smckusick ncbp = sortcombos;
10148af5b582Smckusick if (ncbp == (struct combostr *)0) {
1015*ff46cf54Smckusick sortcombos = cbp;
10168af5b582Smckusick cbp->c_next = cbp;
10178af5b582Smckusick cbp->c_prev = cbp;
10188af5b582Smckusick return;
10198af5b582Smckusick }
10208af5b582Smckusick pcbp = ncbp->c_prev;
10218af5b582Smckusick cbp->c_next = ncbp;
10228af5b582Smckusick cbp->c_prev = pcbp;
10238af5b582Smckusick ncbp->c_prev = cbp;
10248af5b582Smckusick pcbp->c_next = cbp;
10258af5b582Smckusick }
10268af5b582Smckusick
10278af5b582Smckusick /*
1028*ff46cf54Smckusick * Return zero if it is valid to combine frame 'fcbp' with the frames
1029*ff46cf54Smckusick * in 'cbp' and forms a linked chain of frames (i.e., a tree; no loops).
1030*ff46cf54Smckusick * Return positive if combining frame 'fcbp' to the frames in 'cbp'
1031*ff46cf54Smckusick * would form some kind of valid loop. Also return the intersection spots
1032*ff46cf54Smckusick * in 'vertices[]' beside the known intersection at spot 'osp'.
1033*ff46cf54Smckusick * Return -1 if 'fcbp' should not be combined with 'cbp'.
1034*ff46cf54Smckusick * 's' is the combo value for frame 'fcpb'.
10358af5b582Smckusick */
1036*ff46cf54Smckusick checkframes(cbp, fcbp, osp, s, vertices)
10378af5b582Smckusick struct combostr *cbp;
10388af5b582Smckusick struct combostr *fcbp;
1039*ff46cf54Smckusick struct spotstr *osp;
1040*ff46cf54Smckusick int s;
1041*ff46cf54Smckusick struct ovlp_info *vertices;
10428af5b582Smckusick {
1043*ff46cf54Smckusick struct combostr *tcbp, *lcbp;
1044*ff46cf54Smckusick int i, n, mask, flg, verts, loop, index, fcnt;
1045*ff46cf54Smckusick union comboval cb;
1046*ff46cf54Smckusick u_char *str;
10478af5b582Smckusick short *ip;
10488af5b582Smckusick
1049*ff46cf54Smckusick cb.s = s;
1050*ff46cf54Smckusick fcnt = cb.c.a - 2;
1051*ff46cf54Smckusick verts = 0;
1052*ff46cf54Smckusick loop = 0;
1053*ff46cf54Smckusick index = cbp->c_nframes;
10548af5b582Smckusick n = (fcbp - frames) * FAREA;
10558af5b582Smckusick str = &overlap[n];
10568af5b582Smckusick ip = &intersect[n];
1057*ff46cf54Smckusick /*
1058*ff46cf54Smckusick * i == which overlap bit to test based on whether 'fcbp' is
1059*ff46cf54Smckusick * an open or closed frame.
1060*ff46cf54Smckusick */
1061*ff46cf54Smckusick i = cb.c.b ? 2 : 0;
1062*ff46cf54Smckusick for (; tcbp = cbp->c_link[1]; lcbp = cbp, cbp = cbp->c_link[0]) {
1063*ff46cf54Smckusick if (tcbp == fcbp)
1064*ff46cf54Smckusick return (-1); /* fcbp is already included */
1065*ff46cf54Smckusick
1066*ff46cf54Smckusick /* check for intersection of 'tcbp' with 'fcbp' */
1067*ff46cf54Smckusick index--;
1068*ff46cf54Smckusick mask = str[tcbp - frames];
1069*ff46cf54Smckusick flg = cbp->c_flg;
1070*ff46cf54Smckusick n = i + ((flg & C_OPEN_1) != 0);
1071*ff46cf54Smckusick if (mask & (1 << n)) {
1072*ff46cf54Smckusick /*
1073*ff46cf54Smckusick * The two frames are not independent if they
1074*ff46cf54Smckusick * both lie in the same line and intersect at
1075*ff46cf54Smckusick * more than one point.
1076*ff46cf54Smckusick */
1077*ff46cf54Smckusick if (tcbp->c_dir == fcbp->c_dir && (mask & (0x10 << n)))
10788af5b582Smckusick return (-1);
1079*ff46cf54Smckusick /*
1080*ff46cf54Smckusick * If this is not the spot we are attaching
1081*ff46cf54Smckusick * 'fcbp' to and it is a reasonable intersection
1082*ff46cf54Smckusick * spot, then there might be a loop.
1083*ff46cf54Smckusick */
1084*ff46cf54Smckusick n = ip[tcbp - frames];
1085*ff46cf54Smckusick if (osp != &board[n]) {
1086*ff46cf54Smckusick /* check to see if this is a valid loop */
1087*ff46cf54Smckusick if (verts)
1088*ff46cf54Smckusick return (-1);
1089*ff46cf54Smckusick if (fcnt == 0 || cbp->c_framecnt[1] == 0)
1090*ff46cf54Smckusick return (-1);
1091*ff46cf54Smckusick /*
1092*ff46cf54Smckusick * Check to be sure the intersection is not
1093*ff46cf54Smckusick * one of the end points if it is an open
1094*ff46cf54Smckusick * ended frame.
1095*ff46cf54Smckusick */
1096*ff46cf54Smckusick if ((flg & C_OPEN_1) &&
1097*ff46cf54Smckusick (n == tcbp->c_vertex ||
1098*ff46cf54Smckusick n == tcbp->c_vertex + 5 * dd[tcbp->c_dir]))
1099*ff46cf54Smckusick return (-1); /* invalid overlap */
1100*ff46cf54Smckusick if (cb.c.b &&
1101*ff46cf54Smckusick (n == fcbp->c_vertex ||
1102*ff46cf54Smckusick n == fcbp->c_vertex + 5 * dd[fcbp->c_dir]))
1103*ff46cf54Smckusick return (-1); /* invalid overlap */
1104*ff46cf54Smckusick
1105*ff46cf54Smckusick vertices->o_intersect = n;
1106*ff46cf54Smckusick vertices->o_fcombo = cbp;
1107*ff46cf54Smckusick vertices->o_link = 1;
1108*ff46cf54Smckusick vertices->o_off = (n - tcbp->c_vertex) /
1109*ff46cf54Smckusick dd[tcbp->c_dir];
1110*ff46cf54Smckusick vertices->o_frameindex = index;
1111*ff46cf54Smckusick verts++;
11128af5b582Smckusick }
1113*ff46cf54Smckusick }
1114*ff46cf54Smckusick n = i + ((flg & C_OPEN_0) != 0);
1115*ff46cf54Smckusick }
1116*ff46cf54Smckusick if (cbp == fcbp)
1117*ff46cf54Smckusick return (-1); /* fcbp is already included */
1118*ff46cf54Smckusick
1119*ff46cf54Smckusick /* check for intersection of 'cbp' with 'fcbp' */
1120*ff46cf54Smckusick mask = str[cbp - frames];
1121*ff46cf54Smckusick if (mask & (1 << n)) {
1122*ff46cf54Smckusick /*
1123*ff46cf54Smckusick * The two frames are not independent if they
1124*ff46cf54Smckusick * both lie in the same line and intersect at
1125*ff46cf54Smckusick * more than one point.
1126*ff46cf54Smckusick */
1127*ff46cf54Smckusick if (cbp->c_dir == fcbp->c_dir && (mask & (0x10 << n)))
11288af5b582Smckusick return (-1);
1129*ff46cf54Smckusick /*
1130*ff46cf54Smckusick * If this is not the spot we are attaching
1131*ff46cf54Smckusick * 'fcbp' to and it is a reasonable intersection
1132*ff46cf54Smckusick * spot, then there might be a loop.
1133*ff46cf54Smckusick */
1134*ff46cf54Smckusick n = ip[cbp - frames];
1135*ff46cf54Smckusick if (osp != &board[n]) {
1136*ff46cf54Smckusick /* check to see if this is a valid loop */
1137*ff46cf54Smckusick if (verts)
1138*ff46cf54Smckusick return (-1);
1139*ff46cf54Smckusick if (fcnt == 0 || lcbp->c_framecnt[0] == 0)
1140*ff46cf54Smckusick return (-1);
1141*ff46cf54Smckusick /*
1142*ff46cf54Smckusick * Check to be sure the intersection is not
1143*ff46cf54Smckusick * one of the end points if it is an open
1144*ff46cf54Smckusick * ended frame.
1145*ff46cf54Smckusick */
1146*ff46cf54Smckusick if ((flg & C_OPEN_0) &&
1147*ff46cf54Smckusick (n == cbp->c_vertex ||
1148*ff46cf54Smckusick n == cbp->c_vertex + 5 * dd[cbp->c_dir]))
1149*ff46cf54Smckusick return (-1); /* invalid overlap */
1150*ff46cf54Smckusick if (cb.c.b &&
1151*ff46cf54Smckusick (n == fcbp->c_vertex ||
1152*ff46cf54Smckusick n == fcbp->c_vertex + 5 * dd[fcbp->c_dir]))
1153*ff46cf54Smckusick return (-1); /* invalid overlap */
1154*ff46cf54Smckusick
1155*ff46cf54Smckusick vertices->o_intersect = n;
1156*ff46cf54Smckusick vertices->o_fcombo = lcbp;
1157*ff46cf54Smckusick vertices->o_link = 0;
1158*ff46cf54Smckusick vertices->o_off = (n - cbp->c_vertex) /
1159*ff46cf54Smckusick dd[cbp->c_dir];
1160*ff46cf54Smckusick vertices->o_frameindex = 0;
1161*ff46cf54Smckusick verts++;
1162*ff46cf54Smckusick }
1163*ff46cf54Smckusick }
1164*ff46cf54Smckusick return (verts);
1165*ff46cf54Smckusick }
1166*ff46cf54Smckusick
1167*ff46cf54Smckusick /*
1168*ff46cf54Smckusick * Merge sort the frame 'fcbp' and the sorted list of frames 'cbpp' and
1169*ff46cf54Smckusick * store the result in 'scbpp'. 'curlevel' is the size of the 'cbpp' array.
1170*ff46cf54Smckusick * Return true if this list of frames is already in the hash list.
1171*ff46cf54Smckusick * Otherwise, add the new combo to the hash list.
1172*ff46cf54Smckusick */
1173*ff46cf54Smckusick sortcombo(scbpp, cbpp, fcbp)
1174*ff46cf54Smckusick struct combostr **scbpp;
1175*ff46cf54Smckusick struct combostr **cbpp;
1176*ff46cf54Smckusick struct combostr *fcbp;
1177*ff46cf54Smckusick {
1178*ff46cf54Smckusick struct combostr **spp, **cpp;
1179*ff46cf54Smckusick struct combostr *cbp, *ecbp;
1180*ff46cf54Smckusick int n, inx;
1181*ff46cf54Smckusick
1182*ff46cf54Smckusick #ifdef DEBUG
1183*ff46cf54Smckusick if (debug > 3) {
1184*ff46cf54Smckusick char *str;
1185*ff46cf54Smckusick
1186*ff46cf54Smckusick sprintf(fmtbuf, "sortc: %s%c l%d", stoc(fcbp->c_vertex),
1187*ff46cf54Smckusick pdir[fcbp->c_dir], curlevel);
1188*ff46cf54Smckusick dlog(fmtbuf);
1189*ff46cf54Smckusick str = fmtbuf;
1190*ff46cf54Smckusick for (cpp = cbpp; cpp < cbpp + curlevel; cpp++) {
1191*ff46cf54Smckusick sprintf(str, " %s%c", stoc((*cpp)->c_vertex),
1192*ff46cf54Smckusick pdir[(*cpp)->c_dir]);
1193*ff46cf54Smckusick str += strlen(str);
1194*ff46cf54Smckusick }
1195*ff46cf54Smckusick dlog(fmtbuf);
1196*ff46cf54Smckusick }
1197*ff46cf54Smckusick #endif /* DEBUG */
1198*ff46cf54Smckusick
1199*ff46cf54Smckusick /* first build the new sorted list */
1200*ff46cf54Smckusick n = curlevel + 1;
1201*ff46cf54Smckusick spp = scbpp + n;
1202*ff46cf54Smckusick cpp = cbpp + curlevel;
1203*ff46cf54Smckusick do {
1204*ff46cf54Smckusick cpp--;
1205*ff46cf54Smckusick if (fcbp > *cpp) {
1206*ff46cf54Smckusick *--spp = fcbp;
1207*ff46cf54Smckusick do
1208*ff46cf54Smckusick *--spp = *cpp;
1209*ff46cf54Smckusick while (cpp-- != cbpp);
1210*ff46cf54Smckusick goto inserted;
1211*ff46cf54Smckusick }
1212*ff46cf54Smckusick *--spp = *cpp;
1213*ff46cf54Smckusick } while (cpp != cbpp);
1214*ff46cf54Smckusick *--spp = fcbp;
1215*ff46cf54Smckusick inserted:
1216*ff46cf54Smckusick
1217*ff46cf54Smckusick /* now check to see if this list of frames has already been seen */
1218*ff46cf54Smckusick cbp = hashcombos[inx = *scbpp - frames];
1219*ff46cf54Smckusick if (cbp == (struct combostr *)0) {
1220*ff46cf54Smckusick /*
1221*ff46cf54Smckusick * Easy case, this list hasn't been seen.
1222*ff46cf54Smckusick * Add it to the hash list.
1223*ff46cf54Smckusick */
1224*ff46cf54Smckusick fcbp = (struct combostr *)
1225*ff46cf54Smckusick ((char *)scbpp - sizeof(struct combostr));
1226*ff46cf54Smckusick hashcombos[inx] = fcbp;
1227*ff46cf54Smckusick fcbp->c_next = fcbp->c_prev = fcbp;
12288af5b582Smckusick return (0);
1229*ff46cf54Smckusick }
1230*ff46cf54Smckusick ecbp = cbp;
1231*ff46cf54Smckusick do {
1232*ff46cf54Smckusick cbpp = (struct combostr **)(cbp + 1);
1233*ff46cf54Smckusick cpp = cbpp + n;
1234*ff46cf54Smckusick spp = scbpp + n;
1235*ff46cf54Smckusick cbpp++; /* first frame is always the same */
1236*ff46cf54Smckusick do {
1237*ff46cf54Smckusick if (*--spp != *--cpp)
1238*ff46cf54Smckusick goto next;
1239*ff46cf54Smckusick } while (cpp != cbpp);
1240*ff46cf54Smckusick /* we found a match */
1241*ff46cf54Smckusick #ifdef DEBUG
1242*ff46cf54Smckusick if (debug > 3) {
1243*ff46cf54Smckusick char *str;
1244*ff46cf54Smckusick
1245*ff46cf54Smckusick sprintf(fmtbuf, "sort1: n%d", n);
1246*ff46cf54Smckusick dlog(fmtbuf);
1247*ff46cf54Smckusick str = fmtbuf;
1248*ff46cf54Smckusick for (cpp = scbpp; cpp < scbpp + n; cpp++) {
1249*ff46cf54Smckusick sprintf(str, " %s%c", stoc((*cpp)->c_vertex),
1250*ff46cf54Smckusick pdir[(*cpp)->c_dir]);
1251*ff46cf54Smckusick str += strlen(str);
1252*ff46cf54Smckusick }
1253*ff46cf54Smckusick dlog(fmtbuf);
1254*ff46cf54Smckusick printcombo(cbp, fmtbuf);
1255*ff46cf54Smckusick dlog(fmtbuf);
1256*ff46cf54Smckusick str = fmtbuf;
1257*ff46cf54Smckusick cbpp--;
1258*ff46cf54Smckusick for (cpp = cbpp; cpp < cbpp + n; cpp++) {
1259*ff46cf54Smckusick sprintf(str, " %s%c", stoc((*cpp)->c_vertex),
1260*ff46cf54Smckusick pdir[(*cpp)->c_dir]);
1261*ff46cf54Smckusick str += strlen(str);
1262*ff46cf54Smckusick }
1263*ff46cf54Smckusick dlog(fmtbuf);
1264*ff46cf54Smckusick }
1265*ff46cf54Smckusick #endif /* DEBUG */
1266*ff46cf54Smckusick return (1);
1267*ff46cf54Smckusick next:
1268*ff46cf54Smckusick ;
1269*ff46cf54Smckusick } while ((cbp = cbp->c_next) != ecbp);
1270*ff46cf54Smckusick /*
1271*ff46cf54Smckusick * This list of frames hasn't been seen.
1272*ff46cf54Smckusick * Add it to the hash list.
1273*ff46cf54Smckusick */
1274*ff46cf54Smckusick ecbp = cbp->c_prev;
1275*ff46cf54Smckusick fcbp = (struct combostr *)((char *)scbpp - sizeof(struct combostr));
1276*ff46cf54Smckusick fcbp->c_next = cbp;
1277*ff46cf54Smckusick fcbp->c_prev = ecbp;
1278*ff46cf54Smckusick cbp->c_prev = fcbp;
1279*ff46cf54Smckusick ecbp->c_next = fcbp;
12808af5b582Smckusick return (0);
1281*ff46cf54Smckusick }
1282*ff46cf54Smckusick
1283*ff46cf54Smckusick /*
1284*ff46cf54Smckusick * Print the combo into string 'str'.
1285*ff46cf54Smckusick */
1286*ff46cf54Smckusick printcombo(cbp, str)
1287*ff46cf54Smckusick struct combostr *cbp;
1288*ff46cf54Smckusick char *str;
1289*ff46cf54Smckusick {
1290*ff46cf54Smckusick struct combostr *tcbp;
1291*ff46cf54Smckusick
1292*ff46cf54Smckusick sprintf(str, "%x/%d", cbp->c_combo.s, cbp->c_nframes);
1293*ff46cf54Smckusick str += strlen(str);
1294*ff46cf54Smckusick for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
1295*ff46cf54Smckusick sprintf(str, " %s%c%x", stoc(tcbp->c_vertex), pdir[tcbp->c_dir],
1296*ff46cf54Smckusick cbp->c_flg);
1297*ff46cf54Smckusick str += strlen(str);
1298*ff46cf54Smckusick }
1299*ff46cf54Smckusick sprintf(str, " %s%c", stoc(cbp->c_vertex), pdir[cbp->c_dir]);
13008af5b582Smckusick }
13018af5b582Smckusick
13028af5b582Smckusick #ifdef DEBUG
1303*ff46cf54Smckusick markcombo(ocbp)
1304*ff46cf54Smckusick struct combostr *ocbp;
13058af5b582Smckusick {
1306*ff46cf54Smckusick struct combostr *cbp, *tcbp, **cbpp;
1307*ff46cf54Smckusick struct elist *ep, *nep, **epp;
1308*ff46cf54Smckusick struct spotstr *sp;
1309*ff46cf54Smckusick int s, d, m, i;
1310*ff46cf54Smckusick int nframes;
1311*ff46cf54Smckusick int r, n, flg, cmask, omask;
13128af5b582Smckusick
1313*ff46cf54Smckusick /* should never happen but check anyway */
1314*ff46cf54Smckusick if ((nframes = ocbp->c_nframes) >= MAXDEPTH)
1315*ff46cf54Smckusick return;
1316*ff46cf54Smckusick
1317*ff46cf54Smckusick /*
1318*ff46cf54Smckusick * The lower level combo can be pointed to by more than one
1319*ff46cf54Smckusick * higher level 'struct combostr' so we can't modify the
1320*ff46cf54Smckusick * lower level. Therefore, higher level combos store the
1321*ff46cf54Smckusick * real mask of the lower level frame in c_emask[0] and the
1322*ff46cf54Smckusick * frame number in c_frameindex.
1323*ff46cf54Smckusick *
1324*ff46cf54Smckusick * First we traverse the tree from top to bottom and save the
1325*ff46cf54Smckusick * connection info. Then we traverse the tree from bottom to
1326*ff46cf54Smckusick * top overwriting lower levels with the newer emask information.
1327*ff46cf54Smckusick */
1328*ff46cf54Smckusick ep = &einfo[nframes];
1329*ff46cf54Smckusick cbpp = &ecombo[nframes];
1330*ff46cf54Smckusick for (cbp = ocbp; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
1331*ff46cf54Smckusick ep--;
1332*ff46cf54Smckusick ep->e_combo = cbp;
1333*ff46cf54Smckusick *--cbpp = cbp->c_link[1];
1334*ff46cf54Smckusick ep->e_off = cbp->c_voff[1];
1335*ff46cf54Smckusick ep->e_frameindex = cbp->c_frameindex;
1336*ff46cf54Smckusick ep->e_fval.s = cbp->c_linkv[1].s;
1337*ff46cf54Smckusick ep->e_framecnt = cbp->c_framecnt[1];
1338*ff46cf54Smckusick ep->e_emask = cbp->c_emask[1];
1339*ff46cf54Smckusick }
1340*ff46cf54Smckusick cbp = ep->e_combo;
1341*ff46cf54Smckusick ep--;
1342*ff46cf54Smckusick ep->e_combo = cbp;
1343*ff46cf54Smckusick *--cbpp = cbp->c_link[0];
1344*ff46cf54Smckusick ep->e_off = cbp->c_voff[0];
1345*ff46cf54Smckusick ep->e_frameindex = 0;
1346*ff46cf54Smckusick ep->e_fval.s = cbp->c_linkv[0].s;
1347*ff46cf54Smckusick ep->e_framecnt = cbp->c_framecnt[0];
1348*ff46cf54Smckusick ep->e_emask = cbp->c_emask[0];
1349*ff46cf54Smckusick
1350*ff46cf54Smckusick /* now update the emask info */
1351*ff46cf54Smckusick s = 0;
1352*ff46cf54Smckusick for (i = 2, ep += 2; i < nframes; i++, ep++) {
1353*ff46cf54Smckusick cbp = ep->e_combo;
1354*ff46cf54Smckusick nep = &einfo[ep->e_frameindex];
1355*ff46cf54Smckusick nep->e_framecnt = cbp->c_framecnt[0];
1356*ff46cf54Smckusick nep->e_emask = cbp->c_emask[0];
1357*ff46cf54Smckusick
1358*ff46cf54Smckusick if (cbp->c_flg & C_LOOP) {
1359*ff46cf54Smckusick s++;
1360*ff46cf54Smckusick /*
1361*ff46cf54Smckusick * Account for the fact that this frame connects
1362*ff46cf54Smckusick * to a previous one (thus forming a loop).
1363*ff46cf54Smckusick */
1364*ff46cf54Smckusick nep = &einfo[cbp->c_dir];
1365*ff46cf54Smckusick if (--nep->e_framecnt)
1366*ff46cf54Smckusick nep->e_emask &= ~(1 << cbp->c_voff[0]);
13678af5b582Smckusick else
1368*ff46cf54Smckusick nep->e_emask = 0;
13698af5b582Smckusick }
13708af5b582Smckusick }
13718af5b582Smckusick
1372*ff46cf54Smckusick /*
1373*ff46cf54Smckusick * We only need to update the emask values of "complete" loops
1374*ff46cf54Smckusick * to include the intersection spots.
1375*ff46cf54Smckusick */
1376*ff46cf54Smckusick if (s && ocbp->c_combo.c.a == 2) {
1377*ff46cf54Smckusick /* process loops from the top down */
1378*ff46cf54Smckusick ep = &einfo[nframes];
1379*ff46cf54Smckusick do {
1380*ff46cf54Smckusick ep--;
1381*ff46cf54Smckusick cbp = ep->e_combo;
1382*ff46cf54Smckusick if (!(cbp->c_flg & C_LOOP))
1383*ff46cf54Smckusick continue;
1384*ff46cf54Smckusick
1385*ff46cf54Smckusick /*
1386*ff46cf54Smckusick * Update the emask values to include the
1387*ff46cf54Smckusick * intersection spots.
1388*ff46cf54Smckusick */
1389*ff46cf54Smckusick nep = &einfo[cbp->c_dir];
1390*ff46cf54Smckusick nep->e_framecnt = 1;
1391*ff46cf54Smckusick nep->e_emask = 1 << cbp->c_voff[0];
1392*ff46cf54Smckusick ep->e_framecnt = 1;
1393*ff46cf54Smckusick ep->e_emask = 1 << ep->e_off;
1394*ff46cf54Smckusick ep = &einfo[ep->e_frameindex];
1395*ff46cf54Smckusick do {
1396*ff46cf54Smckusick ep->e_framecnt = 1;
1397*ff46cf54Smckusick ep->e_emask = 1 << ep->e_off;
1398*ff46cf54Smckusick ep = &einfo[ep->e_frameindex];
1399*ff46cf54Smckusick } while (ep > nep);
1400*ff46cf54Smckusick } while (ep != einfo);
1401*ff46cf54Smckusick }
1402*ff46cf54Smckusick
1403*ff46cf54Smckusick /* mark all the frames with the completion spots */
1404*ff46cf54Smckusick for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) {
1405*ff46cf54Smckusick m = ep->e_emask;
1406*ff46cf54Smckusick cbp = *cbpp;
1407*ff46cf54Smckusick sp = &board[cbp->c_vertex];
1408*ff46cf54Smckusick d = dd[s = cbp->c_dir];
1409*ff46cf54Smckusick cmask = CFLAG << s;
1410*ff46cf54Smckusick omask = (IFLAG | CFLAG) << s;
1411*ff46cf54Smckusick s = ep->e_fval.c.b ? 6 : 5;
1412*ff46cf54Smckusick for (; --s >= 0; sp += d, m >>= 1)
1413*ff46cf54Smckusick sp->s_flg |= (m & 1) ? omask : cmask;
1414*ff46cf54Smckusick }
1415*ff46cf54Smckusick }
1416*ff46cf54Smckusick
1417*ff46cf54Smckusick clearcombo(cbp, open)
14188af5b582Smckusick struct combostr *cbp;
1419*ff46cf54Smckusick int open;
14208af5b582Smckusick {
14218af5b582Smckusick register struct spotstr *sp;
14228af5b582Smckusick struct combostr *tcbp;
1423*ff46cf54Smckusick int d, n, mask;
14248af5b582Smckusick
1425*ff46cf54Smckusick for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
1426*ff46cf54Smckusick clearcombo(tcbp, cbp->c_flg & C_OPEN_1);
1427*ff46cf54Smckusick open = cbp->c_flg & C_OPEN_0;
1428*ff46cf54Smckusick }
14298af5b582Smckusick sp = &board[cbp->c_vertex];
1430*ff46cf54Smckusick d = dd[n = cbp->c_dir];
1431*ff46cf54Smckusick mask = ~((IFLAG | CFLAG) << n);
1432*ff46cf54Smckusick n = open ? 6 : 5;
1433*ff46cf54Smckusick for (; --n >= 0; sp += d)
14348af5b582Smckusick sp->s_flg &= mask;
14358af5b582Smckusick }
1436*ff46cf54Smckusick
1437*ff46cf54Smckusick list_eq(scbpp, cbpp, n)
1438*ff46cf54Smckusick struct combostr **scbpp;
1439*ff46cf54Smckusick struct combostr **cbpp;
1440*ff46cf54Smckusick int n;
1441*ff46cf54Smckusick {
1442*ff46cf54Smckusick struct combostr **spp, **cpp;
1443*ff46cf54Smckusick
1444*ff46cf54Smckusick spp = scbpp + n;
1445*ff46cf54Smckusick cpp = cbpp + n;
1446*ff46cf54Smckusick do {
1447*ff46cf54Smckusick if (*--spp != *--cpp)
1448*ff46cf54Smckusick return (0);
1449*ff46cf54Smckusick } while (cpp != cbpp);
1450*ff46cf54Smckusick /* we found a match */
1451*ff46cf54Smckusick return (1);
1452*ff46cf54Smckusick }
14538af5b582Smckusick #endif /* DEBUG */
1454