¿Qué operaciones de entero complementario de 2 se pueden usar sin poner a cero bits altos en las entradas, si solo se desea la parte baja del resultado?

En la progtwigción en ensamblador, es bastante común querer calcular algo a partir de los bits más bajos de un registro que no garantiza que los demás bits estén en cero. En lenguajes de nivel superior como C, simplemente debe convertir sus entradas al tamaño pequeño y dejar que el comstackdor 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 1 , algunas de las cuales están presentes en otras ISA.

Utilizaré 64bit x86 para 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 a dos 4 , y que el desbordamiento con signo es un comportamiento indefinido).

Como ejemplo, considere una función simple que puede comstackr a una instrucción LEA 2 . (En el x86-64 SysV (Linux) ABI 3 , los primeros dos rsi funciones 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 sum, incluso de los 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 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 depende de los bits altos de las entradas?

¿Y por qué funciona?



Notas a pie de página

1 Por qué 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 guardar un byte a menudo es posible en instrucciones que de otro modo ejecutado a la misma velocidad. También tiene dependencias falsas (AMD / P4 / Silvermont) al escribir el bajo 8b o 16b de un registro (o un locking cuando luego lee el registro completo (Intel pre-IvB)): por razones históricas, solo escribe en el sub 32b -registra a cero el rest del registro 64b . Casi todas las operaciones aritméticas y lógicas se pueden usar en los 8, 16 o 32 bits bajos, así como en los 64 bits completos, de los registros de propósito general. Las instrucciones de vector entero también son bastante no ortogonales, con algunas operaciones no disponibles para algunos tamaños de elemento.

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

2 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 tamaño del operando de salida sea 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 32bits (un acarreo no establece el bit 32 de rax ). lea eax, [rdx+rsi] 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.

3 x86 ABI : la persona que llama no tiene que poner a cero (o extender la extensión) 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 quería usar el valor de retorno como un índice de matriz tendría que firmar-extenderlo (con movzx rax, eax , o la instrucción especial case-for-eax cdqe . ( cdqe no debe confundirse con cdq , que cdq extiende eax a edx:eax por ej. para configurar para idiv .))

Esto significa que una función que devuelve unsigned int puede calcular su valor de retorno en un rax 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 .


4 C y C ++

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

Sin embargo, los ataques de bits que solo funcionan con el complemento de dos están muy extendidos , porque en la práctica a nadie le importa nada más. Muchas cosas que funcionan con complemento a 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: simplemente tiene un valor de – (2 N -1) (en lugar de 2 N ). La representación de signo / magnitud no tiene esta propiedad: el valor de lugar de cada bit es positivo o negativo según el bit de signo.

También tenga en cuenta que los comstackdores C pueden suponer que el desbordamiento firmado nunca ocurre , porque es un comportamiento indefinido. Entonces, por ejemplo, los comstackdores pueden y deben asumir (x+1) < x siempre es falso . Esto hace que la detección del desbordamiento firmado sea poco conveniente en C. Tenga en cuenta que la diferencia entre el envolvente sin signo (acarreo) y el desbordamiento firmado .

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

  • lógica de bit a bit
  • cambio a la izquierda (incluida la *scale en [reg1 + reg2*scale + disp] )
  • adición / sustracción (y, por lo tanto, instrucciones LEA : nunca se necesita el prefijo de tamaño de dirección. Simplemente use el tamaño de operando deseado para truncar, si es necesario).
  • La mitad baja de un multiplicar por ejemplo, 16b x 16b -> 16b se puede hacer con 32b x 32b -> 32b. Puede evitar lockings de LCP (y problemas de registro parcial) desde 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 imul r32, r/m32, imm32 bajos del resultado. (Tenga cuidado con m32 memoria más amplios si usa la versión m32 , sin embargo).

    Como se señala en el manual de insn ref de Intel, las formas de 2 y 3 operandos de imul son seguras para su uso en enteros sin signo. Los bits de signo de las entradas no afectan los N bits del resultado en un multiplicador de N x N -> N

  • 2 x (es decir, cambiar por x ): funciona al menos en x86, donde el recuento de turnos está enmascarado, en lugar de saturado, hasta el ancho de la operación, por lo que la basura alta en ecx , o incluso los bits altos de cl no lo hacen t afecta el recuento de turnos. También se aplica a los cambios sin indicador BMI2 ( shlx etc.), pero no a los cambios vectoriales ( pslld xmm, xmm/m128 etc., que saturan el recuento). Los comstackdores inteligentes optimizan el enmascaramiento de la cuenta de turnos, lo que permite una expresión segura para que gire en C (sin un 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 incluso afecta a 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 las 16 entradas superiores estén sin signo o con signo extendido antes de hacer un 32b x 32b -> 32b imul . O utilice un mul o imul un solo operando de 16 bits para poner inconvenientemente el resultado en dx:ax . (La elección de instrucción con signo o sin signo afectará a la parte superior 16b de la misma manera que a cero o extensión de signo antes de una imul 32b).

  • direccionamiento de memoria ( [rsi + rax] ): firmar o extender cero según sea necesario. No hay modo de direccionamiento [rsi + eax] .

  • división y rest

  • log2 (es decir, la posición del bit de ajuste más alto)
  • conteo final cero (a menos que sepa que hay un bit determinado en algún lugar de la pieza que desea, o simplemente verifique si el resultado es más grande que N, ya que no lo encontró).

El complemento de dos, como la base 2 sin signo, es un sistema de valor de posición. El MSB para base2 sin signo tiene un valor de posición de 2 N-1 en un número de N bits (por ejemplo, 2 31 ). En el complemento a 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 anular un número base2 sin firmar.

El punto clave es que tener el bit de signo configurado no cambia la interpretación de los otros bits . La sum y la resta funcionan exactamente igual que para la base2 sin signo, y solo la interpretación del resultado es diferente entre firmado y sin signo. (Por ejemplo, el desbordamiento firmado ocurre cuando hay un acarreo adentro pero no fuera del bit de signo ).

Además, solo se propaga desde LSB a MSB (de derecha a izquierda). 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 se afectarán los bits altos. 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 superiores.

Por lo tanto, la sum y la resta tienen la propiedad de que los bits bajos del resultado no dependen de ningún bit superior de los operandos.

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

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


La multiplicación se puede considerar como una adición repetida, o como un cambio y una adición. La mitad inferior no se ve afectada por ningún bit superior. En este ejemplo de 4 bits, he escrito todos los productos de bit que se sumn en los 2 bits de resultado bajos. Solo los 2 bits bajos de cualquiera de las fonts están involucrados. Está claro que esto funciona en general: los productos parciales se desplazan antes de la sum, por lo que los bits altos en la fuente nunca afectan a los bits más bajos en el resultado en general.

Vea Wikipedia para una versión más grande de esto con una explicación mucho más detallada . Hay muchos buenos éxitos de Google para la multiplicación con signo binario , incluido algún material de enseñanza.

  *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 sigue dando 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 completa (y tal vez incluso tiene errores), pero hay buena evidencia de que es cierto y seguro 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 comstackdor Godbolt .

  • El manual de insn ref de Intel dice:

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

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

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