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