Character RAM data write

The wiki states:



I'm:
-Not uploading OAM through DMA
-Not writing to nametable space
-Not writing attributes or palettes
-Not doing scanline trickery to cheat on vblank time

and yet I can only upload 6 tiles max. before the PPU gets confused and messes up writing (spilling beyond vblank). Any advice on how I can improve my code (below)? Or do I need to convert character data to sequential LDA/STA instructions?

You have 20 scanlines during vblank. 20 × 341 ÷ 3 = 2273 cycles.
You're currently uploading 96 bytes, or about 23 cycles per byte.

Let's look at your code:

Yup, that's why.

You'll need a lighter loop to get more bytes uploaded. Align things to pages, don't use multiple iterators, don't expect to be able to use a single general-purpose loop. You probably don't need to have a dedicated partially-unrolled "upload 16 bytes to replace a tile" but if that's your primary use case you may as well.

Well, look at all the branches and index register updates you're doing! Note that the wiki says "moderately unrolled VRAM loading code", and this is not unrolled at all.

The first thing you have to consider is that each tile is 16 bytes, so it's pointless to do all this housekeeping every byte if the transfer will only end on 16-byte boundaries. Unrolling means that you do more work per iteration of the loop, effectively reducing on the amount of branches and comparisons, which add up to a lot of cycles if performed frequently.

Since each tile is 16 bytes, the most obvious optimization you can do is copy 16 bytes during each iteration of the loop, without performing any checks along the way, since you know for sure the transfer won't end before the tile does:


Any particular reason why you are counting down to the pointer overflow using a separate register? The Y register alone will tell you this when it wraps from 255 to 0, there's no need for extra logic here. This frees X to count tiles. Also, as long as the tiles are properly aligned to 16-byte boundaries in the ROM, you don't need to check for pointer overflows, once every tile is fine:


But honestly, even one INY for each byte will cost you a few tiles. If you can buffer the tiles in RAM first you can copy them to VRAM with:


Which is obviously faster.

If you store the tiles interleaved in the ROM (16 1st bytes, then 16 2nd bytes, and so on), you can use indexed addressing to read tiles directly from ROM just as fast, using X to index which tile you're reading:


The only problem with this is that you'll only be able to address 256 tiles this way. To overcome this, I started addressing groups of 4 (or more) tiles, rather than individual tiles, so you can address a total of 1024 tiles, which occupy 16384 bytes, conveniently the same size of a PRG-ROM bank in many mappers.

This is the "moderately unrolled" loop I was referring to. Buffer up to 10 tiles in unused parts of the stack ($0100-$019F) and blast them to VRAM during vblank.

LDA (ptr), Y is the slowest form of LDA, aside from the obscure LDA (ptr,X). For starters, try not accessing data through a pointer. If you need timing reference, see: http://www.6502.org/tutorials/6502opcodes.html#LDA

If you can trade size for speed, you can unroll your loop:


You could also partially unroll:

(There's some more work you could do to this snippet to optimize, but I'm just trying to demonstrate the partial unroll.)

If your data is static, you could store your CHR data as code rather than bytes to upload:

vs.

or even use A/X/Y to avoid redundant loads:

Battletoads actually unpacks its CHR data into RAM like this, and during vblank runs that code from RAM. Obviously this requires a lot more space than just the data bytes, though.

One trick that I like is to store your update on the stack. You temporarily save the stack pointer and then move it to your data, then each byte write looks like:

No need to increment an index register, keep track of a pointer, etc. it's inherent in the PLA. Very easy to unroll this as needed.

Such use of stack is, however, slower to execute than the "code-as-data" [that is, code as LDA #imm / STA $2007 as shown], as PLA is 4 cycles; immediate loads, 2. Brain does not have sufficient resources tonight, for some reason I thought my rebuttal was ninja'd by the post I was rebutting.

Thanks everyone, I think I'll use the strategy of unrolling 16 byte writes (for each tile) and character data alignment in ROM. Maybe even a RAM buffer (on unused stack space?) to uncompress char data if I'm not too lazy to build one.
I can't afford to waste much space (specially with all the program ROM I'm going to use for tile storage -- I'm building an adventure game and each screen can have 144 unique tiles max (!). Poor design? I don't know really but I'm not proficient in art design for tiled games (or any kind of art, for that matter) so I need to follow up with this plan unless I want everything in my game blocky and uglier.




How exactly? I don't understand how to address groups of 4, do you do something like this below or is it more involved than that?

Well, if you want to compare them by speed alone, LDA immediate is the fastest possible, yes. It's a tradeoff of size (either ROM or RAM) for speed though.

The PLA method is reasonably fast, and makes conservative use of RAM. A partially unrolled LDA abs, X is similar in speed to using PLA, but the code required is slightly larger.

The LDA (indirect), Y proposed at the beginning of this thread is more or less the slowest naive method of doing this.


Punch: using striped data like that is an alternative way to unroll your loop. It makes incrementing the index register simpler, at least. Outside the vblank there is probably some increased comlexity somewhere to organize the data (ideally: done offline by a tool).

I considered using the immediate method, in ROM, for tiles that need to be updated constantly, like the main character and animated level objects. This is an incredible waste of ROM though (each byte expands to 5 bytes!), so this is only worth it if you have lots of space available. I started coding a tool to minimize this expansion a little, by using all 3 registers as a small dictionary of recently used values and using INX, DEX, INY, DEY, ASL, LSR, ROR and ROL instead of loading new values whenever possible, but never implemented most of the ideas. The hard part is to figure out which register is the best one for loading a new value to, considering transformations it will go through in the future and how soon the old value will be used again.


Unrolled PLAs are interesting because they use less ROM, and when you have it completely unrolled, you can easily jump in the middle of the code to copy variable amounts of bytes, if you ever need that.

Another place you can put the buffer in is zero page, and as long as you use ZP addressing (meaning the code has to be completely unrolled) you can transfer each byte in 7 cycles, slightly faster than the 8 cycles of the PLA or absolute indexed methods.


Yes, the complexity is all about converting the CHR data from linear to interleaved, which should be done by a little script before the ROM is assembled, so this doesn't have any negative impact on the NES program itself. The main advantage of this method is that you don't have to waste CPU time or RAM preparing the data and buffering, you can blast it straight from ROM to VRAM without any speed penalty.


Something like this, but I'm not sure what A1, A2, etc. mean in your diagram. Let me draw a diagram of what I have in mind:


Since each tile is 16 bytes, a group of 4 would be 64 bytes, so you'd need an unrolled loop that transfers that many bytes (this code would use 384 bytes of ROM). The code would look like this:


Yes, it does use quite a bit of ROM, but it's the only way I'm aware of to avoid the (slow) indirect indexed addressing and still copy the data straight from ROM to VRAM, not wasting CPU time on buffering. If you can program using any language on the PC you can make a tool to interleave the CHR data in 5 minutes.

Each iteration of this loop takes 521 cycles to execute, so you can safely copy 4 blocks of 4 tiles = 16 tiles each frame if you're doing nothing else during VBlank.

I don't think I saw it mentioned, but if the tile/sprite data has repeated bytes (at least 2), then you could get a small speed up with just a redundant STA (no need to re-read or load, etc). That, and possibly prime X and/or Y with the most constant used byte for that data segment to upload, that way it doesn't need to be just sequential repeats. It's only a small optimization, but it's something (I thinking more along the lines of generating the code for this during active display, so it wouldn't apply for existing rom code, unrolled or not).

I did mention a tool I was coding to perform such optimizations on code that would be stored in ROM.

I wouldn't try something like this in realtime though, because the time spent on analyzing the data would be too disproportional (e.g. to know what the most common values are you'd have to scan all the data beforehand) to the little time you'd gain with the optimizations. And you can't even guarantee that there will be successful optimizations every time, so you can't count on that extra time anyway. An offline tool on the other hand could easily count the cycles as it generates code, so you'd always know if a particular block of CHR could be updated in the time you have available.

If you really need this little bit of extra time, it would make much more sense to blank some scanlines and get some extra VBlank time.

Or RAM, as Rainwarrior pointed out. Unrolled loops are pretty trivial to make loops to write into (W)RAM, after all. You don't have to STORE CHR data as code in the ROM itself, just have it so for when you're going to send it. Granted, generating the three-register-lookback version would be harder than just dropping the LDA #xx STA $2007 (A9xx8D0720) over and over...but having the unrolled loop with N iterations of that and deciding where to jump in rather than having loop-control means you'd only have to write the data each update frame, not rewrite the code. (Inserting PPU address-changes would likewise be relatively easy, just changing a 6 to a 7 as necessary...but you'd need to remember to change it back for the sake of the next update.)
it was:

Including register re-stores and use of A, X, and Y?

No, from what I recall Battletoads just has a block of LDA imm / STA $2007 in RAM, and updates the immediate values as needed. If you want to know the details, though, it's easy to just take a look in a debugger.

Yes, that has been discussed before. The comment you quoted however was about the specific technique I was detailing (interleaved tiles accessed with absolute indexed addressing), which allows copying data straight from ROM to VRAM, which has the advantage of not stealing time from the game logic in order to buffer the values.


I didn't know Battletoads did this. I never expected a game without extra RAM to do this, since even a small block of 8 tiles (128 bytes) would expand to 640 bytes, over 30% of the RAM total (2KB).

No, definitely not realtime. The cell, or rather a chunk of data, would be processed external of runtime. That gives the added benefit of compression as well, but slight possible bloat as well (1 extra bit per byte, but really it's dependent on how you implement it). But yeah, predetermined at or before assemble time.





Exactly. You would know what the cycle count would be for that chunk of data to transfer. Yeah, it might be variable from chunk to chunk, but that doesn't mean you can't optimize for such results. The level could be designed in such a way that only certain objects or tile cells can be uploaded per frame, so you design the level around these factors. And knowing the cycle counts ahead of time, allows you figure that into transfer window of time, as well as the build window (active display area).




Nothing says you can't combine both methods. It's a more extreme optimization, but like all level of optimizations - they have their set of limitations; maybe not great for every situation, but specifically advantageous when applicable.

I know the NROM version of Driar does it, but in which level of Battletoads does this happen? I seem to remember that Battletoads stores its VRAM update list in unused stack and does an unrolled PLA STA $2007 loop.

True, I was aware of Driar. It's a simpler game though, with smaller worlds to keep track of, so it can spare a little more RAM than the typical early 90's NES game.

Actually, Battletoads has a block of LDY PTR,X STY $2007 (16 times) in RAM (about 110 bytes).
to prepare code it's change ptr (of char gfx), with every next low byte of ptr greater on 1.
X and A starts from zero, and incremented by ADC #$10 TAX BNE loop. (so total 16 times) =256 bytes (16tiles).
However it doesn't run for full speed, because before it waits for cross-page penalty of ptr,X based on low ptr value - required to timings.
Similar code also used to animate tiles for level2 parallax.
(and you can find same code in my duck tales 2 - two players hack.)

PLA/STA used for update raw/column/attributes/palette.

For update snakes in karnath lair it's uses extreme code in ROM with much of everything. (see BANK3:8062) (bank6 in fceux).