X-Git-Url: http://winboard.nl/cgi-bin?a=blobdiff_plain;f=backend.c;h=dddb308eff3b575f16e86af1831d39433f54bd07;hb=107083ca63cd1dfe481d3c51f4b3a817a0f2c328;hp=e670eaf7808d8187eda4cc37453e350cf37a6cad;hpb=ca6061cbffe88ff5eb2332e733e0a534b89cc5e7;p=xboard.git

diff --git a/backend.c b/backend.c
index e670eaf..dddb308 100644
--- a/backend.c
+++ b/backend.c
@@ -11180,21 +11180,24 @@ PositionMatches(Board b1, Board b2)
 
 int pieceList[256], quickBoard[256];
 ChessSquare pieceType[256] = { EmptySquare };
-Board soughtBoard, reverseBoard;
+Board soughtBoard, reverseBoard, flipBoard, rotateBoard;
 int counts[EmptySquare], minSought[EmptySquare], minReverse[EmptySquare], maxSought[EmptySquare], maxReverse[EmptySquare];
-Boolean epOK;
+int soughtTotal, turn;
+Boolean epOK, flipSearch;
 
 typedef struct {
     unsigned char piece, to;
 } Move;
 
-#define DATABASESIZE 10000000 /* good for 100k games */
-Move moveDatabase[DATABASESIZE];
-int movePtr;
+#define DSIZE (250000)
 
-void MakePieceList(Board board, int *counts)
+Move initialSpace[DSIZE+1000]; // gamble on that game will not be more than 500 moves
+Move *moveDatabase = initialSpace;
+unsigned int movePtr, dataSize = DSIZE;
+
+int MakePieceList(Board board, int *counts)
 {
-    int r, f, n=Q_PROMO;
+    int r, f, n=Q_PROMO, total=0;
     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);
@@ -11205,9 +11208,11 @@ void MakePieceList(Board board, int *counts)
 	    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
+	    total++;
 	}
     }
     epOK = gameInfo.variant != VariantXiangqi && gameInfo.variant != VariantBerolina;
+    return total;
 }
 
 void PackMove(int fromX, int fromY, int toX, int toY, ChessSquare promoPiece)
@@ -11247,8 +11252,23 @@ void PackMove(int fromX, int fromY, int toX, int toY, ChessSquare promoPiece)
 
 int PackGame(Board board)
 {
+    Move *newSpace = NULL;
     moveDatabase[movePtr].piece = 0; // terminate previous game
-    if(movePtr > DATABASESIZE - 500) return 0; // gamble on that game will not be more than 250 moves
+    if(movePtr > dataSize) {
+	if(appData.debugMode) fprintf(debugFP, "move-cache overflow, enlarge to %d MB\n", dataSize/128);
+	dataSize *= 8; // increase size by factor 8 (512KB -> 4MB -> 32MB -> 256MB -> 2GB)
+	if(dataSize) newSpace = (Move*) calloc(8*dataSize + 1000, sizeof(Move));
+	if(newSpace) {
+	    int i;
+	    Move *p = moveDatabase, *q = newSpace;
+	    for(i=0; i<movePtr; i++) *q++ = *p++;    // copy to newly allocated space
+	    if(dataSize > 8*DSIZE) free(moveDatabase); // and free old space (if it was allocated)
+	    moveDatabase = newSpace;
+	} else { // calloc failed, we must be out of memory. Too bad...
+	    dataSize = 0; // prevent calloc events for all subsequent games
+	    return 0;     // and signal this one isn't cached
+	}
+    }
     movePtr++;
     MakePieceList(board, counts);
     return movePtr;
@@ -11260,6 +11280,7 @@ int QuickCompare(Board board, int *minCounts, int *maxCounts)
     switch(appData.searchMode)
     {
       case 1: // exact position match
+	if(!(turn & board[EP_STATUS-1])) return FALSE; // wrong side to move
 	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;
 	}
@@ -11289,8 +11310,7 @@ int QuickCompare(Board board, int *minCounts, int *maxCounts)
 
 int QuickScan(Board board, Move *move)
 {   // reconstruct game,and compare all positions in it
-    int cnt=0, stretch=0;
-    MakePieceList(board, counts);
+    int cnt=0, stretch=0, total = MakePieceList(board, counts);
     do {
 	int piece = move->piece;
 	int to = move->to, from = pieceList[piece];
@@ -11304,7 +11324,7 @@ int QuickScan(Board board, Move *move)
 	    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;
+	    quickBoard[to] = 0; total--;
 	    move++;
 	    continue;
 	  } else if(piece <= Q_BCASTL) { // castling, encoded as (Q_XCASTL, king-to) + (rook, rook-to)
@@ -11318,12 +11338,16 @@ int QuickScan(Board board, Move *move)
 	  }
 	}
 	if(appData.searchMode > 2) counts[pieceType[quickBoard[to]]]--; // account capture
+	if((total -= (quickBoard[to] != 0)) < soughtTotal) return -1; // piece count dropped below what we search for
 	quickBoard[from] = 0;
 	quickBoard[to] = piece;
 	pieceList[piece] = to;
-	cnt++;
+	cnt++; turn ^= 3;
 	if(QuickCompare(soughtBoard, minSought, maxSought) ||
-	   appData.ignoreColors && QuickCompare(reverseBoard, minReverse, maxReverse)) {
+	   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
@@ -11334,24 +11358,44 @@ int QuickScan(Board board, Move *move)
     } while(1);
 }
 
-InitSearch()
+void InitSearch()
 {
     int r, f;
+    flipSearch = FALSE;
     CopyBoard(soughtBoard, boards[currentMove]);
-    MakePieceList(soughtBoard, maxSought);
+    soughtTotal = MakePieceList(soughtBoard, maxSought);
+    soughtBoard[EP_STATUS-1] = (currentMove & 1) + 1;
+    if(currentMove == 0 && gameMode == EditPosition) soughtBoard[EP_STATUS-1] = blackPlaysFirst + 1; // (!)
     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;
     }
+    reverseBoard[EP_STATUS-1] = soughtBoard[EP_STATUS-1] ^ 3; 
     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];
     }
+    if(gameInfo.variant == VariantCrazyhouse || gameInfo.variant == VariantShogi || gameInfo.variant == VariantBughouse)
+	soughtTotal = 0; // in drop games nr of pieces does not fall monotonously
 }
 
 GameInfo dummyInfo;
@@ -11375,6 +11419,7 @@ int GameContainsPosition(FILE *f, ListGame *lg)
     if(lg->gameInfo.fen) ParseFEN(boards[scratch], &btm, lg->gameInfo.fen);
     else CopyBoard(boards[scratch], initialPosition); // default start position
     if(lg->moves) {
+	turn = btm + 1;
 	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.
     }
@@ -11448,6 +11493,10 @@ int GameContainsPosition(FILE *f, ListGame *lg)
 	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;
+	}
     }
 }