[Scummvm-git-logs] scummvm master -> 99f45887d9327b566e09e405645904a9a98e807b

[AndywinXp]

This automated email contains information about 1 new commit which have been
pushed to the 'scummvm' repo located at https://api.github.com/repos/scummvm/scummvm .

Summary:
99f45887d9 SCUMM/HE: FREDDI5: Fix #13797


Commit: 99f45887d9327b566e09e405645904a9a98e807b
    https://github.com/scummvm/scummvm/commit/99f45887d9327b566e09e405645904a9a98e807b
Author: AndywinXp (andywinxp at gmail.com)
Date: 2025-09-28T11:34:53+02:00

Commit Message:
SCUMM/HE: FREDDI5: Fix #13797

Yet another case of "surely we don't need this part from the source code". :)

This fixes #13797:
"SCUMM/HE: FREDDI5: Outline of Freddi appears in the leftmost tide pool"

Turns out their own qsort algo behaves quite differently when several sprites
have the same priority assigned to them.

Changed paths:
    engines/scumm/he/sprite_he.cpp
    engines/scumm/he/sprite_he.h


diff --git a/engines/scumm/he/sprite_he.cpp b/engines/scumm/he/sprite_he.cpp
index 656ed2cccc7..4949ef3daaf 100644
--- a/engines/scumm/he/sprite_he.cpp
+++ b/engines/scumm/he/sprite_he.cpp
@@ -1633,6 +1633,118 @@ static int compareSpritePriority(const void *a, const void *b) {
 	return spr1->priority - spr2->priority;
 }
 
+#define SWAP_SPRITE_PTRS(e1, e2, te) { \
+	te = *e1;                          \
+	*e1 = *e2;                         \
+	*e2 = te;                          \
+}
+
+#define SPRITE_QSORT_CUTOFF 8
+
+void Sprite::qsortSpriteArray(SpriteInfo **base, uint num) {
+	SpriteInfo **lostk[30], **histk[30];
+	SpriteInfo **loguy, **higuy;
+	SpriteInfo **lo, **hi;
+	SpriteInfo **mid;
+	SpriteInfo *t;
+
+	uint size;
+	int stkptr;
+
+	if (num < 2)
+		return;
+
+	stkptr = 0;
+
+	lo = base;
+	hi = base + (num - 1);
+
+recurse:
+	size = (hi - lo) + 1;
+
+	if (size <= SPRITE_QSORT_CUTOFF) {
+		shortsortSpriteArray(lo, hi);
+	} else {
+		mid = lo + (size / 2);
+		SWAP_SPRITE_PTRS(mid, lo, t);
+
+		loguy = lo;
+		higuy = hi + 1;
+
+		for (;;) {
+			do {
+				++loguy;
+			} while (loguy <= hi && compareSpriteCombinedPriority((const SpriteInfo **)loguy, (const SpriteInfo **)lo) <= 0);
+
+			do {
+				--higuy;
+			} while (higuy > lo && compareSpriteCombinedPriority((const SpriteInfo **)higuy, (const SpriteInfo **)lo) >= 0);
+
+			if (higuy < loguy)
+				break;
+
+			SWAP_SPRITE_PTRS(loguy, higuy, t);
+		}
+
+		SWAP_SPRITE_PTRS(lo, higuy, t);
+
+		if (higuy - 1 - lo >= hi - loguy) {
+			if (lo + 1 < higuy) {
+				lostk[stkptr] = lo;
+				histk[stkptr] = higuy - 1;
+				++stkptr;
+			}
+
+			if (loguy < hi) {
+				lo = loguy;
+				goto recurse;
+			}
+		} else {
+			if (loguy < hi) {
+				lostk[stkptr] = loguy;
+				histk[stkptr] = hi;
+				++stkptr;
+			}
+
+			if (lo + 1 < higuy) {
+				hi = higuy - 1;
+				goto recurse;
+			}
+		}
+	}
+
+	--stkptr;
+
+	if (stkptr >= 0) {
+		lo = lostk[stkptr];
+		hi = histk[stkptr];
+		goto recurse;
+	} else {
+		return;
+	}
+}
+
+void Sprite::shortsortSpriteArray(SpriteInfo **lo, SpriteInfo **hi) {
+	SpriteInfo **p, **max, *t;
+
+	while (hi > lo) {
+		max = lo;
+
+		for (p = lo + 1; p <= hi; p++) {
+			if (compareSpriteCombinedPriority((const SpriteInfo **)p, (const SpriteInfo **)max) > 0) {
+				max = p;
+			}
+		}
+
+		SWAP_SPRITE_PTRS(max, hi, t);
+		hi--;
+	}
+}
+
+#undef SPRITE_QSORT_CUTOFF
+
+#undef SWAP_SPRITE_PTRS
+
 void Sprite::buildActiveSpriteList() {
 	SpriteInfo **spritePtr;
 
@@ -1666,7 +1778,7 @@ void Sprite::buildActiveSpriteList() {
 	// Sort the list of active sprites...
 	if (_activeSpriteCount) {
 		if (_vm->_game.heversion > 95) {
-			qsort(_activeSprites, _activeSpriteCount, sizeof(SpriteInfo *), compareSpriteCombinedPriority);
+			qsortSpriteArray(_activeSprites, _activeSpriteCount);
 		} else {
 			qsort(_activeSprites, _activeSpriteCount, sizeof(SpriteInfo *), compareSpritePriority);
 		}
diff --git a/engines/scumm/he/sprite_he.h b/engines/scumm/he/sprite_he.h
index d09d39b934a..c6ede16d40c 100644
--- a/engines/scumm/he/sprite_he.h
+++ b/engines/scumm/he/sprite_he.h
@@ -236,6 +236,8 @@ public:
 	void eraseSprites();
 	bool doesRectIntersectUpdateAreas(const Common::Rect *rectPtr);
 	void checkForForcedRedraws(bool checkOnlyPositivePriority);
+	void qsortSpriteArray(SpriteInfo **base, uint num);
+	void shortsortSpriteArray(SpriteInfo **lo, SpriteInfo **hi);
 	void buildActiveSpriteList();
 	void renderSprites(bool negativeOrPositiveRender);
 	void runSpriteEngines();