связанные: 16-разрядная версия, которая преобразует 1 байт в 2 шестнадцатеричные цифры, которые вы можно распечатать или сохранить в буфер. И Преобразование bin в шестнадцатеричный формат в сборке имеет еще одну 16-битную версию с большим количеством текстовое объяснение в половине ответа, охватывающее шестнадцатеричную часть проблемы с типом int - ›.

Если вы оптимизируете размер кода вместо скорости, есть хак с использованием DAS, который экономит несколько байтов.

16 - степень двойки. В отличие от десятичной дроби или других оснований, которые не являются степенью двойки, нам не нужно деление, и мы можем сначала извлечь наиболее значимую цифру (т. Е. В порядке печати). В противном случае мы можем сначала получить только наименее значимую цифру (а ее значение зависит от всех битов числа), и нам придется вернуться назад: см. Как мне напечатать целое число в программировании на уровне сборки без printf из библиотеки c? для оснований, не имеющих степени двойки.

Каждой 4-битной группе бит соответствует одна шестнадцатеричная цифра. Мы можем использовать сдвиги или повороты, а также маски И, чтобы извлечь каждый 4-битный фрагмент ввода как 4-битное целое число.

К сожалению, шестнадцатеричные цифры 0..9 a..f не являются смежными в наборе символов ASCII (http://www.asciitable.com/). Нам либо нужно условное поведение (ветвь или cmov), либо мы можем использовать таблицу поиска.

Таблица поиска обычно наиболее эффективна для подсчета инструкций и производительности, поскольку мы делаем это неоднократно; современные процессоры имеют очень быстрые кэши L1d, которые делают повторную загрузку соседних байтов очень дешевой. Конвейерное / внеочередное выполнение скрывает задержку ~ 5 циклов загрузки кэша 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"

Чтобы адаптироваться к x86-64, соглашение о вызовах будет передавать аргументы в регистрах вместо стека, например RDI и ESI для x86-64 System V (кроме Windows). Просто удалите часть, которая загружается из стека, и измените цикл, чтобы использовать ESI вместо EAX. (И сделайте режимы адресации 64-битным. Возможно, вам потребуется LEA адрес hex_lut в регистр вне цикла; см. this и this).

Эта версия преобразуется в шестнадцатеричное с ведущими нулями. Если вы хотите отбросить их, bit_scan(input)/4 как lzcnt или __builtin_clz на входе или сравнение SIMD - ›pmovmksb -› tzcnt в выходной строке ASCII сообщит вам, сколько у вас 0 цифр (и, таким образом, вы можете распечатать или скопировать, начиная с первый ненулевой). Или конвертируйте, начиная с младшего полубайта, и работайте в обратном направлении, останавливаясь, когда сдвиг вправо делает значение равным нулю, как показано во второй версии, в которой вместо таблицы поиска используется cmov.

До BMI2 (shrx / rorx) в x86 отсутствует инструкция копирования и сдвига, поэтому вращение на месте с последующим копированием / И трудно превзойти ¹. Современные x86 (Intel и AMD) имеют задержку в 1 цикл для ротации (https://agner.org/optimize/ и https://uops.info/), поэтому эта цепочка зависимостей с циклическим переносом не становится узкое место. (В цикле слишком много инструкций, чтобы он мог выполняться хотя бы с 1 циклом за итерацию даже на 5-разрядном Ryzen.)

Я использовал mov ecx,8 и dec ecx/jnz для удобства чтения; lea ecx, [edi+8] вверху и cmp edi, ecx / jb .digit_loop в качестве ветви цикла меньше общий размер машинного кода и более эффективен на большем количестве процессоров. dec/jcc объединение макросов в единый муп происходит только в семействе Intel Sandybridge; AMD объединяет только jcc с cmp или test. Эта оптимизация снизит его до 7 мопов для внешнего интерфейса на Ryzen, как и у Intel, что по-прежнему больше, чем он может выдать за 1 цикл.

Сноска 1: мы могли бы использовать SWAR (SIMD в регистре) для выполнения И перед сдвигом: x & 0x0f0f0f0f младших полубайтов и shr(x,4) & 0x0f0f0f0f полубайтов, а затем эффективно развернуть, поочередно обрабатывая байты из каждого регистра. (Без какого-либо эффективного способа сделать эквивалент punpcklbw или сопоставить целые числа с несмежными кодами ASCII, нам все равно придется обрабатывать каждый байт отдельно. Но мы могли бы развернуть извлечение байтов и прочитать AH, затем AL (с movzx) для сохранения инструкций сдвига. Чтение регистров с высоким числом 8 может увеличить задержку, но я думаю, что это не требует дополнительных затрат на текущие процессоры. Запись регистров с высоким числом 8 обычно не подходит для процессоров Intel: для чтения полный регистр с внешней задержкой для его вставки. Таким образом, расширение хранилищ путем перетасовки регистров, вероятно, нехорошо. В коде ядра, где вы не можете использовать регистры XMM, но можете использовать BMI2, если он доступен, pdep может расширять полубайты до байтов но это, вероятно, хуже, чем просто маскировка двумя способами.)

Программа испытаний:

// hex.c   converts argv[1] to integer and passes it to itohex
#include <stdio.h>
#include <stdlib.h>

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);
}

скомпилировать с помощью:

nasm -felf32 -g -Fdwarf itohex.asm
gcc -g -fno-pie -no-pie -O3 -m32 hex.c itohex.o

тестовые прогоны:

$ ./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

Альтернативные реализации:

Условный вместо таблицы поиска: требуется несколько дополнительных инструкций и, вероятно, будет медленнее. Но ему не нужны статические данные.

Это можно было бы сделать с помощью ветвления вместо cmov, но в большинстве случаев это было бы еще медленнее. (Это не будет хорошо предсказывать, предполагая случайное сочетание цифр 0..9 и a..f.) https://codegolf.stackexchange.com/questions/193793/little-endian-number-to-string-conversion/193842#193842 показывает версию, оптимизированную для кода. -размер. (За исключением bswap в начале, это обычный uint32_t - ›шестнадцатеричный код с нулевым заполнением.)

Ради интереса, эта версия начинается с конца буфера и уменьшает указатель. (И условие цикла использует сравнение указателя.) Вы можете остановить его, когда EDX станет равным нулю, и использовать EDI + 1 в качестве начала числа, если вы не хотите нулей в начале.

Использование cmp eax,9 / ja вместо cmov остается в качестве упражнения для читателя. В 16-битной версии этого можно было бы использовать другие регистры (например, BX в качестве временного), чтобы разрешить lea cx, [bx + 'a'-10] копирование и добавление. Или просто _27 _ / _ 28_ и jcc, если вы хотите избежать cmov для совместимости с древними процессорами, которые не поддерживают расширения 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

Мы могли бы предоставить еще больше ILP в каждой итерации, используя 2x lea + cmp/cmov. cmp и оба LEA зависят только от значения полубайта, при этом cmov потребляет все 3 из этих результатов. Но существует множество ILP между итерациями, где только shr edx,4 и декремент указателя являются зависимостями, переносимыми по циклу. Я мог бы сэкономить 1 байт размера кода, расположив так, чтобы я мог использовать cmp al, 'a' или что-то в этом роде. И / или add al,'0', если меня не волнуют процессоры, которые переименовывают AL отдельно от EAX.

Тестовый набор, который проверяет наличие ошибок с отклонением на 1, используя число, которое имеет как 9, так и a в его шестнадцатеричных цифрах:

$ nasm -felf32 -g -Fdwarf itohex.asm && gcc -g -fno-pie -no-pie -O3 -m32 hex.c itohex.o && ./a.out 0x19a2d0fb
19a2d0fb

SIMD с SSE2, SSSE3, AVX2 или AVX512F и ~ 2 инструкции с AVX512VBMI

В SSSE3 и более поздних версиях лучше всего использовать перестановку байтов в качестве таблицы поиска полубайтов.

Большинство этих версий SIMD можно использовать с двумя упакованными 32-битными целыми числами в качестве входных данных, при этом младшие и старшие 8 байтов результирующего вектора содержат отдельные результаты, которые вы можете сохранить отдельно с помощью movq и movhps. В зависимости от вашего элемента управления перемешиванием это точно так же, как его использование для одного 64-битного целого числа.

SSSE3 pshufb таблица параллельного поиска. Не нужно возиться с циклами, мы можем сделать это с помощью нескольких операций SIMD на процессорах с pshufb. (SSSE3 не является базовым даже для x86-64; он был новым с Intel Core2 и AMD Bulldozer).

pshufb - это перетасовка байтов, управляемая вектором, а не немедленным (в отличие от всех предыдущих SSE1 / SSE2 / SSE3 перемешивается). Имея фиксированный пункт назначения и переменное управление перемешиванием, мы можем использовать его в качестве параллельной таблицы поиска для параллельного выполнения 16x поисков (из таблицы с 16 байтами в векторе).

Итак, мы загружаем целое число в векторный регистр и распаковываем его полубайты в байты с битовым сдвигом и _ 46_. Затем используйте pshufb, чтобы сопоставить эти полубайты с шестнадцатеричными цифрами.

Это оставляет нам цифры ASCII в регистре XMM с наименьшей значащей цифрой в качестве младшего байта регистра. Поскольку x86 имеет прямой порядок байтов, нет бесплатного способа сохранить их в памяти в обратном порядке, сначала с MSB.

Мы можем использовать дополнительный pshufb, чтобы изменить порядок байтов ASCII в порядке печати, или использовать bswap на входе в целочисленном регистре (и перевернуть полубайт - ›распаковка байтов). Если целое число поступает из памяти, прохождение целочисленного регистра для bswap вроде отстой (особенно для семейства AMD Bulldozer), но если у вас есть целое число в регистре GP, это, в первую очередь, неплохо.

;; 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

Можно упаковать маску AND и элемент управления pshufb в один 16-байтовый вектор, аналогично itohex_AVX512F ниже.

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

Загрузите его в векторный регистр и используйте как маску И, затем используйте его как элемент управления pshufb, чтобы захватить 8 младших байтов в обратном порядке, оставив их в старшем 8. Окончательный результат (8 шестнадцатеричных цифр ASCII) будет в верхняя половина регистра XMM, поэтому используйте movhps [eax], xmm1. В процессорах Intel это всего лишь 1 uop с объединенным доменом, так что он такой же дешевый, как movq. Но на Ryzen это стоит мелочь поверх магазина. Кроме того, этот трюк бесполезен, если вы хотите преобразовать два целых числа параллельно или 64-битное целое число.

SSE2, гарантированно доступен в x86-64:

Без SSSE3 pshufb нам нужно полагаться на скаляр bswap, чтобы расположить байты в правильном порядке печати, и punpcklbw другой способ, чтобы сначала чередовать старший полубайт каждой пары.

Вместо поиска по таблице мы просто добавляем '0' и добавляем еще 'a' - ('0'+10) для цифр больше 9 (чтобы поместить их в диапазон 'a'..'f'). SSE2 имеет упакованное сравнение байтов для большего чем, pcmpgtb. Наряду с побитовым И, это все, что нам нужно, чтобы что-то условно добавить.

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

В этой версии требуется больше векторных констант, чем в большинстве других. 4x 16 байтов - это 64 байта, которые умещаются в одной строке кэша. Вы можете захотеть align 64 перед первым вектором, а не просто align 16, чтобы все они были взяты из одной и той же строки кэша.

Это можно было бы даже реализовать только с MMX, используя только 8-байтовые константы, но тогда вам понадобится emms, поэтому это, вероятно, будет хорошей идеей только для очень старых процессоров, у которых нет SSE2 или которые разделяют 128-битные операции на 64-битные половины (например, Pentium-M или K8). На современных процессорах с удалением mov для векторных регистров (например, Bulldozer и IvyBrige) он работает только с регистрами XMM, но не с MMX. Я организовал использование регистров таким образом, чтобы второй movdqa находился вне критического пути, но я не делал этого в первый раз.

AVX может сохранять movdqa, но более интересным является то, что с AVX2 мы потенциально можем создавать 32 байта шестнадцатеричных цифр за раз из больших входных данных. 2x 64-битных целых или 4x 32-битных целых числа; используйте 128- ›256-битную широковещательную нагрузку для репликации входных данных в каждую дорожку. Оттуда внутренняя линия vpshufb ymm с вектором управления, который считывается из младшей или высокой половины каждой 128-битной полосы, должна настроить вас с полубайтами для младших 64 битов ввода, распакованными в нижней полосе, и полубайтами для старшие 64 бита ввода распакованы в старшей полосе.

Или, если входные числа поступают из разных источников, возможно, vinserti128 высокое значение может оправдать себя на некоторых процессорах, а не просто выполнять отдельные 128-битные операции.

AVX512VBMI (Cannonlake / IceLake, отсутствует в Skylake-X) имеет тасование байтов с 2 регистрами vpermt2b это могло бы совмещать puncklbw чередование с обращением байтов. Или, что еще лучше, у нас есть VPMULTISHIFTQB, который может извлекать 8 невыровненных 8-битовых полей из каждое qword источника.

Мы можем использовать это для извлечения нужных полубайтов в нужном нам порядке, избегая отдельной инструкции сдвига вправо. (Он по-прежнему идет с битами мусора, но vpermb игнорирует высокий объем мусора.)

Чтобы использовать это для 64-битных целых чисел, используйте широковещательный источник и элемент управления с несколькими сдвигами, который распаковывает старшие 32 бита входного qword в нижней части вектора и младшие 32 бита в верхней части вектора. (При вводе с прямым порядком байтов)

Чтобы использовать это для более чем 64 битов ввода, используйте vpmovzxdq для расширения нулями каждого входного двойного слова до qword, установив для vpmultishiftqb тот же элемент управления 28,24, ..., 4,0 узор в каждом qword. (например, создание вектора zmm вывода из 256-битного вектора ввода или четырех двойных слов - ›ymm reg, чтобы избежать ограничений тактовой частоты и других эффектов фактического выполнения 512-битной инструкции AVX512.)

Помните, что более широкий vpermb использует 5 или 6 бит каждого байта управления, что означает, что вам нужно будет транслировать hexLUT в регистр ymm или zmm или повторить его в памяти.

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 не является пересечением полосы движения, потому что задействована только одна полоса движения (в отличие от vpermb ymm или zmm). Но, к сожалению, на CannonLake (согласно результатам instlatx64) задержка в 3 цикла все еще сохраняется. так что pshufb было бы лучше для задержки. Но pshufb обнуляется условно на основе старшего бита, поэтому требуется маскирование вектора управления. Это ухудшает пропускную способность, если предположить, что vpermb xmm составляет всего 1 мкоп. В цикле, где мы можем хранить векторные константы в регистрах (вместо операндов памяти), сохраняется только 1 инструкция вместо 2.

(Обновление: да, https://uops.info/ подтверждает, что vpermb составляет 1 моп с задержкой 3 с, пропускной способностью 1 с на Cannon Lake и Ice Lake. ICL имеет пропускную способность 0,5c для vpshufb xmm / ymm)

AVX2 с переменным сдвигом или маскирование слияния AVX512F для сохранения чередования

С AVX512F мы можем использовать маскирование слияния, чтобы сдвинуть вправо одно двойное слово, оставив другое неизменным после широковещательной передачи числа в регистр XMM.

Или мы могли бы использовать переменный сдвиг AVX2 vpsrlvd, чтобы сделать то же самое, с вектором счетчика сдвига [4, 0, 0, 0]. Intel Skylake и более поздние версии имеют однокомпонентный vpsrlvd; Haswell / Broadwell принимают несколько мопов (2p0 + p5). Ryzen vpsrlvd xmm - это 1 мкоп, задержка 3 с, пропускная способность 1 на 2 такта. (Хуже, чем немедленные смены).

Тогда нам понадобится только перестановка байтов с одним регистром, vpshufb, для чередования полубайтов и обратного байта. Но тогда вам понадобится константа в регистре маски, для создания которой потребуется пара инструкций. Цикл, в котором несколько целых чисел преобразуются в шестнадцатеричный, будет более выигрышным.

Для автономной версии функции без цикла я использовал две половины одной 16-байтовой константы для разных целей: set1_epi8(0x0f) в верхней половине и 8 байтов pshufb управляющего вектора в нижней половине. Это не сильно экономит, потому что операнды широковещательной памяти EVEX допускают vpandd xmm0, xmm0, dword [AND_mask]{1to4}, требуя только 4 байта пространства для константы.

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  xmm0{k1}, 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

AVX512VBMI (Ice Lake и новее)

В отличие от моего 32-битного asm, они оптимизируются для того, чтобы их входной номер находился в регистре, не предполагая, что он все равно должен загружаться из памяти. (Поэтому мы не предполагаем, что трансляция бесплатна.) Но TODO: исследуйте использование bswap вместо тасования SIMD, чтобы получить байты в порядке печати. Особенно для 32-битных целых чисел, где bswap составляет всего 1 моп (против 2 у Intel для 64-битных регистров, в отличие от AMD).

Они печатают все число в порядке печати сначала MSD. Настройте константу множественного сдвига или элементы управления случайным образом для вывода в памяти с прямым порядком байтов, как люди, очевидно, хотят выводить большой хэш в шестнадцатеричном формате. Или для версии SSSE3 просто удалите pshufb с обратным байтом.)

AVX2 / 512 также допускает более широкие версии, которые работают с 16 или 32 байтами ввода за раз, создавая 32 или 64 байта шестнадцатеричного вывода. Вероятно, путем перетасовки, чтобы повторить каждые 64 бита в 128-битной полосе, в векторе с удвоенной шириной, например с vpermq, например _mm256_permutex_epi64(_mm256_castsi128_si256(v), _MM_SHUFFLE(?,?,?,?)).

Моя версия asm использовала 64-битную широковещательную загрузку своего аргумента стека из памяти даже для аргумента u32. Но это было только для того, чтобы я мог сложить загрузку в операнд источника памяти для vpmultishiftqb. Невозможно сообщить компилятору, что он может использовать операнд источника 64-битной широковещательной памяти, при этом старшие 32 бита не заботятся, если значение все равно поступало из памяти (и известно, что оно не находится в конце страницы раньше неотображенная страница, например, аргумент стека 32-битного режима). Так что эта небольшая оптимизация недоступна в C. И обычно после встраивания ваши вары будут в регистрах, и если у вас есть указатель, вы не узнаете, находится он в конце страницы или нет. Версия uint64_t действительно требует широковещательной передачи, но поскольку объект в памяти - это uint64_t, компилятор может использовать операнд источника памяти широковещательной передачи {1to2}. (По крайней мере, clang и ICC достаточно умен, чтобы использовать -m32 -march=icelake-client или в 64-битном режиме со ссылкой вместо значения arg.)

AVX2

#include <immintrin.h>
#include <stdint.h>

#if defined(__AVX512VBMI__) || defined(_MSC_VER)
// AVX512VBMI was new in Icelake
//template<typename T>   // also works for uint64_t, storing 16 or 8 bytes.
void itohex_AVX512VBMI(char *str, uint32_t input_num)
{
    __m128i  v;
    if (sizeof(input_num) <= 4) {
        v = _mm_cvtsi32_si128(input_num); // only low qword needed
    } else {
        v = _mm_set1_epi64x(input_num);   // bcast to both halves actually needed
    }
    __m128i multishift_control = _mm_set_epi8(32, 36, 40, 44, 48, 52, 56, 60,   // high qword takes high 32 bits.  (Unused for 32-bit input)
                                               0,  4,  8, 12, 16, 20, 24, 28);  // low qword takes low 32 bits
    v = _mm_multishift_epi64_epi8(multishift_control, v);
    // bottom nibble of each byte is valid, top holds garbage. (So we can't use _mm_shuffle_epi8)
    __m128i hex_lut = _mm_setr_epi8('0', '1', '2', '3', '4', '5', '6', '7',
                                    '8', '9', 'a', 'b', 'c', 'd', 'e', 'f');
    v = _mm_permutexvar_epi8(v, hex_lut);

    if (sizeof(input_num) <= 4)
        _mm_storel_epi64((__m128i*)str, v);  // 8 ASCII hex digits (u32)
    else
        _mm_storeu_si128((__m128i*)str, v);  // 16 ASCII hex digits (u64)
}
#endif

clang -O3 -m32 фактически компилируется так же, как и мой рукописный asm, за исключением vmovdqa загрузки константы, а не vmovq, потому что в этом случае фактически все это необходимо. Компиляторы недостаточно умны, чтобы использовать только vmovq загрузок и опускать 0 байтов из .rodata, когда верхние 8 байтов константы равны 0. Также обратите внимание, что константа множественного сдвига в выводе asm совпадает, поэтому _mm_set_epi8 является правильным; .

При этом используется 32-разрядное целое число на входе; эта стратегия не работает для 64-битной версии (потому что для нее требуется сдвиг бит в два раза больше).

Пишем hex_lut компактнее:

Вышеупомянутое, я думаю, лучше, особенно на Haswell, но также и на Zen, где переменный сдвиг vpsrlvd имеет более низкую пропускную способность и большую задержку, хотя это всего лишь один муп. Это лучше для узких мест внутреннего порта даже на Skylake: 3 инструкции, которые выполняются только на порту 5, по сравнению с 4 (включая vmovd xmm, reg, vpbroadcastd xmm,xmm и 2x vpshufb) для версии ниже, но такое же количество интерфейсных мопов (при условии наличия микро -слияние векторных констант как операндов источника памяти). Также требуется на 1 векторную константу меньше, что всегда хорошо, особенно если это не цикл.

// Untested, and different strategy from any tested asm version.

// requires AVX2, can take advantage of AVX-512
// Avoids a broadcast, which costs extra without AVX-512, unless the value is coming from mem.
// With AVX-512, this just saves a mask or variable-shift constant.  (vpbroadcastd xmm, reg is as cheap as vmovd, except for code size)
void itohex_AVX2(char *str, uint32_t input_num)
{
    __m128i  v = _mm_cvtsi32_si128(input_num);
    __m128i hi = _mm_slli_epi64(v, 32-4);  // input_num >> 4 in the 2nd dword
    // This trick to avoid a shuffle only works for 32-bit integers
#ifdef __AVX512VL__
                                          // UNTESTED, TODO: check this constant
    v = _mm_ternarylogic_epi32(v, hi, _mm_set1_epi8(0x0f), 0b10'10'10'00);  // IDK why compilers don't do this for us
#else
    v = _mm_or_si128(v, hi);              // the overlaping 4 bits will be masked away anyway, don't need _mm_blend_epi32
    v = _mm_and_si128(v, _mm_set1_epi8(0x0f));     // isolate the nibbles because vpermb isn't available
#endif
    __m128i nibble_interleave = _mm_setr_epi8(7,3, 6,2, 5,1, 4,0,
                                              0,0,0,0,  0,0,0,0);
    v = _mm_shuffle_epi8(v, nibble_interleave);  // and put them in order into the low qword
    __m128i hex_lut = _mm_setr_epi8('0', '1', '2', '3', '4', '5', '6', '7',
                                    '8', '9', 'a', 'b', 'c', 'd', 'e', 'f');
    v = _mm_shuffle_epi8(hex_lut, v);

    _mm_storel_epi64((__m128i*)str, v);  // movq 8 ASCII hex digits (u32)
}

AVX-512 может использовать сдвиг с маской слияния вместо сдвига с переменным счетом, экономя одну векторную константу за счет необходимости настройки регистра маски. Это экономит место в .rodata, но не устраняет все константы, поэтому промах в кеше все равно остановит это. И mov r,imm / kmov k,r - это 2 мопа вместо 1 вне любого цикла, с которым вы это используете.

также AVX2: порт asm-версии itohex_AVX512F с идеей vpsrlvd, которую я добавил позже.

По сравнению с версией SSSE3, при этом сохраняется vpunpcklbw за счет использования vpsrlvd (или маскированного сдвига) для переноса байтов num>>4 и num в один и тот же регистр XMM для настройки для перетасовки байтов с 1 регистром. vpsrlvd является одинарным в Skylake и более поздних версиях, а также в Zen 1 / Zen 2. В Zen это более высокая задержка и не полностью конвейерная в соответствии с https://uops.info/ (пропускная способность 2c вместо 1c, которую можно было бы ожидать от одного uop для одного порта). Но, по крайней мере, он не конкурирует за тот же порт, что и vpshufb и vpbroadcastd xmm,xmm на этих процессорах. (В Haswell это 2 мупа, включая один для p5, так что там он действительно конкурирует, и это строго хуже, чем версия SSSE3, потому что требует дополнительной константы.)

// combining shuffle and AND masks into a single constant only works for uint32_t
// uint64_t would need separate 16-byte constants.
// clang and GCC wastefully replicate into 2 constants anyway!?!

// Requires AVX2, can take advantage of AVX512 (for cheaper broadcast, and alternate shift strategy)
void itohex_AVX2_slrv(char *str, uint32_t input_num)
{
    __m128i  v = _mm_set1_epi32(input_num);
#ifdef __AVX512VL__
    // save a vector constant, at the cost of a mask constant which takes a couple instructions to create
    v = _mm_mask_srli_epi32(v, 1<<3, v, 4);  // high nibbles in the top 4 bytes, low nibbles unchanged.
#else
    v = _mm_srlv_epi32(v, _mm_setr_epi32(0,0,0,4));  // high nibbles in the top 4 bytes, low nibbles unchanged.
#endif

    __m128i nibble_interleave_AND_mask = _mm_setr_epi8(15,11, 14,10, 13,9, 12,8,     // for PSHUFB
                                    0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f); // for PAND
    v = _mm_and_si128(v, nibble_interleave_AND_mask);     // isolate the nibbles because vpermb isn't available
    v = _mm_shuffle_epi8(v, nibble_interleave_AND_mask);  // and put them in order into the low qword
    __m128i hex_lut = _mm_setr_epi8('0', '1', '2', '3', '4', '5', '6', '7',
                                    '8', '9', 'a', 'b', 'c', 'd', 'e', 'f');
    v = _mm_shuffle_epi8(hex_lut, v);

    _mm_storel_epi64((__m128i*)str, v);  // movq 8 ASCII hex digits (u32)
}

Хорошим вариантом для Haswell может быть _mm_slli_epi64(v, 32-4) / _mm_blend_epi32 - vpblendd работает на любом порту, не требуя случайного порта. Или, может быть, даже в целом, поскольку для этого нужна только vmovd настройка, а не vmovd + vpbroadcastd

Для этой функции требуются 2 другие векторные константы (шестнадцатеричный lut и комбинированная маска AND и перемешивания). GCC и clang по глупости оптимизируют 2 использования одной маски в 2 отдельные константы маски, что на самом деле глупо. (Но в цикле только затраты на настройку и регистр, без дополнительных затрат на преобразование. В любом случае вам понадобятся две отдельные 16-байтовые константы для uint64_t версии этого, но моя рукописная версия asm была умной, используя 2 половины одной 16-байтовой константы.

MSVC избегает этой проблемы: он компилирует встроенные функции более буквально и не пытается их оптимизировать (что часто плохо, но здесь позволяет избежать этой проблемы). Но MSVC упускает возможность использования AVX-512 GP-register-source vpbroadcastd xmm0, esi для _mm_set1_epi32 с -arch:AVX512. С -arch:AVX2 (поэтому трансляция должна выполняться двумя отдельными инструкциями) он использует эту векторную константу в качестве операнда источника памяти дважды (для vpand и vpshufb) вместо загрузки в регистр, что довольно сомнительно, но, вероятно, нормально и фактически сохраняет фронт -окончить упс. IDK, что он будет делать в цикле, где подъем груза более очевиден.

hex_lut = _mm_loadu_si128((const __m128i*)"0123456789abcdef"); полностью компилируется с помощью GCC и Clang (они эффективно оптимизируют строковый литерал с его завершающим 0 и просто генерируют выровненную векторную константу). Но MSVC, к сожалению, сохраняет фактическую строку в .rdata, не выравнивая ее. Поэтому я использовал более длинный, менее приятный для чтения _mm_setr_epi8('0', '1', ..., 'f');

выстрелил это

С внутренними компонентами AVX2 или AVX-512

Это задумано как достойная каноническая дублирующая цель для ›шестнадцатеричных вопросов. Все функции в моем ответе были протестированы перед публикацией. Отчасти причина, по которой мы решили написать устаревший 32-разрядный код вместо x86-64, заключается в том, чтобы оправдать представление версии скалярного цикла. SSE2 является базовым для x86-64, поэтому вы всегда должны использовать его в формате int- ›hex, если вам не нужен результат переменной ширины без начальных нулей. (Даже в этом случае вы, вероятно, можете использовать

section .data
msg resb 8
db 10
hex_nums db '0123456789ABCDEF'
xx dd 0FF0FEFCEh
length dw 4

section .text
global main

main:
    mov rcx, 0
    mov rbx, 0
sw:
    mov ah, [rcx + xx]
    mov bl, ah
    shr bl, 0x04
    mov al, [rbx + hex_nums]
    mov [rcx*2 + msg], al
    and ah, 0x0F
    mov bl, ah
    mov ah, [rbx + hex_nums]
    mov [rcx*2 + msg + 1], ah
    inc cx
    cmp cx, [length]
    jl  sw

    mov rax, 1
    mov rdi, 1
    mov rsi, msg
    mov rdx, 9   ;8 + 1
    syscall

    mov rax, 60
    mov rdi, 0
    syscall

section .data
msg resb 8
db 10
hex_nums db '0123456789ABCDEF'
xx dd 0FF0FEFCEh
length dw 4

section .text
global main

main:
    mov rcx, 0
    mov rbx, 0
sw:
    mov ah, [rcx + xx]
    mov bl, ah
    shr bl, 0x04
    mov al, [rbx + hex_nums]
    mov [rcx*2 + msg], al
    and ah, 0x0F
    mov bl, ah
    mov ah, [rbx + hex_nums]
    mov [rcx*2 + msg + 1], ah
    inc cx
    cmp cx, [length]
    jl  sw

    mov rax, 1
    mov rdi, 1
    mov rsi, msg
    mov rdx, 9   ;8 + 1
    syscall

    mov rax, 60
    mov rdi, 0
    syscall

nasm -f elf64 x.asm -o t.o
gcc -no-pie t.o -o t