c-faq.com - UB in Snippet?

[starcow]

Guten Nachmittag Zusammen :-)

Bestimmt dürfte einigen von euch die Seite c-faq.com bekannt sein.
Ich glaube Krishty hatte die irgendwann mal gepostet - eine 1:1 Kopie des Inhaltes, des gleichnamigen Buches - und dieses gilt - soviel ich mitbekommen habe - ja als "echtes Werk" und Klassiker (weshalb mich Zweifel zu meinen Schlussfolgerungen beschleichen).

Jedenfalls bin ich in Kapitel 16, Frage 7 auf ein Snippet gestossen, das - wie ich glaube - eigentlich UB sein müsste.
https://c-faq.com/strangeprob/ptralign.html

Code: Alles auswählen

	unsigned char *p = buf;

	s.c = *p++;

	s.i32 = (long)*p++ << 24;
	s.i32 |= (long)*p++ << 16;
	s.i32 |= (unsigned)(*p++ << 8);
	s.i32 |= *p++;

	s.i16 = *p++ << 8;
	s.i16 |= *p++;

Was mir einleuchtet:
Ohne den cast zu long würde der Bitshift-Operator ja zu int promoten (Ist das die "Ganzzahlerweiterung" zu deutsch?). Doch da dieser hier - in diesem Setting nur 16 Bit aufweist (wie der Autor ja sinnvollerweise auch anmerkt), würde das nicht ausreichen.

Was mir nicht einleuchtet:
Wenn jetzt aber der Wert unter dem zweiten unsigned char grösser als 127 wird, dann muss auch das höchstwertigste Bit in diesem char gesetzt sein. Folglich resultiert dann aber ein Überlauf beim Links-Shift um 24 Bit. (Der erste char, auf den p zeigt wird ja einfach s.c zugewiesen. Hier geht es folglich um den zweiten bis fünften char).
Müsste man da nicht zu unsigned long casten?
Fast der selbe Fehler war doch in der SDL, den Andrew Kelley kürzlich gefunden hatte (danke Krishty für die Erläuterung).

Wir hatten das Thema vor ein paar Wochen kurz im IRC besprochen und ich habe Steve Summit daraufhin angemailt.
Er hat mir jedoch bis heute nicht geantwortet - vielleicht weil wir etwas banales übersehen hatten?

[Krishty]

Ich würde zustimmen, dass das ein Fehler ist. Aber ich hab’s gerade durch Undefined Behavior Sanitizer gejagt und er schlägt nicht an. Schwierig :(

[starcow]

Also "Krishty" vs "UBSan" :-) Ich setze auf dich!

[Schrompf]

Gefährliches Halbwissen: seit C++20 oder so ist Left Shift auf Signed Integern definiertes Verhalten. Nur Right Shift ist immer noch UB, weil sie immer noch kein Zweierkomplement annehmen wollen. Demzufolge ist - falls die Operator Precedence hinhaut und der Cast wirklich vor dem Shift kommt - das eine valide Operation.

[Alexander Kornrumpf]

Das wirft aber, so es denn wirklich falsch ist oder vor 2020 war, jetzt schon die Frage auf, wie man denn in C korrekterweise einen vorzeichenbehafteten Typen aus einem Stream liest, no? Denn selbst wenn man das ganze bit-gefrickel in unsigned implementiert, wird man ja am Ende mindestens einmal casten müssen?!

[NytroX]

Muss man das eigentlich verstehen? Ich kann solchen Code grundsätzlich nicht nachvollziehen.
Macht man so einen Quatsch mit Absicht, um möglichst den Leser zu verwirren und subtile Fehler einzubauen, die jahrelang keiner bemerkt?
Einfach nur, weil man es kann?

[Krishty]

Das wirft aber, so es denn wirklich falsch ist oder vor 2020 war, jetzt schon die Frage auf, wie man denn in C korrekterweise einen vorzeichenbehafteten Typen aus einem Stream liest, no? Denn selbst wenn man das ganze bit-gefrickel in unsigned implementiert, wird man ja am Ende mindestens einmal casten müssen?!

Genau, aber der Cast unsigned zu signed ist AFAIK nie Undefined Behavior gewesen, sondern nur Implementation-Defined (und seit neuestem fest als Zweierkomplement definiert).

[Krishty]

Aus C++0x (weil ich gerade nichts Moderneres hier habe):

The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 × 2^E2, reduced modulo one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1×2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

Ist in unserem Beispiel E1 ein „unsigned type“? Es ist unsigned char, also schon. Aber erstmal hat jawohl die Promotion zu long stattgefunden, sonst ergäbe „reduced modulo one more than the maximum value representable in the result type“ schlicht Null.
Wir scheinen also „signed type and non-negative value“ zu erfüllen (long und z. B. 255), aber nicht „representable in the result type“, denn das Ergebnis würde ja zu einer negativen Zahl überlaufen (sehe ich auch hier im Debugger).

Kann jemand dot rufen? :D

[Alexander Kornrumpf]

FWIW das war auch meine Lesart.

[Krishty]

Es gab 2012 einen Request für diese Ergänzung:

...if E1 has a signed type and non-negative value, and E1 ⨯ 2E2 is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

Falls das angenommen wurde, wäre unser Problem gelöst: Man dürfte ein Bit in das Vorzeichen reinshiften, aber nicht darüber hinaus.

Wenn man jetzt bloß den C++-Standard einsehen könnte, ohne 250 € zu bezahlen …

[dot]

Müsste man da nicht zu unsigned long casten?

Ich würde mal sagen ja, das schaut mir auf jeden Fall nach UB aus. Bachte auch, dass das ja C ist und nicht C++20.

In C++ wäre das OK [expr.shift]/2 (seit C++20). In C aber nicht: https://open-std.org/JTC1/SC22/WG14/www/docs/n3096.pdf 6.5.7/3 (Seite 85).

Wenn man jetzt bloß den C++-Standard einsehen könnte, ohne 250 € zu bezahlen …

https://eel.is/c++draft, https://wg21.link/std20, https://en.cppreference.com/w/c/links, https://en.cppreference.com/w/cpp/links ;-)

[Krishty]

Fantastisch! Danke ❤️

[starcow]

Ich würde mal sagen ja, das schaut mir auf jeden Fall nach UB aus. Bachte auch, dass das ja C ist und nicht C++20.
In C++ wäre das OK [expr.shift]/2 (seit C++20). In C aber nicht: https://open-std.org/JTC1/SC22/WG14/www/docs/n3096.pdf 6.5.7/3 (Seite 85).

Danke dot!
Du meintest Punkt 4, oder?

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has
an unsigned type, the value of the result is E1 × 2^E2, wrapped around. If E1 has a signed type and
nonnegative value, and E1 × 2^E2 is representable in the result type, then that is the resulting value;
otherwise, the behavior is undefined.

Folglich definitv UB - weil "E1 × 2^E2 is representable in the result type" offensichtlich nicht zutrifft.

Das wirft aber, so es denn wirklich falsch ist oder vor 2020 war, jetzt schon die Frage auf, wie man denn in C korrekterweise einen vorzeichenbehafteten Typen aus einem Stream liest, no? Denn selbst wenn man das ganze bit-gefrickel in unsigned implementiert, wird man ja am Ende mindestens einmal casten müssen?!

Das hatte ich noch gar nicht realisiert! :-)
Hat denn jemand einen Vorschlag wie man es nun bewerkstelligen kann, so dass es auch wirklich standardkonform mit eindeutig definiertem Verhalten ist (sagen wir mal, nach C99 Standard)? Der cast nach unsigned int scheindet ja dann wohl aus, wenn dieser implementation-defined ist.

Müsste ich mit folgender Operation nicht ein sehr ähnliches Problem bekommen, da ja gewisserweise auch ein Überlauf stattfindet?

Code: Alles auswählen

	int i = 1;
	i |= -0x80000000;

Ich setzte das höchstwertige Bit bei einer zuvor positiven Zahl.

Ergänzend:

Code: Alles auswählen

	s.i32 |= (unsigned)(*p++ << 8);

Ich seh das erst jetzt, dass bei dieser Anweisung der Autor den Ausdruck absichtlich geklammert hat.
Nun erfolg ja tatsächlich eine promotion to signed int (16 Bit) - also das selbe Problem potentiell gleich nochmals (Overflow).
Und dann der cast nach unsigned int erst danach... Wozu? Dann ists ja zuspät.
Das hätte jetzt ohne Klammer deutlich mehr Sinn gemacht!

[dot]

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has
an unsigned type, the value of the result is E1 × 2^E2, wrapped around. If E1 has a signed type and
nonnegative value, and E1 × 2^E2 is representable in the result type, then that is the resulting value;
otherwise, the behavior is undefined.

Folglich definitv UB - weil "E1 × 2^E2 is representable in the result type" offensichtlich nicht zutrifft.

genau

[starcow]

Ich habe mir nochmals über eine Alternative Gedanken gemacht, die in jedem Fall eindeutig definiert sein sollte.

Code: Alles auswählen

	unsigned char array[] = {0xA0, 0xB1, 0xC2, 129};
	unsigned char* ptr = array;

	// Little Endian implementation

	int x = 0;
	x |= (int)*ptr++;
	x |= (int)*ptr++      *     0x100;
	x |= (int)*ptr++      *   0x10000;
	x |= (int)*(char*)ptr * 0x1000000;

Die Idee ist, dass man den Pointer zuerst in einen char-Pointer castet, sobald dieser auf das "heisse" Byte zu liegen kommt. So würde man dann auch wirklich eine negative Zahl auslesen, falls das höchstwertige Bit in diesem Byte gesetzt sein sollte.
Nun arbeitet man mit einer Multiplikation anstelle des Left-Shiftes (Bei Byte 2 und 3 könnte man nach wie vor auch den Left-Shift verwenden).

Die zwei Fragen, die sich jetzt stellen:
- Ist es überhaupt erlaubt, das höchstwertige Bit eines signed int mittels den Bitwise-Operatoren (&, ^, |) zu verändern?
- Wieviel Zeit verliert man mit der Multiplikation gegenüber dem Left-Shift?

Über einen cast von signed zu unsigned (und umgekehrt) wäre es wohl noch ein Stück weit besser nachvollziehbar (und möglicherweise schneller?). Die Frage ist halt, ob das dann auch wirklich weiterhin implementations-unabhängig bliebe?

[dot]

- Ist es überhaupt erlaubt, das höchstwertige Bit eines signed int mittels den Bitwise-Operatoren (&, ^, |) zu verändern?

Ich denke ja. Zwei Probleme, die ich in deinem Code da oben sehe: char muss nicht unbedingt signed sein und int muss nicht unbedingt 32-Bit breit sein, das könnte also überlaufen.

- Wieviel Zeit verliert man mit der Multiplikation gegenüber dem Left-Shift?

Keine. Jeder auch nur annähernd sinnvolle Compiler wird diese Multiplikationen über Shifts implementieren (e.g.: https://godbolt.org/z/cjW9qoeY6). Es ist generell nicht sinnvoll, manuell "zur Optimierung" Multiplikationen/Divisionen durch Shifts zu ersetzen oder vice versa. In den Situationen, wo das sowohl sinnvoll als auch korrekt wäre, macht der Compiler das sowieso. Und dann gibt es Situationen wo es nicht sinnvoll ist (Shift ist nicht unbedingt immer die bessere Wahl) und Situationen wo es nicht korrekt ist (Division von negativen Zahlen). Du erreichst damit bestenfalls also nichts und schlechtestenfalls ist dein Code damit sowohl langsamer als auch falsch… Am besten schreibt man einfach das hin, was man auch wirklich meint.

Leider scheint GCC den Pattern in deiner Implementierung nicht zu erkennen (imo ein Performancebug, solltest du evtl. reporten). Ich mache es in der Regel so:

Code: Alles auswählen

uint_fast32_t read_uint32_le(unsigned char* ptr) {
    return ((uint_fast32_t)ptr[0] <<  0) |
           ((uint_fast32_t)ptr[1] <<  8) |
           ((uint_fast32_t)ptr[2] << 16) |
           ((uint_fast32_t)ptr[3] << 24);
}

int_fast32_t read_int32_le(unsigned char* ptr) {
    return (int_fast32_t)read_uint32_le(ptr);
}

https://godbolt.org/z/1G4MKTo4M

[starcow]

Alles klar, danke dir dot! :daumen:
Wie ich sehe, machst du das per cast. Im ISO Standard (den du gepostet hattest) müsste das ja eigentlich ebenfalls zu finden sein - also ob der cast von unsigned nach signed nun implementation-defined ist oder (hoffentlich) "uniform-defined" (wenn man das so nennen kann).
Ich werde mal versuchen die entsprechende Seite zu finden.

Btw:
Würde dich denn ein implementation-defined nicht davon abhalten, dass mittels cast zu machen? Das hiesse doch dann eigentlich, dass zwar das Verhalten definiert ist, jedoch von Compiler zu Compiler variieren kann.

[dot]

Wie ich sehe, machst du das per cast. Im ISO Standard (den du gepostet hattest) müsste das ja eigentlich ebenfalls zu finden sein - also ob der cast von unsigned nach signed nun implementation-defined ist oder (hoffentlich) "uniform-defined" (wenn man das so nennen kann).

Ich vergesse immer, dass das in C ja aus irgendeinem Grund leider immer noch implementation-defined ist. Frag mich nicht wieso, eigentlich sollte C23 ja endlich auch Two's Complement übernehmen. Vielleicht wurde das nur übersehen… Either way, in der Praxis wirst du es ziemlich schwer finden, einen Compiler zu finden, wo es nicht so funktioniert. Insbesondere wenn man bedenkt, dass es ja kaum noch sowas wie einen wirklichen C Compiler gibt. Die üblichen "C Compiler" (gcc, clang, msvc) sind ja alle effektiv einfach nur C++ Compiler mit einem C Modus. Und in C++ ist das seit C++20 garantiert…

Btw:
Würde dich denn ein implementation-defined nicht davon abhalten, dass mittels cast zu machen? Das hiesse doch dann eigentlich, dass zwar das Verhalten definiert ist, jedoch von Compiler zu Compiler variieren kann.

Prinzipiell ja, im konkreten Fall ist es aber halt so dass es a) effektiv keine sinnvolle Alternative gibt und b) effektiv hier nur ein sinnvolles Behavior gibt, dem alle relevanten Implementierungen auch folgen.

[starcow]

Ich hab jetzt mal aus Neugier versucht, die explizite Stelle im Standard zu finden, die Bezug nimmt, zum cast int to unsigned int.
Leider bin ich nicht fündig geworden - beim Thema "cast" gabs jedenfalls diesbezüglich nichts zu lesen.

[dot]

Ich hab jetzt mal aus Neugier versucht, die explizite Stelle im Standard zu finden, die Bezug nimmt, zum cast int to unsigned int.
Leider bin ich nicht fündig geworden - beim Thema "cast" gabs jedenfalls diesbezüglich nichts zu lesen.

In C wäre das 6.3.1.3/3 (https://open-std.org/JTC1/SC22/WG14/www/docs/n3096.pdf Seite 46)

Otherwise, the new type is signed and the value cannot be represented in it; either the result is implementation-defined or an implementation-defined signal is raised.

in C++ [conv.integral]/3

Otherwise, the result is the unique value of the destination type that is congruent to the source integer modulo \(2^N\), where \(N\) is the width of the destination type.

[starcow]

Super, dank dir dot!

[starcow]

... und ich habe Steve Summit daraufhin angemailt.
Er hat mir jedoch bis heute nicht geantwortet - vielleicht weil wir etwas banales übersehen hatten?

Ein erfreuliches Update in dieser Sache:
Steve Summit hatte damals mein Mail einfach übersehen. Nun hat er mir doch noch (sehr freundlich und herzlich) geantwortet.

Er beurteilt das Ganze genau gleich wie wir. UB, wenn man es wirklich genau nimmt!

Zu dem cast schreibt er weiter:

Regardless, I don't understand why you do the following cast after "unsigned (int)":

Code: Alles auswählen

s.i32 |= (unsigned)(*p++ << 8);

That I can't explain, either! When I
opened up question 16.7 to review it
while reading your email, I couldn't
believe I'd presented it that way:
it looks *very* strange, doesn't it?

Er hat mir zudem mitgeteilt, dass er plane, die FAQ noch etwas zu überarbeiten - das Projekt scheint also für ihn noch aktuell zu sein!

[starcow]

Aus gegebenem Anlass zum Thema der "Bitshifterei" viewtopic.php?f=4&t=5528&sid=73d32a729f ... 7ac5f5dcc0, wollte ich mir die Zeit nehmen, die beiden Standards C und C++ (soweit es mir möglich war) in diesem einen Punkt nochmals ganz genau miteinander zuvergleichen.

Tatsächlich scheinen sich C und C++ hier, in einem feinen Aspekt zu unterscheiden - was mir irgendwie ungewollt erscheint.
Es geht um Left Shift auf signed.
Im C Standard war und ist (soweit ich es für den Entwurf von C23 sehen kann) das Ganze folgendermassen formuliert:
S.85 6.5.6 Abschnitt 4

E1 << E2
If E1 has a signed type and nonnegative value, and E1 × 2^E2 is representable in the result type, then that is the resulting value;
otherwise, the behavior is undefined.

Mit anderen Worten:
Bei sigend darf ich keine 1 rausschieben UND ich darf zudem keine 1 auf das letzte Bit shiften, um damit z.B. INT_MIN zu kreieren.

Code: Alles auswählen

int_min = 1 << 31; // UB in C
int_min = 1U << 31; // fine

Irgendwie scheint das wohl bei C++ vor C++20 ähnlich gewesen zu sein, da es einen Request gab, der genau diesen Punkt adressierte (wie Krishty richtigerweise bemerkt hatte).

Der Korrekturvorschlag ist wohl der Teil, der grün markiert wurde

...if E1 has a signed type and non-negative value, and E1 ⨯ 2E2 is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

Es gab 2012 einen Request für diese Ergänzung:

...if E1 has a signed type and non-negative value, and E1 ⨯ 2E2 is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

Falls das angenommen wurde, wäre unser Problem gelöst: Man dürfte ein Bit in das Vorzeichen reinshiften, aber nicht darüber hinaus.

Wenn man jetzt bloß den C++-Standard einsehen könnte, ohne 250 € zu bezahlen …

Mit dieser Formulierung wäre dann folgendes wieder erlaubt:

Code: Alles auswählen

int_min = 1 << 31; // fine in C++?

In dem einen alten C++ 2003 Standard, den ich hier einsehen kann, ist es dann wiederum so formuliert:

The value of E1 << E2 is E1 (interpreted as a bit pattern) left-shifted E2 bit positions; vacated bits are
zero-filled. If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity 2 raised to
the power E2, reduced modulo ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise.
[Note: the constants ULONG_MAX and UINT_MAX are defined in the header <climits>). ]

Man kriegt den Eindruck, als wäre man mit diesem Abschnitt irgendwie nie richtig glücklich gewesen.

Bemerkenswert finde ich noch, dass es in C23 wohl nicht angepasst wird (bin mir jedoch nicht sicher).