Ist die Maskierung vor der vorzeichenlosen Linksverschiebung in C / C ++ zu paranoid?

Diese Frage wird von mir motiviert, kryptografische Algorithmen (z. B. SHA-1) in C / C ++ zu implementieren, tragbaren plattformunabhängigen Code zu schreiben und undefiniertes Verhalten gründlich zu vermeiden .

Angenommen, ein standardisierter Krypto-Algorithmus fordert Sie auf, Folgendes zu implementieren:

b = (a << 31) & 0xFFFFFFFF

wo aund bsind vorzeichenlose 32-Bit-Ganzzahlen. Beachten Sie, dass wir im Ergebnis alle Bits verwerfen, die über den niedrigstwertigen 32 Bits liegen.

Als erste naive Annäherung könnten wir annehmen, dass diese intauf den meisten Plattformen 32 Bit breit ist, also würden wir schreiben:

unsigned int a = (...);
unsigned int b = a << 31;

Wir wissen, dass dieser Code nicht überall funktioniert, da er intauf einigen Systemen 16 Bit, auf anderen 64 Bit und möglicherweise sogar 36 Bit breit ist. Mit stdint.hkönnen wir diesen Code jedoch mit dem folgenden uint32_tTyp verbessern :

uint32_t a = (...);
uint32_t b = a << 31;

Also sind wir fertig, oder? Das habe ich mir jahrelang gedacht. ... Nicht ganz. Angenommen, auf einer bestimmten Plattform haben wir:

// stdint.h
typedef unsigned short uint32_t;

Die Regel für die Ausführung von arithmetischen Operationen in C / C ++ lautet: Wenn der Typ (z. B. short) schmaler als ist int, wird er erweitert, intwenn alle Werte passen können oder auf unsigned intandere Weise.

Angenommen, der Compiler definiert shortals 32 Bit (signiert) und intals 48 Bit (signiert). Dann diese Codezeilen:

uint32_t a = (...);
uint32_t b = a << 31;

wird effektiv bedeuten:

unsigned short a = (...);
unsigned short b = (unsigned short)((int)a << 31);

Beachten Sie, dass zu abefördert wird, intweil alle ushort(dh uint32) in int(dh int48) passen .

Aber jetzt haben wir ein Problem: Das Verschieben von Nicht-Null-Bits in das Vorzeichenbit eines vorzeichenbehafteten Integer-Typs ist ein undefiniertes Verhalten . Dieses Problem trat auf, weil wir uint32befördert wurden int48- anstatt befördert zu werden uint48(wo Linksverschiebung in Ordnung wäre).

Hier sind meine Fragen:

1. Ist meine Argumentation richtig und ist dies theoretisch ein legitimes Problem?

2. Ist dieses Problem sicher zu ignorieren, da auf jeder Plattform der nächste Ganzzahltyp doppelt so breit ist?

3. Ist es eine gute Idee, sich gegen diese pathologische Situation richtig zu verteidigen, indem Sie die Eingabe wie folgt vormaskieren?: b = (a & 1) << 31;. (Dies muss auf jeder Plattform korrekt sein. Dies kann jedoch dazu führen, dass ein geschwindigkeitskritischer Krypto-Algorithmus langsamer als erforderlich ist.)

Erläuterungen / Änderungen:

• Ich akzeptiere Antworten für C oder C ++ oder beides. Ich möchte die Antwort für mindestens eine der Sprachen wissen.

• Die Vormaskierungslogik kann die Bitrotation beeinträchtigen. Beispielsweise wird GCC b = (a << 31) | (a >> 1);zu einem 32-Bit-Bitrotationsbefehl in Assemblersprache kompiliert . Wenn wir jedoch die Linksverschiebung vormaskieren, ist es möglich, dass die neue Logik nicht in Bitrotation übersetzt wird, was bedeutet, dass jetzt 4 Operationen anstelle von 1 ausgeführt werden.

Mit der C-Seite des Problems sprechen,

1. Ist meine Argumentation richtig und ist dies theoretisch ein legitimes Problem?

Es ist ein Problem, das ich vorher nicht in Betracht gezogen hatte, aber ich stimme Ihrer Analyse zu. C definiert das Verhalten des <<Bedieners in Bezug auf die Art der geförderten linken Operanden, und es denkbar , dass die ganze Zahl aktionen in diesem Wesen Ergebnis (signed) , intwenn der Vorlagentyp dieses Operanden ist uint32_t. Ich erwarte nicht, dass dies in der Praxis auf einer modernen Maschine der Fall ist, aber ich bin alle dafür, nach dem tatsächlichen Standard zu programmieren, im Gegensatz zu meinen persönlichen Erwartungen.

2. Ist dieses Problem sicher zu ignorieren, da auf jeder Plattform der nächste Ganzzahltyp doppelt so breit ist?

C erfordert keine solche Beziehung zwischen ganzzahligen Typen, obwohl sie in der Praxis allgegenwärtig ist. Wenn Sie jedoch entschlossen sind, sich nur auf den Standard zu verlassen, dh wenn Sie sich Mühe geben, streng konformen Code zu schreiben, können Sie sich nicht auf eine solche Beziehung verlassen.

3. Ist es eine gute Idee, sich gegen diese pathologische Situation richtig zu verteidigen, indem Sie die Eingabe wie folgt vormaskieren?: B = (a & 1) << 31;. (Dies muss auf jeder Plattform korrekt sein. Dies kann jedoch dazu führen, dass ein geschwindigkeitskritischer Krypto-Algorithmus langsamer als erforderlich ist.)

Es unsigned longwird garantiert, dass der Typ mindestens 32 Wertbits aufweist, und er unterliegt keiner Heraufstufung zu einem anderen Typ unter den ganzzahligen Heraufstufungen. Auf vielen gängigen Plattformen hat es genau die gleiche Darstellung wie uint32_tund kann sogar vom gleichen Typ sein. Daher wäre ich geneigt, den Ausdruck so zu schreiben:

uint32_t a = (...);
uint32_t b = (unsigned long) a << 31;

Oder wenn Sie anur einen Zwischenwert für die Berechnung von benötigen b, deklarieren Sie ihn zunächst als unsigned long.

Q1: Das Maskieren vor der Schicht verhindert undefiniertes Verhalten, das OP betrifft.

F2: "... weil auf jeder Plattform der nächste ganzzahlige Typ doppelt so breit ist?" -> nein. Der "nächste" Integer-Typ kann kleiner als 2x oder sogar gleich groß sein.

Das Folgende ist für alle kompatiblen C-Compiler genau definiert uint32_t.

uint32_t a; 
uint32_t b = (a & 1) << 31;

F3: Es uint32_t a; uint32_t b = (a & 1) << 31;wird nicht erwartet, dass Code entsteht, der eine Maske ausführt - er wird in der ausführbaren Datei nicht benötigt - nur in der Quelle. Wenn eine Maske auftritt, sollten Sie einen besseren Compiler verwenden, falls die Geschwindigkeit ein Problem darstellt.

Wie vorgeschlagen , ist es besser, die Unsigniertheit bei diesen Verschiebungen zu betonen.

uint32_t b = (a & 1U) << 31;

@ John Bollinger gute Antwort und Details, wie man mit dem spezifischen Problem von OP umgeht .

Das allgemeine Problem besteht darin, eine Zahl zu bilden, die mindestens aus nBits und einem bestimmten Vorzeichen besteht und keinen überraschenden ganzzahligen Beförderungen unterliegt - dem Kern des OP-Dilemmas. Das Folgende erfüllt dies, indem eine unsignedOperation aufgerufen wird, die den Wert nicht ändert - effektiv ein No-Op, das keine Typprobleme betrifft. Das Produkt hat mindestens die Breite von unsignedoder uint32_t. Das Gießen kann im Allgemeinen den Typ einschränken. Das Gießen muss vermieden werden, es sei denn, es ist sicher, dass keine Verengung auftritt. Ein Optimierungs-Compiler erstellt keinen unnötigen Code.

uint32_t a;
uint32_t b = (a + 0u) << 31;
uint32_t b = (a*1u) << 31;

Ausgehend von dieser Frage nach möglichen UB in der uint32 * uint32Arithmetik sollte der folgende einfache Ansatz in C und C ++ funktionieren:

uint32_t a = (...);
uint32_t b = (uint32_t)((a + 0u) << 31);

Die Ganzzahlkonstante 0uhat den Typ unsigned int. Dies fördert die Hinzufügung a + 0uzu uint32_toder unsigned int, je nachdem, welcher Wert breiter ist. Da der Typ einen Rang intoder höher hat, erfolgt keine Beförderung mehr, und die Verschiebung kann angewendet werden, wobei der linke Operand uint32_toder ist unsigned int.

Die endgültige uint32_tUmwandlung in unterdrückt nur mögliche Warnungen vor einer sich verengenden Konvertierung (z. B. wenn int64 Bit vorhanden sind).

Ein anständiger C-Compiler sollte erkennen können, dass das Hinzufügen von Null ein No-Op ist, was weniger belastend ist als das Erkennen, dass eine Vormaske nach einer vorzeichenlosen Verschiebung keine Wirkung hat.

Um unerwünschte Werbung zu vermeiden, können Sie den größeren Typ mit einigen typedef verwenden, z

using my_uint_at_least32 = std::conditional_t<(sizeof(std::uint32_t) < sizeof(unsigned)),
                                              unsigned,
                                              std::uint32_t>;

Für dieses Codesegment:

uint32_t a = (...);
uint32_t b = a << 31;

aVerwenden Sie Folgendes, um zu einem nicht signierten Typ anstelle eines signierten Typs zu wechseln:

uint32_t b = a << 31u;

Wenn beide Seiten des <<Operators ein vorzeichenloser Typ sind, gilt diese Zeile in 6.3.1.8 (C-Standardentwurf n1570):

Andernfalls wird der Operand mit dem Typ des Konvertierungsrangs mit geringerer Ganzzahl in den Typ des Operanden mit höherem Rang konvertiert, wenn beide Operanden Ganzzahltypen mit Vorzeichen oder beide Ganzzahltypen mit Vorzeichen haben.

Das Problem, das Sie beschreiben, ist darauf zurückzuführen, dass Sie es verwenden. Dies 31ist signed int typealso eine weitere Zeile in 6.3.1.8

Wenn andernfalls der Typ des Operanden mit vorzeichenbehaftetem Integer-Typ alle Werte des Typs des Operanden mit vorzeichenlosem Integer-Typ darstellen kann, wird der Operand mit vorzeichenlosem Integer-Typ in den Typ des Operanden mit vorzeichenbehaftetem Integer-Typ konvertiert.

zwingt azu einem signierten Typ befördert

Aktualisieren:

Diese Antwort ist nicht korrekt, weil 6.3.1.1 (2) (Hervorhebung von mir):

...

Wenn ein int alle Werte des ursprünglichen Typs darstellen kann (wie durch die Breite für ein Bitfeld eingeschränkt), wird der Wert in ein int konvertiert . Andernfalls wird es in ein vorzeichenloses int konvertiert . Diese werden als Integer-Promotions bezeichnet.58) Alle anderen Typen bleiben durch die Integer- Promotions unverändert .

und Fußnote 58 (Hervorhebung von mir):

58) Die ganzzahligen Heraufstufungen werden nur angewendet: als Teil der üblichen arithmetischen Umrechnungen auf bestimmte Argumentausdrücke, auf die Operanden der unären Operatoren +, - und ~ und auf beide Operanden der Verschiebungsoperatoren , wie von ihren jeweiligen angegeben Unterabschnitte.

Da nur eine ganzzahlige Heraufstufung stattfindet und keine übliche arithmetische Konvertierung, 31ugarantiert die Verwendung nicht a, dass auf unsigned intdie oben angegebene Konvertierung umgestellt wird .