Latar Belakang
Saya suka chip 6502 8-bit lama saya. Bahkan menyenangkan untuk menyelesaikan beberapa tantangan di sini di PPCG dalam kode mesin 6502. Tetapi beberapa hal yang seharusnya sederhana (seperti, membaca data atau output ke stdout) tidak perlu rumit untuk dilakukan dalam kode mesin. Jadi ada ide kasar di pikiran saya: Ciptakan mesin virtual 8-bit saya sendiri yang terinspirasi oleh 6502, tetapi dengan desain yang dimodifikasi agar lebih dapat digunakan untuk tantangan. Mulai menerapkan sesuatu, saya menyadari ini mungkin tantangan yang bagus jika desain VM dikurangi seminimal mungkin :)
Tugas
Menerapkan mesin virtual 8-bit yang sesuai dengan spesifikasi berikut. Ini adalah kode-golf , sehingga implementasi dengan byte paling sedikit menang.
Memasukkan
Implementasi Anda harus mengambil input berikut:
Byte tunggal yang tidak ditandatangani
pc
, ini adalah penghitung program awal (alamat di memori tempat VM memulai eksekusi,0
berbasis)Daftar byte dengan panjang
256
entri maksimum , ini adalah RAM untuk mesin virtual (dengan konten awalnya)
Anda dapat mengambil input ini dalam format apa pun yang masuk akal.
Keluaran
Daftar byte yang merupakan isi terakhir RAM setelah VM berakhir (lihat di bawah). Anda dapat berasumsi bahwa Anda hanya mendapatkan input yang pada akhirnya akan berakhir. Format apa pun yang masuk akal diizinkan.
CPU virtual
CPU virtual memiliki
- penghitung program 8-bit,
- register akumulator 8-bit disebut
A
dan - register indeks 8-bit disebut
X
.
Ada tiga bendera status:
Z
- bendera nol ditetapkan setelah beberapa operasi menghasilkan0
N
- Bendera negatif ditetapkan setelah beberapa operasi menghasilkan angka negatif (iow sedikit 7 dari hasil ditetapkan)C
- flag carry diatur dengan penambahan dan pergeseran untuk bit "hilang" dari hasilnya
Setelah mulai, semua bendera dibersihkan, penghitung program diatur ke nilai yang diberikan dan isi dari A
dan X
tidak ditentukan.
Nilai 8-bit mewakili keduanya
- sebuah unsigned integer dalam kisaran
[0..255]
- a ditandatangani integer, komplemen 2, dalam kisaran
[-128..127]
tergantung pada konteksnya. Jika suatu operasi over atau underflow, nilainya membungkus (dan dalam hal penambahan, flag carry dipengaruhi).
Penghentian
Mesin virtual berakhir ketika
- Sebuah
HLT
instruksi tercapai - Alamat memori yang tidak ada diakses
- Penghitung program berjalan di luar memori (perhatikan itu tidak membungkus bahkan jika VM diberikan 256 byte penuh memori)
Mode adressing
- implisit - instruksi tidak memiliki argumen, operan tersirat
- segera - operan adalah byte langsung setelah instruksi
- relatif - (hanya untuk percabangan) byte setelah instruksi ditandatangani (komplemen 2's) dan menentukan offset untuk ditambahkan ke penghitung program jika cabang diambil.
0
adalah lokasi instruksi berikut - absolut - byte setelah instruksi adalah alamat operan
- diindeks - byte setelah instruksi plus
X
(register) adalah alamat operan
Instruksi
Setiap instruksi terdiri dari opcode (satu byte) dan, dalam mode pengalamatan segera , relatif , absolut dan diindeks byte argumen kedua. Ketika CPU virtual menjalankan instruksi, itu menambah penghitung program yang sesuai (oleh 1
atau2
).
Semua opcode yang ditampilkan di sini adalah dalam hex.
LDA
- muat operan keA
- Opcode: langsung:,
00
absolut02
:, diindeks:04
- Flags:
Z
,N
- Opcode: langsung:,
STA
- simpanA
ke dalam operan- Opcode: langsung:,
08
absolut0a
:, diindeks:0c
- Opcode: langsung:,
LDX
- muat operan keX
- Opcode: langsung:,
10
absolut12
:, diindeks:14
- Flags:
Z
,N
- Opcode: langsung:,
STX
- simpanX
ke dalam operan- Opcode: langsung:,
18
absolut1a
:, diindeks:1c
- Opcode: langsung:,
AND
- bitwise dan ofA
dan operan keA
- Opcode: langsung:,
30
absolut32
:, diindeks:34
- Flags:
Z
,N
- Opcode: langsung:,
ORA
- bitwise atau dariA
dan operan keA
- Opcode: langsung:,
38
absolut3a
:, diindeks:3c
- Flags:
Z
,N
- Opcode: langsung:,
EOR
- bitwise xor (eksklusif atau) dariA
dan operan keA
- Opcode: langsung:,
40
absolut42
:, diindeks:44
- Flags:
Z
,N
- Opcode: langsung:,
LSR
- Pergeseran logis ke kanan, geser semua bit operan satu tempat ke kanan, bit 0 pergi untuk dibawa- Opcode: langsung:,
48
absolut4a
:, diindeks:4c
- Flags:
Z
,N
,C
- Opcode: langsung:,
ASL
- Aritmatika bergeser ke kiri, menggeser semua bit operan satu tempat ke kiri, bit 7 pergi untuk membawa- Opcode: langsung:,
50
absolut52
:, diindeks:54
- Flags:
Z
,N
,C
- Opcode: langsung:,
ROR
- Putar ke kanan, geser semua bit operan satu tempat ke kanan, carry pergi ke bit 7, bit 0 pergi ke carry- Opcode: langsung:,
58
absolut5a
:, diindeks:5c
- Flags:
Z
,N
,C
- Opcode: langsung:,
ROL
- Putar ke kiri, geser semua bit operan satu tempat ke kiri, bawa pergi ke bit 0, bit 7 pergi untuk membawa- Opcode: langsung:,
60
absolut62
:, diindeks:64
- Flags:
Z
,N
,C
- Opcode: langsung:,
ADC
- tambahkan dengan carry, operan plus carry ditambahkan keA
, carry diset pada overflow- Opcode: langsung:,
68
absolut6a
:, diindeks:6c
- Flags:
Z
,N
,C
- Opcode: langsung:,
INC
- operan kenaikan satu- Opcode: langsung:,
78
absolut7a
:, diindeks:7c
- Flags:
Z
,N
- Opcode: langsung:,
DEC
- operan decrement oleh satu- Opcode: langsung:,
80
absolut82
:, diindeks:84
- Flags:
Z
,N
- Opcode: langsung:,
CMP
- bandingkanA
dengan operan dengan mengurangi operan dariA
, lupakan hasil. Carry dibersihkan saat underflow, atur sebaliknya- Opcode: langsung:,
88
absolut8a
:, diindeks:8c
- Flags:
Z
,N
,C
- Opcode: langsung:,
CPX
- bandingkanX
- sama sepertiCMP
untukX
- Opcode: langsung:,
90
absolut92
:, diindeks:94
- Flags:
Z
,N
,C
- Opcode: langsung:,
HLT
-- mengakhiri- Opcode: tersirat:
c0
- Opcode: tersirat:
INX
- selisihX
satu- Opcode: tersirat:
c8
- Flags:
Z
,N
- Opcode: tersirat:
DEX
- penguranganX
satu per satu- Opcode: tersirat:
c9
- Flags:
Z
,N
- Opcode: tersirat:
SEC
- atur flag carry- Opcode: tersirat:
d0
- Bendera:
C
- Opcode: tersirat:
CLC
- Membawa bendera yang jelas- Opcode: tersirat:
d1
- Bendera:
C
- Opcode: tersirat:
BRA
- cabang selalu- Opcode: relatif:
f2
- Opcode: relatif:
BNE
- Cabang jikaZ
bendera dibersihkan- Opcode: relatif:
f4
- Opcode: relatif:
BEQ
- cabang jikaZ
flag diatur- Opcode: relatif:
f6
- Opcode: relatif:
BPL
- Cabang jikaN
bendera dibersihkan- Opcode: relatif:
f8
- Opcode: relatif:
BMI
- cabang jikaN
flag diatur- Opcode: relatif:
fa
- Opcode: relatif:
BCC
- Cabang jikaC
bendera dibersihkan- Opcode: relatif:
fc
- Opcode: relatif:
BCS
- cabang jikaC
flag diatur- Opcode: relatif:
fe
- Opcode: relatif:
Opcode
Perilaku VM tidak terdefinisi jika ada opcode ditemukan yang tidak memetakan ke instruksi yang valid dari daftar di atas.
Sesuai permintaan Jonathan Allan , Anda dapat memilih set opcodes Anda sendiri alih-alih opcode yang diperlihatkan di bagian Instruksi . Jika Anda melakukannya, Anda harus melakukannya menambahkan pemetaan penuh ke opcodes yang digunakan di atas dalam jawaban Anda.
Pemetaan harus berupa file hex berpasangan <official opcode> <your opcode>
, misalnya jika Anda mengganti dua opcode:
f4 f5
10 11
Baris baru tidak masalah di sini.
Test case (opcodes resmi)
// 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
Saya mungkin menambahkan lebih banyak testcases nanti.
Referensi dan pengujian
Untuk membantu dengan eksperimen sendiri, berikut ini beberapa implementasi referensi (yang sama sekali tidak golf) - ia dapat menampilkan informasi penelusuran (termasuk instruksi yang dibongkar) kestderr
dan mengonversi opcode saat berjalan.
Cara yang disarankan untuk mendapatkan sumber:
git clone https://github.com/zirias/gvm --branch challenge --single-branch --recurse-submodules
Atau checkout cabang challenge
dan lakukan agit submodule update --init --recursive
setelah kloning, untuk mendapatkan sistem build kustom saya.
Bangun alat dengan GNU make (ketik saja make
, atau gmake
jika di sistem Anda, make default bukan GNU make).
Penggunaan :gvm [-s startpc] [-h] [-t] [-c convfile] [-d] [-x] <initial_ram
-s startpc
- penghitung program awal, default ke0
-h
- input dalam hex (jika tidak biner)-t
- lacak eksekusi kestderr
-c convfile
- Mengonversi opcodes sesuai dengan pemetaan yang diberikan diconvfile
-d
- dump memori yang dihasilkan sebagai data biner-x
- dump memori yang dihasilkan sebagai hexinitial_ram
- Konten RAM awal, baik hex atau biner
Perhatikan bahwa fitur konversi akan gagal pada program yang memodifikasi opcodes saat menjalankan.
Penafian: Aturan dan spesifikasi di atas adalah otoritatif untuk tantangan, bukan alat ini. Ini terutama berlaku untuk fitur konversi opcode. Jika menurut Anda alat yang disajikan di sini memiliki bug yang terkait dengan spesifikasi, silakan laporkan dalam komentar :)
sumber
BRA
("cabang selalu") tidak memperkenalkan cabang dalam aliran kontrol, bukankah seharusnya disebutJMP
?BRA
ada dalam desain chip kemudian (6502 tidak memiliki instruksi seperti itu) seperti 65C02 dan MC 68000.JMP
ada juga. Perbedaannya adalah yangBRA
menggunakan pengalamatan relatif danJMP
menggunakan pengalamatan absolut. Jadi, saya hanya mengikuti desain ini - memang, itu tidak terdengar masuk akal;)Jawaban:
C (gcc) ,
1381133812551073 bytePeningkatan besar berkat ceilingcat dan Rogem.
Cobalah online!
Banyak definisi yang dipindahkan ke flag compiler.
Penjelasan (SANGAT tidak diserang):
sumber
00
byte Anda mungkin sedikit membengkokkan aturannya ... Saya akui saya tidak mencoba menganalisis kode ini ... mungkin Anda bisa menyimpan byte melakukan I / O dalam biner, bukan hex? Akan diizinkan oleh aturan :)APL (Dyalog Classic) ,
397332330 byteterima kasih @ Adm untuk -8 byte
Cobalah online!
sumber
f←
?C (gcc) ,
487,480,463,452,447, 438 byteGunakan pemetaan instruksi ini . Pembaruan untuk petunjuk berkurang 9 byte, dan berpotensi lebih banyak di masa depan. Mengembalikan dengan memodifikasi memori yang ditunjukkan oleh argumen pertama (
M
). Terima kasih kepada @ceilingcat untuk mencukur beberapa byte.Harus dikompilasi dengan flag
-DO=*o -DD=*d -DI(e,a,b)=if(e){a;}else{b;} -Du="unsigned char"
(sudah termasuk dalam bytes).Cobalah online!
Preprosesor
Keduanya menyediakan cara yang lebih pendek untuk merujuk referensi.
Kurangi jumlah byte yang dibutuhkan untuk if-elses dan ketik deklarasi.
Kode
Di bawah ini adalah versi kode yang dapat dibaca manusia, dengan arahan preprosesor diperluas, dan variabel diubah namanya agar mudah dibaca.
Instruksi
Petunjuk disusun sebagai berikut:
Bits 6-7 menunjukkan arity instruksi (
00
Nullary,01
Unary,10
Binary,11
Binary)Bit 0-2 menentukan operan:
R=0
memilihA
danR=1
memilihX
.OP=00
menggunakan register sebagai operan,OP=01
memilih operan langsung,OP=10
memilih operan absolut danOP=11
memilih operan yang diindeks.X
) bahkan ketika mereka biasanya tidak dapat digunakan sesuai spesifikasi. MisalnyaINC A
,ADC X, 10
danASL X
semua pekerjaan.Bits 3-5 menentukan kondisi untuk percabangan: memiliki salah satu bit mengindikasikan flag mana yang akan diuji (bit 3-> C, bit 4-> N, bit 5-> Z). Jika hanya satu bit yang diatur, instruksi akan menguji flag yang ditetapkan. Untuk menguji flag yang belum disetel, ambil komplemen bit. Misalnya
110
tes untuk carry yang tidak disetel dan001
untuk carry yang diset.111
dan000
cabang selalu.Anda juga dapat bercabang ke offset alamat yang disimpan dalam register, memungkinkan Anda untuk menulis fungsi, atau Anda dapat menggunakan mode pengindeksan standar.
OP=01
berperilaku seperti cabang spesifikasi.sumber
JavaScript (ES6), 361 byte
Mengambil input sebagai
(memory)(program_counter)
, di manamemory
anUint8Array
. Output dengan memodifikasi array ini.NB: Kode ini dikompres dengan RegPack dan berisi banyak karakter yang tidak patut, yang semuanya lolos dalam representasi sumber di atas.
Cobalah online!
Pemetaan opcode dan uji kasus
Menggunakan mesin virtual pemetaan opcode ini .
Di bawah ini adalah test case yang diterjemahkan, bersama dengan output yang diharapkan.
Uji kasus # 1
Output yang diharapkan:
Uji kasus # 2
Output yang diharapkan:
Uji kasus # 3
Output yang diharapkan:
Dibongkar dan diformat
Karena kode dikompresi dengan algoritma yang menggantikan string yang sering diulang dengan karakter tunggal, lebih efisien untuk menggunakan blok kode yang sama berulang kali daripada mendefinisikan dan menjalankan fungsi pembantu, atau menyimpan hasil antara (seperti
M[A]
) dalam variabel tambahan.sumber
o = ...
baris ini dieksekusi untuk setiap instruksi, ini mungkin memiliki "opcodes yang tidak diinginkan"?c = M[A] >> 7 & 1
<- apa yang&1
benar - benar dibutuhkan di sini?Uint8Array
memang hanya merangkum daftar byte tersebut. Jadi, jika menempatkan byte dalam string hex adalah cara yang dapat diterima untuk mewakili input, mengapa harus meletakkannya dalam objek kontainer dilarang ...PHP,
581 585 555532 byte (tidak bersaing)mengambil kode OP dan PC sebagai basis 10 integer dari argumen baris perintah,
mencetak memori sebagai daftar
[base 10 address] => base 10 value
.Ini belum diuji secara menyeluruh ; tapi ada gangguan .
Ada peta kode dan inilah ikhtisar untuk pemetaan saya:
catatan samping: hasil
kode
24
dalamBNV
(cabang tidak pernah = 2 byteNOP
);04
,08
,0C
Adalah alias untukINX
,CLC
danSEC
dan apa pun di atas
3F
adalah baik dua byteNOP
atau alias untuk petunjuk mode single.sumber