HOW TO DISASSEMBLE THE ROM | |||||||||||||
[Or How to Write an Optimised Disassembler for the ZX81]There are three "levels" at which we may disassemble, each slightly more sophisticated than the previous. The first two levels are not all that satisfactory, but they are very easy to program.The first "level" we have already achieved - the USR routine HLIST which we saw earlier in the book will do this for us. That is, given an address such as 0808 it will produce an output like this:
and so on. This is not really disassembly, although you can of course look these bytes up in the tables at the back of the book, but it's quite a time consuming task, and you're also very likely to get lost halfway through. The second "level" is not much better, but again is quite easy to program. What I'm talking about is an output something like this:
and so on. As you can see, each instruction has its component bytes listed out to exactly the right length. This produces a very pleasing display, and there is little or no chance of you "getting lost" when actually looking these bytes up in tables. The third "level" is the one we are actually aiming at - the one everybody wants. What we'd really like is an output like this:
and so on. This can be quite easy to program - simply make the computer look up the appropriate words from a table instead of doing it ourselves - however this would take up rather a large amount of space just to store the table. Around 4K in fact. The method I will describe to you will allow such a program to fit in just 1K, but be warned: it's rather difficult. There is actually a "fourth level" of disassembly, which I won't even attempt to touch, but you may like to think about. Imagine an output like this:
As I've said, I'm not even going to touch this one. The only extra it involves is storing yet another table, this time containing all of the labels used. Let's go back a bit now to something relatively simple. Let's consider a slightly improved version of HLIST which reaches the "second level" of disassembly, and works out the length of each instruction before printing it. All we need is a table containing just two pieces of information for each byte. These are a) the number of bytes in an instruction beginning with this byte, and b) the number of bytes in an instruction beginning with DD or FD followed by this byte. As you know, some confusion may arise over those instructions beginning with CB or ED, but we don't actually need any tables or anything to cope with these provided we remember the following rules:
As you can see, there are sixteen rows, and sixteen hex digits in each row. Those instructions beginning with DD or FD which do not exist, such as DD00, have been simply assigned the appropriate number of bytes as if the DD/FD were not there. The following program will "disassemble" to a string of bytes of the right length. It assumes that the table LENS exists, and it assumes that a subroutine HPRINT exists which prints the contents of the A register in hexadecimal without corrupting the other registers. This subroutine was in fact given earlier on in the book. [Thunor: I recommend using chapter11-hexld3d.p so that you can make use of the available HPRINT and address input mechanism. Therefore I've taken the liberty of adding a couple of instructions near the top and updated a couple of relative jumps lower down so that you can achieve this.] [Thunor: I should point out that this program works if you are using it to view valid code, but it doesn't deal with invalid prefixed instructions. Because of this I chose to build upon the author's work and create something more suitable; my enhanced version is listed here.]
Download available for 16K ZX81 -> chapter16-lenslist.p.[Set RAMTOP to 4A00 (18944) with POKE 16389,74/NEW. Type RUN to use LENS LIST. Addresses used: 4A82 to 4B77 is occupied by HEXLD3D, LENS is 4A00, HPRINT is 4A82 and LLIST is 4B78 (19320). To test it, list 4B78 and match the output to the listing above. For a more thorough test, list 4A82 and match it with HEXLD3 in appendix one, remembering that it's been relocated from 4082 to 4A82.]Now we ascend to the "third level" - REAL disassembly in other words. However, I am not going to write the program for you this time round - you'll have to do it by yourself. I will explain precisely what it is you have to do in order to make a 1K disassembler, but the actual program itself must be your creation. DISASSEMBLING THE ROMThe following is an algorithm which will enable you to disassemble the hex codes into assembly, that is to change, for example, 69 to LD L,C, or from CB7E to BIT 7,(HL). One way would be to list a vast table - such as I have included in the appendices - but while alright for human beings it lacks the elegance of a well thought out computer program. The data alone would occupy around 4K. This algorithm will enable you to write your own machine language program occupying significantly less - two or even 1K all told depending on how efficient your program is.In this algorithm, the following conventions will be used:
Define two variables, CLASS and INDEX, and initially let both of them equal zero. Write the byte being disassembled in binary, and split it into three parts; F, G, and H. F consists of bits 7 and 6, G of bits 5, 4, and 3, and H of bits 2, 1, and 0. Thus to disassemble the byte 69 (binary 0110 1001) just split it into three parts thus: 01/010/001. In this particular case F is one, G is five, and H is one. Next, split G into two parts; J and K; with J consisting of bits 2 and 1, and K just bit 0. If G then were binary 101 as above then split it like this: 10/1. In this case we would define J to be two, and K to be one. Set aside an area of memory called DIS. This is to contain a STRING of unknown length. How you store this string is up to you. There are two different methods you could use - either terminate the data with an end-of-data character (any character will do, FF is as good as any), or begin the area DIS with one byte representing the number of characters of data there are in the string (you only need one byte since DIS will never be more than 255 characters in length). DIS should initially be an empty string, (i.e. containing no characters at all). The algorithm begins here.....
Download available for 16K ZX81 -> sif-disasm.p.[There's also a complete listing available which you can easily compare to the algorithm above.]It is possible to write a machine language program which disassembles things by using this algorithm. In fact it is possible to write such a program in just 1K. Surprising as this may sound I should add that although it is possible, the program itself is rather complicated, and involves a completely new programming technique. What I will do is to not actually write the program for you, but to give you hints and suggestions as to how it may be done. The program revolves around eight different subroutines, which are linked together by one MASTER subroutine which calls them all up in any required order. This is achieved as follows. Somewhere in the program there should be a table called SUBTAB which contains eight different addresses - these are the addresses of the eight subroutines which control the program. The register-pair HL' (note the dash) will be pointing to a sequence of data which tells the MASTER subroutine which order it must call the others in. The data in this sequence is terminated by an item in which bit 7 is one. The data consists simply of numbers zero to seven. Zero calls subroutine zero, one calls subroutine one, and so on. Thus this number zero to seven determines exactly which subroutine the MASTER routine is to call. So any item of data in this sequence looks, in binary, like this: 0--- -nnn for most items, or 1--- -nnn for the last item (the part written nnn means the appropriate number zero to seven as described). Now some of these eight subroutines will need to be supplied with DATA, which by coincidence will also need to be a number between zero and seven - if this number in binary is ddd then it makes sense to save space by storing this number amongst some of the unused bits of the subroutine-call, thus making it look, in binary, like this: 0-dd dnnn or 1-dd dnnn. We have now made use of every bit except bit 6. This isn't needed, so for [the] sake of argument let's always make it zero. Any item of data in the sequence can then be 00dd dnnn, but the last byte must be 10dd dnnn. I hope that didn't confuse you. To make things clear, suppose HL' points to an address at which is stored the sequence of data 00 01 22 83. This means that first of all subroutine zero is to be called, then subroutine one, then subroutine two (which will use the data binary 100 somewhere), then finally subroutine three. I say "finally" because bit 7 is set which means we are finished. The master subroutine which will achieve this is as follows:
You can learn a lot from studying this MASTER-SUBROUTINE. Can you see how the appropriate subroutine (one of eight) is called? First of all the label RETURN is pushed onto the stack. This means that if each of the eight routines ends with a RET instruction then control will jump to the label RETURN - just as if the subroutine had been accessed normally. To call the subroutine itself, the address of which was in the register-pair BC, we used PUSH BC followed by RET. Think carefully about how this works. The required address is pushed onto the stack, above the address RETURN. Then a RET instruction is executed. RET has the effect of popping the first number from the stack (the subroutine address) and jumping to that address. The first address left on the stack is now the address RETURN, which enables control to return correctly. All of this is necessary because there is no such instruction as CALL (BC) - in BASIC the statement GOSUB VARIABLE is allowed, but not in machine code. Another way we could have achieved the same as PUSH BC/RET is by using the sequence LD H,B/LD L,C/JP (HL). Can you see why this does the same thing? You may be wondering how the appropriate address came to be in HL' in the first place. There are two means by which this will be determined. Note that all of the alternative registers have specific jobs. These are:
The byte to be disassembled is located and stored in the D register by the means EXX/LD A,(BC)/INC BC/EXX/LD D,A. From this the quantities I called F, G, and H may later be discovered. Somewhere in the program there should be a table called TABLE containing twelve different addresses. HL' is simply read from this table. The twelve addresses correspond to the cases CLASS equals zero and F equals 0, 1, 2, or 3; CLASS equals one and F equals 0, 1, 2, or 3; and CLASS equals two and F equals 0, 1, 2, or 3. The other way in which HL' may be determined is if subroutine zero is called. Subroutine zero is called by the data-byte 00. This will be immediately followed by eight different addresses corresponding to the cases H equals zero, up to H equals seven. Subroutine zero has the task of locating the appropriate address from the list and storing it in the register-pair HL'. One subroutine you will need (but not one of the eight central ones), is a subroutine to add a single character to the end of the string DIS. Using the convention that the string begins at address DIS and is terminated by the byte FF, the string may be emptied by the sequence LD HL,DIS/LD (HL),FF. To add a character (held in the A register) the subroutine is:
The eight subroutines you will need for this disassembly program are as follows: SUBROUTINE 0 - SPLIT This is the subroutine called by the byte 00. It is always the first subroutine called, if it is used at all. The byte 00 should be followed [by] eight new addresses within the disassembler program. Located at these addresses are eight different sequences of data, which correspond to the cases H equals zero, H equals one, and so on up to H equals seven. One of these sequences is selected (according to H) and the data used to decide which of the eight subroutines should then be used. SUBROUTINE 1 - LITERAL The byte 01 (or 81 if it is the last subroutine-call in sequence) is followed by a series of characters, such as N O and P, which represent part or all of the disassembled instruction. The last character should have one of the unused bits (6 or 7) set, to indicate the fact that it is the last character. The subroutine should use one bit of data, with the meaning that if it is called by the byte 09 (or 89) then the literal data following should have a space inserted after the last character. This literal data is to be added to the end of the data storage area called DIS. SUBROUTINE 2 - LIST-G Means select the Gth item from the following list. The subroutine needs data to specify how many items there are in the following list. If there are four items the data 011 (3) is required, if there are eight items, the data 111 (7) is required, and so on, the data always being one less than the number of items in the list. For example the byte 3A (in binary 0/0/111/010 - meaning call subroutine 2 and provide it with the data 111) means select the Gth item from the following list of eight. The list could, for instance, be R, L, C, inverse A, R, R, C, inverse A, R, L, inverse A, R, R, inverse A, D, A, inverse A, C, P, inverse L, S, C, inverse F, C, C, inverse F. I've used 'inverse' to indicate the last character in an individual item. You don't have to do this - you can use any means you choose as long as it works. Thus if G (that is bits 5, 4, and 3 of the instruction being disassembled) were 5, the literal DAA would be added to the end of DIS. The next byte to be interpreted as data will be the byte after the inverse F. SUBROUTINE 3 - LIST-H Means select the Hth item in the following list. Its explanation is exactly the same as that of subroutine 2. SUBROUTINE 4 - SELECT-G Again, three bits of data are required. Interpret as follows. If the data is 000 select r(G), if the data is 001 select s(G), if the data is 010 select q(G), if the data is 011 select n(G), if the data is 100 select c(G), and if the data is 110 select x(G). The item selected is to be added to the end of DIS. SUBROUTINE 5 - SELECT-H As subroutine 4, except that H is used instead of G. SUBROUTINE 6 - SKIP Resets bit 5 of E (the data-byte), and if the previous value of bit 5 was one, skips over n bytes of data. The number n is determined by the immediately following byte. If bit 5 was zero this immediately following byte (which is only there to specify n) is ignored, and the next byte after is then interpreted as the next item of data. SUBROUTINE 7 - K-SKIP Replace bit 3 of E by bit 4, replace bit 4 by bit 5, and reset bit 5. Effectively this is the same as LET G equal J. Then if the previous value of bit 3 was one, n bytes are skipped over, as in subroutine six. This subroutine can be interpreted as IF K equals zero THEN.... otherwise IF K equals one then....
With these eight subroutines, which you will have to write yourself, you can disassemble every instruction. I will give you an example. Suppose CLASS is zero, and F is three. The first byte it has to interpret should be 00. This alters the value of HL' according to the quantity H, that is, bits 2, 1, and 0 of the byte being disassembled. Suppose now that H is one. HL' should now be pointing to the following sequence of data, listed here along with its meaning.
To represent strings of data here you can see I've used just the character codes, with the final character inversed to show that it is the last character. In other words EXX is written as 2A 3D BD rather than just 2A 3D 3D. It is of course very important to know where one string ends and the next begins. If you follow through which subroutines have been called by the data and what they are supposed to do you'll see that in a total of only twenty-seven bytes we have said IF K equals zero then LET DIS equal POP q(J), IF K equals one then LET DIS equal the Jth item from this list: RET/EXX/JP (Y)/LD SP,Y. If this procedure is continued for every instruction, following the algorithm I gave earlier in the chapter, you'll find that the data required for disassembly is now significantly LESS than 1K. The entire disassembly program consists of initialising the variables CLASS and INDEX, assigning BC' (usually input by the human operator), finding the address HL' from tables, and then going into the master-routine. On exiting this it must then replace all V's, X's and Y's as defined earlier in this chapter, and then PRINT the result computed and go on to the next byte to be disassembled and treat it in the same way. The rest of the program consists of the eight subroutines, the table of addresses, and the data required for disassembly. The whole of this will occupy rather less than 1K. However simple, or difficult, I may have made this program sound, you will undoubtedly find writing it a challenge. The vast majority of the program is data, and each address in every table must point to exactly the right byte. If you get any of it wrong it will be very difficult to trace. You can improve the program too. I haven't used bit 6 of the data - you may be able to think of a use for it, for example it could indicate that a comma needs to be inserted, the choice is yours. Like draughts, this program is so vast that even though the machine code listing itself will fit into 1K, you will need more than 1K in order for the machine code to be put there. Any editing program, BASIC or machine code, will take you above the 1K. Good luck. |