Possible Signed Overflow for Luma Chunks

[Xaldew]

Hello,

I've spent a bit of time implementing my own version of the QOI encode/decoder
using Rust. The intent was that the output would binary compatible with that of
the reference decoder. During testing however, I did notice a small discrepancy
between in (at least) one of the testfiles (qoi_test_images/testcard.qoi).

After some debugging, I noticed that I handled the Diff/Luma chunks incorrectly.
After fixing that though, Rust noticed that the expression to compute the Luma
differences can actually overflow:

signed char vr = px.rgba.r - px_prev.rgba.r;
signed char vg = px.rgba.g - px_prev.rgba.g;
signed char vb = px.rgba.b - px_prev.rgba.b;

printf("Pixel=%d\n", px_pos / 4);
printf("dr=%d, dg=%d, db=%d\n", vr, vg, vb);
signed char vg_r = vr - vg;
signed char vg_b = vb - vg;

For the testfile above, this yields the output:

Pixel=6168
dr=72, dg=-105, db=-127

Which really should overflow the vr - vg expression. Then again, maybe I'm
missing some obscure integer promotion rule? I even tried adding sanitizers to
the QOI build files when generating this:

CC ?= clang
CFLAGS_BENCH ?= -std=gnu99 -g3 -fsanitize=signed-integer-overflow $(shell pkg-config --cflags stb)
LFLAGS_BENCH ?= -lpng
CFLAGS_CONV ?= -std=c99 -g3 -fsanitize=signed-integer-overflow $(shell pkg-config --cflags stb)

But they didn't trigger on this, which makes me unsure whether it is "really" a
bug. Either way, given that signed overflow is typically regarded as undefined
behavior according to the C/C++ standards, I think that this should be changed,
or at least documented with a mild warning above the statements.

[phoboslab]

According to this SO answer the behavior is not "undefined" but "implementation defined". I guess the signed-integer-overflow sanitizer doesn't trigger, because there's indeed a promotion to int happening.

Also, it is my understanding that the reason that signed integer overflow is undefined is that 50 years ago there existed some CPUs that didn't use twos-complement representation. Interestingly there is a proposal to abandon anything but twos-complement representation in C.

So I believe this is a non-issue. If you can find any platform where qoi.h does compile but signed integer overflow does not wrap (or more specifically: the demotion of int to char does not do the right thing), I may reconsider :)

Edit: wait, sorry, I think I totally misunderstood the actual issue. For the encoder to produce a QOI_DIFF with an invalid vg_r or vg_b, vg musst be small enough to fit into 6 bits and vr big enough to overflow and result in a value that fits into 4 bits. This can never happen. So the result of these calculations may be wrong, but it doesn't matter because it will not fit into a QOI_DIFF anyway.

I agree that this probably requires some documentation, though.

[Xaldew]

I could be wrong but that SO answer relies on a different behaviour: The literal 1 is defined to be of int type, thus signed char + int will type-promote the signed char to int, thus avoiding this particular issue.

I did actually double check the standard (C99 draft in this case), but my reading was mostly inconclusive:

According to 6.3.1.3: Type promotion outside the range of the target type is implementation defined. E.g., signed char a = 200 is implementation defined, but this doesn't apply in this case.

Chapter 3.4.3 explicitly mentions that signed integer overflow is undefined.

Chapter 5.1.2.3 Actually shows a similar example at item 10, example 2:

char c1, c2;
/* ... */
c1 = c1 + c2;

With the quote:

the ‘‘integer promotions’’ require that the abstract machine promote the value of each variable to int size and then add the two ints and truncate the sum. Provided the addition of two chars can be done without overflow, or with overflow wrapping silently to produce the correct result, the actual execution need only produce the same result, possibly omitting the promotions.

However, it is worth noting that the signedness of char is implementation defined, making this example inconclusive.

Finally, it seems that some clever standards lawyering is actually happening according to this SO answer. So, if I'm reading this correctly, "small integers" are essentially promoted to int before any computations, thus avoiding the overflows.

Sorry, I guess this became a bit long winded. Frankly, I actually agree with you that we would all be better of if that proposal would be accepted and all of this type promotion nonsense went away.

That said however, would you mind if I added a pull request adding a comment above these expressions with something along the lines // Note that the below expressions rely type promotion to ints.? I would argue that it is a good idea to give people porting the code to other languages (such as Rust in my case) a fair warning that some (arguably) complex rules are being used, especially since it supposed to be a reference implementation :)

[phoboslab]

Very interesting. Thanks for looking into the C standard!

Pardon my ignorance and bikeshedding but:

Note that the below expressions rely type promotion to ints

does it, though? What's the alternative in signed char vg_r = vr - vg? If a signed char would saturate (instead of wrapping around), or if we'd do these calculations as int – the result would always be same: vg_r wouldn't fit in a QOI_LUMA.

[Xaldew]

Hmm, your right, upon re-reading the SO answer above, I guess it's more of "may rely on type promotion to int". I guess one compelling alternative would thus be to make the promotion explicit in the code, e.g.:

signed char vg_r = (int)vr - (int)vg;
signed char vg_b = (int)vb - (int)vg;

This doesn't change the output (for most platforms), but does make the type promotions intent explicit.

I wasn't actually considering alternatives though, to be absolutely honest, but that's obviously something to think of. My first implementation was actually using ints (or i32 in Rust), and it worked just fine, it was simply doing a few different encoding decisions compared with the reference. Code and first differing chunk samples below (same testfile):

int vr = px.rgba.r - px_prev.rgba.r;
int vg = px.rgba.g - px_prev.rgba.g;
int vb = px.rgba.b - px_prev.rgba.b;

int vg_r = vr - vg;
int vg_b = vb - vg;

Original:

Encode: Diff { dr: 1, dg: 1, db: 1 }
Encode: Run { run: 6 }
Encode: Diff { dr: 3, dg: 3, db: 3 }
Encode: Run { run: 14 }

Using ints:

Encode: Rgb { r: 255, g: 255, b: 255 }
Encode: Run { run: 6 }
Encode: Rgb { r: 0, g: 0, b: 0 }
Encode: Run { run: 14 }

(This output is all from qoi.h with a few printfs write out the chunks)

Looking at these samples, it seems like using ints will consistently miss the Diff { 3, 3, 3} chunk, so I'm not sure that's a good alternative.

Saturation arithmetic could be interesting, but it's slightly beyond me to test that quickly right now at least. That said, I personally like this alternative better (for both Luma and Diff chunks actually), since I personally thinks it's a bit more "realistic" to look at values close together than wrapping all the way from white to black or vice-versa, even if that is pretty common for synthetic files.

[matu3ba]

Starting with https://en.cppreference.com/w/c/23 integers are represented as twos complement.

Saturation arithmetic could be interesting

1. C23 has <stdckdint.h>. Before that one was forced to use compiler builtins. Usage https://stackoverflow.com/a/20956705.
2. Newer microprocessor archs have dedicated routines for branchfree wrapping and saturation operations.
3. Bear in mind that without (dedicated) hardware support (microcontrollers)

• with hw support for wraparound ops and no saturation ops, one needs a branch
• without hw support for both wraparound and saturation ops one of the following is the case
  • multiplication becomes expensive with a div being needed for the overflow check
  • double register size (bitlen of int1 + bitlen of int2) needed for the overflow check
  • one would need to do register spills for the overflow checks

I suspect (without testing) these should be catched by -Wconversion, which might be off for C code due to old code relying heavy on implicit integer conversions. Personally I do test my toy code with clang -std=c99 -Werror -Weverything -Wno-unsafe-buffer-usage -Wno-declaration-after-statement -Wno-switch-default .\templates\common.c, which also catches stuff like missing static.