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