Pendahuluan
Untuk proyek baru, saya perlu mengekstraksi data level dari video game klasik
Super Mario Bros (SMB) 1985. Lebih khusus lagi, saya ingin mengekstraksi latar belakang grafis dari setiap level permainan tanpa antarmuka, memindahkan sprite, dll.
Tentu saja, saya hanya bisa merekatkan gambar dari permainan dan, mungkin, mengotomatiskan proses menggunakan teknik visi mesin. Tetapi bagi saya tampaknya lebih menarik metode yang dijelaskan di bawah ini, yang memungkinkan Anda untuk menjelajahi elemen-elemen level yang tidak dapat diperoleh menggunakan screenshot.
Pada tahap pertama proyek, kita akan mempelajari bahasa assembler 6502 dan emulator yang ditulis dengan Python. Kode sumber lengkap tersedia di
sini .
Analisis kode sumber
Membalikkan rekayasa program apa pun jauh lebih sederhana jika Anda memiliki kode sumbernya, dan kami memiliki sumber SMB dalam bentuk
17 ribu baris kode assembler 6502 (prosesor NES) yang diterbitkan oleh doppelganger. Karena Nintendo tidak pernah merilis rilis sumber resmi, kode tersebut dibuat dengan membongkar kode mesin SMB, dengan susah payah menguraikan makna setiap bagian, menambahkan komentar dan nama simbol yang bermakna.
Setelah melakukan pencarian cepat pada file, saya menemukan sesuatu yang mirip dengan data level yang kami butuhkan:
;level 1-1
L_GroundArea6:
.db $50, $21
.db $07, $81, $47, $24, $57, $00, $63, $01, $77, $01
.db $c9, $71, $68, $f2, $e7, $73, $97, $fb, $06, $83
.db $5c, $01, $d7, $22, $e7, $00, $03, $a7, $6c, $02
.db $b3, $22, $e3, $01, $e7, $07, $47, $a0, $57, $06
.db $a7, $01, $d3, $00, $d7, $01, $07, $81, $67, $20
.db $93, $22, $03, $a3, $1c, $61, $17, $21, $6f, $33
.db $c7, $63, $d8, $62, $e9, $61, $fa, $60, $4f, $b3
.db $87, $63, $9c, $01, $b7, $63, $c8, $62, $d9, $61
.db $ea, $60, $39, $f1, $87, $21, $a7, $01, $b7, $20
.db $39, $f1, $5f, $38, $6d, $c1, $af, $26
.db $fdJika Anda tidak terbiasa dengan assembler, maka saya akan menjelaskan: semua ini hanya berarti "memasukkan set byte seperti itu ke dalam program yang dikompilasi, dan kemudian mengizinkan bagian lain dari program untuk merujuknya menggunakan simbol
L_GroundArea6 ". Anda bisa mengambil fragmen ini sebagai array di mana setiap elemen adalah byte.
Hal pertama yang dapat Anda perhatikan adalah bahwa volume data sangat kecil (sekitar 100 byte). Oleh karena itu, kami mengecualikan semua jenis pengkodean, memungkinkan Anda untuk secara acak menempatkan blok pada level. Setelah mencari sedikit, saya menemukan bahwa data ini dibaca (setelah beberapa operasi pengalamatan tidak langsung) di
AreaParserCore .
RowOfBricks ini, pada gilirannya, memanggil banyak
RowOfBricks lainnya, yang pada akhirnya meminta
RowOfBricks khusus untuk setiap jenis objek yang diperbolehkan dalam adegan (misalnya,
StaircaseObject ,
VerticalPipe ,
RowOfBricks ):
Grafik panggilan AreaParserCore untuk AreaParserCoreProsedur menulis ke
MetatileBuffer : bagian memori 13-byte, yang merupakan satu kolom blok di level, masing-masing byte mewakili blok yang terpisah. Metatile adalah blok 16x16 dari mana latar belakang gim SMB dibuat:
Tingkat dengan persegi panjang mengelilingi metatileMereka disebut meta-file, karena masing-masing terdiri dari empat petak 8x8-piksel, tetapi lebih dari itu di bawah ini.
Fakta bahwa dekoder bekerja dengan objek yang telah ditentukan menjelaskan ukuran kecil level: level data harus merujuk hanya pada jenis objek dan lokasinya, misalnya, "posisikan pipa pada titik (20, 16), sejumlah blok pada titik (10, 5), ... ". Namun, ini berarti bahwa dibutuhkan banyak kode untuk mengubah data level mentah menjadi file meta.
Mem-Porting jumlah kode ini untuk membuat unpacker level Anda sendiri akan memakan waktu terlalu banyak, jadi mari kita coba pendekatan yang berbeda.
py65emu
Jika kami memiliki antarmuka antara Python dan bahasa assembler 6502, kita bisa memanggil subprocedure
AreaParserCore untuk setiap kolom level, dan kemudian menggunakan Python yang lebih dimengerti untuk mengubah informasi blok menjadi gambar yang diinginkan.
Kemudian
py65emu muncul di tempat kejadian - sebuah emulator 6502 ringkas dengan antarmuka Python. Inilah cara konfigurasi memori yang sama dikonfigurasi di py65emu seperti pada NES:
from py65emu.cpu import CPU from py65emu.mmu import MMU
Setelah itu, kita dapat menjalankan instruksi individual menggunakan metode
cpu.step() , memeriksa memori menggunakan
mmu.read() , mempelajari register mesin menggunakan
cpu.ra ,
cpu.r.pc , dll. Selain itu, kita dapat menulis ke memori menggunakan
mmu.write() .
Perlu dicatat bahwa ini hanyalah emulator prosesor NES: tidak meniru perangkat keras lain, seperti PPU (Picture Processing Unit), sehingga tidak dapat digunakan untuk meniru seluruh permainan. Namun, itu seharusnya cukup untuk memanggil subprocedure parsing, karena tidak menggunakan perangkat perangkat keras lain kecuali CPU dan memori.
Rencananya adalah untuk mengkonfigurasi CPU seperti yang ditunjukkan di atas, dan kemudian untuk setiap kolom level, inisialisasi partisi memori dengan nilai input yang diperlukan untuk
AreaParserCore , panggil
AreaParserCore , dan kemudian baca kembali data kolom. Setelah menyelesaikan operasi ini, kami menggunakan Python untuk mengumpulkan hasilnya menjadi gambar yang sudah jadi.
Tetapi sebelum itu, kita perlu mengkompilasi daftar dalam bahasa assembly ke dalam kode mesin.
x816
Seperti ditunjukkan dalam kode sumber, assembler dikompilasi menggunakan x816. x816 adalah assembler MS-DOS 6502 yang digunakan oleh komunitas
homebrew untuk peretas NES dan ROM. Ini berfungsi dengan baik di
DOSBox .
Bersamaan dengan ROM program, yang diperlukan untuk py65emu, assembler x816 membuat file karakter yang memetakan karakter ke lokasi mereka dalam memori di ruang alamat CPU. Berikut cuplikan file:
AREAPARSERCORE = $0093FC ; <> 37884, statement #3154
AREAPARSERTASKCONTROL = $0086E6 ; <> 34534, statement #1570
AREAPARSERTASKHANDLER = $0092B0 ; <> 37552, statement #3035
AREAPARSERTASKNUM = $00071F ; <> 1823, statement #141
AREAPARSERTASKS = $0092C8 ; <> 37576, statement #3048Di sini kita melihat bahwa fungsi
AreaParserCore dalam kode sumber dapat diakses di
0x93fc .
Untuk kenyamanan, saya menulis parser file simbol yang cocok dengan nama dan alamat simbol:
sym_file = SymbolFile('SMBDIS.SYM') print("0x{:x}".format(sym_file['AREAPARSERCORE']))
Sub-prosedur
Seperti yang dinyatakan dalam rencana di atas, kami ingin mempelajari cara memanggil subprocedure
AreaParserCore dari Python.
Untuk memahami mekanisme sub-prosedur, mari kita periksa sub-prosedur singkat dan tantangan terkait:
WritePPUReg1: sta PPU_CTRL_REG1 ; A 1 PPU sta Mirror_PPU_CTRL_REG1 ; rts ... jsr WritePPUReg1
jsr (lompat ke subrutin, “lompat ke subrutin”)
jsr register PC ke stack dan memberikannya nilai alamat yang
WritePPUReg1 oleh
WritePPUReg1 . Register PC memberitahu prosesor alamat instruksi berikutnya untuk memuat, sehingga instruksi berikutnya dijalankan setelah instruksi
jsr adalah baris pertama dari
WritePPUReg1 .
Pada akhir subrutin, pernyataan
rts dieksekusi (kembali dari subrutin, "kembali dari subrutin"). Perintah ini menghilangkan nilai yang tersimpan dari tumpukan dan menyimpannya dalam register PC, yang memaksa CPU untuk menjalankan instruksi mengikuti panggilan
jsr .
Fitur hebat dari sub-prosedur adalah bahwa Anda dapat membuat panggilan inline, yaitu, panggilan sub-prosedur dalam sub-prosedur. Alamat pengembalian akan didorong ke tumpukan dan muncul dalam urutan yang benar, dengan cara yang sama seperti dengan pemanggilan fungsi dalam bahasa tingkat tinggi.
Berikut adalah kode untuk menjalankan subrutin dari Python:
def execute_subroutine(cpu, addr): s_before = cpu.rs cpu.JSR(addr) while cpu.rs != s_before: cpu.step() execute_subroutine(cpu, sym_file['AREAPARSERCORE'])
Kode menyimpan nilai saat ini dari register penunjuk tumpukan, mengemulasi panggilan
jsr , dan kemudian mengeksekusi instruksi sampai tumpukan kembali ke ketinggian aslinya, yang terjadi hanya setelah kembalinya dari
jsr -
jsr pertama. Ini akan berguna, karena sekarang kita memiliki cara untuk secara langsung memanggil 6502 subrutin dari Python.
Namun, kami lupa sesuatu: bagaimana cara melewatkan nilai input untuk sub-prosedur ini? Kita perlu memberi tahu prosedur level mana yang ingin kita render dan kolom mana yang perlu kita uraikan.
Tidak seperti fungsi dalam bahasa tingkat tinggi, subrutin bahasa assembly 6502 tidak dapat menerima data input yang ditentukan secara eksplisit. Sebagai gantinya, input ditransmisikan dengan menentukan lokasi memori di suatu tempat sebelum panggilan, yang kemudian dibaca di dalam panggilan sub-prosedur. Mengingat ukuran
AreaParserCore , rekayasa balik input yang diperlukan dengan hanya melihat kode sumber akan sangat kompleks dan rawan kesalahan.
Valgrind untuk NES?
Untuk menemukan cara menentukan nilai input
AreaParserCore , saya menggunakan alat
memcheck untuk Valgrind sebagai contoh. Memcheck mengenali operasi akses ke memori yang tidak diinisialisasi dengan menyimpan memori bayangan secara paralel dengan setiap fragmen dari memori yang dialokasikan sebenarnya. Memori bayangan merekam apakah perekaman dilakukan ke memori nyata yang sesuai. Jika program membaca ke alamat yang tidak pernah ditulisnya, maka kesalahan memori yang tidak diinisialisasi akan muncul. Kita bisa menjalankan
AreaParserCore dengan alat yang memberi tahu kita apa input yang perlu ditetapkan sebelum menjalankan subprocedure.
Sebenarnya, menulis versi memcheck sederhana untuk py65emu sangat mudah:
def format_addr(addr): try: symbol_name = sym_file.lookup_address(addr) s = "0x{:04x} ({}):".format(addr, symbol_name) except KeyError: s = "0x{:04x}:".format(addr) return s class MemCheckMMU(MMU): def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self._uninitialized = array.array('B', [1] * 2048) def read(self, addr): val = super().read(addr) if addr < 2048: if self._uninitialized[addr]: print("Uninitialized read! {}".format(format_addr(addr))) return val def write(self, addr, val): super().write(addr, val) if addr < 2048: self._uninitialized[addr] = 0
Di sini kami membungkus unit manajemen memori (MMU) py65emu. Kelas ini berisi larik
_uninitialized , elemen yang memberi tahu kami apakah pernah ditulis ke byte yang sesuai dari RAM yang ditiru. Jika terjadi pembacaan yang tidak diinisialisasi, alamat operasi pembacaan yang tidak valid dan nama karakter yang sesuai akan ditampilkan.
Berikut ini adalah hasil dari MMU yang
execute_subroutine(sym_file['AREAPARSERCORE']) ketika memanggil
execute_subroutine(sym_file['AREAPARSERCORE']) :
Uninitialized read! 0x0728 (BACKLOADINGFLAG):
Uninitialized read! 0x0742 (BACKGROUNDSCENERY):
Uninitialized read! 0x0741 (FOREGROUNDSCENERY):
Uninitialized read! 0x074e (AREATYPE):
Uninitialized read! 0x075f (WORLDNUMBER):
Uninitialized read! 0x0743 (CLOUDTYPEOVERRIDE):
Uninitialized read! 0x0727 (TERRAINCONTROL):
Uninitialized read! 0x0743 (CLOUDTYPEOVERRIDE):
Uninitialized read! 0x074e (AREATYPE):
...Dengan melihat kode, Anda dapat melihat bahwa banyak dari nilai-nilai ini ditetapkan oleh subprocedure
InitializeArea , jadi mari kita jalankan skrip lagi, memanggil fungsi ini terlebih dahulu. Mengulangi proses ini, kami sampai pada urutan panggilan berikut, yang hanya membutuhkan nomor dunia dan nomor area:
mmu.write(sym_file['WORLDNUMBER'], 0)
Kode menulis 48 kolom pertama dari tingkat World 1-1 ke
metatile_data , menggunakan subprocedure
IncrementColumnPos untuk meningkatkan variabel internal yang diperlukan untuk melacak kolom saat ini.
Dan di sini adalah isi dari
metatile_data ditumpangkan pada screenshot dari game (byte dengan nilai 0 tidak ditampilkan):
Jelas,
metatile_data dengan jelas cocok dengan informasi latar belakang.
Grafik Meta
(Untuk melihat hasil akhir, Anda dapat langsung melanjutkan ke bagian "Menghubungkan semuanya bersama".)
Sekarang mari kita cari tahu cara mengubah jumlah file meta yang diterima menjadi gambar nyata. Langkah-langkah yang dijelaskan di bawah ini diciptakan dengan menganalisis sumber dan membaca dokumentasi dengan
Wiki Nesdev yang menakjubkan.
Untuk memahami cara membuat setiap metatile, pertama-tama kita perlu berbicara tentang palet warna NES. PPU konsol NES umumnya dapat membuat 64 warna berbeda, tetapi hitam digandakan beberapa kali (lihat
Nesdev untuk
detailnya ):
Setiap level Mario hanya dapat menggunakan 10 dari 64 warna ini untuk latar belakang, dibagi menjadi 4 palet empat warna; Warna pertama selalu sama. Berikut adalah empat palet untuk World 1-1:
Sekarang mari kita lihat contoh biner dari nomor file meta. Berikut adalah nomor metatile ubin batu retak, yang merupakan tanah tingkat Dunia 1-1:
Indeks palet memberi tahu kita palet mana yang akan digunakan saat me-render metatile (dalam kasus kami, palet 1). Indeks palet juga merupakan indeks dari dua array berikut:
MetatileGraphics_Low:
.db <Palette0_MTiles, <Palette1_MTiles, <Palette2_MTiles, <Palette3_MTiles
MetatileGraphics_High:
.db >Palette0_MTiles, >Palette1_MTiles, >Palette2_MTiles, >Palette3_MTilesKombinasi kedua array ini memberi kami alamat 16-bit, yang dalam contoh kami menunjukkan ke
Palette1_Mtiles :
Palette1_MTiles:
.db $a2, $a2, $a3, $a3 ;vertical rope
.db $99, $24, $99, $24 ;horizontal rope
.db $24, $a2, $3e, $3f ;left pulley
.db $5b, $5c, $24, $a3 ;right pulley
.db $24, $24, $24, $24 ;blank used for balance rope
.db $9d, $47, $9e, $47 ;castle top
.db $47, $47, $27, $27 ;castle window left
.db $47, $47, $47, $47 ;castle brick wall
.db $27, $27, $47, $47 ;castle window right
.db $a9, $47, $aa, $47 ;castle top w/ brick
.db $9b, $27, $9c, $27 ;entrance top
.db $27, $27, $27, $27 ;entrance bottom
.db $52, $52, $52, $52 ;green ledge stump
.db $80, $a0, $81, $a1 ;fence
.db $be, $be, $bf, $bf ;tree trunk
.db $75, $ba, $76, $bb ;mushroom stump top
.db $ba, $ba, $bb, $bb ;mushroom stump bottom
.db $45, $47, $45, $47 ;breakable brick w/ line
.db $47, $47, $47, $47 ;breakable brick
.db $45, $47, $45, $47 ;breakable brick (not used)
.db $b4, $b6, $b5, $b7 ;cracked rock terrain <--- This is the 20th line
.db $45, $47, $45, $47 ;brick with line (power-up)
.db $45, $47, $45, $47 ;brick with line (vine)
.db $45, $47, $45, $47 ;brick with line (star)
.db $45, $47, $45, $47 ;brick with line (coins)
...Ketika Anda mengalikan indeks metatile dengan 4, itu menjadi indeks dari array ini. Data diformat dalam 4 catatan per baris, jadi contoh metatile kami merujuk ke baris kedua puluh, ditandai dengan komentar
cracked rock terrain .
Keempat entri dari baris ini sebenarnya adalah pengidentifikasi ubin: setiap metatile terdiri dari empat ubin 8x8-piksel yang disusun dalam urutan berikut - kiri atas, kiri bawah, kanan atas dan kanan bawah. Pengidentifikasi ini diteruskan langsung ke konsol PES NES. Pengidentifikasi mengacu pada 16 byte data di konsol CHR-ROM, dan setiap catatan dimulai dengan alamat
0x1000 + 16 * < > :
0x1000 + 16 * 0xb4: 0b01111111 0x1000 + 16 * 0xb5: 0b11011110
0x1001 + 16 * 0xb4: 0b10000000 0x1001 + 16 * 0xb5: 0b01100001
0x1002 + 16 * 0xb4: 0b10000000 0x1002 + 16 * 0xb5: 0b01100001
0x1003 + 16 * 0xb4: 0b10000000 0x1003 + 16 * 0xb5: 0b01100001
0x1004 + 16 * 0xb4: 0b10000000 0x1004 + 16 * 0xb5: 0b01110001
0x1005 + 16 * 0xb4: 0b10000000 0x1005 + 16 * 0xb5: 0b01011110
0x1006 + 16 * 0xb4: 0b10000000 0x1006 + 16 * 0xb5: 0b01111111
0x1007 + 16 * 0xb4: 0b10000000 0x1007 + 16 * 0xb5: 0b01100001
0x1008 + 16 * 0xb4: 0b10000000 0x1008 + 16 * 0xb5: 0b01100001
0x1009 + 16 * 0xb4: 0b01111111 0x1009 + 16 * 0xb5: 0b11011111
0x100a + 16 * 0xb4: 0b01111111 0x100a + 16 * 0xb5: 0b11011111
0x100b + 16 * 0xb4: 0b01111111 0x100b + 16 * 0xb5: 0b11011111
0x100c + 16 * 0xb4: 0b01111111 0x100c + 16 * 0xb5: 0b11011111
0x100d + 16 * 0xb4: 0b01111111 0x100d + 16 * 0xb5: 0b11111111
0x100e + 16 * 0xb4: 0b01111111 0x100e + 16 * 0xb5: 0b11000001
0x100f + 16 * 0xb4: 0b01111111 0x100f + 16 * 0xb5: 0b11011111
0x1000 + 16 * 0xb6: 0b10000000 0x1000 + 16 * 0xb7: 0b01100001
0x1001 + 16 * 0xb6: 0b10000000 0x1001 + 16 * 0xb7: 0b01100001
0x1002 + 16 * 0xb6: 0b11000000 0x1002 + 16 * 0xb7: 0b11000001
0x1003 + 16 * 0xb6: 0b11110000 0x1003 + 16 * 0xb7: 0b11000001
0x1004 + 16 * 0xb6: 0b10111111 0x1004 + 16 * 0xb7: 0b10000001
0x1005 + 16 * 0xb6: 0b10001111 0x1005 + 16 * 0xb7: 0b10000001
0x1006 + 16 * 0xb6: 0b10000001 0x1006 + 16 * 0xb7: 0b10000011
0x1007 + 16 * 0xb6: 0b01111110 0x1007 + 16 * 0xb7: 0b11111110
0x1008 + 16 * 0xb6: 0b01111111 0x1008 + 16 * 0xb7: 0b11011111
0x1009 + 16 * 0xb6: 0b01111111 0x1009 + 16 * 0xb7: 0b11011111
0x100a + 16 * 0xb6: 0b11111111 0x100a + 16 * 0xb7: 0b10111111
0x100b + 16 * 0xb6: 0b00111111 0x100b + 16 * 0xb7: 0b10111111
0x100c + 16 * 0xb6: 0b01001111 0x100c + 16 * 0xb7: 0b01111111
0x100d + 16 * 0xb6: 0b01110001 0x100d + 16 * 0xb7: 0b01111111
0x100e + 16 * 0xb6: 0b01111111 0x100e + 16 * 0xb7: 0b01111111
0x100f + 16 * 0xb6: 0b11111111 0x100f + 16 * 0xb7: 0b01111111CHR-ROM adalah memori yang hanya dapat dibaca yang hanya dapat diakses oleh PPU. Ini dipisahkan dari PRG-ROM, yang menyimpan kode program. Oleh karena itu, data di atas tidak tersedia dalam kode sumber dan harus diperoleh dari dump ROM game.
16 byte untuk setiap ubin membuat ubin 8-bit 2-bit: bit pertama adalah 8 byte pertama, dan yang kedua adalah 8 byte kedua:
21111111 13211112
12222222 23122223
12222222 23122223
12222222 23122223
12222222 23132223
12222222 23233332
12222222 23111113
12222222 23122223
12222222 23122223
12222222 23122223
33222222 31222223
11332222 31222223
12113333 12222223
12221113 12222223
12222223 12222233
23333332 13333332Bind data ini ke palet 1:
... dan menggabungkan potongan-potongan:
Akhirnya kami mendapat ubin yang diberikan.
Menyatukan semuanya
Mengulangi prosedur ini untuk setiap file meta, kami mendapatkan tingkat yang sepenuhnya diberikan.
Dan berkat ini, kami dapat mengekstraksi grafik level SMB menggunakan Python!