Ihre Aufgabe ist es, ein Programm in einer x86-Maschinensprache (eine beliebige Version) zu schreiben, das so viele Anweisungen wie möglich durchläuft und dann mit maximal 32 Byte Code angehalten wird und mit nullen Registern beginnt.
Sie können alles über den Arbeitsspeicher annehmen, den Sie mögen, solange er in einem für den x86-Computer verwendbaren Format vorliegt.
Antworten:
2 524224 Anweisungen
Mein Programm:
(Technischer Hinweis: Dies ist für nasm geschrieben Die.
a32
Syntax nasm ist für die alternative Adresse Größe Präfix - Byte Für masm Sie die ersetzen würde.a32
Mitdefb 0x67
.)Zur Verdeutlichung hier die Ausgabe der Auflistung:
Das Programm geht davon aus, dass sich der Prozessor im Real-Modus befindet und dass sich das Programm am unteren Rand eines 64-KB-Speichersegments befindet, das ansonsten auf All-Bit-Null initialisiert wird. Das Design ist einfach: Behandeln Sie den Speicher als eine einzelne riesige Ganzzahl ohne Vorzeichen und erhöhen Sie ihn um alle möglichen Werte, bis er wieder auf Null gesetzt wird. Wiederholen Sie diese 2 32 Mal. Dann halt an.
Die innerste Schleife (Zeilen 4‒6) ist für die Inkrementierung der großen Ganzzahl verantwortlich. Jede Iteration fügt einem einzelnen Byte null oder eins hinzu, je nachdem, ob das vorherige Byte ausgeführt wurde. Beachten Sie, dass auf jedes Byte in der großen Ganzzahl zugegriffen wird, unabhängig davon, ob es sich geändert hat oder nicht. Daher wiederholt diese Schleife immer 2 16 - 14 Mal.
Übrigens, falls Sie sich fragen, dieser Code zeigt den Grund, warum die x86
inc
/dec
-Anweisungen das Übertragsflag nicht beeinflussen: Nur um diese Art von Mehrbyte-Übertragungsmuster zu vereinfachen. (Dieses Muster trat in den Tagen von 8-Bit-Mikroprozessoren häufiger auf, als der ursprüngliche 8080-Befehlssatz definiert wurde.)Zeile 7 bewirkt, dass der Inkrementierungsprozess wiederholt wird, bis eine Eins aus dem letzten Byte ausgeführt wird, was anzeigt, dass die große Ganzzahl auf alle Bits Null zurückgesetzt wurde. Dies dauert lange.
Die Zeilen 8 bis 9 markieren die äußerste Schleife und bewirken, dass dieser Vorgang 32 Mal wiederholt wird, bis das
ecx
Register auf Null rollt. Dies entspricht effektiv dem Hinzufügen weiterer 32 Bit zur riesigen Ganzzahl.Es wäre möglich, eine weitere äußere Schleife hinzuzufügen und dies erneut zu tun, indem (sagen wir) das
edx
Register verwendet wird, und dann möglicherweiseesi
undedi
für noch mehr Wiederholungen. Es lohnt sich jedoch nicht. Die Anweisungen zum Inkrementieren und Schleifen erfordern vier Bytes. Diese vier Bytes werden von der riesigen Ganzzahl entfernt. Wir verlieren also 32 Bit auf dem RAM-Zähler, nur um 32 Bit über ein Register hinzuzufügen: Es wird eine Wäsche. Der einzige Grundecx
für eine Ausnahme ist, dass es einen speziellenloop
Befehl gibt, der nur in drei Bytes passt. Somit tauscht das Programm 24 Bit gegen 32 Bit, eine winzige, aber immer noch positive Verstärkung von 8 Bit.Es ist nicht allzu schwer, die Anzahl der Anweisungen, die das Programm ausführt, direkt zu berechnen, bevor es angehalten wird. Es gibt jedoch eine viel einfachere Möglichkeit, diese Anzahl zu schätzen. Das Programm ändert seinen gesamten Speicher abzüglich der 14 Bytes, die das Programm enthalten, und der Register
bx
undecx
. Dies ergibt 2 16 - 14 + 2 + 4 = 65528 Bytes für insgesamt 524224 Bits. Die Verknüpfung beinhaltet die Erkenntnis, dass während des Ausführens jedes einzelne mögliche Muster von 524224 Bits genau einmal erscheint. Für den RAM und dasecx
Register ist dies leicht zu erkennen, da das Programm jeden einzelnen Wert inkrementiert. Zumbx
Dies ist etwas weniger offensichtlich, da es gleichzeitig mit der Aktualisierung des Speicherwerts geändert wird. Man kann jedoch zeigen, dass sich das Programm angesichts der Struktur des Programms in einer Endlosschleife befinden müsste, wenn ein vollständiges Bitmuster tatsächlich zweimal auftreten würde. Da dies nicht der Fall ist, muss jedes Bitmuster letztendlich nur einmal besucht werden. (Der vollständige Beweis wird natürlich dem Leser als Übung überlassen.)Da jedes mögliche Bitmuster im Verlauf des Programms auftritt, muss das Programm mindestens 2 524224- Befehle ausführen , was ungefähr 1,4 × 10 157807 entspricht . (Die akute Zahl ist aufgrund der Sprunganweisungen sehr geringfügig höher, aber der Unterschied bei dieser Größe ist vernachlässigbar.)
Offensichtlich könnte dies durch die Verwendung von mehr als 64 KB RAM erheblich verbessert werden. Ich halte die nächste Version des Codes zurück, bis ich genau herausgefunden habe, auf wie viel RAM zugegriffen werden kann.
quelle
~ 2 ^ (2 ^ 67) Anweisungen
(at & t Syntax)
Zerlegt, 26 Bytes:
Ähnlich wie bei der Breadbox-Lösung, aber es gibt keinen Grund, bei 16 Bit Adresse anzuhalten. Mein Code verwendet x86-64 und geht davon aus, dass wir 2 ^ 64 Byte Speicher haben und alle außer dem Speicher, der den Code enthält, als riesigen Zähler verwenden.
quelle