Или перевод велосипеда на реактивную тягу
Существует одна очень старая задача, возраст которой равен возрасту Американского Стандартного Кода для Обмена Информацией. Конкретнее — это задача преобразования целого числа в его шестнадцатеричное представление ASCII строкой.
В данной публикации будем рассматривать преобразование целого беззнакового шестидесятичетырехбитного числа в строку фиксированной длины без усечения старших нулей.
Задача на первый взгляд кажется элементарной. Она и была бы таковой, если бы таблица ASCII была другой. Но имеем, то что имеем.
Все решения будут только для IA-32 и Intel 64 архитектуры.
Рассмотрим входные-выходные данные и алгоритм решения этой задачи.
Вход:
64-х битное целое беззнаковое число, которое занимает 8 байт по адресам от младших к старшим. Разряды числа располагаются в том же порядке. Каждый разряд занимает 4 бита, в каждом байте их два.
Выход:
Строка ASCII символов, каждый занимает один байт. Каждый байт представляет одну цифру исходного числа. Порядок расположения знаков — первый байт (младший адрес) — самый старший разряд исходного числа.
Алгоритм:
1) Идти от старших тетрад к младшим
2) Взять тетраду и преобразовать ее в байт с расширением нулем.
3) Прибавить 30h
4) Если значение получилось больше 39h то
4.1) Прибавить еще 17 (десятичное)
4.2) Перейти к 5
4.3) Иначе перейти к 5
5) Сохранить полученный байт в строку
6) Пока обработаны не все тетрады, перейти к 2
Решение №1
В лоб
mov cx,8
mov si,value
mov di,hexstr
add si,cx ;highest byte of value
dec si
next_tetrade:
std
lodsb
mov bl,al
and al,0fh
call digit
cld
stosb
mov al,bl
shr al,4
call digit
loop next_tetrade
ret
digit:
add al,30h
cmp al,39h
jnb _zero-nine
;digit greater than 9
add al,11h
_zero-nine:
ret
Как большинство решений в лоб, оно не отличается ни красотой, ни быстродействием. Главная некрасивость — условный переход, который обходит всего-лишь одну команду. Есть два пути наведения красоты.
Первый — использовать древнюю «магию» в виде последовательности команд AAA AAD 17.
Решение №2
AAA AAD 17
mov cx,8
mov si,value
mov di,hexstr
add si,cx ;highest byte of value
dec si
next_tetrade:
std
lodsb
mov bl,al
and al,0fh
call digit
cld
stosb
mov al,bl
shr al,4
call digit
loop next_tetrade
ret
digit:
mov ah,30h
aaa
aad 11h
ret
Другой путь — использовать команду XLATB.
Решение №3
XLATB
mov cx,8
mov si,value
mov di,hexstr
mov bx,hextable
add si,cx
dec si
m3:
std
lodsb
mov ah,al
and al,0fh
xlatb
cld
stosb
mov al,ah
shr al,4
xlatb
stosb
loop m3
ret
hextable db "0123456789ABCDEF"
Оба решения почти идентичны. Но Решение №2 не будет работать в 64-х битном режиме процессора, из-за ликвидации поддержки в нем команд AAA и AAD.
Но неужели имея возможность обрабатывать по 8 байт за раз, мы смиримся с обработкой лишь по 4 бита?
Есть ли способы превратить 9 (1001) в 39h (00111001) а A (1010) в 41h (01000001)?
Попробуем вскрыть суть пары команд AAA AAD, и подобрать им замену.
Замена AAA AAD
mov bl,0ah
xor ah,ah
div bl ; al - частное, ah -остаток. Понятно, что для цифр больше 9 частное будет равно 1.
mov bh,al ;
shl al,4 ; и из этой единицы мы формируем 11h
add al,bh
add al,30h ; voila!
Этот код, конечно, не годится для наших целей, но он дает ценную информацию. Показывает, что можно получить единицу переноса для цифр больше 9. И показывает как эту единицу потом использовать. Вот если бы можно было бы каждую тетраду превратить в байт, то эти байты можно было бы обрабатывать параллельно. Восемь цифр за раз!
Пусть в rax находится исходное число. Чтобы обособить младшие тетрады, нужно всего-лишь выполнить конъюнкцию с маской. А чтобы не потерялись старшие тетрады, копируем их в rbx.
Unpuck
mov rdx,0f0f0f0f0f0f0f0fh
mov rbx,rax
and rax,rdx
shr rbx,4
and rbx,rdx
К сожалению, не получится получить нужный перенос делением. Есть ли другие методы?
Собственно, элементарно: 10h-0ah=6. Достаточно прибавить 6 к каждому байту и получим в старшей тетраде необходимую единицу.
Carry
mov rdx,0f0f0f0f0f0f0f0fh
mov rcx,0606060606060606h
mov rbx,rax
and rax,rdx
mov rdi,rax ;копия пригодится позже
shr rbx,4
and rbx,rdx
add rax,rcx
shr rax,4
and rax,rdx ; теперь в тех байтах, которые соответствуют цифрам больше 9, находятся единицы. В других - нули.
В отличие от предыдущего способа получения единиц переноса с помощью деления, вместо остатка от деления, у нас остается исходная цифра. То-есть, где была цифра A — там она и останется, а не превратится в 0. Следовательно, прибавлять нужно не 11h, а 41h-3ah=7.
И вот возникает очередная задача, как же сделать из единицы семерку? Да еще так, чтобы не затронуть соседние байты. Ведь 7=0111b, значит двумя сдвигами влево и двумя дизъюнкциями можно получить необходимое.
One to seven
mov rsi,rax
shl rsi,1
or rax,rsi ;11b
shl rsi,1
or rax,rsi ; 111b
А теперь соберем кусочки вместе и посмотрим что получится
Unsigned to hex ver 0.1
mov rax,[value]
mov rdx,0f0f0f0f0f0f0f0fh
mov rcx,0606060606060606h
mov rbx,rax
mov rbp,3030303030303030h
shr rbx,4
and rax,rdx
and rbx,rdx
mov rdi,rax
mov r9,rbx
add rax,rcx
add rbx,rcx
shr rax,4
shr rbx,4
and rax,rdx
and rbx,rdx
mov rsi,rax
mov r8,rbx
shl rsi,1
shl r8,1
or rax,rsi
or rbx,r8
shl rsi,1
shl r8,1
or rax,rsi
or rbx,r8
add rax,rbp
add rbx,rbp
add rax,rdi
add rbx,r9
mov [hexstr],rax
mov [hexstr+8],rbx
Если откомпилировать и запустить этот код, обнаружится одна неприятность — порядок цифр в строке не в порядке. Во-первых, цифры идут задом-наперед, а во-вторых, четные и нечетные цифры сгруппированы вместе. Можно, конечно, отдать на вывод и так, но мы же честные и все-таки наведем порядок.
Deinterleaving
mov rcx,4
highpart:
rol rbx,8
shrd [hexstr],rbx,8
rol rax,8
shrd [hexstr],rax,8
loop highpart
mov rcx,4
lowpart:
rol rbx,8
shrd [hexstr+8],rbx,8
rol rax,8
shrd [hexstr+8],rax,8
loop lowpart
ret
От чего хотели уйти, к тому и пришли. Опять побайтная обработка в 64-х режиме. Для того, чтобы перевернуть байты, поставить их задом-наперед, уже давно Интел сделал команду bswap. А вот за деинтерливингом придется обратить взор в сторону MMX, SSE и их развития. И там есть такая команда и имя ей — punpcklbw. Используем наши находки.
Deinterleaving ver. 2
bswap rax
bswap rbx
mov [hexstr],rax
mov [hexstr+8],rbx
movdqu xmm0,[hexstr]
movdqu xmm1,[hexstr+8]
punpcklbw xmm1,xmm0
movdqu [hexstr],xmm1
Стоп-стоп-стоп. Если уж мы начали использовать SSE, может быть найдется и что-то еще полезное? Может быть переписать наш код полностью на SSE.
Unsigned to hex ver 1.1
movdqu xmm0,[value]
pxor xmm1,xmm1
punpcklbw xmm0,xmm1
movdqa xmm1,xmm0
pand xmm1,[efes]
psllq xmm0,4
pand xmm0,[efes]
por xmm0,xmm1
movdqa xmm1,xmm0
paddb xmm1,[sixes]
psrlq xmm1,4
pand xmm1,[efes]
pxor xmm9,xmm9
psubb xmm9,xmm1
pand xmm9,[sevens]
paddb xmm0,xmm9
paddb xmm0,[zeroes]
movdqu [hexstr],xmm0
mov rax,[hexstr]
mov rbx,[hexstr+8]
bswap rax
bswap rbx
mov [hexstr],rbx
mov [hexstr+8],rax
ret
efes: dq 0f0f0f0f0f0f0f0fh
dq 0f0f0f0f0f0f0f0fh
zeroes: dq 3030303030303030h
dq 3030303030303030h
sixes: dq 0606060606060606h
dq 0606060606060606h
sevens: dq 0707070707070707h
dq 0707070707070707h
Здесь мы упростили распаковку, а получение семерок организовали другим способом, с помощью одного вычитания и одной конъюнкции.
А что же мы выиграли вообще? Сравним быстродействие каждого из способов.
| CPU | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Core 2 Quad Q8200 | 670 | 600 | 150 | 77 | 70 | 77 | 76 | 1170 |
| AMD C-60 | 290 | 195 | 290 | 120 | 105 | 120 | 140 | 290 |
- Lodsb stosb with jnb
- Lodsb stosb with xlatb
- General purpose registers with shrd
- General purpose registers with punpck
- SSE 64 bit
- SSE 64 bit unaligned
- SSE 128 bit
- Lodsb stosb with xlatb 128 bit
Значения в попугаях, являются усредненным количеством тиков процессора.
Если у Интела числа хорошо ложатся на теорию, то у АМД они несколько загадочны. Приятным сюрпризом стало высокое быстродействие SSE кода на процессоре от Интел. Можно смело увеличить разрядность преобразуемых чисел до 256 бит с небольшим ростом потребного времени, благо остается еще много свободных xmm регистров в 64-х битном режиме. Вообще, изначально казалось бы последовательную задачу, стало возможно решать очень параллельным методом.
Обратная задача преобразования шестнадцатеричной строки в число решается не менее занимательно.
На закуску:
SSE 128 bit
movdqa xmm0,[value]
pxor xmm1,xmm1
movdqa xmm2,xmm0
punpcklbw xmm0,xmm1
movdqa xmm1,xmm0
punpckhbw xmm2,xmm1
pand xmm1,[efes]
movdqa xmm3,xmm2
psllq xmm0,4
pand xmm3,[efes]
pand xmm0,[efes]
psllq xmm3,4
por xmm0,xmm1
pand xmm2,[efes]
movdqa xmm1,xmm0
por xmm2,xmm3
paddb xmm1,[sixes]
movdqa xmm3,xmm2
psrlq xmm1,4
paddb xmm3,[sixes]
pand xmm1,[efes]
psrlq xmm3,4
pxor xmm9,xmm9
pand xmm3,[efes]
psubb xmm9,xmm1
pxor xmm10,xmm10
pand xmm9,[sevens]
psubb xmm10,xmm3
paddb xmm0,xmm9
pand xmm10,[sevens]
paddb xmm0,[zeroes]
paddb xmm2,xmm10
movdqa [hexstr],xmm0
paddb xmm2,[zeroes]
mov rax,[hexstr]
movdqa [hexstr+16],xmm2
mov rbx,[hexstr+8]
mov rcx,[hexstr+16]
bswap rax
mov rdx,[hexstr+16+8]
bswap rbx
bswap rcx
mov [hexstr],rbx
bswap rdx
mov [hexstr+8+16],rax
mov [hexstr+8],rcx
mov [hexstr+16],rdx
ret
