Overflow bei add unsigned char

[Alexander S. (alesi)]

Hallo,

ich habe gerade wieder etwas gelernt. Im Nachhinein habe ich eine 
Vermutung warum das Ergebnis bei a + b anders ist als bei c.

/* add_char_overflow.c  */

#include <limits.h>
#include <stdio.h>

int
main(void)
{
    unsigned char a, b, c;

    for (a = 60; a < UCHAR_MAX - 40; a += 20)
        for (b = 30; b < UCHAR_MAX - 60; b += 30) {
            c = a + b;
            printf("%3d %3d %3d %3d\n", a, b, a+b, c);
        }

    return 0;
}

gcc -Wall -pedantic -ansi -o add_char_overflow add_char_overflow.c

 60  30  90  90
 60  60 120 120
 60  90 150 150
 60 120 180 180
 60 150 210 210
 60 180 240 240
 80  30 110 110
 80  60 140 140
 80  90 170 170
 80 120 200 200
 80 150 230 230
 80 180 260   4
100  30 130 130
100  60 160 160
100  90 190 190
100 120 220 220
100 150 250 250
100 180 280  24
120  30 150 150
120  60 180 180
120  90 210 210
120 120 240 240
120 150 270  14
120 180 300  44
140  30 170 170
140  60 200 200
140  90 230 230
140 120 260   4
140 150 290  34
140 180 320  64
160  30 190 190
160  60 220 220
160  90 250 250
160 120 280  24
160 150 310  54
160 180 340  84
180  30 210 210
180  60 240 240
180  90 270  14
180 120 300  44
180 150 330  74
180 180 360 104
200  30 230 230
200  60 260   4
200  90 290  34
200 120 320  64
200 150 350  94
200 180 380 124

[(prx) A. K. (prx)]

Sollte in jedem C Buch stehen.

[Alexander S. (alesi)]

Klar ist die vierte Spalte (c). Erst nach kurzem Nachdenken ist mir auch 
die dritte Spalte (a + b) klar.

/* add_char_overflow.c  */

#include <limits.h>
#include <stdio.h>

int
main(void)
{
    unsigned char a, b, c;

    for (a = 60; a < UCHAR_MAX - 40; a += 20)
        for (b = 30; b < UCHAR_MAX - 60; b += 30) {
            c = a + b;
            printf("%3d %3d %3d %3d %s\n", a, b, a+b, c, (b < UCHAR_MAX - a) ? "Ok" : "Overflow");
        }

    return 0;
}

 60  30  90  90 Ok
 60  60 120 120 Ok
 60  90 150 150 Ok
 60 120 180 180 Ok
 60 150 210 210 Ok
 60 180 240 240 Ok
 80  30 110 110 Ok
 80  60 140 140 Ok
 80  90 170 170 Ok
 80 120 200 200 Ok
 80 150 230 230 Ok
 80 180 260   4 Overflow
100  30 130 130 Ok
100  60 160 160 Ok
100  90 190 190 Ok
100 120 220 220 Ok
100 150 250 250 Ok
100 180 280  24 Overflow
120  30 150 150 Ok
120  60 180 180 Ok
120  90 210 210 Ok
120 120 240 240 Ok
120 150 270  14 Overflow
120 180 300  44 Overflow
140  30 170 170 Ok
140  60 200 200 Ok
140  90 230 230 Ok
140 120 260   4 Overflow
140 150 290  34 Overflow
140 180 320  64 Overflow
160  30 190 190 Ok
160  60 220 220 Ok
160  90 250 250 Ok
160 120 280  24 Overflow
160 150 310  54 Overflow
160 180 340  84 Overflow
180  30 210 210 Ok
180  60 240 240 Ok
180  90 270  14 Overflow
180 120 300  44 Overflow
180 150 330  74 Overflow
180 180 360 104 Overflow
200  30 230 230 Ok
200  60 260   4 Overflow
200  90 290  34 Overflow
200 120 320  64 Overflow
200 150 350  94 Overflow
200 180 380 124 Overflow

[Rolf M. (rmagnus)]

Alexander S. schrieb:
> gcc -Wall -pedantic -ansi -o add_char_overflow add_char_overflow.c

Auch wenn's jetzt in dem Fall keine Rolle spielt, solltest du mal deine 
Optionen updaten. -ansi führt dazu, dass der Compiler auf das 35 Jahre 
alte ANSI-C zurückschaltet.

[900ss (900ss)]

Rolf M. schrieb:
> -ansi führt dazu, dass der Compiler auf das 35 Jahre alte ANSI-C
> zurückschaltet.

Wo ist da der Vorteil? Die Erklärung hast du offen gelassen.

[Bauform B. (bauformb)]

900ss schrieb:
> Wo ist da der Vorteil?

Der Compiler würde auch meine Programme mögen ;) mit -ansi geht 
garnichts:
- error: C++ style comments are not allowed in ISO C90
- error: 'for' loop initial declarations are only allowed in C99 or C11 
mode
- warning: ISO C does not support '__FUNCTION__' predefined identifier
- warning: anonymous variadic macros were introduced in C99
- warning: comma at end of enumerator list
usw. Demnächst gibt's noch Binary Constants und falltgrough und noreturn 
und und

C11: https://open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

C23: https://open-std.org/jtc1/sc22/wg14/www/docs/n3096.pdf

[Rolf M. (rmagnus)]

900ss schrieb:
> Rolf M. schrieb:
>> -ansi führt dazu, dass der Compiler auf das 35 Jahre alte ANSI-C
>> zurückschaltet.
>
> Wo ist da der Vorteil? Die Erklärung hast du offen gelassen.

Na dass eben alle Features, die der Sprache in den letzten 35 Jahren 
hinzugefügt wurden, genutzt werden können. "Bauform" hat ja schon ein 
paar davon gelistet. Wobei gcc manche auch mit -ansi fälschlicherweise 
durchlässt, wie z.B. bool oder stdint.h, die es in C89 eigentlich nicht 
gibt.

[Peter D. (peda)]

Alexander S. schrieb:
> Im Nachhinein habe ich eine
> Vermutung warum das Ergebnis bei a + b anders ist als bei c.

Da braucht man nichts zu vermuten.
Alle Berechnungen erfolgen immer so, als wären sie mindestens int. Und 
auch printf(%d) erwartet int, d.h. bei Bedarf erfolgt eine Erweiterung 
auf int.
Allein die Zuweisung auf c schneidet das höherwertige Byte wieder ab.

[900ss (900ss)]

Rolf M. schrieb:
> 900ss schrieb:
>> Rolf M. schrieb:
>>> -ansi führt dazu, dass der Compiler auf das 35 Jahre alte ANSI-C
>>> zurückschaltet.
>>
>> Wo ist da der Vorteil? Die Erklärung hast du offen gelassen.
>
> Na dass eben alle Features, die der Sprache in den letzten 35 Jahren
> hinzugefügt wurden, genutzt werden können. "Bauform" hat ja schon ein
> paar davon gelistet. Wobei gcc manche auch mit -ansi fälschlicherweise
> durchlässt, wie z.B. bool oder stdint.h, die es in C89 eigentlich nicht
> gibt.

Ach shit, ich hatte das genau anders verstanden. Ich hatte es erst so 
verstanden dass er -ansi nutzen soll und kratzte mich am Kopf und fragte 
mich... äh? Dann geht ja "nichts" mehr :)
Aber eben habe ich gesehen, dass du eigentlich wolltest, dass er -ansi 
aus seinen angegebenen Optionen streicht. Ich hatte die Option irgendwie 
übersehen.

Bauform hat ja schöne Beispiele gebracht.

Ich nutze mal eine IDE im Job, die -ansi default setze wenn man ein 
Projekt erzeugte. Das war das erste was ich gestrichen habe.

[Alexander S. (alesi)]

Hallo,

nur der Vollständigkeit halber hier die Version mit 'unsigned int' wo 
für a+b und c immer das gleiche herauskommt.

/* overflow_uint.c */

#include <stdio.h>
#include <limits.h>

int
main(void)
{
    unsigned int a, b, c;

    printf("UINT_MAX = %u\n", UINT_MAX);

    for (a = UINT_MAX / 8; a < UINT_MAX - UINT_MAX / 4; a += UINT_MAX / 8)
        for (b = UINT_MAX / 8; b < UINT_MAX - UINT_MAX / 4; b += UINT_MAX / 8) {
            c = a + b;
            printf("%u %u %u %u %s\n", a, b, a + b, c, (b <= UINT_MAX - a) ? "Ok" : "Overflow");
        }

    a = UINT_MAX / 2;
    if (UINT_MAX % 2)
        b = a + 1;
    else
        b = a;

    c = a + b;
    printf("%u %u %u %u %s\n", a, b, a + b, c, (b <= UINT_MAX - a) ? "Ok" : "Overflow");

    return 0;
}

$ gcc -Wall -pedantic -ansi -o overflow_uint overflow_uint.c

UINT_MAX = 4294967295
536870911 536870911 1073741822 1073741822 Ok
536870911 1073741822 1610612733 1610612733 Ok
536870911 1610612733 2147483644 2147483644 Ok
536870911 2147483644 2684354555 2684354555 Ok
536870911 2684354555 3221225466 3221225466 Ok
536870911 3221225466 3758096377 3758096377 Ok
1073741822 536870911 1610612733 1610612733 Ok
1073741822 1073741822 2147483644 2147483644 Ok
1073741822 1610612733 2684354555 2684354555 Ok
1073741822 2147483644 3221225466 3221225466 Ok
1073741822 2684354555 3758096377 3758096377 Ok
1073741822 3221225466 4294967288 4294967288 Ok
1610612733 536870911 2147483644 2147483644 Ok
1610612733 1073741822 2684354555 2684354555 Ok
1610612733 1610612733 3221225466 3221225466 Ok
1610612733 2147483644 3758096377 3758096377 Ok
1610612733 2684354555 4294967288 4294967288 Ok
1610612733 3221225466 536870903 536870903 Overflow
2147483644 536870911 2684354555 2684354555 Ok
2147483644 1073741822 3221225466 3221225466 Ok
2147483644 1610612733 3758096377 3758096377 Ok
2147483644 2147483644 4294967288 4294967288 Ok
2147483644 2684354555 536870903 536870903 Overflow
2147483644 3221225466 1073741814 1073741814 Overflow
2684354555 536870911 3221225466 3221225466 Ok
2684354555 1073741822 3758096377 3758096377 Ok
2684354555 1610612733 4294967288 4294967288 Ok
2684354555 2147483644 536870903 536870903 Overflow
2684354555 2684354555 1073741814 1073741814 Overflow
2684354555 3221225466 1610612725 1610612725 Overflow
3221225466 536870911 3758096377 3758096377 Ok
3221225466 1073741822 4294967288 4294967288 Ok
3221225466 1610612733 536870903 536870903 Overflow
3221225466 2147483644 1073741814 1073741814 Overflow
3221225466 2684354555 1610612725 1610612725 Overflow
3221225466 3221225466 2147483636 2147483636 Overflow
2147483647 2147483648 4294967295 4294967295 Ok

[Sebastian W. (wangnick)]

Alexander S. schrieb:
> nur der Vollständigkeit halber

Da fehlt dazwischen aber noch die Version mit uint16_t.

LG, Sebastian

[Alexander S. (alesi)]

Die Version mit uint16_t und 'unsigned long' darf jeder der möchte als 
Hausaufgabe machen. :-)

[Alexander S. (alesi)]

Hallo,

einen habe ich noch. Nach einigen Antworten zuvor, ist mir aber klar, 
dass das Ergebnis allen klar ist.

#include <stdio.h>
#include <limits.h>

int
main(int argc, char *argv[])
{
    signed char c;

    c = SCHAR_MIN;
    printf("%d %d\n", c, c - 1);
    c = SCHAR_MIN;
    printf("%d %d\n", c, c - (signed char) 1);
    c = SCHAR_MIN;
    printf("%d ", c);
    --c;
    printf("%d\n", c);


    c = SCHAR_MAX;
    printf("%d %d\n", c, c + 1);
    c = SCHAR_MAX;
    printf("%d %d\n", c, c + (signed char) 1);
    c = SCHAR_MAX;
    printf("%d ", c);
    ++c;
    printf("%d\n", c);

    return 0;
}

$ gcc -Wall -pedantic -ansi -o overflow_signed_char overflow_signed_char.c
$ ./overflow_signed_char 
-128 -129
-128 -129
-128 127
127 128
127 128
127 -128

Mir ist das Verhalten in so weit klar, als das bei C das Verhalten bei 
underflow und overflow von signed char oder signed int, im Gegensatz zu 
unsigned char oder unsigned int, nicht definiert ist.

[Rolf M. (rmagnus)]

Alexander S. schrieb:
> Mir ist das Verhalten in so weit klar, als das bei C das Verhalten bei
> underflow und overflow von signed char oder signed int, im Gegensatz zu
> unsigned char oder unsigned int, nicht definiert ist.

Bis auf das
> --c;
und das
> ++c;

ist alles wohldefiniert.

[Alexander S. (alesi)]

Rolf M. schrieb:
> ist alles wohldefiniert.

Nicht für signed int.

https://en.wikipedia.org/wiki/Integer_overflow
Tabelle "Integer overflow handling in various programming languages"
C/C++: Signed integer, undefined behavior

http://cs.yale.edu/homes/aspnes/classes/223/notes.html#overflow-and-the-c-standards

P.S. Im Standard selber habe ich nicht nachgeschaut.

[Rolf M. (rmagnus)]

Alexander S. schrieb:
> Rolf M. schrieb:
>> ist alles wohldefiniert.
>
> Nicht für signed int.

Richtig, aber der Wertebereich von signed int ist auf jeden Fall groß 
genug, um den von dir verwendeten Zahlenbereich abzudecken, daher gibt 
es hier außer bei ++ und -- kein Problem.
Denn wie oben schon erwähnt wurde:

Peter D. schrieb:
> Alle Berechnungen erfolgen immer so, als wären sie mindestens int.

Das nennt sich "integer promotion". Das heißt, dass hier:

Alexander S. schrieb:
> c - 1

c erst mal auf int erweitert wird und dann die Berechnung mit dem Typ 
durchgeführt wird. Das Ergebnis ist natürlich dann auch vom Typ int. 
Somit kann da nix überlaufen, weil der Wertebereich von int groß genug 
ist, um das Ergebnis aufzunehmen.

Alexander S. schrieb:
> c - (signed char) 1

Hier ist es das gleiche. Dein Cast ändert daran nichts. Es wird durch 
ihn die 1 lediglich erst nach signed char konvertiert, bevor sie dann 
sofort wieder (wie die Variable c) nach int konvertiert wird. Die 
Berechnung erfolgt dann auch wieder mit Typ int.

Lediglich bei --c und ++c gibt  es ein Problem, weil da das Ergebnis ja 
wieder nach c zurückgeschrieben wird, das aber nicht groß genug dafür 
ist.

[Alexander S. (alesi)]

Dann kannst Du sicher auch erklären, warum

signed char c;

c = c + 1;

und

signed char c;

++c;

unterschiedliche Ergebnisse liefern.

[Rolf M. (rmagnus)]

Weil c in beiden Fällen uninitialisiert ist und dein Code dadurch 
undefiniertes Verhalten auslöst. Aber ich vermute, du wolltest hier c 
mit SCHAR_MAX initialisieren. Dann hast du aber trotzdem undefiniertes 
Verhalten, weil eben der Wertebereich von c nicht mehr ausreicht.

Laut C-Standard ist ++c äquivalent zu c+=1 ("The expression ++E is 
equivalent to (E+=1), where the value 1 is of the appropriate type.")
und das wiederum ist (mit der Ausnahme dass c nur einmal evaluiert wird) 
äquivalent zu c = c + 1. ("A compound assignment of the form E1 op= E2 
is equivalent to the simple assignment expression E1 = E1 op (E2), 
except that the lvalue E1 is evaluated only once, and with respect to an 
indeterminately sequenced function call, the operation of a compound 
assignment is a single evaluation")

Da das Verhalten in diesem Fall undefiniert ist, muss das Ergebnis aber 
nicht gleich sein.

[Alexander S. (alesi)]

Hallo Rolf,

der entscheidende Punkt ist wohl, dass man zwischen

signed char c;
c = SCHAR_MAX;
printf("%d", c + 1);

und

signed char c;
c = SCHAR_MAX;
c = c + 1;
printf("%d", c);

unterscheiden muss. Im ersten Fall ist der Wertebereich int und im 
zweiten Fall signed char.

#include <stdio.h>
#include <limits.h>

int
main(int argc, char *argv[])
{
    signed char c;

    c = SCHAR_MIN;
    printf("%d ", c);
    c = c - (signed char) 1;
    printf("%d\n", c);
    c = SCHAR_MIN;
    printf("%d ", c);
    --c;
    printf("%d\n", c);


    c = SCHAR_MAX;
    printf("%d ", c);
    c = c + (signed char) 1;
    printf("%d\n", c);
    c = SCHAR_MAX;
    printf("%d ", c);
    ++c;
    printf("%d\n", c);

    return 0;
}

$ ./overflow_signed_char 
-128 127
-128 127
127 -128
127 -128

[Rolf M. (rmagnus)]

Alexander S. schrieb:
> der entscheidende Punkt ist wohl, dass man zwischensigned char c;
> c = SCHAR_MAX;
> printf("%d", c + 1);
>
> undsigned char c;
> c = SCHAR_MAX;
> c = c + 1;
> printf("%d", c);
>
> unterscheiden muss. Im ersten Fall ist der Wertebereich int und im
> zweiten Fall signed char.

Ja, weil du im zweiten Fall das Ergebnis nach c zurückschreibst, das vom 
Typ signed char ist, in den es aber nicht reinpasst. Im ersten Fall 
dagegen verarbeitest du das Ergebnis der Addition direkt als int weiter. 
Somit läuft da nichts über. Würdest du schreiben:

int d = c + 1:

dann wäre das Ergebnis das gleiche wie im ersten Fall.