src/video/SpriteChecker.cc at main · doomsdayone/openmsx

◆ main openmsx / src / video / SpriteChecker.cc

17.3 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw

/*
TODO:
- Verify model for 5th sprite number calculation.
  For example, does it have the right value in text mode?
- Further investigate sprite collision registers:
   - If there is NO collision, the value of these registers constantly changes.
     Could this be some kind of indication for the scanline XY coords???
   - Bit 9 of the Y coord (odd/even page??) is not yet implemented.
*/

#include "SpriteChecker.hh"

#include "RenderSettings.hh"

#include "BooleanSetting.hh"
#include "serialize.hh"

#include <algorithm>
#include <bit>
#include <cassert>

namespace openmsx {

SpriteChecker::SpriteChecker(VDP& vdp_, RenderSettings& renderSettings,
                             EmuTime time)
	: vdp(vdp_), vram(vdp.getVRAM())
	, limitSpritesSetting(renderSettings.getLimitSpritesSetting())
	, frameStartTime(time)
{
	vram.spriteAttribTable.setObserver(this);
	vram.spritePatternTable.setObserver(this);
}

void SpriteChecker::reset(EmuTime time)
{
	vdp.setSpriteStatus(0); // TODO 0x00 or 0x1F  (blueMSX has 0x1F)
	collisionX = 0;
	collisionY = 0;

	frameStart(time);

	updateSpritesMethod = &SpriteChecker::updateSprites1;
}

inline SpriteChecker::SpritePattern SpriteChecker::calculatePatternNP(
	unsigned patternNr, unsigned y) const
{
	auto patternPtr = vram.spritePatternTable.getReadArea<256 * 8>(0);
	unsigned index = patternNr * 8 + y;
	SpritePattern pattern = patternPtr[index] << 24;
	if (vdp.getSpriteSize() == 16) {
		pattern |= patternPtr[index + 16] << 16;
	}
	return !vdp.isSpriteMag() ? pattern : doublePattern(pattern);
}
inline SpriteChecker::SpritePattern SpriteChecker::calculatePatternPlanar(
	unsigned patternNr, unsigned y) const
{
	auto [ptr0, ptr1] = vram.spritePatternTable.getReadAreaPlanar<256 * 8>(0);
	unsigned index = patternNr * 8 + y;
	auto patternPtr = (index & 1) ? ptr1 : ptr0;
	index /= 2;
	SpritePattern pattern = patternPtr[index] << 24;
	if (vdp.getSpriteSize() == 16) {
		pattern |= patternPtr[index + (16 / 2)] << 16;
	}
	return !vdp.isSpriteMag() ? pattern : doublePattern(pattern);
}

void SpriteChecker::updateSprites1(int limit)
{
	if (vdp.spritesEnabledFast()) {
		if (vdp.isDisplayEnabled()) {
			// in display area
			checkSprites1(currentLine, limit);
		} else {
			// in border, only check last line of top border
			int l0 = vdp.getLineZero() - 1;
			if ((currentLine <= l0) && (l0 < limit)) {
				checkSprites1(l0, l0 + 1);
			}
		}
	}
	currentLine = limit;
}

inline void SpriteChecker::checkSprites1(int minLine, int maxLine)
{
	// This implementation contains a double for-loop. The outer loop goes
	// over the sprites, the inner loop over the to-be-checked lines. This
	// is not the order in which the real VDP performs this operation: the
	// real VDP renders line-per-line and for each line checks all 32
	// sprites.
	//
	// Though this 'reverse' order allows to skip over very large regions
	// of the inner loop: we only have to process the lines were a
	// particular sprite is actually visible. I measured this makes this
	// routine 4x-5x faster!
	//
	// This routine also needs to detect the sprite number of the 'first'
	// 5th-sprite-condition. With 'first' meaning the first line where this
	// condition occurs. Because our loops are swapped compared to the real
	// VDP, we need some extra fixup logic to correctly detect this.

	// Calculate display line.
	// This is the line sprites are checked at; the line they are displayed
	// at is one lower.
	int displayDelta = vdp.getVerticalScroll() - vdp.getLineZero();

	// Get sprites for this line and detect 5th sprite if any.
	bool limitSprites = limitSpritesSetting.getBoolean();
	int size = vdp.getSpriteSize();
	bool mag = vdp.isSpriteMag();
	int magSize = (mag + 1) * size;
	auto attributePtr = vram.spriteAttribTable.getReadArea<32 * 4>(0);
	uint8_t patternIndexMask = size == 16 ? 0xFC : 0xFF;
	int fifthSpriteNum  = -1;  // no 5th sprite detected yet
	int fifthSpriteLine = 999; // larger than any possible valid line

	int sprite = 0;
	for (/**/; sprite < 32; ++sprite) {
		int y = attributePtr[4 * sprite + 0];
		if (y == 208) break;

		for (int line = minLine; line < maxLine; ++line) { // 'line' changes in loop
			// Calculate line number within the sprite.
			int displayLine = line + displayDelta;
			int spriteLine = (displayLine - y) & 0xFF;
			if (spriteLine >= magSize) {
				// Skip ahead till sprite becomes visible.
				line += 256 - spriteLine - 1; // -1 because of for-loop
				continue;
			}

			auto visibleIndex = spriteCount[line];
			if (visibleIndex == 4) {
				// Find earliest line where this condition occurs.
				if (line < fifthSpriteLine) {
					fifthSpriteLine = line;
					fifthSpriteNum = sprite;
				}
				if (limitSprites) continue;
			}

			SpriteInfo& sip = spriteBuffer[line][visibleIndex];
			int patternIndex = attributePtr[4 * sprite + 2] & patternIndexMask;
			if (mag) spriteLine /= 2;
			sip.pattern = calculatePatternNP(patternIndex, spriteLine);
			sip.x = attributePtr[4 * sprite + 1];
			uint8_t colorAttrib = attributePtr[4 * sprite + 3];
			if (colorAttrib & 0x80) sip.x -= 32;
			sip.colorAttrib = colorAttrib;

			spriteCount[line] = visibleIndex + 1;
		}
	}

	// Update status register.
	uint8_t status = vdp.getStatusReg0();
	if (fifthSpriteNum != -1) {
		// Five sprites on a line.
		// According to TMS9918.pdf 5th sprite detection is only
		// active when F flag is zero.
		if ((status & 0xC0) == 0) {
			status = uint8_t(0x40 | (status & 0x20) | fifthSpriteNum);
		}
	}
	if (~status & 0x40) {
		// No 5th sprite detected, store number of latest sprite processed.
		status = (status & 0x20) | uint8_t(std::min(sprite, 31));
	}
	vdp.setSpriteStatus(status);

	// Optimisation:
	// If collision already occurred,
	// that state is stable until it is reset by a status reg read,
	// so no need to execute the checks.
	// The spriteBuffer array is filled now, so we can bail out.
	if (vdp.getStatusReg0() & 0x20) return;

	/*
	Model for sprite collision: (or "coincidence" in TMS9918 data sheet)
	- Reset when status reg is read.
	- Set when sprite patterns overlap.
	- ??? Color doesn't matter: sprites of color 0 can collide.
	  ??? This conflicts with: https://github.com/openMSX/openMSX/issues/1198
	- Sprites that are partially off-screen position can collide, but only
	  on the in-screen pixels. In other words: sprites cannot collide in
	  the left or right border, only in the visible screen area. Though
	  they can collide in the V9958 extra border mask. This behaviour is
	  the same in sprite mode 1 and 2.

	Implemented by checking every pair for collisions.
	For large numbers of sprites that would be slow,
	but there are max 4 sprites and therefore max 6 pairs.
	If any collision is found, method returns at once.
	*/
	bool can0collide = vdp.canSpriteColor0Collide();
	for (auto line : xrange(minLine, maxLine)) {
		int minXCollision = 999;
		for (int i = std::min<int>(4, spriteCount[line]); --i >= 1; /**/) {
			auto color1 = spriteBuffer[line][i].colorAttrib & 0xf;
			if (!can0collide && (color1 == 0)) continue;
			int x_i = spriteBuffer[line][i].x;
			SpritePattern pattern_i = spriteBuffer[line][i].pattern;
			for (int j = i; --j >= 0; /**/) {
				auto color2 = spriteBuffer[line][j].colorAttrib & 0xf;
				if (!can0collide && (color2 == 0)) continue;
				// Do sprite i and sprite j collide?
				int x_j = spriteBuffer[line][j].x;
				int dist = x_j - x_i;
				if ((-magSize < dist) && (dist < magSize)) {
					SpritePattern pattern_j = spriteBuffer[line][j].pattern;
					if (dist < 0) {
						pattern_j <<= -dist;
					} else {
						pattern_j >>= dist;
					}
					SpritePattern colPat = pattern_i & pattern_j;
					if (x_i < 0) {
						assert(x_i >= -32);
						colPat &= (1 << (32 + x_i)) - 1;
					}
					if (colPat) {
						int xCollision = x_i + std::countl_zero(colPat);
						assert(xCollision >= 0);
						minXCollision = std::min(minXCollision, xCollision);
					}
				}
			}
		}
		if (minXCollision < 256) {
			vdp.setSpriteStatus(vdp.getStatusReg0() | 0x20);
			// verified: collision coords are also filled
			//           in for sprite mode 1
			// x-coord should be increased by 12
			// y-coord                         8
			collisionX = minXCollision + 12;
			collisionY = line - vdp.getLineZero() + 8;
			return; // don't check lines with higher Y-coord
		}
	}
}

void SpriteChecker::updateSprites2(int limit)
{
	// TODO merge this with updateSprites1()?
	if (vdp.spritesEnabledFast()) {
		if (vdp.isDisplayEnabled()) {
			// in display area
			checkSprites2(currentLine, limit);
		} else {
			// in border, only check last line of top border
			int l0 = vdp.getLineZero() - 1;
			if ((currentLine <= l0) && (l0 < limit)) {
				checkSprites2(l0, l0 + 1);
			}
		}
	}
	currentLine = limit;
}

inline void SpriteChecker::checkSprites2(int minLine, int maxLine)
{
	// See comment in checkSprites1() about order of inner and outer loops.

	// Calculate display line.
	// This is the line sprites are checked at; the line they are displayed
	// at is one lower.
	int displayDelta = vdp.getVerticalScroll() - vdp.getLineZero();

	// Get sprites for this line and detect 5th sprite if any.
	bool limitSprites = limitSpritesSetting.getBoolean();
	int size = vdp.getSpriteSize();
	bool mag = vdp.isSpriteMag();
	int magSize = (mag + 1) * size;
	int patternIndexMask = (size == 16) ? 0xFC : 0xFF;
	int ninthSpriteNum  = -1;  // no 9th sprite detected yet
	int ninthSpriteLine = 999; // larger than any possible valid line

	// Because it gave a measurable performance boost, we duplicated the
	// code for planar and non-planar modes.
	int sprite = 0;
	if (planar) {
		auto [attributePtr0, attributePtr1] =
			vram.spriteAttribTable.getReadAreaPlanar<32 * 4>(512);
		// TODO: Verify CC implementation.
		for (/**/; sprite < 32; ++sprite) {
			int y = attributePtr0[2 * sprite + 0];
			if (y == 216) break;

			for (int line = minLine; line < maxLine; ++line) { // 'line' changes in loop
				// Calculate line number within the sprite.
				int displayLine = line + displayDelta;
				int spriteLine = (displayLine - y) & 0xFF;
				if (spriteLine >= magSize) {
					// Skip ahead till sprite is visible.
					line += 256 - spriteLine - 1;
					continue;
				}

				auto visibleIndex = spriteCount[line];
				if (visibleIndex == 8) {
					// Find earliest line where this condition occurs.
					if (line < ninthSpriteLine) {
						ninthSpriteLine = line;
						ninthSpriteNum = sprite;
					}
					if (limitSprites) continue;
				}

				if (mag) spriteLine /= 2;
				unsigned colorIndex = (~0u << 10) | (sprite * 16 + spriteLine);
				uint8_t colorAttrib =
					vram.spriteAttribTable.readPlanar(colorIndex);

				SpriteInfo& sip = spriteBuffer[line][visibleIndex];
				int patternIndex = attributePtr0[2 * sprite + 1] & patternIndexMask;
				sip.pattern = calculatePatternPlanar(patternIndex, spriteLine);
				sip.x = attributePtr1[2 * sprite + 0];
				if (colorAttrib & 0x80) sip.x -= 32;
				sip.colorAttrib = colorAttrib;

				// set sentinel (see below)
				spriteBuffer[line][visibleIndex + 1].colorAttrib = 0;
				spriteCount[line] = visibleIndex + 1;
			}
		}
	} else {
		auto attributePtr0 =
			vram.spriteAttribTable.getReadArea<32 * 4>(512);
		// TODO: Verify CC implementation.
		for (/**/; sprite < 32; ++sprite) {
			int y = attributePtr0[4 * sprite + 0];
			if (y == 216) break;

			for (int line = minLine; line < maxLine; ++line) { // 'line' changes in loop
				// Calculate line number within the sprite.
				int displayLine = line + displayDelta;
				int spriteLine = (displayLine - y) & 0xFF;
				if (spriteLine >= magSize) {
					// Skip ahead till sprite is visible.
					line += 256 - spriteLine - 1;
					continue;
				}

				auto visibleIndex = spriteCount[line];
				if (visibleIndex == 8) {
					// Find earliest line where this condition occurs.
					if (line < ninthSpriteLine) {
						ninthSpriteLine = line;
						ninthSpriteNum = sprite;
					}
					if (limitSprites) continue;
				}

				if (mag) spriteLine /= 2;
				unsigned colorIndex = (~0u << 10) | (sprite * 16 + spriteLine);
				uint8_t colorAttrib =
					vram.spriteAttribTable.readNP(colorIndex);
				// Sprites with CC=1 are only visible if preceded by
				// a sprite with CC=0. However they DO contribute towards
				// the max-8-sprites-per-line limit, so we can't easily
				// filter them here. See also
				//    https://github.com/openMSX/openMSX/issues/497

				SpriteInfo& sip = spriteBuffer[line][visibleIndex];
				int patternIndex = attributePtr0[4 * sprite + 2] & patternIndexMask;
				sip.pattern = calculatePatternNP(patternIndex, spriteLine);
				sip.x = attributePtr0[4 * sprite + 1];
				if (colorAttrib & 0x80) sip.x -= 32;
				sip.colorAttrib = colorAttrib;

				// Set sentinel. Sentinel is actually only
				// needed for sprites with CC=1.
				// In the past we set the sentinel (for all
				// lines) at the end. But it's slightly faster
				// to do it only for lines that actually
				// contain sprites (even if sentinel gets
				// overwritten a couple of times for lines with
				// many sprites).
				spriteBuffer[line][visibleIndex + 1].colorAttrib = 0;
				spriteCount[line] = visibleIndex + 1;
			}
		}
	}

	// Update status register.
	uint8_t status = vdp.getStatusReg0();
	if (ninthSpriteNum != -1) {
		// Nine sprites on a line.
		// According to TMS9918.pdf 5th sprite detection is only
		// active when F flag is zero. Stuck to this for V9938.
		// Dragon Quest 2 needs this.
		if ((status & 0xC0) == 0) {
			status = uint8_t(0x40 | (status & 0x20) | ninthSpriteNum);
		}
	}
	if (~status & 0x40) {
		// No 9th sprite detected, store number of latest sprite processed.
		status = (status & 0x20) | uint8_t(std::min(sprite, 31));
	}
	vdp.setSpriteStatus(status);

	// Optimisation:
	// If collision already occurred,
	// that state is stable until it is reset by a status reg read,
	// so no need to execute the checks.
	// The visibleSprites array is filled now, so we can bail out.
	if (vdp.getStatusReg0() & 0x20) return;

	/*
	Model for sprite collision: (or "coincidence" in TMS9918 data sheet)
	- Reset when status reg is read.
	- Set when sprite patterns overlap.
	- ??? Color doesn't matter: sprites of color 0 can collide.
	  ???  TODO: V9938 data book denies this (page 98).
	  ??? This conflicts with: https://github.com/openMSX/openMSX/issues/1198
	- Sprites that are partially off-screen position can collide, but only
	  on the in-screen pixels. In other words: sprites cannot collide in
	  the left or right border, only in the visible screen area. Though
	  they can collide in the V9958 extra border mask. This behaviour is
	  the same in sprite mode 1 and 2.

	Implemented by checking every pair for collisions.
	For large numbers of sprites that would be slow.
	There are max 8 sprites and therefore max 42 pairs.
	  TODO: Maybe this is slow... Think of something faster.
	        Probably new approach is needed anyway for OR-ing.
	*/
	bool can0collide = vdp.canSpriteColor0Collide();
	for (auto line : xrange(minLine, maxLine)) {
		int minXCollision = 999; // no collision
		std::span<SpriteInfo, 32 + 1> visibleSprites = spriteBuffer[line];
		for (int i = std::min<int>(8, spriteCount[line]); --i >= 1; /**/) {
			auto colorAttrib1 = visibleSprites[i].colorAttrib;
			if (!can0collide && ((colorAttrib1 & 0xf) == 0)) continue;
			// If CC or IC is set, this sprite cannot collide.
			if (colorAttrib1 & 0x60) continue;

			int x_i = visibleSprites[i].x;
			SpritePattern pattern_i = visibleSprites[i].pattern;
			for (int j = i; --j >= 0; /**/) {
				auto colorAttrib2 = visibleSprites[j].colorAttrib;
				if (!can0collide && ((colorAttrib2 & 0xf) == 0)) continue;
				// If CC or IC is set, this sprite cannot collide.
				if (colorAttrib2 & 0x60) continue;

				// Do sprite i and sprite j collide?
				int x_j = visibleSprites[j].x;
				int dist = x_j - x_i;
				if ((-magSize < dist) && (dist < magSize)) {
					SpritePattern pattern_j = visibleSprites[j].pattern;
					if (dist < 0) {
						pattern_j <<= -dist;
					} else {
						pattern_j >>= dist;
					}
					SpritePattern colPat = pattern_i & pattern_j;
					if (x_i < 0) {
						assert(x_i >= -32);
						colPat &= (1 << (32 + x_i)) - 1;
					}
					if (colPat) {
						int xCollision = x_i + std::countl_zero(colPat);
						assert(xCollision >= 0);
						minXCollision = std::min(minXCollision, xCollision);
					}
				}
			}
		}
		if (minXCollision < 256) {
			vdp.setSpriteStatus(vdp.getStatusReg0() | 0x20);
			// x-coord should be increased by 12
			// y-coord                         8
			collisionX = minXCollision + 12;
			collisionY = line - vdp.getLineZero() + 8;
			return; // don't check lines with higher Y-coord
		}
	}
}

// version 1: initial version
// version 2: bug fix: also serialize 'currentLine'
template<typename Archive>
void SpriteChecker::serialize(Archive& ar, unsigned version)
{
	if constexpr (Archive::IS_LOADER) {
		// Recalculate from VDP state:
		//  - frameStartTime
		frameStartTime.reset(vdp.getFrameStartTime());
		//  - updateSpritesMethod, planar
		setDisplayMode(vdp.getDisplayMode());

		// We don't serialize spriteCount[] and spriteBuffer[].
		// These are only used to draw the MSX screen, they don't have
		// any influence on the MSX state. So the effect of not
		// serializing these two is that no sprites will be shown in the
		// first (partial) frame after loadstate.
		std::ranges::fill(spriteCount, 0);
		// content of spriteBuffer[] doesn't matter if spriteCount[] is 0
	}
	ar.serialize("collisionX", collisionX,
	             "collisionY", collisionY);
	if (ar.versionAtLeast(version, 2)) {
		ar.serialize("currentLine", currentLine);
	} else {
		currentLine = 0;
	}
}
INSTANTIATE_SERIALIZE_METHODS(SpriteChecker);

} // namespace openmsx

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1	/*
2	TODO:
3	- Verify model for 5th sprite number calculation.
4	For example, does it have the right value in text mode?
5	- Further investigate sprite collision registers:
6	- If there is NO collision, the value of these registers constantly changes.
7	Could this be some kind of indication for the scanline XY coords???
8	- Bit 9 of the Y coord (odd/even page??) is not yet implemented.
9	*/
10
11	#include "SpriteChecker.hh"
12
13	#include "RenderSettings.hh"
14
15	#include "BooleanSetting.hh"
16	#include "serialize.hh"
17
18	#include <algorithm>
19	#include <bit>
20	#include <cassert>
21
22	namespace openmsx {
23
24	SpriteChecker::SpriteChecker(VDP& vdp_, RenderSettings& renderSettings,
25	EmuTime time)
26	: vdp(vdp_), vram(vdp.getVRAM())
27	, limitSpritesSetting(renderSettings.getLimitSpritesSetting())
28	, frameStartTime(time)
29	{
30	vram.spriteAttribTable.setObserver(this);
31	vram.spritePatternTable.setObserver(this);
32	}
33
34	void SpriteChecker::reset(EmuTime time)
35	{
36	vdp.setSpriteStatus(0); // TODO 0x00 or 0x1F (blueMSX has 0x1F)
37	collisionX = 0;
38	collisionY = 0;
39
40	frameStart(time);
41
42	updateSpritesMethod = &SpriteChecker::updateSprites1;
43	}
44
45	inline SpriteChecker::SpritePattern SpriteChecker::calculatePatternNP(
46	unsigned patternNr, unsigned y) const
47	{
48	auto patternPtr = vram.spritePatternTable.getReadArea<256 * 8>(0);
49	unsigned index = patternNr * 8 + y;
50	SpritePattern pattern = patternPtr[index] << 24;
51	if (vdp.getSpriteSize() == 16) {
52	pattern \|= patternPtr[index + 16] << 16;
53	}
54	return !vdp.isSpriteMag() ? pattern : doublePattern(pattern);
55	}
56	inline SpriteChecker::SpritePattern SpriteChecker::calculatePatternPlanar(
57	unsigned patternNr, unsigned y) const
58	{
59	auto [ptr0, ptr1] = vram.spritePatternTable.getReadAreaPlanar<256 * 8>(0);
60	unsigned index = patternNr * 8 + y;
61	auto patternPtr = (index & 1) ? ptr1 : ptr0;
62	index /= 2;
63	SpritePattern pattern = patternPtr[index] << 24;
64	if (vdp.getSpriteSize() == 16) {
65	pattern \|= patternPtr[index + (16 / 2)] << 16;
66	}
67	return !vdp.isSpriteMag() ? pattern : doublePattern(pattern);
68	}
69
70	void SpriteChecker::updateSprites1(int limit)
71	{
72	if (vdp.spritesEnabledFast()) {
73	if (vdp.isDisplayEnabled()) {
74	// in display area
75	checkSprites1(currentLine, limit);
76	} else {
77	// in border, only check last line of top border
78	int l0 = vdp.getLineZero() - 1;
79	if ((currentLine <= l0) && (l0 < limit)) {
80	checkSprites1(l0, l0 + 1);
81	}
82	}
83	}
84	currentLine = limit;
85	}
86
87	inline void SpriteChecker::checkSprites1(int minLine, int maxLine)
88	{
89	// This implementation contains a double for-loop. The outer loop goes
90	// over the sprites, the inner loop over the to-be-checked lines. This
91	// is not the order in which the real VDP performs this operation: the
92	// real VDP renders line-per-line and for each line checks all 32
93	// sprites.
94	//
95	// Though this 'reverse' order allows to skip over very large regions
96	// of the inner loop: we only have to process the lines were a
97	// particular sprite is actually visible. I measured this makes this
98	// routine 4x-5x faster!
99	//
100	// This routine also needs to detect the sprite number of the 'first'
101	// 5th-sprite-condition. With 'first' meaning the first line where this
102	// condition occurs. Because our loops are swapped compared to the real
103	// VDP, we need some extra fixup logic to correctly detect this.
104
105	// Calculate display line.
106	// This is the line sprites are checked at; the line they are displayed
107	// at is one lower.
108	int displayDelta = vdp.getVerticalScroll() - vdp.getLineZero();
109
110	// Get sprites for this line and detect 5th sprite if any.
111	bool limitSprites = limitSpritesSetting.getBoolean();
112	int size = vdp.getSpriteSize();
113	bool mag = vdp.isSpriteMag();
114	int magSize = (mag + 1) * size;
115	auto attributePtr = vram.spriteAttribTable.getReadArea<32 * 4>(0);
116	uint8_t patternIndexMask = size == 16 ? 0xFC : 0xFF;
117	int fifthSpriteNum = -1; // no 5th sprite detected yet
118	int fifthSpriteLine = 999; // larger than any possible valid line
119
120	int sprite = 0;
121	for (/**/; sprite < 32; ++sprite) {
122	int y = attributePtr[4 * sprite + 0];
123	if (y == 208) break;
124
125	for (int line = minLine; line < maxLine; ++line) { // 'line' changes in loop
126	// Calculate line number within the sprite.
127	int displayLine = line + displayDelta;
128	int spriteLine = (displayLine - y) & 0xFF;
129	if (spriteLine >= magSize) {
130	// Skip ahead till sprite becomes visible.
131	line += 256 - spriteLine - 1; // -1 because of for-loop
132	continue;
133	}
134
135	auto visibleIndex = spriteCount[line];
136	if (visibleIndex == 4) {
137	// Find earliest line where this condition occurs.
138	if (line < fifthSpriteLine) {
139	fifthSpriteLine = line;
140	fifthSpriteNum = sprite;
141	}
142	if (limitSprites) continue;
143	}
144
145	SpriteInfo& sip = spriteBuffer[line][visibleIndex];
146	int patternIndex = attributePtr[4 * sprite + 2] & patternIndexMask;
147	if (mag) spriteLine /= 2;
148	sip.pattern = calculatePatternNP(patternIndex, spriteLine);
149	sip.x = attributePtr[4 * sprite + 1];
150	uint8_t colorAttrib = attributePtr[4 * sprite + 3];
151	if (colorAttrib & 0x80) sip.x -= 32;
152	sip.colorAttrib = colorAttrib;
153
154	spriteCount[line] = visibleIndex + 1;
155	}
156	}
157
158	// Update status register.
159	uint8_t status = vdp.getStatusReg0();
160	if (fifthSpriteNum != -1) {
161	// Five sprites on a line.
162	// According to TMS9918.pdf 5th sprite detection is only
163	// active when F flag is zero.
164	if ((status & 0xC0) == 0) {
165	status = uint8_t(0x40 \| (status & 0x20) \| fifthSpriteNum);
166	}
167	}
168	if (~status & 0x40) {
169	// No 5th sprite detected, store number of latest sprite processed.
170	status = (status & 0x20) \| uint8_t(std::min(sprite, 31));
171	}
172	vdp.setSpriteStatus(status);
173
174	// Optimisation:
175	// If collision already occurred,
176	// that state is stable until it is reset by a status reg read,
177	// so no need to execute the checks.
178	// The spriteBuffer array is filled now, so we can bail out.
179	if (vdp.getStatusReg0() & 0x20) return;
180
181	/*
182	Model for sprite collision: (or "coincidence" in TMS9918 data sheet)
183	- Reset when status reg is read.
184	- Set when sprite patterns overlap.
185	- ??? Color doesn't matter: sprites of color 0 can collide.
186	??? This conflicts with: https://github.com/openMSX/openMSX/issues/1198
187	- Sprites that are partially off-screen position can collide, but only
188	on the in-screen pixels. In other words: sprites cannot collide in
189	the left or right border, only in the visible screen area. Though
190	they can collide in the V9958 extra border mask. This behaviour is
191	the same in sprite mode 1 and 2.
192
193	Implemented by checking every pair for collisions.
194	For large numbers of sprites that would be slow,
195	but there are max 4 sprites and therefore max 6 pairs.
196	If any collision is found, method returns at once.
197	*/
198	bool can0collide = vdp.canSpriteColor0Collide();
199	for (auto line : xrange(minLine, maxLine)) {
200	int minXCollision = 999;
201	for (int i = std::min<int>(4, spriteCount[line]); --i >= 1; /**/) {
202	auto color1 = spriteBuffer[line][i].colorAttrib & 0xf;
203	if (!can0collide && (color1 == 0)) continue;
204	int x_i = spriteBuffer[line][i].x;
205	SpritePattern pattern_i = spriteBuffer[line][i].pattern;
206	for (int j = i; --j >= 0; /**/) {
207	auto color2 = spriteBuffer[line][j].colorAttrib & 0xf;
208	if (!can0collide && (color2 == 0)) continue;
209	// Do sprite i and sprite j collide?
210	int x_j = spriteBuffer[line][j].x;
211	int dist = x_j - x_i;
212	if ((-magSize < dist) && (dist < magSize)) {
213	SpritePattern pattern_j = spriteBuffer[line][j].pattern;
214	if (dist < 0) {
215	pattern_j <<= -dist;
216	} else {
217	pattern_j >>= dist;
218	}
219	SpritePattern colPat = pattern_i & pattern_j;
220	if (x_i < 0) {
221	assert(x_i >= -32);
222	colPat &= (1 << (32 + x_i)) - 1;
223	}
224	if (colPat) {
225	int xCollision = x_i + std::countl_zero(colPat);
226	assert(xCollision >= 0);
227	minXCollision = std::min(minXCollision, xCollision);
228	}
229	}
230	}
231	}
232	if (minXCollision < 256) {
233	vdp.setSpriteStatus(vdp.getStatusReg0() \| 0x20);
234	// verified: collision coords are also filled
235	// in for sprite mode 1
236	// x-coord should be increased by 12
237	// y-coord 8
238	collisionX = minXCollision + 12;
239	collisionY = line - vdp.getLineZero() + 8;
240	return; // don't check lines with higher Y-coord
241	}
242	}
243	}
244
245	void SpriteChecker::updateSprites2(int limit)
246	{
247	// TODO merge this with updateSprites1()?
248	if (vdp.spritesEnabledFast()) {
249	if (vdp.isDisplayEnabled()) {
250	// in display area
251	checkSprites2(currentLine, limit);
252	} else {
253	// in border, only check last line of top border
254	int l0 = vdp.getLineZero() - 1;
255	if ((currentLine <= l0) && (l0 < limit)) {
256	checkSprites2(l0, l0 + 1);
257	}
258	}
259	}
260	currentLine = limit;
261	}
262
263	inline void SpriteChecker::checkSprites2(int minLine, int maxLine)
264	{
265	// See comment in checkSprites1() about order of inner and outer loops.
266
267	// Calculate display line.
268	// This is the line sprites are checked at; the line they are displayed
269	// at is one lower.
270	int displayDelta = vdp.getVerticalScroll() - vdp.getLineZero();
271
272	// Get sprites for this line and detect 5th sprite if any.
273	bool limitSprites = limitSpritesSetting.getBoolean();
274	int size = vdp.getSpriteSize();
275	bool mag = vdp.isSpriteMag();
276	int magSize = (mag + 1) * size;
277	int patternIndexMask = (size == 16) ? 0xFC : 0xFF;
278	int ninthSpriteNum = -1; // no 9th sprite detected yet
279	int ninthSpriteLine = 999; // larger than any possible valid line
280
281	// Because it gave a measurable performance boost, we duplicated the
282	// code for planar and non-planar modes.
283	int sprite = 0;
284	if (planar) {
285	auto [attributePtr0, attributePtr1] =
286	vram.spriteAttribTable.getReadAreaPlanar<32 * 4>(512);
287	// TODO: Verify CC implementation.
288	for (/**/; sprite < 32; ++sprite) {
289	int y = attributePtr0[2 * sprite + 0];
290	if (y == 216) break;
291
292	for (int line = minLine; line < maxLine; ++line) { // 'line' changes in loop
293	// Calculate line number within the sprite.
294	int displayLine = line + displayDelta;
295	int spriteLine = (displayLine - y) & 0xFF;
296	if (spriteLine >= magSize) {
297	// Skip ahead till sprite is visible.
298	line += 256 - spriteLine - 1;
299	continue;
300	}
301
302	auto visibleIndex = spriteCount[line];
303	if (visibleIndex == 8) {
304	// Find earliest line where this condition occurs.
305	if (line < ninthSpriteLine) {
306	ninthSpriteLine = line;
307	ninthSpriteNum = sprite;
308	}
309	if (limitSprites) continue;
310	}
311
312	if (mag) spriteLine /= 2;
313	unsigned colorIndex = (~0u << 10) \| (sprite * 16 + spriteLine);
314	uint8_t colorAttrib =
315	vram.spriteAttribTable.readPlanar(colorIndex);
316
317	SpriteInfo& sip = spriteBuffer[line][visibleIndex];
318	int patternIndex = attributePtr0[2 * sprite + 1] & patternIndexMask;
319	sip.pattern = calculatePatternPlanar(patternIndex, spriteLine);
320	sip.x = attributePtr1[2 * sprite + 0];
321	if (colorAttrib & 0x80) sip.x -= 32;
322	sip.colorAttrib = colorAttrib;
323
324	// set sentinel (see below)
325	spriteBuffer[line][visibleIndex + 1].colorAttrib = 0;
326	spriteCount[line] = visibleIndex + 1;
327	}
328	}
329	} else {
330	auto attributePtr0 =
331	vram.spriteAttribTable.getReadArea<32 * 4>(512);
332	// TODO: Verify CC implementation.
333	for (/**/; sprite < 32; ++sprite) {
334	int y = attributePtr0[4 * sprite + 0];
335	if (y == 216) break;
336
337	for (int line = minLine; line < maxLine; ++line) { // 'line' changes in loop
338	// Calculate line number within the sprite.
339	int displayLine = line + displayDelta;
340	int spriteLine = (displayLine - y) & 0xFF;
341	if (spriteLine >= magSize) {
342	// Skip ahead till sprite is visible.
343	line += 256 - spriteLine - 1;
344	continue;
345	}
346
347	auto visibleIndex = spriteCount[line];
348	if (visibleIndex == 8) {
349	// Find earliest line where this condition occurs.
350	if (line < ninthSpriteLine) {
351	ninthSpriteLine = line;
352	ninthSpriteNum = sprite;
353	}
354	if (limitSprites) continue;
355	}
356
357	if (mag) spriteLine /= 2;
358	unsigned colorIndex = (~0u << 10) \| (sprite * 16 + spriteLine);
359	uint8_t colorAttrib =
360	vram.spriteAttribTable.readNP(colorIndex);
361	// Sprites with CC=1 are only visible if preceded by
362	// a sprite with CC=0. However they DO contribute towards
363	// the max-8-sprites-per-line limit, so we can't easily
364	// filter them here. See also
365	// https://github.com/openMSX/openMSX/issues/497
366
367	SpriteInfo& sip = spriteBuffer[line][visibleIndex];
368	int patternIndex = attributePtr0[4 * sprite + 2] & patternIndexMask;
369	sip.pattern = calculatePatternNP(patternIndex, spriteLine);
370	sip.x = attributePtr0[4 * sprite + 1];
371	if (colorAttrib & 0x80) sip.x -= 32;
372	sip.colorAttrib = colorAttrib;
373
374	// Set sentinel. Sentinel is actually only
375	// needed for sprites with CC=1.
376	// In the past we set the sentinel (for all
377	// lines) at the end. But it's slightly faster
378	// to do it only for lines that actually
379	// contain sprites (even if sentinel gets
380	// overwritten a couple of times for lines with
381	// many sprites).
382	spriteBuffer[line][visibleIndex + 1].colorAttrib = 0;
383	spriteCount[line] = visibleIndex + 1;
384	}
385	}
386	}
387
388	// Update status register.
389	uint8_t status = vdp.getStatusReg0();
390	if (ninthSpriteNum != -1) {
391	// Nine sprites on a line.
392	// According to TMS9918.pdf 5th sprite detection is only
393	// active when F flag is zero. Stuck to this for V9938.
394	// Dragon Quest 2 needs this.
395	if ((status & 0xC0) == 0) {
396	status = uint8_t(0x40 \| (status & 0x20) \| ninthSpriteNum);
397	}
398	}
399	if (~status & 0x40) {
400	// No 9th sprite detected, store number of latest sprite processed.
401	status = (status & 0x20) \| uint8_t(std::min(sprite, 31));
402	}
403	vdp.setSpriteStatus(status);
404
405	// Optimisation:
406	// If collision already occurred,
407	// that state is stable until it is reset by a status reg read,
408	// so no need to execute the checks.
409	// The visibleSprites array is filled now, so we can bail out.
410	if (vdp.getStatusReg0() & 0x20) return;
411
412	/*
413	Model for sprite collision: (or "coincidence" in TMS9918 data sheet)
414	- Reset when status reg is read.
415	- Set when sprite patterns overlap.
416	- ??? Color doesn't matter: sprites of color 0 can collide.
417	??? TODO: V9938 data book denies this (page 98).
418	??? This conflicts with: https://github.com/openMSX/openMSX/issues/1198
419	- Sprites that are partially off-screen position can collide, but only
420	on the in-screen pixels. In other words: sprites cannot collide in
421	the left or right border, only in the visible screen area. Though
422	they can collide in the V9958 extra border mask. This behaviour is
423	the same in sprite mode 1 and 2.
424
425	Implemented by checking every pair for collisions.
426	For large numbers of sprites that would be slow.
427	There are max 8 sprites and therefore max 42 pairs.
428	TODO: Maybe this is slow... Think of something faster.
429	Probably new approach is needed anyway for OR-ing.
430	*/
431	bool can0collide = vdp.canSpriteColor0Collide();
432	for (auto line : xrange(minLine, maxLine)) {
433	int minXCollision = 999; // no collision
434	std::span<SpriteInfo, 32 + 1> visibleSprites = spriteBuffer[line];
435	for (int i = std::min<int>(8, spriteCount[line]); --i >= 1; /**/) {
436	auto colorAttrib1 = visibleSprites[i].colorAttrib;
437	if (!can0collide && ((colorAttrib1 & 0xf) == 0)) continue;
438	// If CC or IC is set, this sprite cannot collide.
439	if (colorAttrib1 & 0x60) continue;
440
441	int x_i = visibleSprites[i].x;
442	SpritePattern pattern_i = visibleSprites[i].pattern;
443	for (int j = i; --j >= 0; /**/) {
444	auto colorAttrib2 = visibleSprites[j].colorAttrib;
445	if (!can0collide && ((colorAttrib2 & 0xf) == 0)) continue;
446	// If CC or IC is set, this sprite cannot collide.
447	if (colorAttrib2 & 0x60) continue;
448
449	// Do sprite i and sprite j collide?
450	int x_j = visibleSprites[j].x;
451	int dist = x_j - x_i;
452	if ((-magSize < dist) && (dist < magSize)) {
453	SpritePattern pattern_j = visibleSprites[j].pattern;
454	if (dist < 0) {
455	pattern_j <<= -dist;
456	} else {
457	pattern_j >>= dist;
458	}
459	SpritePattern colPat = pattern_i & pattern_j;
460	if (x_i < 0) {
461	assert(x_i >= -32);
462	colPat &= (1 << (32 + x_i)) - 1;
463	}
464	if (colPat) {
465	int xCollision = x_i + std::countl_zero(colPat);
466	assert(xCollision >= 0);
467	minXCollision = std::min(minXCollision, xCollision);
468	}
469	}
470	}
471	}
472	if (minXCollision < 256) {
473	vdp.setSpriteStatus(vdp.getStatusReg0() \| 0x20);
474	// x-coord should be increased by 12
475	// y-coord 8
476	collisionX = minXCollision + 12;
477	collisionY = line - vdp.getLineZero() + 8;
478	return; // don't check lines with higher Y-coord
479	}
480	}
481	}
482
483	// version 1: initial version
484	// version 2: bug fix: also serialize 'currentLine'
485	template<typename Archive>
486	void SpriteChecker::serialize(Archive& ar, unsigned version)
487	{
488	if constexpr (Archive::IS_LOADER) {
489	// Recalculate from VDP state:
490	// - frameStartTime
491	frameStartTime.reset(vdp.getFrameStartTime());
492	// - updateSpritesMethod, planar
493	setDisplayMode(vdp.getDisplayMode());
494
495	// We don't serialize spriteCount[] and spriteBuffer[].
496	// These are only used to draw the MSX screen, they don't have
497	// any influence on the MSX state. So the effect of not
498	// serializing these two is that no sprites will be shown in the
499	// first (partial) frame after loadstate.
500	std::ranges::fill(spriteCount, 0);
501	// content of spriteBuffer[] doesn't matter if spriteCount[] is 0
502	}
503	ar.serialize("collisionX", collisionX,
504	"collisionY", collisionY);
505	if (ar.versionAtLeast(version, 2)) {
506	ar.serialize("currentLine", currentLine);
507	} else {
508	currentLine = 0;
509	}
510	}
511	INSTANTIATE_SERIALIZE_METHODS(SpriteChecker);
512
513	} // namespace openmsx

Keyboard