Change in behaviour causes test failures in `image-gif`

[bushrat011899]

Description

In the change from 0.1.8 to 0.1.9, image-gif now has a particular test fail due to an assertion within weezl. Using git bisect, I've determine the last working commit was 760619e, indicating the break is likely caused by 4790a35.

// Before
let want_more_space = if CgC::YIELD_ON_FULL {
    out.is_empty()
} else {
    out.is_empty() && !self.buffer.buffer().is_empty()
}

// After
let want_more_space = {
    out.is_empty()
};

The commit mentions a change in behaviour, but I'm not certain what the migration is for consumers of weezl to preserve existing behaviour?

[bushrat011899]

Toggling Configuration::with_yield_on_full_buffer doesn't appear to revert the change in behaviour either.

[kornelski]

@HeroicKatora

[197g]

I've yanked 0.1.9 as a first measure. We can always republish as 0.1.10.

[197g]

So there are two things, first the change condition and I think the debug assertion condition in 884. so at least the performance work itself isn't responsible for it, which is a little surprising in a good way.

So here's a better description of the bug and lessons:

1. The debug assert should be: self.table.is_full() || … as there's a different concern when we are no longer having any more size switches. Thankfully the code itself seems okay.
2. The gif crate is sometimes calling the decoder with an initially empty output buffer. This triggers the change in behavior.
3. It was previously expecting to get at least the next symbol interpreted and buffered, which is the end-of-stream symbol, but now this breaks the loop and it would always break the loop in the yield on full case. This change only affects downstream that passes an explicitly empty buffer.
4. It's a bit weird to construct a test for this to match the exact condition but I'll try. A few of the frames work, some do not.
5. This crate needs a better test suite. There's behavior being relied on that isn't tested. And since that behavior is in gif, it was quite intentional that this be stable behavior.

[197g]

@kornelski Have you ever tested behavior when passing a size of 1? While this is no longer legal as per the GIF spec, I think this implementation always failed to implement the size switching correctly here because it initialized next_code with a 3-bit number (4) that could never be read and thus never matched the condition for bumping the code size. Before I retest stuff that is already known maybe you have some knowledge about it.

[197g]

I think I have a fix ready but upholding the performance proved surprisingly difficult. Apparently rustc/llvm fails to consider unrolling the loop once and does not realize we introduce an invariant into the loop (self.buffer.buffer().is_empty()) that ensures the core loop can work on the output stream alone. This was implicitly upheld by the empty output: as long as there is a buffer the code block before the loop would move buffer to the output. That is the condition is initially upheld purely by mathematical reasons. (Yeah I should document this while I am at it).

The only method to efficiently test that invariant without always breaking on an empty output that I found is by manually inserting an additional precondition around the whole loop, i.e. doing the loop-header unrolling once myself and then removing redundant parts of its boolean test… That's quite unfortunate. I'll see if I come up with something more minimal.