16 - это степень 2. В отличие от десятичного числа ( Как вывести целое число в Программирование на уровне сборки без printf из библиотеки c? ) или других оснований, которые не являются степенью 2, мыне нужно делить, и мы можем сначала извлечь старшую значащую цифру вместо самой младшей и считать в обратном порядке.
Каждая 4-битная группа битов отображается в одну шестнадцатеричную цифру.Мы можем использовать сдвиги или повороты, а также маски AND, чтобы извлечь каждый 4-битный блок ввода как 4-битное целое число.
К сожалению, шестнадцатеричные цифры 0..9 a..fне смежный в наборе символов ASCII (http://www.asciitable.com/). Нам нужно либо условное поведение (ветвь или cmov), либо мы можем использовать таблицу поиска. Таблица поиска, как правило, наиболее эффективна для подсчета команд и производительности; современные процессорыимеют очень быстрые кэши L1d, которые делают повторные загрузки соседних байтов очень дешевыми. Конвейерное / неупорядоченное выполнение скрывает ~ 5 циклов задержки загрузки кэша 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"
До BMI2 (shrx/ rorx), в x86 отсутствует инструкция копирования и сдвига, поэтому вращение на месте, а затем копирование / AND трудно превзойти 1 . Современные x86 (Intel и AMD) имеют задержку в 1 циклдля поворотов (https://agner.org/optimize/),, так что эта цепочка зависимостей, переносимая циклами, не становится узким местом. (В цикле слишком много инструкций, чтобы он мог выполняться даже по 1 циклу на итерацию даже для Ryzen шириной 5).
Даже если шОптимизирован с помощью cmp / jb с указателем конца для включения слияния cmp / jcc в 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 в целом меньше и более эффективны на большем количестве процессоров.
Сноска 1: Мы могли бы использовать SWAR (SIMD в регистре), чтобы выполнить AND перед сдвигом: x & 0x0f0f0f0fнизкий клочок и shr(x,4) & 0x0f0f0f0f высокий клочок , затем эффективно развернуть, чередуя обработку байта из каждого регистра.(Без какого-либо эффективного способа сделать эквивалент punpcklbw или сопоставления целых чисел с несмежными кодами ASCII, нам все равно нужно просто делать каждый байт отдельно. Но мы могли бы развернуть извлечение байтов и прочитать AH, а затем AL (сmovzx) для сохранения команд смены. Чтение регистров с большими 8 может добавить задержку, но я думаю, что это не потребует дополнительных мопов на текущих процессорах. Запись регистров с высокими 8 обычно не годится для процессоров Intel: это требует дополнительного слиянияUOP, чтобы прочитать полный регистр, с внешней задержкой, чтобы вставить его. Так что получение более широких хранилищ путем перестановки регистров, вероятно, не очень хорошо. В коде ядра, где вы не можете использовать регистры XMM, но можете использовать BMI2, если доступно, pdep может расширить клочки до байтов, но это, вероятно, хуже, чем просто маскировка 2-х способов.)
Тестовая программа:
// 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указатель .(И условие цикла использует сравнение указателей.) Вы можете остановить его, как только 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, 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
Загрузите его в векторный регистр и используйте его в качестве маски 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.Наряду с побитовым AND, это все, что нам нужно для условного добавления чего-либо.
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
Эта версия требует больше векторных констант, чем большинство других.4x16 байтов - это 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: ; 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.
AVX2 variable-shift или AVX512F merge-mask для сохранения чередования
С AVX512F мы можем использовать маскирование слиянием, чтобы сдвинуть один меч вправо, оставив другой без изменений, после передачи числа в регистр XMM.
Или мы могли бы использоватьAVX2 переменная-смещение vpsrlvd, чтобы сделать то же самое , с вектором отсчета смещения [4, 0, 0, 0].Intel Skylake и более поздние имеют однопроцессорную vpsrlvd;Haswell / Broadwell принимают несколько мопов (2p0 + p5).* * * * Ризен 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
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