Jak najlepiej świętować Dzień Programisty? Z grą w Węża z Assemblera!

Gra w Węża, czyli szalony challenge na Dzień Programisty

Gra w Węża, czyli szalony challenge na Dzień Programisty

Dzień programisty to całkiem dobry dzień, aby rozwinąć swój warsztat programistyczny o coś szalonego.

Ciekawy jestem, ile z was miało do czynienia z najprostszym na świecie językiem programowania, czyli assemblerem?

Pewnie przyszło wam teraz do głowy parę, równie szalonych, jak to stwierdzenie, epitetów na mój temat. Ale czy jest coś prostszego niż bezpośrednie wydanie rozkazu procesorowi?

W każdym razie, postanowiłem zrobić sobie taki challenge i zaprogramować coś w assemblerze. Żeby nie było prosto, dodałem kilka dodatkowych ograniczeń:

1. Z kodu, który napiszę powstanie gra.
2. Cały kod, napisany na platformę x86, musi się zmieścić w sektorze rozruchowym dysku.
3. Całość musi być „bootowalna” i obsługiwana na komputerach z BIOSem lub z możliwością emulacji BIOSu (tryb legacy) dla komputerów wyposażonych w UEFI.
4. Zmieścić się z pracami w 24 godziny.

Z gier wybrałem starego i dobrze znanego Węża. Jeżeli chodzi o dysk – pendrive, który łatwiej przenieść i odpalić na innych komputerach.

Trochę teorii Assemblera na początek

Zanim zaczniemy programować Węża, sprawdźmy, na co nas stać. Zacznijmy od sektora rozruchowego  – MBR (Master Boot Record). Ma wielkość 512 bajtów. BIOS ładuje go jako ostatnią operację podczas uruchamiania komputera. Dodatkowo – w bardzo konkretne miejsce w pamięci – pod adres 0x7C00, do którego procesor wykonuje skok (patrząc na pamięć liniowo, ale o tym później).

Niestety nie możemy skorzystać z całych 512B. Dwa bajty uciekają na tak zwany „boot signature”, który mieści się na samym końcu i ma wartość 0xAA55. Bez tej sygnatury BIOS stwierdzi, że nasz MBR nie jest prawidłowy i nie odeśle procesora do tej części pamięci.

Niestety radość z pozostałych 510 bajtów pamięci też jest przedwczesna. BIOS w nowszych płytach głównych sprawdza tabelę partycji zawartą w tym sektorze. Jeżeli coś będzie z nią nie tak, to również nie załaduje takiego dysku. A taka tabela partycji zajmuje 64B (po 16B na partycję, których w MBR może być 4). W ten sposób zostało nam już 446 bajtów wolnego miejsca na nasz kod – patrz rys.1. Wredne, co nie? ????

(Rys.1 źródło: https://en.wikipedia.org/wiki/Master_boot_record).

Pamiętajmy jeszcze o jednym. Procesor (w chwil pisania artykułu) standardowo uruchamia się w trybie rzeczywistym. Dodam tylko, że jest to najstarszy, 16-bitowy tryb procesorów x86. Możemy w nim zaadresować 1MiB pamięci, ale nie mamy żadnej jej ochrony. Możemy więc robić, co nam się podoba. Same zalety, co nie? ;)

Wspominałem wcześniej o adresach liniowych. No właśnie! Standardowy procesor x86  nie patrzy na pamięć liniowo, czyli na całość i po kolei. W trybie rzeczywistym procesora pamięć jest podzielona na segmenty po 64KiB, a adresowanie odbywa się poprzez podanie numeru segmentu oraz offsetu w tym segmencie (segment:offset).

Tylko jak na złość, te segmenty nakładają się na siebie! To znaczy, że segment 0 leży na adresie 0, ale segment 1 nie jest przesunięty o 64KiB, tylko leży na adresie 16. Wynika to z tego, że wewnętrznie procesor, który podaje do RAM, przelicza sobie adres liniowy jako segment * 16 + offset. Dlatego od tej pory będę podawał adresy podzielone na segment i offset.

Przyda nam się jeszcze krótka powtórka z rejestrów w procesorach x86. Na potrzeby tego artykułu potrzebujemy wiedzieć, że mamy rejestry ogólnego przeznaczenia. Są to:

• EAX, który pełni rolę akumulatora,
• EBX, który służy do adresowania,
• ECX, który jest licznikiem,
• EDX, który stanowi dodatkowy rejestr na dane,
• ESP, który jest wskaźnikiem wierzchołka stosu,
• EBP, który wykorzystywany jest do adresowania,
• oraz ESI i EDI, które służą do wskazywania na elementy tablic.

Mamy również dostęp do młodszych 2 bajtów tych rejestrów poprzez odwołanie się do nich bez litery E w nazwie rejestru (np. AX).

Rejestry 16-bitowe rejestry z X w nazwie są podzielone na wersja H i L, które oznaczają odpowiednio starszy i młodszy bajt tego rejestru. Na przykład rejestr AX jest podzielony na AH i AL, a AX stanowi młodsze 2 bajty rejestru EAX.

Oprócz rejestrów ogólnego przeznaczenia mamy rejestry segmentowe, które określają położenie segmentów. Są to rejestry:

• CS do określenia segmentu, gdzie leży aktualnie wykonywany kod,
• DS i ES, które stanowią rejestry segmentów danych,
• SS -rejestr segmentu stosu,
• FS i GS, które stanowią dodatkowe 2 rejestry segmentu.

No dobra, jeszcze trzeba tego Węża wyświetlić na ekranie, ale tutaj sprawa jest prostsza.

Standardowa karta graficzna domyślnie obsługuje, dziś już „antyczny”,  standard VGA. Standard definiuje między innymi tryby pracy karty. Tryb ten określa sposób organizacji pamięci, rozdzielczość, liczbę kolorów i to, czy jest przeznaczony tylko do tekstu (tryb tekstowy) czy do rysowania pojedynczymi pikselami (tryb graficzny).

Standardowo BIOS inicjuje kartę graficzną w tryb tekstowy, który pozwala nam na pisanie 80 znaków w 25 liniach, wykorzystując do tego 4 bity na kolor tekstu i 4 bity (bądź 3, w niektórych przypadkach) na kolor tła. Kolejne 8 bitów jest na kod znaku.

Dodatkowo można pisać bezpośrednio po pamięci karty graficznej, ponieważ jest zmapowana na przestrzeń adresową, która zaczyna się w adresie 0xb800:0000. Tryb ten dodatkowo oferuje nam strony, ale wykorzystamy tylko jedną z nich.

Na pozostałym obszarze pamięci, która nie będzie widoczna przez użytkownika, wsadzimy resztę danych. Ot taka optymalizacja, żeby nie skakać między segmentami i nie tracić na to cennych bajtów kodu.

No to w końcu działamy!

Hola hola! A jaki soft wykorzystałem?

• Do pisania kodu wziąłem pierwszy z brzegu edytor tekstu.
• Do wrzucenia na pendrive mojego wytworu użyłem linuksowego dd.
• Zaś do przemiany kodu w zera i jedynki (asemblacji) skorzystałem z nasma.
• Żeby nie pisać tablicy partycji z palca, to stworzyłem taką za pomocą gparted.
• No i na końcu, choć to już nie jest oprogramowanie, ale przyda się opasła książka z spisem instrukcji dostępnych w procesorach x86: https://cdrdv2.intel.com/v1/dl/getContent/671200

Mamy już wszystko, więc zaczynamy od zaprojektowania mapy pamięci (rys. 2). Z teorii już wiemy, że nasze dane (poza kodem gry, który będzie w miejscu przeznaczonym na bootloader) wpakujemy w segment 0xb8000.

Pierwsze 4000B zajmuje nam już bufor karty graficznej (2B * 80 znaków * 25 linii). Przyda nam się też tablica z informacją o każdym z 2000 pól (0 – puste, 1 – jedzonko dla węża, 2 – wąż). Założyłem tutaj, że krawędzie ekranu będą mówić o granicy pola gry, tzn. wąż nie będzie mógł przechodzić przez ściany. Na te wartości dodatkowo zakodowałem definicje. Kolejną przydatną rzeczą, będzie 1 bajt stan gry (0 – czeka na start, 1 – gramy, 2 – gra gotowa do restartu).

Kolejny bajt to kierunek, w którym biegnie wąż (w lewo, w prawo itd.). Potem mamy jeszcze 2B na seed gry  –przecież jedzonko nie będzie zawsze w tych samych miejscach. A następnie mamy wektor, w którym trzymać będę informacje o pozycjach poszczególnych części węża w dwóch bajtach. Ten młodszy bajt będzie zawierał x, ten starszy będzie zawierał pozycję y.

Pewnie wydaje się wam to rozrzutne, bo dwa razy koduję tę samą informację – ale przyda mi się to do tego, żeby algorytm przesuwania węża po mapie był krótki (w końcu optymalizuje ilość wykonywalnego kodu na dysku, a nie to ile on pamięci RAM zajmie). Jeszcze przydadzą się definicje poszczególnych klawiszy – posłużę się tutaj po prostu kodami, jakie klawiatura wysyła do komputera po naciśnięciu (scan codes).

Inicjalizacja gry w Węża

Czas zająć się inicjalizacją naszej gry. Na początku ustawiłem segment danych DS na wartość 0xb800, zgodnie z wcześniej ustaloną mapą. Niestety, nie można bezpośrednio wpisywać stałej w rejestry segmentowe, dlatego posłużyłem się do tego celu rejestrem AX.

Dodatkowo do rejestru BX wpisałem wielkość mapy pamięci, ponieważ będzie ona potrzebna do wyzerowania tej mapy pamięci. Dodatkowo przyda się wyłączenie obsługi zewnętrznych przerwań sprzętowych za pomocą instrukcją „cli” (rys.3).

Następnie musiałem wyzerować całą pamięć opisaną w mapie pamięci. Wykorzystałem do tego prostą pętlę, opierającą się o to, że instrukcja „dec” zostawia ustawioną w procesorze flagę zera, jeżeli wynik tej operacji dał 0. Dzięki temu mogłem dopisać skok warunkowy „jnz”, który wykona się, jeżeli w BX nie będzie 0 (rys. 4).

Następnie trzeba wygenerować seed, który będzie potrzebny do generatora liczb pseudolosowych (rys.5). Jako seed użyję zegara systemowego, który odlicza czas od włączenia lub restartu komputera. Aby się do niego dobrać, wykorzystałem funkcję BIOS.

Funkcje BIOS to dosyć przydatne narzędzie, które pozwala na komunikację z sprzętem poprzez interfejs przerwań programowych. Dzięki temu mogłem znacznie zaoszczędzić na bajtach.

Teraz przyszedł czas na zainicjowanie pozostałych zmiennych: ustawiam stan gry, początkowy kierunek Węża oraz jego pierwszy fragment.

Tutaj, żeby  oszczędzić bajtów, posklejałem wartości, jakie się dało, aby zapisać je, w miarę możliwości, jedną instrukcją. Zaoszczędziłem aż 16-bajtów. Rozwinięty kod został zapisany w komentarzach w poniższym listingu (rys.6):

Najwyższy czas wygenerować też pierwsze jedzenie (rys.7). Do tego stworzyłem funkcję „generateFood”. Starałem się, aby algorytm był prosty. Nawet wyszedł mi ułomnie prosty, ponieważ losuję współrzędne nowego jedzonka, a następnie sprawdzam, czy danym polu jest Wąż.

Jeżeli jest, to powtarzam cały proces, aż do znalezienia wolnego miejsca. Tak mam świadomość, że algorytm może się zablokować przy bardzo długim wężu. Jednak w moich ramach czasowych nie znalazłem pomysłu na nic lepszego i w miarę niezajmującego dużo miejsca. Liczę na poziom trudności :D

Funkcja losująca też jest wyjątkowo prosta, ponieważ biorę seed z pamięci i mnożę go przez wybraną arbitralnie liczbę pierwszą, a następnie dodaję drugą. Zapisuję wynik z rejestru AX w miejsce starego seeda, a dodatkowo ta wartość zostanie w rejestrze AX jako wynik całej operacji losowania.

Teraz wprowadzamy obsługę klawiatury oraz nasłuchiwanie tyknięć zegara PIT, wedle którego toczyć się będzie gra. W tym celu w tablicy wektorów obsługi przerwań wskażemy wskaźniki na nasze funkcje na odpowiednich pozycjach odpowiadających danemu przerwaniu.

Po całej inicjalizacji można włączyć przerwania sprzętowe i przejść do funkcji  main, która jest bardzo prosta. Wstrzymuje procesor za pomocą instrukcji „hlt”, do momentu aż wykona się przerwanie sprzętowe (bo po co niepotrzebnie grzać procesor.

Następnie sprawdza, czy stan gry nie jest ustawiony na gotowy do resetu. Jeżeli ta, to program skacze do inicjalizacji całej gry od początku. Jeżeli nie, to wracamy do czekania i tak w kółko (rys.8).

Obsługa klawiatury

Po przyjściu przerwania z portu 0x60, który stanowi warstwę komunikacji z kontrolerem klawiatury, odczytuję scan code wciśniętego klawisza. Następnie w przypadku wciśnięcia klawisza „q”, ustawiam stan gry na wartość 2 (gotowa do restartu), a następnie uruchamiam kod odpowiedzialny za wyjście z przerwania.

W innym przypadku sprawdzam, czy kod klawisza, to któraś z strzałek. Robię to za pomocą instrukcji „repne scasb”, która porównuje bajty z lokacji ES:DI z rejestrem AL, przy czym DI jest automatycznie inkrementowany po wykonaniu instrukcji, a instrukcja wykonywana jest CX razy lub do napotkania żądanej wartości.

W przypadku nieznalezienia wartości w tablicy wychodzę z przerwania, ponieważ nie został wciśnięty prawidłowy klawisz. Dodatkowo sprawdzam, czy nie dojdzie do próby zawrócenia Wężem w miejscu tzn. pójścia w kierunku przeciwnym do obecnego. W innym przypadku przypisuję wartość scan code jako kierunek Węża (rys.9).

Logika gry

Teraz został nam najważniejszy fragment kodu do omówienia, czyli funkcja obsługi przerwania z zegara PIT, który będzie nam definiował jedną klatkę gry. W tym fragmencie kodu zawarta jest cała logika gry.

Na początku sprawdzany jest stan gry, czy jest w ogóle sens wykonywania dalszych instrukcji. Potem pobieram współrzędne głowy Węża oraz kierunek poruszania się. Następnie zgodnie z kierunkiem odpowiednio inkrementuję albo dekrementuję jedną z współrzędnych tej głowy, a następnie sprawdzam, czy głowa nie wylądowała poza ekranem. W przypadku wyjścia poza granice wykonuję skok do kodu odpowiedzialnego za zakończenie gry. (rys. 10)

Kod odpowiedzialny za przegraną ustawia wartość stanu na 0. A następnie, wykorzystując funkcję BIOS, wyświetla napis informujący o przegranej. Napis ten mieści się na samym końcu kodu w sekcji, gdzie przechowuję inne dane zdefiniowane podczas tworzenia kodu.

Wracamy do głównego kodu (rys. 12). Po sprawdzeniu granic planszy, następuje sprawdzenie tego, na jakie pole natrafiliśmy na planszy. W przypadku natrafienia na fragment Węża, wołany jest wyżej wspomniany kod obsługi przegranej.

W przypadku natrafienia na jedzenie, następuje przeskok do kodu, który woła funkcję generującą nowe jedzenie, a następnie przejście do sekcji oznaczonej „grow_snake”.

W innym przypadku z mapy gry usuwany jest końcowy fragment Węża oraz z wektora zawierającego współrzędne Węża ostatni wpis. Następnie następuje przeskok do sekcji „grow_snake”.

Teraz nie pozostało nic innego, jak dopisać do mapy gry oraz na początek wektora, informacje o nowej głowie. Nie ważne, czy Wąż zjadł jedzenie, czy nie, ponieważ o to zadbał poprzedni kod.

Na początek wszystkie wartości w wektorze są przesuwane o jeden indeks (2 bajty) dalej, a następnie na początek wektora wstawiane są współrzędne nowej głowy, która wstawiana jest do mapy gry (rys. 13).

Na sam koniec zostało wyrysowanie planszy na ekran. W tym celu przygotowałem sobie odpowiednie „duszki”, które reprezentują odpowiednie stany komórek w planszy. Każda komórka to jeden znak spacji, o tle w odpowiednim kolorze.

Czarny kolor oznacza pole puste, zielony oznacza pole z jedzeniem, Wąż zaś rysowany jest za pomocą koloru brązowego. Dzięki temu, że mam dodatkową mapę gry, mogę jedną krótką pętlą, pod względem ilości zużytych bajtów, narysować całą planszę (rys. 14).

Czas zacząć zabawę!

W ten sposób udało mi się otrzymać kod, który w wersji binarnej zajmuje 429 B. A jak działa? Możesz to zobaczyć na filmiku

www.youtube.com/watch!

A cały kod umiejscowiłem na tym repozytorium

github.com/SzateX/snake-x86-bootloader.

To teraz challenge dla Ciebie!

Czy uda Ci się urwać kilka bajtów z powyższego kodu tak, aby nie zmienić zasady działania gry (sterowanie strzałkami, restart za pomocą klawisza q oraz napis w przypadku porażki)?.

Aha i przy okazji zapraszam do pracy z nami: Oferty - eduPortal (asseco.com) 

Dzień Programisty, Assembler i rekord w Węża. To się musi udać! Wszystkiego najlepszego!