Noté que no hay tal pregunta, así que aquí está:

¿Tiene consejos generales para jugar golf en código máquina? Si el consejo solo se aplica a un determinado entorno o convención de llamadas, especifíquelo en su respuesta.

Por favor, solo un consejo por respuesta (ver aquí ).

mov-inmediato es caro para las constantes

Esto puede ser obvio, pero aún lo pondré aquí. En general, vale la pena pensar en la representación a nivel de bit de un número cuando necesita inicializar un valor.

Inicializando eaxcon 0:

b8 00 00 00 00          mov    $0x0,%eax

debe acortarse ( para el rendimiento y el tamaño del código ) a

31 c0                   xor    %eax,%eax

Inicializando eaxcon -1:

b8 ff ff ff ff          mov    $-1,%eax

se puede acortar a

31 c0                   xor    %eax,%eax
48                      dec    %eax

o

83 c8 ff                or     $-1,%eax

O, más generalmente, cualquier valor de signo extendido de 8 bits se puede crear en 3 bytes con push -12(2 bytes) / pop %eax(1 byte). Esto incluso funciona para registros de 64 bits sin prefijo REX adicional; push/ popdefault operand-size = 64.

6a f3                   pushq  $0xfffffffffffffff3
5d                      pop    %rbp

O dada una constante conocida en un registro, puede crear otra constante cercana usando lea 123(%eax), %ecx(3 bytes). Esto es útil si necesita un registro a cero y una constante; xor-zero (2 bytes) + lea-disp8(3 bytes).

31 c0                   xor    %eax,%eax
8d 48 0c                lea    0xc(%eax),%ecx

Consulte también Establecer todos los bits en el registro de CPU en 1 de manera eficiente

En muchos casos, las instrucciones basadas en acumuladores (es decir, las que toman (R|E)AXcomo operando de destino) son 1 byte más cortas que las instrucciones de caso general; vea esta pregunta en StackOverflow.

Elija su convención de llamadas para colocar los argumentos donde desee.

El lenguaje de su respuesta es asm (en realidad código de máquina), así que trátelo como parte de un programa escrito en asm, no C-compilado-para-x86. Su función no tiene que ser fácilmente invocable desde C con ninguna convención de llamada estándar. Sin embargo, es una buena ventaja si no le cuesta bytes adicionales.

En un programa asm puro, es normal que algunas funciones auxiliares utilicen una convención de llamadas que sea conveniente para ellos y para su interlocutor. Dichas funciones documentan su convención de llamada (entradas / salidas / clobbers) con comentarios.

En la vida real, incluso los programas asm (creo) tienden a usar convenciones de llamadas consistentes para la mayoría de las funciones (especialmente en diferentes archivos fuente), pero cualquier función importante podría hacer algo especial. En code-golf, está optimizando la basura de una sola función, por lo que obviamente es importante / especial.

Para probar su función desde un programa en C, puede escribir una envoltura que coloque los argumentos en los lugares correctos, guarde / restaure cualquier registro adicional que haya marcado y coloque el valor de retorno e/raxsi aún no estaba allí.

Los límites de lo que es razonable: cualquier cosa que no imponga una carga irrazonable a la persona que llama:

• ESP / RSP debe conservarse en llamada; otros registros enteros son juegos justos. (RBP y RBX generalmente se conservan en las llamadas en las convenciones normales, pero podría golpear ambas).
• Cualquier argumento en cualquier registro (excepto RSP) es razonable, pero pedirle a la persona que llama que copie el mismo argumento en varios registros no lo es.

• Requerir que DF (indicador de dirección de cadena para lods/ stos/ etc.) esté despejado (hacia arriba) en la llamada / ret es normal. Dejarlo sin definir en call / ret estaría bien. Requerir que se borre o establecer en la entrada, pero luego dejarlo modificado cuando regrese sería extraño.

• Devolver los valores de FP en x87 st0es razonable, pero regresar st3con basura en otro registro x87 no lo es. La persona que llama tendría que limpiar la pila x87. Incluso regresar st0con registros de pila más altos no vacíos también sería cuestionable (a menos que esté devolviendo valores múltiples).

• Se llamará a su función call, al igual [rsp]que su dirección de devolución. Usted puede evitar call/ retx86 usando registro de enlace como lea rbx, [ret_addr]/ jmp functiony de retorno con jmp rbx, pero eso no es "razonable". Eso no es tan eficiente como call / ret, por lo que no es algo que posiblemente encuentre en el código real.
• El bloqueo de memoria ilimitada por encima de RSP no es razonable, pero el bloqueo de sus argumentos de función en la pila está permitido en las convenciones de llamadas normales. x64 Windows requiere 32 bytes de espacio en la sombra por encima de la dirección de retorno, mientras que x86-64 System V le ofrece una zona roja de 128 bytes por debajo de RSP, por lo que cualquiera de los dos es razonable. (O incluso una zona roja mucho más grande, especialmente en un programa independiente en lugar de funcionar).

Casos límite: escriba una función que produzca una secuencia en una matriz, dados los primeros 2 elementos como argumentos de función . Elegí que la persona que llama almacenara el inicio de la secuencia en la matriz y simplemente pasara un puntero a la matriz. Esto definitivamente está doblando los requisitos de la pregunta. Consideré tomar los argumentos empaquetados en xmm0para movlps [rdi], xmm0, que también sería una convención de llamada extraña.

Devuelve un booleano en BANDERAS (códigos de condición)

Las llamadas al sistema OS X hacen esto ( CF=0significa que no hay error): ¿se considera una mala práctica usar el registro de banderas como un valor de retorno booleano? .

Cualquier condición que pueda verificarse con un JCC es perfectamente razonable, especialmente si puede elegir una que tenga alguna relevancia semántica para el problema. (por ejemplo, una función de comparación podría establecer marcas, por jnelo que se tomarán si no fueran iguales).

Exigir args estrechos (como a char) para ser signo o cero extendido a 32 o 64 bits.

Esto no es irrazonable; usar movzxo movsx para evitar ralentizaciones de registro parcial es normal en el x86 asm moderno. De hecho, clang / LLVM ya crea un código que depende de una extensión no documentada de la convención de llamadas del Sistema V x86-64: los argumentos más estrechos que 32 bits son signos o cero extendido a 32 bits por el llamante .

Puede documentar / describir la extensión a 64 bits escribiendo uint64_to int64_ten su prototipo si lo desea. por ejemplo, puede usar una loopinstrucción, que usa los 64 bits completos de RCX a menos que use un prefijo de tamaño de dirección para anular el tamaño hasta ECX de 32 bits (sí, realmente, el tamaño de la dirección no es el tamaño del operando).

Tenga en cuenta que longsolo es un tipo de 32 bits en Windows ABI de 64 bits y Linux x32 ABI ; uint64_tes inequívoco y más corto de escribir que unsigned long long.

Convenciones de llamadas existentes:

• Windows de 32 bits __fastcall, ya sugerido por otra respuesta : arger entero ecxy edx.

• x86-64 System V : pasa muchos argumentos en los registros y tiene muchos registros de llamadas que puede usar sin prefijos REX. Más importante aún, en realidad se eligió para permitir que los compiladores en línea memcpyo memset con la misma rep movsbfacilidad: los primeros 6 argumentos enteros / puntero se pasan en RDI, RSI, RDX, RCX, R8, R9.

  Si su función usa lodsd/ stosddentro de un ciclo que ejecuta rcxtiempos (con la loopinstrucción), puede decir "invocable desde C como int foo(int *rdi, const int *rsi, int dummy, uint64_t len)con la convención de llamadas del sistema V x86-64". ejemplo: chromakey .

• GCC de 32 bits regparm: argumentos enteros en EAX , ECX, EDX, retorno en EAX (o EDX: EAX). Tener el primer argumento en el mismo registro que el valor de retorno permite algunas optimizaciones, como este caso con un llamador de ejemplo y un prototipo con un atributo de función . Y, por supuesto, AL / EAX es especial para algunas instrucciones.

• El Linux x32 ABI utiliza punteros de 32 bits en modo largo, por lo que puede guardar un prefijo REX al modificar un puntero (por ejemplo, caso de uso ). Todavía puede usar un tamaño de dirección de 64 bits, a menos que tenga un entero negativo de 32 bits con cero extendido en un registro (por lo que sería un gran valor sin signo si lo hiciera [rdi + rdx]).

  Tenga en cuenta que push rsp/ pop raxes de 2 bytes, y equivalente a mov rax,rsp, por lo que aún puede copiar registros completos de 64 bits en 2 bytes.

Utilice codificaciones de forma corta de casos especiales para AL / AX / EAX y otras formas cortas e instrucciones de un solo byte

Los ejemplos suponen el modo de 32/64 bits, donde el tamaño de operando predeterminado es de 32 bits. Un prefijo de tamaño de operando cambia la instrucción a AX en lugar de EAX (o al revés en modo de 16 bits).

• inc/decun registro (que no sea de 8 bits): inc eax/ dec ebp. (No x86-64: los 0x4xbytes del código de operación se reutilizaron como prefijos REX, por lo que inc r/m32es la única codificación).

  8 bits inc bles de 2 bytes, utilizando el inc r/m8código de operación + Modr / M operando codifica . Así que usa inc ebxpara incrementar bl, si es seguro. (por ejemplo, si no necesita el resultado ZF en los casos en que los bytes superiores pueden ser distintos de cero).

• scasd: e/rdi+=4, requiere que el registro apunte a memoria legible. A veces es útil incluso si no te importa el resultado de FLAGS (como cmp eax,[rdi]/ rdi+=4). Y en el modo de 64 bits, scasbpuede funcionar como un byteinc rdi , si lodsb o stosb no son útiles.

• xchg eax, r32: Aquí es donde 0x90 NOP vino de: xchg eax,eax. Ejemplo: reorganice 3 registros con dos xchginstrucciones en un bucle cdq/ para GCD en 8 bytes, donde la mayoría de las instrucciones son de un solo byte, incluido un abuso de / en lugar de /idivinc ecxlooptest ecx,ecxjnz

• cdq: firma-extiende EAX en EDX: EAX, es decir, copia el bit alto de EAX a todos los bits de EDX. Para crear un cero con no negativo conocido, o para obtener un 0 / -1 para agregar / sub o enmascarar. Lección de historia x86: cltqvs.movslq , y también AT&T vs. Intel mnemonics para esto y lo relacionado cdqe.

• lodsb / d : como mov eax, [rsi]/ rsi += 4sin banderas de golpeteo. (Suponiendo que DF es claro, qué convenciones de llamada estándar requieren en la entrada de funciones). También stosb / d, a veces scas, y más raramente movs / cmps.

• push/ pop reg. por ejemplo, en modo de 64 bits, push rsp/ pop rdies de 2 bytes, pero mov rdi, rspnecesita un prefijo REX y es de 3 bytes.

xlatbexiste, pero rara vez es útil. Una tabla de búsqueda grande es algo que debe evitarse. Tampoco he encontrado un uso para AAA / DAA u otras instrucciones BCD empaquetadas o de 2 dígitos ASCII.

1 byte lahf/ sahfrara vez son útiles. Usted pude lahf / and ah, 1como una alternativa a setc ah, pero no es generalmente útil.

Y para CF específicamente, hay sbb eax,eaxque obtener un 0 / -1, o incluso 1-byte no documentado pero universalmente compatible salc(establecer AL desde Carry) que efectivamente lo hace sbb al,alsin afectar a las banderas. (Eliminado en x86-64). Usé SALC en el Desafío de apreciación del usuario # 1: Dennis ♦ .

1 byte cmc/ clc/ stc(flip ("complemento"), clear o set CF) rara vez son útiles, aunque encontré un uso para lacmc adición de precisión extendida con trozos de base 10 ^ 9. Para configurar / borrar incondicionalmente la CF, generalmente haga los arreglos para que eso suceda como parte de otra instrucción, por ejemplo, xor eax,eaxborra CF y EAX. No hay instrucciones equivalentes para otros indicadores de condición, solo DF (dirección de la cadena) e IF (interrupciones). La bandera de transporte es especial para muchas instrucciones; los cambios lo establecen, adc al, 0pueden agregarlo a AL en 2 bytes, y mencioné anteriormente el SALC indocumentado.

std/ cldParecer rara vez vale la pena . Especialmente en el código de 32 bits, es mejor usarlo decen un puntero y un movoperando fuente de memoria para una instrucción ALU en lugar de configurar DF ​​así lodsb/ stosbir hacia abajo en lugar de hacia arriba. Por lo general, si necesita algo hacia abajo, todavía tiene otro puntero hacia arriba, por lo que necesitaría más de uno stdy clden toda la función para usar lods/ stospara ambos. En cambio, solo use las instrucciones de la cuerda para la dirección hacia arriba. (Las convenciones de llamada estándar garantizan DF = 0 en la entrada de función, por lo que puede suponer que es gratis sin usar cld).

Historia de 8086: por qué existen estas codificaciones

En el original 8086, AX fue muy especial: instrucciones como lodsb/ stosb, cbw, mul/ divy otros lo utilizan de forma implícita. Ese sigue siendo el caso, por supuesto; x86 actual no ha eliminado ninguno de los códigos de operación de 8086 (al menos ninguno de los documentados oficialmente). Pero las CPU posteriores agregaron nuevas instrucciones que dieron formas mejores / más eficientes de hacer las cosas sin copiarlas o cambiarlas primero a AX. (O a EAX en modo de 32 bits).

por ejemplo, 8086 careció de adiciones posteriores como movsx/ movzxpara cargar o mover + signo-extender, o 2 y 3 operandos imul cx, bx, 1234que no producen un resultado de mitad alta y no tienen ningún operando implícito.

Además, el principal cuello de botella de 8086 era la búsqueda de instrucciones, por lo que la optimización del tamaño del código era importante para el rendimiento en ese momento . El diseñador ISA de 8086 (Stephen Morse) gastó mucho espacio de codificación de código de operación en casos especiales para AX / AL, incluyendo códigos de operación especiales (E) AX / AL-destino para todas las instrucciones básicas de ALU de src inmediato inmediato , solo código de operación + inmediato sin byte ModR / M. 2 bytes add/sub/and/or/xor/cmp/test/... AL,imm8o AX,imm16o (en modo de 32 bits) EAX,imm32.

Pero no hay un caso especial EAX,imm8, por lo que la codificación ModR / M normal de add eax,4es más corta.

La suposición es que si va a trabajar en algunos datos, lo querrá en AX / AL, por lo que intercambiar un registro con AX es algo que quizás desee hacer, tal vez incluso con más frecuencia que copiar un registro en AX con mov.

Todo lo relacionado con la codificación de instrucciones 8086 admite este paradigma, desde instrucciones como lodsb/wtodas las codificaciones de casos especiales para inmediatos con EAX hasta su uso implícito incluso para multiplicar / dividir.

No te dejes llevar; No es automáticamente una victoria cambiar todo a EAX, especialmente si necesita usar inmediatos con registros de 32 bits en lugar de 8 bits. O si necesita intercalar operaciones en múltiples variables en registros a la vez. O si está utilizando instrucciones con 2 registros, no inmediatamente.

Pero siempre tenga en cuenta: ¿estoy haciendo algo que sería más corto en EAX / AL? ¿Puedo reorganizar para que tenga esto en AL, o estoy aprovechando mejor AL con lo que ya estoy usando?

Mezcle operaciones de 8 bits y 32 bits libremente para aprovechar cada vez que sea seguro hacerlo (no es necesario llevarlo a cabo en el registro completo o lo que sea).

Usar fastcallconvenciones

la plataforma x86 tiene muchas convenciones de llamadas . Debe usar aquellos que pasan parámetros en registros. En x86_64, los primeros parámetros se pasan de todos modos en los registros, por lo que no hay problema. En las plataformas de 32 bits, la convención de llamada predeterminada ( cdecl) pasa los parámetros en la pila, lo que no es bueno para el golf: el acceso a los parámetros en la pila requiere instrucciones largas.

Cuando usas fastcall en plataformas de 32 bits, generalmente se pasan 2 primeros parámetros ecxy edx. Si su función tiene 3 parámetros, puede considerar implementarla en una plataforma de 64 bits.

Prototipos de función C para fastcallconvención (tomado de esta respuesta de ejemplo ):

extern int __fastcall SwapParity(int value);                 // MSVC
extern int __attribute__((fastcall)) SwapParity(int value);  // GNU   

Resta -128 en lugar de sumar 128

0100 81C38000      ADD     BX,0080
0104 83EB80        SUB     BX,-80

Del mismo modo, agregue -128 en lugar de restar 128

Cree 3 ceros con mul(luego inc/ decpara obtener +1 / -1 y cero)

Puede cero eax y edx multiplicando por cero en un tercer registro.

xor   ebx, ebx      ; 2B  ebx = 0
mul   ebx           ; 2B  eax=edx = 0

inc   ebx           ; 1B  ebx=1

dará como resultado que EAX, EDX y EBX sean cero en solo cuatro bytes. Puede poner a cero EAX y EDX en tres bytes:

xor eax, eax
cdq

Pero desde ese punto de partida no puede obtener un tercer registro a cero en un byte más, o un registro +1 o -1 en otros 2 bytes. En su lugar, use la técnica mul.

Ejemplo de caso de uso: concatenación de los números de Fibonacci en binario .

Tenga en cuenta que después de que LOOPfinalice un bucle, ECX será cero y puede usarse para cero EDX y EAX; no siempre tiene que crear el primer cero con xor.

Los registros y las banderas de la CPU están en estados de inicio conocidos

Podemos suponer que la CPU está en un estado predeterminado conocido y documentado basado en la plataforma y el sistema operativo.

Por ejemplo:

DOS http://www.fysnet.net/yourhelp.htm

Linux x86 ELF http://asm.sourceforge.net/articles/startup.html

Para sumar o restar 1, use un byte inco decinstrucciones que son más pequeñas que las instrucciones de sumar y sub multibyte.

lea para las matemáticas

Esta es probablemente una de las primeras cosas que uno aprende sobre x86, pero lo dejo aquí como recordatorio. lease puede usar para multiplicar por 2, 3, 4, 5, 8 o 9 y agregar un desplazamiento.

Por ejemplo, para calcular ebx = 9*eax + 3en una instrucción (en modo de 32 bits):

8d 5c c0 03             lea    0x3(%eax,%eax,8),%ebx

Aquí está sin compensación:

8d 1c c0                lea    (%eax,%eax,8),%ebx

¡Guauu! Por supuesto, también lease puede utilizar para hacer cálculos matemáticos ebx = edx + 8*eax + 3para calcular la indexación de matrices.

Las instrucciones de bucle y cadena son más pequeñas que las secuencias de instrucciones alternativas. Lo más útil es loop <label>cuál es más pequeño que la secuencia de dos instrucciones dec ECXy jnz <label>, y lodsbes más pequeño que mov al,[esi]y inc si.

mov los pequeños aparecen inmediatamente en los registros inferiores cuando corresponde

Si ya sabe que los bits superiores de un registro son 0, puede usar una instrucción más corta para mover un inmediato a los registros inferiores.

b8 0a 00 00 00          mov    $0xa,%eax

versus

b0 0a                   mov    $0xa,%al

Use push/ poppara imm8 a cero bits superiores

Crédito a Peter Cordes. xor/ moves 4 bytes, pero push/ popes solo 3!

6a 0a                   push   $0xa
58                      pop    %eax

Las banderas se configuran después de muchas instrucciones.

Después de muchas instrucciones aritméticas, el indicador de transporte (sin firmar) y el indicador de desbordamiento (firmado) se configuran automáticamente ( más información ). El indicador de signo y el indicador de cero se establecen después de muchas operaciones aritméticas y lógicas. Esto se puede usar para la ramificación condicional.

Ejemplo:

d1 f8                   sar    %eax

ZF se establece mediante esta instrucción, por lo que podemos usarlo para la ramificación condicional.

Use bucles do-while en lugar de bucles while

Esto no es específico para x86, pero es una sugerencia de ensamblaje para principiantes ampliamente aplicable. Si sabe que un ciclo while se ejecutará al menos una vez, reescribiendo el ciclo como un ciclo do-while, con la comprobación de la condición del ciclo al final, a menudo guarda una instrucción de salto de 2 bytes. En un caso especial, incluso podría usarlo loop.

Use las convenciones de llamadas convenientes

Sistema V x 86 utiliza el sistema de pila y V x86-64 usos rdi, rsi, rdx, rcx, etc., para los parámetros de entrada, y raxcomo valor de retorno, pero es perfectamente razonable utilizar su propia convención de llamada. __fastcall usa ecxy edxcomo parámetros de entrada, y otros compiladores / sistemas operativos usan sus propias convenciones . Use la pila y lo que sea que se registre como entrada / salida cuando sea conveniente.

Ejemplo: el contador de bytes repetitivo , utilizando una convención de llamada inteligente para una solución de 1 byte.

Meta: escritura de entrada en registros , escritura de salida en registros

Otros recursos: notas de Agner Fog sobre convenciones de llamadas

Usa movimientos CMOVccy conjuntos condicionalesSETcc

Esto es más un recordatorio para mí, pero existen instrucciones de conjuntos condicionales y existen instrucciones de movimiento condicionales en los procesadores P6 (Pentium Pro) o posteriores. Hay muchas instrucciones que se basan en uno o más de los indicadores establecidos en EFLAGS.

Ahorrar en jmp bytes organizando en if / then en lugar de if / then / else

Esto es ciertamente muy básico, solo pensé en publicar esto como algo en lo que pensar al jugar golf. Como ejemplo, considere el siguiente código directo para decodificar un carácter de dígito hexadecimal:

    cmp $'A', %al
    jae .Lletter
    sub $'0', %al
    jmp .Lprocess
.Lletter:
    sub $('A'-10), %al
.Lprocess:
    movzbl %al, %eax
    ...

Esto puede acortarse en dos bytes dejando que un caso "entonces" caiga en un caso "else":

    cmp $'A', %al
    jb .digit
    sub $('A'-'0'-10), %eax
.digit:
    sub $'0', %eax
    movzbl %al, %eax
    ...

Puede obtener objetos secuenciales de la pila configurando esi en esp, y realizando una secuencia de lodsd / xchg reg, eax.

Para codegolf y ASM: use las instrucciones, use solo registros, presione pop, minimice la memoria de registro o la memoria inmediata

Para copiar un registro de 64 bits, use push rcx; pop rdxen lugar de un 3 byte mov.
El tamaño de operando predeterminado de push / pop es de 64 bits sin necesidad de un prefijo REX.

  51                      push   rcx
  5a                      pop    rdx
                vs.
  48 89 ca                mov    rdx,rcx

(Un prefijo de tamaño de operando puede anular el tamaño push / pop a 16 bits, pero el tamaño de operando push / pop de 32 bits no se puede codificar en modo de 64 bits, incluso con REX.W = 0).

Si uno o ambos registros son r8... r15, úselos movporque push y / o pop necesitarán un prefijo REX. En el peor de los casos, esto realmente pierde si ambos necesitan prefijos REX. Obviamente, normalmente debe evitar r8..r15 de todos modos en el código de golf.

Puede mantener su fuente más legible mientras se desarrolla con esto macro NASM . Solo recuerda que pisa los 8 bytes debajo de RSP. (En la zona roja en x86-64 System V). Pero en condiciones normales es un reemplazo directo para 64 bits mov r64,r64omov r64, -128..127

    ; mov  %1, %2       ; use this macro to copy 64-bit registers in 2 bytes (no REX prefix)
%macro MOVE 2
    push  %2
    pop   %1
%endmacro

Ejemplos:

   MOVE  rax, rsi            ; 2 bytes  (push + pop)
   MOVE  rbp, rdx            ; 2 bytes  (push + pop)
   mov   ecx, edi            ; 2 bytes.  32-bit operand size doesn't need REX prefixes

   MOVE  r8, r10             ; 4 bytes, don't use
   mov   r8, r10             ; 3 bytes, REX prefix has W=1 and the bits for reg and r/m being high

   xchg  eax, edi            ; 1 byte  (special xchg-with-accumulator opcodes)
   xchg  rax, rdi            ; 2 bytes (REX.W + that)

   xchg  ecx, edx            ; 2 bytes (normal xchg + modrm)
   xchg  rcx, rdx            ; 3 bytes (normal REX + xchg + modrm)

La xchgparte del ejemplo es porque a veces necesita obtener un valor en EAX o RAX y no le importa preservar la copia anterior. Sin embargo, push / pop no te ayuda a intercambiar.