Verilog, dioptimalkan untuk area, 130 gerbang LE
Quine itu sendiri (file aktual dikodekan dalam DEC SIXBIT ):
module q(s,d);inout s,d;wire[0:1023]v=1024'b0110111100101001011001111110110110010110100100001111011010010111010101110101010110010110111100101001011001111110110100100110100100001111011010100111010101110110111000011100111100111010011001111011100000001001000111011010100111000101100111111010100111010111010100100110101101101110111010011111010110111000011011001101111000011110011100111000000010001100001011111100111001011001001001111001010000001100110010011010011001100010001010100111100101010010011000101001011001111010011011100000001010010111011010010010110100010110111010100111011010100001100100011111100000011010010111110101110110100100010110111001011011101001000000001001011011001100111001010000001010100111011010100010110100010110111001011011101001001011011011111001001101011011001001010000000000000000101101101111100100110101101100100101000000110001001000110011001100100100001001011011101001101110101111110101110100000000110011001100100100011011110111101001110010100101111011010000011010010001010000010010010011111101110110011101010001010000010010010100000111100010;reg[9:0]i=759;reg[2:0]j=7;assign d=j<6?j==2:v[i];always@(posedge s)if(j>5)begin i=i+1;j=j&1^!i?7:1;end else j=j+1;endmodule
Versi yang dapat dibaca dengan komentar dan testbench:
module q(s,d);
// Declare the ports. Making them both "inout" is shortest.
inout s,d;
// Data storage for the program.
wire[0:1023]v=1024'b{DATA GOES HERE};
// i is the current bit number within the program.
// This is relative to the /end of the data storage/ (not to the start
// of the program), so it starts at a nonzero value so that the output
// starts at the start of the program.
reg[9:0]i=759;
// When expanding bits to (6-bit) bytes, j is the bit number within
// the expansion, from 1 for the first bit up to 6 for the last.
// When not expanding, j is always 7.
// DEC SIXBIT encoding for 0 is (from MSB to LSB) 010 000.
// DEC SIXBIT encoding for 1 is (from MSB to LSB) 010 001.
// We use SSI encoding for the output, so the MSB is sent first.
reg[2:0]j=7;
assign d=j<6?j==2:v[i];
// When we get a strobe:
always@(posedge s)
// If we just output a bit, move onto the next bit.
// We may also need to reset j.
if(j>5)
begin
i=i+1;
j=j&1^!i?7:1;
end
else
// If we're inside a bit, continue to output that bit.
j=j+1;
endmodule
// {TESTBENCH BELOW HERE}
`timescale 10ns / 1ns
module testbench();
reg clock = 0;
wire data, strobe;
always
#1 clock <= !clock;
initial
#14304 $finish;
assign strobe = clock;
q testquine(.s(strobe),.d(data));
always @(negedge strobe)
$display("%d", data);
endmodule // testbench
Penggunaan Verilog memberi saya kontrol lebih besar atas detail tingkat rendah daripada yang saya miliki dengan Verity. Secara khusus, ini memungkinkan saya mengontrol jam dan mengatur ulang aturan sendiri. Program ini ditujukan untuk koneksi serial sinkron dengan input strobo s
dan output datad
. Meskipun masing-masing hanya digunakan dalam satu arah, saya menyatakan keduanya sebagai dua arah untuk menghemat beberapa byte; Saya harus golf bagian-bagian non-data program ke 1024 bit untuk dapat menggunakan gerbang logika 10-bit secara internal (bit ekstra akan lebih mahal di daerah), dan itu hanya goresan di bawah pada 1008, jadi penghematan seperti ini penting. Untuk menyimpan sejumlah besar kode, saya mengandalkan sirkuit reset perangkat keras FPGA daripada menambahkan sendiri, dan saya menggabungkan input strobo dan jam (yang merupakan trik lama yang agak disukai saat ini karena membuatnya sulit untuk menjaga pohon jam seimbang pada kecepatan tinggi, tapi ini berguna untuk bermain golf.) Saya harap itu dapat disintesis; Saya tidak tahu seberapa baik synthesizer Verilog mengatasi menggunakan port dua arah sebagai jam.
Sumber dikodekan dalam DEC SIXBIT (Saya mengasumsikan di sini bahwa kami menafsirkan alfabet tunggal huruf sebagai huruf kecil; sebuah synthesizer Verilog tidak memiliki alasan untuk menggunakan interpretasi huruf besar). Saya menggunakan karakter enam-bit yang ditetapkan secara internal dalam solusi saya yang lain, kemudian membuang-buang byte untuk mengubahnya; lebih baik menggunakan rangkaian karakter yang "alami" dengan lebar enam bit sehingga tidak perlu konversi. Saya memilih rangkaian karakter enam-bit khusus ini karena 0
dan 1
hanya berbeda dalam bit paling tidak signifikan mereka, dan hanya memiliki satu set bit lain, yang berarti bahwa rangkaian untuk mengubah digit biner ke DEC SIXBIT (yaitu "melarikan diri" string) bisa sangat sederhana. Menariknya, karakter yang diatur dalam pertanyaan tidak memiliki karakter baris baru; program aslinya semua dalam satu baris bukan hanyauntuk membuatnya lebih mudah untuk dibuat, tetapi untuk membuatnya mungkin untuk dikodekan! Untung Verilog tidak terlalu peduli dengan spasi putih.
Protokol untuk mengirim data ke host didasarkan pada Synchronous Serial Interface. Saya mengambilnya karena sudah di-clock (memungkinkan saya untuk menggunakan trik jam / strobo, dan juga memungkinkan saya untuk menulis program portabel yang tidak bergantung pada perangkat timing on-chip), dan karena itu sangat sederhana (jadi saya tidak harus membuang banyak kode untuk mengimplementasikannya). Protokol ini tidak menentukan metode untuk menentukan di mana pesan berakhir (tuan rumah seharusnya tahu); dalam kasus khusus ini, saya mengisi output hingga kelipatan 1024 bit dengan nol bit (total 16 bit padding), setelah itu (seperti yang dipersyaratkan oleh SSI) pesan restart. (Saya tidak menerapkan timer mode siaga; tujuannya adalah untuk menentukan apakah akan mengirim pesan baru atau apakah akan mengulangi pesan sebelumnya, dan karena program ini selalu mengirimkan kode sumber sendiri sebagai pesan, perbedaannya tidak terlihat. Anda dapat menganggapnya panjang 0,
Dalam hal logika aktual, hal yang paling menarik adalah cara saya membagi variabel untuk mengurangi jumlah area yang dibutuhkan pada chip. i
, register yang lebih besar, menyimpan "alamat" saat ini dalam data program, dan hanya pernah diubah melalui penambahannya; ini berarti bahwa logikanya dapat disintesis menggunakan konstruksi setengah penambah (yang, seperti namanya, menggunakan hanya setengah sumber daya yang dilakukan penambah; ini sebagian besar hanya masalah pada FPGA terkecil, yang lebih besar akan menggunakan 3-input atau bahkan LUT 4-input yang cukup kuat sehingga mereka akan memiliki banyak kapasitas terbuang mensintesis setengah penambah). Register yang lebih kecil,j
, pada dasarnya adalah keadaan mesin negara dan dengan demikian menangani sebagian besar logika kompleks program. Ini cukup kecil sehingga dapat ditangani sepenuhnya melalui tabel pencarian pada FPGA yang lebih besar (membuat logika pada dasarnya hilang); dalam hal program disintesis untuk FPGA kecil, saya memilih pengkodeannya sedemikian rupa sehingga beberapa bagian dari kode peduli tentang ketiga bit sekaligus.
Ini juga perlu dicatat bahwa saya secara siklus mengijinkan penyimpanan data. Kita bisa mulai i
menunjuk ke mana saja di dalamnya, tidak harus di awal. Dengan pengaturan yang terlihat di sini, kita dapat mencetak dari nilai awal i
hingga akhir secara langsung, lalu mencetak seluruh larik, kemudian mencetak dari awal hingga nilai awal i
, untuk mencetak semua bagian data di tempat yang tepat tanpa perlu menyimpan dan mengembalikan nilai i
. (Trik ini mungkin berguna untuk quines dalam bahasa lain juga.)
Sumbernya panjangnya 1192 6-bit, setara dengan 894 8-bit. Agak memalukan bahwa ini mengandung sumber byte lebih sedikit daripada pengiriman Verity saya, meskipun dioptimalkan untuk sesuatu yang sama sekali berbeda; ini sebagian besar karena Verilog memiliki string dan Verity tidak, yang berarti bahwa meskipun saya telah menyandikan program dalam biner daripada oktal (yang secara substansial kurang efisien dalam hal ukuran kode sumber), saya dapat menyandikan setiap byte program menggunakan enam karakter enam-bit (satu untuk setiap bit) daripada delapan karakter delapan-bit (empat untuk setiap digit oktal). Pengajuan Verilog yang mengkodekan program dalam oktal mungkin akan lebih kecil dalam hal ukuran kode sumber, tetapi hampir pasti akan lebih besar di daerah tersebut.
Saya tidak tahu berapa banyak area yang akan digunakan oleh program ini; itu sangat tergantung pada seberapa kuat pengoptimal dalam Verilog synthesizer Anda (karena masalah minimalisasi mengubah data yang disimpan menjadi satu set gerbang logika adalah sesuatu yang dilakukan dalam synthesizer itu sendiri; melemparkan pekerjaan ke synthesizer membuat kode sumber itu sendiri membuat kode sumber itu sendiri jauh lebih pendek, dan dengan demikian mengurangi area yang dibutuhkan untuk menyimpannya). Seharusnya memiliki kompleksitas O (n log n), dan karenanya jauh lebih kecil daripada O (n²) dari program lain. Saya tertarik melihat OP mencoba menjalankannya di FPGA mereka. (Mungkin butuh beberapa waktu untuk mensintesis; ada beberapa langkah yang dapat Anda ambil untuk mengoptimalkan program untuk waktu kompilasi, tetapi saya tidak mengambilnya di sini karena akan menyebabkan program yang lebih besar = area yang lebih besar.)
Verity 0.10, dioptimalkan untuk ukuran kode sumber (1944 byte)
Saya awalnya salah membaca pertanyaan dan menafsirkannya sebagai kode-golf. Itu mungkin yang terbaik, karena jauh lebih mudah untuk menulis quine dengan kode sumber pendek daripada kode objek pendek di bawah batasan dalam pertanyaan; yang membuat pertanyaan itu cukup mudah sehingga saya merasa bisa menghasilkan jawaban yang masuk akal, dan mungkin berfungsi sebagai batu loncatan dalam perjalanan menuju jawaban yang lebih baik. Itu juga mendorong saya untuk menggunakan bahasa tingkat yang lebih tinggi untuk input, yang berarti bahwa saya perlu sedikit mengekspresikan dalam program itu sendiri. Saya tidak membuat Verity sebagai bahasa golf untuk perangkat keras (saya sebenarnya disewa untuk membuatnya beberapa waktu yang lalu dalam konteks yang sama sekali berbeda), tetapi ada sedikit kenangan di sana (misalnya tingkat yang jauh lebih tinggi daripada HDL biasa, dan itu memiliki boilerplate jauh lebih sedikit; ini juga jauh lebih portabel daripada HDL khas).
Saya cukup yakin bahwa solusi yang tepat untuk kode objek pendek melibatkan penyimpanan data dalam beberapa jenis struktur pohon, mengingat bahwa pertanyaannya melarang penggunaan ROM blok, yang biasanya Anda simpan dalam program praktis; Saya mungkin harus menulis program yang menggunakan prinsip ini (tidak yakin bahasa apa, mungkin Verity, mungkin Verilog; VHDL memiliki terlalu banyak boilerplate yang cenderung optimal untuk masalah semacam ini) di beberapa titik. Itu berarti Anda tidak perlu meneruskan setiap bit kode sumber ke setiap bit "ROM yang dibuat secara manual". Namun, kompiler Verity saat ini mensintesis struktur output berdasarkan prioritas dan asosiatif input, yang berarti bahwa itu secara efektif mewakili pointer instruksi (dengan demikian indeks ke tabel pencarian) di unary,
Program itu sendiri:
Lebih mudah dibaca:
Ide dasarnya adalah bahwa kita menyimpan seluruh data dalam variabel
x
. (Seperti biasa untuk quine, kami memiliki bagian kode dan bagian data; data menyandikan teks kode, dan juga dapat digunakan untuk membuat ulang teks data.) Sayangnya, Verity saat ini tidak mengizinkan sangat besar konstanta ditulis dalam kode sumber (menggunakan integer OCaml selama kompilasi untuk mewakili integer dalam sumber, yang jelas tidak benar dalam bahasa yang mendukung tipe integer lebar sewenang-wenang) - dan selain itu, konstanta tidak memungkinkan konstanta menjadi ditentukan dalam oktal - jadi kami menghasilkan nilaix
saat runtime melalui panggilan berulang ke suatu fungsia
. Kami dapat membuat fungsi void dan menyebutnya berulang kali sebagai pernyataan terpisah, tetapi itu akan menyulitkan untuk mengidentifikasi di mana mulai mengeluarkan teks dari bagian data. Jadi sebagai gantinya, saya membuata
mengembalikan bilangan bulat, dan menggunakan aritmatika untuk menyimpan data (Verity menjamin bahwa aritmatika mengevaluasi dari kiri ke kanan). Bagian data dikodekanx
menggunakan-
tanda tunggal ; ketika ini ditemui pada saat run time, itu diperluas ke penuh-a 5-a 1-
, dll, melalui penggunaany
.Menginisialisasi
y
sebagai salinanx
cukup halus di sini. Karenaa
mengembalikan nol secara khusus, sebagian besar jumlahnya hanya nol minus nol minus ... dan membatalkannya sendiri. Kita akhiri dengan!x
(yaitu "nilaix
"; di Verity, seperti pada OCaml, nama variabel bekerja lebih seperti penunjuk daripada yang lainnya, dan Anda harus melakukan dereferensi secara eksplisit untuk mendapatkan nilai variabel). Aturan Verity untuk unary minus sedikit rumit - minus unaryv
ditulis sebagai(-v)
- dengan demikian(-0-0-0-!x)
diuraikan sebagai(-(0-0-0-!x))
, yang sama dengan!x
, dan kami akhirnya menginisialisasiy
sebagai salinanx
. (Perlu juga dicatat bahwa Verity tidakcall-by-value, tetapi lebih memungkinkan fungsi dan operator untuk memilih urutan mereka mengevaluasi sesuatu;-
akan mengevaluasi argumen kiri sebelum argumen kanan, dan khususnya, jika argumen kiri memiliki efek samping, mereka akan terlihat ketika argumen kanan dievaluasi.)Setiap karakter kode sumber direpresentasikan menggunakan dua digit oktal. Ini berarti bahwa kode sumber terbatas pada 64 karakter yang berbeda, jadi saya harus membuat codepage saya sendiri untuk penggunaan internal. Keluaran dalam ASCII, jadi saya perlu mengkonversi secara internal; ini untuk apa
(if z<32 then z+92 else z)
. Inilah rangkaian karakter yang saya gunakan dalam representasi internal, dalam urutan numerik (mis.\
Memiliki codepoint 0,?
memiliki codepoint 63):Kumpulan karakter ini memberi kita sebagian besar karakter yang penting untuk Verity. Karakter yang hilang adalah
}
(artinya kita tidak dapat membuat blok menggunakan{}
, tetapi untungnya semua pernyataan adalah ekspresi sehingga kita dapat menggunakannya()
sebagai gantinya); dan|
(inilah sebabnya saya harus menggunakan yang eksklusif daripada inklusif ATAU ketika membuat nilaix
, artinya saya perlu menginisialisasi ke 0; namun, saya perlu menentukan seberapa besar ukurannya). Beberapa karakter penting yang ingin saya pastikan ada dalam rangkaian karakter adalah<>
(untuk impor, juga bergeser),()
(sangat sulit untuk menulis program yang dapat diuraikan tanpa ini),$
(untuk segala sesuatu yang berkaitan dengan bitwidth), dan\
( untuk lambdas, secara teori kita bisa mengatasi inilet…in
tetapi akan jauh lebih verbose).Untuk membuat program sedikit lebih pendek, saya membuat singkatan untuk
print
dan untuk!x$$6$$32
(yaitu, "6 bit terbawah!x
, dilemparkan agar dapat digunakan keprint
perpustakaan) melalui mengikat sementara mereka ke argumen lambda.Akhirnya, ada masalah output. Verity menyediakan
print
perpustakaan yang dimaksudkan untuk hasil debug. Pada simulator, ini mencetak kode ASCII ke output standar, yang dapat digunakan untuk menguji program. Pada papan sirkuit fisik, itu tergantung padaprint
perpustakaan yang telah ditulis untuk chip tertentu dan papan di sekitarnya; adaprint
perpustakaan di distribusi Verity untuk papan evaluasi yang saya punya akses untuk mencetak output pada tampilan tujuh-segmen. Mengingat bahwa perpustakaan pada akhirnya akan mengambil ruang pada papan sirkuit yang dihasilkan, mungkin ada baiknya menggunakan bahasa yang berbeda untuk solusi yang dioptimalkan untuk masalah ini sehingga kami dapat menampilkan bit-bit output langsung pada kabel.Omong-omong, program ini adalah O (n²) pada perangkat keras, artinya jauh lebih buruk pada simulator (saya curiga O (n⁴); meskipun tidak yakin, tetapi cukup sulit untuk mensimulasikan bahwa sepertinya tidak mungkin bahkan kubik , dan berdasarkan pada bagaimana waktu bereaksi terhadap perubahan saya ketika saya menulis program, fungsinya tampaknya berkembang sangat cepat). Kompilator Verity membutuhkan 436 pass optimasi (yang jauh, jauh lebih banyak daripada biasanya) untuk mengoptimalkan program, dan bahkan setelah itu, mensimulasikan itu sangat sulit untuk laptop saya. Proses kompilasi-dan-simulasi lengkap membutuhkan waktu berikut:
dan memuncak pada 2740232 kibiby memori. Program ini membutuhkan total siklus 213646 untuk dijalankan. Tapi itu berhasil!
Bagaimanapun, jawaban ini tidak benar-benar memenuhi pertanyaan karena saya mengoptimalkan untuk hal yang salah, tetapi melihat karena belum ada jawaban lain, ini adalah yang terbaik secara default (dan itu menyenangkan untuk melihat seperti apa palu golf akan terlihat seperti di bahasa perangkat keras). Saat ini saya tidak yakin apakah saya akan bekerja pada suatu program yang bertujuan untuk menghasilkan ouptut yang lebih optimal pada chip. (Kemungkinan akan jauh lebih besar dalam hal sumber, karena O (n) pengkodean data akan lebih kompleks daripada yang terlihat di sini.)
sumber
veritygos.org
untuk memeriksa ...