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