gomoku/pickmove.c

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