Is maskeren voor een niet-ondertekende linkerverschuiving in C/C++ te paranoïde?

Deze vraag wordt gemotiveerd doordat ik cryptografische algoritmen (bijv. SHA-1) in C/C++ implementeer, draagbare platformonafhankelijke code schrijf en undefined gedrag.

Stel dat een gestandaardiseerd crypto-algoritme u vraagt ​​om dit te implementeren:

b = (a << 31) & 0xFFFFFFFF

waarbij aen b32-bits gehele getallen zonder teken zijn. Merk op dat we in het resultaat alle bits boven de minst significante 32 bits weggooien.

Als eerste naïeve benadering kunnen we aannemen dat int32 bits breed is op de meeste platforms, dus we zouden schrijven:

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

We weten dat deze code niet overal zal werken omdat intop sommige systemen 16 bits breed is, op andere 64 bits en mogelijk zelfs 36 bits. Maar met behulp van stdint.hkunnen we deze code verbeteren met het type uint32_t:

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

Dus we zijn klaar, toch? Dat dacht ik al jaren. … Niet helemaal. Stel dat we op een bepaald platform:

// stdint.h
typedef unsigned short uint32_t;

De regel voor het uitvoeren van rekenkundige bewerkingen in C/C++ is dat als het type (zoals short) smaller is dan int, het wordt verbreed naar intals alle waarden passen, of unsigned intanders.

Stel dat de compiler shortdefinieert als 32 bits (signed) en intals 48 bits (signed). Dan deze regels code:

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

betekent in feite:

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

Merk op dat awordt gepromoveerd tot intomdat alle ushort(dwz uint32) in int(dwz int48).

Maar nu hebben we een probleem: het verschuiven van niet-nul-bits naar de teken-bit van een ondertekend geheel getal is ongedefinieerd gedrag. Dit probleem deed zich voor omdat onze uint32gepromoveerd was tot int48– in plaats van gepromoveerd te worden tot uint48(waar links-shiften goed zou zijn).

Dit zijn mijn vragen:

1. Is mijn redenering correct, en is dit in theorie een legitiem probleem?

2. Is dit probleem veilig om te negeren, omdat op elk platform het volgende integer-type dubbel zo breed is?

3. Is het een goed idee om je op de juiste manier tegen deze pathologische situatie te verdedigen door de invoer als volgt te maskeren?: b = (a & 1) << 31;. (Dit zal noodzakelijkerwijs correct zijn op elk platform. Maar dit kan een snelheidskritisch crypto-algoritme langzamer maken dan nodig is.)

Verduidelijkingen/aanpassingen:

• Ik accepteer antwoorden voor C of C++ of beide. Ik wil het antwoord weten voor ten minste één van de talen.

• De pre-masking logica kan de bitrotatie schaden. GCC compileert bijvoorbeeld b = (a << 31) | (a >> 1);naar een 32-bits bitrotatie-instructie in assembler. Maar als we de linkerverschuiving vooraf maskeren, is het mogelijk dat de nieuwe logica niet wordt vertaald in bitrotatie, wat betekent dat er nu 4 bewerkingen worden uitgevoerd in plaats van 1.

Antwoord 1, autoriteit 100%

Met de C-kant van het probleem spreken,

1. Is mijn redenering correct, en is dit in theorie een legitiem probleem?

Het is een probleem waar ik nog niet eerder over heb nagedacht, maar ik ben het eens met je analyse. C definieert het gedrag van de operator <<in termen van het type van de gepromotelinker operand, en het is denkbaar dat de integer-promoties ertoe leiden dat (ondertekend ) intwanneer het oorspronkelijke type van die operand uint32_tis. Ik verwacht dat in de praktijk niet op een moderne machine te zien, maar ik ben er helemaal voor om te programmeren volgens de werkelijke standaard, in tegenstelling tot mijn persoonlijke verwachtingen.

2. Is dit probleem veilig om te negeren, omdat op elk platform het volgende integer-type dubbel zo breed is?

C vereist zo’n relatie tussen integer-typen niet, hoewel het in de praktijk alomtegenwoordig is. Als je echter vastbesloten bent om alleen op de standaard te vertrouwen — dat wil zeggen, als je moeite doet om strikt conforme code te schrijven — dan kun je niet vertrouwen op zo’n relatie.

3. Is het een goed idee om je op de juiste manier tegen deze pathologische situatie te verdedigen door de invoer als volgt te maskeren?: b = (a & 1) << 31;.
   (Dit zal noodzakelijkerwijs correct zijn op elk platform. Maar dit zou kunnen)
   maak een snelheidskritisch crypto-algoritme langzamer dan nodig.)

Het type unsigned longheeft gegarandeerd ten minste 32 waardebits en is niet onderhevig aan promotie naar een ander type onder de integer-promoties. Op veel gangbare platforms heeft het exact dezelfde weergave als uint32_t, en kan zelfs van hetzelfde type zijn. Ik zou dus geneigd zijn om de uitdrukking als volgt te schrijven:

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

Of als je aalleen nodig hebt als tussenwaarde in de berekening van b, declareer het dan als een unsigned longom mee te beginnen .

Antwoord 2, autoriteit 92%

Q1: Maskeren vóórde dienst voorkomt ongedefinieerd gedrag waar OP zich zorgen over maakt.

V2: “… omdat op elk platform het volgende integer-type dubbel zo breed is?” –> Nee. Het “volgende” integer-type kan kleiner zijn dan 2x of zelfs even groot.

Het volgende is goed gedefinieerd voor alle compatibele C-compilers die uint32_thebben.

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

Q3: uint32_t a; uint32_t b = (a & 1) << 31;zal naar verwachting geen code bevatten die een masker uitvoert – het is niet nodig in het uitvoerbare bestand – alleen in de bron. Als er toch een masker optreedt, zorg dan voor een betere compiler als snelheid een probleem zou zijn.

Zoals suggereerde, beter om de unsigned-ness te benadrukken met deze verschuivingen.

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

@John Bollingergoed antwoord en details over hoe het specifieke probleem van OP moet worden opgelost.

Het algemeneprobleem is hoe je een getal kunt vormen dat uit minstens nbits bestaat, een bepaald teken enniet onderhevig is aan verrassende integer-promoties – de kern van OP’s dilemma. Het onderstaande voldoet hieraan door een unsigned-bewerking aan te roepen die de waarde niet verandert – effectief een no-op anders dan typeproblemen. Het product zal minstensde breedte hebben van unsignedof uint32_t. Gieten kan in het algemeen het type verkleinen. Gieten moet worden vermeden, tenzij vernauwing zeker niet optreedt. Een optimalisatiecompiler maakt geen onnodige code.

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

Antwoord 3, autoriteit 58%

Een aanwijzing halen uit deze vraagover mogelijke UB in uint32 * uint32rekenkunde, de volgende eenvoudige aanpak zou moeten werken in C en C++:

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

De integer constante 0uheeft het type unsigned int. Dit bevordert de toevoeging a + 0uaan uint32_tof unsigned int, welke van de twee breder is. Omdat het type rang intof hoger heeft, vindt er geen promotie meer plaats en kan de verschuiving worden toegepast met de linker operand uint32_tof unsigned int.

De definitieve cast terug naar uint32_tonderdrukt alleen potentiële waarschuwingen over een versmallende conversie (bijvoorbeeld als int64 bits is).

Een fatsoenlijke C-compiler zou moeten kunnen zien dat het toevoegen van nul een no-op is, wat minder belastend is dan te zien dat een pre-mask geen effect heeft na een niet-ondertekende dienst.

Antwoord 4, autoriteit 42%

Om ongewenste promotie te voorkomen, kunt u het type grotergebruiken met een bepaalde typedef, zoals

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

Antwoord 5

Voor dit codesegment:

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

Om ate promoten tot een niet-ondertekend type in plaats van ondertekend type, gebruik je:

uint32_t b = a << 31u;

Als beide zijden van de operator <<een niet-ondertekend type zijn, is deze regel in 6.3.1.8 (C-standaardconcept n1570) van toepassing:

Anders, als beide operanden integer-typen met teken hebben of beide typen integers zonder teken, wordt de operand met het type lagere conversierang voor gehele getallen geconverteerd naar het type operand met hogere rangorde.

Het probleem dat je beschrijft is veroorzaakt dat je 31gebruikt, wat signed int typeis, dus een andere regel in 6.3.1.8

Anders, als het type van de operand met een geheel getal met teken alle waarden kan vertegenwoordigen van het type van de operand met een geheel getal zonder teken, wordt de operand met het type geheel getal zonder teken geconverteerd naar het type van de operand met een geheel getal met teken type.

dwingt aom te promoveren naar een ondertekend type

Bijwerken:

Dit antwoord is niet correct omdat 6.3.1.1(2) (nadruk van mij):

…

Als een int alle waarden van het originele type kan vertegenwoordigen (als beperkt
door de breedte, voor een bit-veld), wordt de waarde geconverteerd naar een int;
anders wordt het geconverteerd naar een unsigned int. Deze worden de
integer promotions.58) Alle andere typen zijn ongewijzigd door het integer
promoties.

en voetnoot 58 (nadruk van mij):

58) De promoties voor gehele getallen worden alleen toegepast: als onderdeel van de gebruikelijke rekenkundige conversies, op bepaalde argumentuitdrukkingen, op de operanden van de unaire +, – en ~ operators, en op beide operanden van de shift-operators , zoals gespecificeerd door hun respectievelijke subclausules.

Aangezien alleen promotie van gehele getallen plaatsvindt en geen gewone rekenkundige conversie, garandeert het gebruik van 31uniet dat awordt geconverteerd naar unsigned intzoals vermeld hierboven.