2008.03_Wojny rdzeniowe_[Programowanie].pdf

Programowanie

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 Scientiic American . W ten sposób narodziła

się jedna z legend informatyki.

gra, gdzie w pamięci zwanej rdzeniem

(ang. core ), zarządzanej przez komputer

albo procesor o nazwie MARS wykony-

wany jest kod umieszczonych w pamięci programów. Wy-

grywa ten program, który pokona pozostałych przeciwników

np.: poprzez ich wymazanie z pamięci albo poprzez zastąpie-

niem własnym kodem. Mówiąc inaczej, wygrywa ten pro-

gram, który nadal działa, po upłynięciu odpowiedniego cza-

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

zwie RedCode. Jest on bardzo podobny do assemblera. Ist-

nieją kilka wariantów RedCode, jednak w dalszej części sku-

pimy się tylko na oryginalnej wersji RedCode.

Skromne ramy artykułu pozwalają na przedstawienie

tylko kilku przykładów. Dlatego już na samym początku

zachęcam na szukania innych przykładów programów pi-

sanych w RedCode. Warto także na samym początku po-

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

gicznie jak standardy dla języków C, C++ czy Java. Ostat-

nim standardem jest ICWS'94. Dostępne są także pewne

uproszczone odmiany języka RedCode. Bez względu na

odmianę Red Code należy posiadać specjalny symulator

maszyny MARS. Istnieje wiele dostępnych programów,

oicjalnym programem jest pMars, który omawiam w tym

artykule. Innym równie ciekawym jest program o wszyst-

ko mówiącej nazwie CoreWars. Program ten oferuje na-

wet dwie wersje języka programowania dla wojen rdze-

niowych: oryginalny RedCode oraz równie ciekawą jak

sam RedCode odmianę o nazwie CoreWars. Jednak, z ra-

cji ograniczonego miejsca, będziemy zajmować się tylko

samym RedCode i środowiskiem MARS.

MARS – deinicja

Programy napisane w języku RedCode są wykonywane w ra-

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

tego środowiska jest pamięć operacyjna, czyli rdzeń. Zazwy-

czaj do dyspozycji mamy 8000 dostępnych komórek pamię-

ci. Ilość pamięci można zmieniać, a ogólnie wielkość pamię-

ci jest zapisana w przedeiniowanej zmiennej CORESIZE .

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

jest fakt, iż w dostępie do pamięci obowiązuje adresowa-

nie względne. Innymi słowy, nie ma adresu początkowego

oraz końcowego. Adres zerowy to adres komórki, w której

aktualnie się znajdujemy, wartość 1 to adres komórki następ-

marzec 2008

W ojny rdzeniowe to bardzo specyiczna

Programowanie

Wojny Rdzeniowe

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

Oznacza to także, iż rdzeń jest zapętlony. Na-

stępną komórką pamięci po ostatniej jest ko-

mórka pierwsza.

Każda komórka pamięci posiada trzy ele-

menty: pole instrukcji, pole argumentu źródło-

wego A oraz pole argumentu docelowego B .

Nie ma typowych rejestrów jak w rzeczywi-

stych procesorach, jednakże dostępny jest ob-

szar pamięci nazwany P-Space , do którego,

każdy z programów ma wyłączny dostęp. Jed-

nak P-Space jest nowym elementem i klasycz-

na wersja RedCode nie oferuje dostępu do do-

datkowej przestrzeni pamięci.

W jednym takcie wykonywana jest tyl-

ko jedna instrukcja (co oznacza, że czas wy-

konania poszczególnych typów instrukcji

jest taki sam), i po jej wykonaniu MARS

przechodzi do wykonania instrukcji z na-

stępnej komórki pamięci. Wyjątkiem jest in-

strukcja skoku, która przenosi sterowanie do

innego miejsca w pamięci. W pamięci mo-

że być wykonywanych kilkanaście progra-

mów różnych użytkowników. W takim przy-

padku MARS wykonuje je kolejno, po jed-

nej instrukcji.

MARS dopuszcza także uruchamianie pro-

cesów potomnych w ramach programu użyt-

kownika za pomocą instrukcji spl . Każdy z

nowo utworzonych procesów zapisywany jest

w kolejce zadań. System kolejno po jednej in-

strukcji przetwarza procesy z listy zadań.

RedCode

Przedstawiona powyżej deinicja systemu MARS

nie jest zbyt skomplikowana, podobnie jak język

RedCode. Jednak, jak zawsze w przypadku języ-

ka programowania podobnego do assemblera,

napisanie dobrego programu nie jest łatwe.

Pojedyncza instrukcja RedCode, podobnie

jak w wielu istniejących assemblerach, jest zbu-

dowana z czterech elementów: etykiety, kodu in-

strukcji oraz dwóch pól argumentów. Schema-

tycznie przedstawimy to, w następujący sposób:

dat #0, #0 oznacza umieszczenie w aktualnej

komórce wartości 0 w polach A oraz B , natomiast

dat #1, #2 , oznacza umieszczenie odpowied-

nio jedynki i dwójki. Znak $ oznacza bezpośred-

ni adres. Przykładem zastosowania adresowania

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

siebie mov $0,$1 . Ponieważ adresowanie jest

bardzo często używane, to możemy także napi-

sać mov 0, 1 . Większość kompilatorów RedCo-

de dopuszcza stosowanie tego typu skrótu. Inny

przykład instrukcji to mov #2, 1 , oznaczający

przeniesienie dwójki pod następny adres.

Dwa kolejne typy adresowania są repre-

zentowane przez symbole * oraz @ . Pierwszy

adresuje pośrednio przez pole A , drugi sym-

bol przez pole B . Oznacza to iż z pola np.: A od-

czytywany jest adres pod którym znajduje się

informacja o właściwym adresie. Taki typ ad-

resowania to nic innego, jak wskazanie przez

wskaźnik, stosowane w wielu językach wyso-

kiego poziomu jak Pascal czy C. Kolejne tryby

adresowania są reprezentowane przez symbo-

le { , } oraz < , > . Oznaczają one również adreso-

wanie pośrednie przy pomocy pól A oraz B. Jed-

nakże symbol { oznacza iż adres zostanie pobra-

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

skokiem wartość ta zostanie zmniejszona. Po-

dobnie dla symbolu }, ale tym razem zostanie

ona zwiększona. Uzupełnieniem instrukcji Red-

Code są pseudoinstrukcje sterujące procesem

kompilacji programu. Możemy wprowadzać

tekstowe oznaczenia dla wartości liczbowych:

nazwa EQU wartość . Instrukcja ORG etykieta

pozwala na ustalenie adresu początkowego dla

programu. Natomiast instrukcja END [etykie-

ta] oznacza koniec programu. Jeśli chcemy,

aby pewien fragment programu był powtórzo-

ny kilka razy warto zastosować instrukcję FOR :

etykieta trzyliterowy kod instrukcji

[pole_A, pole_B]

Spis wszystkich instrukcji przedstawia tabela

pt. Instrukcje RedCode . Ważną rolę pełni in-

strukcja dat , a dokładniej jej postać dat 0,0

(lub dat $0, $0 ). Jest to nielegalna instrukcja i

jej wykonanie doprowadzi do śmierci wykony-

wanego programu. Domyślnie, cały rdzeń jest

wypełniony tymi instrukcjami. Dodam jesz-

cze, że wyrażenia w nawiasach kwadratowych

są opcjonalne np.: jeśli chcemy zapisać instruk-

cję skoku o pięć komórek do przodu to piszemy

tylko jmp 5 . Argument B , nie jest potrzebny.

Instrukcji języka nie jest wiele, ale istnieje

kilka różnych sposobów adresowania. Podsta-

wową informacją jest fakt, iż adresowanie jest

względne, co zostało już wspomniane wcześniej.

Jednak zastosowanie znaku # (hash) oznacza

bezpośrednią wartość liczbową, czyli instrukcja

Tabela 1. Instrukcje RedCode

Instrukcja

Krótki opis

dat [A,] B

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

mov A, B

kopiowanie z A do B

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

instrukcje

ROF

mul A, B

mnożenie B przez A, wynik zapisywany w B

div A, B

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

nie przez zero powoduje śmierć procesu

mod A, B

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

przez zero powoduje śmierć procesu

Instrukcje zostaną wstawione do programu n

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

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

mer rozwinięcia:

jmp A[, B]

skok bezwarunkowy do komórki A

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

mov 0, xx

ROF

djn A, B

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

spl A[, B]

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

stl A, B

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

cmp A, B

seq A, B

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

Po kompilacji otrzymamy następujący kod:

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

mov 0, 3

mov 0, 4

mov 0, 5

nop [A, B]

instrukcja pusta

ldp A, B

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

stp A, B

zapisz A do komórki B P-Space

www.lpmagazine.org

Programowanie

Wojny Rdzeniowe

RedCode oferuje także dostęp do specjalnych

zmiennych. Jedną z nich jest wielkość rdzenia

CORESIZE . W zmiennej WARRIORS znajduje się

liczba programów uczestniczących w poje-

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

na jakich operatorach działamy. Jednakże po-

dane podstawowe informacje wystarczają do

przedstawienia najprostszych, ale zarazem

najsłynniejszych wojowników RedCode.

Skoczek – Imp

Po opisie instrukcji RedCode, możemy napi-

sać pierwszego wojownika, który posiada tyl-

ko jedną instrukcję mov :

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

mianem skoczka i wbrew pozorom jest dość

skuteczny. Wiele prostych programów może

zostać pokonanych przez ten program. Może-

my także kopiować co dwa pola:

mov 0, 1

Kopiujemy aktualną zawartość komórki rdze-

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

mov 0, 2

Kompilacja programów CoreWars oraz pMars

Przykład zastosowania instrukcji FOR jest pro-

stym rozwinięciem tej idei. Bardziej wyraino-

wany program o sposobie działania podobnym

do skoczka to skoczek spiralny (Listing 1.)

W programie używamy naszego skocz-

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

kiety impsize . Będzie się on kopiował po-

dobnie jak zwykły skoczek, ale z większym

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

spl powstaną cztery oddzielne procesy. To-

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

uszkodzony, pozostają jeszcze trzy inne pro-

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

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

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

szość pojedynków.

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

ne do dystrybucji Linuxa. Oznacza to konieczność samodzielnej kompilacji oraz instalacji.

Łatwiej jest dokonać kompilacji CoreWars, ponieważ pakiet ten posiada skrypt conigure .

Po dekompresji archiwum

tar zxvpf corewars-0.9.13.tar.gz

należy przeprowadzić konigurację np.:

./conigure --preix=/opt

gdzie jak zwykle za pomocą polecenia --preix określamy katalog docelowy. Następnie

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

starszej wersji 1.2.xx), rozpoczynamy właściwą kompilację za pomocą polecenia make . Po

kilku chwilach możemy zainstalować program wydając polecenie make install .

Drugi z programów pMars niestety nie posiada skryptu conigure , został wyposażony

tylko w skrypt makeile . Po dekompresji archiwum

Rozdzielacz – Splitter

Innym prostym programem RedCode jest

Splitter , którego nazwę w wolnym tłuma-

czeniu najlepiej tłumaczyć jako rozdzielacz .

Pierwsza instrukcja tworzy proces potomny

od adresu zerowego. Następnie wchodzimy

w pętlę, pierwsza instrukcja zwiększy o dzie-

sięć adres instrukcji spl . Co oznacza iż na-

stępne wykonanie instrukcji spl , spowodu-

je utworzenie nowego procesu o dziesięć ko-

mórek dalej. Jedyną instrukcją jaką umieści-

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

niu przeniesienia, ponownie zwiększamy ad-

res dla instrukcji spl . Sam program przedsta-

wia się następująco:

tar zxvpf pmars-0.9.2-5.tar.gz

należy przejść do nowo utworzonego katalogu. Jednakże w nim nie znajdziemy pliku ma-

keile . Plik ten znajduje się w podkatalogu src . Po wydaniu polecenia make rozpocznie-

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

dzie gotowym symulatorem wojen rdzeniowych. Będzie to jednak tylko sam symulator, jeśli

chcemy mieć dostęp do graicznego podglądu za pomocą biblioteki SDL, należy zdeinio-

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

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

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

DSDLGRAPHX $(INC)

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

splitter spl 0

loop add #10, splitter

mov splitter, @splitter

jmp loop

INC = `sdl-conig –clags`

LIB = `sdl-conig –libs`

W podobny sposób możemy włączyć graiczny podgląd dla środowiska X-Window. Należy

do linii CFLAGS , dodać następującą deinicję -DXWINGRAPHX . A następnie dodać bądź usu-

nąć komentarz w linii

Zaletą tego programu jest tworzenie dużej ilo-

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

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

Koniecznie trzeba jeszcze wspomnieć o stałej -DSERVER , która jest odpowiedzialna za

obecność debuggera dla RedCode. Jej zdeiniowanie powoduje, iż pMars jest kompilo-

wany w trybie serwera, co oznacza, że otrzymamy symulator pojedynków. Warto tę deini-

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

RedCode o nazwie cdb .

Incendiary Bomb

To kolejny prosty ale bardzo niebezpieczny

program. Jego dwie instrukcje przedstawiają

się następująco:

spl 0, 8

mov -1, <-1

marzec 2008

Programowanie

Wojny Rdzeniowe

Pierwsza instrukcja powołuje do życia nowy pro-

ces od adresu zerowego. Jednakże drugi argu-

ment spl to adres, gdzie instrukcja mov ma prze-

nieść instrukcję spl . Wartość adresu jak widać

jest zmniejsza o jedność, więc już po chwili po-

wstanie osiem instrukcji spl , które nieustanie bę-

dą tworzyć nowe procesy. Możemy nawet zwięk-

szyć wartość pola B instrukcji na inną, a zobacz-

my, że spowoduje to zmianę ilości instrukcji spl .

Ostatecznie instrukcja mov zostanie zamazana

przez instrukcję spl i powstanie swoista pętla in-

strukcji powołujących do życia do nowe procesy.

Karzeł Bombiarz – Dwarf

Zasada działania tego programu jest rów-

nież bardzo prosta. Co cztery komórki

umieszczamy bombę, czyli instrukcję dat

0,0 która jak wiadomo prowadzi do zabi-

cia aktywnego procesu. Ponieważ nasz pro-

gram liczy trzy linie, a bombę umieszczamy

co cztery komórki, oznacza to, iż ominie-

my własny kod. Inne programy mogą zostać

unieszkodliwione przez naszego wojownika

bardzo szybko, jeśli uda się nam traić choć-

by jedną bombą.

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

bomb DAT #0

dwarf ADD #4, bomb

MOV bomb, @bomb

JMP dwarf

Replicators – Replikator Mysz

Ostatnim przykładem programu jaki zostanie po-

kazany jest program o nazwie Mice, czyli Mysz.

Program ten został napisany w roku 1986 przez

Chipa Wendella. 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.)

Rysunek 1. Program Corewars i pojedynek miedzy czterema wojownikami

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-

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, <target

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

www.lpmagazine.org

Programowanie

Wojny Rdzeniowe

szej kolejności należy utworzyć pliki źródłowe

z programami. Do tego celu wystarczy dowolny

edytor tekstowy np.: GEdit w GNOME czy Ka-

te w KDE, albo typowe narzędzie konsolowe jak

choćby VIM. Wszystkie programy opisane w ar-

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

Uruchomienie programów, z poziomu apli-

kacji pMars nie jest zbyt trudne. Jednakże mu-

simy korzystać z konsoli. Warto w katalogu do-

mowym utworzyć nowy podkatalog i dokonać

kompilacji programu pMars, lub przenieść z

płyt DVD gotową wersję pMarsa (dla bibliote-

ki SDL albo X-Windows).

Jeśli chcemy sprawdzić jak wykonuje się

program jednego z wojowników, wystarczy

uruchomić program pmars podając jako argu-

ment nazwę pliku źródłowego programu:

ilość rund np.: na dziesięć, to należy zastoso-

wać parametr -r :

pmars imp.red

pmars -r 10 imp.red dwarf.red

Gdy chcemy zobaczyć pojedynek programów,

to podajemy kilka nazw programów z kodem

źródłowym np.:

Jeśli, chcemy dokładnie śledzić wykonywa-

nie się programu, to warto skorzystać z wbu-

dowanego debuggera o nazwie cdb w progra-

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

Dwarf uruchamiamy symulator MARS'a, w na-

stępujący sposób:

pmars imp.red dwarf.red

Naturalnie program pmars przyjmuje kilka-

naście parametrów. Pierwszym bardzo istot-

nym jest parametr -r . Domyślnie mamy tyl-

ko jedną rundę, więc jeśli chcemy zmienić

pmars -e dwarf.red

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ć

ze skróconej wersji – jedna litera s ) wykonuje

program instrukcja po instrukcji. Możemy doko-

nać deasemblacji wybranego zakresu, np.: pole-

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

komórki numer jeden do komórki numer pięć.

Śledzenie instrukcja po instrukcji jest

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

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

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

nywać cały zestaw poleceń, aż ponownie ste-

rowanie wróci do punktu w którym wykonane

zostało polecenie trace . Gdy śledzimy pojedy-

nek, polecenie progress pokaże aktualny przy-

dział punktów dla każdego programu.

W Sieci

• Oryginalne artykuły o Core Wars

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

• „Król Wzgórza”, (ang. King of the Hill – KOTH), strona zawiera podstawowe informa-

cje oraz adresy o CoreWars

http://www.koth.org/

• Strona programu pMars, oicjalnego systemu do symulacji wojen rdzeniowych

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

• Interesująca strona o CoreWars, zawiera kod programów oraz odnośniki do kilku cie-

kawych publikacji o CoreWars

http://corewar.atspace.com/

• Polska strona o CoreWars, warto przeczytać

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

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

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

• Strona serwera do potyczek związana z programem Corewars

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

Podsumowanie

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

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

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

Autor zajmuje się tworzeniem oprogramo-

wania dla WIN32 i Linuksa. Zainteresowa-

nia: teoria języków programowania oraz

dobra literatura.

Kontakt z autorem: autorzy@linux.com.pl .

marzec 2008

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: