Comparing C to machine language
So I have a program here that prints out Fibonacci numbers, and I want to walk through how we get this program compiled to machine code and running on the computer. But first of all, just to see what the output of this looks like when we run it is it prints out Fibonacci numbers up to 255. And actually, 233 is the largest Fibonacci number that’s less than 255. And then it just starts over. And it just does this forever and ever. And so just as a reminder, Fibonacci numbers start with 0 and 1, and then the next number is just the sum of the last two numbers. So 0+1 is 1, 1+1 is 2, 1+2 is 3, 2+3 is 5, 3+5 is 8. So on and so forth all the way down. And so just to walk through this program to make sure we understand how it works: we’ve got three variables, x, y and z, and we have this loop that just continues forever and ever. But then inside that we set x to 0 and y to 1. So x starts out as 0, y starts out as 1, And then we have this loop here where we print out the value of x. So x is 0, so we print that out. And then we calculate z as being x+y. So 0+1 is 1. And then what we do is basically kind of shift all these numbers over. So x gets equal to y, so x becomes 1. y is equal to z, so then y becomes 1 as well, even though it was already 1 And then we go through and loop it through again. x is less than 255 (it’s only 1), so we loop through again. We print out x, x is 1, and then we compute z again. z is x+y, so 1+1 is 2, And then we kind of shift things over: so x is equal to y, so x is equal to 1, and then y is equal to z. z is 2, so now y becomes 2. And then we loop through again, because x is less than 255. And here we print out 1. We compute z, which is now 1+2 is 3, And then we’ve got to shift things over again, so the two shifts over here, the 3 shifts over here, so x equals y, y equals z,… and then we loop through again. And here we print out the 2, we compute z as x plus y, so 2+3 is 5,… And so on and so forth. And you can see as we do this, we’re printing out 0,1,1,2 and so forth. So 0,1,1,2… and it keeps going like that. So that’s how this program works print out Fibonacci numbers. But what happens when we compile this? So, if we compile it, by running… this is the GNU C Compiler, and I’m saying the output file is just going to be a file called fib. That’ll be the executable that will run, and then the input is fib.c. (Which is this this code here, which is looked on) So if we compile it then we can run it, but what I did here is actually disassemble it. So what this command does, This is just on my macbook. I don’t know if this will work on other computers. Whatever, but it worked on my macbook… and it prints out the machine language instructions that were compiled. And so we’re looking at the compiled version of this program that we would run. And so I want to walk through these instructions, just to see if we can kind of, like, figure out which of these instructions kind of correlate to what’s going on in the original C program here. And so if we start here, the first couple of things here just kind of setting things up. Everything up here isn’t really part of what I wrote here. It’s just kind of setting up the stack frame. (I think this is a return value or something like that) So in which we aren’t really doing anything with. Let’s just kind of ignore those for now. But here’s where we actually get into the code that we wrote over here: so this first line here, this “Move long”, is moving this value 0 into this thing, which is actually an address offset. So %rbp is the the stack base pointer, and this -8 is actually just offset. So this is referring to a location in memory, and so we’re putting a 0 into this specific location in memory. Which is exactly what we’re doing here, we’re saying x=0. and so what we can see is that x is actually this location in memory, this -0x8 offset from the stack base pointer. So over here, I’ll just write down that 0x8 is the variable x so when we see it elsewhere in the program, we’ll know that’s x. So this line here is basically saying: x=0. So we’re setting 0 into 0x8 which is the memory location where x is. The next line is basically the same thing, except now we’re putting 1 into this 0xc location. So here we’re actually saying y=1. and 0xC refers to the variable y in the program over here. The next couple lines (so now we enter this this loop here), So the next couple lines have to do with the the “printf”, and so I’ll just call out these four lines here, that have to do with the printf, and we’re printing the value of x. And basically what these four lines are doing is, it’s setting up all the things, and then calling this, you know, “printf”. I guess this is a memory address that’s somewhere else in the program, it’s not not listed here. But this is presumably the “printf” function that’s provided by the C standard library, and in order to call it, we have to set some things up. I think this is probably the address of the “%dn” string, and then, of course, 0x8. We recognize that, that’s x. So we’re printing x. And then …I’m not sure what this other thing is, and then the “call” actually makes the call to printf. So this sort of corresponds to that “printf”. So then after the printf we have this z=x+y, and that is actually, these three lines here are the z=x+y. And the way this works is, what we’re doing is we’re moving 0x8 (which is x), Into this %esi register, so we’re saying x goes into %esi. And then we’re saying “add the value of c.” So we’re saying “add y to the value of %esi.” (And you probably can’t read my handwriting here, get a little messy…) But basically what we’re saying is, you know, x goes into the %esi register, and then we add the value of y (because 0xc is is the memory location of y) to the %esi register. And then take the value of %esi register, and put it into this 0x10. And 0x10 is a new memory location we haven’t seen yet. So 0x10, that’s actually the memory location of z. And so then we just put this into z. So these three lines are basically doing the z=x+y, so we’re getting x and putting it into %esi, we’re adding y to it, and then we’re putting the the sum back into z. So then, moving on the next two lines here are doing the x=y. And again, we’re using this %esi register as kind of a temporary location. And so we’re taking 0xc (which is y), load it again into %esi, and then we’re taking what’s in %esi and putting it into 0x8. So we’re taking c, and we’re taking y, putting into %esi And then we’re taking %esi and putting it into x, so from y to x, or in other words: x=y. We’re setting x equal to y. So this is the x=y. And then the next two lines are basically the same thing, except now, we’re going from 0x10 into 0xc, so we’re going from z into y. Or the way, we write it here is y=z, So y equals z. This next line, I’m actually not sure what this line does. And so if… yeah, because this is the %eax register being moved into this other memory location that we are not using for anything else, And we don’t have any other variables defined here… I’m honestly not sure what this line is doing. So if you guys know, point it out in the comments. But after this line we do this comparison, so this is the “compare long value”, and so we’re comparing 0xff, which is the hexadecimal representation of 255, we’re comparing that to what’s in the memory location 0x8, which is x. So we’re comparing 255 and x. And we’re saying “jump if less than”.
So “jl” is the jump if less then, (based on this comparison) and the “jump if less than” is taking us to this address f3d. And f3d is up here, the first statement here that was part of our printf. So if x is less than 255, We are going back up to the “printf”, which is what we’re saying here: “while (x is less than 255)” we stay in this loop… if it’s not less than 255 then The program flow just jumps, comes down to the next line here, Which is just a jump. and this is an unconditional jump. We would always jump to f2f. And f2f is back here, where we start with the x=0. And of course you know once this loop is finished we fall down here, and we are back into this main loop that just goes on for ever and ever. So you can see how, when we compile the C program, we end up with this machine code. And so next I want to take the the machine code, and see how we can take machine code similar to this and load it into our home-built breadboard computer.