SimpleVM #8: Details & Loading from File

Category: 

In diesem Artikel vervollständigen wir unsere SimpleVM und erweitern sie außerdem um die Möglichkeit ein Programm aus einer Datei zu laden.

Dieser Artikel ist Teil der Serie: Simple Virtual Machine
#1 Einstieg
#2 Prototyp
#3 Bedingte Sprünge
#4 Funktionen
#5 OOP
#6 Globale Variablen und Java Funktionen
#7 Operator overloading
#8 Details & Loading from File
#9 Bonus: Assemblercode

Zusätzliche Bytecodes

Im Grunde haben wir bereits die wichtigsten Bytecodes, jedoch gibt es noch ein paar wenige, welche das Arbeiten angenehmer machen. Beispielsweise können wir bisher nur ein einzelnes Byte auf den Stack legen. Größere Zahlen und Gleitkommazahlen können wir bisher gar nicht auf den Stack legen. Dazu erzeugen wir nun drei neue OpCodes, je einen um einen short, int und float auf den Stack zu legen. Dabei müssen wir den jeweligen Wert aus mehreren nachfolgenden Bytes zusammensetzen. Die passenden Umwandlungsfunktionen lege ich in eine neue Klasse namens "BitConverter":

package com.infectedbytes.tutorials.simplevm;

public class BitConverter {
  public static short getShort(byte a, byte b) {
    return (short)((a << 8) | b & 0xFF);
  }

  public static int getInt(byte a, byte b, byte c, byte d) {
    return (a << 24) | (b & 0xFF) << 16 | (c & 0xFF) << 8 | (d & 0xFF);
  }

  public static float getFloat(byte a, byte b, byte c, byte d) {
    return Float.intBitsToFloat(getInt(a, b, c, d));
  }

  private BitConverter() {}
}

Grundsätzlich verschieben wir die Bytes einfach um ein Vielfaches von 8 Bit und kombinieren die jeweiligen Ergebnisse mit "oder". Dabei müssen wir beachten, dass wir nur das vorderste Byte direkt verschieben können. Alle anderen müssen wir zuvor mit 0xFF verknüpfen, da ansonsten das byte -1 (0xFF) zu dem int -1 (0xFFFFFFFF) werden würde, aber stattdessen brauchen wir den int 0x000000FF.

Wenn man diese vier Integer nun mit "oder" verknüpft, erhält man den endgültigen Werten: 1234567890
Bei einem Float gehen wir im Grunde genauso vor, allerdings rufen im Anschluss noch die Funktion Float.intBitsToFloat auf, wodurch wir den eigentlichen Float erhalten.
Selbstverständlich müssen wir jetzt nur noch die neuen OpCodes implementieren:

case OpCode.PUSH_SHORT:
  stack.push(new VMInt(BitConverter.getShort(code[pc++], code[pc++])));
  break;
case OpCode.PUSH_INT:
  stack.push(new VMInt(BitConverter.getInt(code[pc++], code[pc++], code[pc++], code[pc++])));
  break;
case OpCode.PUSH_FLOAT:
  stack.push(new VMFloat(BitConverter.getFloat(code[pc++], code[pc++], code[pc++], code[pc++])));
  break;

Schließlich habe ich noch den PUSH Befehl in PUSH_BYTE geändert, damit er zu den anderen Namen passt.

Neben den neuen push-Befehlen, habe ich außerdem noch zwei weitere Befehle hinzugefügt.
Einmal den SWAP-Befehl, welcher die obersten beiden Elemente des Stack vertauscht und einmal den move-Befehl, welcher den Wert von einem Register in ein anderes legt.

case OpCode.SWAP:
  other = stack.pop();
  obj = stack.pop();
  stack.push(other);
  stack.push(obj);
  break;
case OpCode.MOVE:
  obj = locals[code[pc++]];
  locals[code[pc++]] = obj;
  break;

OpCodes verbessern

Einige OpCodes erhalten bisher einen Parameter, welcher z.B. für Sprünge oder als Index benutzt wird. Häufig kann es jedoch vorkommen, dass ein Byte aber nicht ausreicht, daher werden wir nun die Codes so erweitern, dass sie einen Short als Parameter entgegen nehmen.

case OpCode.PUSH_FUNCTION:
  obj = functions[BitConverter.getShort(code[pc++], code[pc++])];
  stack.push(obj);
  break;
case OpCode.PUSH_STRING:
  obj = strings[BitConverter.getShort(code[pc++], code[pc++])];
  stack.push(obj);
  break;

Bisher konnten wir nur 128 verschiedene Funktionen und Stringkonstanten haben, da ein Byte nur einen Wertebereich von -128 bis 127 hat. Nun können wir immerhin auf bis zu 32768 Funktionen bzw. Strings verweisen.
Sämtliche Sprunginstruktionen werden wir nun auch auf einen Short erweitern, damit wir einen größeren Bereich abdecken:

jump = code[pc++];
// wird ersetzt durch:
jump = BitConverter.getShort(code[pc++], code[pc++]);

Wenn man möchte kann man nun auch CALL, LOAD und STORE auf ein Short erweitern, jedoch könnte dort auch ein Byte ausreichen. Denn wenn wir mal ehrlich sind, wird man wohl kaum mehr als 128 Parameter und lokale Variable in einer Funktion brauchen. Bei SELF, GET_GLOBAL und SET_GLOBAL verhälten es sich im Grunde genauso, jedoch denke ich, dass man bei diesen Instruktionen schon eher an die Grenze von 128 kommen könnte. Daher erweitern wir sie vorsichtshalber ebenfalls auf einen Short:

case OpCode.SELF:
  name = strings[BitConverter.getShort(code[pc++], code[pc++])].toString(); // get name of member
  obj = stack.pop(); // get table
  stack.push(obj.get(name)); // push member
  stack.push(obj); // push table
  break;
case OpCode.GET_GLOBAL:
  name = strings[BitConverter.getShort(code[pc++], code[pc++])].toString(); // get name of member
  obj = globals.get(name); // get global object
  stack.push(obj); // push object
  break;
case OpCode.SET_GLOBAL:
  name = strings[BitConverter.getShort(code[pc++], code[pc++])].toString(); // get name of member
  obj = stack.pop(); // get object
  globals.set(name, obj);
  break;

Bytecode Programme laden

Eine sehr wichtige Sache fehlt aber noch! Bisher müssen wir ein Bytecodeprogramm direkt in unseren (Java-)Code definieren. Das bringt einem natürlich herzlich wenig, daher werden wir nun dafür sorgen, dass wir ein Programm auch aus einer Datei laden können. Diese Datei wird dabei direkt den Bytecode enthalten und muss daher durch einen Hex-Editor oder durch einen Compiler erzeugt werden.
Dazu erstellen wir eine neue Klasse namens Loader, welche eine statische load-Funktion enthält.

package com.infectedbytes.tutorials.simplevm;
import java.io.File;
import java.io.IOException;
import com.infectedbytes.tutorials.simplevm.types.VMFunction;
import com.infectedbytes.tutorials.simplevm.types.VMTable;

public class Loader {
  public static VMFunction[] load(VMTable globals, File file) throws IOException {
    // TODO ...
  }
  private Loader(){}
}

Da jede erzeugte Funktion eine Referenz auf einen globalen Table benötigt, müssen wir der load-Funktion natürlich einen solchen Table mitgeben. Außerdem muss sie auch wissen, aus welcher Datei geladen werden soll. Zurückgegeben wird anschließend ein Array von VM Funktionen. Typischerweise würde man die erste Funktion als eine Art "main" Funktion betrachten und direkt ausführen. Diese main-Funktion könnte dann z.B. die ganzen globalen Variablen und "Klassen" erzeugen. Grundsätzlich benötigen wir einen Datei Stream und müssen diesen auch angemessen schließen:

DataInputStream stream = new DataInputStream(new FileInputStream(file));
try {
  // TODO ...
} finally {
  if (stream != null) stream.close();
}

Bevor wir das eigentliche Programm laden, sollten wir erstmal auf eine Magic Number prüfen. Die ersten vier Bytes eines jeden SimpleVM Programms müssen immer gleich sein, falls wir eine Datei laden, bei der die ersten vier Byte anders sind, wissen wir sofort dass es kein gültiges Programm ist und können abbrechen. Am Anfang unserer Loader Klasse definieren wir dazu eine Magic Number. Diese sollte einen Wert haben, welcher von keinem "bekannten" Programm genutzt wird.

public static final int MAGIC_NUMBER = 0x42424242;

public static VMFunction[] load(VMTable globals, File file) throws IOException {
  DataInputStream stream = new DataInputStream(new FileInputStream(file));
  try {
    if(stream.readInt() != MAGIC_NUMBER) throw new IOException("Not a SimpleVM program file");
    // TODO ...
  } finally {
    if (stream != null) stream.close();
  }
}

Wenn die ersten vier Byte korrekt sind, können wir das Programm laden. Dazu müssen wir einmal einlesen, wieviele Funktionen in dieser Datei definiert sind und anschließend werden diese Funktionen geladen.
Was genau müssen wir pro Funktion wissen? Erst einmal hat jede Funktion einige String Konstanten, außerdem müssen wir bei jeder Funktion wissen, wieviele Parameter und wieviele lokale Variablen sie hat.

short functionCount = stream.readShort(); // how many functions do we have?
VMFunction[] functions = new VMFunction[functionCount];
for (int i = 0; i < functionCount; i++) {
  short stringCount = stream.readShort(); // amount of strings in this function
  String[] strings = new String[stringCount];
  for (int j = 0; j < stringCount; j++) {
    short len = stream.readShort(); // length of string
    byte[] buffer = new byte[len]; // create buffer for string
    stream.read(buffer); // read bytes
    strings[j] = new String(buffer); // create string
  }
  int paramCount = stream.readByte(); // read number of parameters
  int locals = stream.readByte(); // read number of local variables
  int codeLen = stream.readInt(); // read length of code
  byte[] code = new byte[codeLen];
  stream.read(code); // read code
  functions[i] = new VMFunction(globals, code, functions, strings, locals, paramCount); // create function
}
return functions;

Um nun ein Testprogramm zu schreiben, benötigen wir erst einmal einen HexEditor. Ich benutze beispielsweise Be.HexEditor
Als Beispielprogramm wollen wir den folgenden Code nutzen:

VMFunction function = new VMFunction(globals, new byte[] {
    GET_GLOBAL, 0, 0,
    PUSH_STRING, 0, 1,
    CALL, 1
}, null, new String[] {"print", "hello"}, 0, 0);

In meinem Hex Editor sieht das nun so aus:

Genauer betrachtet ist dieser Code nun so aufgebaut:

In diesem Fall besteht unser Code nur aus einer Funktion. Auch diese schauen wir uns nun noch einmal etwas genauer an:

Diese Datei können wir nun wie folgt laden und ausführen:

VMFunction[] functions = Loader.load(globals, new File("path/to/program.txt"));
functions[0].call(null);

Abschluss

Damit haben wir unsere SimpleVM vervollständigt. Die VM hat nun alle notwendigen Funktionen und kann außerdem Programme aus Dateien lesen.

Da es etwas aufwendig ist, den Bytecode von Hand zu schreiben, erstellen wir uns im nächsten Artikel einen Assembler, welcher aus einer einfachen Syntax den Bytecode erzeugt.

Quellcode zu diesem Teil der Serie: 08_loading.zip