tło
Lubię mój stary 8-bitowy układ 6502. Zabawne jest nawet rozwiązywanie niektórych problemów tutaj na PPCG w kodzie maszynowym 6502. Ale niektóre rzeczy, które powinny być proste (jak wczytywanie danych lub wysyłanie do standardowego wyjścia) są niepotrzebnie kłopotliwe w kodzie maszynowym. Mam więc w głowie nieokreślony pomysł: wynajdź własną 8-bitową maszynę wirtualną zainspirowaną 6502, ale ze zmienioną konstrukcją, aby była bardziej użyteczna w przypadku wyzwań. Zaczynając coś wdrażać, zdałem sobie sprawę, że może to być miłym wyzwaniem, jeśli konstrukcja maszyny wirtualnej zostanie zredukowana do absolutnego minimum :)
Zadanie
Zaimplementuj 8-bitową maszynę wirtualną zgodną z następującą specyfikacją. To jest golf golfowy , więc wygrywa implementacja z najmniejszą liczbą bajtów.
Wkład
Twoje wdrożenie powinno obejmować następujące dane wejściowe:
Pojedynczy bajt bez znaku
pc
, jest to licznik programu początkowego (adres w pamięci, w którym maszyna wirtualna rozpoczyna wykonywanie,0
na podstawie)Lista bajtów z maksymalną długością
256
wpisów, jest to pamięć RAM dla maszyny wirtualnej (z jej początkową zawartością)
Możesz wziąć to wejście w dowolnym rozsądnym formacie.
Wydajność
Lista bajtów, które są końcową zawartością pamięci RAM po zakończeniu maszyny wirtualnej (patrz poniżej). Możesz założyć, że otrzymujesz tylko dane wejściowe, które ostatecznie prowadzą do zakończenia. Dowolny rozsądny format jest dozwolony.
Wirtualny procesor
Wirtualny procesor ma
- 8-bitowy licznik programów,
- 8-bitowy rejestr akumulatorów o nazwie
A
i - 8-bitowy rejestr indeksu o nazwie
X
.
Istnieją trzy flagi stanu:
Z
- flaga zerowa jest ustawiana po niektórych wynikach operacji0
N
- flaga ujemna jest ustawiana po niektórych operacjach skutkujących liczbą ujemną (ustawiony jest iow bit 7 wyniku)C
- flaga przeniesienia jest ustawiana poprzez dodawanie i przesuwanie „brakującego” bitu wyniku
Po uruchomieniu wszystkie flagi są kasowane, licznik programu jest ustawiany na określoną wartość, a zawartość A
i X
jest nieokreślona.
Wartości 8-bitowe reprezentują albo
- unsigned całkowitą w zakresie
[0..255]
- podpisane całkowitą, 2 jest uzupełnieniem w zakresie
[-128..127]
w zależności od kontekstu. Jeśli operacja jest przepełniona lub niedopełniona, wartość jest zawijana (aw przypadku dodania wpływa na flagę carry).
Zakończenie
Maszyna wirtualna kończy się, kiedy
HLT
Instrukcja zostanie osiągnięta- Dostęp do nieistniejącego adresu pamięci jest uzyskiwany
- Licznik programu działa poza pamięcią (pamiętaj, że nie zawija się, nawet jeśli maszyna wirtualna ma pełne 256 bajtów pamięci)
Tryby adresowania
- niejawne - instrukcja nie ma argumentu, argument jest domyślny
- natychmiastowy - operand jest bajtem bezpośrednio po instrukcji
- względne - (tylko dla rozgałęzienia) bajt po podpisaniu instrukcji (uzupełnienie 2) i określa przesunięcie, które należy dodać do licznika programu, jeśli brana jest gałąź.
0
to lokalizacja następującej instrukcji - bezwzględny - bajt po instrukcji jest adresem argumentu
- zindeksowany - bajt po instrukcji plus
X
(rejestr) to adres argumentu
Instrukcje
Każda instrukcja składa się z kodu operacji (jeden bajt), aw trybach adresowania natychmiastowego , względnego , bezwzględnego i zindeksowanego drugiego bajtu argumentu. Gdy wirtualny procesor wykonuje instrukcję, odpowiednio zwiększa licznik programu (o 1
lub 2
).
Wszystkie pokazane tu kody operacyjne są szesnastkowe.
LDA
- załaduj operand doA
- Kody: natychmiastowe:
00
bezwzględne:02
indeksowane:04
- Flagi:
Z
,N
- Kody: natychmiastowe:
STA
- zapiszA
w operand- Kody: natychmiastowe:
08
bezwzględne:0a
indeksowane:0c
- Kody: natychmiastowe:
LDX
- załaduj operand doX
- Kody: natychmiastowe:
10
bezwzględne:12
indeksowane:14
- Flagi:
Z
,N
- Kody: natychmiastowe:
STX
- zapiszX
w operand- Kody: natychmiastowe:
18
bezwzględne:1a
indeksowane:1c
- Kody: natychmiastowe:
AND
- bitowe oraz zA
i operand naA
- Kody: natychmiastowe:
30
bezwzględne:32
indeksowane:34
- Flagi:
Z
,N
- Kody: natychmiastowe:
ORA
- bitowe lub zA
i operand naA
- Kody: natychmiastowe:
38
bezwzględne:3a
indeksowane:3c
- Flagi:
Z
,N
- Kody: natychmiastowe:
EOR
- bitowe xor (wyłączne lub)A
i operand naA
- Kody: natychmiastowe:
40
bezwzględne:42
indeksowane:44
- Flagi:
Z
,N
- Kody: natychmiastowe:
LSR
- logiczne przesunięcie w prawo, przesunięcie wszystkich bitów argumentu o jedno miejsce w prawo, bit 0 przenosi- Kody: natychmiastowe:
48
bezwzględne:4a
indeksowane:4c
- Flagi:
Z
,N
,C
- Kody: natychmiastowe:
ASL
- przesunięcie arytmetyczne w lewo, przesunięcie wszystkich bitów argumentu o jedno miejsce w lewo, bit 7 przenosi- Kody: natychmiastowe:
50
bezwzględne:52
indeksowane:54
- Flagi:
Z
,N
,C
- Kody: natychmiastowe:
ROR
- obróć w prawo, przesuń wszystkie bity argumentu o jedno miejsce w prawo, przeniesienie przechodzi do bitu 7, bit 0 przechodzi do przeniesienia- Kody: natychmiastowe:
58
bezwzględne:5a
indeksowane:5c
- Flagi:
Z
,N
,C
- Kody: natychmiastowe:
ROL
- obrót w lewo, przesunięcie wszystkich bitów argumentu o jedno miejsce w lewo, przeniesienie przechodzi do bitu 0, bit 7 przechodzi do przeniesienia- Kody: natychmiastowe:
60
bezwzględne:62
indeksowane:64
- Flagi:
Z
,N
,C
- Kody: natychmiastowe:
ADC
- dodaj z przeniesieniem, dodawany jest operand plus przeniesienieA
, przeniesienie jest ustawione na przepełnienie- Kody: natychmiastowe:
68
bezwzględne:6a
indeksowane:6c
- Flagi:
Z
,N
,C
- Kody: natychmiastowe:
INC
- operand inkrementacji o jeden- Kody: natychmiastowe:
78
bezwzględne:7a
indeksowane:7c
- Flagi:
Z
,N
- Kody: natychmiastowe:
DEC
- operand dekrementacji o jeden- Kody: natychmiastowe:
80
bezwzględne:82
indeksowane:84
- Flagi:
Z
,N
- Kody: natychmiastowe:
CMP
- porównajA
z operandem, odejmując operand odA
, zapomnij wynik. Przenoszenie jest kasowane przy niedopełnieniu, w przeciwnym razie ustawione- Kody: natychmiastowe:
88
bezwzględne:8a
indeksowane:8c
- Flagi:
Z
,N
,C
- Kody: natychmiastowe:
CPX
- porównajX
- tak samo jakCMP
dlaX
- Kody: natychmiastowe:
90
bezwzględne:92
indeksowane:94
- Flagi:
Z
,N
,C
- Kody: natychmiastowe:
HLT
- zakończyć- Opcodes: domyślnie:
c0
- Opcodes: domyślnie:
INX
- przyrostX
o jeden- Opcodes: domyślnie:
c8
- Flagi:
Z
,N
- Opcodes: domyślnie:
DEX
- zmniejszenieX
o jeden- Opcodes: domyślnie:
c9
- Flagi:
Z
,N
- Opcodes: domyślnie:
SEC
- ustaw flagę carry- Opcodes: domyślnie:
d0
- Flagi:
C
- Opcodes: domyślnie:
CLC
- wyczyść flagę carry- Opcodes: domyślnie:
d1
- Flagi:
C
- Opcodes: domyślnie:
BRA
- oddział zawsze- Kody: względne:
f2
- Kody: względne:
BNE
- rozgałęzienie, jeśliZ
flaga jest wyczyszczona- Kody: względne:
f4
- Kody: względne:
BEQ
- rozgałęzienie, jeśliZ
ustawiona jest flaga- Kody: względne:
f6
- Kody: względne:
BPL
- rozgałęzienie, jeśliN
flaga jest wyczyszczona- Kody: względne:
f8
- Kody: względne:
BMI
- rozgałęzienie, jeśliN
ustawiona jest flaga- Kody: względne:
fa
- Kody: względne:
BCC
- rozgałęzienie, jeśliC
flaga jest wyczyszczona- Kody: względne:
fc
- Kody: względne:
BCS
- rozgałęzienie, jeśliC
ustawiona jest flaga- Kody: względne:
fe
- Kody: względne:
Kody
Zachowanie maszyny wirtualnej jest niezdefiniowane, jeśli zostanie znaleziony jakikolwiek kod operacji, który nie jest odwzorowany na prawidłową instrukcję z powyższej listy.
Jak na zamówienie Jonathana Allana , to może wybrać swój własny zestaw rozkazy zamiast opcodes podanych w Instrukcji sekcji. Jeśli to zrobisz, musisz dodać pełne mapowanie do kodów operacyjnych użytych powyżej w odpowiedzi.
Mapowanie powinno być plikiem szesnastkowym z parami <official opcode> <your opcode>
, np. Jeśli zastąpisz dwa kody operacyjne:
f4 f5
10 11
Newlines nie mają tutaj znaczenia.
Przypadki testowe (oficjalne kody operacyjne)
// some increments and decrements
pc: 0
ram: 10 10 7a 01 c9 f4 fb
output: 10 20 7a 01 c9 f4 fb
// a 16bit addition
pc: 4
ram: e0 08 2a 02 02 00 6a 02 0a 00 02 01 6a 03 0a 01
output: 0a 0b 2a 02 02 00 6a 02 0a 00 02 01 6a 03 0a 01
// a 16bit multiplication
pc: 4
ram: 5e 01 28 00 10 10 4a 01 5a 00 fc 0d 02 02 d1 6a 21 0a 21 02 03 6a 22 0a 22 52
02 62 03 c9 f8 e6 c0 00 00
output: 00 00 00 00 10 10 4a 01 5a 00 fc 0d 02 02 d1 6a 21 0a 21 02 03 6a 22 0a 22 52
02 62 03 c9 f8 e6 c0 b0 36
Mogę później dodać więcej przypadków testowych.
Referencje i testy
Aby pomóc w przeprowadzaniu własnych eksperymentów, oto niektóre (całkowicie nie golfa) implementacje referencyjne - mogą one wyświetlać informacje o śledzeniu (w tym zdemontowane instrukcje) stderr
i konwertować kody operacyjne podczas działania.
Zalecany sposób uzyskania źródła:
git clone https://github.com/zirias/gvm --branch challenge --single-branch --recurse-submodules
Lub gałąź kasy challenge
i wykonajgit submodule update --init --recursive
odejdź do po klonowaniu, aby uzyskać niestandardowy system kompilacji.
Zbuduj narzędzie z GNU make (po prostu wpisz make
, lub gmake
jeśli w twoim systemie domyślnym make nie jest GNU make).
Zastosowanie :gvm [-s startpc] [-h] [-t] [-c convfile] [-d] [-x] <initial_ram
-s startpc
- początkowy licznik programu, domyślnie0
-h
- dane wejściowe są szesnastkowe (inaczej binarne)-t
- śledzenie wykonania dostderr
-c convfile
- konwertuj kody operacyjne zgodnie z mapowaniem podanym wconvfile
-d
- zrzuć wynikową pamięć jako dane binarne-x
- zrzuć wynikową pamięć jako hexinitial_ram
- początkowa zawartość pamięci RAM, szesnastkowa lub binarna
Uwaga: funkcja konwersji nie powiedzie się w programach, które modyfikują kody operacyjne podczas działania.
Oświadczenie: powyższe zasady i specyfikacje są autorytatywne dla wyzwania, a nie to narzędzie. Dotyczy to w szczególności funkcji konwersji kodu operacyjnego. Jeśli uważasz, że narzędzie przedstawione tutaj ma błąd w specyfikacji, zgłoś to w komentarzu :)
źródło
BRA
(„gałąź zawsze”) nie wprowadza gałęzi w przepływie sterowania, czy nie powinno się jej wywoływaćJMP
?BRA
istnieje w późniejszych projektach układów (6502 nie ma takiej instrukcji), takich jak 65C02 i MC 68000.JMP
istnieje również. Różnica polega na tym, żeBRA
wykorzystuje adresowanie względne iJMP
wykorzystuje adresowanie bezwzględne. Po prostu zastosowałem się do tych projektów - nie brzmi to wcale logicznie;)Odpowiedzi:
C (gcc) ,
1381133812551073 bajtówOgromna poprawa dzięki CeCatcat i Rogem.
Wypróbuj online!
Wiele definicji przeniesiono do flag kompilatora.
Objaśnienie (BARDZO niepoddane golfowi):
źródło
00
bajtów może jednak nieco naginać reguły ... Przyznaję, że nie próbowałem analizować tego kodu ... czy mógłbyś zapisać bajty robiące operacje we / wy w postaci binarnej zamiast szesnastkowej? Pozwolą na to przepisy :)APL (Dyalog Classic) ,
397332330 bajtówdzięki @ Adám za -8 bajtów
Wypróbuj online!
źródło
f←
?C (gcc) ,
487,480,463,452,447, 438 bajtówWykorzystuje to mapowanie instrukcji . Aktualizacja instrukcji straciła 9 bajtów, a potencjalnie więcej w przyszłości. Zwraca przez modyfikację pamięci wskazanej przez pierwszy argument (
M
). Dzięki @ceilingcat za golenie niektórych bajtów.Musi być skompilowany z flagami
-DO=*o -DD=*d -DI(e,a,b)=if(e){a;}else{b;} -Du="unsigned char"
(już zawartymi w bajtach).Wypróbuj online!
Preprocesor
Te dwa stanowią krótszy sposób na usunięcie odniesienia do wskaźników.
Zmniejsz liczbę bajtów potrzebną do if-els i deklaracji typu.
Kod
Poniżej znajduje się czytelna dla człowieka wersja kodu, z rozszerzonymi dyrektywami preprocesora i zmienionymi nazwami zmiennych w celu zapewnienia czytelności.
Instrukcje
Instrukcje mają następującą strukturę:
Bity 6-7 wskazują na istnienie instrukcji (
00
zerowy,01
jednoargumentowy,10
binarny,11
binarny)Bity 0-2 określają operand (y):
R=0
wybieraA
iR=1
wybieraX
.OP=00
wykorzystuje rejestr jako operand,OP=01
wybiera operand bezpośredni,OP=10
wybiera operand bezwzględny iOP=11
wybiera indeksowany indeks.X
), nawet jeśli normalnie nie można ich użyć według specyfikacji. Na przykładINC A
,ADC X, 10
aASL X
wszystkie prace.Bity 3-5 określają warunek rozgałęzienia: posiadanie jednego z bitów wskazuje, którą flagę przetestować (bit 3-> C, bit 4-> N, bit 5-> Z). Jeśli ustawiony jest tylko jeden bit, instrukcja sprawdza flagę zestawu. Aby przetestować flagę nieustawioną, weź uzupełnienie bitów. Na przykład
110
testy dla nieuzbrojonego przenoszenia i001
dla ustawionego przenoszenia.111
i000
gałąź zawsze.Możesz także rozgałęzić się do przesunięcia adresu zapisanego w rejestrze, umożliwiając pisanie funkcji, lub możesz użyć standardowych trybów indeksowania.
OP=01
zachowuje się jak gałąź specyfikacji.źródło
JavaScript (ES6), 361 bajtów
Pobiera dane wejściowe jako
(memory)(program_counter)
, gdziememory
jestUint8Array
. Wyjście poprzez modyfikację tej tablicy.Uwaga: Kod jest skompresowany za pomocą RegPack i zawiera wiele znaków niedrukowalnych, z których wszystkie są zastępowane w powyższej reprezentacji źródła.
Wypróbuj online!
Mapowanie kodów operacyjnych i przypadki testowe
Maszyna wirtualna używa tego mapowania opcode .
Poniżej znajdują się przetłumaczone przypadki testowe wraz z oczekiwanymi wynikami.
Przypadek testowy nr 1
Oczekiwany wynik:
Przypadek testowy nr 2
Oczekiwany wynik:
Przypadek testowy nr 3
Oczekiwany wynik:
Rozpakowane i sformatowane
Ponieważ kod jest kompresowany za pomocą algorytmu, który zastępuje często powtarzane ciągi pojedynczym znakiem, bardziej efektywne jest stosowanie tych samych bloków kodu w kółko niż definiowanie i wywoływanie funkcji pomocniczych lub przechowywanie wyników pośrednich (takich jak
M[A]
) w dodatkowych zmiennych.źródło
o = ...
wiersz jest wykonywany dla każdej instrukcji, może to mieć „niezamierzone kody operacyjne”?c = M[A] >> 7 & 1
<- czy&1
naprawdę jest tu potrzebny?Uint8Array
rzeczywiście po prostu zawiera taką listę bajtów. Jeśli więc umieszczenie bajtów w ciągu szesnastkowym jest akceptowalnym sposobem reprezentowania danych wejściowych, dlaczego umieszczanie ich w obiekcie kontenerowym powinno być zabronione ...PHP, 581585
555532 bajtów (nie-konkurencyjne)pobiera kody PC i OP jako 10 liczb całkowitych bazowych z argumentów wiersza poleceń,
drukuje pamięć jako listę
[base 10 address] => base 10 value
.Nie zostało to jeszcze dokładnie przetestowane ; ale jest awaria .
There's mapie kodu i here's przegląd dla mojego mapowania:
uwaga dodatkowa:
kod
24
skutkujeBNV
(gałąź nigdy = 2 bajtyNOP
);04
,08
,0C
Są aliasyINX
,CLC
aSEC
przede wszystko
3F
jest albo dwa bajtNOP
lub aliasem instrukcji jednomodowych.źródło