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