Pada 1984, buku kultus Steven Levy, Hackers: Heroes of the Computer Revolution , dirilis. Ada terjemahan Rusia amatir, tetapi jauh dari ideal. Saya berusaha untuk memperbaiki ketidakakuratan di dalamnya, meletakkan naskah asli bahasa Inggris di sebelahnya (omong-omong, dan itu bukan tanpa dosa), tetapi meninggalkannya setelah bab kedua. Dengan satu atau lain cara, saya ingin menarik perhatian Anda ke sebuah fragmen (Anda dapat membacanya di artikel terpisah ) yang didedikasikan untuk subrutin untuk mencetak angka dalam sistem desimal. Berapa banyak program seperti itu dapat dikurangi? Berapa batasannya?Pada bulan Agustus 2018, saya menulis sebuah program untuk mengukur waktu eksekusi yang tepat dari instruksi prosesor Soviet 1801BM1 (memiliki serangkaian instruksi PDP-11 ). Mengetahui waktu yang tepat (dalam siklus prosesor) diperlukan saat mengerjakan demo " Apple Baik " untuk komputer BK 0011M. Saya ingin melihat hasil pengukuran dalam desimal. Untuk melakukan ini, saya harus menulis sendiri subrutin - fungsi sistem tidak tersedia karena spesifik dari tes.Hal pertama yang saya lakukan adalah membuat TEN array dengan kekuatan 10. Prosedur mengambil angka dalam register R0, outputnya adalah string teks pada NUMBER. Penting: tidak ada instruksi pembagian dalam prosesor ! MOV #NUMBER,R1 ; pointer to output text string
MOV #TEN,R5
1: CMP (R5)+,R0 ; skip leading zeros
BHI 1 ; branch if higher, for 16-bit not signed
MOV -(R5),R3
BEQ 4 ; if less then 10
2: MOV #47.,R4 ; 0 symbol in ASCII codepage - 1
3: INC R4 ; count digits
SUB R3,R0
BHIS 3 ; branch if higher or same, for 16-bit not signed
MOVB R4,(R1)+ ; print R4
ADD (R5)+,R0
MOV (R5),R3
BNE 2
4: ADD #48.,R0 ; 0 symbol in ASCII codepage
MOVB R0,(R1)+ ; print R0
CLRB (R1) ; end of text marker
RET
TEN: .WORD 10000.,1000.,100.,10.,0
Untuk memahami assembler PDP-11, cukup untuk mengingat bahwa argumen ditulis dari kiri ke kanan (pertama sumber, kemudian penerima), dan perintah cabang bersyarat dimulai dengan huruf B (dari kata branch - branching). Saya tidak akan menjelaskan algoritme, ini tidak menarik dan diberikan di sini hanya sebagai titik awal. Ukuran rutin ini adalah 22 kata (tidak termasuk data).Setelah semuanya berhasil, saya tiba-tiba teringat sebuah cerita dari buku Stephen Levy: peretas berjuang untuk mengurangi ukuran program serupa, dan juga pada arsitektur PDP. Benar, mereka memiliki PDP-1, tetapi beberapa tahun kemudian mereka mendapat PDP-11.
Membuka buku itu, saya menemukan deskripsi yang sangat kabur. Peretas dari MIT mulaisama seperti saya dari daftar tempat desimal. Tetapi apa yang terjadi selanjutnya tidak jelas dari teks. Jelas, ini juga tidak jelas bagi penulis buku, ia hanya menuliskan kata-kata umum dari bibir para saksi mata dari kontes peretasan itu.Saya harus menyelidiki arsip Internet program untuk PDP-1 . Ada banyak hal menarik: Minskytron, kotak Munching, dan apa yang disebut "peretasan tampilan" (omong-omong, patut dicatat bahwa bahkan pada saat itu - di awal tahun 60an - peretas MIT menggunakan istilah " demo " dalam arti yang sama dengan yang kita gunakan sekarang. pada demoscene). Ada banyak rutinitas sistem dalam arsip, tetapi, sayangnya, tidak ada angka desimal di antara mereka.Kemudian, dengan dipersenjatai dengan debugger, saya memutuskan untuk melihat bagaimana prosedur ini diimplementasikan dalam sistem operasi MKDOS, yang saya gunakan pada BK 0010 dan BK 0011M. Astaga! - Setelah melihat dari dekat, saya menyadari bahwa subprogram sangat cocok dengan deskripsi berkabut dari buku "Hacker". Ini kodenya: MOV #10.,R4
CLR R2
1: CLR R1
2: SUB R4,R0 ; 10,
BLO 3
INC R1 ; -
BR 2
3: ADD R4,R0
ADD #48.,R0 ; ASCII- 0
INC R2 ; -
MOVB R0,-(SP)
MOV R1,R0 ; -
BNE 1
INC R2
MOVB #32.,-(SP) ; ASCII-
4: MOVB (SP)+,R0
CALL PRINT
SOB R2,4 ;
RET
Program membentuk string teks pada tumpukan, lalu memanggil prosedur cetak untuk setiap karakter yang disimpan. Rupanya, inilah tepatnya yang dimaksud dalam buku Stephen Levy di bawah ungkapan "bertobat dengan cara yang berlawanan, dan dengan bantuan fokus perangkat lunak yang licik itu dicetak dalam urutan yang benar." Fitur lain dari algoritma harus jelas dari komentar pada kode.Ukuran subrutin adalah 23 kata , tetapi Anda tidak dapat langsung membandingkannya dengan subrutin saya: kondisinya terlalu berbeda. Saya memutuskan untuk membuat kembali program dari MKDOS dengan kondisi saya: pembentukan string teks dalam memori.Pada akhirnya, saya menyadari bahwa lebih baik hanya meninggalkan ide untuk mengurangi angka 10, dan menulis sisanya dari awal. Setelah beberapa putaran optimasi Sansara , saya mendapatkan yang berikut: MOV #NUMBER,R1 ; pointer to output text string
CLRB -(R1) ; end of text marker
MOV #10.,R4
1: MOV #-1.,R5
2: INC R5 ; counter of 10s
SUB R4,R0
BHIS 2 ; branch if higher or same
ADD #58.,R0 ; #10. + '0' ASCII code
MOVB R0,-(R1) ; store R0 to text string
MOV R5,R0 ; let's count next how many 10s in number of 10s
BNE 1
RET ; returns text string pointer in R1
16 kata , batasnya tercapai (saya pikir), ini dia - Nirvana, yang ditulis Stephen Levy secara emosional!Trik apa yang diterapkan di sini:- Perintah pertama mengatur pointer bukan ke awal, tetapi ke akhir baris teks. Teks diisi dari kanan ke kiri - ini juga nyaman karena pada output kita mendapatkan alamat awal baris, siap dikirim ke prosedur pencetakan teks.
- , . (INC R5) 1. 0, , ?.. , 10 – , . , . . – . : 1 , , 1 ( ). , , . . -1.
- 10, , , . – ( ). , – . , , . ( 10 10 ) . : ASCII- 0, ! , , . ADD #58.,R0 (48+10).
Saya sangat senang dengan program tersebut sehingga saya memutuskan untuk membagikannya di forum zx-pk.ru (tanpa mencurigai tradisi lokal untuk mengkritik tanpa argumen). Reaksi komunitas adalah sesuatu seperti ini: "Anda hanya harus melihat bagaimana mereka melakukannya di DEC, itu klasik."Nah, ini adalah program dari DEC , perusahaan yang menciptakan PDP-11 dan memasukkan beberapa peretas dari MIT ke dalam jajarannya:; RETURNS:
; R0 = 0
; R1 -> byte following last digit in converted number
CVBTOD: MOV R0,-(SP) ;SAVE THE NUMBER PASSED TO US
CLR R0 ;SET FOR CRUDE DIVIDE BY 10.
10$: INC R0 ;BUMP QUOTIENT
SUB #10.,(SP) ;REDUCE NUMBER BY 10.
BHIS 10$ ;IF SIGN DIDN'T CHANGE...
ADD #10.+48.,(SP) ;MAKE REMAINDER PRINTABLE
DEC R0 ;REDUCE QUOTIENT
BEQ 20$ ;IF ZERO, TIME TO PRINT
CALL CVBTOD ;OTHERWISE, RECURSE !
20$: MOVB (SP)+,(R1)+ ;STORE A CONVERTED DIGIT
RETURN ;UNWIND THE RECURSION
14 kata , keren! Atau tidak? Saya dikalahkan, tapi mari kita lihat lebih dekat:- Menambahkan kode ASCII karakter 0 dan nomor 10 dilakukan dalam satu operasi. Ternyata trik semacam itu digunakan kembali di tahun 70-an. Keren.
- Program ini menyebut dirinya secara rekursif - solusi yang indah!
- – , . – .
- R1 . , , .
- , ! ?.. , . , zx-pk.ru MOV #NUMBER,R1 !
Total, ukuran sebenarnya adalah 16 kata . Persis seperti punyaku. Kedua program terdiri dari 12 instruksi. Jadi mana yang lebih baik?Bahkan jika Anda mengganti panggilan stack dengan panggilan register, program DEC akan lebih lambat karena instruksi DEC R0 dan CALL di dalam loop.Tapi itu belum semuanya. Ketika saya mulai menulis artikel ini, saya perhatikan bahwa dalam program saya ada instruksi dasar (dari MKDOS) MOV # 10., R4 - tidak masuk akal selain mempercepat loop dalam. Sudah waktunya untuk menyingkirkannya. MOV #NUMBER,R1 ; pointer to output text string
CLRB -(R1) ; end of text marker
1: MOV #-1.,R5
2: INC R5 ; counter of 10s
SUB #10.,R0
BHIS 2 ; branch if higher or same
ADD #58.,R0 ; #10. + '0' ASCII code
MOVB R0,-(R1) ; store R0 to text string
MOV R5,R0 ; let's count next how many 10s in number of 10s
BNE 1 ; loop if R0 is not zero
RET ; returns text string pointer in R1
15 kata . 11 instruksi. Sekarang, sepertinya, itu saja.Ya, gagasan pengoptimalan saya sudah berakhir. Itu adalah tantangan yang menginspirasi, bahkan pertaruhan. Sungguh luar biasa bahwa ide yang diusulkan oleh seorang mahasiswa peretas pada awal tahun 60an untuk PDP-1 digunakan oleh sepuluh Desember dan bahkan dua puluh tahun kemudian, dan itu diterapkan pada komputer Soviet, BK 0011M hingga awal tahun 2000-an. Anehnya, pada tahun 2018, dimungkinkan untuk menemukan kembali sebagian dan mengoptimalkan algoritma. Secara karakteristik, banyak yang menganggap ini tidak mungkin.Jadi, inilah Holy Grail (menurut Stephen Levy), yang coba ditemukan oleh para peretas tahun 60an - program desimal terpendek untuk PDP. Atau ... mungkin lebih pendek?Memperbarui: Saya tahu bahwa hari ini akan datang, tetapi saya tidak berpikir begitu cepat :) Ternyata program tersebut dapat dikurangi dengan satu kata lagi! Gagasan itu disarankan dalam komentar Mr_Rm : MOV #NUMBER,R1 ; pointer to output text string
CLRB -(R1) ; end of text marker
1: CLR R5
2: INC R5 ; counter of 10s +1
SUB #10.,R0
BHIS 2 ; branch if higher or same
ADD #58.,R0 ; #10. + '0' ASCII code
MOVB R0,-(R1) ; store R0 to text string
MOV R5,R0 ; let's count how many 10s in number of 10s
SOB R0,1 ; subtract 1 and loop if not zero
RET ; returns text string pointer in R1
14 kata . 11 instruksi.Kuncinya adalah ini. Ingat, saya menulis bahwa dengan organisasi "salah" dari siklus R5, satu lagi diperoleh dari yang diperlukan? Baiklah, biarkan! Kami akan menguranginya di akhir program. Dalam versi sebelumnya, R5 disalin ke R0, setelah itu perintah BNE (Branch if Not Equal to zero) memeriksa R0, dan jika tidak sama dengan nol, ia pergi ke awal siklus. Kalau saja kita akan mengurangi R0 satu per satu, dan kemudian (jika kita tidak nol) pergi ke awal ... Tunggu sebentar, tapi ini adalah perintah siklus SOB (Kurangi Satu dan Cabang) yang normal. Benar, di sini itu tidak digunakan dengan cara kanonik: memenuhi sekali, dan kemudian penghitung siklus menjadi usang. Ini terlihat mengecilkan hati, tetapi jika Anda melihat versi subrutin sebelumnya, menjadi jelas bagaimana yang baru disingkat.Tautan yang bermanfaat: