asm32.info
Keep it simple — code in asm

Малки трикове за напреднали

В тази статия ще изложа някои кратки трикове, които могат да се реализират само на асемблер и правят програмата по-къса и/или по-бърза.

Предполагам, че за разбирането на тези трикове се изискват базисни знания за инструкциите на 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

Preview

Comments

Малки трикове
Filename:
Title: