SCI: Refactor relocation code

This groundwork enables an object to look up its static name
separately from the normal process that is used to populate
Object::_variables when an object is first constructed.

(The static name property needs to be able to be retrieved from
objects inside of earlier save games whose name properties may
have already been modified at runtime, so the code cannot simply
pluck the value out of Object::_variables when they are first
initialised and then persisted into the save game, as nice and
easy as that would have been.)

This commit also helps to clarify the situation with relocation
tables in SCI1 games that start with a zero entry.

Refs Trac#9780.

6 files changed, 137 insertions, 58 deletions

diff --git a/engines/sci/engine/kscripts.cpp b/engines/sci/engine/kscripts.cpp
index af4b8ff081..75f905e81a 100644
--- a/engines/sci/engine/kscripts.cpp
+++ b/engines/sci/engine/kscripts.cpp
@@ -246,11 +246,7 @@ reg_t kScriptID(EngineState *s, int argc, reg_t *argv) {
 		return NULL_REG;
 	}
 
-	uint32 address = scr->validateExportFunc(index, true);
-
-	// Point to the heap for SCI1.1 - SCI2.1 games
-	if (getSciVersion() >= SCI_VERSION_1_1 && getSciVersion() <= SCI_VERSION_2_1_LATE)
-		address += scr->getScriptSize();
+	const uint32 address = scr->validateExportFunc(index, true) + scr->getHeapOffset();
 
 	// Bugfix for the intro speed in PQ2 version 1.002.011.
 	// This is taken from the patch by NewRisingSun(NRS) / Belzorash. Global 3
diff --git a/engines/sci/engine/object.cpp b/engines/sci/engine/object.cpp
index 386c3e26bf..640feb1418 100644
--- a/engines/sci/engine/object.cpp
+++ b/engines/sci/engine/object.cpp
@@ -123,12 +123,12 @@ int Object::locateVarSelector(SegManager *segMan, Selector slc) const {
 	return -1; // Failed
 }
 
-bool Object::relocateSci0Sci21(SegmentId segment, int location, size_t scriptSize) {
-	return relocateBlock(_variables, getPos().getOffset(), segment, location, scriptSize);
+bool Object::relocateSci0Sci21(SegmentId segment, int location, uint32 heapOffset) {
+	return relocateBlock(_variables, getPos().getOffset(), segment, location, heapOffset);
 }
 
 #ifdef ENABLE_SCI32
-bool Object::relocateSci3(SegmentId segment, uint32 location, int offset, size_t scriptSize) {
+bool Object::relocateSci3(SegmentId segment, uint32 location, int offset, uint32 scriptSize) {
 	assert(offset >= 0 && (uint)offset < scriptSize);
 
 	for (uint i = 0; i < _variables.size(); ++i) {
diff --git a/engines/sci/engine/object.h b/engines/sci/engine/object.h
index 71b366dc79..be20e3bef4 100644
--- a/engines/sci/engine/object.h
+++ b/engines/sci/engine/object.h
@@ -299,9 +299,9 @@ public:
 #endif
 	}
 
-	bool relocateSci0Sci21(SegmentId segment, int location, size_t scriptSize);
+	bool relocateSci0Sci21(SegmentId segment, int location, uint32 heapOffset);
 #ifdef ENABLE_SCI32
-	bool relocateSci3(SegmentId segment, uint32 location, int offset, size_t scriptSize);
+	bool relocateSci3(SegmentId segment, uint32 location, int offset, uint32 scriptSize);
 #endif
 
 	int propertyOffsetToId(SegManager *segMan, int propertyOffset) const;
diff --git a/engines/sci/engine/script.cpp b/engines/sci/engine/script.cpp
index 2f04534343..ea1b6f2f5f 100644
--- a/engines/sci/engine/script.cpp
+++ b/engines/sci/engine/script.cpp
@@ -183,7 +183,7 @@ void Script::load(int script_nr, ResourceManager *resMan, ScriptPatcher *scriptP
 			_exports = _buf->subspan<const uint16>(kSci11ExportTableOffset, _numExports * sizeof(uint16));
 		}
 
-		_localsOffset = _script.size() + 4;
+		_localsOffset = getHeapOffset() + 4;
 		_localsCount = _buf->getUint16SEAt(_localsOffset - 2);
 	} else if (getSciVersion() == SCI_VERSION_3) {
 		_localsCount = _buf->getUint16LEAt(12);
@@ -676,10 +676,9 @@ bool relocateBlock(Common::Array<reg_t> &block, int block_location, SegmentId se
 		error("Attempt to relocate odd variable #%d.5e (relative to %04x)\n", idx, block_location);
 		return false;
 	}
-	block[idx].setSegment(segment); // Perform relocation
-	if (getSciVersion() >= SCI_VERSION_1_1 && getSciVersion() <= SCI_VERSION_2_1_LATE)
-		block[idx].incOffset(scriptSize);
 
+	block[idx].setSegment(segment);
+	block[idx].incOffset(heapOffset);
 	return true;
 }
 
@@ -702,60 +701,123 @@ int Script::relocateOffsetSci3(uint32 offset) const {
 
 bool Script::relocateLocal(SegmentId segment, int location) {
 	if (_localsBlock)
-		return relocateBlock(_localsBlock->_locals, _localsOffset, segment, location, _script.size());
+		return relocateBlock(_localsBlock->_locals, _localsOffset, segment, location, getHeapOffset());
 	else
 		return false;
 }
 
-void Script::relocateSci0Sci21(reg_t block) {
-	SciSpan<const byte> heap = *_buf;
-	uint16 heapOffset = 0;
+uint32 Script::getRelocationOffset(const uint32 offset) const {
+	if (getSciVersion() == SCI_VERSION_3) {
+		SciSpan<const byte> relocStart = _buf->subspan(_buf->getUint32SEAt(8));
+		const uint relocCount = _buf->getUint16SEAt(18);
 
-	if (getSciVersion() >= SCI_VERSION_1_1 && getSciVersion() <= SCI_VERSION_2_1_LATE) {
-		heap = _heap;
-		heapOffset = _script.size();
+		for (uint i = 0; i < relocCount; ++i) {
+			if (offset == relocStart.getUint32SEAt(0)) {
+				return relocStart.getUint32SEAt(4);
+			}
+			relocStart += 10;
+		}
+	} else {
+		const SciSpan<const uint16> relocTable = getRelocationTableSci0Sci21();
+		for (uint i = 0; i < relocTable.size(); ++i) {
+			if (relocTable.getUint16SEAt(i) == offset) {
+				return getHeapOffset();
+			}
+		}
 	}
 
-	if (block.getOffset() >= (uint16)heap.size() ||
-		heap.getUint16SEAt(block.getOffset()) * 2 + block.getOffset() >= (uint16)heap.size())
-	    error("Relocation block outside of script");
-
-	int count = heap.getUint16SEAt(block.getOffset());
-	int exportIndex = 0;
-	int pos = 0;
-
-	for (int i = 0; i < count; i++) {
-		pos = heap.getUint16SEAt(block.getOffset() + 2 + (exportIndex * 2)) + heapOffset;
-		// This occurs in SCI01/SCI1 games where usually one export value is
-		// zero. It seems that in this situation, we should skip the export and
-		// move to the next one, though the total count of valid exports remains
-		// the same
-		if (!pos) {
-			exportIndex++;
-			pos = heap.getUint16SEAt(block.getOffset() + 2 + (exportIndex * 2)) + heapOffset;
-			if (!pos)
-				error("Script::relocate(): Consecutive zero exports found");
+	return kNoRelocation;
+}
+
+const SciSpan<const uint16> Script::getRelocationTableSci0Sci21() const {
+	SciSpan<const byte> relocationBlock;
+	uint16 numEntries;
+	uint16 dataOffset;
+
+	if (getSciVersion() < SCI_VERSION_1_1) {
+		relocationBlock = findBlockSCI0(SCI_OBJ_POINTERS);
+
+		if (!relocationBlock) {
+			return SciSpan<const uint16>();
+		}
+
+		if (relocationBlock != findBlockSCI0(SCI_OBJ_POINTERS, true)) {
+			warning("script.%u has multiple relocation tables", _nr);
 		}
 
+		numEntries = relocationBlock.getUint16SEAt(4);
+
+		if (!numEntries) {
+			return SciSpan<const uint16>();
+		}
+
+		dataOffset = 6;
+
+		// Starting somewhere around SQ1, and continuing through the rest of
+		// SCI1, the relocation table in scripts started including an extra
+		// null entry at the beginning of the table, without a corresponding
+		// increase in the entry count. While this change is consistent in
+		// most of the SCI1mid+ games (all scripts in LSL1, Jones CD,
+		// EQ floppy, SQ1, LSL5, and Ms Astro Chicken have the null entry),
+		// a few games include scripts without the null entry (Castle of Dr
+		// Brain 947 & 997, PQ3 997, KQ5 CD 975 & 997). Since 0 is never a
+		// valid relocation offset, we just skip it if we see it
+		const uint16 firstEntry = relocationBlock.getUint16SEAt(6);
+		if (firstEntry == 0) {
+			dataOffset += 2;
+		}
+	} else if (getSciVersion() >= SCI_VERSION_1_1 && getSciVersion() <= SCI_VERSION_2_1_LATE) {
+		relocationBlock = _heap.subspan(_heap.getUint16SEAt(0));
+
+		if (!relocationBlock) {
+			return SciSpan<const uint16>();
+		}
+
+		numEntries = relocationBlock.getUint16SEAt(0);
+
+		if (!numEntries) {
+			return SciSpan<const uint16>();
+		}
+
+		dataOffset = 2;
+	} else {
+		error("Invalid engine version called Script::getRelocationTableSci0Sci21");
+	}
+
+	// This check should work correctly even with SCI1.1+ because the relocation
+	// table is always at the very end of the heap in these games
+	if (dataOffset + numEntries * sizeof(uint16) != relocationBlock.size()) {
+		warning("script.%u unexpected relocation table size %u", _nr, relocationBlock.size());
+	}
+
+	return relocationBlock.subspan<const uint16>(dataOffset, numEntries * sizeof(uint16));
+}
+
+void Script::relocateSci0Sci21(const SegmentId segmentId) {
+	const SciSpan<const uint16> relocEntries = getRelocationTableSci0Sci21();
+
+	const uint32 heapOffset = getHeapOffset();
+
+	for (uint i = 0; i < relocEntries.size(); ++i) {
+		const uint pos = relocEntries.getUint16SEAt(i) + heapOffset;
+
 		// In SCI0-SCI1, script local variables, objects and code are relocated.
 		// We only relocate locals and objects here, and ignore relocation of
 		// code blocks. In SCI1.1 and newer versions, only locals and objects
 		// are relocated.
-		if (!relocateLocal(block.getSegment(), pos)) {
+		if (!relocateLocal(segmentId, pos)) {
 			// Not a local? It's probably an object or code block. If it's an
 			// object, relocate it.
 			const ObjMap::iterator end = _objects.end();
 			for (ObjMap::iterator it = _objects.begin(); it != end; ++it)
-				if (it->_value.relocateSci0Sci21(block.getSegment(), pos, _script.size()))
+				if (it->_value.relocateSci0Sci21(segmentId, pos, getHeapOffset()))
 					break;
 		}
-
-		exportIndex++;
 	}
 }
 
 #ifdef ENABLE_SCI32
-void Script::relocateSci3(reg_t block) {
+void Script::relocateSci3(const SegmentId segmentId) {
 	SciSpan<const byte> relocStart = _buf->subspan(_buf->getUint32SEAt(8));
 	const uint relocCount = _buf->getUint16SEAt(18);
 
@@ -763,7 +825,7 @@ void Script::relocateSci3(reg_t block) {
 	for (it = _objects.begin(); it != _objects.end(); ++it) {
 		SciSpan<const byte> seeker = relocStart;
 		for (uint i = 0; i < relocCount; ++i) {
-			it->_value.relocateSci3(block.getSegment(),
+			it->_value.relocateSci3(segmentId,
 						seeker.getUint32SEAt(0),
 						seeker.getUint32SEAt(4),
 						_script.size());
@@ -831,7 +893,7 @@ uint32 Script::validateExportFunc(int pubfunct, bool relocSci3) {
 	return offset;
 }
 
-SciSpan<const byte> Script::findBlockSCI0(ScriptObjectTypes type, bool findLastBlock) {
+SciSpan<const byte> Script::findBlockSCI0(ScriptObjectTypes type, bool findLastBlock) const {
 	SciSpan<const byte> foundBlock;
 
 	bool oldScriptHeader = (getSciVersion() == SCI_VERSION_0_EARLY);
@@ -1054,9 +1116,7 @@ void Script::initializeObjectsSci0(SegManager *segMan, SegmentId segmentId) {
 		} while ((uint32)(seeker - *_buf) < getScriptSize() - 2);
 	}
 
-	const SciSpan<const byte> relocationBlock = findBlockSCI0(SCI_OBJ_POINTERS);
-	if (relocationBlock)
-		relocateSci0Sci21(make_reg(segmentId, relocationBlock - *_buf + 4));
+	relocateSci0Sci21(segmentId);
 }
 
 void Script::initializeObjectsSci11(SegManager *segMan, SegmentId segmentId) {
@@ -1108,7 +1168,7 @@ void Script::initializeObjectsSci11(SegManager *segMan, SegmentId segmentId) {
 		seeker += seeker.getUint16SEAt(2) * 2;
 	}
 
-	relocateSci0Sci21(make_reg(segmentId, _heap.getUint16SEAt(0)));
+	relocateSci0Sci21(segmentId);
 
 	for (uint i = 0; i < mismatchedVarCountObjects.size(); ++i) {
 		const reg_t pos = mismatchedVarCountObjects[i];
@@ -1143,7 +1203,7 @@ void Script::initializeObjectsSci3(SegManager *segMan, SegmentId segmentId) {
 		seeker += seeker.getUint16SEAt(2);
 	}
 
-	relocateSci3(make_reg(segmentId, 0));
+	relocateSci3(segmentId);
 }
 #endif
 
diff --git a/engines/sci/engine/script.h b/engines/sci/engine/script.h
index 65f3ffb6ab..b59f87f13a 100644
--- a/engines/sci/engine/script.h
+++ b/engines/sci/engine/script.h
@@ -56,6 +56,10 @@ enum ScriptOffsetEntryTypes {
 	SCI_SCR_OFFSET_TYPE_SAID
 };
 
+enum {
+	kNoRelocation = 0xFFFFFFFF
+};
+
 struct offsetLookupArrayEntry {
 	uint16    type;       // type of entry
 	uint16    id;         // id of this type, first item inside script data is 1, second item is 2, etc.
@@ -105,6 +109,13 @@ public:
 	uint32 getScriptSize() const { return _script.size(); }
 	uint32 getHeapSize() const { return _heap.size(); }
 	uint32 getBufSize() const { return _buf->size(); }
+	inline uint32 getHeapOffset() const {
+		if (getSciVersion() >= SCI_VERSION_1_1 && getSciVersion() <= SCI_VERSION_2_1_LATE) {
+			return _script.size();
+		}
+
+		return 0;
+	}
 
 	const byte *getBuf(uint offset = 0) const { return _buf->getUnsafeDataAt(offset); }
 	SciSpan<const byte> getSpan(uint offset) const { return _buf->subspan(offset); }
@@ -247,7 +258,7 @@ public:
 	 * Finds the pointer where a block of a specific type starts from,
 	 * in SCI0 - SCI1 games
 	 */
-	SciSpan<const byte> findBlockSCI0(ScriptObjectTypes type, bool findLastBlock = false);
+	SciSpan<const byte> findBlockSCI0(ScriptObjectTypes type, bool findLastBlock = false) const;
 
 	/**
 	 * Syncs the string heap of a script. Used when saving/loading.
@@ -276,23 +287,35 @@ public:
 	uint16 getOffsetStringCount() { return _offsetLookupStringCount; };
 	uint16 getOffsetSaidCount() { return _offsetLookupSaidCount; };
 
+	/**
+	 * @returns kNoRelocation if no relocation exists for the given offset,
+	 * otherwise returns a delta for the offset to its relocated position.
+	 */
+	uint32 getRelocationOffset(const uint32 offset) const;
+
 private:
 	/**
+	 * Returns a Span containing the relocation table for a SCI0-SCI2.1 script.
+	 * (The SCI0-SCI2.1 relocation table is simply a list of all of the
+	 * offsets in the script heap whose values should be treated as pointers to
+	 * objects (vs just being numbers).)
+	 */
+	const SciSpan<const uint16> getRelocationTableSci0Sci21() const;
+
+	/**
 	 * Processes a relocation block within a SCI0-SCI2.1 script
 	 *  This function is idempotent, but it must only be called after all
 	 *  objects have been instantiated, or a run-time error will occur.
-	 * @param obj_pos	Location (segment, offset) of the block
 	 */
-	void relocateSci0Sci21(reg_t block);
+	void relocateSci0Sci21(const SegmentId segmentId);
 
 #ifdef ENABLE_SCI32
 	/**
 	 * Processes a relocation block within a SCI3 script
 	 *  This function is idempotent, but it must only be called after all
 	 *  objects have been instantiated, or a run-time error will occur.
-	 * @param obj_pos	Location (segment, offset) of the block
 	 */
-	void relocateSci3(reg_t block);
+	void relocateSci3(const SegmentId segmentId);
 #endif
 
 	bool relocateLocal(SegmentId segment, int location);
diff --git a/engines/sci/engine/vm.cpp b/engines/sci/engine/vm.cpp
index 1d86948fdd..f4071a4843 100644
--- a/engines/sci/engine/vm.cpp
+++ b/engines/sci/engine/vm.cpp
@@ -570,7 +570,7 @@ uint32 findOffset(const int16 relOffset, const Script *scr, const uint32 pcOffse
 		offset = relOffset;
 		break;
 	case SCI_VERSION_1_1:
-		offset = relOffset + scr->getScriptSize();
+		offset = relOffset + scr->getHeapOffset();
 		break;
 #ifdef ENABLE_SCI32
 	case SCI_VERSION_3: