Как преобразовать двоичное целое число в шестнадцатеричную строку?

avatar
Peter Cordes
17 декабря 2018 в 22:14
5484
3
9

Учитывая число в регистре (двоичное целое число), как преобразовать его в строку шестнадцатеричных цифр ASCII? (т.е. преобразовать его в текстовый формат.)

Цифры можно сохранять в памяти или распечатывать на лету, но сохранение в памяти и одновременная печать обычно более эффективны. (Вы можете изменить цикл, который сохраняет, чтобы вместо этого печатать по одному.)

Можем ли мы эффективно обрабатывать все полубайты параллельно с SIMD? (SSE2 или новее?)

Источник
Peter Cordes
17 декабря 2018 в 22:15
0

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

Peter Cordes
12 апреля 2021 в 09:32
0

См. Также github.com/zbjornson/fast-hex для двоичных-> шестнадцатеричных и шестнадцатеричных-> двоичных для больших буферов.

Ответы (3)

avatar
Peter Cordes
17 декабря 2018 в 22:14
20

связанный: 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 отсутствует инструкция копирования и сдвига, поэтому вращение на месте, а затем копирование / И трудно превзойти 1 . Современные 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 макро-слияние в единый uop происходит только в семействе Intel Sandybridge; AMD объединяет только jcc с cmp или test. Эта оптимизация снизила бы его до 7 мопов для внешнего интерфейса на Ryzen, как и у Intel, что по-прежнему больше, чем он может выдать за 1 цикл.

Сноска 1: Мы могли бы использовать SWAR (SIMD в регистре) для выполнения И перед сдвигом: x & 0x0f0f0f0f младшие полубайты и shr(x,4) & 0x0f0f0f0f полубайты высокого ранга , а затем эффективно развернуть путем чередующейся обработки байта из каждого реестра. (Без какого-либо эффективного способа сделать эквивалент punpcklbw или сопоставить целые числа с несмежными кодами ASCII, нам все равно придется обрабатывать каждый байт отдельно. Но мы могли бы развернуть извлечение байтов и прочитать AH, затем AL (с movzx) для сохранения инструкций сдвига. Чтение регистров старшей восьмерки может увеличить задержку, но я думаю, что это не требует дополнительных затрат на текущих процессорах. Запись регистров старшей восьмерки обычно не годится для процессоров Intel: это требует дополнительного слияния uop, чтобы прочитать полный регистр, с внешней задержкой для его вставки. Поэтому получение более широких хранилищ путем перетасовки регистров, вероятно, нехорошо. В коде ядра, где вы не можете использовать регистры 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]. Или просто add / ​​cmp и 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). Имея фиксированный пункт назначения и переменное управление перемешиванием, мы можем использовать его в качестве параллельной таблицы поиска для параллельного выполнения 16-кратного поиска (из таблицы 16 байтов в векторе).

Итак, мы загружаем целое число в векторный регистр и распаковываем его полубайты в байты с битовым сдвигом и punpcklbw. Затем используйте 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-регистровый перестановочный байт <33921492143103105391> > Чередование с обращением байтов. Или, что еще лучше, у нас есть 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 с на Кэннон-Лейк и Ледяное озеро. ICL имеет пропускную способность 0,5 с для 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
ZachB
31 декабря 2018 в 19:01
1

Ваша версия, несомненно, лучше оптимизирована, чем моя, но я сделал библиотеку для перехода в / из гекса здесь: github.com/zbjornson/fast-hex/tree/master/src. Я не смотрел на него в течение года, чтобы увидеть улучшения, которые я пропустил. Также недавно найденные Агнером имплементации: github.com/darealshinji/vectorclass/blob/master/special/….

user2284570
24 декабря 2020 в 11:00
0

@PeterCordes, возможно ли иметь версию AVX512VBMI с использованием встроенных функций компилятора C или общего __attribute__ ((vector_size расширения gcc?

Peter Cordes
24 декабря 2020 в 11:06
0

@ user2284570: Конечно, с Intel intriniscs (_mm_multishift_epi64_epi8) или GNU C __builtin_ia32_something да, вы можете делать почти все, что можете, в asm, хотя вы находитесь на милости компилятора для складывания широковещательных загрузок в операнды памяти. Но с помощью только переносимого кода GNU C native vector __attribute__((vector_size(16))), который может компилироваться для любого ISA, вряд ли вы могли бы написать что-то, что GCC или clang на самом деле будет оптимизировать до vpmultishiftqb, когда это будет доступно. (-march=icelake-client). Возможно, вы сможете написать что-то такое, что можно было бы оптимизировать таким образом.

user2284570
24 декабря 2020 в 11:14
0

@PeterCordes Я имел в виду, что не понял ваш asm-код. Итак, я имел в виду, что мне нужен полный пример с использованием встроенной функции _mm_mask_multishift_epi64_epi8() (или аналогичной). Тем более, что он предназначен для преобразования 11 64-битных целых чисел за один раз в векторном режиме.

Peter Cordes
7 марта 2021 в 15:48
0

@ user2284570: Я опубликовал второй ответ с версиями AVX2 и AVX512VBMI; Оказывается, некоторое переосмысление вариантов оптимизации было выгодно для переменных в регистрах, а не из памяти, и для ограничений компилятора. Так что просто наивный перевод asm на встроенные функции не был бы так хорош. Тем не менее, я не разработал тасование для получения более 128-битных выходных векторов. Если у вас есть больше данных для преобразования, вероятно, стоит сделать их 2x или 64-битные за раз с mm256, или, может быть, даже 4x с векторами mm512.

user2284570
16 марта 2021 в 21:57
0

@PeterCordes, спасибо. Я знаю, что это был бы другой вопрос, но как сделать наоборот? Я имею в виду преобразование строки c ++ произвольного размера в динамический буфер C.

Peter Cordes
16 марта 2021 в 22:32
0

@ user2284570: Да, это отдельный вопрос; спросите, если хотите. На него бесполезно отвечать в комментариях, хотя в качестве отправной точки следует использовать __m256i vpermb для поиска кодов ASCII обратно к их целочисленным значениям без необходимости выполнять дополнительную работу, чтобы отличить 0-9 от A-F. Упаковка полубайтов обратно в байты может быть выполнена с помощью pmaddubsw вместо set1_epi1(1), тогда у вас будет обычный vpackuswb или AVX512 vpermt2b или VPMOVWB.

user2284570
17 марта 2021 в 00:28
0

@PeterCordes Я думал о том, чтобы вы разместили такой вопрос вместе с ответом, подобным текущему, потому что я думаю, что иначе вряд ли получишь ответ.

Peter Cordes
17 марта 2021 в 02:30
0

@ user2284570: Я не знаю, какой вариант использования вы имеете в виду. (Большой буфер шестнадцатеричных цифр, например, hex-undump? Несколько 8-значных 32-битных чисел?) Если вы разместите вопрос с работающей простой скалярной реализацией, они часто получат ответы о том, как векторизовать. Специально для такой известной распространенной проблемы, как атой вместо шестнадцатеричного. Ответ на atoi для десятичного числа был получен несколько лет назад (Как реализовать atoi с помощью SIMD?), хотя для обработки переменной длины требуется много кода.

user2284570
17 марта 2021 в 10:05
0

@PeterCordes простой случай возврата вашего вопроса будет в порядке, независимо от сценария. А про векторизацию я говорил про avx512 и в этом случае ответ маловероятен.

Peter Cordes
17 марта 2021 в 10:39
0

@ user2284570: Давай, спроси; не стесняйтесь ссылаться на эти вопросы и ответы. Я отвечу на него в какой-то момент, или кто-то другой ответит. Убедитесь, что вопрос конкретно о том, какие подмножества AVX-512 вы можете использовать (например, AVX512-VBMI или нет: en.wikipedia.org/wiki/AVX-512#CPUs_with_AVX-512, хотя хороший ответ будет включить более поздние версии для будущих читателей), и полезно ли обрабатывать длинную последовательность шестнадцатеричных цифр, ровно 8 шестнадцатеричных цифр или переменную длину от 1 до 8 или что-то еще.

Peter Cordes
12 апреля 2021 в 09:34
0

@ user2284570: IDK, если вас все еще интересует вопрос, поскольку вы его никогда не публиковали, но github.com/zbjornson/fast-hex имеет шестнадцатеричный-> двоичный файл для большого буфера. (шестнадцатеричный сброс).

user2284570
12 апреля 2021 в 10:00
0

@PeterCordes, используя avx512?

Peter Cordes
12 апреля 2021 в 10:01
0

@ user2284570: Ой, IDK, я не проверял, какие версии он включил.

avatar
Peter Cordes
7 марта 2021 в 15:42
2

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

По запросу, перенос некоторых версий моего asm-ответа на C (который, как я написал, также будет действительным C ++). Ссылка на компилятор и обозреватель Godbolt. Они компилируются обратно в asm почти так же хорошо, как мой рукописный asm. (И я проверил, что векторные константы в сгенерированном компилятором asm соответствуют моим директивам db. Определенно что-то, что нужно проверить при переводе asm на встроенные функции, особенно если вы используете _mm_set_ вместо setr для констант, которые могут показаться более значительными "естественный" в порядке наивысшего-первого. setr использует порядок памяти, такой же, как asm.)

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

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

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

AVX512VBMI (Ice Lake и новее)

#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

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

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


AVX2

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

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

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

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

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

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

По сравнению с версией 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, поскольку требует дополнительной константы.)

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

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

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


Запись hex_lut более компактно:

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

avatar
Алексей Неудачин
11 января 2021 в 13:00
-1

дробно это

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

Peter Cordes
11 января 2021 в 13:23
0

cmp cx, [length] считывает 2 байта из однобайтового db. Также нет очевидной причины хранить length в статическом хранилище; и особенно не читать его на каждой итерации цикла. Примите это как регистр arg. (И, например, это может быть константа equ).

Peter Cordes
11 января 2021 в 13:26
0

Также нет причин использовать 16-битный CX, особенно для того, чтобы не создавать частичную остановку регистров на каждой итерации в процессорах семейства Intel P6, увеличивая CX перед чтением RCX. (Использование ECX, как обычный человек, исправит это.) Использование AH в качестве временного также совершенно не нужно; x86-64 имеет множество других регистров, которые вы можете использовать, не создавая ложных зависимостей от процессоров AMD, используя AL и AH по отдельности. И если бы вы в первую очередь использовали загрузку movzx в полный регистр, вам не понадобился бы второй mov bl, ah, например, только and edx, 0xf / movzx eax, byte [hex_nums + rdx].

Peter Cordes
11 января 2021 в 13:29
0

Кроме того, hex_nums может идти в section .rodata. И размер msg фиксирован и составляет 8 байтов, но length претендует на то, чтобы быть переменным.

Peter Cordes
11 января 2021 в 13:31
0

Кроме того, это печатает результат в обратном порядке: побайтовое изменение двойного слова путем печати младшего байта (младшего адреса) первым. Запустив его, результат будет CEEF0FFF \ n 0123. 0123 берется из шестнадцатеричных_числов, где write(1, msg, 13) считывает прошедшие msg и db 10 новую строку в "0123" в шестнадцатеричных_числах.

Алексей Неудачин
11 января 2021 в 13:47
0

@PeterCordes, да, это должно быть dw, но он работает с db и в этом случае, потому что второй байт идет от заполнения .text и равен 00.

Алексей Неудачин
11 января 2021 в 13:53
0

если мы говорим о действительно быстром коде, его все равно нужно делать с помощью simd, поэтому у меня есть np с cx.

Peter Cordes
11 января 2021 в 14:05
0

Есть разница между «не полностью оптимизированным» и «плохим примером, в котором без всякой причины используются случайные размеры операндов». 32-битный - это естественный размер операнда для 64-битного режима, он предотвращает частичные остановки регистра, потому что запись ECX с расширением нулями в RCX. Написание CX - нет. Он также требует префикса размера операнда, поэтому он требует дополнительного размера кода, чтобы сделать его медленнее. Выбор простой скалярной стратегии не оправдывает намеренную деоптимизацию этой реализации без всякой выгоды!

Peter Cordes
11 января 2021 в 14:07
0

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

Алексей Неудачин
11 января 2021 в 14:17
0

@PeterCordes о порядке байтов - pc - это машина lsb. это хорошо известно, я думаю

Peter Cordes
11 января 2021 в 14:21
0

Да, поэтому, если вы хотите распечатать шестнадцатеричное представление всего двойного слова (а не его 4 отдельных байтов с пробелами между каждым байтом), вы должны либо сохранить в обратном направлении в msg (сначала LSByte), либо прочитать в обратном направлении (сначала MSByte). По соглашению, строка шестнадцатеричных цифр без пробелов представляет собой одно число со стандартными значениями наиболее значимых первых позиций 16 ^ n, 16 ^ n-1, 16 ^ n-2, ..., 16 ^ 0, ровно как в 0FF0FEFCEh в вашем источнике, и как printf("%x") . Чтобы указать, что вы сбрасываете каждый байт отдельно в порядке памяти, оставьте пробел между парами шестнадцатеричных цифр.

Peter Cordes
11 января 2021 в 14:24
0

Вот почему все версии SIMD в моем ответе тратят дополнительные усилия на побайтовое обратное целое число с помощью bswap, обратное изменение конечной строки ASCII с помощью pshufb или другие трюки вместо преобразования цифр в порядке памяти. (Или для скаляра сначала прочтите его наиболее значимый полубайт с rol на 4.) В любом случае, я подумал, что поведение типа printf("%x", val) само собой разумеется, но, возможно, мне следует отредактировать это в моем вопросе, если это не очевидно.

Алексей Неудачин
11 января 2021 в 14:32
0

если вы имели дело с хешами, у вас напечатаны обе шестнадцатеричные строки: hash и hash_reverseordered. зависит от того, нужно ли вам значение или массив байтов из него

Алексей Неудачин
11 января 2021 в 17:11
0

@PeterCordes в криптографии у них есть uint256 для хеш-значения, но в большинстве случаев вам нужен массив.