Wskazówki dotyczące gry w golfa w kodzie maszynowym x86 / x64


27

Zauważyłem, że nie ma takiego pytania, więc oto:

Czy masz ogólne wskazówki dotyczące gry w golfa w kodzie maszynowym? Jeśli wskazówka dotyczy tylko określonego środowiska lub konwencji telefonicznej, określ to w odpowiedzi.

Proszę podać tylko jedną wskazówkę na odpowiedź (patrz tutaj ).

Odpowiedzi:


11

mov-immediate jest drogi dla stałych

To może być oczywiste, ale wciąż będę to tutaj umieszczał. Zasadniczo opłaca się myśleć o reprezentacji liczby na poziomie bitowym, gdy trzeba zainicjować wartość.

Inicjalizacja za eaxpomocą 0:

b8 00 00 00 00          mov    $0x0,%eax

należy skrócić (w celu zwiększenia wydajności i rozmiaru kodu ) do

31 c0                   xor    %eax,%eax

Inicjalizacja za eaxpomocą -1:

b8 ff ff ff ff          mov    $-1,%eax

można skrócić do

31 c0                   xor    %eax,%eax
48                      dec    %eax

lub

83 c8 ff                or     $-1,%eax

Lub bardziej ogólnie, dowolna 8-bitowa wartość z rozszerzonym znakiem może być utworzona w 3 bajtach z push -12(2 bajty) / pop %eax(1 bajt). Działa to nawet w przypadku rejestrów 64-bitowych bez dodatkowego prefiksu REX; push/ popdefault operand-size = 64.

6a f3                   pushq  $0xfffffffffffffff3
5d                      pop    %rbp

Lub biorąc pod uwagę znaną stałą w rejestrze, możesz utworzyć inną pobliską stałą za pomocą lea 123(%eax), %ecx(3 bajtów). Jest to przydatne, jeśli potrzebujesz wyzerowanego rejestru i stałej; xor-zero (2 bajty) + lea-disp8(3 bajty).

31 c0                   xor    %eax,%eax
8d 48 0c                lea    0xc(%eax),%ecx

Zobacz także Ustaw efektywnie wszystkie bity w rejestrze procesora na 1


Ponadto, aby zainicjować rejestr o małej (8-bitowej) wartości innej niż 0: użyj np. push 200; pop edx- 3 bajtów do inicjalizacji.
anatolyg

2
BTW, aby zainicjować rejestr na -1, użyj decnp.xor eax, eax; dec eax
anatolyg

@anatolyg: 200 jest kiepskim przykładem, nie mieści się w znaku-Immun-Extended-8. Ale tak, push imm8/ pop regma 3 bajty i jest fantastyczny dla stałych 64-bitowych na x86-64, gdzie dec/ incto 2 bajty. I push r64/ pop 64(2 bajty) może nawet zastąpić 3 bajty mov r64, r64(3 bajty REX). Zobacz także Ustaw efektywnie wszystkie bity w rejestrze procesora na 1 dla takich rzeczy, jak lea eax, [rcx-1]dana znana wartość w eax(np. Jeśli potrzebujesz wyzerowanego rejestru i innej stałej, po prostu użyj LEA zamiast push / pop
Peter Cordes

10

W wielu przypadkach instrukcje oparte na akumulatorze (tj. Te, które przyjmują (R|E)AXza argument docelowy) są o 1 bajt krótsze niż instrukcje w ogólnym przypadku; zobacz to pytanie na StackOverflow.


Zwykle najbardziej przydatne są al, imm8przypadki specjalne, takie jak or al, 0x20/ sub al, 'a'/ cmp al, 'z'-'a'/ ja .non_alphabeticpo 2 bajty, zamiast 3. Użycie aldanych znakowych również pozwala lodsbi / lub stosb. Lub użyj aldo przetestowania czegoś o niskim bajcie EAX, na przykład lodsd/ test al, 1/ setnz clsprawia, że ​​cl = 1 lub 0 dla parzystych / nieparzystych. Ale w rzadkim przypadku, gdy potrzebujesz natychmiastowej wersji 32-bitowej, to na pewno op eax, imm32, tak jak w mojej odpowiedzi kluczowej barwy
Peter Cordes

8

Wybierz konwencję połączeń, aby wstawić argumenty tam, gdzie chcesz.

Językiem twojej odpowiedzi jest asm (właściwie kod maszynowy), więc traktuj to jako część programu napisanego w asm, a nie w C-kompilowanej dla x86. Twoja funkcja nie musi być łatwo wywoływana z C przy użyciu dowolnej standardowej konwencji wywoływania. To niezły bonus, jeśli nie kosztuje dodatkowych bajtów.

W czystym programie asm normalne jest, że niektóre funkcje pomocnicze używają konwencji wywoływania, która jest dla nich wygodna i dla ich rozmówcy. Takie funkcje dokumentują swoją konwencję wywoływania (wejścia / wyjścia / clobbers) z komentarzami.

W rzeczywistości nawet programy asm (jak sądzę) zwykle używają spójnych konwencji wywoływania dla większości funkcji (szczególnie w różnych plikach źródłowych), ale każda ważna funkcja może zrobić coś specjalnego. W grze w golfa optymalizujesz bzdury za pomocą jednej funkcji, więc oczywiście jest to ważne / specjalne.


Aby przetestować swoją funkcję z poziomu programu C, możesz napisać opakowanie, które umieszcza argumenty w odpowiednich miejscach, zapisuje / przywraca wszelkie dodatkowe rejestry, które kasujesz, i umieszcza wartość zwracaną, e/raxjeśli jeszcze jej nie było.


Granice tego, co rozsądne: wszystko, co nie nakłada nieuzasadnionego obciążenia na osobę dzwoniącą:

  • ESP / RSP musi być zabezpieczony podczas połączeń; inne liczby całkowite są uczciwą grą. (RBP i RBX są zwykle zachowywane w normalnych konwencjach, ale można zablokować oba.)
  • Dowolny argument w dowolnym rejestrze (z wyjątkiem RSP) jest uzasadniony, ale nie jest wymagane poproszenie dzwoniącego o skopiowanie tego samego argumentu do wielu rejestrów.
  • Wymaganie, aby DF (flaga kierunku łańcucha dla lods/ stos/ itd.) Była czysta (w górę) przy wywołaniu / ret jest normalne. Zgoda na niezdefiniowanie podczas połączenia / połączenia byłaby w porządku. Wymaganie, aby zostało wyczyszczone lub ustawione przy wejściu, ale pozostawienie go zmodyfikowanego po powrocie byłoby dziwne.

  • Zwracanie wartości FP w x87 st0jest rozsądne, ale zwracanie st3ze śmieciami w innym rejestrze x87 nie jest. Dzwoniący musiałby wyczyścić stos x87. Nawet zwracanie się st0z niepustymi rejestrami wyższych stosów również byłoby wątpliwe (chyba że zwracasz wiele wartości).

  • Twoja funkcja zostanie wywołana za pomocą call, podobnie jak [rsp]twój adres zwrotny. Państwo może uniknąć call/ retna x86 przy użyciu łącza rejestr jak lea rbx, [ret_addr]/ jmp functioni zwrot z jmp rbx, ale to nie jest „rozsądne”. To nie jest tak wydajne jak call / ret, więc nie jest to coś, co można znaleźć w prawdziwym kodzie.
  • Clobbering nieograniczonej pamięci powyżej RSP jest nieuzasadniony, ale clobbering funkcji argumentów na stosie jest dozwolony w normalnych konwencjach wywoływania. System Windows x64 wymaga 32 bajtów miejsca w cieniu powyżej adresu zwrotnego, podczas gdy system V86 dla systemu x86-64 zapewnia 128-bajtową czerwoną strefę poniżej RSP, więc każdy z nich jest rozsądny. (Lub nawet znacznie większa czerwona strefa, szczególnie w samodzielnym programie, a nie w funkcji).

Przypadki graniczne: napisz funkcję, która tworzy sekwencję w tablicy, biorąc pod uwagę pierwsze 2 elementy jako argumenty funkcji . Zdecydowałem , że osoba wywołująca zapisze początek sekwencji w tablicy i po prostu przekaże wskaźnik do tablicy. To zdecydowanie nagina wymagania pytania. Uważałem biorąc args pakowane w xmm0za movlps [rdi], xmm0, co byłoby również dziwne konwencja powołanie.


Zwraca wartość logiczną w FLAGACH (kody warunków)

Wykonują to wywołania systemowe OS X ( CF=0oznacza brak błędu): czy używanie rejestru flag jako logicznej wartości zwracanej jest uważane za złą praktykę? .

Każdy warunek, który można sprawdzić za pomocą jednego JCC, jest całkowicie uzasadniony, szczególnie jeśli można wybrać taki, który ma semantyczne znaczenie dla problemu. (np. funkcja porównania może ustawić flagi, więc jnezostaną one wzięte, jeśli nie będą równe).


Wymagaj, aby wąskie argumenty (jak a char) były znakami, lub zero rozszerzane do 32 lub 64 bitów.

Nie jest to nierozsądne; Użycie movzxlub movsx uniknięcie częściowego spowolnienia rejestru jest normalne w nowoczesnej wersji x86 asm. W rzeczywistości clang / LLVM już tworzy kod, który zależy od nieudokumentowanego rozszerzenia konwencji wywoływania Systemu x86-64 System V: argumenty węższe niż 32 bity są znakami lub zero rozszerzone do 32 bitów przez osobę dzwoniącą .

Możesz udokumentować / opisać rozszerzenie do 64 bitów, pisząc uint64_tlub int64_tw swoim prototypie, jeśli chcesz. np. możesz użyć loopinstrukcji, która wykorzystuje całe 64 bity RCX, chyba że użyjesz prefiksu rozmiaru adresu, aby zastąpić rozmiar do 32-bitowego ECX (tak naprawdę, rozmiar adresu nie rozmiar operandu).

Zauważ, że longjest to tylko 32-bitowy typ w 64-bitowym ABI dla Windows i ABI dla Linux x32 ; uint64_tjest jednoznaczny i krótszy niż typ unsigned long long.


Istniejące konwencje połączeń:

  • Windows 32-bit __fastcall, już zasugerowany przez inną odpowiedź : liczba całkowita argumentuje w ecxi edx.

  • x86-64 System V : przekazuje wiele argumentów do rejestrów i ma wiele rejestrów z zaplombowanymi wywołaniami, których można używać bez prefiksów REX. Co ważniejsze, faktycznie wybrano, aby umożliwić kompilatorom wstawianie memcpylub zapisywanie tak rep movsbłatwo: pierwsze 6 argumentów liczb całkowitych / wskaźników jest przekazywanych w RDI, RSI, RDX, RCX, R8, R9.

    Jeśli twoja funkcja używa lodsd/ stosdwewnątrz pętli, która działa rcxrazy (z loopinstrukcją), możesz powiedzieć „wywoływalne z C jak int foo(int *rdi, const int *rsi, int dummy, uint64_t len)w konwencji wywoływania Systemu x86-64”. przykład: chromakey .

  • 32-bitowy GCC regparm: Argumenty liczb całkowitych w EAX , ECX, EDX, return w EAX (lub EDX: EAX). Posiadanie pierwszego argumentu w tym samym rejestrze co wartość zwracana pozwala na pewne optymalizacje, takie jak ten przypadek z przykładowym wywoływaczem i prototypem z atrybutem funkcji . I oczywiście AL / EAX jest specjalny dla niektórych instrukcji.

  • Linux x32 ABI używa 32-bitowych wskaźników w trybie długim, dzięki czemu można zapisać prefiks REX podczas modyfikowania wskaźnika ( przykładowy przypadek użycia ). Nadal możesz używać 64-bitowego rozmiaru adresu, chyba że masz w rejestrze 32-bitową ujemną liczbę całkowitą z rozszerzeniem zera (tak więc byłaby to duża wartość bez znaku [rdi + rdx]).

    Zauważ, że push rsp/ pop raxma 2 bajty i jest ekwiwalentem mov rax,rsp, więc nadal możesz kopiować pełne rejestry 64-bitowe w 2 bajtach.


Kiedy wyzwania wymagają zwrotu tablicy, czy uważasz, że powrót na stos jest uzasadniony? Myślę, że tak właśnie zrobią kompilatory, zwracając strukturę według wartości.
qwr

@qwr: nie, główne konwencje wywoływania przekazują ukryty wskaźnik do wartości zwracanej. (Niektóre konwencje przekazują / zwracają małe struktury w rejestrach). C / C ++ zwraca strukturę według wartości pod maską i zobacz koniec Jak obiekty działają w x86 na poziomie zespołu? . Zauważ, że przekazywanie tablic (wewnątrz struktur) powoduje skopiowanie ich na stos dla SysV x86-64: Jakim typem danych C11 jest tablica zgodnie z AMD64 ABI , ale Windows x64 przekazuje wskaźnik non-const.
Peter Cordes

więc co myślisz o rozsądnym czy nie? Czy liczysz x86 zgodnie z tą zasadą codegolf.meta.stackexchange.com/a/8507/17360
qwr

1
@qwr: x86 nie jest „językiem stosowym”. x86 jest maszyną rejestrującą z pamięcią RAM , a nie maszyną stosową . Maszyna stosowa jest jak odwrotna notacja, jak rejestry x87. fld / fld / faddp. Stos wywołań x86 nie pasuje do tego modelu: wszystkie normalne konwencje wywoływania pozostawiają niezmodyfikowane RSP lub wstawiają argumenty ret 16; nie podają adresu zwrotnego, nie wypychają tablicy, a następnie push rcx/ ret. Dzwoniący musiałby znać rozmiar tablicy lub zapisać RSP gdzieś poza stosem, aby się znaleźć.
Peter Cordes

Wywołanie push adres instrukcji po wywołaniu w stosie jmp do wywołanej funkcji; ret pop adres ze stosu i jmp na ten adres
RosLuP

7

W przypadku AL / AX / EAX należy używać kodowania skróconego specjalnego przypadku oraz innych krótkich formularzy i instrukcji jednobajtowych

Przykłady zakładają tryb 32/64-bitowy, w którym domyślny rozmiar operandu to 32 bity. Prefiks wielkości argumentu zmienia instrukcję na AX zamiast EAX (lub odwrotnie w trybie 16-bitowym).

  • inc/decrejestr (inny niż 8-bitowy): inc eax/ dec ebp. (Nie x86-64: 0x4xbajty opcode zostały zmienione na prefiksy REX, więc inc r/m32jest to jedyne kodowanie).

    8-bitowy inc bljest 2 bajty, z użyciem inc r/m8kodu operacji / M + Modr argumentu operacji kodowania . Więc używać inc ebxdo przyrostu bl, czy jest to bezpieczne. (np. jeśli nie potrzebujesz wyniku ZF w przypadkach, gdy górne bajty mogą być niezerowe).

  • scasd: e/rdi+=4, wymaga, aby rejestr wskazywał na czytelną pamięć. Czasami przydatne, nawet jeśli nie obchodzi cię wynik FLAGI (jak cmp eax,[rdi]/ rdi+=4). W trybie 64-bitowym scasbmoże działać jako 1-bajtowyinc rdi , jeśli lodsb lub stosb nie są przydatne.

  • xchg eax, r32: To gdzie 0x90 NOP pochodzi z: xchg eax,eax. Przykład: ponownie ułóż 3 rejestry z dwiema xchginstrukcjami w pętli cdq/ dla GCD w 8 bajtach, gdzie większość instrukcji jest jednobajtowa, w tym nadużycie / zamiast /idivinc ecxlooptest ecx,ecxjnz

  • cdq: znak rozszerza EAX do EDX: EAX, tzn. kopiuje wysoki bit EAX do wszystkich bitów EDX. Aby utworzyć zero ze znanymi nieujemnymi lub uzyskać 0 / -1, aby dodać / sub lub maskować. Lekcja historii x86: cltqvs.movslq oraz mnemoniki AT&T vs. Intel dla tego i pokrewnych cdqe.

  • lodsb / d : like mov eax, [rsi]/ rsi += 4without clobbering flags. (Zakładając, że DF jest jasne, jakie standardowe konwencje wywoływania wymagają przy wprowadzaniu funkcji.) Również stosb / d, czasami scas, a rzadziej movs / cmps.

  • push/ pop reg. np. w trybie 64-bitowym push rsp/ pop rdima 2 bajty, ale mov rdi, rsppotrzebuje prefiksu REX i ma 3 bajty.

xlatbistnieje, ale rzadko jest użyteczny. Dużej tabeli odnośników należy unikać. Nigdy też nie znalazłem zastosowania dla instrukcji AAA / DAA lub innych instrukcji BCD lub 2-ASCII.

1 bajt lahf/ sahfrzadko są przydatne. Ty mógł lahf / and ah, 1jako alternatywa setc ah, ale nie jest to zwykle użyteczne.

A konkretnie w przypadku CF sbb eax,eaxjest 0 / -1, a nawet nieudokumentowany, ale powszechnie obsługiwany 1-bajtowy salc(zestaw AL z Carry), który skutecznie działa sbb al,albez wpływu na flagi. (Usunięte w x86-64). Użyłem SALC w Wyzwaniu uznania użytkownika nr 1: Dennis ♦ .

1-bajtowy cmc/ clc/ stc(odwrócenie („uzupełnienie”), wyczyszczenie lub zestaw CF) są rzadko przydatne, chociaż znalazłem zastosowaniecmc w dodawaniu o rozszerzonej precyzji z podstawowymi fragmentami 10 ^ 9. Aby bezwarunkowo ustawić / wyczyścić CF, zwykle należy to zrobić jako część innej instrukcji, np. xor eax,eaxCzyści CF, a także EAX. Nie ma równoważnych instrukcji dla innych flag stanu, tylko DF (kierunek ciągu) i IF (przerwania). Flaga przenoszenia jest specjalna dla wielu instrukcji; shift ustawia to, adc al, 0może dodać go do AL w 2 bajtach, a wspomniałem wcześniej o nieudokumentowanej SALC.

std/ cldrzadko wydaje się tego warte . Zwłaszcza w kodzie 32-bitowym lepiej jest po prostu użyć decwskaźnika i movoperandu źródła pamięci w instrukcji ALU zamiast ustawiać DF so lodsb/ stosbgo w dół zamiast w górę. Zazwyczaj jeśli trzeba w dół w ogóle, trzeba jeszcze inny wskaźnik idzie w górę, tak że trzeba więcej niż jeden std, a cldw całej funkcji do wykorzystania lods/ stosdla obu stron. Zamiast tego po prostu użyj instrukcji strunowych dla kierunku w górę. (Standardowe konwencje wywoływania gwarantują DF = 0 przy wprowadzaniu funkcji, więc można założyć, że za darmo bez użycia cld.)


Historia 8086: dlaczego te kodowania istnieją

W oryginalnym 8086, AX był wyjątkowy: instrukcje jak lodsb/ stosb, cbw, mul/ divi inni używają go w sposób dorozumiany. Oczywiście nadal tak jest; obecny x86 nie upuścił żadnego z kodów 8086 (przynajmniej żadnego z oficjalnie udokumentowanych). Ale później procesory dodały nowe instrukcje, które dały lepsze / bardziej wydajne sposoby robienia rzeczy bez uprzedniego kopiowania lub zamiany ich na AX. (Lub do EAX w trybie 32-bitowym.)

np. 8086 brakowało później dodatków takich jak movsx/ movzxaby załadować lub przenieść + przedłużyć znak lub 2 i 3 operand imul cx, bx, 1234, które nie dają wyniku w połowie i nie mają żadnych ukrytych argumentów.

Ponadto głównym wąskim gardłem 8086 było pobieranie instrukcji, więc optymalizacja pod kątem rozmiaru kodu była wtedy ważna dla wydajności . Projektant ISA z 8086 (Stephen Morse) poświęcił dużo miejsca na kodowanie opcodu na specjalne przypadki dla AX / AL, w tym specjalne (E) AX / AL-docelowe kody dla wszystkich podstawowych instrukcji ALU natychmiast-src , po prostu opcode + natychmiast bez bajtu ModR / M. 2 bajty add/sub/and/or/xor/cmp/test/... AL,imm8lub AX,imm16lub (w trybie 32-bitowym) EAX,imm32.

Ale nie ma specjalnego przypadku EAX,imm8, więc zwykłe kodowanie ModR / M add eax,4jest krótsze.

Zakładamy, że jeśli będziesz pracować nad niektórymi danymi, będziesz chciał mieć je w AX / AL, więc zamiana rejestru na AX była czymś, co możesz chcieć zrobić, może nawet częściej niż kopiowanie rejestru do AX za pomocą mov.

Wszystko w kodowaniu instrukcji 8086 obsługuje ten paradygmat, od instrukcji takich jak lodsb/wdo wszystkich kodowań specjalnych przypadków dla bezpośrednich znaków w EAX po ich niejawne użycie nawet do mnożenia / dzielenia.


Nie daj się ponieść emocjom; nie jest automatycznie wygraną zamiana wszystkiego na EAX, szczególnie jeśli potrzebujesz natychmiastowego dostępu do rejestrów 32-bitowych zamiast 8-bitowych. Lub jeśli potrzebujesz przeplatać operacje na wielu zmiennych w rejestrach jednocześnie. Lub jeśli korzystasz z instrukcji z 2 rejestrami, w ogóle nie następuje to natychmiast.

Ale zawsze należy pamiętać: czy robię coś, co byłoby krótsze w EAX / AL? Czy mogę zmienić układ, aby mieć to w AL, lub czy obecnie lepiej wykorzystuję AL z tym, do czego już go używam.

Swobodnie miksuj operacje 8-bitowe i 32-bitowe, aby czerpać korzyści, gdy tylko jest to bezpieczne (nie musisz przeprowadzać operacji w pełnym rejestrze ani nic takiego).


cdqjest użyteczny, dla divktórego edxw wielu przypadkach wymaga wyzerowania .
qwr

1
@qwr: racja, możesz nadużyć cdqprzed niepodpisaniem, divjeśli wiesz, że twoja dywidenda jest niższa niż 2 ^ 31 (tj. nie jest ujemna, gdy traktowana jest jak podpisana), lub jeśli użyjesz jej przed ustawieniem eaxpotencjalnie dużej wartości. Normalnie (poza code-golf) chcesz użyć cdqjako konfiguracja do idivi xor edx,edxprzeddiv
Peter Cordes

5

Użyj fastcallkonwencji

Platforma x86 ma wiele konwencji wywoływania . Powinieneś użyć tych, które przekazują parametry w rejestrach. W X86_64 kilka pierwszych parametrów jest przekazywanych do rejestrów, więc nie ma problemu. Na platformach 32-bitowych domyślna konwencja wywoływania ( cdecl) przekazuje parametry na stosie, co nie jest dobre dla gry w golfa - dostęp do parametrów na stosie wymaga długich instrukcji.

Podczas korzystania fastcallz platform 32-bitowych zwykle przekazywane są 2 pierwsze parametry ecxi edx. Jeśli twoja funkcja ma 3 parametry, możesz rozważyć wdrożenie jej na platformie 64-bitowej.

Prototypy funkcji C dla fastcallkonwencji (wzięte z tej przykładowej odpowiedzi ):

extern int __fastcall SwapParity(int value);                 // MSVC
extern int __attribute__((fastcall)) SwapParity(int value);  // GNU   

Lub użyj w pełni niestandardowej konwencji wywoływania , ponieważ piszesz w czystym asmie, niekoniecznie pisząc kod do wywołania z C. Zwracanie wartości logicznych w FLAGS jest często wygodne.
Peter Cordes,

5

Odejmij -128 zamiast dodać 128

0100 81C38000      ADD     BX,0080
0104 83EB80        SUB     BX,-80

Sam dodaj -128 zamiast odjąć 128


1
Działa to również w innym kierunku: dodaj -128 zamiast sub 128. Ciekawostka: kompilatory znają tę optymalizację, a także wykonują powiązaną optymalizację przekształcania < 128w, <= 127aby zmniejszyć wielkość natychmiastowego argumentu cmplub gcc zawsze woli przestawiać porównuje, aby zmniejszyć jasność, nawet jeśli nie jest to -129 vs. -128.
Peter Cordes

4

Utwórz 3 zera za pomocą mul(następnie inc/, decaby uzyskać +1 / -1 oraz zero)

Możesz wyzerować eax i edx, mnożąc przez zero w trzecim rejestrze.

xor   ebx, ebx      ; 2B  ebx = 0
mul   ebx           ; 2B  eax=edx = 0

inc   ebx           ; 1B  ebx=1

spowoduje, że EAX, EDX i EBX będą miały zero w zaledwie czterech bajtach. Możesz wyzerować EAX i EDX w trzech bajtach:

xor eax, eax
cdq

Ale od tego punktu początkowego nie można uzyskać rejestru o trzeciej wartości zerowej w jeszcze jednym bajcie lub rejestru +1 lub -1 w kolejnych 2 bajtach. Zamiast tego użyj techniki Mul.

Przykładowy przypadek użycia: konkatenacja liczb Fibonacciego w systemie binarnym .

Zauważ, że po LOOPzakończeniu pętli ECX będzie wynosić zero i może być użyty do zerowania EDX i EAX; nie zawsze musisz stworzyć pierwsze zero xor.


1
To jest trochę mylące. Czy mógłbyś się rozwinąć?
NoOneIsHere

@NoOneIsHhere wierzę, że chce ustawić trzy rejestry na 0, w tym EAX i EDX.
NieDzejkob

4

Rejestry i flagi procesora znajdują się w znanych stanach uruchamiania

Możemy założyć, że procesor jest w znanym i udokumentowanym stanie domyślnym w oparciu o platformę i system operacyjny.

Na przykład:

DOS http://www.fysnet.net/yourhelp.htm

Linux x86 ELF http://asm.sourceforge.net/articles/startup.html


1
Reguły Code Golf mówią, że Twój kod musi działać na co najmniej jednej implementacji. Linux wybiera zero wszystkich regów (oprócz RSP) i układa je w stos przed wejściem w nowy proces przestrzeni użytkownika, mimo że dokumenty ABI systemu i386 i x86-64 System V mówią, że są „niezdefiniowane” przy wejściu do _start. Więc tak, uczciwą grą jest skorzystanie z tego, jeśli piszesz program zamiast funkcji. Zrobiłem to w Extreme Fibonacci . (W dynamicznie połączonego pliku wykonywalnego, ld.so przebiegów przed skokiem do swoich _start, a nie śmieci pozostawić w rejestrach, ale to tylko statyczny kod.)
Peter Cordes

3

Aby dodać lub odjąć 1, użyj jednego bajtu inclub decinstrukcji, które są mniejsze niż wielobajtowe instrukcje dodawania i odejmowania .


Zauważ, że tryb 32-bitowy ma 1 bajt inc/dec r32z numerem rejestru zakodowanym w kodzie operacji. Czyli inc ebx1 bajt, ale inc bl2. Wciąż mniejszy niż add bl, 1oczywiście dla rejestrów innych niż al. Zauważ też, że inc/ decpozostaw CF niezmodyfikowany, ale zaktualizuj pozostałe flagi.
Peter Cordes

1
2 dla +2 i -2 w x86
l4m2

3

lea do matematyki

Jest to prawdopodobnie jedna z pierwszych rzeczy, których uczy się o x86, ale zostawiam to tutaj jako przypomnienie. leamoże służyć do mnożenia przez 2, 3, 4, 5, 8 lub 9 i dodawania przesunięcia.

Na przykład, aby obliczyć ebx = 9*eax + 3w jednej instrukcji (w trybie 32-bitowym):

8d 5c c0 03             lea    0x3(%eax,%eax,8),%ebx

Tutaj jest bez przesunięcia:

8d 1c c0                lea    (%eax,%eax,8),%ebx

Łał! Oczywiście leamożna go również wykorzystać do obliczeń matematycznych, takich jak ebx = edx + 8*eax + 3obliczanie indeksowania tablic.


1
Może warto wspomnieć, że lea eax, [rcx + 13]jest to wersja bez dodatkowych prefiksów dla trybu 64-bitowego. 32-bitowy rozmiar argumentu (dla wyniku) i 64-bitowy rozmiar adresu (dla wejść).
Peter Cordes

3

Instrukcje pętli i łańcuchów są mniejsze niż alternatywne sekwencje instrukcji. Najbardziej użyteczna jest ta, loop <label>która jest mniejsza niż dwie sekwencje instrukcji dec ECXi jnz <label>, i lodsbjest mniejsza niż mov al,[esi]i inc si.


2

mov małe natychmiast przechodzi do niższych rejestrów, jeśli dotyczy

Jeśli już wiesz, że górnymi bitami rejestru są 0, możesz użyć krótszej instrukcji, aby przenieść natychmiast do niższych rejestrów.

b8 0a 00 00 00          mov    $0xa,%eax

przeciw

b0 0a                   mov    $0xa,%al

Użyj push/ popdla imm8 do zera górnych bitów

Podziękowania dla Petera Cordesa. xor/ movma 4 bajty, ale push/ popma tylko 3!

6a 0a                   push   $0xa
58                      pop    %eax

mov al, 0xajest dobry, jeśli nie potrzebujesz go z zerowym rozszerzeniem do pełnego rejestru. Ale jeśli to zrobisz, xor / mov ma 4 bajty vs. 3 dla push imm8 / pop lub leaz innej znanej stałej. Może to być przydatne w połączeniu z mulzerowaniem 3 rejestrów w 4 bajtach lub cdq, jeśli potrzebujesz wielu stałych.
Peter Cordes

Drugi przypadek użycia dotyczyłby stałych, z [0x80..0xFF]których nie można przedstawić jako imm8 z rozszerzonym znakiem. Lub jeśli znasz już górne bajty, np. mov cl, 0x10Po loopinstrukcji, ponieważ jedynym sposobem, loopaby nie skakać, jest jej wykonanie rcx=0. (Myślę, że to powiedziałeś , ale twój przykład używa xor). Możesz nawet użyć niskiego bajtu rejestru dla czegoś innego, o ile coś innego ustawia go ponownie na zero (lub cokolwiek innego), kiedy skończysz. np. mój program Fibonacciego trzyma -1024w ebx i używa bl.
Peter Cordes

@PeterCordes Dodałem twoją technikę push / pop
qwr

Powinien prawdopodobnie przejść do istniejącej odpowiedzi na temat stałych, gdzie anatolyg zasugerował ją już w komentarzu . Zmienię tę odpowiedź. IMO powinieneś przerobić ten, aby zasugerować użycie 8-bitowego rozmiaru argumentu operacji dla większej ilości rzeczy (oprócz xchg eax, r32) np. mov bl, 10/ dec bl/ jnzWięc twój kod nie dba o wysokie bajty RBX.
Peter Cordes

@PeterCordes hmm. Nadal nie jestem pewien, kiedy użyć 8-bitowych operandów, więc nie jestem pewien, co podać w tej odpowiedzi.
qwr

2

W FLAGI są ustawione po wielu instrukcjach

Po wielu instrukcjach arytmetycznych flagi przenoszenia (niepodpisane) i flagi przepełnienia (podpisane) są ustawiane automatycznie ( więcej informacji ). Flaga Znaku i Flaga Zera są ustawiane po wielu operacjach arytmetycznych i logicznych. Można tego użyć do rozgałęzienia warunkowego.

Przykład:

d1 f8                   sar    %eax

ZF jest ustawiony przez tę instrukcję, więc możemy go użyć do warunkowego rozgałęzienia.


Kiedy używałeś flagi parzystości? Wiesz, że to poziomy xor niskich 8 bitów wyniku, prawda? (Niezależnie od wielkości argumentu, PF jest ustawiany tylko z niskich 8 bitów ; patrz także ). Nie parzysta / nieparzysta; dla tej kontroli ZF po test al,1; zwykle nie dostajesz tego za darmo. (Lub and al,1utworzyć liczbę całkowitą 0/1 w zależności od nieparzystej / parzystej.)
Peter Cordes

W każdym razie, jeśli odpowiedź brzmi „użyj flag już ustawionych w innych instrukcjach, aby uniknąć test/ cmp”, to byłby to dość prosty początkujący x86, ale nadal warty upvote.
Peter Cordes

@PeterCordes Huh, chyba źle zrozumiałem flagę parzystości. Nadal pracuję nad drugą odpowiedzią. Zmienię odpowiedź. I jak zapewne wiesz, jestem początkującym, więc podstawowe wskazówki pomagają.
qwr

2

Używaj pętli do-while zamiast pętli while

Nie jest to specyficzne dla x86, ale jest powszechnie stosowaną wskazówką dla początkujących. Jeśli wiesz, że pętla while uruchomi się co najmniej raz, przepisanie pętli jako pętli do-while, ze sprawdzaniem stanu pętli na końcu, często zapisuje 2-bajtową instrukcję skoku. W szczególnym przypadku możesz nawet użyć loop.


2
Powiązane: Dlaczego pętle są zawsze tak kompilowane? wyjaśnia, dlaczego do{}while()występuje naturalny idiom zapętlania w montażu (szczególnie pod względem wydajności). Zauważ też, że 2-bajtowa jecxz/ jrcxzzanim pętla działa bardzo dobrze, loopaby poradzić sobie ze sprawą „musi działać„ zero razy ”„ wydajnie ”(na rzadkich procesorach, gdzie loopnie jest wolna). jecxzjest również użyteczny w pętli, aby zaimplementowaćwhile(ecx){} , z jmpna dole.
Peter Cordes,

@PeterCordes to bardzo dobrze napisana odpowiedź. Chciałbym znaleźć sposób, aby wskoczyć do środka pętli w programie golfowym.
qwr

Użyj goto jmp i wcięcia ... Pętla wykonaj
RosLuP

2

Używaj dowolnych dogodnych konwencji połączeń

System V x86 używa stosu i System V x86-64 zastosowania rdi, rsi, rdx, rcx, itd. Dla parametrów wejściowych, a raxjako wartość zwracana, ale jest to całkowicie uzasadnione, aby użyć własnego konwencja wywołania. __fastcall używa ecxi edxjako parametry wejściowe, a inne kompilatory / systemy operacyjne stosują własne konwencje . Użyj stosu i innych rejestrów jako wejścia / wyjścia, gdy jest to wygodne.

Przykład: Powtarzalny licznik bajtów , przy użyciu sprytnej konwencji wywoływania dla rozwiązania 1-bajtowego.

Meta: Zapisywanie danych wejściowych do rejestrów , Zapisywanie danych wyjściowych do rejestrów

Inne zasoby: uwagi Agner Fog na temat zwoływania konwencji


1
W końcu zacząłem publikować własną odpowiedź na to pytanie dotyczące wymyślania konwencji telefonicznych i tego, co jest rozsądne w porównaniu z nieuzasadnionym.
Peter Cordes

@PeterCordes niepowiązane, jaki jest najlepszy sposób drukowania w x86? Do tej pory unikałem wyzwań wymagających drukowania. DOS wygląda na to, że ma przydatne przerwania dla I / O, ale planuję tylko pisać odpowiedzi 32/64-bitowe. Jedyny znany mi sposób to int 0x80konfiguracja.
qwr

Tak, int 0x80w 32-bitowym kodzie lub syscallw 64-bitowym kodzie, aby wywołać sys_write, jest jedynym dobrym sposobem. Tego właśnie użyłem do Extreme Fibonacciego . W 64-bitowym kodzie __NR_write = 1 = STDOUT_FILENO, więc możesz mov eax, edi. Lub jeśli górne bajty EAX są równe zero, mov al, 4w kodzie 32-bitowym. Można też call printfczy puts, jak sądzę, i napisać „asm x86 dla Linux + glibc” odpowiedź. Myślę, że rozsądne jest nie liczenie przestrzeni wejściowej PLT, GOT ani samego kodu biblioteki.
Peter Cordes

1
Byłbym bardziej skłonny, aby wywołujący przekazał a char*bufi wygenerował w nim ciąg znaków z ręcznym formatowaniem. np. jak ten (niezręcznie zoptymalizowany pod kątem prędkości) asm FizzBuzz , w którym zapisałem dane ciągów do rejestru, a następnie je zapisałem mov, ponieważ ciągi były krótkie i stałej długości.
Peter Cordes

1

Używaj ruchów CMOVcci zestawów warunkowychSETcc

Jest to bardziej przypomnienie dla mnie, ale istnieją instrukcje zestawu warunkowego i instrukcje przenoszenia warunkowego na procesorach P6 (Pentium Pro) lub nowszych. Istnieje wiele instrukcji opartych na jednej lub więcej flag ustawionych w EFLAGS.


1
Przekonałem się, że rozgałęzienie jest zwykle mniejsze. W niektórych przypadkach jest to naturalne dopasowanie, ale cmovma 2-bajtowy kod operacji ( 0F 4x +ModR/M), więc minimum 3 bajty. Ale źródłem jest r / m32, więc możesz warunkowo załadować 3 bajty. Inne niż rozgałęzianie, setccjest przydatne w większej liczbie przypadków niż cmovcc. Mimo to rozważ cały zestaw instrukcji, a nie tylko podstawowe instrukcje 386. (Chociaż instrukcje SSE2 i BMI / BMI2 są tak duże, że rzadko są użyteczne. rorx eax, ecx, 32To 6 bajtów, więcej niż mov + ror. Niezła wydajność, nie golf, chyba że POPCNT lub PDEP uratuje wiele isns)
Peter Cordes

@PeterCordes dzięki, dodałem setcc.
qwr

1

Zaoszczędź na jmpbajtach, ustawiając w if / then zamiast if / then / else

Jest to z pewnością bardzo podstawowe, pomyślałem, że opublikuję to jako coś do przemyślenia podczas gry w golfa. Jako przykład rozważ następujący prosty kod do zdekodowania znaku szesnastkowego:

    cmp $'A', %al
    jae .Lletter
    sub $'0', %al
    jmp .Lprocess
.Lletter:
    sub $('A'-10), %al
.Lprocess:
    movzbl %al, %eax
    ...

Można to skrócić o dwa bajty, pozwalając, aby przypadek „wtedy” zamienił się w przypadek „inny”:

    cmp $'A', %al
    jb .digit
    sub $('A'-'0'-10), %eax
.digit:
    sub $'0', %eax
    movzbl %al, %eax
    ...

Często robiłbyś to normalnie podczas optymalizacji wydajności, szczególnie gdy dodatkowe subopóźnienie na ścieżce krytycznej dla jednego przypadku nie jest częścią łańcucha zależności przenoszonego przez pętlę (jak tutaj, gdzie każda cyfra wejściowa jest niezależna aż do scalenia 4-bitowych fragmentów ). Ale tak czy inaczej +1. BTW, twój przykład ma oddzielną pominiętą optymalizację: jeśli i tak będziesz potrzebować movzxna końcu, sub $imm, %alnie używaj EAX, aby skorzystać z 2-bajtowego kodowania bez modrm op $imm, %al.
Peter Cordes

Możesz także wyeliminować cmp, wykonując sub $'A'-10, %al; jae .was_alpha; add $('A'-10)-'0'. (Myślę, że mam właściwą logikę). Pamiętaj, że 'A'-10 > '9'nie ma dwuznaczności. Odejmowanie poprawki dla litery spowoduje zawinięcie cyfry dziesiętnej. Jest to bezpieczne, jeśli zakładamy, że nasze dane wejściowe są poprawne hex, tak jak twoje.
Peter Cordes

0

Możesz pobrać kolejne obiekty ze stosu, ustawiając esi na esp i wykonując sekwencję regów lodsd / xchg, eax.


Dlaczego jest to lepsze niż pop eax/ pop edx/ ...? Jeśli chcesz zostawić je na stosie, możesz pushje wszystkie później przywrócić ESP, nadal 2 bajty na obiekt bez potrzeby mov esi,esp. A może chodziło Ci o 4-bajtowe obiekty w 64-bitowym kodzie, gdzie popotrzymalibyśmy 8 bajtów? BTW, możesz nawet użyć popdo przełączania bufora z lepszą wydajnością niż lodsdnp. W celu dodania rozszerzonej precyzji w Extreme Fibonacciego
Peter Cordes

jest to bardziej przydatne po „lea esi, [esp + rozmiar adresu ret]], co wykluczałoby użycie popu, chyba że masz zapasowy rejestr.
Peter Ferrie

Och, dla argumentów funkcyjnych? Dość rzadko chcesz więcej argumentów niż rejestrów lub chcesz, aby dzwoniący zostawił jeden w pamięci zamiast przekazywać je wszystkie do rejestrów. (Mam pół wykończone odpowiedź na temat korzystania z niestandardowych wzywające konwencje, w jednym przypadku standardowej konwencji rejestr dyżuru nie pasuje idealnie.)
Peter Cordes

cdecl zamiast fastcall pozostawi parametry na stosie i łatwo jest mieć wiele parametrów. Zobacz na przykład github.com/peterferrie/tinycrypt.
Peter Ferrie

0

Dla codegolf i ASM: Użyj instrukcji, używaj tylko rejestrów, push pop, minimalizuj pamięć rejestrów lub pamięć natychmiastową


0

Aby skopiować rejestr 64-bitowy, użyj push rcx; pop rdxzamiast 3 bajtów mov.
Domyślny rozmiar argumentu push / pop to 64-bit bez potrzeby używania prefiksu REX.

  51                      push   rcx
  5a                      pop    rdx
                vs.
  48 89 ca                mov    rdx,rcx

(Prefiks wielkości operandu może zastąpić rozmiar push / pop do 16-bitowego, ale 32-bitowego rozmiaru operandu push / pop nie można kodować w trybie 64-bitowym nawet przy REX.W = 0).

Jeśli jeden lub oba rejestry są r8r15, użyj, movponieważ push i / lub pop będą wymagały prefiksu REX. W najgorszym przypadku to faktycznie traci, jeśli oba potrzebują prefiksów REX. Oczywiście w kodzie golfowym zwykle powinieneś unikać r8..r15.


Możesz zachować źródło bardziej czytelne podczas programowania dzięki temu makro NASM . Pamiętaj tylko, że działa na 8 bajtach poniżej RSP. (W czerwonej strefie w systemie x86-64 System V). Ale w normalnych warunkach jest to zastępczy zamiennik dla wersji 64-bitowej mov r64,r64lubmov r64, -128..127

    ; mov  %1, %2       ; use this macro to copy 64-bit registers in 2 bytes (no REX prefix)
%macro MOVE 2
    push  %2
    pop   %1
%endmacro

Przykłady:

   MOVE  rax, rsi            ; 2 bytes  (push + pop)
   MOVE  rbp, rdx            ; 2 bytes  (push + pop)
   mov   ecx, edi            ; 2 bytes.  32-bit operand size doesn't need REX prefixes

   MOVE  r8, r10             ; 4 bytes, don't use
   mov   r8, r10             ; 3 bytes, REX prefix has W=1 and the bits for reg and r/m being high

   xchg  eax, edi            ; 1 byte  (special xchg-with-accumulator opcodes)
   xchg  rax, rdi            ; 2 bytes (REX.W + that)

   xchg  ecx, edx            ; 2 bytes (normal xchg + modrm)
   xchg  rcx, rdx            ; 3 bytes (normal REX + xchg + modrm)

xchgCzęścią przykład dlatego, że czasami trzeba uzyskać wartość w EAX lub RAX i nie dbają o zachowanie starej kopii. Push / pop nie pomaga jednak w wymianie.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.