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