SCI32: Rewrite kArray & kString

This change invalidates earlier SCI32 save games, which separated
arrays and strings in an incompatible manner. Old save games
contain invalid references to a string segment which no longer
exists, and contain incompatible array structures that lack
critical type information.

22 files changed, 849 insertions, 731 deletions

diff --git a/engines/sci/console.cpp b/engines/sci/console.cpp
index 3f65ca799e..6d04b82dc6 100644
--- a/engines/sci/console.cpp
+++ b/engines/sci/console.cpp
@@ -2075,10 +2075,6 @@ bool Console::cmdPrintSegmentTable(int argc, const char **argv) {
 				debugPrintf("A  SCI32 arrays (%d)", (*(ArrayTable *)mobj).entries_used);
 				break;
 
-			case SEG_TYPE_STRING:
-				debugPrintf("T  SCI32 strings (%d)", (*(StringTable *)mobj).entries_used);
-				break;
-
 			case SEG_TYPE_BITMAP:
 				debugPrintf("T  SCI32 bitmaps (%d)", (*(BitmapTable *)mobj).entries_used);
 				break;
@@ -2210,9 +2206,6 @@ bool Console::segmentInfo(int nr) {
 	break;
 
 #ifdef ENABLE_SCI32
-	case SEG_TYPE_STRING:
-		debugPrintf("SCI32 strings\n");
-		break;
 	case SEG_TYPE_ARRAY:
 		debugPrintf("SCI32 arrays\n");
 		break;
@@ -2808,16 +2801,11 @@ bool Console::cmdViewReference(int argc, const char **argv) {
 		case SIG_TYPE_REFERENCE: {
 			switch (_engine->_gamestate->_segMan->getSegmentType(reg.getSegment())) {
 #ifdef ENABLE_SCI32
-				case SEG_TYPE_STRING: {
-					debugPrintf("SCI32 string\n");
-					const SciString *str = _engine->_gamestate->_segMan->lookupString(reg);
-					Common::hexdump((const byte *) str->getRawData(), str->getSize(), 16, 0);
-					break;
-				}
 				case SEG_TYPE_ARRAY: {
 					debugPrintf("SCI32 array:\n");
-					const SciArray<reg_t> *array = _engine->_gamestate->_segMan->lookupArray(reg);
-					hexDumpReg(array->getRawData(), array->getSize(), 4, 0, true);
+					// TODO: Different prints for different types
+					const SciArray *array = _engine->_gamestate->_segMan->lookupArray(reg);
+					hexDumpReg((reg_t *)array->getRawData(), array->size(), 4, 0, true);
 					break;
 				}
 				case SEG_TYPE_BITMAP: {
diff --git a/engines/sci/engine/gc.cpp b/engines/sci/engine/gc.cpp
index 6c1713bed9..50f7709baf 100644
--- a/engines/sci/engine/gc.cpp
+++ b/engines/sci/engine/gc.cpp
@@ -46,7 +46,7 @@ const char *segmentTypeNames[] = {
 	"dynmem",    // 9
 	"obsolete",  // 10: obsolete string fragments
 	"array",     // 11: SCI32 arrays
-	"string"     // 12: SCI32 strings
+	"obsolete"   // 12: obsolete SCI32 strings
 };
 #endif
 
diff --git a/engines/sci/engine/kernel.cpp b/engines/sci/engine/kernel.cpp
index c03504d277..85cad99226 100644
--- a/engines/sci/engine/kernel.cpp
+++ b/engines/sci/engine/kernel.cpp
@@ -410,7 +410,6 @@ uint16 Kernel::findRegType(reg_t reg) {
 	case SEG_TYPE_HUNK:
 #ifdef ENABLE_SCI32
 	case SEG_TYPE_ARRAY:
-	case SEG_TYPE_STRING:
 	case SEG_TYPE_BITMAP:
 #endif
 		result |= SIG_TYPE_REFERENCE;
diff --git a/engines/sci/engine/kernel.h b/engines/sci/engine/kernel.h
index 45477e1153..bd9d1bb770 100644
--- a/engines/sci/engine/kernel.h
+++ b/engines/sci/engine/kernel.h
@@ -484,29 +484,36 @@ reg_t kShowMovieWinPlayUntilEvent(EngineState *s, int argc, reg_t *argv);
 reg_t kShowMovieWinInitDouble(EngineState *s, int argc, reg_t *argv);
 
 reg_t kIsHiRes(EngineState *s, int argc, reg_t *argv);
-reg_t kArray(EngineState *s, int argc, reg_t *argv);
 reg_t kListAt(EngineState *s, int argc, reg_t *argv);
-reg_t kString(EngineState *s, int argc, reg_t *argv);
 
+reg_t kArray(EngineState *s, int argc, reg_t *argv);
+reg_t kArrayNew(EngineState *s, int argc, reg_t *argv);
+reg_t kArrayGetSize(EngineState *s, int argc, reg_t *argv);
+reg_t kArrayGetElement(EngineState *s, int argc, reg_t *argv);
+reg_t kArraySetElements(EngineState *s, int argc, reg_t *argv);
+reg_t kArrayFree(EngineState *s, int argc, reg_t *argv);
+reg_t kArrayFill(EngineState *s, int argc, reg_t *argv);
+reg_t kArrayCopy(EngineState *s, int argc, reg_t *argv);
+reg_t kArrayCompare(EngineState *s, int argc, reg_t *argv);
+reg_t kArrayDuplicate(EngineState *s, int argc, reg_t *argv);
+reg_t kArrayGetData(EngineState *s, int argc, reg_t *argv);
+reg_t kArrayByteCopy(EngineState *s, int argc, reg_t *argv);
+
+reg_t kString(EngineState *s, int argc, reg_t *argv);
 reg_t kStringNew(EngineState *s, int argc, reg_t *argv);
-reg_t kStringSize(EngineState *s, int argc, reg_t *argv);
-reg_t kStringAt(EngineState *s, int argc, reg_t *argv);
-reg_t kStringPutAt(EngineState *s, int argc, reg_t *argv);
+reg_t kStringGetChar(EngineState *s, int argc, reg_t *argv);
 reg_t kStringFree(EngineState *s, int argc, reg_t *argv);
-reg_t kStringFill(EngineState *s, int argc, reg_t *argv);
-reg_t kStringCopy(EngineState *s, int argc, reg_t *argv);
 reg_t kStringCompare(EngineState *s, int argc, reg_t *argv);
-reg_t kStringDup(EngineState *s, int argc, reg_t *argv);
 reg_t kStringGetData(EngineState *s, int argc, reg_t *argv);
-reg_t kStringLen(EngineState *s, int argc, reg_t *argv);
-reg_t kStringPrintf(EngineState *s, int argc, reg_t *argv);
-reg_t kStringPrintfBuf(EngineState *s, int argc, reg_t *argv);
-reg_t kStringAtoi(EngineState *s, int argc, reg_t *argv);
+reg_t kStringLength(EngineState *s, int argc, reg_t *argv);
+reg_t kStringFormat(EngineState *s, int argc, reg_t *argv);
+reg_t kStringFormatAt(EngineState *s, int argc, reg_t *argv);
+reg_t kStringToInteger(EngineState *s, int argc, reg_t *argv);
 reg_t kStringTrim(EngineState *s, int argc, reg_t *argv);
-reg_t kStringUpper(EngineState *s, int argc, reg_t *argv);
-reg_t kStringLower(EngineState *s, int argc, reg_t *argv);
-reg_t kStringTrn(EngineState *s, int argc, reg_t *argv);
-reg_t kStringTrnExclude(EngineState *s, int argc, reg_t *argv);
+reg_t kStringToUpperCase(EngineState *s, int argc, reg_t *argv);
+reg_t kStringToLowerCase(EngineState *s, int argc, reg_t *argv);
+reg_t kStringReplaceSubstring(EngineState *s, int argc, reg_t *argv);
+reg_t kStringReplaceSubstringEx(EngineState *s, int argc, reg_t *argv);
 
 reg_t kScrollWindowCreate(EngineState *s, int argc, reg_t *argv);
 reg_t kScrollWindowAdd(EngineState *s, int argc, reg_t *argv);
diff --git a/engines/sci/engine/kernel_tables.h b/engines/sci/engine/kernel_tables.h
index eafbe1227c..6630f1a98c 100644
--- a/engines/sci/engine/kernel_tables.h
+++ b/engines/sci/engine/kernel_tables.h
@@ -501,44 +501,56 @@ static const SciKernelMapSubEntry kRemapColors_subops[] = {
 };
 
 //    version,         subId, function-mapping,                    signature,              workarounds
+static const SciKernelMapSubEntry kArray_subops[] = {
+	{ SIG_SCI32,           0, MAP_CALL(ArrayNew),                  "ii",                   NULL },
+	{ SIG_SCI32,           1, MAP_CALL(ArrayGetSize),              "r",                    NULL },
+	{ SIG_SCI32,           2, MAP_CALL(ArrayGetElement),           "ri",                   NULL },
+	{ SIG_SCI32,           3, MAP_CALL(ArraySetElements),          "ri.*",                 kArraySetElements_workarounds },
+	{ SIG_SCI32,           4, MAP_CALL(ArrayFree),                 "r",                    NULL },
+	{ SIG_SCI32,           5, MAP_CALL(ArrayFill),                 "riii",                 NULL },
+	{ SIG_SCI32,           6, MAP_CALL(ArrayCopy),                 "ririi",                NULL },
+	// there is no subop 7
+	{ SIG_SCI32,           8, MAP_CALL(ArrayDuplicate),            "r",                    NULL },
+	{ SIG_SCI32,           9, MAP_CALL(ArrayGetData),              "[or]",                 NULL },
+	{ SIG_SCI3,           10, MAP_CALL(ArrayByteCopy),             "ririi",                NULL },
+	SCI_SUBOPENTRY_TERMINATOR
+};
+
+//    version,         subId, function-mapping,                    signature,              workarounds
 static const SciKernelMapSubEntry kString_subops[] = {
-	{ SIG_SCI32,           0, MAP_CALL(StringNew),                 "i(i)",                 NULL },
-	{ SIG_SCI32,           1, MAP_CALL(StringSize),                "[or]",                 NULL },
-	{ SIG_SCI32,           2, MAP_CALL(StringAt),                  "[or]i",                NULL },
-	{ SIG_SCI32,           3, MAP_CALL(StringPutAt),               "[or]i(i*)",            kStringPutAt_workarounds },
-	// StringFree accepts invalid references
-	{ SIG_SCI32,           4, MAP_CALL(StringFree),                "[or0!]",               NULL },
-	{ SIG_SCI32,           5, MAP_CALL(StringFill),                "[or]ii",               NULL },
-	{ SIG_SCI32,           6, MAP_CALL(StringCopy),                "[or]i[or]ii",          NULL },
-	{ SIG_SCI32,           7, MAP_CALL(StringCompare),             "[or][or](i)",          NULL },
-
-	// =SCI2, SCI2.1 Early and SCI2.1 Middle=
-	{ SIG_UNTIL_SCI21MID,  8, MAP_CALL(StringDup),                 "[or]",                 NULL },
-	// TODO: This gets called with null references in Torin. Check if this is correct, or it's
-	// caused by missing functionality
-	{ SIG_UNTIL_SCI21MID,  9, MAP_CALL(StringGetData),             "[or0]",                NULL },
-	{ SIG_UNTIL_SCI21MID, 10, MAP_CALL(StringLen),                 "[or]",                 NULL },
-	{ SIG_UNTIL_SCI21MID, 11, MAP_CALL(StringPrintf),              "[or](.*)",             NULL },
-	{ SIG_UNTIL_SCI21MID, 12, MAP_CALL(StringPrintfBuf),           "[or](.*)",             NULL },
-	{ SIG_UNTIL_SCI21MID, 13, MAP_CALL(StringAtoi),                "[or]",                 NULL },
-	{ SIG_UNTIL_SCI21MID, 14, MAP_CALL(StringTrim),                "[or]i",                NULL },
-	{ SIG_UNTIL_SCI21MID, 15, MAP_CALL(StringUpper),               "[or]",                 NULL },
-	{ SIG_UNTIL_SCI21MID, 16, MAP_CALL(StringLower),               "[or]",                 NULL },
-	// the following 2 are unknown atm (happen in Phantasmagoria)
-	// possibly translate?
-	{ SIG_UNTIL_SCI21MID, 17, MAP_CALL(StringTrn),                 "[or]",                 NULL },
-	{ SIG_UNTIL_SCI21MID, 18, MAP_CALL(StringTrnExclude),          "[or]",                 NULL },
-
-	// SCI2.1 Late + SCI3 - kStringDup + kStringGetData were removed
-	{ SIG_SINCE_SCI21LATE, 8, MAP_CALL(StringLen),                 "[or]",                 NULL },
-	{ SIG_SINCE_SCI21LATE, 9, MAP_CALL(StringPrintf),              "[or](.*)",             NULL },
-	{ SIG_SINCE_SCI21LATE,10, MAP_CALL(StringPrintfBuf),           "[or](.*)",             NULL },
-	{ SIG_SINCE_SCI21LATE,11, MAP_CALL(StringAtoi),                "[or]",                 NULL },
-	{ SIG_SINCE_SCI21LATE,12, MAP_CALL(StringTrim),                "[or]i",                NULL },
-	{ SIG_SINCE_SCI21LATE,13, MAP_CALL(StringUpper),               "[or]",                 NULL },
-	{ SIG_SINCE_SCI21LATE,14, MAP_CALL(StringLower),               "[or]",                 NULL },
-	{ SIG_SINCE_SCI21LATE,15, MAP_CALL(StringTrn),                 "[or]",                 NULL },
-	{ SIG_SINCE_SCI21LATE,16, MAP_CALL(StringTrnExclude),          "[or]",                 NULL },
+	// every single copy of script 64918 in SCI2 through 2.1mid calls StringNew
+	// with a second type argument which is unused (new strings are always type
+	// 3)
+	{ SIG_UNTIL_SCI21MID,  0, MAP_CALL(StringNew),                 "i(i)",                 NULL },
+	{ SIG_UNTIL_SCI21MID,  1, MAP_CALL(ArrayGetSize),              "r",                    NULL },
+	{ SIG_UNTIL_SCI21MID,  2, MAP_CALL(StringGetChar),             "ri",                   NULL },
+	{ SIG_UNTIL_SCI21MID,  3, MAP_CALL(ArraySetElements),          "rii*",                 kArraySetElements_workarounds },
+	{ SIG_UNTIL_SCI21MID,  4, MAP_CALL(StringFree),                "[0r]",                 NULL },
+	{ SIG_UNTIL_SCI21MID,  5, MAP_CALL(ArrayFill),                 "rii",                  NULL },
+	{ SIG_UNTIL_SCI21MID,  6, MAP_CALL(ArrayCopy),                 "ririi",                NULL },
+	{ SIG_SCI32,           7, MAP_CALL(StringCompare),             "rr(i)",                NULL },
+
+	{ SIG_UNTIL_SCI21MID,  8, MAP_CALL(ArrayDuplicate),            "r",                    NULL },
+	{ SIG_UNTIL_SCI21MID,  9, MAP_CALL(StringGetData),             "[0or]",                NULL },
+	{ SIG_UNTIL_SCI21MID, 10, MAP_CALL(StringLength),              "r",                    NULL },
+	{ SIG_UNTIL_SCI21MID, 11, MAP_CALL(StringFormat),              "r.*",                  NULL },
+	{ SIG_UNTIL_SCI21MID, 12, MAP_CALL(StringFormatAt),            "r[ro].*",              NULL },
+	{ SIG_UNTIL_SCI21MID, 13, MAP_CALL(StringToInteger),           "r",                    NULL },
+	{ SIG_UNTIL_SCI21MID, 14, MAP_CALL(StringTrim),                "ri(i)",                NULL },
+	{ SIG_UNTIL_SCI21MID, 15, MAP_CALL(StringToUpperCase),         "r",                    NULL },
+	{ SIG_UNTIL_SCI21MID, 16, MAP_CALL(StringToLowerCase),         "r",                    NULL },
+	{ SIG_UNTIL_SCI21MID, 17, MAP_CALL(StringReplaceSubstring),    "rrrr",                 NULL },
+	{ SIG_UNTIL_SCI21MID, 18, MAP_CALL(StringReplaceSubstringEx),  "rrrr",                 NULL },
+
+	{ SIG_SINCE_SCI21LATE, 8, MAP_CALL(StringLength),              "r",                    NULL },
+	{ SIG_SINCE_SCI21LATE, 9, MAP_CALL(StringFormat),              "r.*",                  NULL },
+	{ SIG_SINCE_SCI21LATE,10, MAP_CALL(StringFormatAt),            "rr.*",                 NULL },
+	{ SIG_SINCE_SCI21LATE,11, MAP_CALL(StringToInteger),           "r",                    NULL },
+	{ SIG_SINCE_SCI21LATE,12, MAP_CALL(StringTrim),                "ri(i)",                NULL },
+	{ SIG_SINCE_SCI21LATE,13, MAP_CALL(StringToUpperCase),         "r",                    NULL },
+	{ SIG_SINCE_SCI21LATE,14, MAP_CALL(StringToLowerCase),         "r",                    NULL },
+	{ SIG_SINCE_SCI21LATE,15, MAP_CALL(StringReplaceSubstring),    "rrrr",                 NULL },
+	{ SIG_SINCE_SCI21LATE,16, MAP_CALL(StringReplaceSubstringEx),  "rrrr",                 NULL },
 	SCI_SUBOPENTRY_TERMINATOR
 };
 
@@ -811,7 +823,7 @@ static SciKernelMapEntry s_kernelMap[] = {
 
 	{ MAP_CALL(AddPlane),          SIG_EVERYWHERE,           "o",                     NULL,            NULL },
 	{ MAP_CALL(AddScreenItem),     SIG_EVERYWHERE,           "o",                     NULL,            NULL },
-	{ MAP_CALL(Array),             SIG_EVERYWHERE,           "(.*)",                  NULL,            NULL },
+	{ MAP_CALL(Array),             SIG_EVERYWHERE,           "(.*)",                  kArray_subops,   NULL },
 	{ MAP_CALL(CreateTextBitmap),  SIG_EVERYWHERE,           "i(.*)",                 NULL,            NULL },
 	{ MAP_CALL(DeletePlane),       SIG_EVERYWHERE,           "o",                     NULL,            NULL },
 	{ MAP_CALL(DeleteScreenItem),  SIG_EVERYWHERE,           "o",                     NULL,            NULL },
diff --git a/engines/sci/engine/kfile.cpp b/engines/sci/engine/kfile.cpp
index e8b9d0461d..324eaf27ea 100644
--- a/engines/sci/engine/kfile.cpp
+++ b/engines/sci/engine/kfile.cpp
@@ -693,8 +693,8 @@ reg_t kFileIOCreateSaveSlot(EngineState *s, int argc, reg_t *argv) {
 	// We don't really use or need any of this...
 
 	uint16 saveSlot = argv[0].toUint16();
-	char* fileName = s->_segMan->lookupString(argv[1])->getRawData();
-	warning("kFileIOCreateSaveSlot(%d, '%s')", saveSlot, fileName);
+	const SciArray &fileName = *s->_segMan->lookupArray(argv[1]);
+	warning("kFileIOCreateSaveSlot(%d, '%s')", saveSlot, fileName.toString().c_str());
 
 	return TRUE_REG;	// slot creation was successful
 }
@@ -1051,7 +1051,7 @@ reg_t kMakeSaveFileName(EngineState *s, int argc, reg_t *argv) {
 	// Param 1: a string with game parameters, ignored
 	// Param 2: the selected slot
 
-	SciString *resultString = s->_segMan->lookupString(argv[0]);
+	SciArray *resultString = s->_segMan->lookupArray(argv[0]);
 	uint16 virtualId = argv[2].toUint16();
 	if ((virtualId < SAVEGAMEID_OFFICIALRANGE_START) || (virtualId > SAVEGAMEID_OFFICIALRANGE_END))
 		error("kMakeSaveFileName: invalid savegame ID specified");
diff --git a/engines/sci/engine/kgraphics32.cpp b/engines/sci/engine/kgraphics32.cpp
index a33fcf3167..3c7a3c2e31 100644
--- a/engines/sci/engine/kgraphics32.cpp
+++ b/engines/sci/engine/kgraphics32.cpp
@@ -317,7 +317,7 @@ reg_t kText(EngineState *s, int argc, reg_t *argv) {
 reg_t kTextSize32(EngineState *s, int argc, reg_t *argv) {
 	g_sci->_gfxText32->setFont(argv[2].toUint16());
 
-	reg_t *rect = s->_segMan->derefRegPtr(argv[0], 4);
+	SciArray *rect = s->_segMan->lookupArray(argv[0]);
 	if (rect == nullptr) {
 		error("kTextSize: %04x:%04x cannot be dereferenced", PRINT_REG(argv[0]));
 	}
@@ -327,10 +327,14 @@ reg_t kTextSize32(EngineState *s, int argc, reg_t *argv) {
 	bool doScaling = argc > 4 ? argv[4].toSint16() : true;
 
 	Common::Rect textRect = g_sci->_gfxText32->getTextSize(text, maxWidth, doScaling);
-	rect[0] = make_reg(0, textRect.left);
-	rect[1] = make_reg(0, textRect.top);
-	rect[2] = make_reg(0, textRect.right - 1);
-	rect[3] = make_reg(0, textRect.bottom - 1);
+
+	reg_t value[4] = {
+		make_reg(0, textRect.left),
+		make_reg(0, textRect.top),
+		make_reg(0, textRect.right - 1),
+		make_reg(0, textRect.bottom - 1) };
+
+	rect->setElements(0, 4, value);
 	return s->r_acc;
 }
 
diff --git a/engines/sci/engine/klists.cpp b/engines/sci/engine/klists.cpp
index db6ffb1310..5cd9c3623d 100644
--- a/engines/sci/engine/klists.cpp
+++ b/engines/sci/engine/klists.cpp
@@ -683,197 +683,105 @@ reg_t kMoveToEnd(EngineState *s, int argc, reg_t *argv) {
 }
 
 reg_t kArray(EngineState *s, int argc, reg_t *argv) {
-	uint16 op = argv[0].toUint16();
-
-	// Use kString when accessing strings
-	// This is possible, as strings inherit from arrays
-	// and in this case (type 3) arrays are of type char *.
-	// kString is almost exactly the same as kArray, so
-	// this call is possible
-	// TODO: we need to either merge SCI2 strings and
-	// arrays together, and in the future merge them with
-	// the SCI1 strings and arrays in the segment manager
-	bool callStringFunc = false;
-	if (op == 0) {
-		// New, check if the target type is 3 (string)
-		if (argv[2].toUint16() == 3)
-			callStringFunc = true;
-	} else {
-		if (s->_segMan->getSegmentType(argv[1].getSegment()) == SEG_TYPE_STRING ||
-			s->_segMan->getSegmentType(argv[1].getSegment()) == SEG_TYPE_SCRIPT) {
-			callStringFunc = true;
-		}
-
-#if 0
-		if (op == 6) {
-			if (s->_segMan->getSegmentType(argv[3].getSegment()) == SEG_TYPE_STRING ||
-				s->_segMan->getSegmentType(argv[3].getSegment()) == SEG_TYPE_SCRIPT) {
-				callStringFunc = true;
-			}
-		}
-#endif
-	}
+	if (!s)
+		return make_reg(0, getSciVersion());
+	error("not supposed to call this");
+}
 
-	if (callStringFunc) {
-		Kernel *kernel = g_sci->getKernel();
-		uint16 kernelStringFuncId = kernel->_kernelFunc_StringId;
-		if (kernelStringFuncId) {
-			const KernelFunction *kernelStringFunc = &kernel->_kernelFuncs[kernelStringFuncId];
-
-			if (op < kernelStringFunc->subFunctionCount) {
-				// subfunction-id is valid
-				const KernelSubFunction *kernelStringSubCall = &kernelStringFunc->subFunctions[op];
-				argc--;
-				argv++; // remove subfunction-id from arguments
-				// and call the kString subfunction
-				return kernelStringSubCall->function(s, argc, argv);
-			}
-		}
-	}
+reg_t kArrayNew(EngineState *s, int argc, reg_t *argv) {
+	uint16 size = argv[0].toUint16();
+	const SciArrayType type = (SciArrayType)argv[1].toUint16();
 
-	switch (op) {
-	case 0: { // New
-		reg_t arrayHandle;
-		SciArray<reg_t> *array = s->_segMan->allocateArray(&arrayHandle);
-		array->setType(argv[2].toUint16());
-		array->setSize(argv[1].toUint16());
-		return arrayHandle;
-	}
-	case 1: { // Size
-		SciArray<reg_t> *array = s->_segMan->lookupArray(argv[1]);
-		return make_reg(0, array->getSize());
+	if (type == kArrayTypeString) {
+		++size;
 	}
-	case 2: { // At (return value at an index)
-		SciArray<reg_t> *array = s->_segMan->lookupArray(argv[1]);
-		if (g_sci->getGameId() == GID_PHANTASMAGORIA2) {
-			// HACK: Phantasmagoria 2 keeps trying to access past the end of an
-			// array when it starts. I'm assuming it's trying to see where the
-			// array ends, or tries to resize it. Adjust the array size
-			// accordingly, and return NULL for now.
-			if (array->getSize() == argv[2].toUint16()) {
-				array->setSize(argv[2].toUint16());
-				return NULL_REG;
-			}
-		}
-		return array->getValue(argv[2].toUint16());
-	}
-	case 3: { // Atput (put value at an index)
-		SciArray<reg_t> *array = s->_segMan->lookupArray(argv[1]);
-
-		uint32 index = argv[2].toUint16();
-		uint32 count = argc - 3;
 
-		if (index + count > 65535)
-			break;
+	reg_t arrayHandle;
+	s->_segMan->allocateArray(type, size, &arrayHandle);
+	return arrayHandle;
+}
 
-		if (array->getSize() < index + count)
-			array->setSize(index + count);
+reg_t kArrayGetSize(EngineState *s, int argc, reg_t *argv) {
+	const SciArray &array = *s->_segMan->lookupArray(argv[0]);
+	return make_reg(0, array.size());
+}
 
-		for (uint16 i = 0; i < count; i++)
-			array->setValue(i + index, argv[i + 3]);
+reg_t kArrayGetElement(EngineState *s, int argc, reg_t *argv) {
+	SciArray &array = *s->_segMan->lookupArray(argv[0]);
+	return array.getAsID(argv[1].toUint16());
+}
 
-		return argv[1]; // We also have to return the handle
-	}
-	case 4: // Free
-		// Freeing of arrays is handled by the garbage collector
-		return s->r_acc;
-	case 5: { // Fill
-		SciArray<reg_t> *array = s->_segMan->lookupArray(argv[1]);
-		uint16 index = argv[2].toUint16();
+reg_t kArraySetElements(EngineState *s, int argc, reg_t *argv) {
+	SciArray &array = *s->_segMan->lookupArray(argv[0]);
+	array.setElements(argv[1].toUint16(), argc - 2, argv + 2);
+	return argv[0];
+}
 
-		// A count of -1 means fill the rest of the array
-		uint16 count = argv[3].toSint16() == -1 ? array->getSize() - index : argv[3].toUint16();
-		uint16 arraySize = array->getSize();
+reg_t kArrayFree(EngineState *s, int argc, reg_t *argv) {
+	s->_segMan->freeArray(argv[0]);
+	return s->r_acc;
+}
 
-		if (arraySize < index + count)
-			array->setSize(index + count);
+reg_t kArrayFill(EngineState *s, int argc, reg_t *argv) {
+	SciArray &array = *s->_segMan->lookupArray(argv[0]);
+	array.fill(argv[1].toUint16(), argv[2].toUint16(), argv[3]);
+	return argv[0];
+}
 
-		for (uint16 i = 0; i < count; i++)
-			array->setValue(i + index, argv[4]);
+reg_t kArrayCopy(EngineState *s, int argc, reg_t *argv) {
+	SciArray &target = *s->_segMan->lookupArray(argv[0]);
+	const uint16 targetIndex = argv[1].toUint16();
 
-		return argv[1];
+	SciArray source;
+	// String copies may be made from static script data
+	if (!s->_segMan->isArray(argv[2])) {
+		source.setType(kArrayTypeString);
+		source.fromString(s->_segMan->getString(argv[2]));
+	} else {
+		source = *s->_segMan->lookupArray(argv[2]);
 	}
-	case 6: { // Cpy
-		if (argv[1].isNull() || argv[3].isNull()) {
-			if (getSciVersion() == SCI_VERSION_3) {
-				// FIXME: Happens in SCI3, probably because of a missing kernel function.
-				warning("kArray(Cpy): Request to copy from or to a null pointer");
-				return NULL_REG;
-			} else {
-				// SCI2-2.1: error out
-				error("kArray(Cpy): Request to copy from or to a null pointer");
-			}
-		}
+	const uint16 sourceIndex = argv[3].toUint16();
+	const uint16 count = argv[4].toUint16();
 
-		reg_t arrayHandle = argv[1];
-		SciArray<reg_t> *array1 = s->_segMan->lookupArray(argv[1]);
-		SciArray<reg_t> *array2 = s->_segMan->lookupArray(argv[3]);
-		uint32 index1 = argv[2].toUint16();
-		uint32 index2 = argv[4].toUint16();
-
-		// The original engine ignores bad copies too
-		if (index2 > array2->getSize())
-			break;
-
-		// A count of -1 means fill the rest of the array
-		uint32 count = argv[5].toSint16() == -1 ? array2->getSize() - index2 : argv[5].toUint16();
-
-		if (array1->getSize() < index1 + count)
-			array1->setSize(index1 + count);
+	target.copy(source, sourceIndex, targetIndex, count);
+	return argv[0];
+}
 
-		for (uint16 i = 0; i < count; i++)
-			array1->setValue(i + index1, array2->getValue(i + index2));
+reg_t kArrayDuplicate(EngineState *s, int argc, reg_t *argv) {
+	reg_t targetHandle;
 
-		return arrayHandle;
+	// String duplicates may be made from static script data
+	if (!s->_segMan->isArray(argv[0])) {
+		const Common::String source = s->_segMan->getString(argv[0]);
+		SciArray &target = *s->_segMan->allocateArray(kArrayTypeString, source.size(), &targetHandle);
+		target.fromString(source);
+	} else {
+		SciArray &source = *s->_segMan->lookupArray(argv[0]);
+		SciArray &target = *s->_segMan->allocateArray(source.getType(), source.size(), &targetHandle);
+		target = source;
 	}
-	case 7: // Cmp
-		// Not implemented in SSCI
-		warning("kArray(Cmp) called");
-		return s->r_acc;
-	case 8: { // Dup
-		if (argv[1].isNull()) {
-			warning("kArray(Dup): Request to duplicate a null pointer");
-#if 0
-			// Allocate an array anyway
-			reg_t arrayHandle;
-			SciArray<reg_t> *dupArray = s->_segMan->allocateArray(&arrayHandle);
-			dupArray->setType(3);
-			dupArray->setSize(0);
-			return arrayHandle;
-#endif
-			return NULL_REG;
-		}
-		SegmentObj *sobj = s->_segMan->getSegmentObj(argv[1].getSegment());
-		if (!sobj || sobj->getType() != SEG_TYPE_ARRAY)
-			error("kArray(Dup): Request to duplicate a segment which isn't an array");
-
-		reg_t arrayHandle;
-		SciArray<reg_t> *dupArray = s->_segMan->allocateArray(&arrayHandle);
-		// This must occur after allocateArray, as inserting a new object
-		// in the heap object list might invalidate this pointer. Also refer
-		// to the same issue in kClone()
-		SciArray<reg_t> *array = s->_segMan->lookupArray(argv[1]);
-
-		dupArray->setType(array->getType());
-		dupArray->setSize(array->getSize());
 
-		for (uint32 i = 0; i < array->getSize(); i++)
-			dupArray->setValue(i, array->getValue(i));
-
-		return arrayHandle;
-	}
-	case 9: // Getdata
-		if (!s->_segMan->isHeapObject(argv[1]))
-			return argv[1];
+	return targetHandle;
+}
 
-		return readSelector(s->_segMan, argv[1], SELECTOR(data));
-	default:
-		error("Unknown kArray subop %d", op);
+reg_t kArrayGetData(EngineState *s, int argc, reg_t *argv) {
+	if (s->_segMan->isObject(argv[0])) {
+		return readSelector(s->_segMan, argv[0], SELECTOR(data));
 	}
 
-	return NULL_REG;
+	return argv[0];
 }
 
+reg_t kArrayByteCopy(EngineState *s, int argc, reg_t *argv) {
+	SciArray &target = *s->_segMan->lookupArray(argv[0]);
+	const uint16 targetOffset = argv[1].toUint16();
+	const SciArray &source = *s->_segMan->lookupArray(argv[2]);
+	const uint16 sourceOffset = argv[3].toUint16();
+	const uint16 count = argv[4].toUint16();
+
+	target.byteCopy(source, sourceOffset, targetOffset, count);
+	return argv[0];
+}
 #endif
 
 } // End of namespace Sci
diff --git a/engines/sci/engine/kpathing.cpp b/engines/sci/engine/kpathing.cpp
index 06f16299aa..667f77f126 100644
--- a/engines/sci/engine/kpathing.cpp
+++ b/engines/sci/engine/kpathing.cpp
@@ -285,6 +285,13 @@ struct PathfindingState {
 static Common::Point readPoint(SegmentRef list_r, int offset) {
 	Common::Point point;
 
+#ifdef ENABLE_SCI32
+	if (getSciVersion() >= SCI_VERSION_2) {
+		point.x = READ_UINT16(list_r.raw + offset * POLY_POINT_SIZE + 0);
+		point.y = READ_UINT16(list_r.raw + offset * POLY_POINT_SIZE + 2);
+	} else
+#endif
+
 	if (list_r.isRaw) {	// dynmem blocks are raw
 		point.x = (int16)READ_SCIENDIAN_UINT16(list_r.raw + offset * POLY_POINT_SIZE);
 		point.y = (int16)READ_SCIENDIAN_UINT16(list_r.raw + offset * POLY_POINT_SIZE + 2);
@@ -296,6 +303,12 @@ static Common::Point readPoint(SegmentRef list_r, int offset) {
 }
 
 static void writePoint(SegmentRef ref, int offset, const Common::Point &point) {
+#ifdef ENABLE_SCI32
+	if (getSciVersion() >= SCI_VERSION_2) {
+		WRITE_UINT16(ref.raw + offset * POLY_POINT_SIZE + 0, point.x);
+		WRITE_UINT16(ref.raw + offset * POLY_POINT_SIZE + 2, point.y);
+	} else
+#endif
 	if (ref.isRaw) {	// dynmem blocks are raw
 		WRITE_SCIENDIAN_UINT16(ref.raw + offset * POLY_POINT_SIZE, point.x);
 		WRITE_SCIENDIAN_UINT16(ref.raw + offset * POLY_POINT_SIZE + 2, point.y);
@@ -1397,10 +1410,8 @@ static reg_t allocateOutputArray(SegManager *segMan, int size) {
 
 #ifdef ENABLE_SCI32
 	if (getSciVersion() >= SCI_VERSION_2) {
-		SciArray<reg_t> *array = segMan->allocateArray(&addr);
+		SciArray *array = segMan->allocateArray(kArrayTypeInt16, size * 2, &addr);
 		assert(array);
-		array->setType(0);
-		array->setSize(size * 2);
 		return addr;
 	}
 #endif
diff --git a/engines/sci/engine/kstring.cpp b/engines/sci/engine/kstring.cpp
index 1c08bf597c..4d96ddc64e 100644
--- a/engines/sci/engine/kstring.cpp
+++ b/engines/sci/engine/kstring.cpp
@@ -202,11 +202,6 @@ reg_t kReadNumber(EngineState *s, int argc, reg_t *argv) {
 }
 
 
-#define ALIGN_NONE 0
-#define ALIGN_RIGHT 1
-#define ALIGN_LEFT -1
-#define ALIGN_CENTER 2
-
 /*  Format(targ_address, textresnr, index_inside_res, ...)
 ** or
 **  Format(targ_address, heap_text_addr, ...)
@@ -214,6 +209,13 @@ reg_t kReadNumber(EngineState *s, int argc, reg_t *argv) {
 ** the supplied parameters and writes it to the targ_address.
 */
 reg_t kFormat(EngineState *s, int argc, reg_t *argv) {
+	enum {
+		ALIGN_NONE   = 0,
+		ALIGN_RIGHT  = 1,
+		ALIGN_LEFT   = -1,
+		ALIGN_CENTER = 2
+	};
+
 	uint16 *arguments;
 	reg_t dest = argv[0];
 	int maxsize = 4096; /* Arbitrary... */
@@ -301,12 +303,6 @@ reg_t kFormat(EngineState *s, int argc, reg_t *argv) {
 			case 's': { /* Copy string */
 				reg_t reg = argv[startarg + paramindex];
 
-#ifdef ENABLE_SCI32
-				// If the string is a string object, get to the actual string in the data selector
-				if (s->_segMan->isObject(reg))
-					reg = readSelector(s->_segMan, reg, SELECTOR(data));
-#endif
-
 				Common::String tempsource = g_sci->getKernel()->lookupText(reg,
 				                                  arguments[paramindex + 1]);
 				int slen = strlen(tempsource.c_str());
@@ -379,12 +375,6 @@ reg_t kFormat(EngineState *s, int argc, reg_t *argv) {
 			case 'u':
 				unsignedVar = true;
 			case 'd': { /* Copy decimal */
-				// In the new SCI2 kString function, %d is used for unsigned
-				// integers. An example is script 962 in Shivers - it uses %d
-				// to create file names.
-				if (getSciVersion() >= SCI_VERSION_2)
-					unsignedVar = true;
-
 				/* int templen; -- unused atm */
 				const char *format_string = "%d";
 
@@ -437,14 +427,6 @@ reg_t kFormat(EngineState *s, int argc, reg_t *argv) {
 
 	*target = 0; /* Terminate string */
 
-#ifdef ENABLE_SCI32
-	// Resize SCI32 strings if necessary
-	if (getSciVersion() >= SCI_VERSION_2) {
-		SciString *string = s->_segMan->lookupString(dest);
-		string->setSize(strlen(targetbuf) + 1);
-	}
-#endif
-
 	s->_segMan->strcpy(dest, targetbuf);
 
 	return dest; /* Return target addr */
@@ -661,238 +643,236 @@ reg_t kStrSplit(EngineState *s, int argc, reg_t *argv) {
 
 #ifdef ENABLE_SCI32
 
-// TODO: there is an unused second argument, happens at least in LSL6 right during the intro
+reg_t kString(EngineState *s, int argc, reg_t *argv) {
+	if (!s)
+		return make_reg(0, getSciVersion());
+	error("not supposed to call this");
+}
+
 reg_t kStringNew(EngineState *s, int argc, reg_t *argv) {
 	reg_t stringHandle;
-	SciString *string = s->_segMan->allocateString(&stringHandle);
-	string->setSize(argv[0].toUint16());
-
-	// Make sure the first character is a null character
-	if (string->getSize() > 0)
-		string->setValue(0, 0);
-
+	const uint16 size = argv[0].toUint16();
+	s->_segMan->allocateArray(kArrayTypeString, size, &stringHandle);
 	return stringHandle;
 }
 
-reg_t kStringSize(EngineState *s, int argc, reg_t *argv) {
-	return make_reg(0, s->_segMan->getString(argv[0]).size());
-}
-
-// At (return value at an index)
-reg_t kStringAt(EngineState *s, int argc, reg_t *argv) {
-	// Note that values are put in bytes to avoid sign extension
-	if (argv[0].getSegment() == s->_segMan->getStringSegmentId()) {
-		SciString *string = s->_segMan->lookupString(argv[0]);
-		byte val = string->getRawData()[argv[1].toUint16()];
-		return make_reg(0, val);
-	} else {
-		Common::String string = s->_segMan->getString(argv[0]);
-		byte val = string[argv[1].toUint16()];
-		return make_reg(0, val);
-	}
-}
-
-// Atput (put value at an index)
-reg_t kStringPutAt(EngineState *s, int argc, reg_t *argv) {
-	SciString *string = s->_segMan->lookupString(argv[0]);
+reg_t kStringGetChar(EngineState *s, int argc, reg_t *argv) {
+	const uint16 index = argv[1].toUint16();
 
-	uint32 index = argv[1].toUint16();
-	uint32 count = argc - 2;
+	// Game scripts may contain static raw string data
+	if (!s->_segMan->isArray(argv[0])) {
+		const Common::String string = s->_segMan->getString(argv[0]);
+		if (index >= string.size()) {
+			return make_reg(0, 0);
+		}
 
-	if (index + count > 65535)
-		return NULL_REG;
+		return make_reg(0, (byte)string[index]);
+	}
 
-	if (string->getSize() < index + count)
-		string->setSize(index + count);
+	SciArray &array = *s->_segMan->lookupArray(argv[0]);
 
-	for (uint16 i = 0; i < count; i++)
-		string->setValue(i + index, argv[i + 2].toUint16());
+	if (index >= array.size()) {
+		return make_reg(0, 0);
+	}
 
-	return argv[0]; // We also have to return the handle
+	return array.getAsID(index);
 }
 
 reg_t kStringFree(EngineState *s, int argc, reg_t *argv) {
-	// Freeing of strings is handled by the garbage collector
+	if (!argv[0].isNull()) {
+		s->_segMan->freeArray(argv[0]);
+	}
 	return s->r_acc;
 }
 
-reg_t kStringFill(EngineState *s, int argc, reg_t *argv) {
-	SciString *string = s->_segMan->lookupString(argv[0]);
-	uint16 index = argv[1].toUint16();
+reg_t kStringCompare(EngineState *s, int argc, reg_t *argv) {
+	const Common::String string1 = s->_segMan->getString(argv[0]);
+	const Common::String string2 = s->_segMan->getString(argv[1]);
 
-	// A count of -1 means fill the rest of the array
-	uint16 count = argv[2].toSint16() == -1 ? string->getSize() - index : argv[2].toUint16();
-	uint16 stringSize = string->getSize();
+	int result;
+	if (argc == 3) {
+		result = strncmp(string1.c_str(), string2.c_str(), argv[2].toUint16());
+	} else {
+		result = strcmp(string1.c_str(), string2.c_str());
+	}
 
-	if (stringSize < index + count)
-		string->setSize(index + count);
+	return make_reg(0, (result > 0) - (result < 0));
+}
 
-	for (uint16 i = 0; i < count; i++)
-		string->setValue(i + index, argv[3].toUint16());
+reg_t kStringGetData(EngineState *s, int argc, reg_t *argv) {
+	if (s->_segMan->isObject(argv[0])) {
+		return readSelector(s->_segMan, argv[0], SELECTOR(data));
+	}
 
 	return argv[0];
 }
 
-reg_t kStringCopy(EngineState *s, int argc, reg_t *argv) {
-	const char *string2 = 0;
-	uint32 string2Size = 0;
-	Common::String string;
+reg_t kStringLength(EngineState *s, int argc, reg_t *argv) {
+	return make_reg(0, s->_segMan->getString(argv[0]).size());
+}
 
-	if (argv[2].getSegment() == s->_segMan->getStringSegmentId()) {
-		SciString *sstr;
-		sstr = s->_segMan->lookupString(argv[2]);
-		string2 = sstr->getRawData();
-		string2Size = sstr->getSize();
-	} else {
-		string = s->_segMan->getString(argv[2]);
-		string2 = string.c_str();
-		string2Size = string.size() + 1;
+namespace {
+	bool isFlag(const char c) {
+		return strchr("-+ 0#", c);
 	}
 
-	uint32 index1 = argv[1].toUint16();
-	uint32 index2 = argv[3].toUint16();
-
-	if (argv[0] == argv[2]) {
-		// source and destination string are one and the same
-		if (index1 == index2) {
-			// even same index? ignore this call
-			// Happens in KQ7, when starting a chapter
-			return argv[0];
-		}
-		// TODO: this will crash, when setSize() is triggered later
-		// we need to exactly replicate original interpreter behavior
-		warning("kString(Copy): source is the same as destination string");
+	bool isPrecision(const char c) {
+		return strchr(".0123456789*", c);
 	}
 
-	// The original engine ignores bad copies too
-	if (index2 >= string2Size)
-		return NULL_REG;
+	bool isWidth(const char c) {
+		return strchr("0123456789*", c);
+	}
 
-	// A count of -1 means fill the rest of the array
-	uint32 count = string2Size - index2;
-	if (argv[4].toSint16() != -1) {
-		count = MIN(count, (uint32)argv[4].toUint16());
+	bool isLength(const char c) {
+		return strchr("hjlLtz", c);
 	}
-//	reg_t strAddress = argv[0];
 
-	SciString *string1 = s->_segMan->lookupString(argv[0]);
-	//SciString *string1 = !argv[1].isNull() ? s->_segMan->lookupString(argv[1]) : s->_segMan->allocateString(&strAddress);
+	bool isType(const char c) {
+		return strchr("dsuxXaAceEfFgGinop", c);
+	}
 
-	if (string1->getSize() < index1 + count)
-		string1->setSize(index1 + count);
+	bool isSignedType(const char type) {
+		return type == 'd' || type == 'i';
+	}
 
-	// Note: We're accessing from c_str() here because the
-	// string's size ignores the trailing 0 and therefore
-	// triggers an assert when doing string2[i + index2].
-	for (uint16 i = 0; i < count; i++)
-		string1->setValue(i + index1, string2[i + index2]);
+	bool isUnsignedType(const char type) {
+		return strchr("uxXoc", type);
+	}
 
-	return argv[0];
-}
+	bool isStringType(const char type) {
+		return type == 's';
+	}
 
-reg_t kStringCompare(EngineState *s, int argc, reg_t *argv) {
-	Common::String string1 = argv[0].isNull() ? "" : s->_segMan->getString(argv[0]);
-	Common::String string2 = argv[1].isNull() ? "" : s->_segMan->getString(argv[1]);
+	Common::String readPlaceholder(const char *&in, reg_t arg) {
+		const char *const start = in;
 
-	if (argc == 3) // Strncmp
-		return make_reg(0, strncmp(string1.c_str(), string2.c_str(), argv[2].toUint16()));
-	else           // Strcmp
-		return make_reg(0, strcmp(string1.c_str(), string2.c_str()));
-}
+		assert(*in == '%');
+		++in;
 
-// was removed for SCI2.1 Late+
-reg_t kStringDup(EngineState *s, int argc, reg_t *argv) {
-	reg_t stringHandle;
-
-	SciString *dupString = s->_segMan->allocateString(&stringHandle);
+		while (isFlag(*in)) {
+			++in;
+		}
+		while (isWidth(*in)) {
+			++in;
+		}
+		while (isPrecision(*in)) {
+			++in;
+		}
+		while (isLength(*in)) {
+			++in;
+		}
 
-	if (argv[0].getSegment() == s->_segMan->getStringSegmentId()) {
-		*dupString = *s->_segMan->lookupString(argv[0]);
-	} else {
-		dupString->fromString(s->_segMan->getString(argv[0]));
+		char format[64];
+		format[0] = '\0';
+		const char type = *in++;
+		Common::strlcpy(format, start, MIN<size_t>(64, in - start + 1));
+
+		if (isType(type)) {
+			if (isSignedType(type)) {
+				const int value = arg.toSint16();
+				return Common::String::format(format, value);
+			} else if (isUnsignedType(type)) {
+				const uint value = arg.toUint16();
+				return Common::String::format(format, value);
+			} else if (isStringType(type)) {
+				Common::String value;
+				SegManager *segMan = g_sci->getEngineState()->_segMan;
+				if (segMan->isObject(arg)) {
+					value = segMan->getString(readSelector(segMan, arg, SELECTOR(data)));
+				} else {
+					value = segMan->getString(arg);
+				}
+				return Common::String::format(format, value.c_str());
+			} else {
+				error("Unsupported format type %c", type);
+			}
+		} else {
+			return Common::String::format("%s", format);
+		}
 	}
+};
 
-	return stringHandle;
-}
-
-// was removed for SCI2.1 Late+
-reg_t kStringGetData(EngineState *s, int argc, reg_t *argv) {
-	if (!s->_segMan->isHeapObject(argv[0]))
-		return argv[0];
+Common::String format(const Common::String &source, int argc, const reg_t *argv) {
+	Common::String out;
+	const char *in = source.c_str();
+	int argIndex = 0;
+	while (*in != '\0') {
+		if (*in == '%') {
+			if (in[1] == '%') {
+				in += 2;
+				out += "%";
+				continue;
+			}
 
-	return readSelector(s->_segMan, argv[0], SELECTOR(data));
-}
+			assert(argIndex < argc);
+			out += readPlaceholder(in, argv[argIndex++]);
+		} else {
+			out += *in++;
+		}
+	}
 
-reg_t kStringLen(EngineState *s, int argc, reg_t *argv) {
-	return make_reg(0, s->_segMan->strlen(argv[0]));
+	return out;
 }
 
-reg_t kStringPrintf(EngineState *s, int argc, reg_t *argv) {
+reg_t kStringFormat(EngineState *s, int argc, reg_t *argv) {
 	reg_t stringHandle;
-	s->_segMan->allocateString(&stringHandle);
-
-	reg_t *adjustedArgs = new reg_t[argc + 1];
-	adjustedArgs[0] = stringHandle;
-	memcpy(&adjustedArgs[1], argv, argc * sizeof(reg_t));
-
-	kFormat(s, argc + 1, adjustedArgs);
-	delete[] adjustedArgs;
+	SciArray &target = *s->_segMan->allocateArray(kArrayTypeString, 0, &stringHandle);
+	reg_t source = argv[0];
+	// Str objects may be passed in place of direct references to string data
+	if (s->_segMan->isObject(argv[0])) {
+		source = readSelector(s->_segMan, argv[0], SELECTOR(data));
+	}
+	target.fromString(format(s->_segMan->getString(source), argc - 1, argv + 1));
 	return stringHandle;
 }
 
-reg_t kStringPrintfBuf(EngineState *s, int argc, reg_t *argv) {
-	return kFormat(s, argc, argv);
+reg_t kStringFormatAt(EngineState *s, int argc, reg_t *argv) {
+	SciArray &target = *s->_segMan->lookupArray(argv[0]);
+	reg_t source = argv[1];
+	// Str objects may be passed in place of direct references to string data
+	if (s->_segMan->isObject(argv[1])) {
+		source = readSelector(s->_segMan, argv[1], SELECTOR(data));
+	}
+	target.fromString(format(s->_segMan->getString(source), argc - 2, argv + 2));
+	return argv[0];
 }
 
-reg_t kStringAtoi(EngineState *s, int argc, reg_t *argv) {
-	Common::String string = s->_segMan->getString(argv[0]);
-	return make_reg(0, (uint16)atoi(string.c_str()));
+reg_t kStringToInteger(EngineState *s, int argc, reg_t *argv) {
+	return make_reg(0, (uint16)s->_segMan->getString(argv[0]).asUint64());
 }
 
 reg_t kStringTrim(EngineState *s, int argc, reg_t *argv) {
-	Common::String string = s->_segMan->getString(argv[0]);
-
-	string.trim();
-	// TODO: Second parameter (bitfield, trim from left, right, center)
-	warning("kStringTrim (%d)", argv[1].getOffset());
-	s->_segMan->strcpy(argv[0], string.c_str());
-	return NULL_REG;
+	SciArray &array = *s->_segMan->lookupArray(argv[0]);
+	const int8 flags = argv[1].toSint16();
+	const char showChar = argc > 2 ? argv[2].toSint16() : '\0';
+	array.trim(flags, showChar);
+	return s->r_acc;
 }
 
-reg_t kStringUpper(EngineState *s, int argc, reg_t *argv) {
+reg_t kStringToUpperCase(EngineState *s, int argc, reg_t *argv) {
 	Common::String string = s->_segMan->getString(argv[0]);
-
 	string.toUppercase();
 	s->_segMan->strcpy(argv[0], string.c_str());
-	return NULL_REG;
+	return argv[0];
 }
 
-reg_t kStringLower(EngineState *s, int argc, reg_t *argv) {
+reg_t kStringToLowerCase(EngineState *s, int argc, reg_t *argv) {
 	Common::String string = s->_segMan->getString(argv[0]);
-
 	string.toLowercase();
 	s->_segMan->strcpy(argv[0], string.c_str());
-	return NULL_REG;
-}
-
-// Possibly kStringTranslate?
-reg_t kStringTrn(EngineState *s, int argc, reg_t *argv) {
-	warning("kStringTrn (argc = %d)", argc);
-	return NULL_REG;
+	return argv[0];
 }
 
-// Possibly kStringTranslateExclude?
-reg_t kStringTrnExclude(EngineState *s, int argc, reg_t *argv) {
-	warning("kStringTrnExclude (argc = %d)", argc);
-	return NULL_REG;
+reg_t kStringReplaceSubstring(EngineState *s, int argc, reg_t *argv) {
+	error("TODO: kStringReplaceSubstring not implemented");
+	return argv[3];
 }
 
-reg_t kString(EngineState *s, int argc, reg_t *argv) {
-	if (!s)
-		return make_reg(0, getSciVersion());
-	error("not supposed to call this");
+reg_t kStringReplaceSubstringEx(EngineState *s, int argc, reg_t *argv) {
+	error("TODO: kStringReplaceSubstringEx not implemented");
+	return argv[3];
 }
-
 #endif
 
 } // End of namespace Sci
diff --git a/engines/sci/engine/kvideo.cpp b/engines/sci/engine/kvideo.cpp
index 46829cceef..ab216c51cf 100644
--- a/engines/sci/engine/kvideo.cpp
+++ b/engines/sci/engine/kvideo.cpp
@@ -253,11 +253,13 @@ reg_t kRobotGetFrameSize(EngineState *s, int argc, reg_t *argv) {
 	Common::Rect frameRect;
 	const uint16 numFramesTotal = g_sci->_video32->getRobotPlayer().getFrameSize(frameRect);
 
-	reg_t *outRect = s->_segMan->derefRegPtr(argv[0], 4);
-	outRect[0] = make_reg(0, frameRect.left);
-	outRect[1] = make_reg(0, frameRect.top);
-	outRect[2] = make_reg(0, frameRect.right - 1);
-	outRect[3] = make_reg(0, frameRect.bottom - 1);
+	SciArray *outRect = s->_segMan->lookupArray(argv[0]);
+	reg_t values[4] = {
+		make_reg(0, frameRect.left),
+		make_reg(0, frameRect.top),
+		make_reg(0, frameRect.right - 1),
+		make_reg(0, frameRect.bottom - 1) };
+	outRect->setElements(0, 4, values);
 
 	return make_reg(0, numFramesTotal);
 }
diff --git a/engines/sci/engine/message.cpp b/engines/sci/engine/message.cpp
index 5300b72b71..b0615b4213 100644
--- a/engines/sci/engine/message.cpp
+++ b/engines/sci/engine/message.cpp
@@ -439,21 +439,8 @@ Common::String MessageState::processString(const char *s) {
 void MessageState::outputString(reg_t buf, const Common::String &str) {
 #ifdef ENABLE_SCI32
 	if (getSciVersion() >= SCI_VERSION_2) {
-		if (_segMan->getSegmentType(buf.getSegment()) == SEG_TYPE_STRING) {
-			SciString *sciString = _segMan->lookupString(buf);
-			sciString->setSize(str.size() + 1);
-			for (uint32 i = 0; i < str.size(); i++)
-				sciString->setValue(i, str.c_str()[i]);
-			sciString->setValue(str.size(), 0);
-		} else if (_segMan->getSegmentType(buf.getSegment()) == SEG_TYPE_ARRAY) {
-			// Happens in the intro of LSL6, we are asked to write the string
-			// into an array
-			SciArray<reg_t> *sciString = _segMan->lookupArray(buf);
-			sciString->setSize(str.size() + 1);
-			for (uint32 i = 0; i < str.size(); i++)
-				sciString->setValue(i, make_reg(0, str.c_str()[i]));
-			sciString->setValue(str.size(), NULL_REG);
-		}
+		SciArray *sciString = _segMan->lookupArray(buf);
+		sciString->fromString(str);
 	} else {
 #endif
 		SegmentRef buffer_r = _segMan->dereference(buf);
diff --git a/engines/sci/engine/savegame.cpp b/engines/sci/engine/savegame.cpp
index be2d7660cb..9def79c918 100644
--- a/engines/sci/engine/savegame.cpp
+++ b/engines/sci/engine/savegame.cpp
@@ -102,66 +102,6 @@ void syncWithSerializer(Common::Serializer &s, Node &obj) {
 	syncWithSerializer(s, obj.value);
 }
 
-#ifdef ENABLE_SCI32
-void syncWithSerializer(Common::Serializer &s, SciArray<reg_t> &obj) {
-	byte type = 0;
-	uint32 size = 0;
-
-	if (s.isSaving()) {
-		type = (byte)obj.getType();
-		size = obj.getSize();
-	}
-	s.syncAsByte(type);
-	s.syncAsUint32LE(size);
-	if (s.isLoading()) {
-		obj.setType((int8)type);
-
-		// HACK: Skip arrays that have a negative type
-		if ((int8)type < 0)
-			return;
-
-		obj.setSize(size);
-	}
-
-	for (uint32 i = 0; i < size; i++) {
-		reg_t value;
-
-		if (s.isSaving())
-			value = obj.getValue(i);
-
-		syncWithSerializer(s, value);
-
-		if (s.isLoading())
-			obj.setValue(i, value);
-	}
-}
-
-void syncWithSerializer(Common::Serializer &s, SciString &obj) {
-	uint32 size = 0;
-
-	if (s.isSaving()) {
-		size = obj.getSize();
-		s.syncAsUint32LE(size);
-	} else {
-		s.syncAsUint32LE(size);
-		obj.setSize(size);
-	}
-
-	for (uint32 i = 0; i < size; i++) {
-		char value = 0;
-
-		if (s.isSaving())
-			value = obj.getValue(i);
-
-		s.syncAsByte(value);
-
-		if (s.isLoading())
-			obj.setValue(i, value);
-	}
-}
-
-#endif
-
 #pragma mark -
 
 // By default, sync using syncWithSerializer, which in turn can easily be overloaded.
@@ -292,9 +232,6 @@ void SegManager::saveLoadWithSerializer(Common::Serializer &s) {
 		} else if (type == SEG_TYPE_ARRAY) {
 			// Set the correct segment for SCI32 arrays
 			_arraysSegId = i;
-		} else if (type == SEG_TYPE_STRING) {
-			// Set the correct segment for SCI32 strings
-			_stringSegId = i;
 		} else if (s.getVersion() >= 36 && type == SEG_TYPE_BITMAP) {
 			_bitmapSegId = i;
 #endif
@@ -707,11 +644,39 @@ void ArrayTable::saveLoadWithSerializer(Common::Serializer &ser) {
 	sync_Table<ArrayTable>(ser, *this);
 }
 
-void StringTable::saveLoadWithSerializer(Common::Serializer &ser) {
-	if (ser.getVersion() < 18)
-		return;
+void SciArray::saveLoadWithSerializer(Common::Serializer &s) {
+	uint16 size;
+
+	if (s.isSaving()) {
+		size = _size;
+	}
+
+	s.syncAsByte(_type);
+	s.syncAsByte(_elementSize);
+	s.syncAsUint16LE(size);
+
+	if (s.isLoading()) {
+		resize(size);
+	}
 
-	sync_Table<StringTable>(ser, *this);
+	switch (_type) {
+	case kArrayTypeByte:
+	case kArrayTypeString:
+		s.syncBytes((byte *)_data, size);
+		break;
+	case kArrayTypeInt16:
+		for (int i = 0; i < size; ++i) {
+			s.syncAsUint16LE(((int16 *)_data)[i]);
+		}
+		break;
+	case kArrayTypeID:
+		for (int i = 0; i < size; ++i) {
+			syncWithSerializer(s, ((reg_t *)_data)[i]);
+		}
+		break;
+	default:
+		error("Attempt to sync invalid SciArray type %d", _type);
+	}
 }
 
 void BitmapTable::saveLoadWithSerializer(Common::Serializer &ser) {
diff --git a/engines/sci/engine/savegame.h b/engines/sci/engine/savegame.h
index 6616081a20..5995de7818 100644
--- a/engines/sci/engine/savegame.h
+++ b/engines/sci/engine/savegame.h
@@ -37,7 +37,7 @@ struct EngineState;
  *
  * Version - new/changed feature
  * =============================
- *      38 - SCI32 cursor
+ *      38 - SCI32 cursor, accurate SCI32 arrays/strings
  *      37 - Segment entry data changed to pointers
  *      36 - SCI32 bitmap segment
  *      35 - SCI32 remap
diff --git a/engines/sci/engine/seg_manager.cpp b/engines/sci/engine/seg_manager.cpp
index 5cf8d6162d..ced3830a29 100644
--- a/engines/sci/engine/seg_manager.cpp
+++ b/engines/sci/engine/seg_manager.cpp
@@ -42,7 +42,6 @@ SegManager::SegManager(ResourceManager *resMan, ScriptPatcher *scriptPatcher)
 
 #ifdef ENABLE_SCI32
 	_arraysSegId = 0;
-	_stringSegId = 0;
 	_bitmapSegId = 0;
 #endif
 
@@ -72,7 +71,6 @@ void SegManager::resetSegMan() {
 
 #ifdef ENABLE_SCI32
 	_arraysSegId = 0;
-	_stringSegId = 0;
 	_bitmapSegId = 0;
 #endif
 
@@ -88,9 +86,8 @@ void SegManager::initSysStrings() {
 		_parserPtr = make_reg(_saveDirPtr.getSegment(), _saveDirPtr.getOffset() + 256);
 #ifdef ENABLE_SCI32
 	} else {
-		SciString *saveDirString = allocateString(&_saveDirPtr);
-		saveDirString->setSize(256);
-		saveDirString->setValue(0, 0);
+		SciArray *saveDirString = allocateArray(kArrayTypeString, 256, &_saveDirPtr);
+		saveDirString->byteAt(0) = '\0';
 
 		_parserPtr = NULL_REG;	// no SCI2 game had a parser
 #endif
@@ -863,7 +860,10 @@ bool SegManager::freeDynmem(reg_t addr) {
 }
 
 #ifdef ENABLE_SCI32
-SciArray<reg_t> *SegManager::allocateArray(reg_t *addr) {
+#pragma mark -
+#pragma mark Arrays
+
+SciArray *SegManager::allocateArray(SciArrayType type, uint16 size, reg_t *addr) {
 	ArrayTable *table;
 	int offset;
 
@@ -875,10 +875,14 @@ SciArray<reg_t> *SegManager::allocateArray(reg_t *addr) {
 	offset = table->allocEntry();
 
 	*addr = make_reg(_arraysSegId, offset);
-	return &table->at(offset);
+
+	SciArray *array = &table->at(offset);
+	array->setType(type);
+	array->resize(size);
+	return array;
 }
 
-SciArray<reg_t> *SegManager::lookupArray(reg_t addr) {
+SciArray *SegManager::lookupArray(reg_t addr) {
 	if (_heap[addr.getSegment()]->getType() != SEG_TYPE_ARRAY)
 		error("Attempt to use non-array %04x:%04x as array", PRINT_REG(addr));
 
@@ -899,48 +903,11 @@ void SegManager::freeArray(reg_t addr) {
 	if (!arrayTable.isValidEntry(addr.getOffset()))
 		error("Attempt to use non-array %04x:%04x as array", PRINT_REG(addr));
 
-	arrayTable[addr.getOffset()].destroy();
 	arrayTable.freeEntry(addr.getOffset());
 }
 
-SciString *SegManager::allocateString(reg_t *addr) {
-	StringTable *table;
-	int offset;
-
-	if (!_stringSegId) {
-		table = (StringTable *)allocSegment(new StringTable(), &(_stringSegId));
-	} else
-		table = (StringTable *)_heap[_stringSegId];
-
-	offset = table->allocEntry();
-
-	*addr = make_reg(_stringSegId, offset);
-	return &table->at(offset);
-}
-
-SciString *SegManager::lookupString(reg_t addr) {
-	if (_heap[addr.getSegment()]->getType() != SEG_TYPE_STRING)
-		error("lookupString: Attempt to use non-string %04x:%04x as string", PRINT_REG(addr));
-
-	StringTable &stringTable = *(StringTable *)_heap[addr.getSegment()];
-
-	if (!stringTable.isValidEntry(addr.getOffset()))
-		error("lookupString: Attempt to use non-string %04x:%04x as string", PRINT_REG(addr));
-
-	return &(stringTable[addr.getOffset()]);
-}
-
-void SegManager::freeString(reg_t addr) {
-	if (_heap[addr.getSegment()]->getType() != SEG_TYPE_STRING)
-		error("freeString: Attempt to use non-string %04x:%04x as string", PRINT_REG(addr));
-
-	StringTable &stringTable = *(StringTable *)_heap[addr.getSegment()];
-
-	if (!stringTable.isValidEntry(addr.getOffset()))
-		error("freeString: Attempt to use non-string %04x:%04x as string", PRINT_REG(addr));
-
-	stringTable[addr.getOffset()].destroy();
-	stringTable.freeEntry(addr.getOffset());
+bool SegManager::isArray(reg_t addr) const {
+	return addr.getSegment() == _arraysSegId;
 }
 
 #pragma mark -
diff --git a/engines/sci/engine/seg_manager.h b/engines/sci/engine/seg_manager.h
index 8ed1c3a143..60d0ee5b83 100644
--- a/engines/sci/engine/seg_manager.h
+++ b/engines/sci/engine/seg_manager.h
@@ -433,14 +433,10 @@ public:
 	reg_t getParserPtr() const { return _parserPtr; }
 
 #ifdef ENABLE_SCI32
-	SciArray<reg_t> *allocateArray(reg_t *addr);
-	SciArray<reg_t> *lookupArray(reg_t addr);
+	SciArray *allocateArray(SciArrayType type, uint16 size, reg_t *addr);
+	SciArray *lookupArray(reg_t addr);
 	void freeArray(reg_t addr);
-
-	SciString *allocateString(reg_t *addr);
-	SciString *lookupString(reg_t addr);
-	void freeString(reg_t addr);
-	SegmentId getStringSegmentId() { return _stringSegId; }
+	bool isArray(reg_t addr) const;
 
 	SciBitmap *allocateBitmap(reg_t *addr, const int16 width, const int16 height, const uint8 skipColor = kDefaultSkipColor, const int16 displaceX = 0, const int16 displaceY = 0, const int16 scaledWidth = kLowResX, const int16 scaledHeight = kLowResY, const uint32 paletteSize = 0, const bool remap = false, const bool gc = true);
 	SciBitmap *lookupBitmap(reg_t addr);
@@ -469,7 +465,6 @@ private:
 
 #ifdef ENABLE_SCI32
 	SegmentId _arraysSegId;
-	SegmentId _stringSegId;
 	SegmentId _bitmapSegId;
 #endif
 
diff --git a/engines/sci/engine/segment.cpp b/engines/sci/engine/segment.cpp
index 7943946ee4..11331f0599 100644
--- a/engines/sci/engine/segment.cpp
+++ b/engines/sci/engine/segment.cpp
@@ -67,9 +67,6 @@ SegmentObj *SegmentObj::createSegmentObj(SegmentType type) {
 	case SEG_TYPE_ARRAY:
 		mem = new ArrayTable();
 		break;
-	case SEG_TYPE_STRING:
-		mem = new StringTable();
-		break;
 	case SEG_TYPE_BITMAP:
 		mem = new BitmapTable();
 		break;
@@ -254,63 +251,39 @@ SegmentRef DynMem::dereference(reg_t pointer) {
 
 SegmentRef ArrayTable::dereference(reg_t pointer) {
 	SegmentRef ret;
-	ret.isRaw = false;
-	ret.maxSize = at(pointer.getOffset()).getSize() * 2;
-	ret.reg = at(pointer.getOffset()).getRawData();
-	return ret;
-}
 
-void ArrayTable::freeAtAddress(SegManager *segMan, reg_t sub_addr) {
-	at(sub_addr.getOffset()).destroy();
-	freeEntry(sub_addr.getOffset());
+	SciArray &array = at(pointer.getOffset());
+	const bool isRaw = array.getType() != kArrayTypeID;
+
+	ret.isRaw = isRaw;
+	ret.maxSize = isRaw ? array.byteSize() : array.size();
+	if (isRaw) {
+		ret.raw = (byte *)array.getRawData();
+	} else {
+		ret.reg = (reg_t *)array.getRawData();
+	}
+	return ret;
 }
 
 Common::Array<reg_t> ArrayTable::listAllOutgoingReferences(reg_t addr) const {
-	Common::Array<reg_t> tmp;
+	Common::Array<reg_t> refs;
 	if (!isValidEntry(addr.getOffset())) {
-		error("Invalid array referenced for outgoing references: %04x:%04x", PRINT_REG(addr));
+		// Scripts may still hold references to array memory that has been
+		// explicitly freed; ignore these references
+		return refs;
 	}
 
-	const SciArray<reg_t> *array = &at(addr.getOffset());
-
-	for (uint32 i = 0; i < array->getSize(); i++) {
-		reg_t value = array->getValue(i);
-		if (value.getSegment() != 0)
-			tmp.push_back(value);
+	SciArray &array = const_cast<SciArray &>(at(addr.getOffset()));
+	if (array.getType() == kArrayTypeID) {
+		for (uint16 i = 0; i < array.size(); ++i) {
+			const reg_t value = array.getAsID(i);
+			if (value.isPointer()) {
+				refs.push_back(value);
+			}
+		}
 	}
 
-	return tmp;
-}
-
-Common::String SciString::toString() const {
-	if (_type != 3)
-		error("SciString::toString(): Array is not a string");
-
-	Common::String string;
-	for (uint32 i = 0; i < _size && _data[i] != 0; i++)
-		string += _data[i];
-
-	return string;
-}
-
-void SciString::fromString(const Common::String &string) {
-	if (_type != 3)
-		error("SciString::fromString(): Array is not a string");
-
-	setSize(string.size() + 1);
-
-	for (uint32 i = 0; i < string.size(); i++)
-		_data[i] = string[i];
-
-	_data[string.size()] = 0;
-}
-
-SegmentRef StringTable::dereference(reg_t pointer) {
-	SegmentRef ret;
-	ret.isRaw = true;
-	ret.maxSize = at(pointer.getOffset()).getSize();
-	ret.raw = (byte *)at(pointer.getOffset()).getRawData();
-	return ret;
+	return refs;
 }
 
 #endif
diff --git a/engines/sci/engine/segment.h b/engines/sci/engine/segment.h
index add5f4c57c..39376e380c 100644
--- a/engines/sci/engine/segment.h
+++ b/engines/sci/engine/segment.h
@@ -24,7 +24,7 @@
 #define SCI_ENGINE_SEGMENT_H
 
 #include "common/serializer.h"
-
+#include "common/str.h"
 #include "sci/engine/object.h"
 #include "sci/engine/vm.h"
 #include "sci/engine/vm_types.h"	// for reg_t
@@ -70,7 +70,7 @@ enum SegmentType {
 
 #ifdef ENABLE_SCI32
 	SEG_TYPE_ARRAY = 11,
-	SEG_TYPE_STRING = 12,
+	// 12 used to be string, now obsolete
 	SEG_TYPE_BITMAP = 13,
 #endif
 
@@ -408,142 +408,459 @@ public:
 
 #ifdef ENABLE_SCI32
 
-template<typename T>
-class SciArray {
+#pragma mark -
+#pragma mark Arrays
+
+enum SciArrayType {
+	kArrayTypeInt16   = 0,
+	kArrayTypeID      = 1,
+	kArrayTypeByte    = 2,
+	kArrayTypeString  = 3,
+	// Type 4 was for 32-bit integers; never used
+	kArrayTypeInvalid = 5
+};
+
+enum SciArrayTrim {
+	kArrayTrimRight  = 1, ///< Trim whitespace after the last non-whitespace character
+	kArrayTrimCenter = 2, ///< Trim whitespace between non-whitespace characters
+	kArrayTrimLeft   = 4  ///< Trim whitespace before the first non-whitespace character
+};
+
+class SciArray : public Common::Serializable {
 public:
-	SciArray() : _type(-1), _data(NULL), _size(0), _actualSize(0) { }
+	SciArray() :
+		_type(kArrayTypeInvalid),
+		_size(0),
+		_data(nullptr) {}
 
-	SciArray(const SciArray<T> &array) {
+	SciArray(const SciArray &array) {
 		_type = array._type;
 		_size = array._size;
-		_actualSize = array._actualSize;
-		_data = new T[_actualSize];
+		_elementSize = array._elementSize;
+		_data = malloc(_elementSize * _size);
 		assert(_data);
-		memcpy(_data, array._data, _size * sizeof(T));
+		memcpy(_data, array._data, _elementSize * _size);
 	}
 
-	SciArray<T>& operator=(const SciArray<T> &array) {
+	SciArray &operator=(const SciArray &array) {
 		if (this == &array)
 			return *this;
 
-		delete[] _data;
+		free(_data);
 		_type = array._type;
 		_size = array._size;
-		_actualSize = array._actualSize;
-		_data = new T[_actualSize];
+		_elementSize = array._elementSize;
+		_data = malloc(_elementSize * _size);
 		assert(_data);
-		memcpy(_data, array._data, _size * sizeof(T));
+		memcpy(_data, array._data, _elementSize * _size);
 
 		return *this;
 	}
 
 	virtual ~SciArray() {
-		destroy();
+		free(_data);
+		_size = 0;
+		_type = kArrayTypeInvalid;
 	}
 
-	virtual void destroy() {
-		delete[] _data;
-		_data = NULL;
-		_type = -1;
-		_size = _actualSize = 0;
-	}
+	void saveLoadWithSerializer(Common::Serializer &s);
 
-	void setType(byte type) {
-		if (_type >= 0)
-			error("SciArray::setType(): Type already set");
+	/**
+	 * Returns the type of this array.
+	 */
+	SciArrayType getType() const {
+		return _type;
+	}
 
+	/**
+	 * Sets the type of this array. The type of the array may only be set once.
+	 */
+	void setType(SciArrayType type) {
+		assert(_type == kArrayTypeInvalid);
+		switch(type) {
+		case kArrayTypeID:
+			_elementSize = sizeof(reg_t);
+			break;
+		case kArrayTypeInt16:
+			_elementSize = sizeof(int16);
+			break;
+		case kArrayTypeString:
+			_elementSize = sizeof(char);
+			break;
+		case kArrayTypeByte:
+			_elementSize = sizeof(byte);
+			break;
+		default:
+			error("Invalid array type %d", type);
+		}
 		_type = type;
 	}
 
-	void setSize(uint32 size) {
-		if (_type < 0)
-			error("SciArray::setSize(): No type set");
+	/**
+	 * Returns the size of the array, in elements.
+	 */
+	uint16 size() const {
+		return _size;
+	}
 
-		// Check if we don't have to do anything
-		if (_size == size)
-			return;
+	/**
+	 * Returns the size of the array, in bytes.
+	 */
+	uint16 byteSize() const {
+		return _size * _elementSize;
+	}
 
-		// Check if we don't have to expand the array
-		if (size <= _actualSize) {
-			_size = size;
-			return;
+	/**
+	 * Ensures the array is large enough to store at least the given number of
+	 * values given in `newSize`. If `force` is true, the array will be resized
+	 * to store exactly `newSize` values. New values are initialized to zero.
+	 */
+	void resize(uint16 newSize, const bool force = false) {
+		if (force || newSize > _size) {
+			_data = realloc(_data, _elementSize * newSize);
+			if (newSize > _size) {
+				memset((byte *)_data + _elementSize * _size, 0, (newSize - _size) * _elementSize);
+			}
+			_size = newSize;
 		}
+	}
+
+	/**
+	 * Shrinks a string array to its optimal size.
+	 */
+	void snug() {
+		assert(_type == kArrayTypeString || _type == kArrayTypeByte);
+		resize(strlen((char *)_data) + 1, true);
+	}
 
-		// So, we're going to have to create an array of some sort
-		T *newArray = new T[size];
-		memset(newArray, 0, size * sizeof(T));
+	/**
+	 * Returns a pointer to the array's raw data storage.
+	 */
+	void *getRawData() { return _data; }
+	const void *getRawData() const { return _data; }
 
-		// Check if we never created an array before
-		if (!_data) {
-			_size = _actualSize = size;
-			_data = newArray;
-			return;
+	/**
+	 * Gets the value at the given index as a reg_t.
+	 */
+	reg_t getAsID(const uint16 index) {
+		if (getSciVersion() >= SCI_VERSION_3) {
+			resize(index);
+		} else {
+			assert(index < _size);
 		}
 
-		// Copy data from the old array to the new
-		memcpy(newArray, _data, _size * sizeof(T));
+		switch(_type) {
+		case kArrayTypeInt16:
+			return make_reg(0, ((int16 *)_data)[index]);
+		case kArrayTypeByte:
+		case kArrayTypeString:
+			return make_reg(0, ((byte *)_data)[index]);
+		case kArrayTypeID:
+			return ((reg_t *)_data)[index];
+		default:
+			error("Invalid array type %d", _type);
+		}
+	}
+
+	/**
+	 * Sets the value at the given index from a reg_t.
+	 */
+	void setFromID(const uint16 index, const reg_t value) {
+		if (getSciVersion() >= SCI_VERSION_3) {
+			resize(index);
+		} else {
+			assert(index < _size);
+		}
 
-		// Now set the new array to the old and set the sizes
-		delete[] _data;
-		_data = newArray;
-		_size = _actualSize = size;
+		switch(_type) {
+		case kArrayTypeInt16:
+			((int16 *)_data)[index] = value.toSint16();
+			break;
+		case kArrayTypeByte:
+		case kArrayTypeString:
+			((byte *)_data)[index] = value.toSint16();
+			break;
+		case kArrayTypeID:
+			((reg_t *)_data)[index] = value;
+			break;
+		default:
+			error("Invalid array type %d", _type);
+		}
 	}
 
-	T getValue(uint16 index) const {
-		if (index >= _size)
-			error("SciArray::getValue(): %d is out of bounds (%d)", index, _size);
+	/**
+	 * Returns a reference to the byte at the given index. Only valid for
+	 * string and byte arrays.
+	 */
+	byte &byteAt(const uint16 index) {
+		assert(_type == kArrayTypeString || _type == kArrayTypeByte);
 
-		return _data[index];
+		if (getSciVersion() >= SCI_VERSION_3) {
+			resize(index);
+		} else {
+			assert(index < _size);
+		}
+
+		return ((byte *)_data)[index];
 	}
 
-	void setValue(uint16 index, T value) {
-		if (index >= _size)
-			error("SciArray::setValue(): %d is out of bounds (%d)", index, _size);
+	/**
+	 * Returns a reference to the char at the given index. Only valid for
+	 * string and byte arrays.
+	 */
+	char &charAt(const uint16 index) {
+		assert(_type == kArrayTypeString || _type == kArrayTypeByte);
 
-		_data[index] = value;
+		if (getSciVersion() >= SCI_VERSION_3) {
+			resize(index);
+		} else {
+			assert(index < _size);
+		}
+
+		return ((char *)_data)[index];
 	}
 
-	byte getType() const { return _type; }
-	uint32 getSize() const { return _size; }
-	T *getRawData() { return _data; }
-	const T *getRawData() const { return _data; }
+	/**
+	 * Returns a reference to the int16 at the given index. Only valid for int16
+	 * arrays.
+	 */
+	int16 &int16At(const uint16 index) {
+		assert(_type == kArrayTypeInt16);
 
-protected:
-	int8 _type;
-	T *_data;
-	uint32 _size; // _size holds the number of entries that the scripts have requested
-	uint32 _actualSize; // _actualSize is the actual numbers of entries allocated
-};
+		if (getSciVersion() >= SCI_VERSION_3) {
+			resize(index);
+		} else {
+			assert(index < _size);
+		}
 
-class SciString : public SciArray<char> {
-public:
-	SciString() : SciArray<char>() { setType(3); }
+		return ((int16 *)_data)[index];
+	}
+
+	/**
+	 * Returns a reference to the reg_t at the given index. Only valid for ID
+	 * arrays.
+	 */
+	reg_t &IDAt(const uint16 index) {
+		assert(_type == kArrayTypeID);
 
-	// We overload destroy to ensure the string type is 3 after destroying
-	void destroy() { SciArray<char>::destroy(); _type = 3; }
+		if (getSciVersion() >= SCI_VERSION_3) {
+			resize(index);
+		} else {
+			assert(index < _size);
+		}
 
-	Common::String toString() const;
-	void fromString(const Common::String &string);
-};
+		return ((reg_t *)_data)[index];
+	}
 
-struct ArrayTable : public SegmentObjTable<SciArray<reg_t> > {
-	ArrayTable() : SegmentObjTable<SciArray<reg_t> >(SEG_TYPE_ARRAY) {}
+	/**
+	 * Reads values from the given reg_t pointer and sets them in the array,
+	 * growing the array if needed to store all values.
+	 */
+	void setElements(const uint16 index, uint16 count, const reg_t *values) {
+		resize(index + count);
+
+		switch (_type) {
+		case kArrayTypeInt16: {
+			const reg_t *source = values;
+			int16 *target = (int16 *)_data + index;
+			while (count--) {
+				assert(source->isNumber());
+				*target++ = source->toSint16();
+				++source;
+			}
+			break;
+		}
+		case kArrayTypeID: {
+			const reg_t *source = values;
+			reg_t *target = (reg_t *)_data + index;
+			while (count--) {
+				*target++ = *source++;
+			}
+			break;
+		}
+		case kArrayTypeByte:
+		case kArrayTypeString: {
+			const reg_t *source = values;
+			byte *target = (byte *)_data + index;
+			while (count--) {
+				assert(source->isNumber());
+				*target++ = source->getOffset();
+				++source;
+			}
+			break;
+		}
+		default:
+			error("Attempted write to SciArray with invalid type %d", _type);
+		}
+	}
 
-	virtual void freeAtAddress(SegManager *segMan, reg_t sub_addr);
-	virtual Common::Array<reg_t> listAllOutgoingReferences(reg_t object) const;
+	/**
+	 * Fills the array with the given value. Existing values will be
+	 * overwritten. The array will be grown if needed to store all values.
+	 */
+	void fill(const uint16 index, uint16 count, const reg_t value) {
+		if (count == 65535 /* -1 */) {
+			count = size() - index;
+		}
 
-	void saveLoadWithSerializer(Common::Serializer &ser);
-	SegmentRef dereference(reg_t pointer);
-};
+		if (!count) {
+			return;
+		}
 
-struct StringTable : public SegmentObjTable<SciString> {
-	StringTable() : SegmentObjTable<SciString>(SEG_TYPE_STRING) {}
+		resize(index + count);
 
-	virtual void freeAtAddress(SegManager *segMan, reg_t sub_addr) {
-		at(sub_addr.getOffset()).destroy();
-		freeEntry(sub_addr.getOffset());
+		switch (_type) {
+		case kArrayTypeInt16: {
+			const int16 fillValue = value.toSint16();
+			int16 *target = (int16 *)_data + index;
+			while (count--) {
+				*target++ = fillValue;
+			}
+			break;
+		}
+		case kArrayTypeID: {
+			reg_t *target = (reg_t *)_data + index;
+			while (count--) {
+				*target = value;
+			}
+			break;
+		}
+		case kArrayTypeByte:
+		case kArrayTypeString: {
+			byte *target = (byte *)_data + index;
+			const byte fillValue = value.getOffset();
+			while (count--) {
+				*target = fillValue;
+			}
+			break;
+		}
+		case kArrayTypeInvalid:
+			error("Attempted write to uninitialized SciArray");
+		}
+	}
+
+	/**
+	 * Copies values from the source array. Both arrays will be grown if needed
+	 * to prevent out-of-bounds reads/writes.
+	 */
+	void copy(SciArray &source, const uint16 sourceIndex, const uint16 targetIndex, uint16 count) {
+		if (count == 65535 /* -1 */) {
+			count = source.size() - sourceIndex;
+		}
+
+		if (!count) {
+			return;
+		}
+
+		resize(targetIndex + count);
+		source.resize(sourceIndex + count);
+
+		assert(source._elementSize == _elementSize);
+
+		const byte *sourceData = (byte *)source._data + sourceIndex * source._elementSize;
+		byte *targetData = (byte *)_data + targetIndex * _elementSize;
+		memmove(targetData, sourceData, count * _elementSize);
+	}
+
+	void byteCopy(const SciArray &source, const uint16 sourceOffset, const uint16 targetOffset, const uint16 count) {
+		error("SciArray::byteCopy not implemented");
 	}
 
+	/**
+	 * Removes whitespace from string data held in this array.
+	 */
+	void trim(const int8 flags, const char showChar) {
+		enum {
+			kWhitespaceBoundary = 32,
+			kAsciiBoundary = 128
+		};
+
+		byte *data = (byte *)_data;
+		byte *source;
+		byte *target;
+
+		if (flags & kArrayTrimLeft) {
+			target = data;
+			source = data;
+			while (*source != '\0' && *source != showChar && *source <= kWhitespaceBoundary) {
+				++source;
+			}
+			strcpy((char *)target, (char *)source);
+		}
+
+		if (flags & kArrayTrimRight) {
+			source = data + strlen((char *)data) - 1;
+			while (source > data && *source != showChar && *source <= kWhitespaceBoundary) {
+				--source;
+			}
+			*source = '\0';
+		}
+
+		if (flags & kArrayTrimCenter) {
+			target = data;
+			while (*target && *target <= kWhitespaceBoundary && *target != showChar) {
+				++target;
+			}
+
+			if (*target) {
+				while (*target && (*target > kWhitespaceBoundary || *target == showChar)) {
+					++target;
+				}
+
+				if (*target) {
+					source = target;
+					while (*source) {
+						while (*source && *source <= kWhitespaceBoundary && *source != showChar) {
+							++source;
+						}
+
+						while (*source && (*source > kWhitespaceBoundary || *source == showChar)) {
+							*target++ = *source++;
+						}
+					}
+
+					--source;
+					while (source > target && (*source <= kWhitespaceBoundary || *source >= kAsciiBoundary) && *source != showChar) {
+						--source;
+					}
+					++source;
+
+					memmove(target, source, strlen((char *)source) + 1);
+				}
+			}
+		}
+	}
+	
+	/**
+	 * Copies the string data held by this array into a new Common::String.
+	 */
+	Common::String toString() const {
+		assert(_type == kArrayTypeString);
+		return Common::String((char *)_data);
+	}
+
+	/**
+	 * Copies the string from the given Common::String into this array.
+	 */
+	void fromString(const Common::String &string) {
+		// At least LSL6hires uses a byte-type array to hold string data
+		assert(_type == kArrayTypeString || _type == kArrayTypeByte);
+		resize(string.size() + 1, true);
+		Common::strlcpy((char *)_data, string.c_str(), string.size() + 1);
+	}
+
+protected:
+	void *_data;
+	SciArrayType _type;
+	uint16 _size;
+	uint8 _elementSize;
+};
+
+struct ArrayTable : public SegmentObjTable<SciArray> {
+	ArrayTable() : SegmentObjTable<SciArray>(SEG_TYPE_ARRAY) {}
+
+	virtual Common::Array<reg_t> listAllOutgoingReferences(reg_t object) const;
+
 	void saveLoadWithSerializer(Common::Serializer &ser);
 	SegmentRef dereference(reg_t pointer);
 };
diff --git a/engines/sci/engine/workarounds.cpp b/engines/sci/engine/workarounds.cpp
index 68f5f4c7d6..71ffda5fa0 100644
--- a/engines/sci/engine/workarounds.cpp
+++ b/engines/sci/engine/workarounds.cpp
@@ -396,6 +396,12 @@ const SciWorkaroundEntry kAbs_workarounds[] = {
 };
 
 //    gameID,           room,script,lvl,          object-name, method-name, local-call-signature, index,                workaround
+const SciWorkaroundEntry kArraySetElements_workarounds[] = {
+	{ GID_PHANTASMAGORIA,902, 64918,  0,                "Str", "callKernel",                NULL,     0, { WORKAROUND_FAKE, 0 } }, // tries to set an element of a string array to the ego object when starting a new game and selecting a chapter above 1
+	SCI_WORKAROUNDENTRY_TERMINATOR
+};
+
+//    gameID,           room,script,lvl,          object-name, method-name, local-call-signature, index,                workaround
 const SciWorkaroundEntry kCelHigh_workarounds[] = {
 	{ GID_KQ5,            -1,   255,  0,          "deathIcon", "setSize",                   NULL,     0, { WORKAROUND_STILLCALL, 0 } }, // english floppy: when getting beaten up in the inn and probably more, called with 2nd parameter as object - bug #5049
 	{ GID_PQ2,            -1,   255,  0,              "DIcon", "setSize",                   NULL,     0, { WORKAROUND_STILLCALL, 0 } }, // when showing picture within windows, called with 2nd/3rd parameters as objects
@@ -767,13 +773,9 @@ const SciWorkaroundEntry kUnLoad_workarounds[] = {
 };
 
 //    gameID,           room,script,lvl,          object-name, method-name,  local-call-signature, index,                workaround
-const SciWorkaroundEntry kStringPutAt_workarounds[] = {
-	{ GID_PHANTASMAGORIA,902, 64918, 0,                 "Str", "callKernel",                 NULL,     0, { WORKAROUND_IGNORE, 0 } }, // When starting a new game from after chapter 1, the game tries to save ego's object in a string
-};
-
-//    gameID,           room,script,lvl,          object-name, method-name,  local-call-signature, index,                workaround
 const SciWorkaroundEntry kScrollWindowAdd_workarounds[] = {
 	{ GID_PHANTASMAGORIA, 45, 64907,  0,   "ScrollableWindow", "addString",                  NULL,     0, { WORKAROUND_STILLCALL, 0 } }, // ScrollWindow interface passes the last two parameters twice
+	SCI_WORKAROUNDENTRY_TERMINATOR
 };
 
 SciWorkaroundSolution trackOriginAndFindWorkaround(int index, const SciWorkaroundEntry *workaroundList, SciCallOrigin *trackOrigin) {
diff --git a/engines/sci/engine/workarounds.h b/engines/sci/engine/workarounds.h
index 2f7a9e56e2..5304fceb31 100644
--- a/engines/sci/engine/workarounds.h
+++ b/engines/sci/engine/workarounds.h
@@ -89,12 +89,13 @@ extern const SciWorkaroundEntry kRandom_workarounds[];
 extern const SciWorkaroundEntry kReadNumber_workarounds[];
 extern const SciWorkaroundEntry kPaletteUnsetFlag_workarounds[];
 extern const SciWorkaroundEntry kSetCursor_workarounds[];
+extern const SciWorkaroundEntry kArraySetElements_workarounds[];
 extern const SciWorkaroundEntry kSetPort_workarounds[];
 extern const SciWorkaroundEntry kStrAt_workarounds[];
 extern const SciWorkaroundEntry kStrCpy_workarounds[];
 extern const SciWorkaroundEntry kStrLen_workarounds[];
 extern const SciWorkaroundEntry kUnLoad_workarounds[];
-extern const SciWorkaroundEntry kStringPutAt_workarounds[];
+extern const SciWorkaroundEntry kStringNew_workarounds[];
 extern const SciWorkaroundEntry kScrollWindowAdd_workarounds[];
 
 extern SciWorkaroundSolution trackOriginAndFindWorkaround(int index, const SciWorkaroundEntry *workaroundList, SciCallOrigin *trackOrigin);
diff --git a/engines/sci/graphics/controls32.cpp b/engines/sci/graphics/controls32.cpp
index bdc7248708..89997d38a5 100644
--- a/engines/sci/graphics/controls32.cpp
+++ b/engines/sci/graphics/controls32.cpp
@@ -313,8 +313,8 @@ reg_t GfxControls32::kernelEditText(const reg_t controlObject) {
 
 	if (textChanged) {
 		editor.text.trim();
-		SciString *string = _segMan->lookupString(textObject);
-		string->fromString(editor.text);
+		SciArray &string = *_segMan->lookupArray(textObject);
+		string.fromString(editor.text);
 	}
 
 	return make_reg(0, textChanged);
diff --git a/engines/sci/graphics/transitions32.cpp b/engines/sci/graphics/transitions32.cpp
index e98f783922..c45017efd4 100644
--- a/engines/sci/graphics/transitions32.cpp
+++ b/engines/sci/graphics/transitions32.cpp
@@ -267,9 +267,9 @@ void GfxTransitions32::kernelSetShowStyle(const uint16 argc, const reg_t planeOb
 				// NOTE: SCI2.1mid engine does no check to verify that an array is
 				// successfully retrieved, and SegMan will cause a fatal error
 				// if we try to use a memory segment that is not an array
-				SciArray<reg_t> *table = _segMan->lookupArray(pFadeArray);
+				SciArray &table = *_segMan->lookupArray(pFadeArray);
 
-				uint32 rangeCount = table->getSize();
+				uint32 rangeCount = table.size();
 				entry->fadeColorRangesCount = rangeCount;
 
 				// NOTE: SCI engine code always allocates memory even if the range
@@ -278,7 +278,7 @@ void GfxTransitions32::kernelSetShowStyle(const uint16 argc, const reg_t planeOb
 				if (rangeCount > 0) {
 					entry->fadeColorRanges = new uint16[rangeCount];
 					for (size_t i = 0; i < rangeCount; ++i) {
-						entry->fadeColorRanges[i] = table->getValue(i).toUint16();
+						entry->fadeColorRanges[i] = table.int16At(i);
 					}
 				}
 			}