Новые решения старой задачи

в 11:56, , рубрики: open source, parallel programming, sse, Программирование

image

Или перевод велосипеда на реактивную тягу

Существует одна очень старая задача, возраст которой равен возрасту Американского Стандартного Кода для Обмена Информацией. Конкретнее — это задача преобразования целого числа в его шестнадцатеричное представление 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

  1. Lodsb stosb with jnb
  2. Lodsb stosb with xlatb
  3. General purpose registers with shrd
  4. General purpose registers with punpck
  5. SSE 64 bit
  6. SSE 64 bit unaligned
  7. SSE 128 bit
  8. 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

Автор: V2008n

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js