Brainfuck-> Java Byte Code Compiler

Ich habe ein Programm erstellt, um Brainfuck-Quellcode in Java-Bytecode zu kompilieren. Machen Sie sich also eine Notiz. Ich werde den Java-Bytecode nicht im Detail erklären. Normalerweise würde ich eine Bibliothek wie ASM verwenden, aber da es eine große Sache ist, werde ich die Bytes handschriftlich schreiben.

The Java Virtual Machine Specification Siehe Kapitel 4 für Klassendateien und Kapitel 6 für Befehlssätze.

Was ist Brainfuck?

Wikipedia

Turing Eine komplette Programmiersprache mit nur acht Anweisungen. Nicht praktisch, aber interessant. Grob gesagt verfügt die Brainfuck-Ausführungsumgebung über ein Byte-Array und Zeiger auf ihre Elemente, und es fühlt sich an, als würde sie mit einem Befehlssatz betrieben. Siehe den Link für Details.

Vorbereitung

Da es nicht möglich ist, Byte-Arrays auf unterschiedliche Weise zu erstellen, definieren Sie zunächst eine bequeme Methode zum gemeinsamen Schreiben von Bytes.

/**
 * Helper class to create byte array fluently.
 */
public final class FluentByteWriter {

    private final OutputStream os;

    public FluentByteWriter(OutputStream os) {
        this.os = os;
    }

    public FluentByteWriter write(Object... bytes) {

        try {
            for (Object o : bytes) {
                //Es scheint einige Sprachen zu geben, die nicht mit Mustern übereinstimmen können
                if (o instanceof Integer) {
                    os.write((Integer) o);  // Note high-order bits are ignored
                } else if (o instanceof Byte) {
                    os.write((Byte) o);
                } else if (o instanceof byte[]) {
                    os.write((byte[]) o);
                } else if (o instanceof String) {
                    os.write(((String) o).getBytes(StandardCharsets.UTF_8));
                } else {
                    throw new UnsupportedOperationException("Unwritable class: " + o.getClass().getCanonicalName());
                }
            }
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }

        return this;
    }

}

Empfängt ein Objekt mit einem Argument variabler Länge und schreibt es entsprechend seinem Typ in einen OutputStream. OutputStream.write (int) ist eine Methode, die die oberen 24 Bits des Arguments int ignoriert und schreibt (Java int ist 4 Byte). Ohne sie sind die hexadezimalen Literale von Java signiert, sodass das höchstwertige Bit keinen gültigen Wert schreiben kann. (Wenn Sie beispielsweise versuchen, "0xCA" zu schreiben, wird dies als int-Typ anstelle von Byte betrachtet und kann nicht in der Methode verwendet werden, die Byte als Argument verwendet.)

Definieren Sie als Nächstes einen Helfer, der int in ein 4-Byte / 2-Byte-Byte-Array konvertiert und schreibt. Dies ignoriert auch die höherwertigen Bits.

public static byte[] toByteArray4(int n) {
    return ByteBuffer.allocate(4).putInt(n).array();
}
public static byte[] toByteArray2(short n) {
    return ByteBuffer.allocate(2).putShort(n).array();
}

Nur für eine 4-Byte-Version gehen Sie zu Guava Ints.toByteArray () Es gibt -int-), aber da auch eine 2-Byte-Version erforderlich ist, ist diese eindeutig definiert. (Wenn ich jetzt darüber nachdenke, bin ich mit Shorts.toByteArray () zufrieden.)

kompilieren

Die Spezifikationen des Ausgabebytecodes sind wie folgt.

Kurz gesagt, es ermöglicht Ihnen, Bytecode auszuführen, der von "Java Main" konvertiert wurde.

Vorbereitung

0xCA, 0xFE, 0xBA, 0xBE, // CAFEBABE
0x00, 0x00,  // miner version: 0
0x00, 0x31,  // major version: 49  // Version 49 doesn't require stack map
0x00, 0x20,  // constant pool count: 31 + 1
// constant pool
0x07, 0x00, 0x02,  // 1. class: Main
0x01, 0x00, 0x04,  // 2. utf8
"Main",
0x07, 0x00, 0x04,  // 3. class: java/lang/Object
0x01, 0x00, 0x10,  // 4. utf8
"java/lang/Object",
// System.out.print
0x09, 0x00, 0x06, 0x00, 0x08,  // 5. fieldref System.out
0x07, 0x00, 0x07,  // 6. class
0x01, 0x00, 0x10,  // 7. utf8
"java/lang/System",
0x0C, 0x00, 0x09, 0x00, 0x0A,  // 8. name and type
0x01, 0x00, 0x03,  // 9. utf8
"out",
0x01, 0x00, 0x15,  // 10. utf8
"Ljava/io/PrintStream;",
0x0A, 0x00, 0x0C, 0x00, 0x0E,  // 11. method PrintStream.print(int)
0x07, 0x00, 0x0D,  // 12. class
0x01, 0x00, 0x13,  // 13. utf8
"java/io/PrintStream",
0x0C, 0x00, 0x0F, 0x00, 0x10,  // 14. name and type
0x01, 0x00, 0x05,  // 15. utf8
"print",
0x01, 0x00, 0x04,  // 16. utf8
"(C)V",
// System.in.read(int)
0x09, 0x00, 0x06, 0x00, 0x12,  // 17. fieldref System.in
0x0C, 0x00, 0x13, 0x00, 0x14,  // 18. name and type
0x01, 0x00, 0x02,  // 19. utf8
"in",
0x01, 0x00, 0x15,  // 20. utf8
"Ljava/io/InputStream;",
0x0A, 0x00, 0x16, 0x00, 0x18,  // 21. method InputStream.read(int)
0x07, 0x00, 0x17,  // 22. class
0x01, 0x00, 0x13,  // 23. utf8
"java/io/InputStream",
0x0C, 0x00, 0x19, 0x00, 0x1A,  // 24. name and type
0x01, 0x00, 0x04,  // 25. utf8
"read",
0x01, 0x00, 0x3,  // 26. utf8
"()I",
// main
0x01, 0x00, 0x04,  // 27. utf8
"main",
0x01, 0x00, 0x16,  // 28. utf8
"([Ljava/lang/String;)V",
0x01, 0x00, 0x04,  // 29. utf8
"args",
0x01, 0x00, 0x13,  // 30. utf8
"[Ljava/lang/String;",
// "Code" for Attribute
0x01, 0x00, 0x04,  // 31. utf8
"Code",
0x00, 0x21,  // access_flags: ACC_SUPER ACC_PUBLIC
0x00, 0x01,  // this class
0x00, 0x03,  // super class
0x00, 0x00,  // interfaces count
// interfaces[]
//NOP
0x00, 0x00,  // fields count
// fields[]
// NOP
0x00, 0x01,  // method count

Es gibt nichts Besonderes zu erwähnen. Schreiben Sie normalen Java-Bytecode.

Es hat kein , da es nicht instanziiert werden muss. Die Bytecode-Version ist 49, da es schwierig ist, eine Stapelzuordnung von 50 zu benötigen. (Stapelkarten finden Sie hier (https://docs.oracle.com/javase/specs/jvms/se9/html/jvms-4.html#jvms-4.10))

        // methods[]
        // main
        0x00, 0x09,  // access flags: ACC_PUBLIC ACC_STATIC
        0x00, 0x1B,  // name index: main
        0x00, 0x1C,  // descriptor index
        0x00, 0x01,  // attributes count
        // attribute info
        0x00, 0x1F  // attribute name index: Code
);
byte[] code = compileCodes(is);
w.write(
        ByteUtils.toByteArray4(code.length + 12),  // attribute length
        // info
        0x00, 0x04,  // max stack
        0x00, 0x02,  // max locals
        // code length
        ByteUtils.toByteArray4(code.length),
        // code
        code,
        0x00, 0x00,  // exception table length
        // exception table
        // NOP
        0x00, 0x00,  // attribute count
        // attribute info[]
        // NOP
        // class attributes count
        0x00, 0x00
        // attributes
        // NOP

Die Methode compileCodes () führt die eigentliche Brainfuck-Java-Bytecode-Konvertierung durch.

Brainfuck-Java-Bytecode-Konvertierung

Bereiten Sie zuerst die Umgebung vor.


w.write(
        // creates data buffer
        0x11, 0x75, 0x30,  // sipush 30000
        0xBC, 0x0A,        // newarray int
        0x4B,              // astore_0  // ignore application arguments (String[] args)
        // creates instruction pointer
        0x03,              // iconst_0
        0x3C               // istore_1
);
w.write(
        compileCodeElements(is),
        0xB1  // return
);

Machen Sie zuerst einen Puffer.

sipush 30000
newarray int
astore_0

Was ich falsch gemacht habe, war ein Array von Ints anstelle von Bytes. Es ist mir egal, es ist mir egal ...

Dann machen Sie einen Anweisungszeiger.

iconst_0
istore_1

compileCodeElements()

Endlich die eigentliche Codekonvertierung.

while ((i = is.read()) >= 0) {
    switch (i) {
    case ('+'):
        // ...
        break;
    case ('-'):
        // ...
        break;
    /*
     * ....

Es ist einfach, weil Sie keinen Lexer oder Parser benötigen. Lesen Sie ein Zeichen direkt aus dem Stream und verzweigen Sie das Token mit dem Schalter.

0x2A,  // aload_0
0x1B,  // iload_1
0x5C,  // dup2
0x2E,  // iaload
0x04,  // iconst_1
0x60,  // iadd
0x4F   // iastore

stack_1.png

dup2 ist eine Anweisung zum Duplizieren der beiden obersten Stapel. Lesen Sie die Array-Werte mit "iaload" und speichern Sie sie.

Was Sie tun, ist nur eine hinzuzufügen. Korrekt.

0x2A,  // aload_0
0x1B,  // iload_1
0x5C,  // dup2
0x2E,  // iaload
0x02,  // iconst_m1
0x60,  // iadd
0x4F   // iastore

Es ist fast dasselbe wie "+", nur durch Hinzufügen von "-1".

0x84, 0x01, 0x01  // iinc 1 1

<

0x84, 0x01, 0xFF  // iinc 1 -1

Lokale Variablen können mit der Anweisung "iinc" inkrementiert / dekrementiert werden, sodass sie mit nur einer Anweisung geschrieben werden können.

.

0xB2, 0x00, 0x05,  // getstatic System.out
0x2A,              // aload_0
0x1B,              // iload_1
0x2E,              // iaload
0x92,              // i2c
0xB6, 0x00, 0x0B   // invokevirtual print(C)V

Ich möchte es als Zeichenfolge ausgeben, also konvertiere int in char und rufe dann "System.out.print (char)" auf.

stack_2.png

,

0x2A,              // aload_0
0x1B,              // iload_1
0xB2, 0x00, 0x11,  // getstatic System.in
0xB6, 0x00, 0x15,  // invokevirtual read()I
0x4F               // iastore

System.in.read () gibt int zurück, also speichern Sie es so wie es im Array ist.

[

w.write((Object) compileLoop(is));

Die Schleife ruft eine andere Methode auf. Wenn Sie "compileLoop ()" und "compileElement ()" gegenseitig aufrufen, können Sie den Prozess sauber schreiben.

w.write(
        // load current pointer value
        0x2A,  // aload_0
        0x1B,  // iload_1
        0x2E   // iaload
);
byte[] insideLoop = compileCodeElements(is);
w.write(
        // if the current pointer indicates 0...
        // 6 = ifeq(3) + goto(3)
        0x99, ByteUtils.toByteArray2(insideLoop.length + 6),    // ifeq
        insideLoop,
        0xA7, ByteUtils.toByteArray2(-(insideLoop.length + 6))  // goto
);

Lesen Sie zuerst den Wert des Puffers, auf den der aktuelle Zeiger zeigt. Der Befehl ifeq prüft, ob er 0 ist, und wenn er 0 ist, springt er zum Ende der Schleife, andernfalls verarbeitet er. Am Ende der Verarbeitung kehrt goto zum Anfang der Schleife zurück. Der Grund für das Hinzufügen von 6 zur Codelänge besteht darin, die Länge der Anweisungen "ifeq" und "goto" auszuschließen.

Zuerst dachte ich, dass die angegebenen Koordinaten des Sprungziels absolut sind, also befürchtete ich, dass es aus irgendeinem Grund nicht funktionieren würde. Geben Sie tatsächlich die relative Größe Ihres aktuellen Standorts an. Es ist viel einfacher, Code zu generieren. Ich war beeindruckt, dass es gut durchdacht war (kleines Durchschnittsgefühl).

Wie oben erwähnt, werden Schleifen durch gegenseitige Wiederholung verarbeitet, sodass Sie das Sprungziel kennen können, ohne die Anzahl der Schleifen wie den häufig angezeigten BF-Interpreter zu zählen.

]

case (']'):
    // exit loop
    return baos.toByteArray();

Beenden Sie den Prozess und verlassen Sie die Schleife. Wenn es ohne ein übereinstimmendes [ aufgerufen wird, wird der Prozess beendet. Da ich die Spezifikation nicht finden konnte, als keine Übereinstimmung gefunden wurde, betrachtete ich sie als undefiniert und machte es einfacher. Es kann freundlicher sein, einen Kompilierungsfehler zu machen.

Optimierung

TODO

Ich werde es eines Tages tun, indem ich mich auf [POSTD-Artikel] beziehe (http://postd.cc/adventures-in-jit-compilation-part-1-an-interpreter/).

Impressionen

Bonus

Originalartikel (Dieser Qiita-Artikel ist eine Verfeinerung dieses Artikels) Repository

Recommended Posts

Brainfuck-> Java Byte Code Compiler
Java
Java
[Java] Einen Fehler im JDK-Compiler beheben
Java-Kern: HotSpot-Compiler stürzt unter SIGSEGV ab