Added flood fill support. Pajama2 puzzle seems to be ok now

svn-id: r19158

6 files changed, 327 insertions, 39 deletions

diff --git a/scumm/floodfill_he.cpp b/scumm/floodfill_he.cpp
new file mode 100644
index 0000000000..458ee65bc2
--- /dev/null
+++ b/scumm/floodfill_he.cpp
@@ -0,0 +1,229 @@
+/* ScummVM - Scumm Interpreter
+ * Copyright (C) 2001  Ludvig Strigeus
+ * Copyright (C) 2001-2005 The ScummVM project
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * $Header$
+ *
+ */
+
+#include "common/stdafx.h"
+
+#include "scumm/intern.h"
+#include "scumm/scumm.h"
+#include "scumm/floodfill_he.h"
+
+namespace Scumm {
+	
+static bool floodFillPixelCheck(int x, int y, const FloodFillState *ffs) {
+	int diffColor = ffs->color1 - ffs->color2;
+	if (x >= 0 && x < ffs->dst_w && y >= 0 && y < ffs->dst_h) {
+		uint8 color = *(ffs->dst + y * ffs->dst_w + x);
+		diffColor = color - ffs->color1;
+	}
+	return diffColor == 0;
+}
+
+static void floodFillProcessRect(FloodFillState *ffs, const Common::Rect *r) {
+	Common::Rect *dr = &ffs->dstBox;
+	if (dr->right >= dr->left && dr->top <= dr->bottom) {
+		int rw = r->right - r->left + 1;
+		int rh = r->bottom - r->top + 1;
+		assert(r->top + rh <= ffs->dst_h);
+		assert(r->left + rw <= ffs->dst_w);
+		uint8 *dst = ffs->dst + r->top * ffs->dst_w + r->left;
+		if (rw <= 1) {
+			--rh;
+			while (rh >= 0) {
+				*dst = ffs->color2;
+				dst += ffs->dst_w;
+				--rh;
+			}
+		} else {
+			--rh;
+			while (rh >= 0) {
+				memset(dst, ffs->color2, rw);
+				dst += ffs->dst_w;
+				--rh;
+			}
+		}
+		dr->extend(*r);
+	} else {
+		*dr = *r;
+	}
+}
+
+static void floodFillAddLine(FloodFillLine **ffl, int y, int x1, int x2, int dy) {
+	(*ffl)->y = y;
+	(*ffl)->x1 = x1;
+	(*ffl)->x2 = x2;
+	(*ffl)->inc = dy;
+	(*ffl)++;
+}
+
+static void floodFillProcess(int x, int y, FloodFillState *ffs, FloodFillPixelCheckCallback pixelCheckCallback) {
+	ffs->dstBox.left = ffs->dstBox.top = 12345;
+	ffs->dstBox.right = ffs->dstBox.bottom = -12345;
+	
+	FloodFillLine **fillLineCur = &ffs->fillLineTableCur;
+	FloodFillLine **fillLineEnd = &ffs->fillLineTableEnd;
+	
+	assert(*fillLineCur < *fillLineEnd);
+	if (ffs->srcBox.top <= y + 1 && ffs->srcBox.bottom >= y + 1) {
+		(*fillLineCur)->y = y;
+		(*fillLineCur)->x1 = x;
+		(*fillLineCur)->x2 = x;
+		(*fillLineCur)->inc = 1;
+		(*fillLineCur)++;
+	}
+	
+	assert(*fillLineCur < *fillLineEnd);
+	if (ffs->srcBox.top <= y && ffs->srcBox.bottom >= y) {
+		(*fillLineCur)->y = y + 1;
+		(*fillLineCur)->x1 = x;
+		(*fillLineCur)->x2 = x;
+		(*fillLineCur)->inc = -1;
+		(*fillLineCur)++;
+	}
+
+	assert(ffs->fillLineTable <= *fillLineCur);
+	FloodFillLine **fillLineStart = fillLineCur;
+	
+	while (ffs->fillLineTable < *fillLineStart) {
+		Common::Rect r;
+		int x_start;
+		FloodFillLine *fflCur = --(*fillLineCur);
+  		int dy = fflCur->inc;
+  		int x_end = fflCur->x2;
+  		int x1 = fflCur->x1;
+  		int x2 = fflCur->x1 + 1;
+		r.bottom = r.top = y = fflCur->y + fflCur->inc;
+  		r.left = x2;
+  		r.right = x1;
+  		x = x1;
+  		while (ffs->srcBox.left <= x) {
+			if (!(*pixelCheckCallback)(x, y, ffs)) {
+				break;
+			}
+			r.left = x;
+			--x;
+		}
+		if (r.right >= r.left && r.top <= r.bottom) {
+			floodFillProcessRect(ffs, &r);
+		}
+		if (x >= x1) goto skip;
+		x_start = x + 1;
+		if (x1 > x_start) {
+			assert(*fillLineEnd > *fillLineCur);
+			if (ffs->srcBox.top <= y - dy && ffs->srcBox.bottom >= y - dy) {
+				--x1;
+				floodFillAddLine(fillLineCur, y, x_start, x1, -dy);
+			}
+		}
+		x = x2;
+		while (x_start <= x_end) {
+			r.left = x;
+			r.top = y;
+			r.right = x - 1;
+			r.bottom = y;
+			while (ffs->srcBox.right >= x) {
+				if (!(*pixelCheckCallback)(x, y, ffs)) {
+					break;
+				}
+				r.right = x;
+				++x;
+			}
+			if (r.right >= r.left && r.top <= r.bottom) {
+				floodFillProcessRect(ffs, &r);
+			}
+			assert(ffs->fillLineTableCur < ffs->fillLineTableEnd);
+			if (ffs->srcBox.top <= y + dy && ffs->srcBox.bottom >= y + dy) {
+				floodFillAddLine(&ffs->fillLineTableCur, y, x_start, x - 1, dy);
+			}
+			x_start = x_end + 1;
+			if (x > x_start) {
+				assert(ffs->fillLineTableCur < ffs->fillLineTableEnd);
+				if (ffs->srcBox.top <= y - dy && ffs->srcBox.bottom >= y - dy) {
+					floodFillAddLine(&ffs->fillLineTableCur, y, x_start, x - 1, -dy);
+				}
+			}
+skip:
+			++x;
+			while (x <= x_end) {
+				if ((*pixelCheckCallback)(x, y, ffs)) {
+					break;
+				}
+				++x;
+			}
+			x_start = x;
+		}
+	}
+}
+
+void floodFill(FloodFillParameters *ffp, ScummEngine_v90he *vm) {
+	uint8 *dst;
+	VirtScreen *vs = &vm->virtscr[kMainVirtScreen];
+	if (ffp->flags & 0x8000) {
+		dst = vs->getBackPixels(0, vs->topline);
+	} else {
+		dst = vs->getPixels(0, vs->topline);
+	}
+	uint8 color = ffp->flags & 0xFF;
+
+	Common::Rect r;
+	r.left = r.top = 12345;
+	r.right = r.bottom = -12345;
+	
+	FloodFillState *ffs = new FloodFillState;
+	ffs->fillLineTableCount = vs->h * 2;
+	ffs->fillLineTable = new FloodFillLine[ffs->fillLineTableCount];
+	ffs->color2 = color;
+	ffs->dst = dst;
+	ffs->dst_w = vs->w;
+	ffs->dst_h = vs->h;
+	ffs->srcBox = ffp->box;
+	ffs->fillLineTableCur = &ffs->fillLineTable[0];
+	ffs->fillLineTableEnd = &ffs->fillLineTable[ffs->fillLineTableCount];
+	
+	if (ffp->x < 0 || ffp->y < 0 || ffp->x >= vs->w || ffp->y >= vs->h) {
+		ffs->color1 = color;
+	} else {
+		ffs->color1 = *(dst + ffp->y * vs->w + ffp->x);
+	}
+	
+	debug(5, "floodFill() x=%d y=%d color1=%d ffp->flags=0x%X", ffp->x, ffp->y, ffs->color1, ffp->flags);
+	if (ffs->color1 != color) {
+		floodFillProcess(ffp->x, ffp->y, ffs, floodFillPixelCheck);
+		r = ffs->dstBox;
+	}
+	r.debugPrint(5, "floodFill() dirty_rect");
+	
+	delete[] ffs->fillLineTable;
+	delete ffs;
+	
+	vm->VAR(119) = 1;
+	
+	if (r.left <= r.right && r.top <= r.bottom) {
+		if (ffp->flags & 0x8000) {
+			vm->gdi.copyVirtScreenBuffers(r);
+		} else {
+			++r.bottom;
+			vm->markRectAsDirty(kMainVirtScreen, r);
+		}
+	}
+}
+
+} // End of namespace Scumm
diff --git a/scumm/floodfill_he.h b/scumm/floodfill_he.h
new file mode 100644
index 0000000000..0023cd2a15
--- /dev/null
+++ b/scumm/floodfill_he.h
@@ -0,0 +1,67 @@
+/* ScummVM - Scumm Interpreter
+ * Copyright (C) 2001  Ludvig Strigeus
+ * Copyright (C) 2001-2005 The ScummVM project
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * $Header$
+ *
+ */
+
+#if !defined(FLOODFILL_HE_H) && !defined(DISABLE_HE)
+#define FLOODFILL_HE_H
+
+#include "common/rect.h"
+
+namespace Scumm {
+
+struct FloodFillParameters {
+	Common::Rect box;
+	int32 x;
+	int32 y;
+	int32 flags;
+	int32 unk1C; /* unused */
+};
+
+struct FloodFillLine {
+	int y;
+	int x1;
+	int x2;
+	int inc;
+};
+
+struct FloodFillState {
+	FloodFillLine *fillLineTable;
+	FloodFillLine *fillLineTableEnd;
+	FloodFillLine *fillLineTableCur;
+	Common::Rect dstBox;
+	Common::Rect srcBox;
+	uint8 *dst;
+	int dst_w;
+	int dst_h;
+	int color1;
+	int color2;
+	int fillLineTableCount;
+};
+
+class ScummEngine_v90he;
+
+typedef bool (*FloodFillPixelCheckCallback)(int x, int y, const FloodFillState *ffs);
+
+void floodFill(FloodFillParameters *ffp, ScummEngine_v90he *vm);
+
+} // End of namespace Scumm
+
+#endif
diff --git a/scumm/intern.h b/scumm/intern.h
index cbe588552b..2c02a8da78 100644
--- a/scumm/intern.h
+++ b/scumm/intern.h
@@ -24,6 +24,7 @@
 #define INTERN_H
 
 #include "scumm/scumm.h"
+#include "scumm/floodfill_he.h"
 #include "scumm/sprite_he.h"
 #include "scumm/wiz_he.h"
 
@@ -1121,15 +1122,7 @@ protected:
 
 	const OpcodeEntryV90he *_opcodesV90he;
 
-	struct FloodStateParameters {
-		Common::Rect box;
-		int32 field_10;
-		int32 field_14;
-		int32 field_18;
-		int32 field_1C;
-	};
-
-	FloodStateParameters _floodStateParams;
+	FloodFillParameters _floodFillParams;
 
 	struct VideoParameters {
 		byte filename[260];
@@ -1218,7 +1211,7 @@ protected:
 	void o90_getSpriteGroupInfo();
 	void o90_setSpriteGroupInfo();
 	void o90_getWizData();
-	void o90_floodState();
+	void o90_floodFill();
 	void o90_mod();
 	void o90_shl();
 	void o90_shr();
diff --git a/scumm/module.mk b/scumm/module.mk
index 9e3165ddce..60498cb631 100644
--- a/scumm/module.mk
+++ b/scumm/module.mk
@@ -79,6 +79,7 @@ endif
 
 ifndef DISABLE_HE
 MODULE_OBJS += \
+	scumm/floodfill_he.o \
 	scumm/logic_he.o \
 	scumm/palette_he.o \
 	scumm/resource_v7he.o \
diff --git a/scumm/saveload.cpp b/scumm/saveload.cpp
index 833146b74b..e24036971e 100644
--- a/scumm/saveload.cpp
+++ b/scumm/saveload.cpp
@@ -37,7 +37,6 @@
 #include "scumm/scumm.h"
 #include "scumm/sound.h"
 #include "scumm/verbs.h"
-#include "scumm/wiz_he.h"
 
 #include "sound/audiocd.h"
 #include "sound/mixer.h"
@@ -1237,15 +1236,15 @@ void ScummEngine_v70he::saveOrLoad(Serializer *s, uint32 savegameVersion) {
 void ScummEngine_v90he::saveOrLoad(Serializer *s, uint32 savegameVersion) {
 	ScummEngine_v70he::saveOrLoad(s, savegameVersion);
 
-	const SaveLoadEntry floodStateEntries[] = {
-		MKLINE(FloodStateParameters, box.left, sleInt32, VER(51)),
-		MKLINE(FloodStateParameters, box.top, sleInt32, VER(51)),
-		MKLINE(FloodStateParameters, box.right, sleInt32, VER(51)),
-		MKLINE(FloodStateParameters, box.bottom, sleInt32, VER(51)),
-		MKLINE(FloodStateParameters, field_10, sleInt32, VER(51)),
-		MKLINE(FloodStateParameters, field_14, sleInt32, VER(51)),
-		MKLINE(FloodStateParameters, field_18, sleInt32, VER(51)),
-		MKLINE(FloodStateParameters, field_1C, sleInt32, VER(51)),
+	const SaveLoadEntry floodFillEntries[] = {
+		MKLINE(FloodFillParameters, box.left, sleInt32, VER(51)),
+		MKLINE(FloodFillParameters, box.top, sleInt32, VER(51)),
+		MKLINE(FloodFillParameters, box.right, sleInt32, VER(51)),
+		MKLINE(FloodFillParameters, box.bottom, sleInt32, VER(51)),
+		MKLINE(FloodFillParameters, x, sleInt32, VER(51)),
+		MKLINE(FloodFillParameters, y, sleInt32, VER(51)),
+		MKLINE(FloodFillParameters, flags, sleInt32, VER(51)),
+		MKLINE(FloodFillParameters, unk1C, sleInt32, VER(51)),
 		MKEND()
 	};
 
@@ -1262,7 +1261,7 @@ void ScummEngine_v90he::saveOrLoad(Serializer *s, uint32 savegameVersion) {
 
 	_sprite->saveOrLoadSpriteData(s, savegameVersion);
 
-	s->saveLoadArrayOf(&_floodStateParams, 1, sizeof(_floodStateParams), floodStateEntries);
+	s->saveLoadArrayOf(&_floodFillParams, 1, sizeof(_floodFillParams), floodFillEntries);
 
 	_numSpritesToProcess = _sprite->_numSpritesToProcess;
 	s->saveLoadEntries(this, HE90Entries);
diff --git a/scumm/script_v90he.cpp b/scumm/script_v90he.cpp
index 88763d883d..33c9e7784b 100644
--- a/scumm/script_v90he.cpp
+++ b/scumm/script_v90he.cpp
@@ -98,7 +98,7 @@ void ScummEngine_v90he::setupOpcodes() {
 		OPCODE(o90_jumpToScriptUnk),
 		OPCODE(o90_videoOps),
 		OPCODE(o90_getVideoData),
-		OPCODE(o90_floodState),
+		OPCODE(o90_floodFill),
 		/* 30 */
 		OPCODE(o90_mod),
 		OPCODE(o90_shl),
@@ -1760,41 +1760,40 @@ void ScummEngine_v90he::o90_getWizData() {
 	}
 }
 
-void ScummEngine_v90he::o90_floodState() {
+void ScummEngine_v90he::o90_floodFill() {
 	byte subOp = fetchScriptByte();
 	subOp -= 54;
 
 	switch (subOp) {
 	case 0:
-		_floodStateParams.field_1C = pop();
+		_floodFillParams.unk1C = pop();
 		break;
 	case 3:
-		memset(&_floodStateParams, 0, sizeof(_floodStateParams));
-		_floodStateParams.box.left = 0;
-		_floodStateParams.box.top = 0;
-		_floodStateParams.box.right = 640;
-		_floodStateParams.box.bottom = 480;
+		memset(&_floodFillParams, 0, sizeof(_floodFillParams));
+		_floodFillParams.box.left = 0;
+		_floodFillParams.box.top = 0;
+		_floodFillParams.box.right = 639;
+		_floodFillParams.box.bottom = 479;
 		break;
 	case 11:
-		_floodStateParams.field_14 = pop();
-		_floodStateParams.field_10 = pop();
+		_floodFillParams.y = pop();
+		_floodFillParams.x = pop();
 		break;
 	case 12:
-		_floodStateParams.field_18 = pop();
+		_floodFillParams.flags = pop();
 		break;
 	case 13:
-		_floodStateParams.box.bottom = pop();
-		_floodStateParams.box.right = pop();
-		_floodStateParams.box.top = pop();
-		_floodStateParams.box.left = pop();
+		_floodFillParams.box.bottom = pop();
+		_floodFillParams.box.right = pop();
+		_floodFillParams.box.top = pop();
+		_floodFillParams.box.left = pop();
 		break;
 	case 201:
-		//floodState(_floodStateParams);
+		floodFill(&_floodFillParams, this);
 		break;
 	default:
-		error("o90_floodState: Unknown case %d", subOp);
+		error("o90_floodFill: Unknown case %d", subOp);
 	}
-	debug(1, "o90_floodState stub (%d)", subOp);
 }
 
 void ScummEngine_v90he::o90_shl() {