assembly - carry - ¿Qué operaciones de enteros complementarios de 2 se pueden usar sin poner a cero los bits altos en las entradas, si solo se desea la parte baja del resultado?

carry flag (1)

Amplias operaciones que se pueden usar con basura en bits superiores:

lógicas bit a bit
desplazamiento a la izquierda (incluida la *scale en [reg1 + reg2*scale + disp] )
suma / resta (y, por lo tanto, instrucciones LEA : el prefijo de tamaño de dirección nunca es necesario. Solo use el tamaño de operando deseado para truncar si es necesario).
La mitad baja de una multiplicación. Por ejemplo, 16b x 16b -> 16b se puede hacer con un 32b x 32b -> 32b. Puede evitar los bloqueos de LCP (y los problemas de registro parcial) de imul r16, r/m16, imm16 utilizando un imul r32, r/m32, imm32 imul r16, r/m16, imm16 de 32 bits imul r32, r/m32, imm32 y luego leyendo solo los 16 bajos del resultado. ( m32 embargo, tenga cuidado con las referencias de memoria más amplias si usa la versión m32 ).

Como lo señala el manual de referencia de Intel, las formas de imul operando 2 y 3 son seguras para su uso en enteros sin signo. Los bits de signo de las entradas no afectan los N bits del resultado en una multiplicación N x N -> N bits).
2 ^x (es decir, desplazamiento por x ): funciona al menos en x86, donde el recuento de desplazamiento está enmascarado, en lugar de saturado, hasta el ancho de la operación, por lo que la basura es alta en ecx , o incluso los bits altos de cl , don '' t afecta el recuento de turnos. También se aplica a los cambios sin bandera BMI2 ( shlx etc.), pero no a los cambios de vectores ( pslld xmm, xmm/m128 , etc., que saturan el recuento). Los compiladores inteligentes optimizan el enmascaramiento del conteo de turnos, lo que permite un idioma seguro para las rotaciones en C (sin comportamiento indefinido) .

Obviamente, las banderas como carry / overflow / sign / zero se verán afectadas por la basura en bits altos de una operación más amplia. Los cambios de x86 ponen el último bit desplazado en la bandera de acarreo, por lo que esto incluso afecta los cambios.

Operaciones que no se pueden usar con basura en bits superiores:

Giro a la derecha
multiplicación completa: por ejemplo, para 16b x 16b -> 32b, asegúrese de que los 16 superiores de las entradas tengan extensión cero o de signo antes de hacer una imul 32b x 32b -> 32b. O use un mul o imul 16 bits de un operando para colocar el resultado en dx:ax . (La elección de la instrucción con signo versus sin signo afectará a los 16b superiores de la misma manera que la extensión de cero o de signo antes de un imul 32b).
direccionamiento de memoria ( [rsi + rax] ): signo o extensión cero según sea necesario. No hay modo de direccionamiento [rsi + eax] .
división y resto
log2 (es decir, la posición del bit de ajuste más alto)
recuento cero final (a menos que sepa que hay un bit establecido en algún lugar de la parte que desea, o simplemente verifique un resultado mayor que N, ya que no encontró la verificación).

El complemento a dos, como la base 2 sin signo, es un sistema de valor posicional. El MSB para base2 sin signo tiene un valor posicional de 2 ^N-1 en un número de N bits (por ejemplo, 2 ³¹ ). En el complemento de 2, el MSB tiene un valor de -2 ^N-1 (y por lo tanto funciona como un bit de signo). El artículo de Wikipedia explica muchas otras formas de entender el complemento de 2 y negar un número de base2 sin signo.

El punto clave es que tener el bit de signo establecido no cambia la interpretación de los otros bits . La suma y la resta funcionan exactamente igual que para uns2 base2, y es solo la interpretación del resultado lo que difiere entre firmado y sin signo. (Por ejemplo, el desbordamiento firmado se produce cuando hay un arrastre pero no fuera del bit de signo ).

Además, lleve propagados de LSB a MSB (de derecha a izquierda) solamente. La resta es la misma: independientemente de si hay algo en los bits altos para pedir prestado, los bits bajos lo toman prestado. Si eso causa un desbordamiento o arrastre, solo los bits altos se verán afectados. P.ej:

0x801F -0x9123 ------- 0xeefc

Los 8 bits bajos, 0xFC , no dependen de lo que pidieron prestado. Se "envuelven" y pasan el préstamo a los 8 bits superiores.

Por lo tanto, la suma y la resta tienen la propiedad de que los bits bajos del resultado no dependen de los bits superiores de los operandos.

Como LEA solo usa la suma (y el desplazamiento a la izquierda), usar el tamaño de dirección predeterminado siempre está bien. Retrasar el truncamiento hasta que el tamaño del operando entre en juego para el resultado siempre está bien.

(Excepción: el código de 16 bits puede usar un prefijo de tamaño de dirección para hacer cálculos de 32 bits. En el código de 32 bits o 64 bits, el prefijo de tamaño de dirección reduce el ancho en lugar de aumentarlo).

La multiplicación puede considerarse como una suma repetida o como un cambio y una suma. La mitad baja no se ve afectada por ninguna parte superior. En este ejemplo de 4 bits, he escrito todos los productos de bits que se suman en los 2 bits de resultado bajos. Solo están involucrados los 2 bits bajos de cualquiera de las fuentes. Está claro que esto funciona en general: los productos parciales se desplazan antes de la adición, por lo que los bits altos en la fuente nunca afectan a los bits inferiores en el resultado en general.

Ver Wikipedia para una versión más grande de esto con una explicación mucho más detallada . Hay muchos buenos resultados de Google para la multiplicación con signo binario , incluido material didáctico.

*Warning*: This diagram is probably slightly bogus. ABCD A has a place value of -2^3 = -8 * abcd a has a place value of -2^3 = -8 ------ RRRRrrrr AAAAABCD * d sign-extended partial products + AAAABCD * c + AAABCD * b - AABCD * a (a * A = +2^6, since the negatives cancel) ---------- D*d ^ C*d+D*c

Hacer una multiplicación con signo en lugar de una multiplicación sin signo todavía da el mismo resultado en la mitad baja (los 4 bits bajos en este ejemplo). La extensión de signo de los productos parciales solo ocurre en la mitad superior del resultado.

Esta explicación no es muy exhaustiva (y tal vez incluso tiene errores), pero hay buena evidencia de que es verdadera y segura de usar en el código de producción:

gcc usa imul para calcular el producto unsigned long de dos entradas unsigned long . Vea un ejemplo de esto de gcc aprovechando LEA para otras funciones en el explorador del compilador Godbolt .
El manual de referencia de Intel dice:

Las formas de dos y tres operandos también se pueden usar con operandos sin signo porque la mitad inferior del producto es la misma, independientemente de si los operandos están firmados o no. Sin embargo, los indicadores CF y OF no pueden usarse para determinar si la mitad superior del resultado no es cero.

La decisión de diseño de Intel de introducir solo 2 y 3 formas operando de imul , no mul .

Obviamente, las operaciones lógicas binarias bit a bit (y / o / xor / not) tratan cada bit de forma independiente: el resultado de una posición de bit depende solo del valor de las entradas en esa posición de bit. Los cambios de bits también son bastante obvios.

En la programación de ensamblaje, es bastante común querer calcular algo de los bits bajos de un registro que no garantiza que los otros bits estén a cero. En lenguajes de nivel superior como C, simplemente convierte sus entradas al tamaño pequeño y deja que el compilador decida si necesita poner a cero los bits superiores de cada entrada por separado, o si puede cortar los bits superiores del resultado después del hecho.

Esto es especialmente común para x86-64 (también conocido como AMD64), por varias razones ¹ , algunas de las cuales están presentes en otras ISA.

Usaré 64 bits x86 como ejemplos, pero la intención es preguntar sobre / discutir el complemento de 2 y la aritmética binaria sin signo en general, ya que todas las CPU modernas lo usan . (Tenga en cuenta que C y C ++ no garantizan el complemento ^{4 de} dos, y que el desbordamiento firmado es un comportamiento indefinido).

Como ejemplo, considere una función simple que puede compilarse en una instrucción LEA ² . (En el x86-64 SysV (Linux) ABI ³ , los dos primeros rsi función están en rsi y rsi , con el retorno en rax . int es un tipo de 32 bits).

; int intfunc(int a, int b) { return a + b*4 + 3; } intfunc: lea eax, [edi + esi*4 + 3] ; the obvious choice, but gcc can do better ret

gcc sabe que la suma, incluso de enteros con signo negativo, solo se transmite de derecha a izquierda, por lo que los bits superiores de las entradas no pueden afectar lo que entra en eax . Por lo tanto, guarda un byte de instrucción y usa lea eax, [rdi + rsi*4 + 3]

¿Qué otras operaciones tienen esta propiedad de los bits bajos del resultado que no dependen de los bits altos de las entradas?

¿Y por qué funciona?

Notas al pie

¹ Por qué esto aparece con frecuencia para x86-64 : x86-64 tiene instrucciones de longitud variable, donde un byte de prefijo adicional cambia el tamaño del operando (de 32 a 64 o 16), por lo que a menudo es posible guardar un byte en instrucciones que de otra manera ejecutado a la misma velocidad. También tiene dependencias falsas (AMD / P4 / Silvermont) al escribir los bajos 8b o 16b de un registro (o una parada cuando luego se lee el registro completo (Intel pre-IvB)): por razones históricas, solo escribe en 32b sub -registros cero el resto del registro 64b . Casi toda la aritmética y la lógica se pueden usar en los bajos 8, 16 o 32 bits, así como en los 64 bits completos de los registros de propósito general. Las instrucciones de vectores enteros también son bastante no ortogonales, con algunas operaciones no disponibles para algunos tamaños de elementos.

Además, a diferencia de x86-32, el ABI pasa argumentos de función en registros, y no se requiere que los bits superiores sean cero para los tipos estrechos.

² LEA: al igual que otras instrucciones, el tamaño de operando predeterminado de LEA es de 32 bits, pero el tamaño de dirección predeterminado es de 64 bits. Un byte de prefijo de tamaño de operando ( 0x66 o REX.W ) puede hacer que el operando de salida tenga un tamaño de 16 o 64 bits. Un byte de prefijo de tamaño de dirección ( 0x67 ) puede reducir el tamaño de la dirección a 32 bits (en modo de 64 bits) o 16 bits (en modo de 32 bits). Entonces, en el modo de 64 bits, lea eax, [edx+esi] toma un byte más que lea eax, [rdx+rsi] .

Es posible hacer lea rax, [edx+esi] , pero la dirección solo se calcula con 32 bits (un carry no establece el bit 32 de rax ). Obtiene resultados idénticos con lea eax, [rdx+rsi] , que es dos bytes más corto. Por lo tanto, el prefijo de tamaño de dirección nunca es útil con LEA , como advierten los comentarios en la salida de desensamblaje del excelente desensamblador objconv de Agner Fog.

³ x86 ABI : la persona que llama no tiene que poner a cero (o extender el signo) la parte superior de los registros de 64 bits utilizados para pasar o devolver tipos más pequeños por valor. Una persona que llama que quisiera usar el valor de retorno como un índice de matriz tendría que firmarlo-extenderlo (con movzx rax, eax , o la instrucción especial case-for-eax cdqe . (No debe confundirse con cdq , que firma- extiende eax a edx:eax por ejemplo, para configurar para idiv .))

Esto significa que una función que devuelve unsigned int puede calcular su valor de retorno en un temporal de 64 bits en rax , y no requiere un mov eax, eax para poner a cero los bits superiores de rax . Esta decisión de diseño funciona bien en la mayoría de los casos: a menudo, la persona que llama no necesita instrucciones adicionales para ignorar los bits indefinidos en la mitad superior de rax .

⁴ C y C ++

C y C ++ específicamente no requieren enteros binarios con signo del complemento a dos (excepto para std::atomic tipos std::atomic C ++ ). El complemento y el signo / magnitud también están permitidos , por lo que para C totalmente portátil, estos trucos solo son útiles con tipos unsigned . Obviamente, para operaciones con signo, un bit de signo establecido en la representación de signo / magnitud significa que los otros bits se restan, en lugar de sumar, por ejemplo. No he trabajado a través de la lógica para el complemento de uno

Sin embargo, bit-hacks que solo funcionan con el complemento de dos están widespread , porque en la práctica a nadie le importa nada más. Muchas cosas que funcionan con el complemento de dos también deberían funcionar con el complemento de uno, ya que el bit de signo todavía no cambia la interpretación de los otros bits: solo tiene un valor de - (2 ^N -1) (en lugar de 2 ^N ). La representación de signo / magnitud no tiene esta propiedad: el valor posicional de cada bit es positivo o negativo dependiendo del bit de signo.

También tenga en cuenta que los compiladores de C pueden asumir que el desbordamiento firmado nunca ocurre , porque es un comportamiento indefinido. Entonces, por ejemplo, los compiladores pueden asumir (x+1) < x siempre es falso . Esto hace que la detección de desbordamiento firmado sea bastante inconveniente en C. Tenga en cuenta que la diferencia entre envolvente sin signo (carry) y desbordamiento firmado .