Investigamos por todo internet para así regalarte la respuesta a tu problema, en caso de alguna duda puedes dejar un comentario y respondemos porque estamos para ayudarte.
Solución:
relacionado: versión de 16 bits que convierte 1 byte en 2 dígitos hexadecimales que puede imprimir o almacenar en un búfer. Y convertir bin a hexadecimal en ensamblado tiene otra versión de 16 bits con mucha explicación de texto en la mitad de la respuesta que cubre la parte int -> hex-string del problema.
Si optimiza el tamaño del código en lugar de la velocidad, hay un truco que usa DAS que ahorra unos pocos bytes.
16 es una potencia de 2. A diferencia de las bases decimales u otras que no son una potencia de 2, no necesitamos división, y podemos extraer el dígito más significativo primero (es decir, en orden de impresión). De lo contrario, solo podemos obtener primero el dígito menos significativo (y su valor depende de todos los bits del número) y tenemos que retroceder: consulte ¿Cómo imprimo un número entero en Programación a nivel de ensamblador sin printf de la biblioteca c? para bases sin potencia de 2.
Cada grupo de bits de 4 bits se asigna a un dígito hexadecimal. Podemos usar cambios o rotaciones, y máscaras Y, para extraer cada fragmento de 4 bits de la entrada como un entero de 4 bits.
Desafortunadamente, los dígitos hexadecimales 0..9 a..f no son contiguos en el juego de caracteres ASCII (http://www.asciitable.com/). Necesitamos un comportamiento condicional (una rama o cmov) o podemos usar una tabla de búsqueda.
Una tabla de búsqueda suele ser la más eficaz para el recuento y el rendimiento de las instrucciones, ya que lo hacemos repetidamente; Las CPU modernas tienen cachés L1d muy rápidos que hacen que las cargas repetidas de bytes cercanos sean muy económicas. La ejecución canalizada / desordenada oculta la latencia de ~ 5 ciclos de una carga de caché L1d.
;; NASM syntax, i386 System V calling convention
global itohex ; inputs: char* output, unsigned number
itohex:
push edi ; save a call-preserved register for scratch space
mov edi, [esp+8] ; out pointer
mov eax, [esp+12] ; number
mov ecx, 8 ; 8 hex digits, fixed width zero-padded
.digit_loop: ; do
rol eax, 4 ; rotate the high 4 bits to the bottom
mov edx, eax
and edx, 0x0f ; and isolate 4-bit integer in EDX
movzx edx, byte [hex_lut + edx]
mov [edi], dl ; copy a character from the lookup table
inc edi ; loop forward in the output buffer
dec ecx
jnz .digit_loop ; while(--ecx)
pop edi
ret
section .rodata
hex_lut: db "0123456789abcdef"
Para adaptarse a x86-64, la convención de llamada pasará argumentos en los registros en lugar de la pila, por ejemplo, RDI y ESI para x86-64 System V (no Windows). Simplemente elimine la parte que se carga de la pila y cambie el bucle para usar ESI en lugar de EAX. (Y haga que los modos de direccionamiento sean de 64 bits. Es posible que deba dejar el hex_lut dirección en un registro fuera del bucle; ver esto y esto).
Esta versión se convierte a hexadecimal con ceros a la izquierda. Si quieres dejarlos, bit_scan(input)/4 igual que lzcnt o __builtin_clz en la entrada, o SIMD compare -> pmovmksb -> tzcnt en la cadena ASCII de salida le dirá cuántos dígitos 0 tiene (y por lo tanto puede imprimir o copiar comenzando en el primer distinto de cero). O convierta comenzando con el nibble bajo y trabaje hacia atrás, deteniéndose cuando un cambio a la derecha hace que el valor sea cero, como se muestra en la segunda versión que usa cmov en lugar de una tabla de búsqueda.
Hasta el IMC2 (shrx / rorx), x86 carece de una instrucción de copiar y cambiar, por lo que rotar en el lugar y luego copiar / AND es difícil de superar1. El x86 moderno (Intel y AMD) tiene una latencia de 1 ciclo para rotaciones (https://agner.org/optimize/ y https://uops.info/), por lo que esta cadena de dependencia de bucle no se convierte en un cuello de botella. (Hay demasiadas instrucciones en el bucle para que se ejecute incluso en 1 ciclo por iteración, incluso en Ryzen de 5 anchos).
solía mov ecx,8 y dec ecx/jnz para la legibilidad humana; lea ecx, [edi+8] en la parte superior y cmp edi, ecx / jb .digit_loop ya que la rama del bucle tiene un tamaño de código de máquina general más pequeño y es más eficiente en más CPU. dec/jcc la macrofusión en un solo uop solo ocurre en la familia Intel Sandybridge; AMD solo fusiona jcc con cmp o test. Esta optimización lo reduciría a 7 uops para el front-end en Ryzen, al igual que Intel, que aún es más de lo que puede emitir en 1 ciclo.
Nota al pie 1: Podríamos usar SWAR (SIMD dentro de un registro) para hacer el AND antes de cambiar: x & 0x0f0f0f0f bocados bajos, y shr(x,4) & 0x0f0f0f0f bocados altos, luego desenrolle de manera efectiva alternando el procesamiento de un byte de cada registro. (Sin ninguna forma eficiente de hacer un equivalente de punpcklbw o mapeando enteros a los códigos ASCII no contiguos, todavía tenemos que hacer cada byte por separado. Pero podríamos desenrollar la extracción de bytes y leer AH y luego AL (con movzx) para guardar las instrucciones de turno. La lectura de registros de alto 8 puede agregar latencia, pero creo que no cuesta uops adicionales en las CPU actuales. Escribir registros de alto 8 generalmente no es bueno en las CPU de Intel: cuesta un uop de fusión adicional para leer el registro completo, con un retraso de front-end para insertarlo. Así que conseguir tiendas más amplias barajando los registros probablemente no sea bueno. En el código del kernel donde no puede usar los registros XMM, pero podría usar BMI2 si está disponible, pdep podría expandir nibbles a bytes, pero esto probablemente sea peor que solo enmascarar 2 formas).
Programa de prueba:
// hex.c converts argv[1] to integer and passes it to itohex
#include
#include
void itohex(char buf[8], unsigned num);
int main(int argc, char**argv)
unsigned num = strtoul(argv[1], NULL, 0); // allow any base
char buf[9] = 0;
itohex(buf, num); // writes the first 8 bytes of the buffer, leaving a 0-terminated C string
puts(buf);
compilar con:
nasm -felf32 -g -Fdwarf itohex.asm
gcc -g -fno-pie -no-pie -O3 -m32 hex.c itohex.o
ejecuciones de prueba:
$ ./a.out 12315
0000301b
$ ./a.out 12315123
00bbe9f3
$ ./a.out 999999999
3b9ac9ff
$ ./a.out 9999999999 # apparently glibc strtoul saturates on overflow
ffffffff
$ ./a.out 0x12345678 # strtoul with base=0 can parse hex input, too
12345678
Implementaciones alternativas:
Condicional en lugar de tabla de búsqueda: toma varias instrucciones más y probablemente sea más lento. Pero no necesita datos estáticos.
Se podría hacer con ramificaciones en lugar de cmov, pero eso sería incluso más lento la mayor parte del tiempo. (No predecirá bien, asumiendo una mezcla aleatoria de 0..9 y a..f dígitos). Https://codegolf.stackexchange.com/questions/193793/little-endian-number-to-string-conversion / 193842 # 193842 muestra una versión optimizada para el tamaño del código. (Aparte de un bswap al principio, es un uint32_t normal -> hexadecimal con relleno de ceros).
Solo por diversión, esta versión comienza al final del búfer y disminuye un puntero. (Y la condición de bucle usa una comparación de puntero). Puede hacer que se detenga una vez que EDX se convierta en cero, y use EDI + 1 como el comienzo del número, si no desea ceros a la izquierda.
Usando un cmp eax,9 / ja en lugar de cmov se deja como ejercicio para el lector. Una versión de 16 bits de esto podría usar diferentes registros (como tal vez BX como temporal) para permitir lea cx, [bx + 'a'-10] copiar y agregar. O solo add/cmp y jcc, si quieres evitar cmov para compatibilidad con CPU antiguas que no admiten extensiones P6.
;; NASM syntax, i386 System V calling convention
itohex: ; inputs: char* output, unsigned number
itohex_conditional:
push edi ; save a call-preserved register for scratch space
push ebx
mov edx, [esp+16] ; number
mov ebx, [esp+12] ; out pointer
lea edi, [ebx + 7] ; First output digit will be written at buf+7, then we count backwards
.digit_loop: ; do
mov eax, edx
and eax, 0x0f ; isolate the low 4 bits in EAX
lea ecx, [eax + 'a'-10] ; possible a..f value
add eax, '0' ; possible 0..9 value
cmp ecx, 'a'
cmovae eax, ecx ; use the a..f value if it's in range.
; for better ILP, another scratch register would let us compare before 2x LEA,
; instead of having the compare depend on an LEA or ADD result.
mov [edi], al ; *ptr-- = c;
dec edi
shr edx, 4
cmp edi, ebx ; alternative: jnz on flags from EDX to not write leading zeros.
jae .digit_loop ; while(ptr >= buf)
pop ebx
pop edi
ret
Podríamos exponer aún más ILP dentro de cada iteración usando 2x lea + cmp/cmov. cmp y ambas LEA solo dependen del valor del nibble, con cmov consumiendo los 3 de esos resultados. Pero hay muchos ILP en las iteraciones con solo el shr edx,4 y el puntero decrementa como dependencias de bucle. Podría haber ahorrado 1 byte de tamaño de código organizando para poder usar cmp al, 'a' o algo. Y / o add al,'0' si no me importaran las CPU que cambian el nombre de AL por separado de EAX.
Caso de prueba que verifica los errores de uno por uno usando un número que tiene ambos 9 y a en sus dígitos hexadecimales:
$ nasm -felf32 -g -Fdwarf itohex.asm && gcc -g -fno-pie -no-pie -O3 -m32 hex.c itohex.o && ./a.out 0x19a2d0fb
19a2d0fb
SIMD con SSE2, SSSE3, AVX2 o AVX512F y ~ 2 instrucciones con AVX512VBMI
Con SSSE3 y versiones posteriores, es mejor utilizar un byte shuffle como tabla de búsqueda nibble.
La mayoría de estas versiones SIMD podrían usarse con dos enteros empaquetados de 32 bits como entrada, con los 8 bytes bajos y altos del vector de resultados que contienen resultados separados que puede almacenar por separado con movq y movhps. Dependiendo de su control de reproducción aleatoria, esto es exactamente como usarlo para un entero de 64 bits.
SSSE3 pshufb tabla de búsqueda paralela. No es necesario perder el tiempo con los bucles, podemos hacer esto con algunas operaciones SIMD, en CPU que tienen pshufb. (SSSE3 no es la base ni siquiera para x86-64; era nuevo con Intel Core2 y AMD Bulldozer).
pshufb es un byte shuffle controlado por un vector, no inmediato (a diferencia de todos los shuffles SSE1 / SSE2 / SSE3 anteriores). Con un destino fijo y un control aleatorio variable, podemos usarlo como una tabla de búsqueda paralela para realizar búsquedas 16x en paralelo (de una tabla de 16 bytes de entrada en un vector).
Así que cargamos todo el entero en un registro vectorial y descomprimimos sus nibbles en bytes con un desplazamiento de bits y punpcklbw. Entonces usa un pshufb para asignar esos nibbles a dígitos hexadecimales.
Eso nos deja con los dígitos ASCII, un registro XMM con el dígito menos significativo como el byte más bajo del registro. Dado que x86 es little-endian, no hay forma gratuita de almacenarlos en la memoria en el orden opuesto, con el MSB primero.
Podemos usar un extra pshufb para reordenar los bytes ASCII en orden de impresión, o utilice bswap en la entrada en un registro entero (e invierta el nibble -> desempaquetado de bytes). Si el entero proviene de la memoria, pasando por un registro de enteros para bswap un poco apesta (especialmente para la familia AMD Bulldozer), pero si tienes el número entero en un registro GP en primer lugar, es bastante bueno.
;; NASM syntax, i386 System V calling convention
section .rodata
align 16
hex_lut: db "0123456789abcdef"
low_nibble_mask: times 16 db 0x0f
reverse_8B: db 7,6,5,4,3,2,1,0, 15,14,13,12,11,10,9,8
;reverse_16B: db 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
section .text
global itohex_ssse3 ; tested, works
itohex_ssse3:
mov eax, [esp+4] ; out pointer
movd xmm1, [esp+8] ; number
movdqa xmm0, xmm1
psrld xmm1, 4 ; right shift: high nibble -> low (with garbage shifted in)
punpcklbw xmm0, xmm1 ; interleave low/high nibbles of each byte into a pair of bytes
pand xmm0, [low_nibble_mask] ; zero the high 4 bits of each byte (for pshufb)
; unpacked to 8 bytes, each holding a 4-bit integer
movdqa xmm1, [hex_lut]
pshufb xmm1, xmm0 ; select bytes from the LUT based on the low nibble of each byte in xmm0
pshufb xmm1, [reverse_8B] ; printing order is MSB-first
movq [eax], xmm1 ; store 8 bytes of ASCII characters
ret
;; The same function for 64-bit integers would be identical with a movq load and a movdqu store.
;; but you'd need reverse_16B instead of reverse_8B to reverse the whole reg instead of each 8B half
Es posible empaquetar la máscara AND y el control pshufb en un vector de 16 bytes, similar a itohex_AVX512F debajo.
AND_shuffle_mask: times 8 db 0x0f ; low half: 8-byte AND mask
db 7,6,5,4,3,2,1,0 ; high half: shuffle constant that will grab the low 8 bytes in reverse order
Cárguelo en un registro vectorial y úselo como máscara Y, luego úselo como pshufb control para tomar los 8 bytes bajos en orden inverso, dejándolos en el 8. Su resultado final (8 dígitos hexadecimales ASCII) estará en la mitad superior de un registro XMM, así que use movhps [eax], xmm1. En las CPU Intel, esto sigue siendo solo 1 uop de dominio fusionado, por lo que es tan barato como movq. Pero en Ryzen, cuesta una mezcla en la parte superior de una tienda. Además, este truco es inútil si desea convertir dos enteros en paralelo o un entero de 64 bits.
SSE2, disponible garantizado en x86-64:
Sin SSSE3 pshufb, necesitamos confiar en escalar bswap para poner los bytes en el orden correcto de impresión, y punpcklbw la otra forma de entrelazar primero con el mordisco alto de cada par.
En lugar de una búsqueda de tabla, simplemente agregamos '0'y agrega otro 'a' - ('0'+10) para dígitos mayores de 9 (para ponerlos en el 'a'..'f' distancia). SSE2 tiene una comparación de bytes empaquetados para mayor que, pcmpgtb. Junto con un AND bit a bit, eso es todo lo que necesitamos para agregar algo condicionalmente.
itohex: ; tested, works.
global itohex_sse2
itohex_sse2:
mov edx, [esp+8] ; number
mov ecx, [esp+4] ; out pointer
;; or enter here for fastcall arg passing. Or rdi, esi for x86-64 System V. SSE2 is baseline for x86-64
bswap edx
movd xmm0, edx
movdqa xmm1, xmm0
psrld xmm1, 4 ; right shift: high nibble -> low (with garbage shifted in)
punpcklbw xmm1, xmm0 ; interleave high/low nibble of each byte into a pair of bytes
pand xmm1, [low_nibble_mask] ; zero the high 4 bits of each byte
; unpacked to 8 bytes, each holding a 4-bit integer, in printing order
movdqa xmm0, xmm1
pcmpgtb xmm1, [vec_9]
pand xmm1, [vec_af_add] ; digit>9 ? 'a'-('0'+10) : 0
paddb xmm0, [vec_ASCII_zero]
paddb xmm0, xmm1 ; conditional add for digits that were outside the 0..9 range, bringing them to 'a'..'f'
movq [ecx], xmm0 ; store 8 bytes of ASCII characters
ret
;; would work for 64-bit integers with 64-bit bswap, just using movq + movdqu instead of movd + movq
section .rodata
align 16
vec_ASCII_zero: times 16 db '0'
vec_9: times 16 db 9
vec_af_add: times 16 db 'a'-('0'+10)
; 'a' - ('0'+10) = 39 = '0'-9, so we could generate this from the other two constants, if we were loading ahead of a loop
; 'A'-('0'+10) = 7 = 0xf >> 1. So we could generate this on the fly from an AND. But there's no byte-element right shift.
low_nibble_mask: times 16 db 0x0f
Esta versión necesita más constantes vectoriales que la mayoría de las demás. 4x 16 bytes son 64 bytes, que caben en una línea de caché. Tu podrías querer align 64 antes del primer vector en lugar de solo align 16, por lo que todos provienen de la misma línea de caché.
Esto incluso podría implementarse solo con MMX, usando solo constantes de 8 bytes, pero luego necesitaría un emms por lo que probablemente solo sería una buena idea en CPU muy antiguas que no tienen SSE2, o que dividen las operaciones de 128 bits en mitades de 64 bits (por ejemplo, Pentium-M o K8). En las CPU modernas con eliminación de mov para registros vectoriales (como Bulldozer e IvyBrige), solo funciona en registros XMM, no MMX. Arreglé el uso del registro para que el segundo movdqa está fuera del camino crítico, pero no lo hice por primera vez.
AVX puede salvar un movdqa, pero más interesante es con AVX2 podemos producir potencialmente 32 bytes de dígitos hexadecimales a la vez a partir de entradas grandes. 2x enteros de 64 bits o 4x enteros de 32 bits; utilizar una carga de difusión de 128-> 256 bits para replicar los datos de entrada en cada carril. A partir de ahí, en el carril vpshufb ymm con un vector de control que lee desde la mitad baja o alta de cada carril de 128 bits debería configurarlo con los nibbles para los 64 bits bajos de entrada desempaquetados en el carril bajo, y los nibbles para los 64 bits altos de entrada desempaquetados en el carril alto.
O si los números de entrada provienen de diferentes fuentes, tal vez vinserti128 el alto podría vale la pena en algunas CPU, en lugar de simplemente realizar operaciones separadas de 128 bits.
AVX512VBMI (Cannonlake / IceLake, no presente en Skylake-X) tiene un byte shuffle de 2 registros vpermt2b que podría combinar el puncklbw entrelazado con inversión de bytes. O mejor aún, tenemos VPMULTISHIFTQB que puede extraer 8 campos de bits de 8 bits no alineados de cada palabra q de la fuente.
Podemos usar esto para extraer los nibbles que queremos en el orden que queremos directamente, evitando una instrucción separada de desplazamiento a la derecha. (Todavía viene con trozos de basura, pero vpermb ignora la basura alta.)
Para usar esto para enteros de 64 bits, use una fuente de transmisión y un control de cambio múltiple que descomprima los 32 bits altos de la palabra q de entrada en la parte inferior del vector y los 32 bits bajos en la parte superior del vector. (Suponiendo entrada de little-endian)
Para usar esto para más de 64 bits de entrada, use vpmovzxdq para ampliar a cero cada dword de entrada en una qword, preparándose para vpmultishiftqb con el mismo patrón de control 28,24, …, 4,0 en cada qword. (por ejemplo, producir un vector zmm de salida a partir de un vector de entrada de 256 bits, o cuatro dwords -> un ymm reg para evitar límites de velocidad de reloj y otros efectos de ejecutar realmente una instrucción AVX512 de 512 bits).
Cuidado con que más ancho vpermb usa 5 o 6 bits de cada byte de control, lo que significa que deberá transmitir el hexLUT a un registro ymm o zmm, o repetirlo en la memoria.
itohex_AVX512VBMI: ; Tested with SDE
vmovq xmm1, [multishift_control]
vpmultishiftqb xmm0, xmm1, qword [esp+8]1to2 ; number, plus 4 bytes of garbage. Or a 64-bit number
mov ecx, [esp+4] ; out pointer
;; VPERMB ignores high bits of the selector byte, unlike pshufb which zeroes if the high bit is set
;; and it takes the bytes to be shuffled as the optionally-memory operand, not the control
vpermb xmm1, xmm0, [hex_lut] ; use the low 4 bits of each byte as a selector
vmovq [ecx], xmm1 ; store 8 bytes of ASCII characters
ret
;; For 64-bit integers: vmovdqa load [multishift_control], and use a vmovdqu store.
section .rodata
align 16
hex_lut: db "0123456789abcdef"
multishift_control: db 28, 24, 20, 16, 12, 8, 4, 0
; 2nd qword only needed for 64-bit integers
db 60, 56, 52, 48, 44, 40, 36, 32
# I don't have an AVX512 CPU, so I used Intel's Software Development Emulator
$ /opt/sde-external-8.4.0-2017-05-23-lin/sde -- ./a.out 0x1235fbac
1235fbac
vpermb xmm no es un cruce de carril porque solo hay un carril involucrado (a diferencia de vpermb ymm o zmm). Pero desafortunadamente en CannonLake (según los resultados de instlatx64), todavía tiene una latencia de 3 ciclos, por lo que pshufb sería mejor para la latencia. Pero pshufb condicionalmente ceros basados en el bit alto, por lo que requiere enmascarar el vector de control. Eso empeora las cosas para el rendimiento, suponiendo vpermb xmm es solo 1 uop. En un bucle donde podemos mantener las constantes vectoriales en registros (en lugar de operandos de memoria), solo guarda 1 instrucción en lugar de 2.
(Actualización: sí, https://uops.info/ confirma vpermb es 1 uop con latencia 3c, rendimiento 1c en Cannon Lake y Ice Lake. ICL tiene un rendimiento de 0.5c para vpshufb xmm / ymm)
Cambio variable AVX2 o combinación-enmascaramiento AVX512F para guardar un intercalado
Con AVX512F, podemos usar el enmascaramiento de combinación para desplazar a la derecha una dword y dejar la otra sin modificar, después de transmitir el número en un registro XMM.
O podríamos usar un cambio variable AVX2 vpsrlvd hacer exactamente lo mismo, con un vector de recuento de turnos de [4, 0, 0, 0]. Intel Skylake y posteriores tienen single-uop vpsrlvd; Haswell / Broadwell toman múltiples uops (2p0 + p5). Ryzen vpsrlvd xmm es 1 uop, 3c de latencia, 1 por 2 de rendimiento de reloj. (Peor que los turnos inmediatos).
Entonces solo necesitamos un byte shuffle de un solo registro, vpshufb, para intercalar nibbles y byte-reverse. Pero luego necesita una constante en un registro de máscara que requiere un par de instrucciones para crear. Sería una ganancia mayor en un bucle convirtiendo varios enteros en hexadecimal.
Para una versión independiente sin bucle de la función, utilicé dos mitades de una constante de 16 bytes para diferentes cosas: set1_epi8(0x0f) en la mitad superior y 8 bytes de pshufb vector de control en la mitad inferior. Esto no ahorra mucho porque los operandos de memoria de transmisión EVEX permiten vpandd xmm0, xmm0, dword [AND_mask]1to4, solo requiere 4 bytes de espacio para una constante.
itohex_AVX512F: ;; Saves a punpcklbw. tested with SDE
vpbroadcastd xmm0, [esp+8] ; number. can't use a broadcast memory operand for vpsrld because we need merge-masking into the old value
mov edx, 1<<3 ; element #3
kmovd k1, edx
vpsrld xmm0k1, xmm0, 4 ; top half: low dword: low nibbles unmodified (merge masking). 2nd dword: high nibbles >> 4
; alternatively, AVX2 vpsrlvd with a [4,0,0,0] count vector. Still doesn't let the data come from a memory source operand.
vmovdqa xmm2, [nibble_interleave_AND_mask]
vpand xmm0, xmm0, xmm2 ; zero the high 4 bits of each byte (for pshufb), in the top half
vpshufb xmm0, xmm0, xmm2 ; interleave nibbles from the high two dwords into the low qword of the vector
vmovdqa xmm1, [hex_lut]
vpshufb xmm1, xmm1, xmm0 ; select bytes from the LUT based on the low nibble of each byte in xmm0
mov ecx, [esp+4] ; out pointer
vmovq [ecx], xmm1 ; store 8 bytes of ASCII characters
ret
section .rodata
align 16
hex_lut: db "0123456789abcdef"
nibble_interleave_AND_mask: db 15,11, 14,10, 13,9, 12,8 ; shuffle constant that will interleave nibbles from the high half
times 8 db 0x0f ; high half: 8-byte AND mask
Al final de todo puedes encontrar los informes de otros sys admins, tú igualmente tienes la libertad de insertar el tuyo si dominas el tema.