[QUIZ#3] Matthias Reitinger (C++/Assembler)


#1
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.

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;
}
Nach dem Kompilieren durch bspw.
Code:
g++ -o bf bf.cc
erfolgt der Aufruf mit
Code:
./bf <datei1> [<datei2> ...]
Es werden dann alle übergebenen Dateien der Reihe nach eingelesen, als BrainScript-Quellcode interpretiert und ausgeführt.
 

Anhänge

OnlyFoo

Erfahrenes Mitglied
#2
Hey, das kenn ich irgendwoher =) sehr schön...
Hey, und es ist noch schneller als mein Programm, obwohl meines noch optimiert. Erstaunlich - liegt wohl an meinen schlechten Assemblerkentnissen =)
 
Zuletzt bearbeitet:
#3
Hey, und es ist noch schneller als mein Programm, obwohl meines noch optimiert. Erstaunlich - liegt wohl an meinen schlechten Assemblerkentnissen =)
Der Grund dürfte vermutlich sein, dass du auf Bereichsüberschreitungen testest und ich nicht. Außerdem laufen meine Schleifen nur über Sprünge an konstante Adressen ab, du verwendest stattdessen den Stack (wenn ich das beim Überfliegen richtig gesehen habe).

Ansonsten fällt mir bei meinem Code gerade noch auf, dass fehlende schließende Klammern nicht bemängelt werden. Und bei der ersten schließenden Klammer, zu der es keine zugehörige öffnende Klammer gibt, wird nicht mehr weitergeparst... ach, egal, ich nenn das einfach mal ein Feature ;)
 

OnlyFoo

Erfahrenes Mitglied
#4
Nein, bei Schleifen habe ich auch konstante Adressen, bzw relative Adressen, jedenfalls ohne den Stack zu nutzen...
Ja das mit den Grenzen stimmt. Muss mal schauen, wie das ohne aussieht.

Glückwunsch: Ohne Vergleiche ist mein Programm noch langsamer. Wie kann das denn sein?
 
Zuletzt bearbeitet:

OnlyFoo

Erfahrenes Mitglied
#6
Nein, hab ich nicht. Aber ich hab den Code gestern komplett umgeschrieben, also den generierten ByteCode. Nun ist das ganze Programm dreimal so schnell und schaft die Mandelbrotmenge in nur 2 Sekunden.