Compression algorithm in mid2agb

[PlatinumLucario]

From reading the decomp, the mid2agb shows a compression algorithm that starts here.

Then it relies on a CalculateCompressionScore method to determine if the whole note is matching enough to be squashed into a patt, and if it is, it goes into CompressWholeNote and marks the whole note as a "pattern", with the specified whole note that it reads from.

That's how it works, at least in the mid2agb version used with the mainline Pokémon games.

Hopefully this can be used as a reference for a possible better compression algorithm too.

[ipatix]

Can you give an example where midi2agb produces non-ideal compression? I remember there were a few cases where midi2agb wouldn't compress ideally, but it's honestly too long ago that I remember which case that is.

[PlatinumLucario]

Okay, for example with mus_route104.mid when converting to ASM between mid2agb and midi2agb, and running their ASM files in Kompare, I found one whole note that doesn't get marked as a pattern in track 8 (track 9 in classic mid2agb, because it starts at 1 instead of 0) at the 3rd whole note on that track, as seen here:

And the other compression miss, is when repeated note types are not discarded:

[ipatix]

Huh, you're right. That clearly shouldn't happen.

[ipatix]

I think it may be because of this:

midi2agb/midi2agb.cpp

Line 1910 in 19a6f83

if (abar.events[ievt].type == agb_ev::ty::LOOP_START)

But in addition this bar doesn't collapse to a PATT because the bar contains a loop start marker, so it detects it as different (even though labels technically don't alter playback). I guess I could make it skip this, but I have to think this through that it doesn't cause other issues.

[PlatinumLucario]

Pretty sure I had a similar issue while rewriting classic mid2agb into C#, where one didn't get marked as a pattern:

That one turned out to be that I forgot to add the check for `events[index1].Param2 != events[index2].Param2` in the `IsCompressionMatch()` method, so this

            if (events[index1].Type != events[index2].Type ||
                events[index1].Note != events[index2].Note ||
                events[index1].Param1 != events[index2].Param1 ||
                events[index1].Time != events[index2].Time)
            {
                return false;
            }

Was supposed to be this:

            if (events[index1].Type != events[index2].Type ||
                events[index1].Note != events[index2].Note ||
                events[index1].Param1 != events[index2].Param1 ||
                events[index1].Param2 != events[index2].Param2 ||
                events[index1].Time != events[index2].Time)
            {
                return false;
            }

Might be a similar case with midi2agb?

[PlatinumLucario]

Also, I think any "PEND" command needs to not be counted, if it's to check if it's a matching pattern.

[PlatinumLucario]

From what I can see, any loop starting point always needs to have has its [songTitle]_[trackNumber]_LOOP right before the whole note marker, but because midi2agb places it below the whole note maker, that's where the issue lies

[PlatinumLucario]

So for the pattern stuff to work correctly, it needs the correct title, as such: [songTitle]_[trackNum]_[patternNum], could the issue be that it skips that part if the loop is in the same spot? Because it's definitely possible in the classic to have it in the same location, that's why the loop title is always above the whole note marker.

[ipatix]

In midi2agb the label order should not be relevant. Neither should it be relevant for the resulting file, since they'd point to the same address. However, perhaps labels and PENDs should be ignored. I'll have to look into this more carefully, since pretty much nothing is being ignored at the moment.

[PlatinumLucario]

I see, in that case, it shouldn't mark the next whole note as a reference for patterns, but rather the whole note that's marked as mus_route104_8_LOOP:, as seen here (classic mid2agb output on left, midi2agb output on right):

The main issue I can see here is that midi2agb isn't placing the "PEND" into the correct whole note at the bottom, but places it into the whole note that comes after it, along with adding the mus_route104_8_3: after the whole note marker.

And the ones that are marked as patterns should instead reference mus_route104_8_LOOP instead of mus_route104_8_3, for example:

This output:

@ 002   ----------------------------------------
mus_route104_8_LOOP:
        .byte           N04   , En1 , v112
        .byte   W16
        .byte                   En1
        .byte   W16
        .byte                   En1
        .byte   W08
        .byte                   En1 , v088
        .byte   W08
        .byte                   En1 , v112
        .byte   W16
        .byte                   En1 , v096
        .byte   W08
        .byte                   En1 , v112
        .byte   W04
        .byte                   En1 , v052
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte                   En1
        .byte   W04
@ 003   ----------------------------------------
mus_route104_8_3:
        .byte           N04   , En1 , v112
        .byte   W16
        .byte                   En1
        .byte   W16
        .byte                   En1
        .byte   W08
        .byte                   En1 , v088
        .byte   W08
        .byte                   En1 , v112
        .byte   W16
        .byte                   En1 , v096
        .byte   W08
        .byte                   En1 , v112
        .byte   W04
        .byte                   En1 , v052
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte   PEND
@ 004   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_3
@ 005   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_3
@ 006   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_3
@ 007   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_3
@ 008   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_3

Should be:

@ 002   ----------------------------------------
mus_route104_8_LOOP:
        .byte           N04   , En1 , v112
        .byte   W16
        .byte                   En1
        .byte   W16
        .byte                   En1
        .byte   W08
        .byte                   En1 , v088
        .byte   W08
        .byte                   En1 , v112
        .byte   W16
        .byte                   En1 , v096
        .byte   W08
        .byte                   En1 , v112
        .byte   W04
        .byte                   En1 , v052
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte   PEND
@ 003   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_LOOP
@ 004   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_LOOP
@ 005   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_LOOP
@ 006   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_LOOP
@ 007   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_LOOP
@ 008   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_LOOP

[PlatinumLucario]

Okay, I've kinda narrowed the issue down a bit, after some debugging with the breakpoints, it seems that the bars[2] and bars[3] may almost have the same events, but here's the difference: bars[2] contains LOOP_START in events[0] and bars[2] events vector contains 25 entries, while bars[3] events vector contains 24 entries.

Now I know that LOOP_START is added into the events list before the compression begins, which I have a feeling may be why it's considering them as different, even though they've got identical events.

So I'm gonna try testing it with it marking them is_referenced = true and does_reference = true before the LOOP_START and LOOP_END events are inserted and see what happens.

Or what I could do, is copy the bars entry to a new variable, and have the LOOP_START event removed from that new variable, so it can then be used for comparing with the other bars entry, so that is_referenced and does_reference can be correctly marked as true.

[PlatinumLucario]

Also, I've noticed some stuff like agb_out using a hardcoded format, instead of doing a conditional check to see if it references a LOOP_START location, and not writing the output

            assert(!abar.is_referenced || !abar.does_reference);
            agb_out(fout, "@ %03zu   ----------------------------------------\n", ibar);
            if (abar.is_referenced) {
                // TODO This sometimes adds unneccessary labels and PENDs below
                // In some cases the compressor will decide to not call this section
                // in the end due to smaller space usage without a call. Probably a bit
                // more complicated to fix.
                agb_out(fout, "%s_%zu_%zu:\n", arg_sym.c_str(), itrk, ibar);
                state.reset();
            }

If I end up implementing the change, it would end up writing two labels, which is not ideal:

@ 002   ----------------------------------------
mus_route104_8_LOOP:
mus_route104_8_2:
        .byte           N04   , En1 , v112
        .byte   W16
        .byte                   En1
        .byte   W16
        .byte                   En1
        .byte   W08
        .byte                   En1 , v088
        .byte   W08
        .byte                   En1 , v112
        .byte   W16
        .byte                   En1 , v096
        .byte   W08
        .byte                   En1 , v112
        .byte   W04
        .byte                   En1 , v052
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte                   En1
        .byte   W04
        .byte   PEND
@ 003   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_2
@ 004   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_2
@ 005   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_2
@ 006   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_2
@ 007   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_2
@ 008   ----------------------------------------
        .byte   PATT
         .word  mus_route104_8_2

So I'll need to look into this further, and implement something like a vector that contains a table of references to those [label]_[trackNum]_LOOP and [label]_[trackNum]_[patternNum] strings.

[ipatix]

Labels shouldn't be a problem. You can practically ignore them, since only really the assembler cares about them. They don't consume space and don't influence the song data.

[PlatinumLucario]

I agree, but for this one, it's not so much the label as much as the event that's in the bar itself, there is however a slight issue if I try to erase the loop_start element from the bar.events vector and re-add it back into the vector after the bar.is_referenced are marked as true.

When it tries to compare with the bars and the compression table, there ends up being a mismatch, causing it to crash with a "assertion failed" error. Very likely because I lack understanding of C++ memory management and is fairly new to me.

So I'm thinking the more easier (and probably best) approach would be to have the loop_start event inserted into the last event of the previous bar, instead of at the beginning of the current bar.

I'll give that a go and see if I can get any improvements or if I get memory errors from it.