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