🌹 🧓🏽 🔤 Porting Quake ke iPod Classic 📵 🚆 👋🏻

Luncurkan Quake on iPod Classic ( video ).

TL; DR : Saya berhasil menjalankan Quake di pemutar MP3. Artikel tersebut menjelaskan bagaimana ini terjadi.

Saya menghabiskan sebagian musim panas lalu pada beberapa hal favorit saya: Rockbox dan game Quake id Software. Saya bahkan berkesempatan untuk menggabungkan kedua hobi ini dengan memindahkan Quake ke Rockbox! Mustahil untuk berharap lebih!

Posting ini menceritakan tentang cara kerjanya. Ini adalah cerita panjang yang membentang selama hampir dua tahun. Selain itu, ini adalah upaya pertama saya untuk mendokumentasikan proses pengembangan, terperinci dan tidak dipernis, berbeda dengan dokumentasi teknis yang telah selesai, yang telah saya tulis terlalu banyak dalam hidup saya. Artikel ini juga akan memiliki rincian teknis, tetapi pertama-tama saya akan mencoba berbicara tentang proses pemikiran yang mengarah pada pembuatan kode.

Sayangnya, sudah waktunya untuk mengucapkan selamat tinggal pada Rockbox dan Quake, setidaknya untuk waktu dekat. Selama beberapa bulan, waktu luang akan menjadi sumber daya yang sangat langka bagi saya, jadi sebelum bergegas untuk bekerja, saya cepat-cepat mengungkapkan pikiran saya.

Rockbox

Rockbox adalah proyek open source yang penasaran, yang saya habiskan banyak waktu untuk meretas. Hal terbaik tentang itu tertulis di halaman web: "Rockbox adalah firmware gratis untuk pemutar musik digital." Itu benar - kami membuat pengganti lengkap untuk perangkat lunak pabrik yang datang bersama pemain Sandisk Sansa, Apple iPod, dan banyak perangkat lain yang didukung.

Kami tidak hanya berusaha menciptakan kembali fungsi-fungsi firmware asli, tetapi juga mengimplementasikan dukungan untuk ekstensi yang dapat diunduh yang disebut plug - in -program kecil yang berjalan pada pemutar MP3. Rockbox sudah memiliki banyak gim dan demo hebat, yang paling mengesankan di antaranya adalah penembak orang pertama Doom dan Duke Nukem 3D ¹. Tetapi saya merasa ada sesuatu yang hilang dalam dirinya.

Gempa muncul di panggung

Gempa adalah penembak orang pertama yang sepenuhnya tiga dimensi. Mari kita lihat apa artinya itu. Kata-kata kunci di sini adalah "sepenuhnya tiga dimensi . " Tidak seperti Doom dan Duke Nukem 3D, yang biasa disebut 2.5D (bayangkan sebuah peta 2D dengan komponen ketinggian opsional), Quake diimplementasikan dalam 3D penuh. Setiap dhuwur dan poligon ada dalam ruang 3D. Ini berarti bahwa trik pseudo-3D lama tidak lagi berfungsi - semuanya dilakukan dalam 3D penuh. Namun, saya terganggu. Singkatnya, Gempa adalah hal yang kuat.

Dan Gempa tidak memaafkan lelucon. Penelitian kami menunjukkan bahwa Quake “membutuhkan” prosesor x86 dengan frekuensi sekitar 100 MHz dan FPU, serta sekitar 32 MB RAM. Sebelum Anda mulai terkikik, ingatlah bahwa platform target untuk Rockbox tidak sebanding dengan apa yang menjadi fokus John Carmack saat menulis permainan - Rockbox bahkan bekerja pada perangkat dengan prosesor dengan frekuensi hanya 11 MHz dan 2 MB RAM (tentu saja, Gempa seharusnya tidak berfungsi pada seperti perangkat). Dengan mengingat hal ini, saya melihat koleksi pemutar audio digital saya yang semakin berkurang dan memilih yang paling kuat dari yang selamat: Apple iPod Classic / 6G dengan prosesor ARMv5E 216 MHz dan 64 MB RAM (indeks Emenunjukkan adanya ekstensi ARM DSP - nanti ini akan menjadi penting bagi kami). Spesifikasi serius, tetapi hampir tidak ada cukup untuk menjalankan Quake.

Pelabuhan

Ada versi Quake yang luar biasa yang dapat berjalan di SDL . Ini memiliki nama logis SDLQuake . Untungnya, saya telah mem-porting perpustakaan SDL ke Rockbox (ini adalah topik untuk artikel lain), jadi mempersiapkan Quake untuk kompilasi ternyata menjadi proses yang cukup sederhana: salin struktur kode sumber; make; kami memperbaiki kesalahan; bilas, sabun, ulangi. Saya mungkin melukis banyak detail yang membosankan di sini, tetapi bayangkan kekaguman saya karena telah berhasil menyusun dan menautkan executable Quake. Saya sangat senang.

"Yah, muat!" Saya pikir.

Dan itu boot! Saya disambut oleh latar belakang dan menu konsol Quake yang indah. Semuanya sempurna. Tapi luangkan waktu Anda! Ketika saya memulai permainan, ada sesuatu yang salah. Level "Pendahuluan" tampaknya memuat secara normal, tetapi posisi spawn pemain benar-benar keluar dari peta. Aneh , pikirku. Saya mencoba berbagai trik, mulai debugging dan splashf, tetapi semuanya sia-sia - bug itu ternyata terlalu rumit bagi saya, atau bagi saya sepertinya itu.

Dan situasi ini bertahan selama beberapa tahun. Mungkin patut dibicarakan sedikit tentang waktunya. Upaya pertama untuk meluncurkan Quake dilakukan pada September 2017, setelah itu saya menyerah, dan Frankenstein saya dari Quake dan Rockbox tergeletak di rak, mengumpulkan debu, hingga Juli 2019. Setelah menemukan kombinasi sempurna antara kebosanan dan motivasi, saya memutuskan untuk melanjutkan dengan menyelesaikan apa yang saya mulai.

Saya mulai debugging. Keadaan aliran saya sedemikian rupa sehingga saya tidak ingat secara praktis tidak ada detail tentang apa yang saya lakukan, tetapi saya akan mencoba untuk menciptakan kembali jalan kerja.

Saya menemukan bahwa struktur Quake dibagi menjadi dua bagian utama: kode mesin di C dan logika tingkat tinggi dari game di QuakeC, bahasa yang dikompilasi bytecode. Saya selalu berusaha untuk menjauh dari QuakeC VM karena takut irasional men-debug kode orang lain. Tetapi sekarang saya dipaksa untuk terjun ke dalamnya. Samar-samar saya ingat sesi streaming gila saat saya mencari sumber bug. Setelah banyak grep, saya menemukan pelakunya: pr_cmds.c:PF_setorigin. Fungsi ini menerima vektor tiga dimensi yang menetapkan koordinat baru pemain saat memuat peta, yang karena alasan tertentu selalu sama (0, 0, 0). Hm ...

Saya menelusuri ulang aliran data dan menemukan dari mana asalnya: dari panggilan Q_atof()- fungsi konversi klasik dari string ke float. Dan kemudian wawasan saya sadar: Saya menulis satu set fungsi pembungkus yang mendefinisikan ulang Q_atof()kode Quake, dan implementasi saya atof()mungkin salah. Sangat mudah untuk memperbaikinya. Saya mengganti kesalahan saya dengan fungsi yang atofbenar dari kode Quake. Dan voila! Level entri yang terkenal dengan tiga koridor dimuat tanpa masalah, seperti halnya "E1M1: The Slipgate Complex". Output audio masih terdengar seperti mesin pemotong rumput yang rusak, tapi kami masih menjalankan Quake di pemutar MP3!

Masuk kedalam lubang kelinci

Proyek ini akhirnya menjadi alasan untuk apa yang saya tunda: mempelajari bahasa assembly ARM ² .

Masalahnya adalah siklus pencampuran suara yang sensitif terhadap kecepatan snd_mix.c(ingat suara mesin pemotong rumput?).

Fungsi ini SND_PaintChannelFrom8menerima array sampel audio mono 8-bit dan mencampurnya menjadi aliran stereo 16-bit, saluran kiri dan kanan yang diskalakan secara terpisah berdasarkan dua parameter bilangan bulat. GCC melakukan pekerjaan yang buruk mengoptimalkan aritmatika saturasi, jadi saya memutuskan untuk melakukannya sendiri. Hasilnya benar-benar memuaskan saya.

Ini adalah versi assembler dari apa yang saya dapatkan (versi C disajikan di bawah):

SND_PaintChannelFrom8:
        ;; r0: int true_lvol
        ;; r1: int true_rvol
        ;; r2: char *sfx
        ;; r3: int count

        stmfd sp!, {r4, r5, r6, r7, r8, sl}

        ldr ip, =paintbuffer
        ldr ip, [ip]

        mov r0, r0, asl #16                 ; prescale by 2^16
        mov r1, r1, asl #16

        sub r3, r3, #1                      ; count backwards

        ldrh sl, =0xffff                    ; halfword mask

1:
        ldrsb r4, [r2, r3]                  ; load input sample
        ldr r8, [ip, r3, lsl #2]                ; load output sample pair from paintbuffer
                                ; (left:right in memory -> right:left in register)
        ;; right channel (high half)
        mul r5, r4, r1                      ; scaledright = sfx[i] * (true_rvol << 16) -- bottom half is zero
        qadd r7, r5, r8                     ; right = scaledright + right (in high half of word)
        bic r7, r7, sl                      ; zero bottom half of r7

        ;; left channel (low half)
        mul r5, r4, r0                      ; scaledleft = sfx[i] * (true_rvol << 16)
        mov r8, r8, lsl #16                 ; extract original left channel from paintbuffer
        qadd r8, r5, r8                     ; left = scaledleft + left

        orr r7, r7, r8, lsr #16                 ; combine right:left in r7
        str r7, [ip, r3, lsl #2]                ; write right:left to output buffer
        subs r3, r3, #1                         ; decrement and loop

        bgt 1b                          ; must use bgt instead of bne in case count=1

        ldmfd sp!, {r4, r5, r6, r7, r8, sl}

        bx lr

Ada retasan rumit di sini yang perlu dijelaskan. Saya menggunakan instruksi qaddprosesor DSP ARM untuk mengimplementasikan penambahan saturasi yang murah, tetapi qaddhanya bekerja dengan kata-kata 32-bit, dan game menggunakan sampel suara 16-bit. Peretasannya adalah saya pertama kali menggeser sampel yang tersisa 16 bit; Saya menggabungkan sampel dengan qadd; dan kemudian lakukan reverse shift. Jadi dalam satu instruksi saya melakukan apa yang GCC ambil tujuh. (Ya, itu akan mungkin dilakukan tanpa peretasan sama sekali jika saya bekerja dengan ARMv6, yang memiliki aritmetika saturasi penuh seperti MMX qadd16, tetapi sayangnya, hidup tidak begitu sederhana. Selain itu, peretasan ternyata keren!)

Perhatikan juga bahwa Saya membaca dua sampel stereo sekaligus (menggunakan kata-kata ldrdanstr) untuk menghemat beberapa siklus lagi.

Di bawah ini adalah versi C untuk referensi:

void SND_PaintChannelFrom8 (int true_lvol, int true_rvol, signed char *sfx, int count)
{
        int     data;
        int             i;

        // we have 8-bit sound in sfx[], which we want to scale to
        // 16bit and take the volume into account
        for (i=0 ; i<count ; i++)
        {
            // We could use the QADD16 instruction on ARMv6+
            // or just 32-bit QADD with pre-shifted arguments
            data = sfx[i];
            paintbuffer[2*i+0] = CLAMPADD(paintbuffer[2*i+0], data * true_lvol); // need saturation
            paintbuffer[2*i+1] = CLAMPADD(paintbuffer[2*i+1], data * true_rvol);
        }
}

Saya menghitung bahwa, dibandingkan dengan versi C yang dioptimalkan, jumlah instruksi per sampel menurun hingga 60%. Sebagian besar loop disimpan dengan menggunakan qaddsaturasi dan pengemasan operasi memori untuk aritmatika.

Konspirasi angka "prima"

Berikut ini adalah bug lain yang menarik yang saya temukan dalam proses. Dalam daftar kode rakitan, di sebelah instruksi bgt(cabang "jika lebih dari") ada komentar bahwa bne(cabang "jika tidak sama") tidak dapat digunakan karena kasus batas yang memperlambat program dengan jumlah sampel sama dengan 1. Ini mengarah ke transfer siklik integer aktif 0xFFFFFFFFdan penundaan yang sangat lama (yang akhirnya berakhir).

Kasing garis batas ini dipicu oleh satu suara tertentu, yang memiliki panjang 7325 sampel ³ . Apa yang istimewa dari 7325? Mari kita coba mencari sisa dari pembagiannya dengan kekuatan dua:

\begin{aligned} 7325 & \equiv 1 & (\mod 2) \\ 7325 & \equiv 1 & (\mod 4) \\ 7325 & \equiv 5 & (\mod 8) \\ 7325 & \equiv 13 & (\mod 16) \\ 7325 & \equiv 29 & (\mod 32) \\ 7325 & \equiv 29 & (\mod 64) \\ 7325 & \equiv 29 & (\mod 128) \\ 7325 & \equiv 157 & (\mod 256) \\ 7325 & \equiv 157 & (\mod 512) \\ 7325 & \equiv 157 & (\mod 1024) \\ 7325 & \equiv 1181 & (\mod 2048) \\ 7325 & \equiv 3229 & (\mod 4096) \end{aligned}

$\begin{align*} 7325 &\equiv 1 &\pmod{2} \\ 7325 &\equiv 1 &\pmod{4} \\ 7325 &\equiv 5 &\pmod{8} \\ 7325 &\equiv 13 &\pmod{16} \\ 7325 &\equiv 29 &\pmod{32} \\ 7325 &\equiv 29 &\pmod{64} \\ 7325 &\equiv 29 &\pmod{128} \\ 7325 &\equiv 157 &\pmod{256} \\ 7325 &\equiv 157 &\pmod{512} \\ 7325 &\equiv 157 &\pmod{1024} \\ 7325 &\equiv 1181 &\pmod{2048} \\ 7325 &\equiv 3229 &\pmod{4096} \end{align*}$

5, 13, 29, 157 ...

Apakah Anda memperhatikan sesuatu? Yaitu - secara kebetulan, 7325 adalah angka "prima" ketika membaginya dengan kekuatan dua. Ini entah bagaimana (saya tidak mengerti bagaimana) mengarah pada fakta bahwa array dari satu sampel ditransfer ke kode pencampuran suara, sebuah kasus batas dipicu dan hang.

Saya menghabiskan setidaknya satu hari untuk mengidentifikasi penyebab bug ini, sebagai hasil dari mengetahui bahwa semua itu disebabkan oleh satu instruksi yang salah. Terkadang itu terjadi dalam hidup, bukan?

Perpisahan

Saya akhirnya mengemas port ini sebagai patch dan menggabungkannya dengan cabang Rockbox utama, di mana sekarang ini. Dalam Rockbox versi 3.15 dan yang lebih baru, ia hadir dalam rakitan untuk sebagian besar platform target ARM dengan ⁴ tampilan warna . Jika Anda tidak memiliki platform yang didukung, maka Anda dapat melihat demo user890104 .

Demi menghemat ruang, saya melewatkan beberapa poin menarik. Misalnya, ada kondisi balapan yang terjadi hanya ketika zombie membelah daging ketika laju pengambilan sampel 44,1 kHz. (Ini adalah hasil dari aliran suara yang mencoba memuat suara - ledakan, dan pemuat model yang mencoba memuat model daging. Kedua bagian kode ini menggunakan satu fungsi yang menggunakan satu variabel global.) Dan ada juga banyak masalah pemesanan (love you, ARM! ) dan sekelompok rendering mikro yang saya buat untuk memeras beberapa frame lagi dari peralatan. Tapi aku akan meninggalkan mereka lain kali. Dan sekarang saatnya mengucapkan selamat tinggal pada Quake - Saya menyukai pengalaman ini.

Semua yang terbaik, dan terima kasih untuk ikannya!

Catatan

Duke Nukem 3D , runtime Rockbox SDL, . , user890104.
ARM, Tonc: Whirlwind Tour of ARM Assembly — ( GBA) . , ARM Quick Reference Card.
, 100 .
Sejujurnya, saya tidak ingat platform target spesifik mana yang didukung dan tidak mendukung Quake. Jika Anda penasaran, buka situs web Rockbox dan coba instal build untuk platform Anda. Dan beri tahu saya lewat pos saat berfungsi! Versi terbaru dari Rockbox Utility (mulai 1.4.1 dan lebih tinggi) juga mendukung instalasi otomatis versi shareware Quake.

Porting Quake ke iPod Classic