tabla - ¿El enmascaramiento antes del desplazamiento a la izquierda sin firmar en C/C++ es demasiado paranoico?

tipos de datos en c++

Question

Esta pregunta está motivada por mí implementando algoritmos criptográficos (por ejemplo, SHA-1) en C / C ++, escribiendo código portátil independiente de la plataforma y evitando completamente el comportamiento indefinido .

Suponga que un algoritmo criptográfico estandarizado le pide que implemente esto:

b = (a << 31) & 0xFFFFFFFF

donde a y b son enteros de 32 bits sin signo. Tenga en cuenta que en el resultado, descartamos cualquier bit por encima de los 32 bits menos significativos.

Como primera aproximación ingenua, podríamos suponer que int tiene 32 bits de ancho en la mayoría de las plataformas, por lo que escribiríamos:

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

Sabemos que este código no funcionará en todas partes porque int tiene 16 bits de ancho en algunos sistemas, 64 bits en otros y posiblemente incluso 36 bits. Pero usando stdint.h , podemos mejorar este código con el tipo uint32_t :

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

Así que hemos terminado, ¿verdad? Eso es lo que pensé durante años. ... no del todo. Supongamos que en una determinada plataforma, tenemos:

// stdint.h
typedef unsigned short uint32_t;

La regla para realizar operaciones aritméticas en C / C ++ es que si el tipo (como short ) es más estrecho que int , entonces se amplía a int si todos los valores pueden ajustarse, o unsigned int contrario.

Digamos que el compilador define short como 32 bits (con signo) e int como 48 bits (con signo). Entonces estas líneas de código:

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

significará efectivamente:

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

Tenga en cuenta que a se promueve a int porque todo ushort (es decir, uint32 ) encaja en int (es decir, int48 ).

Pero ahora tenemos un problema: desplazar bits que no son cero a la izquierda en el bit de signo de un tipo entero con signo es un comportamiento indefinido . Este problema ocurrió porque nuestro uint32 fue promovido a int48 , en lugar de ser promovido a uint48 (donde el desplazamiento a la izquierda estaría bien).

Aquí están mis preguntas:

1. ¿Es correcto mi razonamiento, y este es un problema legítimo en teoría?

2. ¿Es seguro ignorar este problema porque en cada plataforma el siguiente tipo entero es el doble del ancho?

3. ¿Es una buena idea defenderse correctamente de esta situación patológica enmascarando previamente la entrada de esta manera ?: b = (a & 1) << 31; . (Esto será necesariamente correcto en todas las plataformas. Pero esto podría hacer que un algoritmo criptográfico de velocidad crítica sea más lento de lo necesario).

Aclaraciones / ediciones:

• Aceptaré respuestas para C o C ++ o ambas. Quiero saber la respuesta de al menos uno de los idiomas.

• La lógica de preenmascaramiento puede dañar la rotación de bits. Por ejemplo, GCC compilará b = (a << 31) | (a >> 1); b = (a << 31) | (a >> 1); a una instrucción de rotación de bits de 32 bits en lenguaje ensamblador. Pero si premascaramos el desplazamiento a la izquierda, es posible que la nueva lógica no se traduzca en rotación de bits, lo que significa que ahora se realizan 4 operaciones en lugar de 1.

Answer 1

Hablando al lado C del problema,

1. ¿Es correcto mi razonamiento, y este es un problema legítimo en teoría?

Es un problema que no había considerado antes, pero estoy de acuerdo con su análisis. C define el comportamiento del operador << en términos del tipo del operando izquierdo promovido , y es concebible que las promociones enteras resulten en ese int (firmado) cuando el tipo original de ese operando es uint32_t . No espero ver eso en la práctica en ninguna máquina moderna, pero estoy dispuesto a programar según el estándar real en lugar de mis expectativas personales.

2. ¿Es seguro ignorar este problema porque en cada plataforma el siguiente tipo entero es el doble del ancho?

C no requiere tal relación entre los tipos enteros, aunque es omnipresente en la práctica. Sin embargo, si está decidido a confiar solo en el estándar, es decir, si se está esforzando por escribir un código estrictamente conforme, entonces no puede confiar en esa relación.

3. ¿Es una buena idea defenderse correctamente de esta situación patológica enmascarando previamente la entrada de esta manera ?: b = (a & 1) << 31 ;. (Esto será necesariamente correcto en todas las plataformas. Pero esto podría hacer que un algoritmo criptográfico de velocidad crítica sea más lento de lo necesario).

Se garantiza que el tipo unsigned long tiene al menos 32 bits de valor, y no está sujeto a promoción a ningún otro tipo bajo las promociones de enteros. En muchas plataformas comunes, tiene exactamente la misma representación que uint32_t , e incluso puede ser del mismo tipo. Por lo tanto, me inclinaría a escribir la expresión de esta manera:

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

O si necesita a solo como un valor intermedio en el cálculo de b , entonces, declare que es un unsigned long para empezar.

Answer 2

P1: El enmascaramiento antes del turno evita el comportamiento indefinido que preocupa a OP.

P2: "... porque en cada plataforma el siguiente tipo entero es el doble del ancho?" -> no. El tipo entero "siguiente" podría ser menor que 2x o incluso del mismo tamaño.

Lo siguiente está bien definido para todos los compiladores C compatibles que tienen uint32_t .

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

Q3: uint32_t a; uint32_t b = (a & 1) << 31; uint32_t a; uint32_t b = (a & 1) << 31; no se espera que incurra en código que realice una máscara, no es necesario en el ejecutable, solo en la fuente. Si se produce una máscara, obtenga un mejor compilador en caso de que la velocidad sea un problema.

Como se suggested , es mejor enfatizar la falta de firma con estos cambios.

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

La buena respuesta de @John Bollinger detalla bien cómo manejar el problema específico de OP.

El problema general es cómo formar un número que tenga al menos n bits, un cierto signo y no esté sujeto a sorprendentes promociones de enteros, el núcleo del dilema de OP. Lo siguiente cumple con esto al invocar una operación unsigned que no cambia el valor, efectiva unsigned operaciones que no sean de tipo. El producto tendrá al menos el ancho de unsigned o uint32_t . La fundición, en general, puede reducir el tipo. Es necesario evitar el vaciado a menos que sea seguro que no se produzca el estrechamiento. Un compilador de optimización no creará código innecesario.

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

Answer 3

Para este segmento de código:

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

Para promover a tipo sin signo en lugar de un tipo con signo, use:

uint32_t b = a << 31u;

Cuando ambos lados del operador << son de tipo sin signo, se aplica esta línea en 6.3.1.8 (borrador estándar C n1570):

De lo contrario, si ambos operandos tienen tipos enteros con signo o ambos tienen tipos enteros sin signo, el operando con el tipo de rango de conversión de entero menor se convierte al tipo del operando con mayor rango.

El problema que está describiendo se debe a que usa 31 que está signed int type por lo que otra línea en 6.3.1.8

De lo contrario, si el tipo de operando con tipo entero con signo puede representar todos los valores del tipo de operando con tipo entero sin signo, entonces el operando con tipo entero sin signo se convierte en el tipo de operando con tipo entero con signo.

fuerza a a ascenso a un tipo firmado

Actualizar:

Esta respuesta no es correcta porque 6.3.1.1 (2) (énfasis mío):

...

Si un int puede representar todos los valores del tipo original (según lo restringido por el ancho, para un campo de bits), el valor se convierte en un int ; de lo contrario, se convierte en un int sin signo . Estas se denominan promociones enteras.58) Todos los demás tipos no cambian con las promociones enteras .

y nota 58 (énfasis mío):

58) Las promociones enteras solo se aplican: como parte de las conversiones aritméticas habituales, a ciertas expresiones de argumento, a los operandos de los operadores unarios +, - y ~, y a ambos operandos de los operadores de desplazamiento , según lo especificado por sus respectivos subcláusulas

Dado que solo está ocurriendo una promoción de enteros y no una conversión aritmética común, usar 31u no garantiza que se convierta a unsigned int como se indicó anteriormente.

Answer 4

Para evitar promociones no deseadas, puede usar el tipo mayor con algún tipo de definición, como

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

Answer 5

Tomando una pista de esta pregunta sobre la posible UB en la aritmética uint32 * uint32 , el siguiente enfoque simple debería funcionar en C y C ++:

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

La constante entera 0u tiene el tipo unsigned int . Esto promueve la adición de a + 0u uint32_t a uint32_t o unsigned int , lo que sea más ancho. Debido a que el tipo tiene un rango int o superior, no se produce más promoción y el cambio se puede aplicar con el operando izquierdo uint32_t o unsigned int .

La conversión final a uint32_t solo suprimirá posibles advertencias sobre una conversión de reducción (digamos si int es de 64 bits).

Un compilador decente de C debería poder ver que agregar cero es un no-op, que es menos oneroso que ver que una máscara previa no tiene efecto después de un cambio sin firmar.