imulq y detección de desbordamiento largo largo sin firmar en C y asm

5 minutos de lectura

imulq y deteccion de desbordamiento largo largo sin firmar en
cabeza

Como alguien nuevo en el ensamblaje, uso gcc para la ingeniería inversa. Pero ahora me encontré con un problema de alguna manera divertido: trato de multiplicar dos enteros de 64 bits por x86-64. El código C tiene el siguiente aspecto:

unsigned long long 
val(unsigned long long a, unsigned long long b){
    return a*b;
}

y compilado con gcc:

val:
    movq    %rdi, %rax
    imulq   %rsi, %rax
    ret

Puede ser contrario a la intuición usar la multiplicación con signo para enteros sin signo, pero funciona para C.

Sin embargo, me gustaría comprobar si hay desbordamientos en la multiplicación. Ahora, el indicador de desbordamiento se establece si el resultado es mayor que 2^63-1 (Supongo que porque después de todo es una multiplicación con signos). Pero para 64 bits sin firmar, esto seguiría siendo correcto siempre que el resultado no sea mayor que 2^64-1.

¿Cuál es la forma correcta de hacer la multiplicación (en conjunto) en este caso?

  • ¿Podría usted, tal vez, probar, después del hecho, para ver si el resultado es “(sin firmar…) más pequeño” de lo que solía ser? Solo adivinando…

    –Mike Robinson

    7 julio 2016 a las 19:25

  • O simplemente podrías usar mulque establece CF y OF si el resultado de la multiplicación sin signo desborda el tamaño del operando.

    – FEO

    7 julio 2016 a las 19:27

  • @ead: Porque imul hace lo mismo para n*n -> n-multiplicaciones de bits. También, mul sólo tiene una forma de un operando (utiliza [r/e]ax implícitamente) y siempre golpeando [r/e]ax y [r/e]dx. Es simplemente menos flexible.

    – FEO

    7 julio 2016 a las 19:38

  • En C, la multiplicación sin signo no se desborda. Si el resultado está fuera del rango del tipo sin signo, se ajusta descartando los bits de orden superior. Si desea verificar si fue necesario algún ajuste de este tipo, entonces está haciendo algo diferente a la multiplicación sin signo C. (Absolutamente no pretendo implicar que haya algo malo en eso).

    –Keith Thompson

    7 julio 2016 a las 20:15

  • @KeithThompson: “desbordamiento” se usa aquí para significar “envolver”, como si la mitad alta descartada no fuera cero. Es una de esas palabras que tiene al menos un significado técnico, pero se usa para otras cosas relacionadas que tienen diferentes nombres técnicos. (por ejemplo, llevar a cabo una adición sin firmar)

    – Peter Cordes

    7 julio 2016 a las 20:21

  • Estoy un poco confundido por tu último párrafo. Como es imul r64, 64 una mejor elección que mul r32 en la mayoría de las CPU, si es más lento en Atom y AMD? ¿Estoy leyendo eso mal?

    – Cody gris

    7 julio 2016 a las 20:27

  • @CodyGray: mul r32 tiene una sobrecarga adicional para mover los datos a los registros correctos. Esto compensa parte de la diferencia de velocidad en otras CPU. También, imul r64, r64 es más rápido en Intel moderno, es decir, “la mayoría de las CPU” que la gente está sintonizando. Quise decir “la mayoría de las CPU” como promedio ponderado por popularidad, no “la mayoría de los tipos de CPU”. IIRC, clang tiende a generar imul r64,r64 incluso si convierte dos variables de 32 bits a 64 bits.

    – Peter Cordes

    7 julio 2016 a las 20:32

  • @CodyGray: aunque, para ser honesto, los compiladores aparentemente se comportan de esa manera porque son tontos, no necesariamente porque sea mejor. Incluso con -march=bdver2 (es decir, AMD piledriver), uso de clang y gcc imul r64, r64. En realidad, incluso con -march=atom, donde es completamente horrible. Ah me acabo de dar cuenta mul r32 dejaría el resultado dividido entre dos registros. Hmm, no estoy seguro de si todavía hay un punto útil para hacer. Tal vez debería quitar ese último párrafo.

    – Peter Cordes

    7 julio 2016 a las 20:37

  • Sospecho que los compiladores prefieren imul r64, r64 porque facilita significativamente la asignación de registros. Pero ese también es un buen punto sobre dejar los resultados divididos entre dos registros. Sin duda, habría una penalización al fusionar esos dos resultados, y cuando hay registros de 64 bits disponibles, también podría usarlos desde el principio. Pero eso no importaría en el caso de que estuvieras multiplicando dos valores de 32 bits, porque los estándares del lenguaje C y C++ permiten que el compilador simplemente deseche los 32 bits superiores del resultado.

    – Cody gris

    7 julio 2016 a las 20:41


  • @CodyGray: imul r32,r32 es siempre al menos tan rápido como mul r32 en todas las CPU. Esto solo surge para los compiladores cuando saben que los multiplicandos son todos cero en sus 32 bits superiores (por ejemplo, después de un lanzamiento). Y sí, la fusión requiere SHL + OR. Creo que recuerdo probar lo que hicieron los compiladores, con algún código donde cualquiera de las dos era una opción válida. ¿Quizás almacenar los resultados en una estructura, donde era solo una tienda 64b frente a dos tiendas 32b? O con ORing en las mitades superior e inferior solo para obligar al compilador a combinarlas de cualquier manera.

    – Peter Cordes

    7 julio 2016 a las 20:52

  • Accidentalmente usaste la variante de 2 operandos allí

    – harold

    7 julio 2016 a las 20:02

  • @harold La variante de 2 operandos de IMUL fue intencional… No estoy multiplicando por un valor inmediato.

    – Cody gris

    7 julio 2016 a las 20:04

  • Pero entonces el resultado no es de 128 bits.

    – harold

    7 julio 2016 a las 20:05

  • xD, ambos publicamos nuestras respuestas con minutos de diferencia. Pero no necesitas poner a cero rdx delante de una multiplicación. Siempre es un operando de solo escritura. Entonces mov rax, [a] / imul rax, [b] funcionaría, excepto por el error que señaló Harold. (Donde realmente necesita la forma de un operando mul [b].) O si realmente quiere probar la mitad superior manualmente, use mov rdx, [a] / mulx rsi, rdi, [b] / test rsi,rsi. (MULX está en IMC2)

    – Peter Cordes

    7 julio 2016 a las 20:11


  • Hmm, estaba pensando que la versión de dos operandos se comportaba de la misma manera que la versión de un operando, poniendo el resultado en RDX:RAX. Supongo que leí el manual demasiado rápido. Bueno, eso hace que la respuesta sea menos útil. Oh bien.

    – Cody gris

    7 julio 2016 a las 20:19


¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad