initial implementation of o72_arrayOps_127 and o90_sortArray

svn-id: r17337

4 files changed, 229 insertions, 22 deletions

diff --git a/TODO b/TODO
index 20faaa3ebd..657dce8a8a 100644
--- a/TODO
+++ b/TODO
@@ -265,8 +265,6 @@ SCUMM
   - Add support for processWizImage mode 7 (For soccer2004)
   - Add support for processWizImage mode 10 (For footdemo)
   - Add support for RMAP/XMAP resources in drawWizImage (Used by akos codec 32 too)
-  - Add support for arrayOps case 127 (For chase/lost/smaller/bb2demo/footdemo).
-  - Add support for o90_sortArray (Used in bb2demo/footdemo/lost/smaller).
   - Add support for o90_getPolygonOverlap case10 (Used in Caramel Pit of pajama3)
   - Add support for floodState (For puzzle in pajama2)
   - Add support for o80_unknownE0 type1 (For binoculars in pajama2)
diff --git a/scumm/intern.h b/scumm/intern.h
index ca923e6814..296402358d 100644
--- a/scumm/intern.h
+++ b/scumm/intern.h
@@ -739,6 +739,10 @@ protected:
 	virtual void writeArray(int array, int idx2, int idx1, int value);
 	void redimArray(int arrayId, int newDim2start, int newDim2end, 
 					int newDim1start, int newDim1end, int type);
+	void checkArrayLimits(int array, int dim2start, int dim2end, int dim1start, int dim1end);
+	void copyArray(int array1, int a1_dim2start, int a1_dim2end, int a1_dim1start, int a1_dim1end, 
+					int array2, int a2_dim2start, int a2_dim2end, int a2_dim1start, int a2_dim1end);
+	void copyArrayHelper(ArrayHeader *ah, int idx2, int idx1, int len1, byte **data, int *size, int *num);
 	virtual int setupStringArray(int size);
 	int readFileToArray(int slot, int32 size);
 	void writeFileFromArray(int slot, int resID);
@@ -902,6 +906,9 @@ protected:
 	int isWizPixelNonTransparent(int resnum, int state, int x, int y, int flags);
 	uint8 getWizPixelColor(int resnum, int state, int x, int y, int flags);
 	int computeWizHistogram(int resnum, int state, int x, int y, int w, int h);
+
+	void getArrayDim(int array, int *dim2start, int *dim2end, int *dim1start, int *dim1end);
+	void sortArray(int array, int dim2start, int dim2end, int dim1start, int dim1end, int sortOrder);
 	
 	uint8 *getHEPalette(int palSlot);
 	void setHEPaletteColor(int palSlot, uint8 color, uint8 r, uint8 g, uint8 b);
diff --git a/scumm/script_v72he.cpp b/scumm/script_v72he.cpp
index 15ce984fb2..e47835fae2 100644
--- a/scumm/script_v72he.cpp
+++ b/scumm/script_v72he.cpp
@@ -1423,18 +1423,19 @@ void ScummEngine_v72he::o72_arrayOps() {
 		break;
 	case 127:
 		{
-		// TODO
-		//Array1
-		dim1end = pop();
-		dim1start = pop();
-		dim2end = pop();
-		dim2start = pop();
-		//Array2
-		array = fetchScriptWord();
-		dim1end = pop();
-		dim1start = pop();
-		dim2end = pop();
-		dim2start = pop();
+			int a1_dim1end = pop();
+			int a1_dim1start = pop();
+			int a1_dim2end = pop();
+			int a1_dim2start = pop();
+			int array2 = fetchScriptWord();
+			int a2_dim1end = pop();
+			int a2_dim1start = pop();
+			int a2_dim2end = pop();
+			int a2_dim2start = pop();
+			if (a1_dim1end - a1_dim1start != a2_dim1end - a2_dim1start || a2_dim2end - a2_dim2start != a1_dim2end - a1_dim2start) {
+				warning("Source and dest ranges size are mismatched");
+			}
+			copyArray(array, a1_dim2start, a1_dim2end, a1_dim1start, a1_dim1end, array2, a2_dim2start, a2_dim2end, a2_dim1start, a2_dim1end);
 		}
 		break;
 	case 128:
@@ -1977,6 +1978,107 @@ void ScummEngine_v72he::redimArray(int arrayId, int newDim2start, int newDim2end
 	ah->dim2end = TO_LE_32(newDim2end);
 }
 
+void ScummEngine_v72he::checkArrayLimits(int array, int dim2start, int dim2end, int dim1start, int dim1end) {
+	if (dim1end < dim1start) {
+		warning("Across max %d smaller than min %d", dim1end, dim1start);
+ 	}
+ 	if (dim2end < dim2start) {
+	 	warning("Down max %d smaller than min %d", dim2end, dim2start);
+ 	}
+	ArrayHeader *ah = (ArrayHeader *)getResourceAddress(rtString, readVar(array));
+	assert(ah);
+	if (ah->dim2start > dim2start || ah->dim2end < dim2end || ah->dim1start > dim1start || ah->dim1end < dim1end) {
+		warning("Invalid array access (%d,%d,%d,%d) limit (%d,%d,%d,%d)", dim2start, dim2end, dim1start, dim1end, ah->dim2start, ah->dim2end, ah->dim1start, ah->dim1end);
+	}
+}
+
+void ScummEngine_v72he::copyArray(int array1, int a1_dim2start, int a1_dim2end, int a1_dim1start, int a1_dim1end, 
+				int array2, int a2_dim2start, int a2_dim2end, int a2_dim1start, int a2_dim1end)
+{
+	debug(5, "ScummEngine_v72he::copyArray(%d, [%d,%d,%d,%d], %d, [%d,%d,%d,%d])", array1, a1_dim2start, a1_dim2end, a1_dim1start, a1_dim1end, array2, a2_dim2start, a2_dim2end, a2_dim1start, a2_dim1end);
+	byte *dst, *src;
+	int dstPitch, srcPitch;
+	int rowSize;
+	checkArrayLimits(array1, a1_dim2start, a1_dim2end, a1_dim1start, a1_dim1end);
+	checkArrayLimits(array2, a2_dim2start, a2_dim2end, a2_dim1start, a2_dim1end);
+	int a12_num = a1_dim2end - a1_dim2start + 1;
+	int a11_num = a1_dim1end - a1_dim1start + 1;	
+	int a22_num = a2_dim2end - a2_dim2start + 1;
+	int a21_num = a2_dim1end - a2_dim1start + 1;
+	if (a22_num != a12_num || a21_num != a11_num) {
+		warning("Operation size mismatch (%d vs %d)(%d vs %d)", a12_num, a22_num, a11_num, a21_num);
+	}	
+
+	if (array1 != array2) {
+		ArrayHeader *ah1 = (ArrayHeader *)getResourceAddress(rtString, readVar(array1));
+		assert(ah1);
+		ArrayHeader *ah2 = (ArrayHeader *)getResourceAddress(rtString, readVar(array2));
+		assert(ah2);
+		if (FROM_LE_32(ah1->type) == FROM_LE_32(ah2->type)) {
+			copyArrayHelper(ah1, a1_dim2start, a1_dim1start, a1_dim1end, &dst, &dstPitch, &rowSize);
+			copyArrayHelper(ah2, a2_dim2start, a2_dim1start, a2_dim1end, &src, &srcPitch, &rowSize);
+			for (; a1_dim2start <= a1_dim2end; ++a1_dim2start) {
+				memcpy(dst, src, rowSize);
+				dst += dstPitch;
+				src += srcPitch;
+			}
+		} else {
+			for (; a1_dim2start <= a1_dim2end; ++a1_dim2start, ++a2_dim2start) {
+				int a2dim1 = a2_dim1start;
+				int a1dim1 = a1_dim1start;
+				for(; a1dim1 <= a1_dim1end; ++a1dim1, ++a2dim1) {
+					int val = readArray(array2, a2_dim2start, a2dim1);
+					writeArray(array1, a1_dim2start, a1dim1, val);
+				}
+			}
+		}
+	} else {
+		if (a2_dim2start != a1_dim2start || a2_dim1start != a1_dim1start) {
+			ArrayHeader *ah = (ArrayHeader *)getResourceAddress(rtString, readVar(array1));
+			assert(ah);
+			if (a2_dim2start > a1_dim2start) {
+				copyArrayHelper(ah, a1_dim2start, a1_dim1start, a1_dim1end, &dst, &dstPitch, &rowSize);
+				copyArrayHelper(ah, a2_dim2start, a2_dim1start, a2_dim1end, &src, &srcPitch, &rowSize);
+			} else {
+				copyArrayHelper(ah, a1_dim2end, a1_dim1start, a1_dim1end, &dst, &dstPitch, &rowSize);
+				copyArrayHelper(ah, a2_dim2end, a2_dim1start, a2_dim1end, &src, &srcPitch, &rowSize);				
+			}
+			for (; a1_dim2start <= a1_dim2end; ++a1_dim2start) {
+				memcpy(dst, src, rowSize);
+				dst += dstPitch;
+				src += srcPitch;
+			}
+		}
+	}
+}
+
+void ScummEngine_v72he::copyArrayHelper(ArrayHeader *ah, int idx2, int idx1, int len1, byte **data, int *size, int *num) {
+	const int pitch = FROM_LE_32(ah->dim1end) - FROM_LE_32(ah->dim1start) + 1;
+	const int offset = pitch * (idx2 - FROM_LE_32(ah->dim2start)) + idx1 - FROM_LE_32(ah->dim1start);
+
+	switch (FROM_LE_32(ah->type)) {
+	case kByteArray:
+	case kStringArray:
+		*num = len1 - idx1 + 1;
+		*size = pitch;
+		*data = ah->data + offset;
+		break;
+	case kIntArray:
+		*num = (len1 - idx1 + 1) * 2;
+		*size = pitch * 2;
+		*data = ah->data + offset * 2;
+		break;
+	case kDwordArray:
+		*num = (len1 - idx1 + 1) * 4;
+		*size = pitch * 4;
+		*data = ah->data + offset * 4;
+		break;
+	default:
+		error("Invalid array type", FROM_LE_32(ah->type));
+		break;
+	}
+}
+
 void ScummEngine_v72he::o72_checkGlobQueue() {
 	byte subOp = fetchScriptByte();
 	int idx = pop();
diff --git a/scumm/script_v90he.cpp b/scumm/script_v90he.cpp
index 6a7cb369c3..c1f236b8fb 100644
--- a/scumm/script_v90he.cpp
+++ b/scumm/script_v90he.cpp
@@ -1960,6 +1960,103 @@ void ScummEngine_v90he::o90_redim2dimArray() {
 	}
 }
 
+void ScummEngine_v90he::getArrayDim(int array, int *dim2start, int *dim2end, int *dim1start, int *dim1end) {
+	ArrayHeader *ah = (ArrayHeader *)getResourceAddress(rtString, readVar(array));
+	assert(ah);
+	if (dim2start && *dim2start == -1) {
+		*dim2start = ah->dim2start;
+	}
+	if (dim2end && *dim2end == -1) {
+		*dim2end = ah->dim2end;
+	}
+	if (dim1start && *dim1start == -1) {
+		*dim1start = ah->dim1start;
+	}
+	if (dim1end && *dim1end == -1) {
+		*dim1end = ah->dim1end;
+	}
+}
+
+static int sortArrayOffset;
+
+static int compareByteArray(const void *a, const void *b) {
+	int va = *((const uint8 *)a + sortArrayOffset);
+	int vb = *((const uint8 *)a + sortArrayOffset);
+	return va - vb;
+}
+
+static int compareByteArrayReverse(const void *a, const void *b) {
+	int va = *((const uint8 *)a + sortArrayOffset);
+	int vb = *((const uint8 *)a + sortArrayOffset);
+	return vb - va;
+}
+
+static int compareIntArray(const void *a, const void *b) {
+	int va = READ_LE_UINT16((const uint8 *)a + sortArrayOffset * 2);
+	int vb = READ_LE_UINT16((const uint8 *)b + sortArrayOffset * 2);
+	return va - vb;
+}
+
+static int compareIntArrayReverse(const void *a, const void *b) {
+	int va = READ_LE_UINT16((const uint8 *)a + sortArrayOffset * 2);
+	int vb = READ_LE_UINT16((const uint8 *)b + sortArrayOffset * 2);
+	return vb - va;
+}
+
+static int compareDwordArray(const void *a, const void *b) {
+	int va = READ_LE_UINT32((const uint8 *)a + sortArrayOffset * 4);
+	int vb = READ_LE_UINT32((const uint8 *)b + sortArrayOffset * 4);
+	return va - vb;
+}
+
+static int compareDwordArrayReverse(const void *a, const void *b) {
+	int va = READ_LE_UINT32((const uint8 *)a + sortArrayOffset * 4);
+	int vb = READ_LE_UINT32((const uint8 *)b + sortArrayOffset * 4);
+	return vb - va;
+}
+
+void ScummEngine_v90he::sortArray(int array, int dim2start, int dim2end, int dim1start, int dim1end, int sortOrder) {
+	debug(5, "sortArray(%d, [%d,%d,%d,%d], %d)", array, dim2start, dim2end, dim1start, dim1end, sortOrder);
+
+	assert(dim1start == dim1end);
+	checkArrayLimits(array, dim2start, dim2end, dim1start, dim1end);
+	ArrayHeader *ah = (ArrayHeader *)getResourceAddress(rtString, readVar(array));
+	assert(ah);
+
+	const int num = dim2end - dim2start + 1;
+	const int pitch = FROM_LE_32(ah->dim1end) - FROM_LE_32(ah->dim1start) + 1;
+	const int offset = pitch * (dim2start - FROM_LE_32(ah->dim2start));
+	sortArrayOffset = dim1start - FROM_LE_32(ah->dim1start);
+
+	switch (FROM_LE_32(ah->type)) {
+	case kByteArray:
+	case kStringArray:
+		if (sortOrder <= 0) {
+			qsort(ah->data + offset, num, pitch, compareByteArray);
+		} else {
+			qsort(ah->data + offset, num, pitch, compareByteArrayReverse);
+		}
+		break;
+	case kIntArray:
+		if (sortOrder <= 0) {
+			qsort(ah->data + offset * 2, num, pitch * 2, compareIntArray);
+		} else {
+			qsort(ah->data + offset * 2, num, pitch * 2, compareIntArrayReverse);
+		}
+		break;
+	case kDwordArray:
+		if (sortOrder <= 0) {
+			qsort(ah->data + offset * 4, num, pitch * 4, compareDwordArray);
+		} else {
+			qsort(ah->data + offset * 4, num, pitch * 4, compareDwordArrayReverse);
+		}
+		break;
+	default:
+		error("Invalid array type", FROM_LE_32(ah->type));
+		break;
+	}
+}
+
 void ScummEngine_v90he::o90_sortArray() {
 	// Sorts array via qsort
 	byte subOp = fetchScriptByte();
@@ -1967,21 +2064,24 @@ void ScummEngine_v90he::o90_sortArray() {
 	switch (subOp) {
 	case 129:
 	case 134: // HE100
-		fetchScriptWord();
-		pop();
-		pop();
-		pop();
-		pop();
-		pop();
+		{	
+			int array = fetchScriptWord();
+			int sortOrder = pop();
+			int dim1end = pop();
+			int dim1start = pop();
+			int dim2end = pop();
+			int dim2start = pop();
+			getArrayDim(array, &dim2start, &dim2end, &dim1start, &dim1end);
+			sortArray(array, dim2start, dim2end, dim1start, dim1end, sortOrder);
+		}
 		break;
 	default:
 		error("o90_sortArray: Unknown case %d", subOp);
 	}
-	debug(1,"o90_sortArray stub (%d)", subOp);
 }
 
 void ScummEngine_v90he::o90_getObjectData() {
-	// Object releated
+	// Object related
 	byte subOp = fetchScriptByte();
 	subOp -= 32;