Verilog, flächenoptimiert, 130 LE-Tore
Das Quine selbst (die eigentliche Datei ist in DEC SIXBIT codiert ):
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
Lesbare Version mit Kommentaren und einer 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
Durch die Verwendung von Verilog habe ich erheblich mehr Kontrolle über die Details auf niedriger Ebene als mit Verity. Insbesondere kann ich damit die Uhr steuern und die Regeln selbst zurücksetzen. Dieses Programm ist für eine synchrone serielle Verbindung mit Strobe-Eingang sund Datenausgang vorgesehend. Obwohl jedes nur in einer Richtung verwendet wird, habe ich beide als bidirektional deklariert, um einige Bytes zu sparen. Ich musste die Nicht-Daten-Teile des Programms auf 1024 Bit reduzieren, um 10-Bit-Logikgatter intern verwenden zu können (zusätzliche Bits wären flächenmäßig teurer), und es kratzt nur knapp unter 1008, also Einsparungen wie das ist wichtig. Um eine beträchtliche Menge an Code zu sparen, verlasse ich mich auf die Hardware-Reset-Schaltung des FPGA, anstatt meine eigene hinzuzufügen, und füge die Strobe- und Clock-Eingänge zusammen (ein alter Trick, der heutzutage verpönt ist, weil er es schwierig macht um den Uhrenbaum bei hohen Taktraten im Gleichgewicht zu halten, aber es ist nützlich zum Golfen.) Ich hoffe, das ist synthetisierbar; Ich weiß nicht, wie gut Verilog-Synthesizer mit der Verwendung eines bidirektionalen Ports als Uhr umgehen können.
Die Quelle ist in DEC SIXBIT codiert (ich gehe hier davon aus, dass wir das einzelne Buchstabenalphabet als Kleinbuchstaben interpretieren; ein Verilog-Synthesizer hätte keinen Grund, eine Großbuchstabeninterpretation zu verwenden). Ich habe in meiner anderen Lösung intern einen Sechs-Bit-Zeichensatz verwendet und dann Bytes verschwendet, um ihn zu konvertieren. Es ist besser, einen Zeichensatz zu verwenden, der "natürlich" sechs Bit breit ist, damit keine Konvertierung erforderlich ist. Ich habe diesen speziellen Sechs-Bit-Zeichensatz ausgewählt, weil 0und 1sich nur in ihrem niedrigstwertigen Bit unterscheiden und nur ein anderes Bit gesetzt ist, was bedeutet, dass die Schaltung zum Konvertieren einer Binärziffer in DEC SIXBIT (dh "Escape" einer Zeichenfolge) sehr sein kann einfach. Interessanterweise fehlt dem fraglichen Zeichensatz ein Zeilenumbruchzeichen. Das ursprüngliche Programm ist nicht nur in einer Zeileum das Generieren zu vereinfachen, aber das Codieren zu ermöglichen! Es ist gut, dass Verilog sich hauptsächlich nicht um Leerzeichen kümmert.
Das Protokoll zum Senden von Daten an den Host basiert auf der synchronen seriellen Schnittstelle. Ich habe es ausgewählt, weil es getaktet ist (was mir erlaubt, den Clock / Strobe-Trick zu verwenden und ein tragbares Programm zu schreiben, das nicht auf On-Chip-Timing-Geräten basiert) und weil es sehr einfach ist (also nicht müssen viel Code verschwenden, um es zu implementieren). Dieses Protokoll gibt keine Methode zum Festlegen an, wo die Nachricht endet (der Host soll es wissen). In diesem speziellen Fall habe ich die Ausgabe mit Null-Bits (insgesamt 16 Füllbits) auf ein Vielfaches von 1024 Bits aufgefüllt. Danach wird die Nachricht (wie von SSI gefordert) neu gestartet. (Ich implementiere keinen Timer für den Leerlaufmodus. Er dient dazu zu bestimmen, ob eine neue Nachricht gesendet oder die vorherige Nachricht wiederholt werden soll. Da dieses Programm immer seinen eigenen Quellcode als Nachricht sendet, ist die Unterscheidung nicht sichtbar Sie können es als Länge 0 betrachten,
In Bezug auf die tatsächliche Logik ist das Interessanteste die Art und Weise, wie ich die Variablen aufteile, um die auf dem Chip benötigte Fläche zu reduzieren. iDas größere Register enthält die aktuelle "Adresse" in den Programmdaten und wird immer nur durch Inkrementieren geändert. Dies bedeutet, dass seine Logik mithilfe der Halbaddierer-Konstruktion synthetisiert werden kann (die, wie der Name schon sagt, nur die Hälfte der Ressourcen eines Addierers verbraucht; dies ist meist nur bei den kleinsten FPGAs von Bedeutung, bei größeren mit 3 Eingängen oder sogar 4-Eingangs-LUTs, die so leistungsfähig sind, dass sie viel verschwendete Kapazität haben, um einen Halbaddierer zu synthetisieren. Das kleinere Register,jist im Grunde ein Zustandsmaschinenzustand und behandelt daher den größten Teil der komplexen Logik des Programms. Es ist klein genug, dass es vollständig über eine Nachschlagetabelle auf einem größeren FPGA verarbeitet werden kann (wodurch die Logik im Grunde verschwindet). Für den Fall, dass das Programm für ein kleines FPGA synthetisiert wird, habe ich seine Codierung so gewählt, dass sich nur wenige Teile des Codes um alle drei Bits gleichzeitig kümmern.
Es ist auch erwähnenswert, dass ich den Datenspeicher zyklisch permutiert habe. Wir können iüberall darauf zeigen, nicht unbedingt am Anfang. Mit der hier gezeigten Anordnung können wir idirekt vom Anfangswert bis zum Ende drucken, dann das gesamte Array maskieren und dann vom Anfang bis zum Anfangswert von idrucken, um alle Teile der Daten im zu drucken richtige Orte, ohne den Wert von speichern und wiederherstellen zu müssen i. (Dieser Trick kann auch für Quines in anderen Sprachen nützlich sein.)
Die Quelle ist 1192 6-Bit-Bytes lang, was 894 8-Bit-Bytes entspricht. Es ist irgendwie peinlich, dass dies weniger Quellbytes enthält als meine Verity-Übermittlung, obwohl es für etwas ganz anderes optimiert wurde. Dies liegt hauptsächlich daran, dass Verilog Zeichenfolgen hat und Verity nicht, was bedeutet, dass ich jedes Byte des Programms codieren kann, obwohl ich das Programm eher binär als oktal codiert habe (was in Bezug auf die Quellcodegröße wesentlich weniger effizient ist) Verwenden von sechs Sechs-Bit-Zeichen (eines für jedes Bit) anstelle von acht Acht-Bit-Zeichen (vier für jede Oktalstelle). Eine Verilog-Übermittlung, die das Programm in Oktal codiert, wäre wahrscheinlich kleiner in Bezug auf die Quellcode-Größe, aber mit ziemlicher Sicherheit größer in der Fläche.
Ich weiß nicht, wie viel Fläche dieses Programm letztendlich nutzen wird. Dies hängt stark davon ab, wie leistungsfähig der Optimierer in Ihrem Verilog-Synthesizer ist (da das Minimierungsproblem beim Konvertieren der gespeicherten Daten in eine Reihe von Logikgattern im Synthesizer selbst ausgeführt wird. Wenn Sie die Arbeit auf den Synthesizer übertragen, wird der Quellcode selbst erstellt viel kürzer und reduziert somit die zum Speichern benötigte Fläche). Es sollte jedoch eine Komplexität von O (n log n) haben und daher viel kleiner sein als das O (n²) des anderen Programms. Es würde mich interessieren, wie das OP versucht, es auf seinem FPGA auszuführen. (Die Synthese kann jedoch einige Zeit in Anspruch nehmen. Sie können verschiedene Schritte ausführen, um ein Programm für die Kompilierungszeit zu optimieren, aber ich habe hier keine Schritte unternommen, da dies zu einem größeren Programm = größerer Fläche führen würde.)
Verity 0.10, optimiert für die Quellcodegröße (1944 Bytes)
Ich habe die Frage ursprünglich falsch verstanden und als Code-Golf interpretiert. Das war wahrscheinlich das Beste, da es unter den Einschränkungen in der Frage viel einfacher ist, eine Quine mit kurzem Quellcode als kurzen Objektcode zu schreiben. Das machte die Frage so einfach, dass ich das Gefühl hatte, eine vernünftige Antwort liefern zu können und als Sprungbrett auf dem Weg zu einer besseren Antwort zu fungieren. Es veranlasste mich auch, eine höhere Sprache für die Eingabe zu verwenden, was bedeutet, dass ich im Programm selbst weniger ausdrücken müsste. Ich habe Verity nicht als Golfsprache für Hardware erstellt (ich wurde tatsächlich vor einiger Zeit beauftragt, es in einem völlig anderen Kontext zu erstellen), aber es gibt dort eine ziemliche Reminiszenz (z. B. ist es wesentlich höher als ein typisches HDL, und das ist es auch hat viel weniger Boilerplate; es ist auch viel tragbarer als das typische HDL).
Ich bin mir ziemlich sicher, dass die richtige Lösung für kurzen Objektcode darin besteht, die Daten in einer Baumstruktur zu speichern, da die Frage die Verwendung des Block-ROMs verbietet, in dem Sie sie normalerweise in einem praktischen Programm speichern würden. Ich könnte versuchen, irgendwann ein Programm zu schreiben, das dieses Prinzip verwendet (nicht sicher, welche Sprache, vielleicht Verity, vielleicht Verilog; VHDL hat zu viel Boilerplate, um für diese Art von Problem wahrscheinlich optimal zu sein). Das würde bedeuten, dass Sie nicht jedes Bit des Quellcodes an jedes Bit Ihres "manuell erstellten ROM" übergeben müssen. Der Verity-Compiler synthetisiert derzeit jedoch die Struktur der Ausgabe basierend auf der Priorität und Assoziativität der Eingabe, was bedeutet, dass er den Befehlszeiger (also den Index zur Nachschlagetabelle) effektiv in unär darstellt.
Das Programm selbst:
Besser lesbar:
Die Grundidee ist, dass wir die gesamten Daten in der Variablen speichern
x. (Wie bei einem Quine üblich, haben wir einen Codeabschnitt und einen Datenabschnitt. Die Daten codieren den Text des Codes und können auch zum Neuerstellen des Textes der Daten verwendet werden.) Leider lässt Verity derzeit keine sehr großen Daten zu Konstanten, die in den Quellcode geschrieben werden sollen (es werden OCaml-Ganzzahlen während der Kompilierung verwendet, um Ganzzahlen in der Quelle darzustellen, was in einer Sprache, die beliebig breite Ganzzahltypen unterstützt, eindeutig nicht korrekt ist) - und außerdem erlaubt es keine Konstanten in oktal angegeben - also generieren wir den Wert vonxzur Laufzeit durch wiederholte Aufrufe einer Funktiona. Wir könnten eine void-Funktion erstellen und sie wiederholt als separate Anweisungen aufrufen, aber das würde es schwierig machen zu identifizieren, wo mit der Ausgabe des Textes des Datenabschnitts begonnen werden soll. Also habe ich stattdessenaeine Ganzzahl zurückgegeben und die Daten mit Arithmetik gespeichert (Verity garantiert, dass die Arithmetik von links nach rechts ausgewertet wird). Der Datenabschnitt wirdxmit einem einzelnen-Vorzeichen codiert . Wenn dies zur Laufzeit auftritt, wird es-a 5-a 1-über die Verwendung von vollständig usw. erweiterty.Das Initialisieren
yals Kopie vonxist hier ziemlich subtil. Daaspeziell Null zurückgegeben wird, ist der größte Teil der Summe nur Null minus Null minus… und bricht sich selbst ab. Wir enden mit!x(dh "dem Wert vonx"; in Verity wie in OCaml funktioniert der Name einer Variablen eher wie ein Zeiger als alles andere, und Sie müssen ihn explizit dereferenzieren, um den Wert der Variablen zu erhalten). Veritys Regeln für unäres Minus sind ein wenig komplex - das unäre Minus vonvwird als geschrieben(-v)-(-0-0-0-!x)analysiert also als(-(0-0-0-!x)), was gleich ist!x, und wir werden am Endeyals Kopie von initialisiertx. (Es ist auch erwähnenswert, dass Verity nicht istCall-by-Value, sondern ermöglicht es Funktionen und Operatoren, die Reihenfolge zu wählen, in der sie die Dinge bewerten.-bewertet das linke Argument vor dem rechten Argument, und insbesondere wenn das linke Argument Nebenwirkungen hat, werden diese sichtbar, wenn das rechte Argument ausgewertet wird.)Jedes Zeichen des Quellcodes wird mit zwei Oktalziffern dargestellt. Dies bedeutet, dass der Quellcode auf 64 verschiedene Zeichen beschränkt ist, sodass ich meine eigene Codepage für den internen Gebrauch erstellen musste. Die Ausgabe erfolgt in ASCII, daher musste ich intern konvertieren. Dafür ist das da
(if z<32 then z+92 else z). Hier ist der Zeichensatz, den ich in der internen Darstellung verwendet habe, in numerischer Reihenfolge (dh\hat Codepunkt 0,?hat Codepunkt 63):Dieser Zeichensatz gibt uns die meisten für Verity wichtigen Zeichen. Bemerkenswerte fehlende Zeichen sind
}(was bedeutet, dass wir keinen Block mit erstellen können{}, aber zum Glück sind alle Anweisungen Ausdrücke, sodass wir()stattdessen verwenden können); und|(aus diesem Grund musste ich beim Erstellen des Werts von ein exklusives statt einschließendes ODER verwendenx, was bedeutet, dass ich es auf 0 initialisieren muss; ich musste jedoch angeben, wie groß es trotzdem war). Einige der kritischen Zeichen, die ich sicherstellen wollte, befanden sich im Zeichensatz:<>(für Importe, auch Verschiebungen)()(sehr schwer zu schreiben, ein Programm, das ohne diese analysiert werden kann),$(für alles, was mit Bitbreite zu tun hat) und\( Für Lambdas könnten wir theoretisch damit umgehenlet…inaber es wäre viel ausführlicher).Um das Programm etwas kürzer zu machen, habe ich Abkürzungen für
printund für!x$$6$$32(dh "die unteren 6 Bits von!x, die für dieprintBibliothek verwendbar sind ) erstellt , indem ich sie vorübergehend an Lambda-Argumente gebunden habe.Schließlich gibt es das Problem der Ausgabe. Verity bietet eine
printBibliothek, die für die Debug-Ausgabe vorgesehen ist. Auf einem Simulator werden die ASCII-Codes auf die Standardausgabe gedruckt, die perfekt zum Testen des Programms verwendet werden kann. Auf einer physischen Leiterplatte hängt es davon ab, dass eineprintBibliothek für den bestimmten Chip und die Platine geschrieben wurde, die sie umgeben.printIn der Verity-Distribution befindet sich eine Bibliothek für eine Evaluierungskarte, auf die ich Zugriff hatte und die die Ausgabe auf Sieben-Segment-Displays druckt. Angesichts der Tatsache, dass die Bibliothek am Ende Platz auf der resultierenden Leiterplatte beansprucht, kann es sinnvoll sein, eine andere Sprache für eine optimierte Lösung dieses Problems zu verwenden, damit wir die Bits der Ausgabe direkt auf Drähten ausgeben können.Übrigens ist dieses Programm auf der Hardware O (n²), was bedeutet, dass es auf einem Simulator viel schlimmer ist (ich vermute O (n⁴); ich bin mir zwar nicht sicher, aber es war schwer genug zu simulieren, dass es unwahrscheinlich ist, dass es überhaupt kubisch ist und basierend darauf, wie die Zeit auf meine Änderungen reagierte, als ich das Programm schrieb, scheint die Funktion tatsächlich sehr schnell zu wachsen. Der Verity-Compiler benötigte 436 Optimierungsdurchläufe (was viel, viel mehr ist als normalerweise), um das Programm zu optimieren, und selbst danach war es für meinen Laptop sehr schwierig, es zu simulieren. Der vollständige Kompilierungs- und Simulationslauf dauerte folgende Zeit:
und erreichte einen Höchstwert von 2740232 Kibibyte Speicher. Das Programm benötigt insgesamt 213646 Taktzyklen. Es funktioniert aber!
Wie auch immer, diese Antwort erfüllt die Frage nicht wirklich, da ich für das Falsche optimiert habe, aber da es noch keine anderen Antworten gibt, ist dies standardmäßig die beste (und es ist schön zu sehen, wie eine Golf-Quine aussehen würde eine Hardwaresprache). Ich bin mir derzeit nicht sicher, ob ich an einem Programm arbeiten werde, das darauf abzielt, einen optimierten Ausgang auf dem Chip zu erzeugen. (Es wäre wahrscheinlich viel größer in Bezug auf die Quelle, da eine O (n) -Datencodierung ziemlich komplexer wäre als die hier gezeigte.)
quelle
veritygos.orgzu überprüfen ...