Brainfuck-> Compilateur de code d'octet Java

J'ai créé un programme pour compiler le code source de Brainfuck en code octet Java, alors prenez note. Je n'expliquerai pas le code d'octet Java en détail. Normalement, j'utiliserais une bibliothèque telle que ASM, mais comme c'est un gros problème, j'écrirai les octets à la main.

The Java Virtual Machine Specification Voir le chapitre 4 pour les fichiers de classe et le chapitre 6 pour les jeux d'instructions.

Qu'est-ce que Brainfuck?

Wikipedia

Turing Un langage de programmation complet avec seulement huit instructions. Pas pratique mais intéressant. En gros, l'environnement d'exécution de Brainfuck a un tableau d'octets et des pointeurs vers ses éléments, et on a l'impression de l'utiliser avec un jeu d'instructions. Voir le lien pour plus de détails.

Préparation

Puisqu'il n'est pas possible de créer des tableaux d'octets de différentes manières, définissez d'abord une méthode pratique pour écrire des octets ensemble.

/**
 * 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) {
                //Il semble que certaines langues ne puissent pas être mises en correspondance
                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;
    }

}

Reçoit un objet avec un argument de longueur variable et l'écrit dans un OutputStream en fonction de son type. ʻOutputStream.write (int) `est une méthode qui ignore les 24 bits supérieurs de l'argument int et écrit (Java int est de 4 octets). Sans lui, les littéraux hexadécimaux de Java sont signés, de sorte que le bit le plus significatif ne peut pas écrire une valeur valide. (Par exemple, lorsque vous essayez d'écrire «0xCA», il est considéré comme de type int au lieu d'octet, et il ne peut pas être utilisé dans la méthode qui prend byte comme argument).

Ensuite, définissez un assistant qui convertit int en un tableau d'octets de 4 octets / 2 octets et l'écrit. Cela ignore également les bits de poids fort.

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();
}

Pour la version 4 octets uniquement, accédez à Guava [Ints.toByteArray ()](http://google.github.io/guava/releases/snapshot-jre/api/docs/com/google/common/primitives/Ints.html#toByteArray Il y a -int-), mais comme une version 2 octets est également requise, elle est définie de manière unique. (Quand j'y pense maintenant, je suis content de Shorts.toByteArray ())

compiler

Les spécifications du code d'octet de sortie sont les suivantes.

En bref, il vous permet d'exécuter le bytecode converti par java Main.

Préparation

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

Il n'y a rien de spécial à mentionner. Écrivez du code d'octet Java ordinaire.

Il n'a pas <init> car il n'a pas besoin d'être instancié. La version de code d'octet est 49 car il est gênant d'avoir besoin d'une carte de pile à partir de 50. (Voir ici pour les cartes de pile (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

La méthode compileCodes () effectue la conversion du bytecode Brainfuck-Java.

Conversion de bytecode Brainfuck-Java

Tout d'abord, préparez l'environnement.


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
);

Faites d'abord un tampon.

sipush 30000
newarray int
astore_0

Ce que j'ai fait une erreur a été de créer un tableau d'entiers au lieu d'octets. Je m'en fiche, je m'en fiche ...

Créez ensuite un pointeur d'instructions.

iconst_0
istore_1

compileCodeElements()

Enfin, la conversion de code réelle.

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

C'est facile parce que vous n'avez pas besoin d'un lexer ou d'un analyseur. Lisez un caractère directement à partir du flux et branchez le jeton avec le commutateur.

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

stack_1.png

dup2 est une instruction pour dupliquer les deux premiers de la pile. Lisez les valeurs du tableau avec ʻiaload` et enregistrez-le.

Ce que vous faites, c'est simplement en ajouter un. C'est vrai.

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

C'est presque la même chose que «+» simplement en ajoutant «-1».

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

<

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

Les variables locales peuvent être incrémentées / décrémentées avec l'instruction ʻiinc`, donc elles peuvent être écrites avec une seule instruction.

.

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

Je veux le sortir sous forme de chaîne de caractères, donc convertissez int en char puis appelez System.out.print (char).

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 () renvoie int, donc enregistrez-le tel quel dans le tableau.

[

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

La boucle appelle une autre méthode. Si vous appelez réciproquement compileLoop () et compileElement (), vous pouvez écrire le processus proprement.

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
);

Tout d'abord, lisez la valeur du tampon pointé par le pointeur actuel. Vérifiez s'il vaut 0 avec l'instruction ʻifeq, et s'il vaut 0, sautez à la fin de la boucle, sinon procédez. A la fin du traitement, goto revient au début de la boucle. La raison d'ajouter 6 à la longueur du code est d'exclure la longueur des instructions ʻifeq et goto.

Au début, je pensais que les coordonnées spécifiées de la destination du saut étaient absolues, donc je craignais que cela ne fonctionne pas pour une raison quelconque. En fait, spécifiez la taille relative de votre emplacement actuel. Il est beaucoup plus facile de générer du code. J'ai été impressionné par le fait que c'était bien pensé (petite sensation moyenne).

Comme mentionné ci-dessus, les boucles sont traitées en utilisant la récurrence mutuelle, de sorte que vous pouvez connaître la destination du saut sans compter le nombre de boucles comme l'interpréteur BF que vous voyez souvent.

]

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

Quittez le processus et quittez la boucle. S'il est appelé sans correspondance [, le processus se terminera. Comme je ne pouvais pas trouver la spécification lorsqu'aucune correspondance n'était trouvée, je l'ai considérée comme non définie et je l'ai facilitée. Il peut être plus gentil de faire une erreur de compilation.

optimisation

TODO

Je le ferai un jour en me référant à article POSTD.

Impressions

prime

Article original (Cet article Qiita est un raffinement de cet article) Dépôt

Recommended Posts

Brainfuck-> Compilateur de code d'octet Java
Java
Java
[Java] Comment résoudre un bogue dans le compilateur JDK
noyau Java: le compilateur HotSpot plante sur SIGSEGV