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