Как конвертировать число в гекс?
Учитывая число в регистре (двоичное целое число), как преобразовать его в строку шестнадцатеричных цифр ASCII?
Цифры могут быть сохранены в памяти или распечатаны на лету, но хранение в памяти и одновременная печать обычно более эффективны. (Вы можете изменить цикл, который хранит, чтобы печатать по одному.)
Можем ли мы эффективно обрабатывать все кусочки параллельно с SIMD? (SSE2 или позже?)
3 ответа
16- степень 2. В отличие от десятичного числа ( Как вывести целое число в программировании на уровне сборки без printf из библиотеки c?) Или других оснований, которые не являются степенью 2, нам не нужно деление, и мы можем сначала извлеките наиболее значимую цифру вместо наименее значащей и считайте в обратном порядке.
Каждая 4-битная группа битов отображается в одну шестнадцатеричную цифру.Мы можем использовать сдвиги или повороты, а также маски AND, чтобы извлечь каждый 4-битный фрагмент ввода как 4-битное целое число.
К сожалению, шестнадцатеричные цифры 0..9 a..f не являются смежными в наборе символов ASCII ( http://www.asciitable.com/). Нам либо нужно условное поведение (ветвь или cmov), либо мы можем использовать таблицу поиска. Таблица поиска, как правило, наиболее эффективна для подсчета команд и производительности; современные процессоры имеют очень быстрые кэши L1d, которые делают повторные загрузки соседних байтов очень дешевыми.
;; NASM syntax, i386 System V calling convention
global itohex
itohex: ; inputs: char* output, unsigned number
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"
До ИМТ2 (shrx/rorx), в x86 отсутствует инструкция копирования и сдвига, поэтому вращение на месте, а затем копирование /AND трудно превзойти. Современный x86 (Intel и AMD) имеет задержку в 1 цикл для поворотов ( https://agner.org/optimize/), поэтому цепочка зависимостей, переносимых циклами, не становится узким местом. (В цикле слишком много инструкций, чтобы он выполнялся даже по 1 циклу за итерацию даже на 5-кратном Ryzen.)
Даже если мы оптимизировали с помощью cmp / jb с указателем конца, чтобы включить cmp/jcc fusion на Ryzen, это все еще 7 моп, больше, чем конвейер может обработать за 1 цикл. dec/jcc макрослияние в один моп происходит только в семействе Intel Sandybridge; AMD только сливает cmp или тест с jcc. я использовал mov ecx,8 и dec/jnz для читабельности человека;lea ecx, [edi+8]а такжеcmp edi, ecx / jb .digit_loopв целом меньше и эффективнее на большем количестве процессоров.
Тестовая программа:
// 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 и... цифр.)
Просто для удовольствия, эта версия начинается в конце буфера и уменьшает указатель. (И условие цикла использует сравнение указателей.) Вы можете остановить его, как только 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
Проверьте ошибки off-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 и AVX512
Большинство из этих версий SIMD могут использоваться с двумя упакованными 32-разрядными целыми числами в качестве входных данных, причем младшие и старшие 8 байтов вектора результатов содержат отдельные результаты, которые можно хранить отдельно сmovqа такжеmovhps, В зависимости от вашего элемента управления в случайном порядке это похоже на использование его для одного 64-разрядного целого числа.
SSSE3pshufbтаблица параллельного поиска. Нет необходимости возиться с циклами, мы можем сделать это с помощью нескольких операций 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
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
Загрузите его в векторный регистр и используйте в качестве маски AND, затем используйте в качестве 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. Я организовал использование регистра, поэтому 2-й movdqa сбился с критического пути, но я не делал этого в первый раз.
AVX может сохранить movdqa, но более интересно то, что с AVX2 мы можем потенциально генерировать 32 байта шестнадцатеричных цифр за один раз из больших входных данных. 2x 64-разрядных целых или 4x 32-разрядных целых числа; используйте 128->256-битную широковещательную загрузку для репликации входных данных в каждую полосу. Оттуда, в переулке vpshufb ymm с контрольным вектором, который считывает нижнюю или верхнюю половину каждой 128-битной дорожки, вы должны установить полубайты для младших 64 битов ввода, распакованных в низшей полосе, и полубайты для старших 64 битов ввода, распакованных в высокая полоса
Или, если входные номера приходят из разных источников, может быть, vinserti128 высокий может стоить того на некоторых процессорах, а не просто выполнять 128-битные операции.
AVX512VBMI (Cannonlake, отсутствует в Skylake-X) имеет 2-регистровое перемешивание байтов vpermt2bчто может объединитьpuncklbwчередование с обращением байтов.Или даже лучше, у нас есть VPMULTISHIFTQBкоторый может извлечь 8 невыровненных байтов из каждого qword источника. Мы можем использовать это, чтобы извлечь нужные кусочки в нужный нам порядок, избегая отдельной инструкции правого сдвига. (Это все еще идет с мусорными битами, все же.)
Чтобы использовать это для 64-битных целых чисел, используйте источник широковещания и управляющий вектор, который захватывает старшие 32 бита входного qword внизу вектора и младшие 32 бита в верхней части вектора.
Чтобы использовать это для более чем 64 бит ввода, используйтеvpmovzxdqобнулить каждое входное слово в qword, настроив для vpmultishiftqb с тем же 28,24,...,4,0 контрольным шаблоном в каждом слове. (например, создание вектора вывода zmm из 256-битного вектора ввода или четырех слов -> рег ymm, чтобы избежать ограничений тактовой частоты и других эффектов фактического выполнения 512-битной инструкции AVX512.)
itohex_AVX512VBMI: ; and AVX1. 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 или змм). Но, к сожалению, на CannonLake ( согласно результатам instlatx64) он все еще имеет задержку в 3 цикла, поэтому pshufb было бы лучше для задержки. Но pshufb требует маскировки вектора управления, так что это ухудшает пропускную способность, предполагая, vpermb только 1 моп. В цикле, где мы можем хранить векторные константы в регистрах (вместо операндов памяти), он сохраняет только 1 инструкцию вместо 2.
Или с AVX512F, мы можем использовать маскирование слиянием, чтобы сдвинуть одно слово вправо, оставив другое неизменным, после передачи числа в регистр XMM. Тогда нам нужен только один регистр байтового перемешивания, vpshufb, чередовать клев и обратный байт. Но тогда вам нужна константа в регистре масок, которая создает пару инструкций для создания. Это был бы больший выигрыш в цикле преобразования нескольких целых чисел в гекс.
Для нецикличной автономной версии функции я использовал две половины одной 16-байтовой константы для разных вещей: set1_epi8(0x0f) в верхней половине, и 8 байтов pshufb контрольный вектор в нижней половине. Это не сильно экономит, потому что операнды вещательной памяти EVEX позволяют vpandd xmm0, xmm0, dword [AND_mask]{1to4}, требующий только 4 байта пространства для константы.
itohex_AVX512F: ;; and AVX1. Saves a pshufb. 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
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
С внутренними компонентами AVX2 или AVX-512
По запросу, перенос некоторых версий моего asm-ответа на C (который, как я написал, также будет действительным C ++). Ссылка на компилятор и обозреватель Godbolt. Они компилируются обратно в asm почти так же хорошо, как мой рукописный asm. (И я проверил, что векторные константы в сгенерированном компилятором asm соответствуют моему
dbдирективы. Определенно что-то, что нужно проверить при переводе asm на встроенные функции, особенно если вы используете
_mm_set_ вместо констант, которые могут показаться более "естественными" в порядке наивысшего приоритета.
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-битной полосе в векторе с удвоенной шириной, например, с
<tcode id="4290012"></tcode> подобно
_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-битном режиме со ссылкой вместо значения arg.)
clang -O3 -m32 фактически компилируется так же, как и мой рукописный asm, за исключением
vmovdqaload константы, а не, потому что в этом случае это действительно все, что нужно. Компиляторы недостаточно умны, чтобы использовать только
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, где переменный сдвиг имеет более низкую пропускную способность и большую задержку, хотя это всего лишь один муп. Это лучше для узких мест внутреннего порта даже на Skylake: 3 инструкции, которые выполняются только на порту 5, по сравнению с 4 (включая
vmovd xmm, reg`` и 2x) для версии ниже, но такое же количество интерфейсных мопов (при условии микро-слияния векторных констант в качестве операндов источника памяти). Также требуется на 1 векторную константу меньше, что всегда хорошо, особенно если это не цикл.
AVX-512 может использовать сдвиг с маской слияния вместо сдвига с переменным счетом, экономя одну векторную константу за счет необходимости настройки регистра маски. Это экономит место в
.rodataно не удаляет все константы, поэтому промах в кеше все равно остановит это. И
mov r,imm/
kmov k,r составляет 2 мопса вместо 1 вне любого цикла, с которым вы его используете.
также AVX2: порт asm-версии itohex_AVX512F с идеей, которую я добавил позже.
// 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 используя (или маскированный сдвиг), чтобы получить байты
num>>4 и
num в тот же регистр XMM для настройки перетасовки байтов с 1 регистром.
vpsrlvdявляется одинарным в Skylake и более поздних версиях, а также в Zen 1 / Zen 2. Однако в Zen это более высокая задержка и, согласно https://uops.info/ , не полностью конвейерная (пропускная способность 2c вместо ожидаемой 1c). из-за того, что это один uop для одного порта.) Но, по крайней мере, он не конкурирует за тот же порт, что и и
vpbroadcastd xmm,xmmна этих процессорах. (На Haswell это 2 мупа, включая один для p5, поэтому он действительно конкурирует, и это строго хуже, чем версия SSSE3, потому что для этого требуется дополнительная константа.)
Хорошим вариантом для Haswell может быть
_mm_slli_epi64(v, 32-4)/
_mm_blend_epi32 -
vpblenddработает на любом порту, не нуждаясь в случайном порте. Или, может быть, даже в целом, поскольку для этого нужна только настройка, а не
vmovd +
vpbroadcastd
Для этой функции требуются две другие векторные константы (шестнадцатеричный lut и комбинированная маска AND и перетасовки). GCC и clang глупо «оптимизируют» 2 использования одной маски в 2 отдельные константы маски, что действительно глупо. (Но в цикле затраты только на установку и регистр, без дополнительных затрат на преобразование.) В любом случае вам понадобятся 2 отдельные 16-байтовые константы для
uint64_t версия этой, но моя рукописная версия asm была умной, используя две половины одной 16-байтовой константы.
MSVC избегает этой проблемы: он компилирует встроенные функции более буквально и не пытается их оптимизировать (что часто плохо, но здесь позволяет избежать этой проблемы). Но MSVC упускает возможность использования AVX-512 GP-register-source
<tcode id="4290047"></tcode> за
_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');
шустро это
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