RedCode

RedCode jest językiem stworzonym na potrzeby gry „Core Wars” – w której gracze piszą programy – zawodników które walczą ze sobą w pamięci komputera. Programy umieszczane są w losowych miejscach pamięci i nie wiedzą w jakim miejscu znajduje się przeciwnik. Gra polega na psuciu kodu przeciwnika przez wpisywanie mu bzdur, lub przebudowę jego programu tak, by odwoływał się do innych obszarów pamięci niż chciał tego przeciwnik – programista.

Język jakiego używamy do pisania swoich zawodników przypomina wczesne asslemblery. Mamy tu proste operacje na liczbach całkowitych, instrukcje skoku, przypisania, kilka trybów adresowania oraz – co może zdziwić – ale czyni grę na prawdę fascynującą – instrukcja rozdzielnia programu na wątki.

Myślę, że po napisaniu kilku niewielkich programów w języku RedCode – czytelnik nie będzie miał problemów w używaniu wskaźników i trochę lepiej zrozumie zasady funkcjonowania komputera.

Budowa instrukcji

Instrukcja w języku RedCode składa się z trzech pól:

·         Kod polecenia

·         Pierwszy argument

·         Drugi argument

Instrukcję zapisujemy jako

              KOD arg1, arg2

 

Gdzie KOD jest kodem instrukcji – trzyznakowym skrótem oznaczającym operacje, natomiast arg1 i arg2 – są argumentami instrukcji. W niektórych przypadkach arg2 jest niepotrzebny i piszemy tylko

 

              KOD arg1

 

Instrukcja może być poprzedzona etykietą:

 

etykieta:     KOD arg1, arg2

 

Jeśli instrukcja nie wymaga podania argumentów – nie trzeba ich pisać w programie, jednak pamięć dla nich jest zawsze dostępna i może być używana do przechowywania danych. Jeśli modyfikujemy jakąś komórkę pamięci, lub pobieramy wartość komórki pamięci – to zawsze jest to pamięć przeznaczona na pierwszy argument.

Program operuje na wartościach z przedziału od 0 do 9999 (lub – jeśli są traktowane jako liczby ze znakiem z zakresu –5000 do 4999). Programy pracują w pamięci która ma tyle komórek ile można zaadresować – 10000. Wszystkie operacje wykonywane są modulo 10000.

Jedna instrukcja zawsze zajmuje jedną komórkę pamięci i jest wykonywana w jednym cyklu pracy komputera.

W grze „Core Wars” programu pracują 2 programy których instrukcje są wykonywane na przemian. Wątki każdego z graczy wykowywane są po jednej instrukcji.

Tryby adresowania

W językach typu asembler – których instrukcje odpowiadają bezpośrednio instrukcjom jakie wykonuje procesor, nie mamy różnych typów zmiennych – jak to ma miejsce w językach wyższego rzędu. To jak interpretujemy dane w pamięci – zależy od programu i aktualnie wykonywanej instrukcji. Mamy tu natomiast choć – co w językach wyższego rzędu  nie występuje – lub coś czym w językach wyższego rzędu się nie wspomina – różne sposoby adresowania pamięci – czyli różne sposoby obliczania adresu pod jakim znajduje się dana w pamięci.

W podstawowej definicji języka mamy do dyspozycji 4 sposoby adresowania pamięci.

1.        Natychmiastowe – argument na którym działamy jest umieszczony w samej instrukcji. Nie trzeba więc obliczać adresu komórki pamięci, tylko działać na danej umieszczonej w kodzie instrukcji. W C++ odpowiada takiemu sposobowi adresowania – wzięcie stałej. Tu jednak, ponieważ możemy modyfikować kod programu – pojęcie stałej nie istnieje. Możemy przecież wstawić wartość bezpośrednio w instrukcję. W języku RedCode wartość adresowaną natychmiastowo – poprzedza znak ‘#’ – wskazujący, że mamy użyć wartości a nie zawartości komórki i tym adresie.

2.        Bezpośrednie – operacja będzie wykonana na komórce o wskazanym numerze. Ponieważ program powinien być przenośny i jego działanie nie powinno zależeć od miejsca w jakim został umieszczony, wszystkie komórki pamięci adresowane są względem bieżącego adresu. Ten typ adresowania określony jest samą liczba (bez dodatkowych znaków określających tryb adresowania), można również używać etykiet pisząc po prostu nazwę etykiety. Kompilator programu obliczy adres względny i umieści w kompilacje odpowiednią wartość.

3.        Pośrednie – w instrukcji umieszczamy adres komórki z której bierzemy adres komórki o którą nam chodzi. O ile adresowanie bezpośrednie przypomina użycie zmiennych – to adresowanie pośrednie – jest typowym użyciem zmiennej wskaźnikowej. Ten sposób adresowania pozwala na obliczanie adresu lub ogólniej zmianę adresu pod którym będziemy czytać lub pisać pamięć, beż konieczności modyfikacji kodu programu w czasie jego wykonywania. Adresowanie pośrednie oznaczamy poprzez dodanie znaku ‘@’ przed liczbą oznaczającą adres komórki. Można tu również używać etykiet.

4.        Pośrednie predekrementowane – znane programistom mającym praktykę w języku C. Działa dokładnie tak samo jak pośrednie – jednak przed użyciem wskaźnika – jego zawartość jest zmniejszana o 1. Podobnie jak w innych przypadkach możemy używać etykiet – i podobnie jak w innych przypadkach ten typ adresowania jest oznaczony znakiem poprzedzającym adres komórki pamięci. W tym wypadku znakiem mniejszości ‘<’

Lista instrukcji

W podstawowej wersji języka RedCode – mamy do dyspozycji 11 instrukcji. Instrukcje mogą posiadać jeden lub dwa parametry. W większości przypadków parametry mogą być określone przez wszystkie typy adresowania. W niektórych przypadkach pewne tryby adresowania nie są dozwolone.

Pełna lista instrukcji zawiera operacje o kodach: DAT, MOV, JMP, ADD, SUB, CMP, JMZ, JMN, DJN, SLT, SPL pozwalające na wykonywanie dodawania i odejmowania, skoków warunkowych i bezwarunkowych oraz rozdzielania programu na wątki.

DAT arg1

W zasadzie nie jest to polecenie. Komputer próbujący wykonać tą instrukcję – kończy aktualnie wykonywany wątek. Instrukcja ta jest używana do przechowywanie wartości w pamięci. Jej pierwszy argument jest wartością przechowywaną w komórce pamięci. Tryb adresowania tego parametru nie ma znaczenia. Wartości przechowywane w komórkach w których znajduje się instrukcja DAT – zazwyczaj służy jako licznik lub wskaźnik w adresowaniu pośrednim.

Wpisując do komórki pamięci wartość (adresowaną natychmiastowo) – powodujemy wstawienie instrukcji DAT do tej komórki.

MOV arg1, arg2

Operacja kopiowania danej. Argument pierwszy jest źródłem danej – określa jaka wartość (przy adresowaniu natychmiastowym) albo jaka komórka pamięci (przy adresowaniu bezpośrednim i pośrednim) będzie skopiowana. Argument drugi określa dokąd skopiować zawartość Argument 2 nie może być adresowany natychmiastowo – trzeba tu wskazać komórkę pamięci.

Jeśli argument 1 jest po prostu wartością (adresowaną natychmiastowo) – to w komórce określonej przez drugi argument – zostanie umieszczona instrukcja DAT z pierwszym parametrem równym kopiowanej wartości. Jeśli pierwszy argument adresuje komórkę pamięci (adresowanie bezpośrednie lub pośrednie) – to kopiowana jest cała komórka – razem z kodem operacji i drugim argumentem.

Jeśli użyto adresowanie pośredniego predekrementowanego – to dodatkowo wartości wskaźników ulegają zmniejszeniu przed pobraniem (użyciem) wskaźników.

JMP arg1

Skok bezwarunkowy do miejsca w programie określonym argumentem. Nie możemy używać tu adresowania natychmiastowego – jedynie pośrednie lub bezpośrednie – powodujące skok do określonej komórki pamięci, lub komórki której adres znajduje się we wskazanej komórce.

Pamiętajmy, że każde adresowanie dotyczy adresowania względem bieżącej lokalizacji instrukcji w pamięci. Dlatego pętlę nieskończoną możemy zapisać jako JMP 0

ADD arg1, arg2

Dodaj wartość pierwszego argumentu do komórki pamięci określonej drugim parametrem. Drugi parametr nie może być adresowany natychmiastowo – musi to być komórka pamięci. W komórce w której umieszczany jest wynik – jedynie wartość pola pierwszego argumentu ulega zmianie. Pole operacji i drugiego parametru pozostają bez zmian.

Pamiętajmy że wszystkie operacje arytmetyczne wykonywane są modulo 10000. Tak wiec nie można się dziwić, że 6000+6000=2000, lub – co jeszcze bardziej zabawne – że suma dwu wartości ujemnych – może być dodatnia

SUB arg1, arg2

Różnica argumentu drugiego I pierwszego Wynik umieszczany jest w komórce pamięci określanej drugim argumentem. Działa podobnie jak dodawanie – z tą różnicą że wynik jest – różnicą.

CMP arg1, arg2

Porównanie dwu parametrów. Jeśli argumenty są równe – to kolejna instrukcja jest przeskakiwana. Instrukcja ta dopuszcza wszystkie tryby adresowania dla obu argumentów i jest zazwyczaj połączona z instrukcją JMP, która prowadzi do miejsca w programie do którego należy przeskoczyć, ale można też użyć innej instrukcji jako instrukcji wykonywanej warunkowo.

SLT arg1, arg2

Działa podobnie jak CMP – z tą różnicą, że kolejna instrukcja jest przeskakiwana, jeśli pierwszy argument jest mniejszy niż drugi. Podobnie jak w przypadku instrukcji CMP – wszystkie tryby adresowania są dostępne dla obu argumentów.

JMZ arg1, arg2

Instrukcja skoku warunkowego – jeśli wartość pierwszego argumentu jest równy zero – to wykonywany jest skok do miejsca określonego przez drugi argument. Jeśli wartość ta jest różna od zera – to program przechodzi do kolejnej instrukcji.

Pierwszy argument może stosować dowolne tryby adresowania, drugi – jedynie bezpośrednie i pośrednie.

JMN arg1, arg2

Działa podobnie jak instrukcja JMZ – ale skok następuje wtedy gdy wartość pierwszego argumentu jest różna od zera.

DJN arg1, arg2

Bardzo ciekawa instrukcje – Jej działanie to zmniejszenie zawartości komórki pamięci adresowanej (pośrednio lub bezpośrednio przez pierwszy argument, oraz skok pod adres  wskazany przez argument drugi (również adresowany pośrednio lub bezpośrednio) jeśli pierwszy argument – po zmniejszeniu – jest różny od zera.

Za tym skomplikowanym opisem kryje się – instrukcja pętli, którą łatwo zapisać jako:

 

Start:     MOV 10, licznik    ; inicjujemy licznik na 10 iteracji

Petla:     ...

           ...

           ...

           DJN Licznik, Petla ; zmniejszenie – kolejna iteracja

           ...

Licznik:   DAT #0

SPL arg1

Jedna z najciekawszych instrukcji – powodująca rozdzielenie programu poprzez utworzenie nowego wątku. Początek nowego wątku jest wskazywany przez argument instrukcji. (adresowany bezpośrednio lub pośrednio). Instrukcja pozwalające na pisanie silnych wielowątkowych programów, ale także wolnych.

W grze, zawodnicy – a więc programu – otrzymują dokładnie połowę czasu procesora. Czas każdego zawodnika – jest dzielony pomiędzy wątki jego programu. Jeśli jeden zawodnik pracuje w jednym wątku, a drugi uruchamia ich kilka – to program zawodnika pierwszego będzie działał kilkakrotnie szybciej Pamiętajmy jednak, że program uważa się za zniszczony – jeśli wszystkie jego wątki zostaną zabite.

Przykładowy program

Jako przykład zaproponowałbym program który ostrzeliwuje pamięć wokół siebie – a następnie ucieka – kopiując się w inne miejsce pamięci.

 

; Program: Copier

;  Author: WGan

; Version: 1

 

         ; poczatek - inicjacja wskaznikow

start:   mov #target, count

         mov #117, target

         mov  4, source

 

         ; ostrzal przed soba

         mov  #0, -12

         mov  #0, -5

         mov  #0, -10

 

         ; petla kopiujaca sie w inne miejsce

loop:    mov  <source, <target

         djn  count, loop

 

         ; obliczenie adresu skoku - i skok

         sub  #3, target

         jmp  @target

 

         ; obszar zmiennych

target:  dat  #0

source:  dat  #0

count:   dat #0

 

Program jest dość prosty i chyba nie wymaga komentarza. Zwróćmy uwagę, że adresy względne podawane są nie według pola w jakim się znajdują, lecz względem instrukcji w której są używane. Jako samodzielne ćwiczenie – proponuję dodanie kodu który uruchomi dwa lub trzy takie programy wędrujące z różnym krokiem – czyli przeskakujące różną ilość komórek pamięci.

Będzie to wymagało dodania nowej etykiety – w instrukcji przypisującej do zmiennej target – adres względny końca przepisywanego programu – tak byśmy mogli zmodyfikować daną stojącą na pierwszym miejscu – dodając do niej jakąś wartość – trzeba to niestety zrobić po pewnym opóźnieniu – tak by program zdążył się już przepisać.

Inne asemblery

Podobną budowę mają inne asemblery. Poszczególne wersje różnią się liczbą instrukcji i operacji logicznych i arytmetycznych, zestawem trybów adresowania, ilością rejestrów czy wspólnym lub rozdzielonym adresowaniem portów wejścia / wyjścia.

Ponadto różne instrukcje mają różny koszt – wykonując się w czasie od jednego – nawet do kilkudziesięciu taktów zegara. Mogą też zajmować od jednej to kilku komórek pamięci.

Bogactwo języka zależy tu ściśle od sprzętu – procesora na który są pisane programy.

Większość procesorów pozwala na wywoływanie podprogramów, korzystanie z rejestrów – specjalnej pamięci wewnątrz procesora, wykonywania operacji arytmetycznych i logicznych. Szczególnie bogate są niekiedy sposoby adresowania – których liczba dochodziła do dwunastu.

Zadania

1.        Proszę napisać program który nie będzie ‘strzelał’ instrukcjami DAT, ale zerował pierwszy argument instrukcji w pamięci – nie naruszając kodu operacji.

2.        Proszę napisać program który będzie wędrował po pamięci wstecz.

3.        Proszę napisać program który rozmnoży takie wędrowniczki – tworząc programy wędrujące z różnym krokiem.

4.        Proszę napisać własnego zawodnika do gry w „Core Wars” – zachowanie może być dowolne, ale powinno być nastawione na przeżycie.