editor here. So this episode turns out the microphone didn't work. I'm assuming you don't want to watch two hours of me typing complete silence, I'm just gonna skip ahead to the next episode. You didn't really lose much anyway. What I was doing was writing the bulk of the parser and dealing with the code that actually stores information about the instructions for the read from the source file in memory and I was doing it all wrong. So no great loss. Well, let the previous session be a lesson to you about coding too late at night. So what I was doing wrong all through there is that I conflated two different things, both of which are using the heap of records. The first is the heap as being, well it's really a list, the list of records as being a representation of the incoming source code and the other thing is using it as a memory store for arbitrary data objects. So the symbol definitions actually need to appear as arbitrary data objects but a label definition like this has to appear as a item in the source code. So what we actually need is a new record which we will put here which is a label definition and that's going to say that this label is defined at the current program counter. Now there will be a reference to the symbol and we need to add a record here so this will be, so now we can define the symbol object anywhere and then the label definition will appear at the point where the label should be set and with the additional clear thinking this actually simplifies these things over here. So we have three types of leaf symbol which is an address in zero page, an address in the BSS and an address in the text segment plus a computed symbol which will also contain constants. Do we need uninitialized versus unknown? I think so. So over here in Paar's expression this is correct whenever we find a computed symbol we are going to resolve the underlying variable so the things being left in token variable and token value which is what the parser will actually use will be the base variable and the accumulated offset. So that's correct. The next bit is symbol definition so if we add or find the symbol we read the token. If the token is a colon it is a label reference so that we know that this symbol that we're referencing must be a forward reference or a something weird just happened to my computer. Okay let's try that again. I think I've removed the offending program but yeah my computer's having a bit of a hard time at the moment. Not quite sure why. Okay where were we? So we have just seen a label definition because we have a colon. If the symbol is uninitialized which means that we have just created it here we want to proceed. If it's unknown means it's a forward reference we proceed. Let's actually change this to reference. Okay so we know that in both these cases we're going to end up with a text symbol. However we also we also want to add a label definition record which points at our symbol. Okay so now an equals sign means that we are creating a computed value so if the symbol is anything other than uninitialized fail pass the expression and we set the symbol up. Okay that built. Now what did we get? So we should have a forward reference for label which is what we have here. Then we have the expression record indicating that we have an LDA that is pointing at that symbol with that opcode AD and the address is 1965 which should point at the label record and the offset is one which is correct and that's the end. Then we have a byte record containing the RTS. Then we have a label definition record 830065. So that has actually created a label a label definition pointing at 650 which doesn't make sense. So this seems to be not correct. So I fired up the actual debugger because my emulator here has one. It's a very simple machine code level debugger but after printing the address of the table and looking at the memory what we're seeing here makes very little sense. No it makes perfect sense. This is not a symbol record this is a label definition record. So that now comes like so. If we dump the memory again 836A2F. 2F6A is the address of the top of the heap so that's done. Okay now that took an annoyingly long time to figure out which is what happened offline. Never mind. Okay so we now have there is our label definition record. There is end of file and now notice that we are not actually paying attention to the program counter anywhere here. That will come later in a second pass through. Okay what have we got so far then? We should now have proper definitions. We should be able to do this and have it work. So we create the value a here pointing at symbol of type 5 meaning computed. There is a reference to our symbol. There is our offset. There is our name. Then here is our forward reference which is now a text type 4. Link pointer. Here we have our expression the LDA. Here is our LDA. AD is the opcode. 1968 is the address which is also the address in A. That's the backing symbol followed by the offset. That's not right. It has failed to propagate the offset into the expression node. Great. I thought that was working. A lot of this code here is garbage. So what we're doing here is we fetch the underlying symbol which has got the offset in it. We dereference it. If it's computed we dereference it. So we now have the base variable in token variable and the offset in offset. If there is a plus or minus following we wish to update the offset and save. And here is our one. Okay I think I'm going to call that done. So there is a ton of stuff that needs actual work but we should have the basics of our assembler parser. It only supports ALU instructions and single opcode instructions but there is enough here to start to move on to the second pass and we're at ouch 4k. Suddenly got bigger. Yeah this code is a bit contorted. It may be possible to simplify this. Anyway as this is a prototype I now want to move on to the next bit which is determining code placement. So this is what we developed the records for. What we're going to do is walk the data structure that we've put together that is this stuff. Why have I called that tokens? Is walk the data structure trying to assign sizes to things and this will allow us to actually put concrete values to these symbols. So we are going to simply go for that. So what this is going to be is so we start at the top and we iterate down through the list. This is why you were sure that all our records had sizes so that we can walk them efficiently. So the type is in the top byte and the length is in the top nibble more or less. Top three bits and the bottom is in the bottom five bits. This will walk the list and do nothing which is good. We are going to keep track of the program counter. So if this is a byte record we increment the program counter. Very simple and here let's just once we reach the end let's just print the program counter. That should be len minus one because we don't want to include the overhead. In fact we can do this properly. It's a byte record and we want the offset of bytes. Okay that's showing that we've used zero bytes because... interesting! We do have a bytes record in here. That RTS. So we should have had one. That should be type not len. Right so we have one byte. Now the only the only other thing we currently have is an ALU operation. This can be zero. This can be two or three bytes long. Oh hell! I've been dramatically overthinking this. So all this complicated stuff here. We know upfront whether I was going to say that we know upfront whether our instruction is pointing at zero page or not from the type of the symbol. But of course we don't because it might be a forward reference. And down here I have... okay this resolves the forward reference to a label to a text symbol. So once we've seen the label definition we now know that the symbol is forward reference. We know the symbol is pointing to the text segment and therefore must be using two byte addressing modes. But during the parse phase we might be looking at a forward reference here therefore we don't know this. So we're always going to have to use the longest encoding. Now once we've finished the parse phase all symbols should be resolved. So if there are any forward references left otherwise we just do nothing. So we should be able to test that by just doing LDAZ. We don't have a Z. So here under record ALU we want to be using either the two byte or the two byte address or the one byte address. So this is straightforward. If there is a variable set and it's pointing at zero page then we want to change the b-value encoding which I shall find down here. These to use the zero page form but only if the encoding... Look at the wrong column. This column. Only if it's something that can be legally turned into the zero page form otherwise we leave it at the the absolute address form. So that's if it's seven make it five. If it's three make it one. This is unsetting the two bit from the B code. I'm just looking to see are there any other uses of that bit. So no bit set. Bit one set. Bit two set. Bit three set. So this is zero one one. This is zero zero one. This is one one one. This is one zero one. Six here is one one zero. And we do not want to clear the two bit because that will take us to this which is the wrong thing. Okay so if so we're going to extract the the B field which is these bits here. So that will be one one one oh oh. And I cannot quite remember. Yes we can use a B for binary. So if B is this one this or this then clear the bit. And in fact we are going to want to record that anyway because we need to determine how long instruction is going to be from the the B value. So this is three bytes is two bytes. This is two bytes three bytes two bytes three bytes three bytes. Okay so it now thinks the program counter has advanced four places which is correct. This is three bytes this is one byte. And the label will finally be set to this address. In fact we should be able to have done that one yet. Let's put that in here. So this is just going to be this. So now we look at our saved dump. We are expecting to see that label here has been given a value. So label is the symbol which is here. 60 is the record header. 04 is the label type which should be text. 0 1 2 3 4 which it is. Then we have the variable it's based on which is 0 for this type. And then the value which is 4 which is the right value. Okay and there is one other thing we need to do which is if we ever have to change anything then we need to record that fact because we're actually going to want to run this until the sizes of things converge. So if at any point a instruction changes size we need to go around again because all our program counter references may change. It's only after we've been through this once when nothing has changed that we know that we are finished. Okay so the next step is to actually write it out. Let's just do and this should actually be also be very straightforward. We're going to do the same thing where we just iterate through all this lot. So we're just going to copy this except instead of doing any computations we just use the values that we have. So if it's a symbol do nothing. If it's bytes then we just write them. We want to do write byte. Amidst byte writes them to the to a new bytes record which is not what we want. So this is going to be byte record. Okay ALU down here also pretty similar. We are going to write the opcode. The offset just can fetch the offset if there is a variable then computes the actual address of the the address of the thing and then here we write it out whereas this is a zero page thing so we just write the write the single byte. Label definition generates no code okay should not be wrote place code this should be write code and there is no return changed. So now if we run it we should end up with the actual assembled result which I can see as a glance is wrong. So what we've got what we've done is here we have our LDA which is that has got the right value in it which is five. Label has address four so a is five that's correct and then we have an RTS which is here that's correct and then we have a 6C which looks like a record header byte which suggests that we have actually written one too many byte here that looks okay. Okay so that drops us into our debugger and just printed the address so if we dump this we get the actual record which just contains a six zero so it returns the correct six zero so the 6C must be coming from somewhere else that's a bug in my debugger it is not continuing on from a break statement properly so that's because I forgot to save it yeah there's definitely a 6C coming from somewhere in there oh I know where it's come from right it's in fact completely harmless what this is where this has come from is we're actually using our output buffer as our parse buffer so it is going to contain garbage from the previous word that we read which is being overwritten as we write bytes so that's where that 6C is coming from so that's that's correct it'll just get overwritten when we do more things okay however we have not done everything yet because we also need to write relocations now these will appear immediately after the the main code that we're going to have right text relocations so this is again it's going to be another copy of place code here the difference here between this and write code hang on we put this in the wrong place is that we actually want to keep track of the program counter again yeah we need to put this after write code so do you want to advance the program counter here and here not here okay now record ALU is a reference to a value that needs relocating so let's just do the if there is a variable then we are going to need to relocate when we run it we see that we need to write one relocation of type 4 which is text at PC0 in fact it's not PC0 it is it needs to relocate the high byte for a text relocation so the high byte is going to be at PC plus 2 zero page relocations affect the low byte of the address which is a PC plus 1 now for zero page relocations it's the same code although that we know that this can only be a zero page symbol and again it's at PC plus 1 and up here as well we are going to need to do data data relocate we haven't done anything about the data and bss segments I'll leave those for the time being so that this is seen that we need a text relocation at address 2 which is this byte and what it'll do when the binary is loaded is that it will read in it will add on to all the bytes marked in the relocation table a value based on where the program is loaded in memory thus fixing up all the addresses to the correct thing and in fact this is only writing text relocation so it's never writing zero page relocations so when we get one of those we just want to do nothing and this can go away completely now it can't because we need to keep track of the program counter but it turns into that so how bad has this affected our ouch but that's actually because we've got printf in it there we go that's better printf is the printf library is enormous using printf causes it to be pulled in 5k so on our BBC master this is actually using up a substantial amount of our memory that's still a reasonable amount left did I copy the correct source file in here no I did not so now we should be able to actually run it properly the asterisk means that CPM has crashed and it's fallen back to the acorn mobs prompt so I don't know why it's doing that so thinking about memory our assembler is now 5k once we've put in all the rest of the assembler it's going to be going to be bigger so let's say 10k maybe 15 that's still going to leave well another 5k will take this down to 12 another 5k after that will take it down to 7k of free memory which should be enough for a small program on a bigger system such as the the BBC master tube system where you have like 60 odd k of memory free that will be enough for a large program so I think that this is actually plausible this approach we're taking there are some optimizations we can do this stuff is terrible so let's just do some playing with those and see how much we can make things smaller okay let's try a bit of optimization to see if we can make a difference here now one of the things I really don't like is I'm using actual explicit constants for the b values so let's fix that and it creates an enum with our doing over that with our b values in it so let's find that table so we have x ind is not x ind is not not well formatted z page is one immediate is two abs is three y ind is four x index is let's go with x pointer and y pointer just so they're clearly different from index y index is six and x index is seven in fact all of these now let's do that so down here at the top of parser along with all the instruction tables we're going to have we're going to have a table of you know I'm going to put these in here so that we're going to use the shifted versions through out because I think that will make life easier so here this is going to give the instruction length and we're just going to use a simple lookup table so x pointer is two zero page is two immediate is two absolute is three y pointer is two x index zero page is two y index and x index are three so this should be eight long which we can enforce like this so in order to get the instruction length all we need to do is okay so how big is our program 4911 so we can get rid of a lot of this stuff by just doing so what does this do to our code length okay yeah okay so pulling calling get instant length is actually going to pull in some extra code so we have saved here exactly the same amount that we spent on it earlier so let's not that one how about this one you can replace this entire switch statement with that there we go we say well hold 20 bytes and that actually becomes smaller and more rather more readable so what else can we do well each of the property each of the B modes actually has various properties so we can say does it reference zero page is it a pointer so what we're doing here we want to know here the link we want to know the length of the op codes build it does not build so we can actually say think clang is in lining get instant length which I like it not to that should not be bigger and in fact we can do a little bit better than this so this will get the length of any ALU format instructions that's any of these for anything else it won't work more or less so I mean for these instructions this column will work this column will not work because these are all one byte length this column will work this column will work likewise here but these won't for this block of instructions these are all rather mixed we've got some zero page ones here these are one byte they're quite different these are one byte that's three byte and we've got like outliers like JSR which is a three byte jump indirect etc but for the normal ALU instructions this will now pull the length out of the op code so doesn't make any sense there but here for example we can just say op code slightly smaller if we do s op code here what does that do to themes program length smaller I was not expecting that it's managed to cache it in a variable okay so what is it we actually want to know about our instructions so we want b equals 3 and b equals 7 3 is these are the two absolute modes in fact we also need six I've completely missed that one mess that one up but not here yet because there is no zero page index with y operation this is a indirect operation so we do actually want just these two but we can certainly change these to x index and absolute so what I was thinking about with properties is that we may be able to create a simple table of addressing mode properties so looking went up would just be a dereference and an and with one of these which would probably save space so so this is going to be the prop pointer just be prop pointer zero page or the prop pointer this one is the prop game the wrong button so both of these are B prop abs with B prop shrinkable and my other properties zero page absolute pointer shrinkable immediate so what we're doing here is that if it is zero page or immediate then the instruction link is two otherwise instruction links is three okay what does that do to our length quite a bit smaller why I don't know but I'm willing to guess that this is now sufficiently complicated that LLVM has decided not to inline it okay so down here in our placement we don't need that anymore and in fact it occurs to me it's abs and x index I actually put the flags in the wrong place abs is shrinkable y index is not size a little smaller as it's an improvement so we don't need anything in right code but we do need it this here right text relocations so if this is a absolute value if there's an absolute addressing mode there is a variable and the variable is pointing at the at one of our text segments then we need a relocation exactly the same length great so has that actually helped well it's helped a little we've already gone down from our original 4911 to 4883 we may be able to use the flag stuff to help elsewhere you should find out whether this works yes that looks good so I think that's mostly been a success and this is we need to want to change these to use the constants one is x pointer this one is not equal to y that is y pointer that is x pointer this is x index this is y index no it's not this is x index zp and this is x index this one is y index this is zero zero page this is absolute still looks good for our minimal testing so we were 4883 we are 4889 yeah this is way too premature optimization it's making the code cleaner which is a good thing and it's making all this stuff shorter which is nice okay let's try LDA and see what happens so here is our first LDA and then here we are correctly getting the low byte which is nice good that seems to have worked okay I think that we have not actually emitting any of the relocation stuff yet let's just do that so the way the relocations work is that it's a list of nibbles each of which indicates the distance from the last relocation so we need to know what that is we need a buffer to store the actual relocation information in and we need a flag to tell us whether we actually need to flush the buffer or not so to write this relocation we are going to have to calculate the delta between where we are now and the last relocation and then write multiple relocation nibbles right I'm going to have to take this all out of line this relocation zero relocation buffer is minus one minus one being special value to mean that there is nothing in it so you went 16 okay this yeah this is actually going to write a raw nibble so if relocation buffer is minus one then save the relocation in the top four bits otherwise right to the last relocation the current relocation together and the relocation buffer is now empty so we don't want last relocation anymore for some reason if I occasionally when I bump my mouse it will delete a line from the editor and I'm not quite sure why and turn caps lock on they calculate the delta which is PC minus last relocation while the delta is greater than or equal to E E is a magic value which means don't actually do a relocation just advance the pointer by e bite and on the exit we want to write a F relocation meaning the end of the stream and if there is a pending bite let's actually just do a flush relocation so that just becomes a flush relocation to flush the stream that should be location buffer okay what do we get in our output file we should have a relocation at address three we do not we do however to relocation to the dress 0 I know what I did to update this and in fact we want the address to be PC plus 2 because that is the high bite of the opcode so we have a relocation of 0 followed by a 2 so 2 is correct it puts a relocation here which is what we want and then there's an F so where is that initial 0 coming from have I I have forgotten to call reset relocation writer I'm gonna bump my mouse and did something weird again and turn caps lock on right 2 F is correct that is the correct relocation table for this code here notice that this 7 from this does not get a relocation entry because that's always getting the low bite which doesn't need this form of relocation so good and we are a five and a half K is growing annoyingly but I think we are going to be able to make it work we also have way too many copies of this routine I'm not really sure it's worth trying to comment things out to be honest I would involve a function pointer and I don't think it's worth it and multiple switches because we're also going to have to copy write text relocations to write 0 page relocations but let's do that now because 0 page relocations are actually fairly simple so if it's a ZP we go through this code so we can common this actually as I put these the wrong way around let's just stack this down here so this again is going to be location for this that's gonna be PC plus one and that's going to be ZP or him no no it's not in fact I don't think that's relevant at all I think the only thing that matters is the variable type so I think you can get rid of that completely because this will then relocate any two-byte addresses it's assuming that all text symbols will be encoded using two-byte forms but we can so the same applies down here if it's a zero-page symbol regardless of whether it's a abs form where it's going to be encoded as a two-byte constant so three-byte instruction or as a two-byte instruction with one byte of address that is still going to work and that makes our code a little bit smaller but we have but we have no way to generate zero-page constants yet so that's not actually going to do anything it does generate a interesting two three f zero right so that's try to relocate this which we can't do so actually I think that we are going to need to I think we are going to need to gate that so if it's a absolute which will be not that if we abs or the three indexes double-check that there's our table abs and the two indexes sorry then it's going to attempt to relocate it not otherwise okay two f f zero for the relocation table remember these are read as nibbles so that is now looking more correct let me just put another one of these in two five f zero so zero one two relocate that address zero one two three four five relocate that address excellent okay I think that we have relocations working what are we going to do next well the biggie the thing that really that is going to take work is branch instructions because the 6502 only has these conditional branches and they only take relative offsets which can be one byte so they can jump between minus 128 and plus 127 bytes from the program counter when this is executed I want to allow branches to expand so that if you try to jump too far then it will turn this into the reason for this is compilers so this is five bytes this is two bytes so we're going to need our branch instructions to shrink based on where they are jumping to and that's going to be the big job of the code placement so let's do that next time