Малки трикове за напреднали
В тази статия ще изложа някои кратки трикове, които могат да се реализират само на асемблер и правят програмата по-къса и/или по-бърза.
Предполагам, че за разбирането на тези трикове се изискват базисни знания за инструкциите на x86, както и познания за бройни системи - специално двоична и шестнайсетична, както и за основните бинарни логически операции.
По-начинаещите също могат да прочетат статията и дори и да не разберат всичко, могат да питат, а и някои от примерите могат да им помогнат да си изградят "мислене на асемблер".
1. Аритметика
1.1. Изчисляване на абсолютна стойност
Най-късото решение известно до сега е:
.abs:
neg eax
jl .abs
Дължина 4 байта. Кодът работи така:
а) Ако eax съдържа отрицателно число на входа, след инверсията резултата е по-голям от 0, прехода не се изпълнява и на изхода получаваме положителна стойност.
б) Ако eax съдържа положително число, след инверсията, резултата е по-малък от нула, прехода се изпълнява и попадаме в ситуация а) когато имаме отрицателно число на входа.
Този трик е по-известен във варианта:
.abs:
neg eax
js .abs
Този вариант има обаче един недостатък, че има скрит бъг, който води до безкраен цикъл. Наистина, ако на входа се подаде числото $80000000, което няма положителен еквивалент, се получава безкраен цикъл и програмата ще заспи.
При варианта с jl проблема се решава, защото при него се използва и флага за препълване (инструкцията е за работа с числа със знак) който при "neg $80000000" се вдига, индицирайки грешен знак и прехода не се изпълнява.
Горният вариант е най-късото възможно решение, но дали е най-бързото. При новите процесори - не, заради прехода. Въобще при последните модели процесори, условните преходи трябва да се избягват, ако искаме да получим най-високата скорост на изпълнение.
Ето един вариант на abs, без използването на преходи:
cdq
xor eax, edx
sub eax, edx
Как работи този код: Знаем, че:
-x = (not x) + 1 = (not x) - (-1); (1)
От друга страна знаем, че:
not x = x xor (-1); (2)
Инструкцията cdq (convert dword to qword) запълва edx със знаковият бит на eax - тоест ако eax e положително, edx = 0, а ако eax е отрицателно, edx=-1.
Сега, ако на входа на кода се подаде положително число, edx = 0 и операциите върху eax са:
xor eax, 0
sub eax, 0
Което очевидно няма да промени стойността му. Ако eax е отрицателно, ще имаме:
xor eax, -1 ;( not eax от (2) )
sub eax, -1 ;( събирането с 1 от (1) )
Което ще ни даде точно neg eax.
Този код ще се изпълни по-бързо на компютри Pentium и по-нови.
Недостатъците му са два:
1. задължително трябва да се използват eax/edx (ax/dx)
2. Губи се съдържанието на edx.
3. инструкцията cdq не е от най бързите в новите процесори.
Решението на проблеми 1 и 3 е замяната на cdq със еквивалента и:
mov edx, eax
sar edx, 31
Така получаваме окончателният код:
mov edx, eax
sar edx, 31
xor eax, edx
sub eax, edx
Този код с дължина 9 байта е най-бърз от показаните, ако се направи правилно сдвояване на кода, за използване на двата конвеера на новите процесори. Тоест между инструкциите трябва да се вмъкнат други инструкции от кода, които не са свързани с тези и могат да се изпълняват паралелно.
Допълнително предимство е, че могат да се използват произволни два регистъра.
1.2. Функции Min/Max
Задачата е: Имаме две беззнакови числа в два регистъра да кажем eax и ebx. На изхода, в eax трябва да е по-малкото/по-голямото от двете числа. Задачата да се реши без преходи.
Ето го и решението с използване на един допълнителен регистър:
;---------------------------------
; Вход:
; eax, ebx - 2 числа без знак
; Изход:
; eax = min(eax, ebx)
;---------------------------------
.min:
sub ebx,eax
sbb ecx,ecx
and ecx,ebx
add eax,ecx
Как работи:
След първата инструкция, в ebx имаме разликата между двете числа (тоест това е числото, което трябва да прибавим към eax, за да получим числото в ebx)
Флагът CF = 1 ако ebx<eax или CF=0 ако ebx>eax.
Втората инструкция нулира ecx, ако CF=0 и запълва ecx с 1-ци (ecx=-1) ако CF=1 (напомням, че инструкцията sbb op1, op2 извършва следната операция: op1 = op1 - op2 - CF)
Третата инструкция вкарва в ecx стойността на разликата (ebx) но само ако ecx = (-1). Иначе ecx си остава 0 ( and със 0 = 0 )
И накрая последната инструкция или събира eax със 0 (ако ecx e 0, тоест ако ebx>eax на входа) или събира eax с разликата (ebx-eax) ако ecx = (ebx-eax), тоест ако на входа ebx<eax. Но eax+(ebx-eax) е точно равно на ebx; тоест на изхода eax = входното ebx.
За да приспособим този код за функцията max, трябва само да инвертираме (not) стойността на ecx след инструкцията sbb.
Тогава ще имаме ecx=-1 ако CF=0 (ebx > eax) и съответно ecx=0 ако CF=1 (ebx < eax).
Ето го и пълният код:
;---------------------------------
; Вход:
; eax, ebx - 2 числа без знак
; Изход:
; eax = max(eax, ebx)
;---------------------------------
.max:
sub ebx,eax
sbb ecx,ecx
not ecx
and ecx,ebx
add eax,ecx
Смятам, че работата на този код не се нуждае от пояснения.
Само ще добавя, че за постигане на максимална скорост, инструкциите трябва да се сдвоят правилно с други инструкции за паралелно изпълнение.
Оригинала на кода за функцията min е на Агнер Фог. Модификацията за изпълнение на max е на автора на тази статия.
1.3. Беззнаково събиране с насищане без MMX
MMX инструкциите имат събиране с насищане, обаче използването им, ако не е масово е неудобно, а в много случаи вероятно ще е и по-бавно.
Отделно използването на новите разширения прави програмата силно нечетлива.
За щастие, използването на нормалните x86 инструкции в случая е просто и доста ефективно. Стойността на насищане е 255 ако работим с байтове, 65535 за думи или 4294967295 за двойна дума.
Ето кода за 8 битово събиране с насищане:
; AL е първото събираемо и съдържа резултата.
; BL е второто събираемо.
add al,bl ; събираме.
sbb bl,bl ; BL = 0 ако няма пренос (препълване) или $ff ако има.
or al,bl ; AL = сумата, ако няма пренос или $ff ако има.
; BL = 0 ако няма препълване или $ff ако има.
1.4. Инструкцията LEA за пресмятания
Инструкцията lea се използва обикновенно за адресна аритметика, тоест за изчисляването
на адреси в масиви и структури. Но нищо не ни пречи да я използваме и за изчисляване на
аритметични изрази.
Поради големите възможности на адресациите при процесорите x86, възможностите, които ни дава тази инструкция са наистина големи.
Общият вид на всеки адрес в процесора е:
EA = [reg1 + N*reg2 + M]
където N = {1, 2, 4 или 8} a M е произволна 32 битова константа.
Както може да се види, това ни дава, макар и ограничена, но възможност да правим две събирания и едно умножение само с една инструкция.
Ето и някои примери за умножение на числа които не са степен на 2:
lea ebx, [eax+2*eax] ; ebx = 3*eax
lea ebx, [eax+4*eax] ; ebx = 5*eax
lea ebx, [eax+8*eax] ; ebx = 9*eax
С използване на още една инструкция може да се реализира бързо умножение по 10:
lea ebx, [eax+4*eax] ; ebx = eax * 5
shl ebx, 1 ; ebx = ebx * 2
Трябва да отбележа, че ако пишете на FASM или Fresh, ще можете да използвате директно константи които не са степен да 2 със сорса. Тоест FASM допуска:
lea eax, [5*ebx]
lea eax, [9*eax]
и автоматично ще го компилира като:
lea eax, [ebx+4*ebx]
lea eax, [eax+8*eax]
Другото предимство на lea е че не модифицира флаговете. Тоест можем да променяме стойността на регистър, без флаговете да се променят от последната операция. Например:
cmp eax, [esi]
lea esi, [esi+4] ; esi = esi + 4
je .equal
.notequal:
.equal:
Това може да направи кода много по-четлив и кратък в някои случаи.
2. Цикли
Един интересен начин за реализация на два вложени цикъла със използване на само един регистър. Оптимизацията е по размер, но по всяка вероятност ще работи и доста бързо:
OuterLoopCount = 10
InnerLoopCount = 20
mov ecx, OuterLoopCount
.outerloop:
; инструкции за външният цикъл
mov ch, InnerLoopCount
.innerloop:
; инструкции за вътрешният цикъл
dec ch
jnz .innerloop
loop .outerloop
Идеята е да се използва старшият байт на cx (ch) за организиране на вътрешният цикъл. След излизането от този цикъл, ch=0, така че инструкцията loop може да работи правилно със целият регистър ecx.
3. Тестове и проверки
3.1. Проверка за точна степен на 2
Понякога трябва да проверим дали едно число е точна степен на 2. Тоест, дали съдържа един и само един бит, равен на 1.
; eax съдържа числото, което трябва да се тества. Използва се един допълнителен регистър. В случая ebx.
xor ebx, ebx ; eax = X, ebx = 0
sub ebx, eax ; ebx = -X
jz .zero ; числото е 0
and ebx, eax
cmp ebx, eax
jne .not_power_of_two
; тук сме, ако eax е точна степен на 2.
След края на този код, ebx съдържа бита от eax с най-ниска степен, който е равен на 1. (или 0 ако eax=0) Ако тази стойност не ни трябва, то кода може да се направи и по-прост:
lea ebx, [eax-1]
and ebx, eax
jnz .not_power_of_two
test eax, eax
jz .zero
; тука сме, само ако eax е степен на 2
3.2. Проверка на сложни условия
Този пример ще ни позволи да правим по елегантен и бърз начин сложни проверки от вида:
if (x=a) and (y=b) then
; някакъв код
else
; друг код
end if
Ето и кода на асемблер (приемаме, че a и b са константи, а x и y променливи, но това разбира се съвсем не е задължително):
mov eax, a
mov ebx, b
xor eax, [x]
xor ebx, [y]
or eax, ebx
jnz .else
.then:
; тук е кода за "then"
jmp .еndif
.else:
; тук е кода аз "else"
.endif:
Операцията xor x, a ще даде 0 само ако двата операнда са равни. В противен случай, поне един бит ще бъде 1. Същото е и при xor y, b ; Операцията or между двете стойности ще даде 0 от своя страна само ако и двата операнда са 0, тоест ако (x=a) и (y=b). Съответно условният преход ще отиде на .else ако резултата от or инструкцията е <> 0 или ще продължи надолу, ако резултата е 0, тоест условието е изпълнено. Използвайки още някои регистри можем да разширим условието до повече членове, тоест до:
if (x=a) and (y=b) and (z=c) and (t=d) then
...
Голямо преимущество на горният код е, че отделните операции xor и mov не са зависими, тоест на новите процесори ще се изпълняват паралелно в двата конвеера с максимална скорост.
Last modified on: 01.08.2013 08:17:43