Le masquage avant décalage gauche non signé en C / C ++ est-il trop paranoïaque?

Question

Cette question est motivée par me mettre en œuvre des algorithmes cryptographiques (par exemple SHA-1) en C/C++, écrit portable de la plate-forme agnostique code, et soigneusement éviter un comportement indéfini.

Supposons qu'un standardisé algorithme de chiffrement vous demande de mettre en œuvre ce:

b = (a << 31) & 0xFFFFFFFF

où a et b sont des entiers 32 bits non signés. Remarquez que dans la suite, nous supprimons tous les bits au-dessus de la moins importante à 32 bits.

---

Dans un premier naïf approximation, on peut supposer que l' int 32 bits de large sur la plupart des plates-formes, donc on peut écrire:

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

Nous savons que ce code ne fonctionne pas partout, parce que int est de 16 bits de large sur certains systèmes, 64 bits sur les autres, et peut-être même de 36 bits. Mais à l'aide de stdint.h, nous pouvons améliorer ce code avec l' uint32_t type:

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

Nous sommes donc à faire, non? C'est ce que j'ai pensé pendant des années. ... Pas tout à fait. Supposons que sur une certaine plate-forme, nous avons:

// stdint.h
typedef unsigned short uint32_t;

La règle pour effectuer des opérations arithmétiques en C/C++, c'est que si le type (comme short) est plus étroite que int, puis il est élargi à l' int si toutes les valeurs peuvent s'adapter, ou unsigned int sinon.

Disons que le compilateur définit short 32 bits (signé) et int 48 bits (signé). Ensuite, ces lignes de code:

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

effectivement signifier:

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

Notez que a est promu int parce que tout d' ushort (c - uint32) s'inscrit dans int (c - int48).

Mais maintenant, nous avons un problème: déplacement non-zéro les bits à gauche dans le bit de signe d'un entier signé de type est un comportement indéfini. Ce problème est arrivé parce que notre uint32 a été promu int48 - au lieu d'être promu uint48 (où de gauche décalage serait bien).

---

Voici mes questions:

1. Est mon raisonnement correct, et est-ce un problème légitime dans la théorie?

2. Ce problème est-il sûr d'ignorer parce que sur chaque plate-forme de l'entier suivant le type est le double de la largeur?

3. Est une bonne idée de correctement se défendre contre cette situation pathologique par pré-masquage de l'entrée comme ceci?: b = (a & 1) << 31;. (Ce sera nécessairement correct sur chaque plate-forme. Mais cela pourrait permettre à une vitesse critiques de l'algorithme de chiffrement plus lentement que nécessaire.)

Précisions/modifications:

• Je vais accepter les réponses pour le C ou C++, ou les deux. Je veux savoir la réponse à au moins l'une des langues.

• La pré-masquage logique peut nuire à peu de rotation. Par exemple, GCC compiler b = (a << 31) | (a >> 1); 32 bits de rotation de bits de l'instruction en langage d'assemblage. Mais si nous pré-masque le virage à gauche, il est possible que la nouvelle logique n'est pas traduit en peu de rotation, ce qui signifie maintenant 4 opérations sont effectuées au lieu de 1.

Answer 1

Parlant de la C côté du problème,

1. Est mon raisonnement correct, et est-ce un problème légitime dans la théorie?

C'est un problème que je n'avais pas avant, mais je suis d'accord avec votre analyse. C définit le comportement de l' << de l'opérateur en termes de type de l' promu opérande de gauche, et il-il concevable que l'entier des promotions en sorte que l'être (signé) int lorsque le type de l'opérande est - uint32_t. Je ne m'attends pas à voir que, dans la pratique moderne de la machine, mais je suis pour la programmation de la norme, par opposition à mes attentes personnelles.

2. Ce problème est-il sûr d'ignorer parce que sur chaque plate-forme de l'entier suivant le type est le double de la largeur?

C ne nécessite pas une telle relation entre les types integer, même si elle est omniprésente dans la pratique. Si vous êtes déterminé à ne compter que sur la norme, mais -- c'est, si vous prenez soin d'écrire en se conformant strictement code, alors vous ne pouvez pas compter sur un tel lien.

3. Est une bonne idée de correctement se défendre contre cette situation pathologique par pré-masquage de l'entrée comme ceci?: b = (a-1) << 31;. (Ce sera nécessairement correct sur chaque plate-forme. Mais cela pourrait faites une vitesse critique algorithme de chiffrement plus lentement que nécessaire.)

Le type unsigned long est la garantie d'avoir au moins 32 valeur de bits, et il n'est pas soumise à la promotion de tout autre type, en vertu de l'entier des promotions. Sur de nombreuses plates-formes communes, il a exactement la même représentation que uint32_t, et même peut-être du même type. Ainsi, j'ai tendance à écrire l'expression comme ceci:

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

Ou si vous avez besoin d' a seulement comme une valeur intermédiaire dans le calcul de l' b, puis le déclarer comme un unsigned long pour commencer.

Answer 2

Q1: de Masquage avant la maj de prévenir un comportement indéfini que l'OP a le souci.

Q2: "... parce que sur chaque plate-forme de l'entier suivant le type est le double de la largeur?" --> non. Le "prochain" de type entier pourrait être inférieur à 2x ou même de la même taille.

La suite est bien définie pour tous conformes à la norme C compilateurs qui ont uint32_t.

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

Q3: est - uint32_t a; uint32_t b = (a & 1) << 31; ne devrait pas subir de code qui effectue un masque, il n'est pas nécessaire dans le fichier exécutable - seulement dans la source. Si un masque ne se produisent, pour obtenir un meilleur compilateur vitesse devrait être un problème.

Comme suggéré, pour mieux souligner la non signé-ness avec ces changements.

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

---

@John Bollinger bonne réponse bien les détails de comment gérer les OP de problème spécifique.

Le général problème est de savoir comment former un nombre qui est d'au moins n bits, un signe certain-ness et non soumis à surprenant entier promotions - le cœur de l'OP dilemme. Ci-dessous répond en invoquant un unsigned opération ne change pas la valeur efficace d'un no-op, autres que de type de préoccupations. Le produit sera d'au moins la largeur de l' unsigned ou uint32_t. De la coulée, en général, peut préciser le type. La coulée doit être évitée sauf si le rétrécissement est certain de ne pas se produire. Une optimisation du compilateur ne créera pas de code inutile.

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

Answer 3

En prenant un indice de cette question à propos d'une possible UB en uint32 * uint32 l'arithmétique, de la simple suivant l'approche devrait travailler en C et C++:

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

La constante entière 0u type unsigned int. Ce qui favorise le plus a + 0u de uint32_t ou unsigned int, celle qui est la plus large. Parce que le type a rang int ou plus, pas plus de promotion se produit, et le changement peut être appliqué avec l'opérande de gauche étant uint32_t ou unsigned int.

La distribution finale retour à l' uint32_t va juste supprimer les éventuels avertissements au sujet d'un rétrécissement de conversion (dire si int 64 bits).

Un décent C compilateur doit être en mesure de voir que l'ajout de zéro est un no-op, ce qui est moins onéreux que de voir qu'une pré-masque n'a pas d'effet après un unsigned maj.

Answer 4

Pour éviter les promotions non désirées, vous pouvez utiliser le type supérieur avec certains typedef, comme

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

Answer 5

Pour ce segment de code:

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

Pour promouvoir a d'un type non signé à la place de type signé, utilisez:

uint32_t b = a << 31u;

Lorsque les deux côtés de l' << de l'opérateur est d'un type non signé, alors cette ligne dans 6.3.1.8 (C projet de norme n1570) s'applique:

Sinon, si les deux opérandes ont signé des types d'entiers, ou les deux, ont entier non signé types, l'opérande avec le type de moindre conversion d'entier rang est convertie dans le type de l'opérande avec plus rang.

---

Le problème que vous décrivez est causée vous utilisez 31 qui signed int type , et donc une autre ligne dans 6.3.1.8

Sinon, si le type de l'opérande de type entier signé peut représenter l'ensemble des valeurs du type de l'opérande de type entier non signé, puis l'opérande de type entier non signé est convertie dans le type de l'opérande de type entier signé.

les forces de a de promus à un type signé

---

Mise à jour:

Cette réponse n'est pas correcte parce que 6.3.1.1(2) (l'emphase est mienne):

...

Si un int peut représenter toutes les valeurs du type d'original (que la restriction de l' par la largeur, pour un peu de champ), la valeur est convertie en int; sinon, il est converti en unsigned int. On les appelle les entier promotions.58) Tous les autres types sont inchangées par l' entier des promotions.

et la note de bas de page 58 (l'emphase est mienne):

58) L'entier des promotions sont appliquées uniquement: dans le cadre de l'habitude de l'arithmétique conversions, pour certains argument expressions à opérandes de l'unaire +, -, et ~ opérateurs, et pour les deux opérandes des opérateurs de décalage, comme spécifié par leurs subdivisions.

Depuis entiers de promotion qui se passe et qui n'est pas commun conversion arithmétique, à l'aide de 31u ne garantit pas l' a être converti en unsigned int comme indiqué ci-dessus.