X-Git-Url: http://winboard.nl/cgi-bin?a=blobdiff_plain;f=backend.c;h=7ffbd84199037dc318bff5b448feda98816b20eb;hb=1f070c3ba500547459ad3df71fbdbad1e5b4b4a0;hp=e0bb52f23216e122641d9722c2f4a725d0cb7955;hpb=1a2052a0c7bf59ec549cf7f6ed11e5114f7b15c6;p=xboard.git

diff --git a/backend.c b/backend.c
index e0bb52f..7ffbd84 100644
--- a/backend.c
+++ b/backend.c
@@ -1868,7 +1868,7 @@ SendToICS(s)
 {
     int count, outCount, outError;
 
-    if (icsPR == NULL) return;
+    if (icsPR == NoProc) return;
 
     count = strlen(s);
     outCount = OutputMaybeTelnet(icsPR, s, count, &outError);
@@ -1887,7 +1887,7 @@ SendToICSDelayed(s,msdelay)
 {
     int count, outCount, outError;
 
-    if (icsPR == NULL) return;
+    if (icsPR == NoProc) return;
 
     count = strlen(s);
     if (appData.debugMode) {
@@ -3900,7 +3900,7 @@ read_from_ics(isr, closure, data, count, error)
 #if ZIPPY
 		if (appData.zippyPlay && first.initDone) {
 		    ZippyGameEnd(endtype, why);
-		    if (first.pr == NULL) {
+		    if (first.pr == NoProc) {
 		      /* Start the next process early so that we'll
 			 be ready for the next challenge */
 		      StartChessProgram(&first);
@@ -5426,7 +5426,7 @@ char *
 PvToSAN(char *pv)
 {
 	static char buf[10*MSG_SIZ];
-	int i, k=0, savedEnd=endPV;
+	int i, k=0, savedEnd=endPV, saveFMM = forwardMostMove;
 	*buf = NULLCHAR;
 	if(forwardMostMove < endPV) PushInner(forwardMostMove, endPV);
 	ParsePV(pv, FALSE, 2); // this appends PV to game, suppressing any display of it
@@ -5436,7 +5436,7 @@ PvToSAN(char *pv)
 	    k += strlen(buf+k);
 	}
 	snprintf(buf+k, 10*MSG_SIZ-k, "%s", lastParseAttempt); // if we ran into stuff that could not be parsed, print it verbatim
-	if(forwardMostMove < savedEnd) PopInner(0);
+	if(forwardMostMove < savedEnd) { PopInner(0); forwardMostMove = saveFMM; } // PopInner would set fmm to endPV!
 	endPV = savedEnd;
 	return buf;
 }
@@ -10040,7 +10040,7 @@ NextTourneyGame(int nr, int *swapColors)
 	matchGame = 1; roundNr = nr / syncInterval + 1;
     }
 
-    if(first.pr != NoProc) return 1; // engines already loaded
+    if(first.pr != NoProc || second.pr != NoProc) return 1; // engines already loaded
 
     // redefine engines, engine dir, etc.
     NamesToList(firstChessProgramNames, command, mnemonic); // get mnemonics of installed engines
@@ -10648,7 +10648,7 @@ Reset(redraw, init)
     timeRemaining[0][0] = whiteTimeRemaining;
     timeRemaining[1][0] = blackTimeRemaining;
 
-    if (first.pr == NULL) {
+    if (first.pr == NoProc) {
 	StartChessProgram(&first);
     }
     if (init) {
@@ -11173,6 +11173,205 @@ PositionMatches(Board b1, Board b2)
     return TRUE;
 }
 
+#define Q_PROMO  4
+#define Q_EP     3
+#define Q_BCASTL 2
+#define Q_WCASTL 1
+
+int pieceList[256], quickBoard[256];
+ChessSquare pieceType[256] = { EmptySquare };
+Board soughtBoard, reverseBoard, flipBoard, rotateBoard;
+int counts[EmptySquare], minSought[EmptySquare], minReverse[EmptySquare], maxSought[EmptySquare], maxReverse[EmptySquare];
+Boolean epOK, flipSearch;
+
+typedef struct {
+    unsigned char piece, to;
+} Move;
+
+#define DATABASESIZE 10000000 /* good for 100k games */
+Move moveDatabase[DATABASESIZE];
+int movePtr;
+
+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] = n; else
+	    if(board[r][f] == BlackKing) pieceList[2] = n; // remember which are Kings, for castling
+	}
+    }
+    epOK = gameInfo.variant != VariantXiangqi && gameInfo.variant != VariantBerolina;
+}
+
+void PackMove(int fromX, int fromY, int toX, int toY, ChessSquare promoPiece)
+{
+    int sq = fromX + (fromY<<4);
+    int piece = quickBoard[sq];
+    quickBoard[sq] = 0;
+    moveDatabase[movePtr].to = pieceList[piece] = sq = toX + (toY<<4);
+    if(piece == pieceList[1] && fromY == toY && (toX > fromX+1 || toX < fromX-1) && fromX != BOARD_LEFT && fromX != BOARD_RGHT-1) {
+	int from = toX>fromX ? BOARD_RGHT-1 : BOARD_LEFT;
+	moveDatabase[movePtr++].piece = Q_WCASTL;
+	quickBoard[sq] = piece;
+	piece = quickBoard[from]; quickBoard[from] = 0;
+	moveDatabase[movePtr].to = pieceList[piece] = sq = toX>fromX ? sq-1 : sq+1;
+    } else
+    if(piece == pieceList[2] && fromY == toY && (toX > fromX+1 || toX < fromX-1) && fromX != BOARD_LEFT && fromX != BOARD_RGHT-1) {
+	int from = (toX>fromX ? BOARD_RGHT-1 : BOARD_LEFT) + (BOARD_HEIGHT-1 <<4);
+	moveDatabase[movePtr++].piece = Q_BCASTL;
+	quickBoard[sq] = piece;
+	piece = quickBoard[from]; quickBoard[from] = 0;
+	moveDatabase[movePtr].to = pieceList[piece] = sq = toX>fromX ? sq-1 : sq+1;
+    } else
+    if(epOK && (pieceType[piece] == WhitePawn || pieceType[piece] == BlackPawn) && fromX != toX && quickBoard[sq] == 0) {
+	quickBoard[(fromY<<4)+toX] = 0;
+	moveDatabase[movePtr].piece = Q_EP;
+	moveDatabase[movePtr++].to = (fromY<<4)+toX;
+	moveDatabase[movePtr].to = sq;
+    } else
+    if(promoPiece != pieceType[piece]) {
+	moveDatabase[movePtr++].piece = Q_PROMO;
+	moveDatabase[movePtr].to = pieceType[piece] = (int) promoPiece;
+    }
+    moveDatabase[movePtr].piece = piece;
+    quickBoard[sq] = piece;
+    movePtr++;
+}
+
+int PackGame(Board board)
+{
+    moveDatabase[movePtr].piece = 0; // terminate previous game
+    if(movePtr > DATABASESIZE - 500) return 0; // gamble on that game will not be more than 250 moves
+    movePtr++;
+    MakePieceList(board, counts);
+    return movePtr;
+}
+
+int QuickCompare(Board board, int *minCounts, 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] != maxCounts[r]) return FALSE;
+	return TRUE;
+      case 6: // material range with given imbalance
+	for(r=0; r<BlackPawn; r++) if(counts[r] - minCounts[r] != counts[r+BlackPawn] - minCounts[r+BlackPawn]) return FALSE;
+	// fall through to range comparison
+      case 5: // material range
+	for(r=0; r<EmptySquare; r++) if(counts[r] < minCounts[r] || counts[r] > maxCounts[r]) return FALSE;
+	return TRUE;
+    }
+}
+
+int QuickScan(Board board, Move *move)
+{   // reconstruct game,and compare all positions in it
+    int cnt=0, stretch=0;
+    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 -1;
+	  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)
+	    piece = pieceList[piece]; // first two elements of pieceList contain King numbers
+	    from  = pieceList[piece]; // so this must be King
+	    quickBoard[from] = 0;
+	    quickBoard[to] = piece;
+	    pieceList[piece] = to;
+	    move++;
+	    continue;
+	  }
+	}
+	if(appData.searchMode > 2) counts[pieceType[quickBoard[to]]]--; // account capture
+	quickBoard[from] = 0;
+	quickBoard[to] = piece;
+	pieceList[piece] = to;
+	cnt++;
+	if(QuickCompare(soughtBoard, minSought, maxSought) ||
+	   appData.ignoreColors && QuickCompare(reverseBoard, minReverse, maxReverse) ||
+	   flipSearch && (QuickCompare(flipBoard, minSought, maxSought) ||
+				appData.ignoreColors && QuickCompare(rotateBoard, minReverse, maxReverse))
+	  ) {
+	    static int lastCounts[EmptySquare+1];
+	    int i;
+	    if(stretch) for(i=0; i<EmptySquare; i++) if(lastCounts[i] != counts[i]) { stretch = 0; break; } // reset if material changes
+	    if(stretch++ == 0) for(i=0; i<EmptySquare; i++) lastCounts[i] = counts[i]; // remember actual material
+	} else stretch = 0;
+	if(stretch && (appData.searchMode == 1 || stretch >= appData.stretch)) return cnt + 1 - stretch;
+	move++;
+    } while(1);
+}
+
+InitSearch()
+{
+    int r, f;
+    flipSearch = FALSE;
+    CopyBoard(soughtBoard, boards[currentMove]);
+    MakePieceList(soughtBoard, maxSought);
+    CopyBoard(reverseBoard, boards[currentMove]);
+    for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
+	int piece = boards[currentMove][BOARD_HEIGHT-1-r][f];
+	if(piece < BlackPawn) piece += BlackPawn; else if(piece < EmptySquare) piece -= BlackPawn; // color-flip
+	reverseBoard[r][f] = piece;
+    }
+    for(r=0; r<6; r++) reverseBoard[CASTLING][r] = boards[currentMove][CASTLING][(r+3)%6];
+    if(appData.findMirror && appData.searchMode <= 3 && (!nrCastlingRights
+		 || (boards[currentMove][CASTLING][2] == NoRights || 
+		     boards[currentMove][CASTLING][0] == NoRights && boards[currentMove][CASTLING][1] == NoRights )
+		 && (boards[currentMove][CASTLING][5] == NoRights || 
+		     boards[currentMove][CASTLING][3] == NoRights && boards[currentMove][CASTLING][4] == NoRights ) )
+      ) {
+	flipSearch = TRUE;
+	CopyBoard(flipBoard, soughtBoard);
+	CopyBoard(rotateBoard, reverseBoard);
+	for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
+	    flipBoard[r][f]    = soughtBoard[r][BOARD_WIDTH-1-f];
+	    rotateBoard[r][f] = reverseBoard[r][BOARD_WIDTH-1-f];
+	}
+    }
+    for(r=0; r<BlackPawn; r++) maxReverse[r] = maxSought[r+BlackPawn], maxReverse[r+BlackPawn] = maxSought[r];
+    if(appData.searchMode >= 5) {
+	for(r=BOARD_HEIGHT/2; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) soughtBoard[r][f] = EmptySquare;
+	MakePieceList(soughtBoard, minSought);
+	for(r=0; r<BlackPawn; r++) minReverse[r] = minSought[r+BlackPawn], minReverse[r+BlackPawn] = minSought[r];
+    }
+}
+
 GameInfo dummyInfo;
 
 int GameContainsPosition(FILE *f, ListGame *lg)
@@ -11182,44 +11381,33 @@ 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) {
+	if((next = QuickScan( boards[scratch], &moveDatabase[lg->moves] )) < 0) return -1; // quick scan rules out it is there
+	if(appData.searchMode >= 4) return next; // for material searches, trust QuickScan.
+    }
+    if(btm) plyNr++;
+    if(PositionMatches(boards[scratch], 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;
+	yyboardindex = scratch;
+	quickFlag = plyNr+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,18 +11462,14 @@ 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)]);
-	if(PositionMatches(boards[scratch + (plyNr&1)], boards[currentMove])) return plyNr;
+	ApplyMove(fromX, fromY, toX, toY, promoChar, boards[scratch]);
+	if(PositionMatches(boards[scratch], boards[currentMove])) return plyNr;
+	if(appData.ignoreColors && PositionMatches(boards[scratch], reverseBoard)) return plyNr;
+	if(appData.findMirror) {
+	    if(PositionMatches(boards[scratch], flipBoard)) return plyNr;
+	    if(appData.ignoreColors && PositionMatches(boards[scratch], rotateBoard)) return plyNr;
+	}
     }
 }
 
@@ -13132,7 +13316,7 @@ int
 WaitForEngine(ChessProgramState *cps, DelayedEventCallback retry)
 {
     char buf[MSG_SIZ];
-    if (cps->pr == NULL) {
+    if (cps->pr == NoProc) {
 	StartChessProgram(cps);
 	if (cps->protocolVersion == 1) {
 	  retry();
@@ -14813,7 +14997,7 @@ SendToProgram(message, cps)
     int count, outCount, error;
     char buf[MSG_SIZ];
 
-    if (cps->pr == NULL) return;
+    if (cps->pr == NoProc) return;
     Attention(cps);
 
     if (appData.debugMode) {