Matthias Reitinger
ɐɯıǝɹ
Hallo,
ich habe mich mal an einem kleinen "BrainScript-Assembler" versucht. Vor der Ausführung wird das BrainScript-Programm in x86-Maschinencode (mit Linux-spezifischen Systemaufrufen für Ein- und Ausgabe) übersetzt und der erzeugte Code anschließend aufgerufen.
Das eigentliche Vorhaben war noch etwas komplizierter, denn geplant war es als JIT-Compiler. Das heißt, dass sämtlichen Schleifen als Unterprogramme interpretiert werden und vor der Ausführung zunächst nicht in Maschinencode übersetzt werden (mit Ausnahmen bei z.B. Schleifen unter einer bestimmten Größe). Erst wenn der Schleifenkörper während der Ausführung tatsächlich betreten wird, sollte der entsprechende Quellcode dann in Maschinencode umgewandelt werden. Leider scheiterte dieser Plan an mangelnder Zeit...
Deshalb hier die "unge-JIT-ete" Variante. Der Zeit ebenfalls zum Opfer fielen triviale Optimierungen des Codes (mehrere Inkrementierungen durch eine Addition ersetzen, [-] durch Nullsetzen der aktuellen Zelle etc.).
Die Erweiterung habe ich nicht implementiert. Das Verhalten bei Über-/Unterschreiten des zulässigen Datenbereichs von 30.000 Zellen ist undefiniert.
Nach dem Kompilieren durch bspw.
erfolgt der Aufruf mit
Es werden dann alle übergebenen Dateien der Reihe nach eingelesen, als BrainScript-Quellcode interpretiert und ausgeführt.
ich habe mich mal an einem kleinen "BrainScript-Assembler" versucht. Vor der Ausführung wird das BrainScript-Programm in x86-Maschinencode (mit Linux-spezifischen Systemaufrufen für Ein- und Ausgabe) übersetzt und der erzeugte Code anschließend aufgerufen.
Das eigentliche Vorhaben war noch etwas komplizierter, denn geplant war es als JIT-Compiler. Das heißt, dass sämtlichen Schleifen als Unterprogramme interpretiert werden und vor der Ausführung zunächst nicht in Maschinencode übersetzt werden (mit Ausnahmen bei z.B. Schleifen unter einer bestimmten Größe). Erst wenn der Schleifenkörper während der Ausführung tatsächlich betreten wird, sollte der entsprechende Quellcode dann in Maschinencode umgewandelt werden. Leider scheiterte dieser Plan an mangelnder Zeit...
Deshalb hier die "unge-JIT-ete" Variante. Der Zeit ebenfalls zum Opfer fielen triviale Optimierungen des Codes (mehrere Inkrementierungen durch eine Addition ersetzen, [-] durch Nullsetzen der aktuellen Zelle etc.). Die Erweiterung habe ich nicht implementiert. Das Verhalten bei Über-/Unterschreiten des zulässigen Datenbereichs von 30.000 Zellen ist undefiniert.
C++:
#include <fstream>
#include <istream>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
class BFAssembler {
private:
// Ein Label bezeichnet eine bestimmte Adresse im Maschinencode.
typedef std::vector<char>::size_type label;
// Ein Target ist ein Paar von Labeln: am ersten Label steht die Adresse, die
// auf das zweite Label verweist.
typedef std::pair<label, label> target;
typedef void (*bffunc) (void);
public:
BFAssembler(char *data) : data_(data) {};
/**
* Assembliert den in <s> gespeicherten BF-Quellcode.
**/
void assemble(const std::string &s) {
std::istringstream iss(s);
assemble(iss);
}
/**
* Assembliert den BF-Quellcode, der aus dem Eingabestrom <is> gelesen wird.
**/
void assemble(std::istream &is) {
code_.clear();
asmProlog();
asmBFInit();
_assemble(is);
asmEpilog();
}
/**
* Führt das assemblierte Programm aus.
**/
void run() {
updateTargets();
(reinterpret_cast<bffunc>(&code_[0]))();
}
private:
/**
* Eigentliche Implementierung des Parsers und Assemblers
**/
void _assemble(std::istream &is) {
while (is.good()) {
char ch;
is >> ch;
switch (ch) {
case '+': asmIncData(); break;
case '-': asmDecData(); break;
case '>': asmIncPtr(); break;
case '<': asmDecPtr(); break;
case ',': asmGetc(); break;
case '.': asmPutc(); break;
case '[': {
// TODO: Das Setzen des Targets für den Schleifenbeginn geschieht
// momentan ziemlich unsauber: asmLoopStart erzeugt ein neues Target,
// das zunächst auf das Label 0 verweist. Über targets_.size() - 1
// holen wir uns den Index dieses Targets. Nach der Assemblierung des
// Schleifenkörpers setzen wir nachträglich das Ziel des Targets auf
// das aktuelle Label. Dieses Vorgehen ist ziemlich unsauber und sollte
// deswegen durch etwas besseres ersetzt werden.
asmLoopStart();
label loop_body = getCurrentLabel();
int loop_target_index = targets_.size() - 1;
_assemble(is);
asmLoopEnd(loop_body);
targets_[loop_target_index].second = getCurrentLabel();
break;
}
case ']':
return;
default:
// Nicht-Steuerzeichen ignorieren
break;
}
}
}
/**
* Gibt das aktuelle Label zurück. An diese Position wird der nächste
* Maschinencode geschrieben.
**/
label getCurrentLabel() {
return code_.size();
}
/**
* Aktualisiert die Sprungziele im Maschinencode.
**/
void updateTargets() {
std::vector<std::pair<label, label> >::iterator it;
for (it = targets_.begin(); it != targets_.end(); ++it) {
label from = it->first;
label to = it->second;
char *absolute_base_address = &(code_[from]);
char *absolute_target_address = &(code_[to]);
// Die relative Adresse des Sprungziels bezieht sich auf die Position
// *nach* der absoluten Basis-Adresse (<absolute_base_address>), darum
// muss die Länge dieser Adresse nochmal abgezogen werden (- 4).
ptrdiff_t relative_target_address = absolute_target_address -
absolute_base_address - 4;
code_[from] = relative_target_address & 0xFF;
code_[from+1] = (relative_target_address >> 8) & 0xFF;
code_[from+2] = (relative_target_address >> 16) & 0xFF;
code_[from+3] = (relative_target_address >> 24) & 0xFF;
}
}
/***************************************************************************\
| Assembler-Funktionen |
| |
| Jede der asm*-Funktionen hängt den Maschinencode der entsprechenden |
| Operation an die Liste der Maschinenbefehle <code_> an. Der erzeugte |
| Maschinencode geht davon aus, dass der Zeiger auf die aktuelle Zelle |
| stets im Register %ecx zur Verfügung steht. |
\***************************************************************************/
/**
* Assembliert:
* Einen Integer <i> mit 32 Bit Breite in Intel Byte Order (LSB first).
**/
void inline asmInt32(int i) {
code_.push_back( i & 0xFF);
code_.push_back((i >> 8) & 0xFF);
code_.push_back((i >> 16) & 0xFF);
code_.push_back((i >> 24) & 0xFF);
}
/**
* Assembliert:
* Das niedrigstwertige Byte von <i>.
**/
void inline asmByte(int i) {
code_.push_back(i & 0xFF);
}
/**
* Assembliert:
* Die zwei niedrigstwertigen Bytes von <i> (MSB first).
**/
void inline asm2Bytes(int i) {
code_.push_back((i >> 8) & 0xFF);
code_.push_back( i & 0xFF);
}
/**
* Assembliert:
* Die drei niedrigstwertigen Bytes von <i> (MSB first).
**/
void inline asm3Bytes(int i) {
code_.push_back((i >> 16) & 0xFF);
code_.push_back((i >> 8) & 0xFF);
code_.push_back( i & 0xFF);
}
/**
* Assembliert:
* Standard-Prolog für eine Funktion (Stack setzen).
**/
void asmProlog() {
asmByte(0x55); // push %ebp
asm2Bytes(0x89E5); // mov %esp, %ebp
}
/**
* Assembliert:
* Standard-Epilog für eine Funktion (Stack wiederherstellen, Rücksprung).
**/
void asmEpilog() {
asmByte(0x5D); // pop %ebp
asmByte(0xC3); // ret
}
/**
* Assembliert:
* Initialisierung für das BF-Programm (setzt %ecx auf die Startadresse des
* Datenbereichs).
**/
void asmBFInit() {
asmByte(0xB9); // mov data_, %ecx
asmInt32(reinterpret_cast<int>(data_));
}
/**
* Assembliert:
* Inkrementiert das Byte an Adresse %ecx.
**/
void asmIncData() {
asm2Bytes(0xFE01); // incb (%ecx)
}
/**
* Assembliert:
* Dekrementiert das Byte an Adresse %ecx;
**/
void asmDecData() {
asm2Bytes(0xFE09); // decb (%ecx)
}
/**
* Assembliert:
* Inkrementiert %ecx.
*/
void asmIncPtr() {
asmByte(0x41); // inc %ecx
}
/**
* Assembliert:
* Dekrementiert %ecx.
*/
void asmDecPtr() {
asmByte(0x49); // dec %ecx
}
/**
* Assembliert:
* Führt einen Systemaufruf (Interrupt 0x80) durch. Das erste und dritte
* Argument des Systemaufrufs werden entsprechend der Parameter gesetzt,
* der zweite muss sich bereits in %ecx befinden.
**/
void asmSyscall(int syscall, int arg0, int arg2) {
asmByte(0xB8); // mov syscall, %eax
asmInt32(syscall);
asmByte(0xBB); // mov arg0, %ebx
asmInt32(arg0);
asmByte(0xBA); // mov arg2, %edx
asmInt32(arg2);
asm2Bytes(0xCD80); // int $0x80
}
/**
* Assembliert:
* Schreibt das Byte (%ecx) auf die Standardausgabe.
*/
void asmPutc() {
// Syscall 4 (sys_write), Standardausgabe (1), ein Zeichen
asmSyscall(4, 1, 1);
}
/**
* Assembliert:
* Liest ein Byte von der Standardeingabe und speichert es in (%ecx). Im
* Fehlerfall (z.B. EOF) wird (%ecx) auf 0 gesetzt.
*/
void asmGetc() {
// Syscall 3 (sys_read), Standardeingabe (0), ein Zeichen
asmSyscall(3, 0, 1);
asmByte(0x3D); // cmp $0x0, %eax
asmInt32(0);
asm2Bytes(0x7F03); // jg (+3)
asm3Bytes(0xC60100); // movb $0x0, (%ecx)
}
/**
* Assembliert:
* Start einer Schleife: springt bei (%ecx) == 0 zum Schleifenende. Da das
* Ende der Schleife zum Zeitpunkt des Aufrufes von asmLoopStart noch nicht
* bekannt ist, wird als Sprungziel zunächst das Label 0 verwendet. Dies
* muss später vom Aufrufer auf das korrekte Label gesetzt werden.
*/
void asmLoopStart() {
asm3Bytes(0x803900); // cmpb $0x0, (%ecx)
asm2Bytes(0x0F84); // je end
asmJumpTarget(0);
}
/**
* Assembliert:
* Ende einer Schleife: springt bei (%ecx) != 0 zum Schleifenkörper an
* Position <body>.
*/
void asmLoopEnd(label body) {
asm3Bytes(0x803900); // cmpb $0x0, (%ecx)
asm2Bytes(0x0F85); // jne body
asmJumpTarget(body);
}
/**
* Assembliert:
* Ziel eines Sprungbefehls. Erstellt einen Eintrag in der internen Liste der
* Sprungziele und fügt einen Platzhalter für die Adresse in den Code ein.
*/
void asmJumpTarget(label addr) {
targets_.push_back(
std::make_pair<label, label>(getCurrentLabel(), addr));
asmInt32(0); // Platzhalter für Adresse
}
private:
// Enthält den assemblierten Maschinencode
std::vector<char> code_;
// Liste aller Sprungziele
std::vector<target> targets_;
// Zeiger auf den Datenbereich des BF-Programms
char *data_;
};
const size_t DATA_SIZE = 30000;
int main(int argc, char *argv[]) {
char *data = new char[DATA_SIZE];
for (int i = 1; i < argc; ++i) {
// TODO: Error handling...
std::ifstream ifs(argv[i]);
memset(data, 0, DATA_SIZE);
BFAssembler bfasm(data);
bfasm.assemble(ifs);
bfasm.run();
}
delete[] data;
return 0;
}
Code:
g++ -o bf bf.cc
Code:
./bf <datei1> [<datei2> ...]
