123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527 |
- /*
- 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 <cassert>
- namespace openmsx {
- SpriteChecker::SpriteChecker(VDP& vdp_, RenderSettings& renderSettings,
- EmuTime::param time)
- : vdp(vdp_), vram(vdp.getVRAM())
- , limitSpritesSetting(renderSettings.getLimitSpritesSetting())
- , frameStartTime(time)
- {
- vram.spriteAttribTable.setObserver(this);
- vram.spritePatternTable.setObserver(this);
- }
- void SpriteChecker::reset(EmuTime::param time)
- {
- vdp.setSpriteStatus(0); // TODO 0x00 or 0x1F (blueMSX has 0x1F)
- collisionX = 0;
- collisionY = 0;
- frameStart(time);
- updateSpritesMethod = &SpriteChecker::updateSprites1;
- }
- static inline SpriteChecker::SpritePattern doublePattern(SpriteChecker::SpritePattern a)
- {
- // bit-pattern "abcd...." gets expanded to "aabbccdd"
- // upper 16 bits (of a 32 bit number) contain the pattern
- // lower 16 bits must be zero
- // // abcdefghijklmnop0000000000000000
- a = (a | (a >> 8)) & 0xFF00FF00; // abcdefgh00000000ijklmnop00000000
- a = (a | (a >> 4)) & 0xF0F0F0F0; // abcd0000efgh0000ijkl0000mnop0000
- a = (a | (a >> 2)) & 0xCCCCCCCC; // ab00cd00ef00gh00ij00kl00mn00op00
- a = (a | (a >> 1)) & 0xAAAAAAAA; // a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0
- return a | (a >> 1); // aabbccddeeffgghhiijjkkllmmnnoopp
- }
- inline SpriteChecker::SpritePattern SpriteChecker::calculatePatternNP(
- unsigned patternNr, unsigned y)
- {
- const byte* patternPtr = vram.spritePatternTable.getReadArea(0, 256 * 8);
- 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 byte* ptr0;
- const byte* ptr1;
- vram.spritePatternTable.getReadAreaPlanar(0, 256 * 8, ptr0, ptr1);
- unsigned index = patternNr * 8 + y;
- const byte* 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;
- const byte* attributePtr = vram.spriteAttribTable.getReadArea(0, 32 * 4);
- byte 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) {
- // 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;
- }
- int 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];
- byte colorAttrib = attributePtr[4 * sprite + 3];
- if (colorAttrib & 0x80) sip.x -= 32;
- sip.colorAttrib = colorAttrib;
- spriteCount[line] = visibleIndex + 1;
- }
- }
- // Update status register.
- byte 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 = 0x40 | (status & 0x20) | fifthSpriteNum;
- }
- }
- if (~status & 0x40) {
- // No 5th sprite detected, store number of latest sprite processed.
- status = (status & 0x20) | 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 (int line = minLine; line < maxLine; ++line) {
- 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 + Math::countLeadingZeros(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) {
- const byte* attributePtr0;
- const byte* attributePtr1;
- vram.spriteAttribTable.getReadAreaPlanar(
- 512, 32 * 4, attributePtr0, attributePtr1);
- // 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) {
- // 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;
- }
- int 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;
- int colorIndex = (~0u << 10) | (sprite * 16 + spriteLine);
- byte 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 {
- const byte* attributePtr0 =
- vram.spriteAttribTable.getReadArea(512, 32 * 4);
- // 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) {
- // 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;
- }
- int 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;
- int colorIndex = (~0u << 10) | (sprite * 16 + spriteLine);
- byte 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.
- byte 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 = 0x40 | (status & 0x20) | ninthSpriteNum;
- }
- }
- if (~status & 0x40) {
- // No 9th sprite detected, store number of latest sprite processed.
- status = (status & 0x20) | 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 (int line = minLine; line < maxLine; ++line) {
- int minXCollision = 999; // no collision
- SpriteInfo* 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 + Math::countLeadingZeros(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 (ar.isLoader()) {
- // 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.
- 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
|