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