Quickscan

diff --git a/backend.c b/backend.c
index 9259013..e235dc1 100644 (file)
--- a/backend.c
+++ b/backend.c
@@ -11173,6 +11173,130 @@ PositionMatches(Board b1, Board b2)
     return TRUE;
 }
 
+#define Q_PROMO  4
+#define Q_EP     3
+#define Q_WCASTL 2
+#define Q_BCASTL 1
+
+int pieceList[256], quickBoard[256];
+ChessSquare pieceType[256] = { EmptySquare };
+Board soughtBoard, reverseBoard;
+int counts[EmptySquare], soughtCounts[EmptySquare], reverseCounts[EmptySquare], maxSought[EmptySquare], maxReverse[EmptySquare];
+
+typedef struct {
+    unsigned char piece, to;
+} Move;
+
+Move moveDatabase[4000000];
+int movePtr = 0;
+
+void MakePieceList(Board board, int *counts)
+{
+    int r, f, n=Q_PROMO;
+    for(r=0;r<EmptySquare;r++) counts[r] = 0; // piece-type counts
+    for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
+       int sq = f + (r<<4);
+        if(board[r][f] == EmptySquare) quickBoard[sq] = 0; else {
+           quickBoard[sq] = ++n;
+           pieceList[n] = sq;
+           pieceType[n] = board[r][f];
+           counts[board[r][f]]++;
+           if(board[r][f] == WhiteKing) pieceList[1] = sq; else
+           if(board[r][f] == BlackKing) pieceList[2] = sq; // remember where Kings start, for castling
+       }
+    }
+}
+
+void PackMove(int fromX, int fromY, int toX, int toY, char promoChar)
+{
+    int sq = fromX + (fromY<<4);
+    int piece = quickBoard[sq];
+    quickBoard[sq] = 0;
+    moveDatabase[movePtr].to = pieceList[piece] = sq = toX + (toY<<4);
+    if(promoChar) {
+       
+    }
+    moveDatabase[movePtr].piece = piece;
+    quickBoard[sq] = piece;
+    movePtr++;
+}
+
+int PackGame(Board board)
+{
+    moveDatabase[movePtr++].piece = 0; // terminate previous game
+    MakePieceList(board, counts);
+    return movePtr;
+}
+
+int QuickCompare(Board board, int *counts, int *maxCounts)
+{   // compare according to search mode
+    int r, f;
+    switch(appData.searchMode)
+    {
+      case 1: // exact position match
+       for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
+           if(board[r][f] != pieceType[quickBoard[(r<<4)+f]]) return FALSE;
+       }
+       return TRUE;
+      case 2: // can have extra material on empty squares
+       for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
+           if(board[r][f] == EmptySquare) continue;
+           if(board[r][f] != pieceType[quickBoard[(r<<4)+f]]) return FALSE;
+       }
+       return TRUE;
+      case 3: // material with exact Pawn structure
+       for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
+           if(board[r][f] != WhitePawn && board[r][f] != BlackPawn) continue;
+           if(board[r][f] != pieceType[quickBoard[(r<<4)+f]]) return FALSE;
+       } // fall through to material comparison
+      case 4: // exact material
+       for(r=0; r<EmptySquare; r++) if(counts[r] != soughtCounts[r]) return FALSE;
+       return TRUE;
+      case 5: // material range with given imbalance
+       for(r=0; r<EmptySquare; r++) if(counts[r] < soughtCounts[r] || counts[r] > maxCounts[r]) return FALSE;
+      case 6: // material range
+       for(r=0; r<EmptySquare; r++) if(counts[r] < soughtCounts[r] || counts[r] > maxCounts[r]) return FALSE;
+       return TRUE;
+    }
+}
+
+int QuickScan(Board board, Move *move)
+{   // reconstruct game,and compare all positions in it
+    MakePieceList(board, counts);
+    do {
+       int piece = move->piece;
+       int to = move->to, from = pieceList[piece];
+       if(piece <= Q_PROMO) { // special moves encoded by otherwise invalid piece numbers 1-4
+         if(!piece) return FALSE;
+         if(piece == Q_PROMO) { // promotion, encoded as (Q_PROMO, to) + (piece, promoType)
+           piece = (++move)->piece;
+           from = pieceList[piece];
+           counts[pieceType[piece]]--;
+           pieceType[piece] = (ChessSquare) move->to;
+           counts[move->to]++;
+         } else if(piece == Q_EP) { // e.p. capture, encoded as (Q_EP, ep-sqr) + (piece, to)
+           counts[pieceType[quickBoard[to]]]--;
+           quickBoard[to] = 0;
+           move++;
+           continue;
+         } else if(piece <= Q_BCASTL) { // castling, encoded as (Q_XCASTL, king-to) + (rook, rook-to)
+           from = pieceList[piece]; // first two elements of pieceList contain initial King positions
+           piece = quickBoard[from]; // so this must be King
+           quickBoard[from] = 0;
+           quickBoard[to] = piece;
+           pieceList[piece] = to;
+           continue;
+         }
+       }
+       if(appData.searchMode > 2) counts[pieceType[quickBoard[to]]]--; // account capture
+       quickBoard[from] = 0;
+       quickBoard[to] = piece;
+       pieceList[piece] = to;
+       if(QuickCompare(soughtBoard, soughtCounts, maxSought)) return TRUE;
+       move++;
+    } while(1);
+}
+
 GameInfo dummyInfo;
 
 int GameContainsPosition(FILE *f, ListGame *lg)
@@ -11182,44 +11306,30 @@ int GameContainsPosition(FILE *f, ListGame *lg)
     char promoChar;
     static int initDone=FALSE;
 
+    // weed out games based on numerical tag comparison
+    if(lg->gameInfo.variant != gameInfo.variant) return -1; // wrong variant
+    if(appData.eloThreshold1 && (lg->gameInfo.whiteRating < appData.eloThreshold1 && lg->gameInfo.blackRating < appData.eloThreshold1)) return -1;
+    if(appData.eloThreshold2 && (lg->gameInfo.whiteRating < appData.eloThreshold2 || lg->gameInfo.blackRating < appData.eloThreshold2)) return -1;
+    if(appData.dateThreshold && (!lg->gameInfo.date || atoi(lg->gameInfo.date) < appData.dateThreshold)) return -1;
     if(!initDone) {
        for(next = WhitePawn; next<EmptySquare; next++) keys[next] = random()>>8 ^ random()<<6 ^random()<<20;
        initDone = TRUE;
     }
-    dummyInfo.variant = VariantNormal;
-    FREE(dummyInfo.fen); dummyInfo.fen = NULL;
-    dummyInfo.whiteRating = 0;
-    dummyInfo.blackRating = 0;
-    FREE(dummyInfo.date); dummyInfo.date = NULL;
+    if(lg->gameInfo.fen) ParseFEN(boards[scratch], &btm, lg->gameInfo.fen);
+    else CopyBoard(boards[scratch], initialPosition); // default start position
+    if(lg->moves && !QuickScan( boards[scratch], &moveDatabase[lg->moves] )) return -1; // quick scan rules out it is there
+    if(btm) CopyBoard(boards[scratch+1], boards[scratch]), plyNr++;
+    if(PositionMatches(boards[scratch + plyNr], boards[currentMove])) return plyNr;
     fseek(f, lg->offset, 0);
     yynewfile(f);
-    CopyBoard(boards[scratch], initialPosition); // default start position
     while(1) {
        yyboardindex = scratch + (plyNr&1);
-      quickFlag = 1;
+       quickFlag = 1;
        next = Myylex();
-      quickFlag = 0;
+       quickFlag = 0;
        switch(next) {
            case PGNTag:
                if(plyNr) return -1; // after we have seen moves, any tags will be start of next game
-#if 0
-               ParsePGNTag(yy_text, &dummyInfo); // this has a bad memory leak...
-               if(dummyInfo.fen) ParseFEN(boards[scratch], &btm, dummyInfo.fen), free(dummyInfo.fen), dummyInfo.fen = NULL;
-#else
-               // do it ourselves avoiding malloc
-               { char *p = yy_text+1, *q;
-                 while(!isdigit(*p) && !isalpha(*p)) p++;
-                 q  = p; while(*p != ' ' && *p != '\t' && *p != '\n') p++;
-                 *p = NULLCHAR;
-                 if(!StrCaseCmp(q, "Date") && (p = strchr(p+1, '"'))) { if(atoi(p+1) < appData.dateThreshold) return -1; } else
-                 if(!StrCaseCmp(q, "Variant")  &&  (p = strchr(p+1, '"'))) dummyInfo.variant = StringToVariant(p+1); else
-                 if(!StrCaseCmp(q, "WhiteElo")  && (p = strchr(p+1, '"'))) dummyInfo.whiteRating = atoi(p+1); else
-                 if(!StrCaseCmp(q, "BlackElo")  && (p = strchr(p+1, '"'))) dummyInfo.blackRating = atoi(p+1); else
-                 if(!StrCaseCmp(q, "WhiteUSCF") && (p = strchr(p+1, '"'))) dummyInfo.whiteRating = atoi(p+1); else
-                 if(!StrCaseCmp(q, "BlackUSCF") && (p = strchr(p+1, '"'))) dummyInfo.blackRating = atoi(p+1); else
-                 if(!StrCaseCmp(q, "FEN")  && (p = strchr(p+1, '"'))) ParseFEN(boards[scratch], &btm, p+1);
-               }
-#endif
            default:
                continue;
 
@@ -11274,14 +11384,6 @@ int GameContainsPosition(FILE *f, ListGame *lg)
                break;
        }
        // Move encountered; peform it. We need to shuttle between two boards, as even/odd index determines side to move
-       if(plyNr == 0) { // but first figure out variant and initial position
-           if(dummyInfo.variant != gameInfo.variant) return -1; // wrong variant
-           if(appData.eloThreshold1 && (dummyInfo.whiteRating < appData.eloThreshold1 && dummyInfo.blackRating < appData.eloThreshold1)) return -1;
-           if(appData.eloThreshold2 && (dummyInfo.whiteRating < appData.eloThreshold2 || dummyInfo.blackRating < appData.eloThreshold2)) return -1;
-           if(appData.dateThreshold && (!dummyInfo.date || atoi(dummyInfo.date) < appData.dateThreshold)) return -1;
-           if(btm) CopyBoard(boards[scratch+1], boards[scratch]), plyNr++;
-           if(PositionMatches(boards[scratch + plyNr], boards[currentMove])) return plyNr;
-       }
        CopyBoard(boards[scratch + (plyNr+1&1)], boards[scratch + (plyNr&1)]);
        plyNr++;
        ApplyMove(fromX, fromY, toX, toY, promoChar, boards[scratch + (plyNr&1)]);

diff --git a/backend.h b/backend.h
index 6f08f91..460ae48 100644 (file)
--- a/backend.h
+++ b/backend.h
@@ -280,6 +280,7 @@ typedef struct _ListGame {
     ListNode node;
     int number;
     int position;
+    int moves;
     unsigned long offset;   /*  Byte offset of game within file.     */
     GameInfo gameInfo;      /*  Note that some entries may be NULL. */
 } ListGame;

diff --git a/gamelist.c b/gamelist.c
index a36af7a..712d9b9 100644 (file)
--- a/gamelist.c
+++ b/gamelist.c
@@ -47,7 +47,9 @@
 /* Variables
  */
 List gameList;
-
+extern Board initialPosition;
+extern int quickFlag;
+extern int movePtr;
 
 /* Local function prototypes
  */
@@ -212,18 +214,22 @@ int GameListBuild(f)
     ChessMove cm, lastStart;
     int gameNumber;
     ListGame *currentListGame = NULL;
-    int error;
+    int error, scratch=100, plyNr=0, fromX, fromY, toX, toY;
     int offset;
     char lastComment[MSG_SIZ], buf[MSG_SIZ];
-
+struct {
+    long sec;  /* Assuming this is >= 32 bits */
+    int ms;    /* Assuming this is >= 16 bits */
+} t,t2; GetTimeMark(&t);
     GameListFree(&gameList);
     yynewfile(f);
     gameNumber = 0;
+    quickFlag = 1;
 
     lastStart = (ChessMove) 0;
     yyskipmoves = FALSE;
     do {
-        yyboardindex = 0;
+        yyboardindex = scratch + (plyNr & 1);
        offset = yyoffset();
        cm = (ChessMove) Myylex();
        switch (cm) {
@@ -285,10 +291,13 @@ int GameListBuild(f)
                    ParsePGNTag(yy_text, &currentListGame->gameInfo);
                }
            } while (cm == PGNTag || cm == Comment);
-           break;
+           if(1) { CopyBoard(boards[scratch], initialPosition); plyNr = 0; currentListGame->moves = PackGame(boards[scratch]); }
+           if(cm != NormalMove) break;
+         case IllegalMove:
+               if(appData.testLegality) break;
          case NormalMove:
            /* Allow the first game to start with an unnumbered move */
-           yyskipmoves = TRUE;
+           yyskipmoves = FALSE;
            if (lastStart == (ChessMove) 0) {
              if ((error = GameListNewGame(&currentListGame))) {
                rewind(f);
@@ -299,6 +308,32 @@ int GameListBuild(f)
              currentListGame->offset = offset;
              lastStart = MoveNumberOne;
            }
+         case WhiteCapturesEnPassant:
+         case BlackCapturesEnPassant:
+         case WhitePromotion:
+         case BlackPromotion:
+         case WhiteNonPromotion:
+         case BlackNonPromotion:
+         case WhiteKingSideCastle:
+         case WhiteQueenSideCastle:
+         case BlackKingSideCastle:
+         case BlackQueenSideCastle:
+         case WhiteKingSideCastleWild:
+         case WhiteQueenSideCastleWild:
+         case BlackKingSideCastleWild:
+         case BlackQueenSideCastleWild:
+         case WhiteHSideCastleFR:
+         case WhiteASideCastleFR:
+         case BlackHSideCastleFR:
+         case BlackASideCastleFR:
+               fromX = currentMoveString[0] - AAA;
+               fromY = currentMoveString[1] - ONE;
+               toX = currentMoveString[2] - AAA;
+               toY = currentMoveString[3] - ONE;
+               CopyBoard(boards[scratch + (plyNr+1&1)], boards[scratch + (plyNr&1)]);
+               plyNr++;
+               ApplyMove(fromX, fromY, toX, toY, currentMoveString[4], boards[scratch + (plyNr&1)]);
+               PackMove(fromX, fromY, toX, toY, currentMoveString[4]);
            break;
         case WhiteWins: // [HGM] rescom: save last comment as result details
         case BlackWins:
@@ -334,7 +369,8 @@ int GameListBuild(f)
            PrintPGNTags(debugFP, &currentListGame->gameInfo);
        }
     }
-
+GetTimeMark(&t2);printf("GameListBuild %d msec\n", SubtractTimeMarks(&t2,&t));
+    quickFlag = 0;
     DisplayTitle("WinBoard");
     rewind(f);
     yyskipmoves = FALSE;

diff --git a/xgamelist.c b/xgamelist.c
index 5767b98..9b851d4 100644 (file)
--- a/xgamelist.c
+++ b/xgamelist.c
@@ -326,12 +326,19 @@ GameListCreate(name, callback, client_data)
     return shell;
 }
 
+extern int soughtCounts[];
+extern Board soughtBoard;
+
 static int
 GameListPrepare(int byPos)
 {   // [HGM] filter: put in separate routine, to make callable from call-back
     int nstrings;
     ListGame *lg;
     char **st, *line;
+struct {
+    long sec;  /* Assuming this is >= 32 bits */
+    int ms;    /* Assuming this is >= 16 bits */
+} t,t2; GetTimeMark(&t);
 
     if(st = glc->strings) while(*st) free(*st++);
     nstrings = ((ListGame *) gameList.tailPred)->number;
@@ -339,6 +346,7 @@ GameListPrepare(int byPos)
     st = glc->strings;
     lg = (ListGame *) gameList.head;
     listLength = wins = losses = draws = 0;
+    if(byPos) MakePieceList(boards[currentMove], soughtCounts), CopyBoard(soughtBoard, boards[currentMove]);
     while (nstrings--) {
        int pos = -1;
        line = GameListLine(lg->number, &lg->gameInfo);
@@ -357,6 +365,7 @@ GameListPrepare(int byPos)
        lg->position = pos;
        lg = (ListGame *) lg->node.succ;
      }
+GetTimeMark(&t2);printf("GameListPrepare %d msec\n", SubtractTimeMarks(&t2,&t));
      DisplayTitle("XBoard");
     *st = NULL;
     return listLength;