Make pixel differences unbiased

[jmi2k]

HW implementations would benefit from it, as the circuitry needed to sign-extend is simpler than the one to account for biases. Context: https://github.com/phoboslab/qoi/issues/28#issuecomment-980627601

[dougallj]

Yeah, ARM64 probably would benefit too as it has a signed-bitfield extraction instruction (SBFX).

[nigeltao]

IIUC, for e.g. the DIFF_8 opcode that has 2-bit deltas, you're proposing to change the interpretation (from 'Old' to 'New'):

Bits  Old  New
00    -2   +0
01    -1   +1
10    +0   -2
11    +1   -1

[jmi2k]

Yeah, that's it!

[jmi2k]

Also, maybe relevant: https://stackoverflow.com/questions/5814072/sign-extend-a-nine-bit-number-in-c/17719010#17719010

[aldanor]

Another option would be to not leave the 8-bit space at all (https://github.com/phoboslab/qoi/issues/28#issuecomment-980547560), but then you would have to use wrapping adds/subs throughout, so technically it's a different encoding.

[jmi2k]

Another option would be to not leave the 8-bit space at all (phoboslab/qoi#28 (comment)), but then you would have to use wrapping adds/subs throughout, so technically it's a different encoding.

Didn't the final QOI spec explicitly mention that QOI_DIFF uses wrapping arithmetic? The encoder is free to do what you're mentioning, the decoder will decode both just fine.

Also, how does all of that relate to using two's complement in QOI_DIFF fields? AFAIK it should be irrelevant...

[aldanor]

Another option would be to not leave the 8-bit space at all (phoboslab/qoi#28 (comment)), but then you would have to use wrapping adds/subs throughout, so technically it's a different encoding.

Didn't the final QOI spec explicitly mention that QOI_DIFF uses wrapping arithmetic? The encoder is free to do what you're mentioning, the decoder will decode both just fine.

Also, how does all of that relate to using two's complement in QOI_DIFF fields? AFAIK it should be irrelevant...

Thanks - indeed, I must have missed that part.

Just tested the wrapping-ops encoder implementation on a few files out of the reference image set:

• Approximately 6-7% speedup using 8-bit wrapping ops when encoding and not going into 16-bit space.
• Either no difference in encoded files (kodak images), or barely any difference (on wikipedia.org screenshot, compression is 0.46 KB better out of 1.5 MB total).

With this, I don't understand why this hasn't been made the reference encoder implementation. Why allow multiple encoder implementations that don't yield bitwise-identical results, while one of them seems to be faster and compress the same or sometimes better?

(perhaps this might be a separate thread if anyone cares)

[jmi2k]

In these cases, I think it's useful to differentiate between a conforming string and a canonical string in the spec. There is nothing wrong with allowing multiple conforming strings for the same input (in fact, sometimes it's even desirable). Usually the encoder is made to produce canonical strings (so that they are reproducible and can be compared) but the decoder is made to accept conforming strings (so that it's more lenient). See Postel's law

[phoboslab]

I agree. As long as the file format is strictly followed, an encoder can make whatever tradeoffs it wants.

I tried to implement the wrapping diff in the C encoder (by just replacing int with char here) and it led to ~12% slower encoding. Not sure if I'm doing it wrong, or if Rust does this differently somehow.

For better compression an encoder could chose to check first if a QOI_COLOR would actually be smaller, even though the diffs would fit in a QOI_DIFF_24. If only alpha changes and rgb stay the same, the C encoder produces a QOI_DIFF_24 (3 bytes) when the QOI_COLOR would only be 2 bytes. Again, I decided for performance over the best possible compression.

A very fast "encoder" could chose to just spit out QOI_COLOR chunks and do nothing else. Imho that's totally fine.