nesdev.org

I usually employ the jump table/split jump table technique, running as many parallel tables as I need values for my structs. However, this creates a hard cap of 256 entries/indexes. So what I'm wondering, what are the various techniques for creating "structs" that can accommodate more than 256 entries?

The wiki unfortunately doesn't have (that I could find) a page on techniques for this. I'm especially interested in techniques that have some advantage over the others (cycles, complexity, etc). Right tool for the problem, right? I'm also curious if these techniques have any "name" like we have for "split jump table" or "rts trick", so I can google up more information.

The one I already know about is the classic LDA (address),Y trick, where you store the address to a blobish struct and read out it's values by adjusting Y.

But I imagine there must be more. Maybe using the carry to switch between table1 and table2, or jump tables of jump tables, or MMC5's multiplication register, or using some self-modifying code, etc.

The most straightforward method would be to simply have multiple levels of jump tables - one for each byte of your index, since the 6502 only has 8-bit registers to begin with. In other words, something like this: I also can't help but wonder exactly what it is you're doing that requires a jump table longer than 256 entries...

I've never heard this term, apparently it's a real term.

"The BLOB structure, derived from Binary Large Object, contains information about a block of data."

Well, regardless of the method you use, there's no way you'll achieve the same level of performance if you need to address more than 256 of anything... This is an 8-bit CPU after all.

I'm genuinely interested in knowing what practical use such a big jump table could possibly have?

Sumez wrote:I'm genuinely interested in knowing what practical use such a big jump table could possibly have?

Compiler-compilers like Flex (and probably Yacc) output huge jump tables. Probably irrelevant for NES games though

Quietust wrote: I also can't help but wonder exactly what it is you're doing that requires a jump table longer than 256 entries...

That. You didn't give details but if you need a jump table larger than 256 entries I can almost guarantee you're doing something wrong. This is why there is no "techniques" mentionned in the wiki - because nobody needs that.

The techniques for storing/using jump tables really apply to any tables, for the most part? Like really the only specific tricks I can think of for jump tables are stuff like using RTS or RTI, which are not really about the table or its size but just about how you use the data once retrieved.

So, some ideas:

1. Split multi-byte structures into parallel 1-byte tables ("stripes", "structure of arrays"). This gets you up to 256 entries pretty well.

2. LDA (indirect), Y is a straightforward generic solution. Tables of arbitrary size are easy to implement. As a jump-table specific option, you could also put a JMP (indirect) instruction in RAM (ZP?) ahead of time, update its operand with the computed lookup address, and run that directly instead of fetching it with LDA.

3. Multiple layers works too. Quietust suggested a jump table to select a second set of jump tables. Not sure whether the naive way of doing this is any better than just computing a pointer like in #2, but the subdivision idea itself has a lot of potential. Getting those subdivisions down to <= 256 entries lets you use the striping (#1) concept at the same time.

If you've got <= 512 entries or <= 1024 entries you might just branch to select from a couple of parallel LDA abs, X lookups? You can build a small binary tree search in code with a few ROR / BCS nodes.

If you've got an appropriate mapper with enough banks, you might even use banking to select pages of your table quickly. Put each 256-entry table in a different bank, and then a quick STA $8000 could be faster than doing any branching/indirection. (You can still use the rest of the bank for other data.) If your table is really large you're probably already dealing with banks anyway.

Thanks for the responses!

Quietust wrote:I also can't help but wonder exactly what it is you're doing that requires a jump table longer than 256 entries...

Sumez wrote:I'm genuinely interested in knowing what practical use such a big jump table could possibly have?

SMB3 already has 180 different kinds of game objects: Mushroom, Fireflower, Leaf, Hammer Bros Suit, Goombas, Flying Goomas, Koopa Troopas, Boo, Chain Chomp, Cheep Cheep, Piranha Plant, Bullet Bill, Bob-omb, Thwomp, Blooper, Dry Bones, Hammerbros, Sledge Bro, Nipper Plant, Para-Beetle, etc etc etc etc.

You could problaby trim away some of the broken unused game objects from the engine, and use the leftover 76 slots, but in the end the majority of slots is already taken. If you were going to, say, port over the game objects from SMB2 and SMBW you'd find yourself running past the 256 limit in a flash.

There is also the thing that a lot of game objects use another game object as a different "state", for instance, enemies that hide in their shell when stomped on does so by changing themselves into a different game object. I could probably bake those behaviors into the original game object but it would be a pretty big overhaul, and it would incur some execution cost.

And there are even game objects that have duplicates with slight behavior differences. Bob-ombs shot out of a cannon walk around for a few seconds before exploding, while Bob-ombs found naturally in various levels walk around forever until Mario disturbs them. Nintendo solved this by simply making it two different types of game objects that invokes mostly the same routines.

Bregalad wrote:That. You didn't give details but if you need a jump table larger than 256 entries I can almost guarantee you're doing something wrong. This is why there is no "techniques" mentionned in the wiki - because nobody needs that.

You can almost guarantee that no NES game needs jump tables larger than 256? Wut?

How about like, a JRPG that wants more than 256 types of enemies? More than 256 types of items/weapons?

I get that usually 256 is more than enough, but surely that cannot be some universal rule.

rainwarrior wrote:you could also put a JMP (indirect) instruction in RAM (ZP?) ahead of time, update its operand with the computed lookup address, and run that directly instead of fetching it with LDA.

Oh, you mean having code instead of data? That's an interesting idea, enemies could have an "initialization" routine instead of static data. You'd probably have to store certain of those values in RAM though, unless you wanna run that routine each time you need to look up some bit or byte.

rainwarrior wrote:If you've got an appropriate mapper with enough banks, you might even use banking to select pages of your table quickly. Put each 256-entry table in a different bank, and then a quick STA $8000 could be faster than doing any branching/indirection. (You can still use the rest of the bank for other data.) If your table is really large you're probably already dealing with banks anyway.

Interestingly enough, this is already what SMB3 does for it's game objects, except each bank only holds 36 entries for some bizarre reason (defeating the point). I thought about adopting the same technique, but figured it's too messy.

Does switching banks incur any cycle cost? If not, I might reconsider it. All each entry would need would be a bank number and the usual object id, and looking up the data would be ultra cheap, provided that the only cost to switching the bank would be the LDA/STA to the register.

Drakim wrote:Does switching banks incur any cycle cost? If not, I might reconsider it. All each entry would need would be a bank number and the usual object id, and looking up the data would be ultra cheap, provided that the only cost to switching the bank would be the LDA/STA to the register.

The only "cost" behind switching banks is the amount of time required to write to the bank register - in hardware, the "bank bits" are updated every cycle based on the address you're currently accessing.

That's great. Although it's a bit messy (especially since you gotta ensure the data is perfectly aligned between banks), that's gotta be the most performant big jump table remotely possible on the NES.

Stepping back a bit, if you have more than 256 items to dispatch on, then your identifier will be at least 2 bytes. It can make sense then to just use address pointers for IDs instead of enums & dispatch tables at all.

Whether or not those pointers point to code to jump to, point to a data structure for LDA (zp),y addressing, or are larger than 16-bit to accommodate banking information (or encode banking in various bits of the 16-bit word to be extracted before use to save space) is up to you. But it's big enough that you can use the identifier itself directly.

White Flame wrote:Stepping back a bit, if you have more than 256 items to dispatch on, then your identifier will be at least 2 bytes. It can make sense then to just use address pointers for IDs instead of enums at all.

Whether or not those pointers point to code to jump to, point to a data structure for LDA (zp),y addressing, or are larger than 16-bit to accommodate banking information (or encode banking in various bits of the 16-bit word to be extracted before use to save space) is up to you. But it's big enough that you can use the identifier itself directly instead of having to store large dispatch tables for further lookup.

This is indeed true. It also has the advantage being "limitless", you could pretty much park your data anywhere. However, there are some other advantages you might be missing out on.

If you are simply using addresses then there will be no rhyme or reason to their order, while a 2 byte index follows a linear predictable order. This means you could potentially do stuff like look up the "next entry", scan though entries searching for a value, or pick a random entry.

Also the bank switching technique rainwarrior mention is a lot faster, if performance is important. Using the identifier directly is probably faster than having a jump table of jump tables though.

My original thoughts on this was
There is no way you are going to be able to update more than 256 entities in a frame, so you might as well split them across multiple frames and thus each jump table will be under 256 bytes.

However your problem is not that one, its you want to have a potential 256+ number of entity code functions. To which I don't think having a massive LUT on the function is the way to go.
When you have that many functions you are
a.) not going to need all of them at once ( no need for 256+)
b.) not going to be able to fit all of them in a single bank ( this is why Nintendo only have 36 entries in the bank ) Given you need to keep your NMI and IRQ handlers in ROM as well that puts you in a mapper that is going to give you a 16K bank( most probably )

At this point to do the dispatch, you are going to need it to be in some common ROM area, and is going to need to translate 2 bytes into 3 bytes ( bank, lo, hi ), I would either, depending on the needs.
Make a dynamic table of 256 and then you fill in the 256 the level you want needs, thus you drop the table down to 256 per level.
Or
You make a table to the Entities FSM and then have sub states inside the FSM that you dispatch on. For example the walk around Bomb-ob and the Para-shooting Bomb-ob both are Bomb-Obs but the first starts at Bomb-Ob FSM state 0 while the Para one starts at FSM state 5 and then they share the explode logic state as say FSM state 4. This allows you to fold the 256+ states into smaller FSMs for dispatch.
Or if you have a large number and you have a large number of shared update functions. Do the more expensive look up once and then store the Bank and Ptr Lo and Ptr Hi along with State number for each entity. Thus each frame you load/store the bank then jump to the Lo/Hi function for maximum speed. And then when you need to change it you have the State number to modify and then do the more expensive 256+ 2byte -> 3 byte look up.

Another way to speed this up is to sort your entities by state, then make the dispatch function cache the last result. Then when it goes to do the next ent, it looks up to see if the index is the same as the last and if so, just uses the existing values.

While there's no way to argue that it will always be true, I feel it's extremely unlikely to have more than 256 entirely different types of objects that are still similar enough to justify sharing the same jump table. For example, is there a reason that a boss enemy should be interchangeable with a powerup that does nothing other than sit still and wait to be touched?
Moreover, I feel that once you're dealing with so many variations, you're beginning to work with repeated patterns that should justify ordering your logic differently - Having 256 different potential subroutines to jump to actually sounds more wasteful to me than the huge jump table itself.

The examples you came up with yourself are actually good examples for this:

Drakim wrote: How about like, a JRPG that wants more than 256 types of enemies?

I can't say for sure how popular JRPGs did this, but here's how I would do it. Every enemy in a JRPG shares the same basic behavior, so I most likely wouldn't have a jump table based on the enemy type. Instead a simple scripting system or stored data segments would help decide what patterns each enemy should follow. For example you would have one enemy with the following data (very simplified):

Graphic: (pink palette swap of a goblin graphic)
HP: 255
Defense: 14
Behavior 1: Always use melee attacks
Behavior 2: Attack characters with the lowest HP xx% of the time
Behavior 3: (null)

Even though you might have more than 256 different enemy types, they'll most likely be a similar combination of behaviors, and those are unlikely to exceed 256. Or if they do - you could change the system to have "types" of behavior, eg. one jump table to decide how the monster should choose its target, one to determine which attacks to use, one to determine how likely it is to flee, etc.

Drakim wrote:More than 256 types of items/weapons?

This one is absolutely just data. A sword is unlikely to be more than just a set of bytes to indicate attack power, a graphic, a sell price, maybe a level requirement, etc. Having a jump table to handle different behaviors for each possible weapon for any place in the code that handles weapons/items, sounds absurdly excessive.
For special exceptions, such as curses or helpful effects, how this is handled is probably very unique to the effect in question. For example an item that heals your HP while walking, you'd probably just have code that specifically checks for this item to be equipped by anyone whenever you take a step. Or if you have multiple items with walking effects, that's just a flag somewhere in the item data, and then you'd have a jump table for those effects specifically.