Buat berang tersibuk dalam kode mesin x86 dalam 32 byte atau kurang

8

Tugas Anda adalah menulis sebuah program dalam bahasa mesin x86 (versi apa pun yang Anda suka) yang akan menjalankan sebanyak mungkin instruksi dan kemudian berhenti, menggunakan maksimum 32 byte kode dan mulai dengan register zeroed-out.

Anda dapat mengasumsikan apa pun tentang memori akses acak yang Anda suka, asalkan itu dalam format yang dapat digunakan untuk mesin x86.

Joe Z.
sumber
3
Ada mesin Turing berang-berang yang cukup kecil yang perilaku penghentiannya tidak diketahui ( en.wikipedia.org/wiki/Busy_beaver#Known_values ). Apa yang terjadi ketika seseorang mengimplementasikan salah satunya?
asmeurer
Ada beberapa detail yang bisa diisi di sini. Apakah kita memiliki setumpuk yang diatur untuk kita? Seberapa besar itu? Apakah program ini gratis untuk mengakses memori? Jika ya, berapa jumlahnya? Apakah kita memiliki akses baca-tulis ke semua 4 GB? Jika demikian, dapatkah kita memilih di mana program kita berada?
kotak roti
Anda dapat mengasumsikan apa pun tentang memori yang Anda inginkan, saya kira, selama register yang sebenarnya semuanya di-nolkan pada awal eksekusi kode. (Apakah ini akan menimbulkan masalah? Saya tidak terlalu berpengalaman dengan bahasa mesin.)
Joe Z.
Bisakah kita berasumsi bahwa prosesor dalam mode nyata dan / atau mode terlindungi? Karena jika kita dapat mengasumsikan mode terlindungi, yang membuka banyak pertanyaan lain tentang Global Descriptor Table dan paging table, dll. Mengingat masalah-masalah itu, mungkin lebih baik hanya menegakkan real-mode, yang berarti lebih sedikit memori yang tersedia . Kecuali jika kita dapat mengasumsikan mode tidak nyata, yang saya sadari sekarang saya secara implisit mengasumsikan bahwa saya ada di dalamnya. Tetapi bagaimanapun juga, ini mungkin harus secara eksplisit disebut dalam deskripsi masalah.
kotak roti

Jawaban:

8

2 instruksi 524224

Program saya:

_start:
        mov     bl, _end
        stc
iloop:  adc     [bx], al
        inc     bx
        jnz     iloop
        jnc     _start
        a32
        loop    _start
        hlt
_end:

(Catatan teknis: ini ditulis untuk nasm. Sintaks a32is nasm untuk byte awalan ukuran alamat alternatif. Untuk masm, Anda akan mengganti a32dengan defb 0x67.)

Untuk lebih jelasnya, inilah output listing:

 1                  _start:
 2 0000 B310                mov     bl, _end
 3 0002 F9                  stc
 4 0003 1007        iloop:  adc     [bx], al
 5 0005 43                  inc     bx
 6 0006 75F9                jnz     iloop
 7 0008 73F4                jnc     _start
 8 000A 67                  a32
 9 000B E2F1                loop    _start
10 000D F4                  hlt
11                  _end:

Program mengasumsikan bahwa prosesor berada dalam mode nyata, dan bahwa program tersebut terletak di bagian bawah segmen memori 64k yang dinyatakan diinisialisasi ke semua-bit-nol. Desainnya sederhana: perlakukan memori sebagai bilangan bulat tak bertanda raksasa tunggal, dan tambahkan melalui semua nilai yang mungkin, hingga memori berputar kembali menjadi nol semua. Ulangi ini 2 32 kali. Lalu berhenti.

Loop terdalam (baris 4‒6) bertanggung jawab untuk menambah bilangan bulat besar. Setiap iterasi menambahkan nol atau satu ke satu byte, tergantung pada apakah ada pelaksanaan byte sebelumnya. Perhatikan bahwa setiap byte dalam integer besar diakses, apakah itu telah berubah atau tidak, jadi loop ini selalu berulang 2 16 - 14 kali.

By the way, jika Anda bertanya-tanya, kode ini menggambarkan alasan mengapa x86 inc/ decinstruksi tidak mempengaruhi flag carry: hanya untuk menyederhanakan semacam ini pola carry multi-byte. (Pola ini muncul lebih sering pada zaman mikroprosesor 8-bit, ketika set instruksi 8080 yang asli didefinisikan.)

Baris 7 menyebabkan proses penambahan ulang sampai satu dilakukan dari byte terakhir, menunjukkan bahwa bilangan bulat besar telah diatur ulang ke semua-bit-nol. Ini butuh waktu lama.

Baris 8‒9 menandai loop terluar, dan menyebabkan proses ini berulang 2 32 kali, sampai ecxregister berputar ke nol. Ini setara dengan menambahkan 32 bit ke integer raksasa.

Adalah mungkin untuk menambahkan loop luar lain dan melakukan ini lagi menggunakan (katakanlah) edxregister, dan kemudian mungkin menggunakan esidan ediuntuk pengulangan yang lebih banyak lagi. Namun, itu tidak layak dilakukan. Instruksi untuk menambah dan mengulang membutuhkan empat byte. Keempat byte tersebut diambil dari integer raksasa. Jadi kita kehilangan 32 bit pada penghitung RAM, hanya untuk menambahkan 32 bit melalui register: akhirnya menjadi pembasuhan. Satu-satunya alasan ecxadalah pengecualian adalah bahwa ia memiliki loopinstruksi khusus yang hanya cocok menjadi tiga byte. Dengan demikian program berdagang 24 bit untuk 32, keuntungan kecil tapi masih positif 8 bit.

Tidak terlalu sulit untuk secara langsung menghitung jumlah instruksi yang dijalankan oleh program sebelum berhenti. Namun, ada cara yang lebih sederhana untuk memperkirakan angka ini. Program memodifikasi semua memorinya, kurang dari 14 byte yang berisi program, bxdan ecxregister. Ini menambahkan hingga 2 16 - 14 + 2 + 4 = 65528 byte, dengan total 524224 bit. Jalan pintas melibatkan menyadari bahwa, dalam proses berjalan, setiap pola yang mungkin dari 524224 bit muncul tepat sekali. Untuk RAM dan ecxregister, ini mudah dilihat, karena program bertambah setiap nilai. Untukbxini sedikit kurang jelas, karena sedang diubah pada saat yang sama dengan nilai dalam memori sedang diperbarui. Namun, orang dapat menunjukkan bahwa, mengingat struktur program, jika pola bit lengkap benar-benar muncul dua kali, maka program harus berada dalam loop tak terbatas. Karena ini bukan masalahnya, setiap pola bit pada akhirnya harus dikunjungi hanya sekali. (Bukti lengkap dibiarkan sebagai latihan untuk pembaca, tentu saja.)

Karena setiap pola bit yang mungkin muncul dalam program, program harus menjalankan setidaknya 2 524224 instruksi, yang kira-kira sama dengan 1,4 × 10 157807 . (Angka acutal sangat sedikit lebih tinggi, karena instruksi lompatan, tetapi perbedaan pada besarnya ini diabaikan.)

Jelas, ini dapat ditingkatkan secara signifikan dengan menggunakan lebih dari 64k RAM. Saya menunda versi kode selanjutnya sampai saya tahu persis berapa banyak RAM yang dapat diakses.

kotak roti
sumber
Bukankah itu 17 instruksi (34 byte)? Atau apakah saya melewatkan sesuatu?
Joe Z.
@ Joz. inc adalah 1 byte (jika Anda tidak memasangnya dalam mode 16 bit)
salin
Oh Jadi program ini sebenarnya panjangnya 25 byte?
Joe Z.
Ya, ini 25 byte
salin
Maaf, saya seharusnya lebih eksplisit. Saya menambahkan output listing untuk menghindari ambiguitas.
kotak roti
4

~ 2 ^ (2 ^ 67) instruksi

(at & t sintaks)

start:
    movq    $0x1a,%rax
    stc
loop:
    adcb    %cl,(%rax)
    incq    %rax
    jnz     loop
    jnc     start
    hlt

Dibongkar, 26 byte:

start:
0000000000000000    movq    $0x0000001a,%rax
0000000000000007    stc
loop:
0000000000000008    adcb    %cl,(%rax)
000000000000000a    incq    %rax
000000000000000d    jne loop
0000000000000013    jae start
0000000000000019    hlt

Mirip dengan solusi breadbox, tetapi tidak ada alasan untuk berhenti di 16 bit alamat. Kode saya menggunakan x86-64 dan menganggap kami memiliki 2 ^ 64 byte memori dan kami menggunakan semua kecuali memori yang memegang kode sebagai penghitung raksasa.

Keith Randall
sumber