as the assembler Radek Hnilica hnilica.cz Jarošova 12 Hodonín Czech Republic

as the assembler

Radek Hnilica hnilica.cz Jarošova 12 Hodonín 695 01 Czech Republic [email protected]

as the assembler by Radek Hnilica $Header:$ Edition Copyright © 2002, 2009 Radek Hnilica Tato kniha, p˚uvodnˇe cˇ lánek, vznikla jako pracovní sešit pˇri studiu pˇrekladaˇcu˚ jazyka symbolických adres, assembleru. Jsou zde poznatky které jsem k danému tématu poshánˇel a hlevnˇe odkazy na další zdroje. Tento dokument je k dispozici v nˇekolika r˚uzných formátech. Jako vícestránkový HTML dokument (index.html), postscriptový (as.ps) cˇ i PDF (as.pdf) soubor formátovaný na velikost papíru A4. Pokud nˇekterý z tˇechto formát˚u nenaleznete, nebo bude neaktuální dejte m i vˇedˇet, pˇripravím jej pro vás. Aktuální verze knihy je vystavena na www.hnilica.cz (http://www.hnilica.cz/book/as/index.html), www2.hnilica.cz (http://www2.hnilica.cz/book/as/index.html) a na penguin.cz/~radek (http://www.penguin.cz/~radek/book/as/index.html). This article is about the assembler construction. Poˇcet stran v Postscriptové a PDF verzi: 20 .

FIXME: dopsat.

Revision History Revision 0.1 2002-01-26 Pracovní verze. Revision 0.2 2009-08-11 Pˇrdˇeláno z cˇ lánku na knihu.

ˇ Venování FIXME:napsat.

Table of Contents Colophon................................................................................................................................................................. 6 Pˇredmluva.............................................................................................................................................................vii 1. Úvod .................................................................................................................................................................... 1 2. První nápady ...................................................................................................................................................... 2 3. Jednopruchodový ˚ assembler............................................................................................................................. 3 3.1. Back Patching.......................................................................................................................................... 3 4. Dvoupruchodový ˚ assembler .............................................................................................................................. 4 4.1. 2 pass assembler for SIC/XE................................................................................................................... 6 5. Assembler skeleton........................................................................................................................................... 10 5.1. Lexical Analysis .................................................................................................................................... 10 6. Making an assembler....................................................................................................................................... 11 6.1. Lexical scanner (scan.c, scan.h) ...................................................................................................... 11 6.2. Symbol Table (symtab.c, symtab.h) ................................................................................................ 12 6.3. Parser ..................................................................................................................................................... 13

iv

List of Tables 6-1. Scanner Interface ............................................................................................................................................ 11 6-2. Symbol Table Interface................................................................................................................................... 12 6-3. Parser entry points .......................................................................................................................................... 13

v

COLOPHON COLOPHON Tento dokument je psán s pomocí znaˇckovacího jazyka DocBook (http://www.docbook.org/tgd/en/html/) editorem Emacs (http://www.gnu.org/software/emacs/) a transformován do r˚uzných formát˚u nsátroji: DocBook XSL Stylesheets (http://wiki.docbook.org/topic/DocBookXslStylesheets), OpenJade (http://openjade.sourceforge.net/) a množstvím skript˚u v Bashi (http://www.gnu.org/software/bash/) a Ruby (http://www.ruby-lang.org/en/) na operaˇcním systému Debian GNU Linux (www.debian.org).

6

Pˇredmluva First section are about history and theory, section Chapter 6 is about programing real assember.

vii

Chapter 1. Úvod This work is about writing an assembler. One day I was thinking about new microprocessor and from this point I get to writing an assembler for it. What is assembler? Assembler is program which translates assembler source into machine code. But this does also an compiler. The main difference is, that compiler source is an high level language, but assembler is low level. Assembler instructions monstly map one to one. One instruction to on operation code.

1

Chapter 2. První nápady Odkazy: • Assembler Pseudocode. (http://www.unf.edu/ccec/cis/cwinton/html/cop3601/supplements/pass12.html) 2 pass assembler for SIC/XE • •

Assembler can be a one pass assembler. But this Jednopr˚uchodový assembler je takový, kdy výstupní strojový kód je generován hned pˇri prvním pr˚uchodu. Bohužel toto ˇrešení má ˇradu obtíží. Nejvetší z nich je znalost, nebo spíše neznalost adresy dpoˇredného skoku. Tedy skoku na adresu která ještˇe není známa neb bude definována dále v programu. NOW:

NOP JMP FORWARD ... FORWARD:

Další nepˇríjemnost se vyskytuje u architektur které mají pro jedu operaci nekolik možných vyjádˇrení lišících se v délce strojového kódu. Takovým ukázkovým pˇríkladem je instrukce skuku JUMP na architektuˇre Intel 80x86 která má 3 r˚uzné kódy v délce 2,3 a 5 bajt˚u. Narazíme-li v pr˚uchudu na instrukci JUMP FORWARD, nevíme který operaˇcní kód použít.

2

Chapter 3. Jednopruchodový ˚ assembler Jednopr˚uchodový assembler je nejrychlejší, ale v pˇrípadˇe rˇešení nˇekterých problému vyplývajících z jednopr˚uchodovost se zvˇetší jeho složitost a vzrostou pamˇetové nároky.

3.1. Back Patching Zp˚usob jak se vyrovnat s “neznalostí” cílové adresy v pˇrípadˇe skoku dopˇredu je back patching, tedy zpˇetná oprava. Její princip spoˇcívá v rozšíˇrení struktury tabulky symbol˚u o seznam adres na kterých je symbol ve strojovém kódu použit. Pˇri prním výskytu je pro symbol bytvoˇrena položka v tabulce a je rovnou do seznamu použití pˇridána asresa tohoto výskytu. Pˇri každém dalším použití je seznam prodloužen o adresu. V okamžiku kdy je symbol definován, projdeme všechny adresy v seznamu a “opravíme” hodnoty na adresách správnou, právˇe získanou hodnotou.

3

Chapter 4. Dvoupruchodový ˚ assembler Odkazy: • Using yyparse() to make a two pass assembler? (http://stackoverflow.com/questions/717848/usingyyparse-to-make-a-two-pass-assembler) • • • •

Dvoupr˚uchodový assembler je nejjednodušší reakce na problém dopˇredného skoku. Tedy alspoˇn mnˇe se tak jeví. Základní princip je ten, že pˇri prvním pr˚uchodu takzvanˇe pˇrekládáme na slepo. Tímto prvním pr˚uchodem zjistíme hodnoty všech symbol˚u, které si poznamenáme do tabulky symbol˚u. Pˇri druhém pr˚uchodu pak generujeme kód pˇri znalosti hodnotu všech symbol˚u, tedy i tˇech jenž jsou definován až po svém použití v kódu. Program udržuje následující datové struktury: • OPTAB

— Operation Code Table

• LOCCTR

— Location Counter

• SYMTAB

— Symbol Table

OPTAB. Tato tabulka popisuje vztah mezi symbolickými názvy instrukcí a jejich operaˇcním kódem. Rovnˇež zohledˇnuje rozdílné formáty instrukcí, adresních mód˚u a délku instrukcí. Tato tabulka je statická a její obsah se nemˇení. Definice vazby mezi symbolickým názvem instrukce a jejím cˇ íselným operaˇcním kódem tabulkou umožˇnuje snadno modifikovat assembler pro podobný cˇ i jiný procesor. Pro každý takový procesor máme pak vastní OPTAB. Pˇri prvním pr˚uchodu je OPTAB použita ke kontrole instrukcí. Pˇri druhém pr˚uchodu slouží k pˇrekladu instrukcí na cˇ íselné operaˇcní kódy. ˇ LOCCTR. Císelná promˇenná udávající aktuální adresu, adresu instrukce, ve výstupním kódu. Na zaˇcátku je nastavena na 0 a v pr˚ubˇehu zpracování m˚uže být mimo jiné zmˇenˇena pseudoinstrukcí ORG. Po zpracování instrukce ve zdrojovém souboru je LOCCTR zvˇetšena o poˇcet bajt˚u které instrukce zabírá. V prvním pr˚uchodu, kdykoliv narazíme na label (symbolickou adresu) je její hodnota nastavena z LOCCTR. SYMTAB. Tabulka symbol˚u obsahuje všechny symboly s jejich popisem a konkrétními hodnotami. Tabulka se mˇení, pˇri zahájení pˇrekladu je prázdná a postupnˇe jak jsou objevovány jednotlivé symboly ve zdrojovém kódu jsou do ní doplˇnovány. Rovnˇež v okamžiku kdy je známa hodnota symbolu je tato do tabulky doplnˇena. Example 4-1. Pseudokód prvního pruchodu ˚ begin read first input line if OPCODE = ’START’ then begin save #[OPERAND] as starting address initialize LOCCTR to starting address write line to intermediate file read next input line end {if START} else

4

Chapter 4. Dvoupr˚uchodový assembler initialize LOCCTR to 0 while OPCODE != ’END’ do begin if this is not a comment line then begin if there is a symbol in the LABEL field then begin search SYMTAB for LABEL if found then set error flag (duplicate symbol) else insert (LABEL, LOCCTR) into SYMTAB end {if symbol} search OPTAB for OPCODE if found then add 3 {instruction length} to LOCCTR else if OPCODE = ’WORD’ then add 3 to LOCCTR else if OPCODE = ’RESW’ then add 3 * #[OPERAND] to LOCCTR else if OPCODE = ’RESB’ then add #[OPERAND] to LOCCTR else if OPCODE = ’BYTE’ then begin find length of constat in bytes add length to LOCCTR end {if BYTE} else set error flag (invalid operation code) end {if not a comment} write line to intermediate file read next input line end {while not END} write last line to intermediate file save (LOCCTR - starting address) as program lenght end {Pass1}

Example 4-2. První pruchod ˚ LOCCTR := 0 -- We begin from start of adress space. ➊ while OPCODE != ’.end’ do if defined(LABEL) SYMTAB(LABEL).VALUE := LOCCTR -- look for OPCODE in OPTAB if OPCODE is in OPTAB LOCCTR + := OPTAB[OPCODE].LEN else if OPCODE is pseudoinstruction compute the LENGTH from argument part of the instruction LOCCTR + := LENGTH else -- unknown instruction error "Unknown instruction:" OPCODE end if end while

➊

Chceme-li generovat kód od jiné adresy než 0, použijeme jako první instrukci pseudoinstrukci “.org”

5

Chapter 4. Dvoupr˚uchodový assembler

Druhý pr˚uchod je v podstatˇe rozšíˇrením pruchodu prvního o generování strojového kódu. Example 4-3. Druhý pruchod ˚ LOCCTR := 0 while OPCODE != ’.end’ do -- look for OPCODE in OPTAB if OPCODE is in OPTAB CODE := OPTAB[OPCODE].CODE modify CODE by instruction arguments emit (CODE) emit arguments ➊ LOCCTR + := OPTAB[OPCODE].LEN else if OPCODE is pseudoinstruction if pseudoinstruction have to generate some code compute code/data from arguments and emit ➋ compute the LENGTH from argument part of the instruction LOCCTR + := LENGTH else -- unknown instruction error "Unknown instruction:" OPCODE end if end while

➊

Pˇri vyhodnocení argument˚u m˚uže dojít k použití SYMTAB

➋

A pˇri vyhodnocování pseudoinstrukcí taktéž.

4.1. 2 pass assembler for SIC/XE

Poznámky a komentáˇre k dvoupr˚uchodovému assembleru (http://www.unf.edu/ccec/cis/cwinton/html/cop3601/supplements/pass12.h uveˇrejnˇeném na COP 3601: Instroduction to Systems Software (http://www.unf.edu/ccec/cis/cwinton/html/cop3601/f06/3601menu.h Ukázky jsem stáhl, a postupnˇe pˇrepisoval a doplˇnoval komentáˇri. Example 4-4. První pruchod ˚ BEGIN enných*/ initialize Scnt, Locctr, ENDval, and Errorflag to 0 /* Nastavení promˇ /* Pˇ reskoˇ cení komentᡠrových ˇ rádk˚ u */ WHILE Sourceline[Scnt] is a comment BEGIN increment Scnt END {while} /* ˇ Radek ˇ císlo Scnt není komentᡠr. Rozdˇ elíme jej na Label, Opcode, ... */ Breakup Sourceline[Scnt] IF Opcode = ’START’ THEN BEGIN convert Operand from hex and save in Locctr and ENDval IF Label not NULL THEN Insert (Label, Locctr) into Symtab ENDIF

6

Chapter 4. Dvoupr˚uchodový assembler increment Scnt Breakup Sourceline[Scnt] END ENDIF WHILE Opcode <> ’END’ BEGIN IF Sourceline[Scnt] is not a comment THEN BEGIN IF Label not NULL THEN Xsearch Symtab for Label IF not found Insert (Label, Locctr) into Symtab ELSE set errors flag in Errors[Scnt] ENDIF ENDIF Xsearch Opcodetab for Opcode IF found THEN DO CASE 1. Opcode is ’RESW’ or ’RESB’ BEGIN increment Locctr by Storageincr IF error THEN set errors flag in Errors[Scnt] ENDIF END {case 1 (RESW or RESB)} 2. Opcode is ’WORD’ or ’BYTE’ THEN BEGIN increment Locctr by Storageincr IF error THEN set errors flag in Errors[Scnt] ENDIF END {case 2 (WORD or BYTE)} 3. OTHERWISE BEGIN increment Locctr by Opcodeincr IF error THEN set errors flag in Errors[Scnt] ENDIF {case 3 (default)} END ENDCASE ELSE /* directives such as BASE handled here or */ set errors flag in Errors[Scnt] ENDIF END {IF block} ENDIF increment Scnt Breakup Sourceline[Scnt] END {while} IF Label not NULL THEN Xsearch Symtab for Label IF not found Insert (Label, Locctr) into Symtab ELSE set errors flag in Errors[Scnt] ENDIF

7

Chapter 4. Dvoupr˚uchodový assembler ENDIF IF Operand not NULL Xsearch Symtab for Operand IF found install in ENDval ENDIF ENDIF END {of Pass 1}

Example 4-5. Druhý pruchod ˚ BEGIN initialize Scnt, Locctr, Skip, and Errorflag to 0 write assembler report headings WHILE Sourceline[Scnt] is a comment BEGIN append to assembler report increment Scnt END {while} Breakup Sourceline[Scnt] IF Opcode = ’START’ THEN BEGIN convert Operand from hex and save in Locctr append to assembler report increment Scnt Breakup Sourceline[Scnt] END ENDIF format and place the load point on object code array format and place ENDval on object code array, index ENDloc WHILE Opcode <> ’END’ BEGIN IF Sourceline[Scnt] is not a comment THEN BEGIN Xsearch Opcodetab for Opcode IF found THEN DO CASE 1. Opcode is ’RESW’ or ’RESB’ BEGIN increment Locctr by Storageincr place ’!’ on object code array replace the value at index ENDloc with loader address format and place Locctr on object code array format and place ENDval on object code array, index ENDloc set Skip to 1 END 2. Opcode is ’WORD’ or ’BYTE’ BEGIN increment Locctr by Storageincr Dostorage to get Objline IF error THEN set errors flag in Errors[Scnt] ENDIF END 3. OTHERWISE BEGIN increment Locctr by Opcodeincr

8

Chapter 4. Dvoupr˚uchodový assembler Doinstruct to get Objline IF error THEN set errors flag in Errors[Scnt] ENDIF END ENDCASE ELSE /* directives such as BASE handled here or */ set errors flag in Errors[Scnt] ENDIF END ENDIF append to assembler report IF Errors[Scnt] <> 0 THEN BEGIN set Errorflag to 1 append error report to assembler report END ENDIF IF Errorflag = 0 and Skip = 0 THEN BEGIN place Objline on object code array END ENDIF IF Skip = 1 THEN set Skip to 0 ENDIF increment Scnt Breakup Sourceline[Scnt] END {while} place ’!’ on object code array IF Errorflag = 0 THEN transfer object code array to file ENDIF END {of Pass 2}

9

Chapter 5. Assembler skeleton 5.1. Lexical Analysis Lexical analysis: breaking the input into individual words or “tokens”

10

Chapter 6. Making an assembler Building of an Assembler for Z80 Processor This part describes building of an assembler for subset of small Zilog Z80 CPU. As an example I build one assembler targeted to Zilog Z80 CPU. The assembler consist from few modules. Every module have it’s own work and defined interface for comunication with others modules. The modules are

Modules description Lexical Scanner, files scan.c and scan.h Lexical Scanner is only module, responsible for reading of input stream. Its main function is to chop input character stream into lexemes. parser in files parse.c and parse.h library of functions for parsing the ... Pseudoinstructions (Directives) in files pseudo.[ch] Realizing pseudoinstructions Symbol tablesymtab.[ch] The symbol table. Opcode table in files optab.c and optab.h This realizes the procesor operation codes. This part is the one which is target processor dependable. I plan to do [ještˇe] one processor more in future. The main part in files as.c and as.h This is glue which holds all parts together. It also defines global varibales which may other parts modify.

As you can see, every module consists of two files, the header file “.h” which contains description of module interface. It means that it exports public functions, variables, type and constant definitions. The second file “.c” is [vlastní] module definition, description how things are done and how works.

6.1. Lexical scanner (scan.c, scan.h) Lexical scanner, which consists of two files scan.c, scan.h chops input character stream into well defined small pieces called tokens. It also rips out the comments. I have chosen * FIXME: vybral jsem si

(to) not use a program like lex/flex for creating this lexical sanner. Instead I wrote it handy. Table 6-1. Scanner Interface

11

Chapter 6. Making an assembler function or variable

description

scan_initialize Module initialization, must to call before module usage. scan_terminate Module termination, have to call after last usage. scan_fopen scan_fuse

Report !FIXME: Oznámit! to scanner what input stream to use for reading.

scan_fcopy

Copy all input to given stream while reading. This only sets the copy stream.

scan

Main entry point. Every call to scan returns nex token choped from input file.

6.1.1. Scanner Interface There are two functions for setting the input stream. It is scan_fopen and scan_fuse. The first is used when we nead to read from an file, the second when we read from stream.

Interface description scan_fopen(char *file_name)

This function opens the source file it’s name was given, and sets the module input stream istream to it. All subsequent readings are done from this file/stream. This function is for reading from file, when the file name was given on assembler command line. scan_fuse(FILE *stream)

When we don’t know the source file name, but have an stream. Then we use this function for telling lexical scanner from what source it has to read. This is the case when assembler have source file in it’s input stream, stdio. byte scan() This is main entry point for lexical scanner. Calling this function scanns input stream for one lexeme, and sets the module public variable sym to that lexeme. It also returns the type of lexeme.

6.1.2. Scanner Internals istream

Input stream. The stram from which scanner reads characters. It is setted only by functions scan_fopen and scan_fuse.

6.2. Symbol Table (symtab.c, symtab.h) Table 6-2. Symbol Table Interface function or variable

12

description

Chapter 6. Making an assembler function or variable

description

symtab_initializeModule initialization, must to call before module usage. symtab_terminate Module termination, have to call after last usage. addsym

Adds a new symbol to table.

findsym

Look for symbol in table.

6.3. Parser Parser module is there for parsing instruction arguments for normal instruction or assembler directive (pseudoinstruction). There are few entry points: Table 6-3. Parser entry points function

description

do_number

This functions parse one number from an parameter fields. Note!! Symbolic names are also evaluated. Because this is run only in second pass, it must always evaluate to number. If not, an error is risen.

13