decoder: Always attempt to produce data

[kstrafe]

Some images contain data outside the final scan so we need to account for this.

Not sure if we should overwrite planes like we do if we have overlap but the added reftest succeeds with this patch.

Issue: https://github.com/image-rs/image/issues/1234

[HeroicKatora]

Do you know any details on the copyright status of the reference test?

[kstrafe]

@HeroicKatora Not sure about copyright, @Shnatsel do you know?

Also with regards to opimization, is it possible to know somehow if we're at the last progressive scan for a plane? This way we can skip decoding previous progressive planes. Cargo bench has gone up for decode a 512x512 progressive JPEG by 198%.

[HeroicKatora]

@Shnatsel Where did you find them?

[kstrafe]

Related issue: https://github.com/image-rs/jpeg-decoder/issues/96

[Shnatsel]

This image is from an image collection that was going around via snail mailed over a decade ago. Sadly the copyright information is long lost.

[kstrafe]

Perhaps we should keep the progressive configuration and replace the content with a color gradient or something. Anyone know how to do this?

[HeroicKatora]

@BourgondAries Not sure, but if you find out removing the copyrighted info that way would be interesting for many other samples as well.

[Shnatsel]

I'll try mangling and minimizing the test case with a fuzzer. Hang on

[Shnatsel]

Done:

I made the fuzz harness crash if this particular error is encountered, and then used AFL's peruvian were-rabbit mode it discover other inputs that caused the same crash. Code used:

use afl::fuzz;

use jpeg_decoder::{Decoder, Error};

#[inline(always)]
fn decode(data: &[u8]) -> Result<Vec<u8>, Error> {
    let mut decoder = Decoder::new(data);
    decoder.decode()
}

fn main() {
    fuzz(true, |data: &[u8]| {
        let result = decode(data);
        if let Err(error) = result {
            match error {
                Error::Format(error_string) => {
                    if error_string == "no data found" {
                        panic!("That's me")
                    }
                }
                Error::Unsupported(_) => {}
                Error::Io(_) => {}
                Error::Internal(_) => {}
            }
        }

    });
}

[Shnatsel]

But I'm not sure a valid reference render even exists for this autogenerated file.

[kstrafe]

@Shnatsel the read data gives a difference from imagemagick's conversion to png (that's likely another bug). I think we need an image that just reproduces the progressiveness of the cat picture.

[Shnatsel]

Try this one

[kstrafe]

Still the same (decoding difference: "tests/reftest/images/partial_progressive-diff.png", maximum difference was 231), convert also issues a bunch of warnings including convert: Corrupt JPEG data: premature end of data segment 'partial_progressive.jpg' @ warning/jpeg.c/JPEGWarningHandler/397.

So this might be outside the spec (hence the difference in decoded data?).

[Shnatsel]

Yeah, the autogenerated images I posted likely exercise some undefined behavior. The original cat picture triggers no warnings though.

[kstrafe]

I've force-pushed with a file generated by fuzzing that was convertable by imagemagick (only has some corrupt data before its header, but this works), thanks @Shnatsel!

[kstrafe]

@HeroicKatora is this good for merging?

[Shnatsel]

Cargo bench has gone up for decode a 512x512 progressive JPEG by 198%.

Is this still the case? Even though I'm the person who originally filed the issue, I'm not convinced that supporting <0.1% of extra images is worth taking a 3x performance hit on all progressive images.

[kstrafe]

@Shnatsel should still be the case, yes. We could do re-do the jpeg decode by including planes if there exist missing planes here:

        if planes.is_empty() || planes.iter().any(|plane| plane.is_empty()) {
            return Err(Error::Format("no data found".to_owned()));
        }

This would still be correct, and only impact performance of these very rare images. If you think this is a good idea I can write a patch later today.

[HeroicKatora]

That sounds good. I kind of assumed you were already going to try this anyways since you asked about optimization somewhere early. The PR is also a good PoC for the method of reproducing and regression testing decoding errors while avoiding IP issues, that might actually have a lot more impact than this issue, format, library or even use case :smile:

[kstrafe]

The above appears to have a failure originating in criterion. Not sure if related to my patch.

[kstrafe]

It seems criterion 0.3.3 uses an unstable library feature in rust 1.34.2, I've attempted pushing with criterion 0.3.2 but 0.3.3 was still being compiled. @HeroicKatora

[Shnatsel]

Nice! Since the issue stems from coefficients_finished being unreliable, could you also add a comment why this extra code path is necessary, i.e. why the calculation of coefficients_finished can't be fixed?

[kstrafe]

@Shnatsel I honestly wouldn't know since I know nothing of JPEG decoding, but it seems like it assumes planes will be available when all coefficients are non-zero, which in some jpegs isn't the case. Added a comment in code similar to this.

[HeroicKatora]

You can ignore criterion failing for now (although it's annoying that CI doesn't continue with the other checks..).

That said, I'm not convinced that is a lot better. It introduces a new trait bound which is a major (breaking) change. In a sense, that is is the ultimate regression or non-fix¹. And I still don't sincerely understand how this is broken in the first place (I'd like to, to be confident in the solution). Brute-force decoding all scans and components is hardly a satisfying explanation. Is there a way to check if we'll need a single component in a scan later? Which wrong assumption does the code in the current form make (and then how do we correct it)? Why do other decoders not trip up, I'm sure not reasonably fast one will reparse the whole file? Could it be that compoments are allowed to be finished in different scans?

---

¹Also note that seeking to Start(0) is not correct. It only works if the stream was at that position initially. That is not necessarily true.

[HeroicKatora]

I honestly wouldn't know since I know nothing of JPEG decoding, but it seems like it assumes planes will be available when all coefficients are non-zero, which in some jpegs isn't the case.

Didn't see that before writing the comment. That might be the first good lead. More precisely it assumes all coefficients of all planes become non-zero at the same time. Maybe that is not guaranteed?

[HeroicKatora]

Here's a trace of the coefficients while decoding the above image, just before entering decode_scan:

Next scan
Component 0: coeff 0
Component 1: coeff 0
Component 2: coeff 0
Next scan
Component 2: coeff 18446744073709551614
Next scan
Component 1: coeff 18446744073709551614
Next scan
Component 0: coeff 1
Component 1: coeff 18446744073709551615
Component 2: coeff 18446744073709551615
Next scan
Component 0: coeff 18446744073709551615

[HeroicKatora]

I assume that plane 1 and 2 should be decoded in the second to last scan, and plane 0 in the last one. However, the current code would only decode the 0th plane and ignore the 1st and 2nd.

[HeroicKatora]

That would be the second confirmation then. I presume it might fail some tests though since it might overwrite some completed planes in later scans and it sounds more costly, e.g. the 0-plane would be decoded and discarded in the second to last scan here. I think we should treat each component of a scan separately. That would also come without any big performance cost as each plane is decoded once when completed.

[kstrafe]

Been trying to only make workers work on planes with self.coefficients_finished[i] == !0, but there's some dependencies here that I don't quite understand (causing among others out-of-bounds errors).

The previously pushed progressive image also differs from the cat picture in that it only finishes plane 0 and 1, but leaves plane 2 at 1 (that is - the coefficients_finished variable). What should we do in such cases? We are right in producing data but our coefficient is at 1. I looked at perhaps doing a look-ahead for an EOI marker (in which case we can force produce_data=true) but that marker is generated after decoding.

[HeroicKatora]

The applicable section appears to be the inverse of itu-t81, G.1.2.2 as mention in the paragraph that is G.2. For some reason, this particularly detailed and intricate part of the spec is not replicated for the decoder but relies on reversing the encoding procedure. Note that some easier scenarios contain full, lengthy descriptions of the procedure. W T F.

[HeroicKatora]

It appears, even though it does not explicitely say, that the specification allows any prefix of low-frequency bands to be specified. Only the zeroe'th coefficient (called DC) must be specified for all components in a frame. In progressive mode the coefficients of a components may further be divided into bands (that is, coefficients with subsequent indices) and a scan may contain a block of coefficients from any band of any component. Missing coefficients should be substituted by zeroes. If I read this right, then it may not even be necessary to specify all coefficients for an image to decode.

One particular restriction, which currently does not appear to be checked, for progressive encoded data:

[..] only scans which code DC coefficients may have interleaved blocks from more than one component. All other scans shall have only one component.

[HeroicKatora]

One further quote in the encoding part:

However, it is convenient to calculate the FDCT for the entire set of components in a frame before starting the scans

Since the decoding section says that the encoding should be reversed, it seems to follow that the recommendation is for all IDCT to start only after all scans have been completed. I'm not sure if I'm reading too much into it or how efficient this actually is.

[HeroicKatora]

The previously pushed progressive image also differs from the cat picture [..]

I noted. I have a patch ready that would fix the original image but not the reduced sample :(

[kstrafe]

The previously pushed progressive image also differs from the cat picture [..]

I noted. I have a patch ready that would fix the original image but not the reduced sample :(

Great! I don't think I can help much more with regards to fixing the decoder. I'll close this PR. Thanks for your time.

[HeroicKatora]

Thank you for your time and help with trying out ideas. And your input towards producing replacement images :)

[Shnatsel]

The reduced sample decoding differently might be valid. I don't expect the JPEG spec to fully define all behavior, so it probably triggers some edge cases not clearly defined by the spec. As long as the original image decodes and does not make everything 3x slower, I'd be happy.

[Shnatsel]

@BourgondAries thanks your contributions! This issue turned out to be more thorny than anticipated, but I feel you've made good progress here!