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.
Jawaban:
2 instruksi 524224
Program saya:
(Catatan teknis: ini ditulis untuk nasm. Sintaks
a32
is nasm untuk byte awalan ukuran alamat alternatif. Untuk masm, Anda akan menggantia32
dengandefb 0x67
.)Untuk lebih jelasnya, inilah output listing:
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
/dec
instruksi 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
ecx
register 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)
edx
register, dan kemudian mungkin menggunakanesi
danedi
untuk 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 alasanecx
adalah pengecualian adalah bahwa ia memilikiloop
instruksi 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,
bx
danecx
register. 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 danecx
register, ini mudah dilihat, karena program bertambah setiap nilai. Untukbx
ini 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.
sumber
~ 2 ^ (2 ^ 67) instruksi
(at & t sintaks)
Dibongkar, 26 byte:
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.
sumber