Upcoming breaking changes & locking in the data format

[phoboslab]

Saying that I'm surprised by the amount of attention this is getting would be an understatement. There's lots of discussion going on about how the data format and compression could be improved and what features could be added.

I want to give my views here and discuss how to go forward.

First and foremost, I want QOI to be simple. Please keep this in mind. I consider the general compression scheme to be done. There's lots of interesting ideas on how to improve compression. I want to tinker with these ideas - but not for QOI.

QOI will not be versioned. There will only be one version of QOI's data format. I'm hoping we will be able to strictly define what exactly that is in the coming days.

QOI will only support 24bit RGB and 32bit RGBA data. I acknowledge there's some need for fewer or more channels and also for higher bit depths or paletted color - QOI will not serve these needs.

So, with all that said, there's some breaking changes that are probably worthwhile. I want to discuss if and how to implement those.

Proposed changes

1. width, height and size in the header should be stored as big endian for consistency with the rest of the format (this change already happened in c03edb2)

2. Color differences (QOI_DIFF_*) should be stored have the same range as two's-complement. That means:

• 2bit: -2..1 instead of the current range -1..2
• 4bit: -8..7 instead of the current range -7..8
• 5bit: -16..15 instead of the current range -15..16

3. The header should accommodate some more info. Currently there's demand for
   3a) number of channels ( The number of channels should be encoded in the QOI header #16)
   3b) the colorspace (Consider adding a sRGB flag to the header #25 and this huge discussion on HN)
   3c) un-/premultiplied alpha (Clarify that RGBA means non-premultiplied alpha #13)
   3d) user-defined values

So, 1) is already implemented; 2) seems like the right thing to do (any objections?); 3) is imho worth discussing.

3a) Storing the number of channels (3 or 4) in the header would allow a user of this library to omit if they want RGB or RGBA and files would be more descriptive of their contents. You would still be able to enforce 3 or 4 channels when loading. This is consistent to what stbi_load does

int x,y,n;
unsigned char *data = stbi_load(filename, &x, &y, &n, 0);
// ... process data if not NULL ...
// ... x = width, y = height, n = # 8-bit components per pixel ...
// ... replace '0' with '1'..'4' to force that many components per pixel
// ... but 'n' will always be the number that it would have been if you said 0

It is my opinion that the channels header value should be purely informative. Meaning, en-/decoder will do exactly the same, regardless of the number of channels. The extra 5bit for alpha in QOI_DIFF_24 will still be wasted for RGB files.

3b) I don't understand enough about the colorspace issue to gauge the significance. If we implement this however, I would suggest to give this a full byte in the header, where 0 = sRGB and any non-zero value is another, user-defined(?) colorspace.

3c) I'm against an option for premultiplied alpha, because it puts more burden on any QOI implementation to decode in the right pixel format. We should just specify that QOI images have un-premultiplied alpha.

3d) For simplicity's sake I'd like to put 3a) and 3b) as one byte each into the header. I'm uncertain if we then should "pad" the u32 size in the header with two more bytes. This would make the size 4byte aligned again, but there's probably no need for it!? A u16 unused could also cause more confusion when other QOI libraries suddenly specify any of these bits to mean something.

With all this, the header would then be the following 16 bytes:

struct qoi_header_t {
	char [4];       // magic bytes "qoif"
	u16 width;      // image width in pixels (BE)
	u16 height;     // image height in pixels (BE)
	 u8 channels;   // must be 3 (RGB) or 4 (RGBA)
	 u8 colorspace; // 0 = sRGB (other values currently undefined)
	u16 unused;     // free for own use
	u32 size;       // number of data bytes following this header (BE)
};

The one issue I have with this, is how to give these extra header value to the user of this library. qoi_read("file.qoi", &w, &h, &channels_in_file, &colorspace, want_channels) looks like an ugly API. So maybe that would rather be implemented as qoi_read_ex() and qoi_read() stays as it is. I'm still not sure if I want that extended header...

What's the opinion of the other library authors?

[meshula]

On color spaces... I'm one of those 'experts' the HN thread is complaining about :)

If the user is doing complex image operations in a color accurate space, they're going to be using, most likely OpenEXR, because the values are important, as is the colorimetric information, and there's a lot more information that needs to be stored beyond color space (as is pointed out in the HN thread).

The intent of QOI is fast compress/decompress of data, obviously in a real time context.

The data QOI is going to be used with is therefore going to be either linear or SRGB. Drawing a line on the sand on those two seems like a clear, useful, choice.

There's a rub though. It's normal to store linear alpha with sRGB data. Also, it's common to store linear data in color channels, for example, in a normal map or other material input such as "metalness" in a typical PBR set up.

I propose that it makes sense to simply make the rule that individual channels are either linear-and-user-interpreted, or sRGB-with-gamma, and have the format include a byte with a bitmask indicating which channel is which.

I also propose that a bit of 0 would mean gamma, and 1 linear, and ordered such that the A channel lands in the LSB. A mask of 0 therefore might mean all gamma, and a mask of 1 would mean sRGB and linear alpha, regardless of the number of channels. That would make the two most common combinations result in a byte of zero and one, for any number of channels with alpha. The conciseness of only needing to care about zero or one in general appeals to me.

[pfusik]

Color differences (QOI_DIFF_*) should be stored as two's-complement.

👍

Also my three cents:

• Make width and height 32-bit.
• Make it clear if the diffs wrap or not. Currently the decoder wraps, but the encoder doesn't take advantage of it.
• There are three different code points allocated to "same pixel as last": index of last pixel, RLE 1 and diff24 with all flags clear.

[pfusik]

u32 size; // number of data bytes following this header (BE)

What's the use of this? It requires the encoder to either seek the file, buffer the whole output or do a first pass just to compute this number.

[aldanor]

u32 size; // number of data bytes following this header (BE)

What's the use of this? It requires the encoder to either seek the file, buffer the whole output or do a first pass just to compute this number.

Yea, I had the same question. This requires the writer to support seeking (which would yield problems with compression encoders), or you have to encode everything into a buffer first.

The only advantage, I guess, would be able to skip qoi-encoded images if there were many of them streamed in a row, or something like that.

[ikskuh]

I agree with the previous two writes that i find the size field in the header restricting. My implementation verifies that the stream is indeed not more than size bytes long. The size field also allows skipping QOI images in a stream without decoding.

It is my opinion that the channels header value should be purely informative.

I agree with this. I think additional fields like color space and such should also be purely informative, as otherwise the decode might need to perform color space conversion. I would say that color space will only ever affect RGB, but QOI will always use linear alpha.

I also agree with 1) and 2). We should not support premultiplied alpha, as it makes things more complex. I can also live with the current offset method for the signed deltas.

One question i had for the file format was: What is the purpose of the four padding bytes at the end of the file in the original implementation? 🤔

[phoboslab]

Make width and height 32-bit.

What's your reasoning for this? Maybe I'm a bit naive, but a 64k x 64k image seems plenty large to me. The 12bit width/height in MPEG1 still holds up 30 years later (admittedly barely).

Make it clear if the diffs wrap or not. Currently the decoder wraps, but the encoder doesn't take advantage of it.

Uh, interesting! Didn't even think about it. I'll check if it makes a significant difference in compression. My hunch is that it does not - and the added complexity is not worth it.

There are three different code points allocated to "same pixel as last": index of last pixel, RLE 1 and diff24 with all flags clear.

True. I guess QOI_RUN_8 with 1 could be omitted and be always encoded as QOI_INDEX. QOI_RUN_8 could then be 2..33, but we don't gain much here. Omitting QOI_DIFF_24 with all 0 differences is difficult. I don't think this is an issue.

What's the use of u32 size?

Good question! I was thinking of this as additional way to verify if we have a valid header. Streaming QOI images would also benefit from this. An alternative would be a special QOI_IMAGE_END code.

Case in point: I've had very frustrating experiences with MPEG1 not having any field of the frame size or an indicator for a frame end, resulting in one extra frame of latency - you have to wait until the next frame arrives until you can be sure you have enough data to decode the current one.

MPEG 1 was conceived in a way where you could encode data and spit it out to the wire immediately. Same for receiving: as soon as you get any bits from the wire you can theoretically start decoding. Yet, none(?) of the (software) decoders take advantage of it. ffmpeg and libmpeg2 buffers data for a whole frame before they start decoding. It's non-trivial to have a streaming decoder.

I agree with the previous two writes that i find the size field in the header restricting.

Can you clarify what you mean by "restricting"?

What is the purpose of the four padding bytes at the end of the file

Since the longest chunk we can have is 5 bytes (QOI_COLOR with RGBA set), having an extra 4 bytes that we can ignore at the end means we only have to check once per loop iteration if didn't run out of data. Without these extra 4 bytes, we would need to check for every decoded chunk separately. E.g.:

else if ((b1 & QOI_MASK_3) == QOI_RUN_16) {
	// We need an extra byte here. Check if we have enough data
	if (p >= chunks_len) {
		free(pixels);
		return NULL;
	}
	int b2 = bytes[p++];
	run = (((b1 & 0x1f) << 8) | (b2)) + 32;
}
...
else if ((b1 & QOI_MASK_4) == QOI_COLOR) {
	// Calculate how many extra bytes we need
	int bytes_needed = 
		((b1 >> 4) & 1) +
		((b1 >> 2) & 1) +
		((b1 >> 1) & 1) +
		((b1 >> 0) & 1);
	// Check if we have enough data
	if (p + bytes_needed > chunks_len) {
		free(pixels);
		return NULL;
	}
	if (b1 & 8) { px.rgba.r = bytes[p++]; }
	if (b1 & 4) { px.rgba.g = bytes[p++]; }
	if (b1 & 2) { px.rgba.b = bytes[p++]; }
	if (b1 & 1) { px.rgba.a = bytes[p++]; }
}

In contrast, the 4 bytes padding seemed like a nicer solution to guard against malicious input.

[ikskuh]

Make it clear if the diffs wrap or not. Currently the decoder wraps, but the encoder doesn't take advantage of it.

Uh, interesting! Didn't even think about it. I'll check if it makes a significant difference in compression. My hunch is that it does not - and the added complexity is not worth it.

It's a significant difference in the decoder to check if the overflow/wraparound would happen and error out because if format violation or just let the wraparound happen, and have improved encoding space (as hard on/off transitions can be encoded in a single byte instead of a QOI_COLOR encoding)

Case in point: I've had very frustrating experiences with MPEG1 not having any field of the frame size or an indicator for a frame end, resulting in one extra frame of latency - you have to wait until the next frame arrives until you can be sure you have enough data to decode the current one.

QOI always encodes all pixels, so you know the end of frame is reached when you have decoded exactly width * height pixels. It doesn't allow jumping forward in a stream of QOI images, but omitting it allows encoding a QOI image directly into a socket compared to encoding it into memory, and then sending the full thing. Imho, it's better to omit the size field, as decoding QOI doesn't cost much time, especially if you only read the bytes.

True. I guess QOI_RUN_8 with 1 could be omitted and be always encoded as QOI_INDEX. QOI_RUN_8 could then be 2..33, but we don't gain much here. Omitting QOI_DIFF_24 with all 0 differences is difficult. I don't think this is an issue.

Agreed. Encoding a run as 2…33 would make pictures also a tad smaller. I think this is worth the improvement as there isn't any difference in the decoder, and the encoder only gets slightly harder by introducing a single branch that checks if run-lengh is 1 and emit a QOI_INDEX instead of a QOI_RUN8

In contrast, the 4 bytes padding seemed like a nicer solution to guard against malicious input.

Ah. My implementation checks for the overrun anways, so i was wondering why it's there. Also note that malicious input doesn't have these 4 "safety" bytes on purpose, so we cannot rely on them being there.

[pfusik]

What's your reasoning for this? Maybe I'm a bit naive, but a 64k x 64k image seems plenty large to me.

1. I remember very well when 320x200 was called "hires". With 1bpp. Now I'm writing this on a 4k monitor.
2. Not all images fit on screen, e.g. satellite photos. Phones with 108 Mpix cameras are readily available. That's 12k x 9k.
3. If speed is a selling point for this format, it should support large images.

I'll check if it makes a significant difference in compression. My hunch is that it does not - and the added complexity is not worth it.

There's not much complexity here. Truncate the deltas in the encoder to 8 bits and document it.
Rejecting overflows in the decoder would make things complex.

[phoboslab]

It's a significant difference in the decoder to check if the overflow/wraparound would happen (...)

Right. That makes sense! I see now that allowing for wrapping is the better choice.

Also note that malicious input doesn't have these 4 "safety" bytes on purpose, so we cannot rely on them being there.

Doesn't matter. qoi_decode() get's the full buffer size, including those 4 bytes. It just stops the decode 4 bytes early. A malicious file could specify a data size of 1 and then start a QOI_COLOR with RGBA, causing us to read 4 bytes over the buffer end without this padding.

[pfusik]

two's-complement

To clarify: you want to keep the biases encoding and just move the range by one?
Because two's-complement normally means that e.g. zero is stored as zero and the high bit is the sign.

[phoboslab]

To clarify: you want to keep the biases encoding and just move the range by one?

Sorry, yes. I just wanted to shift the range by one to be consistent with the range of a two's complement int.

[nektro]

Make width and height 32-bit.

I propose having a u8 that specifies the bit size of the width and height values. this would allow small images to take up a few fewer bytes, and super large images possible.