seeseekey.net

Wenn man mal auf der Suche nach einem klei­nen Zeit­ver­treib ist, kann man natür­lich so eini­ges aus­den­ken, so z.B. eine eigene CPU Archi­tek­tur. Dabei muss man diese nicht in Hard­ware gie­ßen, son­dern es reicht wenn man diese emu­liert. Und so ent­stand in eini­ger Zeit eine CPU wel­che auf den Namen „Struc­tura“ hört. Ein Design­ziel war es dabei, die CPU nur mit den nötigs­ten Maschi­nen­be­feh­len aus­zu­stat­ten. Das führte bei der „Struc­tura“ zu fol­gen­den Befeh­len (hier als Assem­bler Mne­mo­nics dargestellt):

• [0] - JUMP
• [1] - ADD
• [2] - COPY

Das bedeu­tet das es unter ande­rem keine Nichtope­ra­tion wie z.B. NOOP bzw. NOP im Befehls­satz der CPU gibt. Der Grund dafür ist ganz ein­fach. Eine Nichtope­ra­tion lässt sich durch einen JUMP um null Byte emu­lie­ren, was im End­ef­fekt nur eine Erhö­hung des „Instruc­tion Coun­ters“ kurz „IC“ zur Folge hat. Da JUMP auf den Opcode 0 gelegt wurde führt, dies zu einer inter­es­san­ten Reak­tion der CPU wenn sie das Ende des Pro­gramms erreicht und ver­sucht den rest­li­chen Spei­cher zu inter­pre­tie­ren. Die CPU inter­pre­tiert das als Sprung an die Adresse 0 und beginnt mit dem Pro­gramm von vorne.

Der Befehls­auf­bau der Maschi­nen­be­fehle stellt sich dabei so da:

JUMP (Breite: 40 Byte)
  [Int64|Befehlswort - 0]
  [Int64|Adressinterpretation - 0/ANCTAAV 1/ACTAAV 2/RNCTAAV 3/RCTAAV]
      ANCTAAV - Adress not contains target adress as value
      ACTAAV - Adress contains target adress as value
      RNCTAAV - Register not contains target adress as value
      RCTAAV - Register contains target adress as value
  [Int64|Sprungbedingung - 0/NONE 1/ZERO 2/POS 3/NEG 4/OVF]
  [Int64|Sprungadressierung - 0/ABS 1/REL] 
  [Int64|Adresse oder Wert]

ADD (Breite: 32 Byte)
  [Int64|Befehlswort - 1]
  [Int64|Modus - 0/RAR 1/RANR 2/RAV] 
      RAR - Register and register
      RANR - Register and negative register
      RAV - Register and value
  [Int64|Register] 
  [Int64|Register oder Wert]

COPY (Breite: 40 Byte)
  [Int64|Befehlswort - 2] 
  [Int64|Modus - 0/NACTAAV 1/FACTAAV 2/SACTAAV 3/BACTAAV]
    NACTAAV - No adress contains target adress as value
    FACTAAV - First adress contains target adress as value
    SACTAAV - Second adress contains target adress as value
    BACTAAV - Both adress contains target adress as value
  [Int64|Menge an kopierenden Daten in Byte]
  [Int64|Register, Speicheradresse oder ZERO] 
  [Int64|Register oder Speicheradresse]

Jeder Opcode auf der CPU ist 8 Byte lang und wird als Int64 inter­pre­tiert. Die „Struc­tura“ ist mit den Regis­tern A bis Z aus­ge­stat­tet, was 26 All­zweck­re­gis­ter mit einer Breite von 8 Byte sind. Neben die­sen All­zweck­re­gis­tern besitzt es das Spe­zi­al­re­gis­ter IC bei wel­chem es sich um den „Instruc­tion Coun­ter“ han­delt und einige Flags mit den Namen „Zero“, „Posi­tive“, „Nega­tive“ und „Over­flow“. Beim Start beginnt die CPU mit der Aus­füh­rung des Pro­gramms ab der Adresse 0. Eine Beson­der­heit ist, das die CPU kei­nen Stack und keine Inter­rupts unterstützt.

Damit Peri­phe­rie ange­spro­chen wer­den kann, gibt es bestimmte Berei­che im Spei­cher in wel­che sich diese Geräte ein­blen­den. Der Bereich für Ein­blen­dun­gen ist dabei ab der Adresse 9.000.000.000.000.000.000 (7CE66C50E2840000) bis 9.223.372.036.854.775.807 (7FFFFFFFFFFFFFFF) zu finden.

Die Gra­fik­karte wird dabei ab der Adresse 9.000.000.000.000.000.000 bis ein­schließ­lich 9.099.999.999.999.999.999 ein­ge­blen­det. In den ers­ten 4096 Byte befin­det sich dabei der Kon­fi­gu­ra­ti­ons­block der Gra­fik­karte, wel­cher Infor­ma­tio­nen über die Auf­lö­sung und andere Ein­stel­lun­gen enthält.

Ab der Adresse 9.100.000.000.000.000.000 bis ein­schließ­lich 9100000000000008191 wird die Tas­ta­tur bzw. deren Ein­ga­be­puf­fer ein­ge­blen­det. Die ers­ten zwei Byte im Spei­cher der CPU sind dabei ein UInt16 wel­cher den aktu­el­len Zei­chen­in­dex der Tas­ta­tur in ihrem Tas­ta­tur­puf­fer angibt. Jede Ein­gabe auf der wird dabei vom Tas­ta­tur­ge­rät in Form eines Bytear­rays mit der Größe von fünf Byte über­tra­gen. Das erste Byte gibt dabei den Modi­fier an, die rest­li­chen 4 Bytes ent­hal­ten das erzeugte Zei­chen in Form eines UTF-32 Zeichens.

Der sche­ma­ti­sche Auf­bau der CPU und deren Peripherie

Der Assem­bler für die CPU unter­stützt eine Reihe von Mne­mo­nics, wel­che anschlie­ßend in die Maschi­nen­spra­che über­setzt wer­den. Diese sind:

ABS [Register]
ADD [Register] [Register oder Wert]
CLR [Register oder ALL]
COPY [Int64|Menge an kopierenden Daten in Byte] [Register oder Speicheradresse] [Register oder Speicheradresse]
DIV [Register] [Register oder Wert]
LOAD [Speicheradresse] [Register]
DEC [Register]
INC [Register]
JUMP [Sprungbedingung|NONE|ZERO|POS|NEG|OVL] [Sprungadressierung|ABS|REL] [Adresse oder Wert]
MOD [Register] [Register oder Wert]
MUL [Register] [Register oder Wert]
NEG [Register]
NOOP
SHIFTL [Register] [Register oder Wert]
SHIFTR [Register] [Register oder Wert]
WRITE [Register] [Speicheradresse]

Beim Assem­bler han­delt es sich genau­ge­nom­men nicht um einen Assem­bler der rei­nen Lehre, son­dern um eine Kreu­zung aus Assem­bler, Macroas­sem­bler und Hoch­spra­che. Für die kom­ple­xe­ren Kom­man­dos wie „MUL“ oder „SHIFTL“ wer­den bestimmte Regis­ter wäh­rend der Berech­nung belegt (im Fall von „MUL“ z.B. das W, X, Y und Z Regis­ter). Die vom Kom­mando beleg­ten Regis­ter sind dabei in der Doku­men­ta­tion auf­ge­führt. Das führt natür­lich dazu das eine sol­che Mul­ti­pli­ka­tion nach der Auf­lö­sung aus sehr vie­len Befeh­len besteht:

COPY 8 Y A;
COPY 8 Z ZERO;
ADD Z 3;
COPY 8 X ZERO;
ADD Y 0;
JUMP POS REL 72;
JUMP ZERO REL 32;
ADD X 1;
ADD Z 0;
JUMP POS REL 72;
JUMP ZERO REL 32;
ADD X 1;
COPY 8 A ZERO;
ADD Y 0;
JUMP POS REL 184;
JUMP ZERO REL 144;
COPY 8 W Y;
ADD Y -W;
ADD Y -W;
COPY 8 W ZERO;
ADD Z 0;
JUMP POS REL 184;
JUMP ZERO REL 144;
COPY 8 W Z;
ADD Z -W;
ADD Z -W;
COPY 8 W ZERO;
ADD A Y;
ADD Z -1;
JUMP POS REL -104;
COPY 8 W X;
ADD W -2;
JUMP ZERO REL 368;
COPY 8 W X;
ADD W -1;
JUMP ZERO REL 112;
COPY 8 W X;
ADD W 0;
JUMP ZERO REL 144;
COPY 8 W A;
ADD A -W;
ADD A -W;
COPY 8 W ZERO;
COPY 8 X ZERO;
COPY 8 Y ZERO;
COPY 8 Z ZERO;

Wäh­rend der Ent­wick­lung gab es dabei einige inter­es­sante Ideen wie man bestimmte Sachen im Assem­bler lösen könnte. So zum Bei­spiel fol­gen­des Problem:

ADD A 555;  //Fülle den Register A mit dem Wert 555
COPY 8 B A; //Kopiere Register A zu B
DEC B; //Reduziere B um 1
COPY 8 *A B; //kopiere der Wert von B an die Adresse welche im A Register A definiert ist (555)
COPY 8 D *A; //Kopiere das was ab 555 steht in den Register D

Im D Regis­ter sollte nun der Wert 554 ste­hen. Mög­lich wird dies dadurch, das die CPU weiß das sie nicht den Wert nach A kopie­ren soll, son­dern den Wert wel­cher in A ent­hal­ten ist, als Ziel­adresse benutzt. Theo­re­tisch wäre dies auch anders lös­bar gewe­sen. So hätte der Assem­bler das * in selbst­mo­di­fiz­tie­ren­den Quell­code auf­lö­sen kön­nen. Aus einem „COPY 8 *A D“ wäre dann in etwa fol­gen­der Quell­text erzeugt worden:

COPY 8 (IC+32) A;
COPY B [IC+32];

Das Pro­blem an die­ser Geschichte ist das der Assem­bler bei die­ser Vari­ante sehr viel über die Inne­reien der CPU wis­sen muss. So muss z.B. genau defi­niert sein wann der IC erhöht wird, da die­ser für den selbst­mo­di­fi­zier­ten Code benö­tigt wird. Zur Erkä­rung: Die erste Zeile kopiert die Adresse wel­che in A liegt in die nächste Zeile und modi­fi­ziert somit den COPY Befehl wäh­rend der Lauf­zeit. Dadurch wird die Adres­sie­rung über den Regis­ter­wert möglich.

Inter­es­sant ist auch die Berech­nung eines Sprung­zie­les. Möchte man z.B. fol­gen­des Pro­gramm ausführen:

ADD A 7;
JUMP NONE REL -104

stellt sich die Frage wie man die rela­tive Sprung­weite aus­rech­net. Hier­bei kommt es auf die Breite der Befehle an. Bei den Grund­be­feh­len (ADD, COPY und JUMP) ent­spricht diese den in der Maschi­nen­co­de­be­schrei­bung ange­ge­be­nen Breite. Andere Befehle wie „MUL“ oder „SHIFTL“ zäh­len zu den kom­ple­xen Befeh­len, da diese im Maschi­nen­code aus meh­re­ren Anwei­sun­gen bestehen.

Hier besteht die ein­fachste Mög­lich­keit darin, den JUMP Befehl im ers­ten Moment mit Fan­ta­sie­wer­ten zu fül­len. Anschlie­ßend wird der Emu­la­tor mittels:

Structura.exe program.asm -disassemble -withIC

auf­ge­ru­fen. Bei der Dar­stel­lung mit­tels „withIC“ wird der Wert des ICs am Anfang des Befehls und am Ende des Befehls angezeigt.

(256/296)            JUMP ZERO REL 32;
(296/328)            ADD X 1;
(328/360)            ADD Z 0;

Möchte man nun also zum Befehl „ADD Z 0;“ sprin­gen so rech­net man 328-296 und hat so das rich­tige Sprung­ziel errechnet.

Und natür­lich fehlt auch noch eine Umset­zung in Hard­ware, aber bis das soweit ist, kann es natur­ge­mäß dau­ern. Bei der Struc­tura han­delt es sich natür­lich nicht um eine effi­zi­ente CPU, son­dern um eine bei wel­cher ver­sucht wurde, die CPU inter­nen Befehle auf ein Mini­mum zu begren­zen und das Design als sol­ches ein­fach zu hal­ten. Dies schlägt sich unter ande­rem darin nie­der, das jedes Befehls­wort 8 Byte lang ist, und somit für 3 Befehle über­di­men­sio­niert, aber dafür die Ein­fach­heit der Maschine intern gege­ben ist.

Und natür­lich erkauft man sich dies mit eini­gen Nach­tei­len, so sind die Bit­ver­schie­bungs­ope­ra­tion eigent­lich eine der schnells­ten in einer CPU. Durch die Emu­la­tion über zusätz­li­chen Assem­bler­code wird es eine der lang­sams­ten Ope­ra­tion. Aber eine CPU mit einem gro­ßen Befehls­satz zu emu­lie­ren, ist schließ­lich ein­fach und das war nicht der Sinn der Übung.

Anschauen kann man sich das unter der GPLv3 ste­hende Pro­jekt unter https://github.com/seeseekey/Structura/. Eine vor­kom­pi­lierte Ver­sion zum tes­ten gibt es hier zum Down­load. In der Imple­men­ta­tion befin­den sich sicher­lich noch einige Feh­ler auf wel­che mich gerne hin­ge­wie­sen wer­den darf. Jetzt müsste nur noch jemand Linux auf das Sys­tem por­tie­ren, wobei dies ohne wei­te­res nicht funk­tio­nie­ren sollte, das die CPU Dinge wie Inter­rupts nicht unter­stützt. Aller­dings wäre es natür­lich durch­aus mög­lich ein eige­nes mini­ma­les Betriebs­sys­tem für das emu­lierte Sys­tem zu schreiben.