Programowanie

Programowanie

Wojny Rdzeniowe

Wojny Rdzeniowe

Wojny rdzeniowe

Marek Sawerwain

Wojny rdzeniowe – CoreWars – to legenda informatyki. Po raz pierwszy wzmianka o CoreWars pojawiła się w roku 1984 na The University of Western Ontario w Kanadzie. Jeden z autorów, A. K. Dewdney, napisał także kilka artykułów na ten temat do czasopisma Scientific American. W ten sposób narodziła się jedna z legend informatyki.

.pl

Wojny rdzeniowe to bardzo specyficzna maszyny MARS. Istnieje wiele dostępnych programów, gra, gdzie w pamięci zwanej rdzeniem oficjalnym programem jest pMars, który omawiam w tym (ang. core), zarządzanej przez komputer artykule. Innym równie ciekawym jest program o wszyst-software.com

albo procesor o nazwie MARS wykony- ko mówiącej nazwie CoreWars. Program ten oferuje na-linux@

wany jest kod umieszczonych w pamięci programów. Wy- wet dwie wersje języka programowania dla wojen rdze-grywa ten program, który pokona pozostałych przeciwników niowych: oryginalny RedCode oraz równie ciekawą jak np.: poprzez ich wymazanie z pamięci albo poprzez zastąpie- sam RedCode odmianę o nazwie CoreWars. Jednak, z ra-niem własnym kodem. Mówiąc inaczej, wygrywa ten pro- cji ograniczonego miejsca, będziemy zajmować się tylko gram, który nadal działa, po upłynięciu odpowiedniego cza- samym RedCode i środowiskiem MARS.

su. Programy dla systemu MARS są tworzone w języku o na-

zwie RedCode. Jest on bardzo podobny do assemblera. Ist- MARS – definicja

nieją kilka wariantów RedCode, jednak w dalszej części sku- Programy napisane w języku RedCode są wykonywane w ra-pimy się tylko na oryginalnej wersji RedCode.

mach ściśle określonego środowiska. Głównym elementem

Skromne ramy artykułu pozwalają na przedstawienie tego środowiska jest pamięć operacyjna, czyli rdzeń. Zazwy-tylko kilku przykładów. Dlatego już na samym początku czaj do dyspozycji mamy 8000 dostępnych komórek pamię-

zachęcam na szukania innych przykładów programów pi- ci. Ilość pamięci można zmieniać, a ogólnie wielkość pamię-

sanych w RedCode. Warto także na samym początku po- ci jest zapisana w przedefiniowanej zmiennej CORESIZE.

wiedzieć, iż istnieją standardy języka RedCode, analo-

Ważnym elementem, sprawiającym nieco kłopotów,

gicznie jak standardy dla języków C, C++ czy Java. Ostat- jest fakt, iż w dostępie do pamięci obowiązuje adresowa-nim standardem jest ICWS'94. Dostępne są także pewne nie względne. Innymi słowy, nie ma adresu początkowego uproszczone odmiany języka RedCode. Bez względu na oraz końcowego. Adres zerowy to adres komórki, w której odmianę Red Code należy posiadać specjalny symulator aktualnie się znajdujemy, wartość 1 to adres komórki następ-56

marzec 2008

www.lpmagazine.org

57





Programowanie

Programowanie

Wojny Rdzeniowe

Wojny Rdzeniowe

nej, a wartość -1 to adres komórki poprzedniej. RedCode

dat #0, #0 oznacza umieszczenie w aktualnej

Oznacza to także, iż rdzeń jest zapętlony. Na- Przedstawiona powyżej definicja systemu MARS komórce wartości 0 w polach A oraz B, natomiast stępną komórką pamięci po ostatniej jest ko- nie jest zbyt skomplikowana, podobnie jak język dat #1, #2, oznacza umieszczenie odpowied-mórka pierwsza.

RedCode. Jednak, jak zawsze w przypadku języ- nio jedynki i dwójki. Znak $ oznacza bezpośred-Każda komórka pamięci posiada trzy ele- ka programowania podobnego do assemblera, ni adres. Przykładem zastosowania adresowania menty: pole instrukcji, pole argumentu źródło- napisanie dobrego programu nie jest łatwe.

względnego może być instrukcja kopiująca samą

wego A oraz pole argumentu docelowego B.

Pojedyncza instrukcja RedCode, podobnie siebie mov $0,$1. Ponieważ adresowanie jest Nie ma typowych rejestrów jak w rzeczywi- jak w wielu istniejących assemblerach, jest zbu- bardzo często używane, to możemy także napi-stych procesorach, jednakże dostępny jest ob- dowana z czterech elementów: etykiety, kodu in- sać mov 0, 1. Większość kompilatorów RedCo-szar pamięci nazwany P-Space, do którego, strukcji oraz dwóch pól argumentów. Schema- de dopuszcza stosowanie tego typu skrótu. Inny każdy z programów ma wyłączny dostęp. Jed- tycznie przedstawimy to, w następujący sposób: przykład instrukcji to mov #2, 1, oznaczający nak P-Space jest nowym elementem i klasycz-przeniesienie dwójki pod następny adres.

na wersja RedCode nie oferuje dostępu do do- etykieta trzyliterowy kod instrukcji

Dwa kolejne typy adresowania są repre-

datkowej przestrzeni pamięci.

[pole_A, pole_B]

zentowane przez symbole * oraz @. Pierwszy

W jednym takcie wykonywana jest tyl-

adresuje pośrednio przez pole A, drugi sym-

ko jedna instrukcja (co oznacza, że czas wy- Spis wszystkich instrukcji przedstawia tabela bol przez pole B. Oznacza to iż z pola np.: A od-konania poszczególnych typów instrukcji pt. Instrukcje RedCode. Ważną rolę pełni in- czytywany jest adres pod którym znajduje się jest taki sam), i po jej wykonaniu MARS strukcja dat, a dokładniej jej postać dat 0,0 informacja o właściwym adresie. Taki typ ad-przechodzi do wykonania instrukcji z na- (lub dat $0, $0). Jest to nielegalna instrukcja i resowania to nic innego, jak wskazanie przez stępnej komórki pamięci. Wyjątkiem jest in- jej wykonanie doprowadzi do śmierci wykony- wskaźnik, stosowane w wielu językach wyso-strukcja skoku, która przenosi sterowanie do wanego programu. Domyślnie, cały rdzeń jest kiego poziomu jak Pascal czy C. Kolejne tryby innego miejsca w pamięci. W pamięci mo- wypełniony tymi instrukcjami. Dodam jesz- adresowania są reprezentowane przez symbo-

że być wykonywanych kilkanaście progra- cze, że wyrażenia w nawiasach kwadratowych le {, } oraz <, >. Oznaczają one również adreso-mów różnych użytkowników. W takim przy- są opcjonalne np.: jeśli chcemy zapisać instruk- wanie pośrednie przy pomocy pól A oraz B. Jed-padku MARS wykonuje je kolejno, po jed- cję skoku o pięć komórek do przodu to piszemy nakże symbol { oznacza iż adres zostanie pobra-nej instrukcji.

tylko jmp 5. Argument B, nie jest potrzebny.

ny z komórki o adresie zawartym w A, ale przed

MARS dopuszcza także uruchamianie pro-

Instrukcji języka nie jest wiele, ale istnieje skokiem wartość ta zostanie zmniejszona. Pocesów potomnych w ramach programu użyt- kilka różnych sposobów adresowania. Podsta- dobnie dla symbolu }, ale tym razem zostanie kownika za pomocą instrukcji spl. Każdy z wową informacją jest fakt, iż adresowanie jest ona zwiększona. Uzupełnieniem instrukcji Red-nowo utworzonych procesów zapisywany jest względne, co zostało już wspomniane wcześniej. Code są pseudoinstrukcje sterujące procesem w kolejce zadań. System kolejno po jednej in- Jednak zastosowanie znaku # (hash) oznacza kompilacji programu. Możemy wprowadzać strukcji przetwarza procesy z listy zadań.

bezpośrednią wartość liczbową, czyli instrukcja tekstowe oznaczenia dla wartości liczbowych: nazwa EQU wartość. Instrukcja ORG etykieta

Tabela 1. Instrukcje RedCode

pozwala na ustalenie adresu początkowego dla

Instrukcja

Krótki opis

programu. Natomiast instrukcja END [etykie-

dat [A,] B

instrukcja do przechowywania danych, próba jej wykonania zabija proces

ta] oznacza koniec programu. Jeśli chcemy,

aby pewien fragment programu był powtórzo-

mov A, B

kopiowanie z A do B

ny kilka razy warto zastosować instrukcję FOR:

add A, B

dodawanie A do B, wynik zapisywany w B

sub A, B

odejmowanie A od B, wynik zapisywany w B

[zmienna] FOR n

mul A, B

mnożenie B przez A, wynik zapisywany w B

instrukcje

div A, B

dzielenie całkowite B przez A, część całkowita wyniku zapisywana w B, dziele-

ROF

nie przez zero powoduje śmierć procesu

mod A, B

dzielenie modulo B przez A, reszta z dzielenia zapisywana w B, dzielenie

Instrukcje zostaną wstawione do programu n

przez zero powoduje śmierć procesu

razy, co więcej możemy używać wyrażenia

jmp A[, B]

skok bezwarunkowy do komórki A

zmienna, które będzie zawierać aktualny nu-

mer rozwinięcia:

jmn A, B

skok do A, jeśli B jest różne od zera

jmz A, B

skok do A, jeśli B jest równe zero

xx FOR 5

djn A, B

zmniejszenie B o 1 i skok do A, jeśli B jest różne od zera

mov 0, xx

spl A[, B]

uruchomienie równoległego procesu w komórce A

ROF

stl A, B

jeśli A mniejsze od B, to omiń następną instrukcję

cmp A, B

- jeśli A jest równe B, to omiń następną instrukcję

Po kompilacji otrzymamy następujący kod:

seq A, B

sne A, B

odwrotnie niż cmp, jeśli A i B są różne, to omiń następną instrukcję

mov 0, 1

mov 0, 2

nop [A, B]

instrukcja pusta

mov 0, 3

ldp A, B

załaduj komórkę A P-Space do komórki B

mov 0, 4

stp A, B

zapisz A do komórki B P-Space

mov 0, 5

56

marzec 2008

www.lpmagazine.org

57





Programowanie

Programowanie

Wojny Rdzeniowe

Wojny Rdzeniowe

RedCode oferuje także dostęp do specjalnych Skoczek – Imp

cały rdzeń. Taki program zwykło się określać

zmiennych. Jedną z nich jest wielkość rdzenia Po opisie instrukcji RedCode, możemy napi- mianem skoczka i wbrew pozorom jest dość CORESIZE. W zmiennej WARRIORS znajduje się sać pierwszego wojownika, który posiada tyl- skuteczny. Wiele prostych programów może liczba programów uczestniczących w poje- ko jedną instrukcję mov:

zostać pokonanych przez ten program. Może-

dynku. Możemy również dokładnie opisywać,

my także kopiować co dwa pola:

na jakich operatorach działamy. Jednakże po- mov 0, 1

dane podstawowe informacje wystarczają do

mov 0, 2

przedstawienia najprostszych, ale zarazem Kopiujemy aktualną zawartość komórki rdze- mov 0, 2

najsłynniejszych wojowników RedCode.

nia do następnej. I ten sposób zamazywany jest

Przykład zastosowania instrukcji FOR jest pro-

stym rozwinięciem tej idei. Bardziej wyrafino-

wany program o sposobie działania podobnym

Kompilacja programów CoreWars oraz pMars

do skoczka to skoczek spiralny (Listing 1.)

W programie używamy naszego skocz-

Omawiane środowisko pMars i wspomniane CoreWars niestety nie są zazwyczaj dołącza-

ka (etykieta imp), który kopiuje się do ety-

ne do dystrybucji Linuxa. Oznacza to konieczność samodzielnej kompilacji oraz instalacji. kiety impsize. Będzie się on kopiował po-

Łatwiej jest dokonać kompilacji CoreWars, ponieważ pakiet ten posiada skrypt configure. dobnie jak zwykły skoczek, ale z większym Po dekompresji archiwum

przesunięciem. Co więcej dzięki instrukcji

spl powstaną cztery oddzielne procesy. To-

tar zxvpf corewars-0.9.13.tar.gz

też, jeśli nawet któryś z procesów zostanie

należy przeprowadzić konfigurację np.:

uszkodzony, pozostają jeszcze trzy inne pro-

cesy, które nadal będą sukcesywnie zamazy-

./configure --prefix=/opt

wać rdzeń. Takie rozwiązanie powoduje, iż

zwykły skoczek będzie przegrywał więk-

gdzie jak zwykle za pomocą polecenia --prefix określamy katalog docelowy. Następnie szość pojedynków.

po zakończonej konfiguracji (środowisko CoreWars wymaga obecności biblioteki GTK+ w

starszej wersji 1.2.xx), rozpoczynamy właściwą kompilację za pomocą polecenia make. Po Rozdzielacz – Split er kilku chwilach możemy zainstalować program wydając polecenie make install.

Innym prostym programem RedCode jest

Drugi z programów pMars niestety nie posiada skryptu configure, został wyposażony Splitter, którego nazwę w wolnym tłuma-tylko w skrypt makefile. Po dekompresji archiwum

czeniu najlepiej tłumaczyć jako rozdzielacz.

Pierwsza instrukcja tworzy proces potomny

tar zxvpf pmars-0.9.2-5.tar.gz

od adresu zerowego. Następnie wchodzimy

należy przejść do nowo utworzonego katalogu. Jednakże w nim nie znajdziemy pliku ma-w pętlę, pierwsza instrukcja zwiększy o dzie-

kefile. Plik ten znajduje się w podkatalogu src. Po wydaniu polecenia make rozpocznie-sięć adres instrukcji spl. Co oznacza iż na-

my proces kompilacji, a po kilku chwilach zostanie utworzony plik wykonywalny, który bę-

stępne wykonanie instrukcji spl, spowodu-

dzie gotowym symulatorem wojen rdzeniowych. Będzie to jednak tylko sam symulator, jeśli je utworzenie nowego procesu o dziesięć ko-chcemy mieć dostęp do graficznego podglądu za pomocą biblioteki SDL, należy zdefinio-mórek dalej. Jedyną instrukcją jaką umieści-

wać odpowiednią stałą -DSDLGRAPHX. Stałą tę umieszczamy w zmiennej CFLAGS. Po doko-

my pod nową pozycją jest spl. Po wykona-

naniu tej zmiany, definicja zmiennej CFLAGS przybiera następującą postać

niu przeniesienia, ponownie zwiększamy ad-

res dla instrukcji spl. Sam program przedsta-

CFLAGS = -O4 -fomit-frame-pointer $(DBG) -DSERVER -DEXT94 -DPERMUTATE -

wia się następująco:

DSDLGRAPHX $(INC)

splitter spl 0

Dodatkowo należy usunąć komentarz dla zmiennych INC oraz LIB:

loop add #10, splitter

mov splitter, @splitter

INC = `sdl-config –cflags`

jmp loop

LIB = `sdl-config –libs`

W podobny sposób możemy włączyć graficzny podgląd dla środowiska X-Window. Należy Zaletą tego programu jest tworzenie dużej ilo-do lini CFLAGS, dodać następującą definicję -DXWINGRAPHX. A następnie dodać bądź usu-

ści procesów, a ponieważ wygrywa ten program,

nąć komentarz w lini

który ciągle działa, więc Rozdzielacz ma duże

szanse na przeżycie ataku innych programów.

LIB = -L/usr/X11R6/lib -lX11

Incendiary Bomb

Koniecznie trzeba jeszcze wspomnieć o stałej -DSERVER, która jest odpowiedzialna za To kolejny prosty ale bardzo niebezpieczny obecność debuggera dla RedCode. Jej zdefiniowanie powoduje, iż pMars jest kompilo-program. Jego dwie instrukcje przedstawiają

wany w trybie serwera, co oznacza, że otrzymamy symulator pojedynków. Warto tę defini-się następująco:

cje usunąć, jeśli planujemy testować i sprawdzać, jak zachowują się programy, nad który-mi aktualnie pracujemy. Bowiem, będziemy mogli skorzystać z wbudowanego debuggera spl 0, 8

RedCode o nazwie cdb.

mov -1, <-1

58

marzec 2008

www.lpmagazine.org

59





Programowanie

Programowanie

Wojny Rdzeniowe

Wojny Rdzeniowe

Pierwsza instrukcja powołuje do życia nowy pro- Karzeł Bombiarz – Dwarf

Sam kod źródłowy, jest bardzo prosty:

ces od adresu zerowego. Jednakże drugi argu- Zasada działania tego programu jest rów-ment spl to adres, gdzie instrukcja mov ma prze- nież bardzo prosta. Co cztery komórki bomb DAT #0

nieść instrukcję spl. Wartość adresu jak widać umieszczamy bombę, czyli instrukcję dat dwarf ADD #4, bomb jest zmniejsza o jedność, więc już po chwili po- 0,0 która jak wiadomo prowadzi do zabi- MOV bomb, @bomb wstanie osiem instrukcji spl, które nieustanie bę- cia aktywnego procesu. Ponieważ nasz pro- JMP dwarf dą tworzyć nowe procesy. Możemy nawet zwięk- gram liczy trzy linie, a bombę umieszczamy szyć wartość pola B instrukcji na inną, a zobacz- co cztery komórki, oznacza to, iż ominie- Replicators – Replikator Mysz my, że spowoduje to zmianę ilości instrukcji spl. my własny kod. Inne programy mogą zostać Ostatnim przykładem programu jaki zostanie po-Ostatecznie instrukcja mov zostanie zamazana unieszkodliwione przez naszego wojownika kazany jest program o nazwie Mice, czyli Mysz.

przez instrukcję spl i powstanie swoista pętla in- bardzo szybko, jeśli uda się nam trafić choć- Program ten został napisany w roku 1986 przez strukcji powołujących do życia do nowe procesy. by jedną bombą.

Chipa Wendel a. Jego zadaniem jest kopiowa-

nie się po rdzeniu w pewnych odstępach określo-

nych przez wartość określoną pod etykietą spa-

cer. Powoływane są także nowe procesy instruk-

cją spl. Kopiowanie kodu następuje przy uży-

ciu instrukcji mov oraz instrukcji pętli djz. Pro-

gram Mysz tworzy nowe procesy, które kopiują

kod do następnego adresu. W ten sposób trudniej

jest usunąć program z pamięci, ponieważ po usu-

nięciu pierwszego procesu, pozostaje drugi, który

dysponuje pełnym kodem programu. Nowe po-

wstałe procesy także przenoszą kod w inne miej-

sca pamięci. Tego typu programy nazywa się re-

plikatorami, ponieważ przenoszą się samodziel-

nie po pamięci, a każdy proces jest niezależny.

Program ten działa niewątpliwe w sposób podob-

ny do typowego wirusa komputerowego, który

infekuje kolejne programy. Pełen kod źródłowe-

go programu jest następujący (Listing 2.)

Jak uruchamiać programy?

Po podaniu kilku przykładów, należy się jeszcze

słowo dla tych użytkowników, którzy chcieliby

uruchomić zamieszczone programy. W pierw-

Rysunek 1. Program Corewars i pojedynek miedzy czterema wojownikami

Listing 1. Kod źródłowy dla skoczka spiralnego

impsize equ 2667

example spl 4

spl 2

jmp imp+(0*impsize)

jmp imp+(1*impsize)

spl 2

jmp imp+(2*impsize)

jmp imp+(3*impsize)

imp mov 0, impsize

Listing 2. Replikator Mysz

top dat #0, #0

start mov #12, top

loop mov @Top,
djn loop, top

spl @target,0

spacer equ 653

add #spacer, target

jmz start, top

target dat #0, #833

end Start

Rysunek 2. Program pMars oraz walka między skoczkami

58

marzec 2008

www.lpmagazine.org

59





Programowanie

Wojny Rdzeniowe

szej kolejności należy utworzyć pliki źródłowe uruchomić program pmars podając jako argu- ilość rund np.: na dziesięć, to należy zastoso-z programami. Do tego celu wystarczy dowolny ment nazwę pliku źródłowego programu:

wać parametr -r:

edytor tekstowy np.: GEdit w GNOME czy Ka-

te w KDE, albo typowe narzędzie konsolowe jak pmars imp.red

pmars -r 10 imp.red dwarf.red

choćby VIM. Wszystkie programy opisane w ar-

tykule znajdują się także na płycie DVD.

Gdy chcemy zobaczyć pojedynek programów, Jeśli, chcemy dokładnie śledzić wykonywa-Uruchomienie programów, z poziomu apli- to podajemy kilka nazw programów z kodem nie się programu, to warto skorzystać z wbu-kacji pMars nie jest zbyt trudne. Jednakże mu- źródłowym np.:

dowanego debuggera o nazwie cdb w progra-

simy korzystać z konsoli. Warto w katalogu do-

mie pMars. Chcąc śledzić pracę np.: programu

mowym utworzyć nowy podkatalog i dokonać pmars imp.red dwarf.red

Dwarf uruchamiamy symulator MARS'a, w na-

kompilacji programu pMars, lub przenieść z

stępujący sposób:

płyt DVD gotową wersję pMarsa (dla bibliote- Naturalnie program pmars przyjmuje kilka-ki SDL albo X-Windows).

naście parametrów. Pierwszym bardzo istot- pmars -e dwarf.red

Jeśli chcemy sprawdzić jak wykonuje się nym jest parametr -r. Domyślnie mamy tyl-

program jednego z wojowników, wystarczy ko jedną rundę, więc jeśli chcemy zmienić Poleceń debuggera jest dość sporo, krótki opis wszystkich zobaczymy po wydaniu polecenia

help lub po prostu po naciśnięciu klawisza en-

ter. Instrukcja step (możemy także korzystać

W Sieci

ze skróconej wersji – jedna litera s) wykonuje

program instrukcja po instrukcji. Możemy doko-

�ó Oryginalne artykuły o Core Wars

nać deasemblacji wybranego zakresu, np.: pole-



http://www.koth.org/info/sciam/

cenie list 1,5 wyświetli zawartość rdzenia od

�ó �śKról Wzgórza”, (ang. King of the Hil – KOTH), strona zawiera podstawowe informa-komórki numer jeden do komórki numer pięć.

cje oraz adresy o CoreWars

Śledzenie instrukcja po instrukcji jest



http://www.koth.org/

żmudne, więc warto użyć polecenia trace,

�ó Strona programu pMars, oficjalnego systemu do symulacji wojen rdzeniowych

które po każdym wydanym poleceniu go, bądź



http://www.koth.org/pmars/

po wciśniętym klawiszu enter, będzie wyko-

�ó Interesująca strona o CoreWars, zawiera kod programów oraz odnośniki do kilku cie-nywać cały zestaw poleceń, aż ponownie ste-

kawych publikacji o CoreWars

rowanie wróci do punktu w którym wykonane



http://corewar.atspace.com/

zostało polecenie trace. Gdy śledzimy pojedy-

�ó Polska strona o CoreWars, warto przeczytać

nek, polecenie progress pokaże aktualny przy-



http://www.knf.pw.edu.pl/~adamow/corewar

dział punktów dla każdego programu.

�ó Nieco starsze środowisko do wojen rdzeniowych, lecz równie dobre jak pMars



http://sourceforge.net/projects/corewars/

Podsumowanie

�ó Strona serwera do potyczek związana z programem Corewars

Wielu osobom może się wydawać, że wpatry-



http://sal.math.ualberta.ca/

wanie się w migoczące kwadraty, to zwykła

strata czasu. Nie jest to sprawiedliwa opinia,

gdyż warto choćby wypróbować przedstawio-

ne programy, choć są to tylko najprostsze przy-

kłady. Koniecznie trzeba to zrobić, jeśli chcemy

pisać bardziej skomplikowane programy. W In-

ternecie można odszukać wiele interesujących

przykładów stanowiących prawdziwe wyzwa-

nie. Jednakże piękno wojen rdzeniowych ujaw-

nia się w małych programach, opartych o pew-

ną strategię bądź ideę. Wszystkie wykorzy-

stane biblioteki, kod źródłowy programu oraz

wszystkie listingi z artykułu znajdują się na

stronie http://www.lpmagazine.org.

O autorze

Autor zajmuje się tworzeniem oprogramo-

wania dla WIN32 i Linuksa. Zainteresowa-

nia: teoria języków programowania oraz

dobra literatura.

Rysunek 3. Program pMars i debugger cdb podczas śledzenia programu Dwarf

Kontakt z autorem: [e-mail].

60

marzec 2008