Write Your Own Assembler ======================== By D.W. Edwards =============== Contents: -------- Introduction Processor Choice 6502 Instruction Set & Architecture 6502 Addressing Modes 6502 Opcodes Assembly Language Syntax-The Basics Translating Code Labels, Symbol Tables & Hashing Single-Line Assembly Jump Tables Extra Information For Assemblers A Complete Example Assembler Some Processors To Choose From Bibliography Introduction ------------ Once again, I, the manic DOC file writer and prime supplier of headbanging code to the universe at large, provide you, the long-suffering members of ACC with yet another piece of mental torture. However, just in case there ARE one or two brave fellows willing to take up the challenge, this series of arti- cles will provide you with the basic tools required to do the job. To make life easier, I shall cover a nice, simple processor, and just to keep you on your toes, I shall cover the simpler addressing modes only. I intend this to provide a starting point:should anyone want a full-blown work- ing assembler, they will have to work out the extra details themselves. Processor Choice ---------------- For this article, there were a wealth of processors to choose from. I could have chosen any of the following mass of chips to use: MC6800 8080 8085 6502 Z80 6809 6301 80x86 MC680x0 SPARC 88000 65316 TMS9900 TMS99000 Z8000 Z800 Z80000 T800 F100L 1802 F8 F11 8049 6303 V20 V30 ARM3 TMS34020 or any others that you could think of. However, some of these chips have com- plex instruction sets (the Z8000 has the ability to perform 64-bit arithmetic among other things, and the TMS34020 can operate on any operand size from a single bit to 32 bits, and any size in between) and it would not be fair to throw some of these at the novice. So, with this in mind, and also bearing in mind that many Amiga users are also former Commodore 64 users, I shall choose the 6502. Apart from the existence of a large number of former C64 users in the Amiga community, and the existence of a C64 emulator for the Amiga (PD too!) allowing the assembly language programmer to test his/her efforts with 6502 code, the 6502 is one of the simplest chips to understand. However, despite the stated simplicity of the 6502 architecture, the fundamental principles lying behind the construction of a 6502 assembler are common to all of the other processors, no matter how complex. Also, the 6502 was the first chip that I learned to program, way back in the heady days of the Commodore PET (anyone remember those?) and I fould that I could make the 6502 perform some amazing stunts on a 32K PET (Ye Gods, 32K! Now I can't live without a megabyte!). 6502 Instruction Set & Architecture ----------------------------------- The 6502 has the simplest instruction set of any mass-market micro- processor (the joke among the cynics is that the 6502 was the world's first RISC chip!). The basic instructions are (for those who have not encountered the processor before:experienced users can skip this section): ADC : Add with carry memory to accumulator AND : Logical AND memory operand to accumulator ASL : Arithmetic shift left given operand Bxx : Various branch instructions. The full list is: BCC Branch on carry clear BCS Branch on carry set BEQ Branch on equal (to zero) BMI Branch on result minus BNE Branch on not equal (to zero) BPL Branch on result plus BVC Branch on overflow clear BVS Branch on overflow set BIT : Test bits with accumulator BRK : Software BREAK instruction (vector $FFFE) similar to 6809 software interrupt CLC : Clear carry flag CLD : Clear decimal flag CLI : Clear interrupt disable CLV : Clear overflow CMP : Compare memory with accumulator CPX : Compare memory with X register CPY : Compare memory with Y register DEC : Decrement memory operand DEX : Decrement X register DEY : Decrement Y register EOR : Exclusive-OR memory with accumulator INC : Increment memory operand INX : Increment X register INY : Increment Y register JMP : Jump to new program location JSR : Jump to subroutine, saving PC on stack LDA : Load accumulator LDX : Load X register LDY : Load Y register LSR : Logical shift right given operand NOP : No operation (do nothing for 2 cycles) ORA : Inclusive-OR memory with accumulator PHA : Push accumulator on stack PHP : Push processor status on stack PLA : Pull accumulator off stack PLP : Pull processor status off stack ROL : Rotate given operand left one bit ROR : Rotate given operand right one bit RTI : Return from interrupt RTS : Return from subroutine SBC : Subtract with borrow memory from accumulator SEC : Set carry flag SED : Set decimal flag SEI : Set interrupt disable STA : Store accumulator in memory STX : Store X register in memory STY : Store Y register in memory TAX : Transfer accumulator to X register TAY : Transfer accumulator to Y register TSX : Transfer stack pointer to X register TXA : Transfer X register to accumulator TXS : Transfer X register to stack pointer TYA : Transfer Y register to accumulator The 6502 is VERY simple internally. The chip has 6 registers: PC : Program counter (16 bits) S : Stack pointer (8/9 bits) P : Processor status (aka condition codes/flags) (8 bits) A : Accumulator (8 bits) X : X index register (8 bits) Y : Y index register (8 bits) and most of the instructions reference one of the above registers explicitly. Implicit references are contained within JMP (affects PC) and JSR (affects PC and S) and there are doubtless others in the above table that you can spot. One query you may have if you have never encountered the 6502 before is how the stack pointer can be 8 or 9 bits. Well, when you write data to the stack pointer, you write it as an 8-bit value (using TXS). However, the stack on a 6502 is ALWAYS located at memory locations $100 to $1FF, and the stack pointer has an extra 9th bit (which is ALWAYS set to 1). Because of this, the stack operations are faster than on those processors that possess a 16-bit stack pointer (but the stack size is restricted in hardware!). Ok, having dealt with that query, it is time to cover the 6502 add- ressing modes, and then the opcodes themselves (which depend heavily upon the choice of addressing mode). 6502 Addressing Modes --------------------- In the Sybex book, instructions referencing registers other than the accumulator are called 'implied' instructions (even though many of them state EXPLICITLY which register is being referenced!), and instructions that ref- erence the accumulator are called 'accumulator' instructions. Although this artificial distinction is semantically wasteful for the 6502 programmer, for the assembler writer it turns out to be more useful. Also, memory operands are split into absolute operands (where the ad- dress is a full 16-bit value) and zero-page operands (where the address is an 8-bit value) which are restricted to the memory addresses $00-$FF. The 6502 also has indexed addressing modes, which appear in the fol- lowing forms in 6502 assembler: LDA label,X LDA label,Y In each case, 'label' can be either an absolute memory operand or a zero-page operand, in which case the opcode changes accordingly. There exists a set of restrictions upon which of these can be used with various instructions, the principal restriction applying to instructions referencing each of the index registers X and Y. In an instruction such as: LDX operand 'operand' CANNOT be indexed with X, and: LDY operand CANNOT be used with an operand indexed with Y. The other modes in use are indirect modes (where the operand is used to obtain an ADDRESS, which in turn is read to locate the final operand). The allowed forms are: LDA (operand,X) [1] and: LDA (operand),Y [2] These work in two rather convoluted ways. First, form number [1]. The address is computed by taking the address of 'operand' (which is a zero-page operand) and adding the contents of the X register to it (note:only the low 8 bits of the address are affected during the addition!). This address, and the follow- ing address, are then read in sequence to obtain a pointer. The contents of the memory location addressed by this pointer are used as the final operand. Form [2] works differently. The zero-page location 'operand' and the next location in memory are read, to obtain a 16-bit pointer. The contents of Y are then added to the value of this pointer, and the resulting memory loc- ation is read to obtain the final operand. The major exception is the JMP instruction. This has the form: JMP (location) where the 16-bit value of 'location' is used directly as a pointer to another location, which in turn is used as the location for the jump instruction. The 6502 also allows immediate operands, such as: LDA #$20 where the actual data to be used is contained within the instruction. These addressing modes affect the opcodes themselves (as might be ex- pected), as opposed to some processors which use an extra byte or word before or after the instruction to indicate the addressing mode (the 68000 uses both an altered instruction opcode word and where necessary a postword to indicate one of many complex addressing modes). Now I shall cover the opcodes for the 6502 processor. 6502 Opcodes ------------ The 6502 opcodes are best laid out in a table, as is done in the book "Programming the 6502" by Rodnay Zaks. However, there is little room for lay- ing out a wide table using GenAm as the editor for this article, so I shall condense the table to make it fit. The leftmost column is the instruction mnemonic as used in 6502 ass- embly language. The following columns are the instruction bytes themselves, where an instruction is legal for the given addressing mode, with the add- ressing modes in the following order, left to right: Implied, Accumulator, Absolute, Zero-Page, Immediate, Absolute-X, Absolute-Y, Indirect-X, Indirect-Y, Relative, Zero-Page-X, Zero-Page-Y, Indirect Where an opcode for that mode does not exist, the legend -- is used. So, now to the opcode table: IP AC AB ZP IM AX AY IX IY RL ZX ZY ID ADC -- -- 6D 65 69 7D 79 61 71 -- 75 -- -- AND -- -- 2D 25 29 3D 39 21 31 -- 35 -- -- ASL -- 0A 0E 06 -- 1E -- -- -- -- 16 -- -- BCC -- -- -- -- -- -- -- -- -- 90 -- -- -- BCS -- -- -- -- -- -- -- -- -- B0 -- -- -- BEQ -- -- -- -- -- -- -- -- -- F0 -- -- -- BIT -- -- 2C 24 -- -- -- -- -- -- -- -- -- BMI -- -- -- -- -- -- -- -- -- 30 -- -- -- BNE -- -- -- -- -- -- -- -- -- D0 -- -- -- BPL -- -- -- -- -- -- -- -- -- 10 -- -- -- BVC -- -- -- -- -- -- -- -- -- 50 -- -- -- BVS -- -- -- -- -- -- -- -- -- 70 -- -- -- CLC 18 -- -- -- -- -- -- -- -- -- -- -- -- CLD D8 -- -- -- -- -- -- -- -- -- -- -- -- CLI 58 -- -- -- -- -- -- -- -- -- -- -- -- CLV B8 -- -- -- -- -- -- -- -- -- -- -- -- CMP -- -- CD C5 C9 DD D9 C1 D1 -- D5 -- -- CPX -- -- EC E4 E0 -- -- -- -- -- -- -- -- CPY -- -- CC C4 C0 -- -- -- -- -- -- -- -- DEC -- -- CE C6 -- DE -- -- -- -- D6 -- -- DEX CA -- -- -- -- -- -- -- -- -- -- -- -- DEY 88 -- -- -- -- -- -- -- -- -- -- -- -- EOR -- -- 4D 45 49 5D 59 41 51 -- 55 -- -- INC -- -- EE E6 -- FE -- -- -- -- F6 -- -- INX E8 -- -- -- -- -- -- -- -- -- -- -- -- INY C8 -- -- -- -- -- -- -- -- -- -- -- -- JMP -- -- 4C -- -- -- -- -- -- -- -- -- 6C JSR -- -- 20 -- -- -- -- -- -- -- -- -- -- LDA -- -- AD A5 A9 BD B9 A1 B1 -- B5 -- -- LDX -- -- AE A6 A2 -- BE -- -- -- -- B6 -- LDY -- -- AC A4 A0 BC -- -- -- -- B4 -- -- LSR -- 4A 4E 46 -- 5E -- -- -- -- -- 56 -- NOP EA -- -- -- -- -- -- -- -- -- -- -- -- ORA -- -- 0D 05 09 1D 19 01 11 -- -- 15 -- PHA 48 -- -- -- -- -- -- -- -- -- -- -- -- PHP 08 -- -- -- -- -- -- -- -- -- -- -- -- PLA 68 -- -- -- -- -- -- -- -- -- -- -- -- PLP 28 -- -- -- -- -- -- -- -- -- -- -- -- ROL -- 2A 2E 26 -- 3E -- -- -- -- 36 -- -- ROR -- 6A 6E 66 -- 7E -- -- -- -- 76 -- -- RTI 40 -- -- -- -- -- -- -- -- -- -- -- -- RTS 60 -- -- -- -- -- -- -- -- -- -- -- -- SBC -- -- ED E5 E9 FD F9 E1 F1 -- F5 -- -- SEC 38 -- -- -- -- -- -- -- -- -- -- -- -- SED F8 -- -- -- -- -- -- -- -- -- -- -- -- SEI 78 -- -- -- -- -- -- -- -- -- -- -- -- STA -- -- 8D 85 -- 9D 99 81 91 -- 95 -- -- STX -- -- 8E 86 -- -- -- -- -- -- -- 96 -- STY -- -- 8C 84 -- -- -- -- -- -- 94 -- -- TAX AA -- -- -- -- -- -- -- -- -- -- -- -- TAY A8 -- -- -- -- -- -- -- -- -- -- -- -- TSX BA -- -- -- -- -- -- -- -- -- -- -- -- TXA 8A -- -- -- -- -- -- -- -- -- -- -- -- TXS 9A -- -- -- -- -- -- -- -- -- -- -- -- TYA 98 -- -- -- -- -- -- -- -- -- -- -- -- This covers the full list of 6502 opcodes (hovever, there exists a CMOS 6502 chip with added instructions, PHX, PHY, PLX and PLY, but I do not have access to the necessary information to supply those opcodes. If you have access to the opcodes for these added instructions, the option to build them in to your own assembler is of course open) as supplied in "Programming the 6502" men- tioned above. Assembly Language Syntax-The Basics ----------------------------------- 6502 assembly language syntax is quite simple. The examples below are all legal examples of 6502 assembly language instructions, and any assembler MUST be able to translate them: INX ;implied instruction ROL A ;accumulator instruction LDX #$30 ;immediate instruction LDA $20 ;zero-page LDA $3000 ;absolute instruction LDA $A000,X ;indexed instruction LDA $B000,Y ;so is this LDA $40,X ;zero-page indexed where allowed STX $10,Y ;this is allowed LDA ($40,X) ;indexed indirect LDA ($10),Y ;indirect indexed JMP ($3000) ;indirect absolute LDA label ;labels should be allowed JSR label ;especially for this BEQ label ;relative instruction As well as routines to decode the text, and separate the text into opcodes, operands and any preceding labels, as in: label LDA #$30 the code needs to be able to take preceding labels and store them along with their associated addresses to allow the assembler to reference the labels in a consistent anner during assembly. Also, if the assembler is going to be a sophisticated product, it needs to be able to handle operands that contain an arithmetic expression, as in: LDA loc+TABSIZE*ENTLEN or even more complicated expressions if need be. I have already written code to handle arithmetic expressions, which needs relatively little modification to handle assembler labels within expressions. See previous ACC discs for the article and accompanying code. Translating Code ---------------- The primary routines for translating code need to be able to separate the text line being read into up to four component parts. These are: 1) Any preceding labels used by branch instructions at other points in the code where present; 2) The opcode mnemonic itself, e.g., LDA; 3) The operand if an operand is present; 4) Any trailing comments where present (the standard syntax for virtually ALL assemblers for comments is to use the ';' character to precede it. Since part 2), the opcode, should ALWAYS be present, first let us see how to detect an opcode. I shall use 68000 assembler routines to perform this task, but the theory applies whatever the chosen development language. The routine I shall use to check if an operand IS an opcode is called GetOpcode() (surprise, surprise). The code is supplied below: * GetOpcode(a0,a1) -> d0,a2 * a0 = ptr to string to test * a1 = ptr to array of BCPL strings for legal opcodes * Check if the string contains the given opcode. Handling * of the postfix letters done separately. * Returns: * d0 : opcode number (for jump table) if valid opcode * -1 if error * a2 : ptr to located opcode if d0 valid * d0-d3 corrupt GetOpcode movem.l a0-a1,-(sp) ;save text & opcode pointers moveq #0,d0 ;initial opcode number GTO_1 move.l a1,a2 ;copy current opcode ptr moveq #0,d1 move.b (a1)+,d1 ;get char count beq.s GTO_5 ;oops-hit list end GTO_2 move.b (a0)+,d2 ;get source char move.b (a1)+,d3 ;get opcode char and.b #$DF,d2 ;convert to and.b #$DF,d3 ;upper case cmp.b d2,d3 ;chars equal? bne.s GTO_3 ;skip if not subq.w #1,d1 ;done all chars? bne.s GTO_2 ;back for more if not movem.l (sp)+,a0-a1 ;recover text, opcode pointer tst.w d0 ;and signal success rts GTO_3 move.l (sp),a0 ;get text pointer GTO_4 addq.l #1,a1 ;skip past this opcode subq.w #1,d1 ;skipped it? bne.s GTO_4 ;back if not subq.l #1,a1 ;correct ptr to BCPL string! addq.w #1,d0 ;new opcode number bra.s GTO_1 ;and try next opcode GTO_5 movem.l (sp)+,a0-a1 ;recover pointers and moveq #-1,d0 ;signal failure rts The use of this routine is simple. Create a table of strings for the opcodes such as this example table (which is incomplete:modify it to suit your own purposes): OpcodeTable dc.b 4,"ADC",0 dc.b 4,"AND",0 dc.b 4,"ASL",0 dc.b 4,"BCC",0 ... etc. The first byte of each entry is the length of the string being scanned for, and the remaining bytes for each entry are the opcode strings. Note that I have terminated all of the opcode strings with null bytes. There is a reason for this (as there usually is in my code!), namely to prevent the main string scanning routine confusing labels with opcodes in lines such as: rolex ROL A where if provision to ensure an exact match was not made, the scanner would mistakenly treat the label as an instruction of the form "ROL EX" or similar. This problem is not so great in 6502 assembler, but manifests itself far more in the case of 6809 assembler which has instructions such as: NEGA NEG memory where a scanner that tries to locate the "NEG" part first and then obtain the destination register operand would find itself in trouble with label clashes. Ok, so we have a routine that can test a string to see if it is truly an opcode. By changing the opcode table above, we can use the same routine in the case of 6502, Z80, 6809 or any other assembly language. Now comes the harder part. We need to split up the line into its com- ponent parts. Two low-level routines are needed to assist this process, name- ly SkipSpace() and SkipChars(): * SkipSpace(a0) -> a0,CCR * a0 = ptr to string to skip along * Skips spaces and TAB chars until either: * 1) End of String (EOS) met (null byte at end of string) * 2) A non-space character hit. * Sets Z flag if EOS met. SkipSpace tst.b (a0) ;EOS met? beq.s SkippedSpace ;exit if so cmp.b #" ",(a0) ;hit space? beq.s SKS_1 ;branch if so cmp.b #9,(a0) ;hit TAB? beq.s SKS_1 ;branch if so tst.b (a0) ;ensure correct CCR state! SkippedSpace rts SKS_1 addq.l #1,a0 ;point to next char bra.s SkipSpace ;and resume scan * SkipChars(a0) -> a0,CCR * a0 = ptr to string to skip along * Skips non-space chars until either: * 1) End of String (EOS) hit * 2) A space or TAB hit * Sets Z flag if EOS met. SkipChars tst.b (a0) ;hit EOS? beq.s SkippedChars ;exit if so cmp.b #" ",(a0) ;hit space? beq.s SkippedChars ;branch if so cmp.b #9,(a0) ;hit TAB? beq.s SkippedChars ;branch if so addq.l #1,a0 ;point to next char bra.s SkipChars ;and resume scan SkippedChars tst.b (a0) ;ensure correct CCR state! rts Now the trick that is needed is how to use these routines. However, before it is possible to proceed, the ability to handle labels as and when they arrive needs to be covered. This process now follows. Labels, Symbol Tables & Hashing ------------------------------- First, what is a symbol table? A symbol table is a vital requirement for assemblers, and is quite simply a table of encountered labels plus their associated addresses. The structure that I shall use for the symbol table is as follows: 14 bytes : label text, up to 13 characters plus a trailing null character. 2 bytes : Assembly address of this label. Now, the first problem that is encountered is this. How do we insert a label into a symbol table? Second, how do we retrieve it for future reference by a line containing an instruction referencing that label? The bad news is that simple sequential insertion into an array is NOT valid. This would be okay if the source code being passed through the assem- bler only contains a few labels. But what if the source file is large, and is littered with hundreds or even thousands of labels? Trawling through an array in a sequential search becomes time-consuming after a few elements, so some means of speeding access regardless of the number of entries contained within the symbol table. Welcone to hashing! Hashing is the process used by assemblers to make symbol table access as fast as possible. The principle is quite simple. Take the text to be inserted, and use it to generate a number that can be used to index into the symbol table. Then use that index to insert the label plus the associated address into the symbol table. Once this is done, any access that is needed to that label can be performed quite simply, by using the same pro- cedure to generate the index into the table once again, and then using this index to recover the data. The access time is the same regardless of how big the symbol table is while the table is less than 50% full. Hashing sounds like the dream solution to the problem of accessing a symbol table quickly, but it has one handicap. The method used to generate an index into the table relies upon the text string being passed to it, and it is possible for two different strings to generate the SAME number. This situ- ation is called a COLLISION, and hash routines need to have collision correc- tion built in to handle such a situation. Below is the symbol table handling code that I have used in the past, tested and working, requiring merely that you insert the routines into your own code and call them with the given parameters. First, the routine to gen- erate the hash code: * HashCode(a0) -> d7 * a0 = ptr to label string to generate hash code for * returns hash code in d7 (which is offset within the * hash table). * d0 corrupt HashCode move.l a0,-(sp) ;save label pointer moveq #0,d7 ;initial hash code move.l d7,d0 HashCode_1 move.b (a0)+,d0 ;get char beq.s HashCode_2 ;EOS met-exit add.l d7,d7 ;create hash code add.l d0,d7 ror.l #8,d0 ;was ASL not ROR eor.l #$3AC210D9,d0 ;randomly chosen magic no. add.l d0,d7 bra.s HashCode_1 HashCode_2 move.l (sp)+,a0 ;recover text ptr and.l #$FFF,d7 ;constrain to range 0-4095 lsl.l #4,d7 ;make offset within hashtable rts This routine will generate a hash code that acts as an offset into a symbol table made up of elements of 16 bytes in size, structured as stated above, & constrained to access a symbol table 64K in size. Alterations to HashCode() can be made to accomodate larger symbol tables of course. The offset gener- ated within the HashCode() routine is designed to be added on to the pointer to the symbol table to reference the desired element. Now, to handle collisions, the ReHash() routine below is used. This takes the current hash number, and spits out a new one. This routine is used whenever a collision is encountered: * ReHash(d7) -> d7 * d7 = Hash code returned by HashCode() above * returns a new hash code in d7 * Used to create a new hash code if a hash table collision * occurs. * d0 corrupt ReHash move.l d7,d0 add.l d7,d7 ;create hash code add.l d0,d7 ror.l #8,d0 ;was asl eor.l #$FA198E26,d0 ;randomly chosen magic no. add.l d0,d7 addq.l #1,d7 ;prevent self-locking! and.l #$FFF,d7 ;constrain to range 0-4095 lsl.l #4,d7 ;make offset within hashtable rts The DoHash() routine below uses HashCode() and ReHash() to keep trying for a hash number corresponding to a free hash slot. Once a free hash slot has been found, then the routine returns with the appropriate hash code. WARNING : IF THE SYMBOL TABLE IS FULL, THIS ROUTINE LOCKS UP! * DoHash(a0) -> d7 * a0 = ptr to label text to hash for * Performs a HashCode(), then if collision occurs, performs * a ReHash() until free slot occurs. * d0/a1 corrupt DoHash bsr HashCode ;get 1st hash code DoHash_1 move.l d7,a1 add.l symtab(a6),a1 ;ptr to symbol table entry tst.b (a1) ;occupied already? beq.s DoneHash ;exit if so bsr ReHash ;else get another hashcode bra.s DoHash_1 ;and check that one DoneHash rts Having set up the routines for the symbol table, we now need routines capable of referencing the symbol table, inserting new labels into the symbol table, and checking to see if a label has already been inserted. First, the routine to check for whether a label exists in the table (which needs a variable cal- led 'symtab' to be defined in a GenAm RS section, and referenced off A6): * LabelExists(a0) -> d7,a1,CCR * a0 = ptr to label text * Checks to see if a label exists in the symbol table. * After calling this code, use BEQ to branch if label exists. * Also, returns either: * Hash code of label if it exists, or * Hash code of next free slot in the hash table in d7, * and symtab ptr in a1 to either the existing label * or the next free slot. * d0-d1/d7/a1 corrupt LabelExists bsr HashCode ;get hash code for label LEX_1 move.l d7,a1 add.l symtab(a6),a1 ;ptr to label move.b (a1),d0 ;get 1st char seq d0 tst.b d0 ;label exists? bne.s LEX_Done ;skip if not bsr CmpStr ;compare strings beq.s LEX_Done ;skip if it's this one! bsr ReHash ;else try a new hash slot bra.s LEX_1 LEX_Done rts LabelExists() takes account of possible collisions, checking to see if the label text located matches that passed to the routine. It returns a pointer to the symbol table entry (or next free slot) in A1, and the hash code for that entry in D7. Now a routine to insert a new label into the symbol table. The rou- tine InsertLabel() inserts a new label into the symbol table, returning an error code (corresponding to a 'label already defined' error within an assem- bler program) if the label already exists and has been defined. * InsertLabel(a0,d0) -> d0 * a0 = ptr to label text to insert into symbol table * d0 = address to insert with symbol * Inserts label into symbol table with the given address. * If label already exists, return error code in d0 (NULL if ok). * d1/d7/a1 corrupt InsertLabel move.w d0,-(sp) ;save address bsr LabelExists ;already in table? beq.s ISL_1 ;skip if so move.l a1,-(sp) ;save symtab ptr moveq #_LABELSIZE,d0 ;max label size bsr CopyLabel ;insert label move.l (sp)+,a1 ;recover symtab ptr move.w (sp)+,d0 ;recover address move.w d0,14(a1) ;insert address into table moveq #0,d0 ;signal all's well rts ISL_1 tst.w (sp)+ ;clean up stack moveq #_ERR_ISDEF,d0 ;signal failure rts The final routine is one to obtain the value of a label that has been inser- ted into the symbol table, for use within an arithmetic expression, for exam- ple. A call to this routine would be required within the expression handling code to obtain the value of the label within an expression, and provision for handling undefined forward references needs to be included during the first assembly pass. The GetLabel() routine appears below: * GetLabel(a0) -> d0,d1 * a0 = ptr to label text within an expression string * Get the value of the label embedded within an expression * string if it exists, and return an error code if no value * exists (on Pass 2 only!) * Returns: * d0 = error code (0=valid label found, -1=failed) * d1 = value of label if valid label found * a0 corrupt GetLabel movem.l a1-a2,-(sp) ;save these-needed elsewhere lea labelbuf(pc),a1 ;point to conversion buffer move.l a1,a2 GLB_1 move.b (a0)+,d0 ;get label char beq.s GLB_7 ;copy EOS if hit! cmp.b #"0",d0 ;before "0"? bcs.s GLB_2 ;don't copy if so cmp.b #"9",d0 ;within 0-9 range? bls.s GLB_3 ;copy if so cmp.b #"A",d0 ;before "A"? bcs.s GLB_2 ;don't copy if so cmp.b #"Z",d0 ;within A-Z range? bls.s GLB_3 ;copy if so cmp.b #"_",d0 ;underscore? beq.s GLB_3 ;copy these cmp.b #"a",d0 ;before "a"? bcs.s GLB_2 ;don't copy if so cmp.b #"z",d0 ;within a-z range? bhi.s GLB_2 ;don't copy if not GLB_3 move.b d0,(a1)+ ;copy char bra.s GLB_1 ;and back for more GLB_2 moveq #0,d0 ;force EOS on illegal char GLB_7 move.b d0,(a1) ;save EOS move.l a0,-(sp) ;save new text pointer! move.l a2,a0 ;recover ptr bsr StrLen ;get label length cmp.w #_LABELSIZE,d7 ;too long? bls.s GLB_4 add.w #_LABELSIZE,a0 clr.b (a0) ;else put EOS here GLB_4 move.l a2,a0 bsr LabelExists ;found it? beq.s GLB_5 ;skip if so moveq #-1,d0 bra.s GLB_6 GLB_5 move.l a1,a0 add.w #_LABELSIZE+1,a0 ;point to label code move.w (a0),d1 moveq #0,d0 GLB_6 movem.l (sp)+,a0-a2 ;recover text & operator ptrs rts This covers symbol tables and label handling. Now comes the main scanner code that the assemblr will need - the heart of any assembler. Single-Line Assembly -------------------- Several variables will need to be maintained by the assembler. By far and away the most important will be the current value of the program counter, whose value will have to be set (either initialised to zero or set during the assembly by an ORG directive or similar) prior to the start of each assembly pass. So, assuming that a line of 6502 assembly source has been read by the program, a routine to scan the line and split it into its various components is needed. The following routines perform this task, but if you are to copy these routines to your own code, take note that they require various equates and RS defined variables that are not included below! Scan the code below for the required missing equates and variables (which should ALL be defined using GenAm RS directives, and referenced via a memory block pointed to by A6 and allocated using the Exec AllocMem() call). First, InitParser() sets some variables prior to performing the ass- embly of the given line: * InitParser(a6) * a6 = ptr to main variable table * Initialise those variables that require resetting * for each call of the line parser. * d0/a1 corrupt InitParser moveq #0,d0 move.l d0,currlabel(a6) ;ptr to label move.w d0,operand(a6) ;operand value move.w d0,defcount(a6) ;no of BYTES of DEFB/DEFW move.b d0,opsize(a6) ;size of opcode move.b d0,gotargs(a6) ;whether args found or not move.w d0,error_code(a6) ;ensure no repeat errors! move.w pc_value(a6),oldpc_value(a6) moveq #-1,d0 move.w d0,opcodenum(a6) rts Note that the variable opcodenum(a6) is set to -1. This is the value for an illegal opcode (i.e., one not recognised as a legal opcode by the assembler). When the line parser scans the line, a call to GetOpcode() will return -1 for an unrecognised instruction, and a value from zero upwards for one of the le- gal 6502 opcodes (or whatever opcodes are legal within the assembler of your choice). The following routine performs the actual line scan: * ScanLine(a6) -> d0 * a6 = ptr to main variables * Split text line into various arguments. Then save * pointers to them, plus various relevant data. * Note:this time, will NOT get its wires crossed if a label * looks like an opcode because of a new opcode list! * Returns : * d0 = NULL if no error found * error code if an error was located * See INCLUDES/MainEquates.i for list of error codes. * d0-d1/a2 corrupt ScanLine move.l readptr(a6),a0 ;ptr to current line to read move.l a0,a1 ;copy ptr SCL_FEOS tst.b (a1)+ ;skip past EOS for this line bne.s SCL_FEOS move.l a1,readptr(a6) ;this is ptr to next line bsr SkipSpace ;find 1st true char beq SCL_Done ;EOS met-exit NOW cmp.b #";",(a0) ;hit comment? beq SCL_Done ;exit NOW if so move.l a0,-(sp) ;save ptr to 1st char bsr SkipChars ;skip past last char move.l a0,endptr(a6) ;save text ptr move.b (a0),endchar(a6) ;and character pointed to clr.b (a0) ;temp insert EOS move.l (sp)+,a0 ;recover text ptr lea opcodes(pc),a1 ;point to opcode list bsr GetOpcode ;is it an opcode? bpl.s SCL_1 ;skip if so cmp.b #1,pass(a6) ;Pass 1? bne.s SCL_2 ;skip if not move.w pc_value(a6),d0 bsr InsertLabel ;else treat text as label tst.w d0 ;error? bne SCL_Exit ;exit NOW if so move.l a1,currlabel(a6) ;save label ptr SCL_2 move.l endptr(a6),a0 ;get end pointer move.b endchar(a6),(a0) ;reset char bsr SkipSpace ;find next true char beq SCL_Done ;null line cmp.b #";",(a0) ;hit comment? beq SCL_Done ;ignore it move.l a0,-(sp) ;save ptr to it bsr SkipChars ;find end move.l a0,endptr(a6) ;save ptr to it move.b (a0),endchar(a6) ;save end char clr.b (a0) ;temp EOS move.l (sp)+,a0 ;recover start ptr lea opcodes(pc),a1 ;opcode list bsr GetOpcode ;found one? bpl.s SCL_1 ;skip if so moveq #_ERR_INST,d0 ;else signal error bra.s SCL_Exit ;and exit SCL_1 move.w d0,opcodenum(a6) ;save opcode number move.l a2,opcodeptr(a6) ;and opcode string ptr move.w d0,d2 move.l endptr(a6),a0 ;get end pointer move.b endchar(a6),(a0) ;reset char bsr SkipSpace ;find next true char beq.s SCL_Done ;null line cmp.b #";",(a0) ;hit comment? beq.s SCL_Done ;ignore it cmp.b #_QUOTE,(a0) ;start of text arg? bne.s SCL_3 ;skip if not move.l a0,-(sp) ;save text ptr addq.l #1,a0 ;point past quote SCL_4 move.b (a0)+,d0 ;get char beq.s SCL_5 ;exit if EOS hit cmp.b #_QUOTE,d0 ;hit end quote? beq.s SCL_5 ;skip if so cmp.b #"\",d0 ;backslash? bne.s SCL_4 ;scan more chars if not addq.l #1,a0 ;point past following char bra.s SCL_4 ;and continue SCL_5 clr.b (a0) ;append end EOS bra.s SCL_6 ;and continue SCL_3 move.l a0,-(sp) ;save ptr to it bsr SkipChars ;find end move.l a0,endptr(a6) ;save ptr to it move.b (a0),endchar(a6) ;save end char clr.b (a0) ;temp EOS SCL_6 move.l (sp)+,a0 ;recover start ptr move.l a0,argptr(a6) ;save ptr to operand st gotargs(a6) ;we have an operand SCL_Done moveq #0,d0 ;signal all's well SCL_Exit rts Read the comments included above carefully, and take note of how the routine handles null lines (lines consisting of a lone ASCII NUL character) or lines containing only an initial label (these lone labels are still inserted into the symbol table), or lines that contain only comments. Once this routine has set various variables, other routines can be called to take these variables & use the data to perform the actual assembly itself. Below is the MakeCode() routine that takes the opcode number, and uses it to obtain the address of a routine to handle the given opcode from a jump table: * MakeCode(a6) * a6 = ptr to main program variables * Perform actual machine code generation for a given * set of parameters (opcode number, address mode etc). * d0/a0 corrupt MakeCode moveq #0,d0 move.w opcodenum(a6),d0 ;opcode number bmi.s MakeCode_4 ;there isn't one! add.l d0,d0 add.l d0,d0 ;jump table offset lea AdModeTable(pc),a3 add.l d0,a3 ;ptr to ptr move.l (a3),d0 ;ptr to routine beq.s MakeCode_1 ;skip if nonexistent move.l d0,a3 jsr (a3) ;execute it! MakeCode_1 move.w d0,-(sp) ;save any error moveq #0,d0 move.w opcodenum(a6),d0 ;opcode number add.l d0,d0 add.l d0,d0 ;jump table offset lea MakeMC(pc),a3 add.l d0,a3 ;ptr to ptr move.l (a3),d0 ;ptr to routine beq.s MakeCode_2 ;skip if nonexistent move.l d0,a3 jsr (a3) ;execute it! move.b timing1(a6),d1 add.b timing2(a6),d1 ;create total move.b d1,totime(a6) ;timing value MakeCode_2 move.w (sp)+,d1 ;get 1st error beq.s MakeCode_3 ;none, so skip move.w d1,d0 ;else signal this rts MakeCode_3 tst.w d0 ;signal IF 2nd error! rts MakeCode_4 moveq #0,d0 rts Note that the routines in the jump tables (one for obtaining the addressing mode for each opcode, one to perform the actual generation of machine code) MUST be in the same order as the list of opcodes being referenced by calls to the GetOpcode() routine, otherwise all hell will break loose! Below, the ParseLine() routine performs the entire single-line assem- bly function in one go: * ParseLine(a6) * a6 = ptr to main variable block * Separate text arguments from line, then create data needed * for full assembly of given instruction. * d0-d1/a2 corrupt ParseLine addq.l #1,linenum(a6) ;update line count addq.l #1,linefile(a6) ;update line count bsr.s InitParser ;set up parser PSL_1 bsr ScanLine ;create assembly data move.w d0,error_code(a6) ;save error code bsr MakeCode ;then create opcode beq.s PSL_Done move.w d0,error_code2(a6) PSL_Done rts Jump Tables ----------- Having obtained various useful pieces of information such as which of the opcodes has been discovered, the next stage is to perform functions such as address mode evaluation and then the actual assembly. Since these proced- ures may differ for each opcode (in general, instructions fall into one of a limited number of classes, and address mode handling can be broken up into a collection of routines to handle each of these classes), the best way to han- dle these is via jump tables. The routines thus far displayed assume that two jump tables exist, a jump table for address mode evaluation (the 'AdModeTable' label found within the MakeCode() routine) and another for actual machine code generation (the 'MakeMC' label within MakeCode() again). It is usual to write separate routines to handle each type of addres- sing mode, and then write higher-level routines that call each of the indivi- dual address mode evaluation routines in a certain sequence. Pointers to each of these higher-level routines are then placed into the address mode jump ta- ble. For example, in 6502 code, ADC, SBC, AND, ORA and EOR all follow the same pattern for operand addressing modes. So it would be wise to write seve- ral routines to scan for each of the possible addressing modes, for example: CheckAbsolute() CheckIndexed() CheckIndX() CheckIndY() CheckImmediate() and then write a routine called CheckADCType() that calls each of these in turn. In the address mode jump table, place pointers to CheckADCType() in the positions corresponding to the various instructions requiring this routine, as in: AdModeTable dc.l CheckADCType ;ADC dc.l CheckADCType ;AND ... ;some others dc.l CheckADCType ;CMP ... etc. Then, where the actual opcodes follow a pattern, as in ADC, EOR etc., write a routine to handle them all as a group, for example DoADCType(), and place in the second jump table pointers to this routine as shown above. MAKE SURE THAT THE TABLE ENTRY POSITIONS MATCH! As an example of the sort of code that can be used, I present a copy of the CheckImmediate() routine used to check for immediate mode operands. It should give you some idea of the sort of code that is needed. NOTE:this rou- tine needs the expression handler from a previous ACC disc in order to work, as well as several equates defined AND tables of operators for the expression handler provided! * CheckImmediate(a0,a6) -> d0,d1 * a0 = ptr to operand argument to scan * a6 = ptr to main program variables * Returns: * d0 = _ADR_IMM if true immediate operand ("#" found) * -1 if not * d1 = value of immediate operand if d0=_ADR_IMM * zero if d0=-1 but no error found * error code if d0=-1 and error found * Tested & works for constants AND labels! * d0-d5/a0-a3 corrupt CheckImmediate move.l a0,-(sp) ;save text ptr cmp.b #"#",(a0)+ ;is it an immediate operand? bne.s CIM_2 lea CompOps(pc),a1 lea Funcs(pc),a2 bsr DoExp ;get its value bne.s CIM_2 ;skip if error found moveq #_ADR_IMM,d0 ;set addr mode bra.s CIM_1 CIM_2 moveq #0,d1 moveq #-1,d0 CIM_1 move.l (sp)+,a0 rts I leave it to you to write routines to scan for legal indexed and indirect operands for a 6502 assembler (after all, why should I do ALL of the work?). Extra Information For Assemblers -------------------------------- An important factor in the coding of an assembler is the order that a given processor stores its address operands. For the 6502, the order of storage of an address operand is as follows: Instruction: LDA $3080 (6502, 3 bytes) Stored At: Address $4000-$4002 Memory Map: $4000 : $AD (opcode byte) $4001 : $80 (low byte of address) $4002 : $30 (high byte of address) This is also the same as the order for the Z80 processor. Motorola processors store their addresses in the reverse order, as in: Instruction: LDAA $3080 (6800, 3 bytes) Stored At: Address $4000-$4002 Memory Map: $4000 : $B6 (opcode byte) $4001 : $30 (high byte of address) $4002 : $80 (low byte of address) Take care when assembling operands of this form-check the storage order of the given processor! Note that high-byte first order applies to the 680x0 series too, namely: Instruction: MOVE.W $1A000,D0 Stored At: Address $20000-$20006 Memory Map: $20000 : $3039 $20002 : $0001 $20004 : $A000 Intel 80x86 processors cause far more headaches. They sometimes need 32-bit address data, stored in the following order: Byte 1 : Offset, Low Byte Byte 2 : Offset, High Byte Byte 3 : Segment, Low Byte Byte 4 : Segment, High Byte and also need provisions for different forms of the CALL and RET instructions when taking into account that the routines being called and returned to exist in different segments (those who haven't encountered the 8086, be warned:its segmented memory addressing scheme is bloody horrible!) or exist within the same segment. This changes again when moving on to 80286 and 80386 chips with 32-bit memory addressing extensions, and 80386 chips operating in 'virtual 8086' mode (if you can't handle the prospect of 16 terabytes of virtual add- ress space and 65,536 emulated 8086s in parallel, don't ask about the fancier features of 80386 chips!). Intel processors have more headaches to take account of (80x86 again). Extensions to 80286 and 80386 instruction sets (and 80486 with the maths co- processor instructions) from the basic 8086 scheme have their own problems. I do not have information about the 8087/80287/80387 mathematics coprocessors, or their instruction sets, but they use the IEEE standard for mathematics co- processor instructions (similar to Motorola 68881/68882), and the 80486 is a combination of 80386 and 80387 on one chip. I hasten to add that writing an assembler for the 80486 is a daunting task! And should that be insufficient challenge, try the latest 80586 from Intel, with RISC instruction extensions and Harvard Architecture features. I guarantee that you'll have LOTS of fun writing an assembler for this chip! A Complete Example Assembler ---------------------------- As promised in an earlier letter to ACC, I shall provide for the de- light and delectation of you all a complete example of how an assembler pro- gram is written. The example is NOT, you will be sad to find out, a 6502 as- sembler, the creation of that is up to you for now (hence this article). The assembler in question is a 6809 assembler (which is a much greater challenge to the assembler writer) and I include the source code for its version 1.0 incarnation which CANNOT yet be used for 6809 development work as it contains a bug (resulting in non-functioning 6809 programs if attempts are made to use it to the full). The exact nature of the bug and the fix required is left as an exercise for the adventurous ACC coder. Should anyone want a WORKING 6809 assembler, Version 2.0 of the pro- gram is now available, FULLY TESTED AND BUG-FREE, for a small shareware fee (come on, five quid isn't much to pay for a fully working cross assembler for the 6809 processor, is it?). For the Version 1.0 incarnation (which is pro- vided solely for tutorial purposes to ACC) see the files: a6809.s a6809.i A6809.DOC for more information on such matters as 6809 assembly language, how the A6809 program operates, and some other details. Have fun picking the code apart! Some Processors To Choose From ------------------------------ An obvious choice for Amiga programmers is the 68000 itself, and now that I've added a COMPLETE description of the 68000 instruction set WITH THE BINARY OPCODES to the DOCS DISC (also see ACC18 for typed_68000.doc) then it is only a matter of time before someone out there writes a PD assembler for the Amiga. Such persons might like to consider extending the instruction set to take account of the 68010 (also supplied on the file), and then moving on to the 68020/68030 (to keep A2000 and A3000 owners happy). Finally, there is the mega-powerful 68040 (with built-in floating-point coprocessor, based upon the 68882) which will REALLY test your coding abilities! Then of course there's the Intel 80x86 series, as found on PCs world- wide. A cross assembler for these will make the Amiga a handy development ma- chine (especially as it's the only low-cost one that multitasks properly!), but be warned. I have access to the 8086 instruction set (but am still look- ing for 80286/80386) and it's BLOODY AWFUL. Tackle this one if you're feeling brave (especially the 80486!). This series has coprocessors (the 80x87 series of chips) which behave on Intel machines in a manner similar to the 68881 and 68882 on 680x0-based machines. Then there's the good old 8-bit processors. 6502 for ex-C64 owners who have still kept their C64, Z80 for ex-Spectrum/Amstrad CPC owners (like myself), and 6800 family for anyone who still has a machine in the cupboard built by SWTP (who?) way back in '78. And just to make life even more interesting, how about the TMS9900, as found on the Texas TI99/4A and inside various military computers? This is an oddity, having no registers other than a program counter and a workspace pointer, which allows it to treat a block of memory locations as if they are internal chip registers! Of course, processors have moved on even from the 68040, and there is a new generation of chips available. The 32-bit ARM3 from Acorn, powerhouse of the Archimedes (nice but TOOOO expensive) with guaranteed 13 MIPS speed is a nice chip to tackle because its instructions are all laid out in bit fields within the opcodes. Have fun with this one! Then there are the super-chips. First, the Intel i860, supercomputer on a chip. Performs two floating-point multiplies in one clock cycle using a pipelining technique, and according to some hits 25 MIPS. Not for the faint- hearted. The i860 has an instruction set that looks like a conventional ass- embler instruction set, yet has parallel-processing features and exists in versions with clock speeds up to 50MHz (yielding 25 integer MIPS and 4.5 LIN- PACK MFLOPS performance). Why not try something really unusual? The Texas Instruments TMS34020 megachip as found in high-power graphics workstations (usually as an off-the- peg alternative to a blitter) can handle instructions of any bit width from 1 to 32 bits (as far as I know) and can hit 20 MIPS speed (how about a 19-bit add followed by an 11-bit multiply? The TMS34020 can do it!). It's also much in demand by companies developing virtual reality systems, so if you want to make a few grand, write an assembler for it (VERY HARD THOUGH!). And at last we hit the Inmos T800. Better known as the Transputer, it is a chip that is purpose-designed for multiprocessor systems, and on its own can hit 10 MIPS with ease (that's at 10 MHz too!). Of course, this one's much harder than the rest because of the built-in high-speed multiprocessor commu- nications, and the fact that its instruction set is the weirdest in existence on ANY processor this side of Alpha Centauri according to those who have had dealings with it. You COULD write an assembler for it, but you'll find that a transputer assembler needs MUCH more than the basic opcode translation feat- ures of standard assemblers (you'll need code to allow transputer assembler source to be distributed across processor networks!) and the bizarre nature of its instruction set alone should put off all except terminal hack-freaks such as myself! Bibliography ------------ The following titles are all of interest. Where exact authorship de- tails are unknown, this is signified with a '???', and ditto for unknown ISBN numbers. Those texts not specifying the covered processors in the titles have this information in brackets after the title. Also, Sybex book titles include where possible the Sybex catalogue number for ordering direct. Note:there are no titles for the Intel 8080 listed. The Intel 8080 (dating back to 1976) is covered in Z80 programming manuals, since the Z80 is an extended 8080 with a superior hardware configuration to the original (virtually nobody uses 8080s or 8085s any more, systems containing them have all upgraded to the Z80). The Intel 8080 official mnemonics are listed in the Sybex book on Z80 programming (see below). Furthermore, some instruction sets have restricted access. The Inmos T800 (Transputer) is restricted because Inmos is trying to force people into buying a £25,000 development system using the OCCAM-2 language, but it hasn't stopped some adventurers from obtaining the instruction set. Also, Inmos have changed the instruction set when upgrading from the T414 to the T800, while making the OCCAM-2 development system compatible with both sets (again an at- tempt to manipulate the market) so writing a T414/T800 compatible assembler is not for the fainthearted. In any case, they have the weirdest instruction sets known this side of Alpha Centauri (and probably beyond too). Access to several other instruction sets are restricted because the processors are of military origin (Ferranti F100L) and if you could get access to the instruc- tion sets, then so could a host of undesirables with far greater resources than you (e.g. dear old Saddam in Iraq, Kim Il Sung in North Korea and other personae non gratae) and use them for their own purposes (don't be fooled by the large CEP of an SS-1C SCUD-B missile, it's not controlled by strings or valves you know!). In any case, many military processors have built-in digi- tal signal processing hardware and instructions to manipulate said hardware, and unless you're hooking your Amiga up to an AWACS radar intallation you'll not be needing this feature! For those instruction sets whose access is open to the software dev- elopment community, the titles below should be of assistance. Programming The 6502 By Rodnay Zaks Publisher:Sybex (cat. no C202) ISBN 0 89588 046 6 Programming The Z80 By Rodnay Zaks Publisher:Sybex (cat. no C280) ISBN Programming The 6809 By Rodnay Zaks & William Labiak Publisher:Sybex (cat. no C209) ISBN 0 89588 078 4 Programming The 8088/8086 By James W Coffron Publisher:Sybex ISBN ??? Programming The 68000 By ??? Publisher:Sybex ISBN ??? Programming The Z8000 By Richard Mateosian Publisher:Sybex (cat. no C281) ISBN ??? Assembly Language Programming For The 6502 By Lance A Leventhal Publisher:Osborne McGraw-Hill ISBN ??? Assembly Language Programming For The Z80 By Lance A Leventhal Publisher:Osborne McGraw-Hill ISBN ??? Assembly Language Programming For The 6809 By Lance A Leventhal Publisher:Osborne McGraw-Hill ISBN ??? Assembly Language Programming For The 68000/68010/68020 By Lance A Leventhal Publisher:Osborne McGraw-Hill ISBN ??? MC6809-MC6809E Microprocessor Programming Manual By ??? Publisher:Motorola ISBN ??? 6809 Microcomputer Programming And Interfacing, With Experiments By Andrew C Staugaard Jr Publisher:Howard W Sams & Co ISBN ??? The 6809 Cookbook By Carl R Warren Publisher:TAB Books Inc ISBN ??? Intel iAPX86 Series Manual (8086/80286/80386) By ??? Publisher:Intel Corporation ISBN ??? Intel iAPX486 Manual (80486) By ??? Publisher:Intel ISBN ??? Motorola MC88000 Series Manual (88000/88100) By ??? Publisher:Motorola ISBN ??? International Microprocessor Dictionary (ALL) By ??? Publisher:Sybex ISBN ??? The Texas TMS Series (9900/99000/34020) By ??? Publisher:Texas Instruments ISBN ???