Challenge!

[neilbaldwin]

I need someone clever to come up with an efficient way to scan my tracker's Songs for used Pattern numbers.

I've got 8 Songs with 5 Tracks in each song. In each track there are 128 steps, a step is simply a Pattern number. There are 128 Patterns.

Any Pattern number can be used in any step and can be used multiple times.

One of the functions of Pulsar's editor needs to find an unused Pattern.

I've tried several different ways to do this but all of them so far take far too much processing (just to check ever Step of each Track of each Song is over 5000 iterations alone).

The ideal solution (because this type of information is useful in other areas of the editor) would be to maintain at all times which Patterns are used and which aren't.

Over to you

[tepples]

I've got 8 Songs with 5 Tracks in each song. In each track there are 128 steps, a step is simply a Pattern number.

So far similar to the order table of NerdTracker II.

One of the functions of Pulsar's editor needs to find an unused Pattern.

The first pattern after the last used pattern should work.

I've tried several different ways to do this but all of them so far take far too much processing (just to check ever Step of each Track of each Song is over 5000 iterations alone).

How long does an iteration take, and how long is the user willing to wait? It takes 16,384 iterations to fill a page of CHR RAM using a pixel-based codec, yet Codemasters games do exactly this.

If you're trying to garbage-collect unused patterns, people are used to waiting up to a few seconds for this to occur: "FRE" on Applesoft BASIC, "Compact Stack" on HyperCard, "Compact Folder" on Outlook Express, "Compact and Repair" on Access, "Compact Database" (the VACUUM command) on SQLite Database Browser, defragmentation on numerous file systems, etc. The upper bound for an acceptable defrag pause on an NES game is probably the time to save in Mario Paint for Super NES.

The ideal solution (because this type of information is useful in other areas of the editor) would be to maintain at all times which Patterns are used and which aren't.

In other words, the "volume bitmap" on a file system. That information can be rebuilt in the background when the program starts.

[Memblers]

What I had envisioned doing (I never worked on any editor for it) for optimizations during pattern editing was to keep it unoptimized during editing, but when you play it or before you switch to edit a different pattern, it compresses it (re-using repeated data from other patterns, if possible). When saving the entire file, then it would iterate through each pattern to re-optimize, because more repeated data could have emerged. I guess this works out sort of like LZ77 in the end result, a sliding window buffer, if I understand the term correctly. Seems convoluted but maybe the music data would be pretty compact, and able to reference the unpacked data if it's in the buffer. I don't know if that's much help, though, being just a general idea.

[blargg]

Yeah, some kind of compression scheme that was block-oriented, with good performance for gradual decompression going forwards. So for editing, you decompress one block and edit it uncompressed. I actually used something almost exactly like this in QuickNES for storing a movie of the entire game. When a new block is accessed, it decompresses before giving you the pointer. Then if you access it again, it sees it's already decompressed. So the question is whether there is a lot of seeking.

[neilbaldwin]

I wish I had more hands so I could give you four thumbs down.

[Tom]

So if I understand correctly, there's 128 patterns, and you just need to find one that's not used? Use 128 bytes, each byte is the use count of that pattern. When something references the pattern, increment its use count, and when something stops using it, decrement. To find an unsed pattern just loop over the 128 bytes looking for a zero.

[tokumaru]

So if I understand correctly, there's 128 patterns, and you just need to find one that's not used? Use 128 bytes, each byte is the use count of that pattern. When something references the pattern, increment its use count, and when something stops using it, decrement.

That's exactly how my old level editor used to work. Since it created block structures dynamically, every time a block was added to or removed from the map I had to make sure no orphan structures would be left around.

To find an unsed pattern just loop over the 128 bytes looking for a zero.

Or you could have a linked list of unused patterns. If each pattern is not gonna be used more than 128 times, you can use bit 7 to distinguish between used an unused, and the lower 7 bits would be either the number of times it was used (minus 1 to fit the 0 to 127 range) or the index of the next unused pattern. Then all you need is an extra variable to indicate the first unused pattern.

So, when you need to use a new pattern, just grab the index from that variable, go to that pattern and grab the index of the next unused pattern and overwrite the variable with that so it becomes the first unused pattern, and then indicate that the current slot is not unused anymore by using its flag and reset the usage count.

When you decrement the usage count and detect that the pattern is not being used anymore you can just add it to the beginning of the list of free patterns by linking to it with the variable I mentioned before and making it link to the pattern that the variable was linking to previously.

This will give you quick access to the slots since you will not have to waste time searching for anything.

[neilbaldwin]

So if I understand correctly, there's 128 patterns, and you just need to find one that's not used? Use 128 bytes, each byte is the use count of that pattern. When something references the pattern, increment its use count, and when something stops using it, decrement. To find an unsed pattern just loop over the 128 bytes looking for a zero.

Thanks Tom.

It did occur to me to do something similar but because it's physically possible to use the same Pattern more than 255 times I discounted it. Whether you would or not is another question but because you *can* you'd need a solution that could either cope with that or stop the user from doing so.

For sanity's sake though I might actually go down this route.

[Kasumi]

Then, rather than using one byte of RAM per pattern, use two as a 16 bit number. Can the user use a pattern more than 65,535 times?

[tepples]

Then, rather than using one byte of RAM per pattern, use two as a 16 bit number.

Now you've used 1/8 of the NES's internal RAM to keep a reference count.

Again, how long does each iteration take? You'll have to do that to build the reference count at power-on anyway. The delay might be something that can be hidden by an animation.

[neilbaldwin]

Then, rather than using one byte of RAM per pattern, use two as a 16 bit number.

Now you've used 1/8 of the NES's internal RAM to keep a reference count.

Again, how long does each iteration take? You'll have to do that to build the reference count at power-on anyway. The delay might be something that can be hidden by an animation.

There are a couple of utility functions that scan each song, track by track (i.e. the 5000+ iterations that I eluded to). That's fine for situations where you're not refreshing the audio engine (remember: Pulsar is refreshing the audio several times per frame so there's not a lot of CPU time left).

The trouble is there is a "Clone Pattern" and a "Insert Next Free Pattern" function that you really need to be able to use on-the-fly while the music is playing. Both these functions rely on being able to retrieve a free Pattern very quickly (i.e. within the current frame).

[tokumaru]

Both these functions rely on being able to retrieve a free Pattern very quickly (i.e. within the current frame).

If this is the case you could just use the linked list I talked about before. If you keep this list of free patterns you can get a new one instantaneously, without any kind of search. Then you can return unused patterns to this list at a slower pace, since from your description that task doesn't seem as urgent.

[tepples]

The trouble is there is a "Clone Pattern" and a "Insert Next Free Pattern" function that you really need to be able to use on-the-fly while the music is playing. Both these functions rely on being able to retrieve a free Pattern very quickly (i.e. within the current frame).

Unless you need to rapidly find free patterns one after another, you might be able to get away with caching only one free pattern. Then once that pattern is created, you can start the iterations to find the next pattern.