Branching Logic
Higher level languages introduce the privilege of combining multiple conditions into one larger condition that will either pass or fail. Assembly languages do not have that feature - they can perform the same work, but doing to requires a little bit more thought. In addition, if statements in MIPS tend to be structured differently because of the way branching works.
Consider the following Java program:
If A is true, then we enter the first scope. If A is false but B is true, we enter the second scope. In all other cases, we enter the third scope. Pretty straightforward. Here is that same program (more or less), but in MIPS:
This code snippet applies a sort of inverse thinking. Instead of entering the scope we want when the appropriate condition is true, we skip it if the appropriate condition is false. The beqz instruction means branch equal to zero. In MIPS, the value 0 indicates false - anything else indicates true. So instead of checking if A is true and branching to some location, we check if it is false and skip to the part of the code looking at B.
In each scope we add an instruction jumping past the other scopes. If we didn't, then it's possible we'd run through both scopes even though only one of them is supposed to be run. Line 24 is unnecessary, but it obeys a sort of rigid format which makes the code a bit more readable.
Interestingly enough, this is not the only way to translate the Java program into MIPS. One could just as easily have done something like this instead:
Here we don't invert the logic. Instead we set aside a region at the top of the branching logic that checks for all of the different cases, and then create labels to jump to where the scope bodies are located. The instruction bnez means branch not equal to zero, and is the logical inverse of beqz. This format works well for if statements that only check one condition at a time. But what if we check multiple conditions at once?
There is no way to check for two conditions with a single instruction. If we want to check if both A and B are true, we need to use two branch instructions - one for each condition. The most compact MIPS code would probably look like this:
This, again, inverts the branching logic. Instead of checking that both A and B are true, we check if either one is false. If A is false, there is no sense in checking for B, so just skip straight to the else body. But if A is true, then we also have to check that B is not false. Compare this to the other way of doing it:
There is more overhead in doing it this way. That's not to say that doing it this way is invalid - it is all a matter of preference. Correctness of your program matters much more, and if organizing your branching logic this way helps you, then by all means go ahead and do it.
Main Memory
So far we have been using registers to store all of our variables. However, there is a limited number of registers at the programmer's disposal, and virtually no application would be able to fit everything in 128 bytes (32 registers, 4 bytes each). Everything else must be stored in main memory, which is limited by the size of the computer's RAM. Most computers nowadays have 4 GB or 8 GB of RAM - millions of times more than the total amount of memory in just registers.
In order to do work, variables must be loaded from memory to be used in a computation, and then perhaps stored back in memory when that computation is done. MIPS has several instructions for dealing with this, some which load and some which store.
This program prints the number 100 to the console and then exits. On line 17, it defines the label a_number in the data section which is of type word. A word is just a 4-byte area in memory, and can store any type of information. However, when declaring a .word, the MIPS assembler will expect an integer number as its given value. On line 3, it uses the lw instruction, which stands for load word. This will load a_number into the register $a0 which is then passed to the syscall to print the number. This is essentially creating a copy of the variable using the register as storage space - the value remains unchanged in main memory.
A load word instruction looks for 4 contiguous bytes and loads them all at once, however it is possible to load smaller amounts of data with other load instructions, lb and lh, which stand for load byte and load half-word, respectively.
Here we change a_number to a byte with the .byte directive. We also add a half-word (2-byte) variable b_number with the value 32767 with the .half directive. Printing these out looks exactly the same as before:
The only thing that is changed is the fact that we are now using lb and lh instead of lw. Since registers are 4 bytes large and we're loading smaller amounts of data into them, MIPS will place that data such that the more significant (higher-valued) bits are unimportant. In order words, when using lb, the byte will reside in the least significant 8 bits of the register. When using lh, the half-word will reside in the least significant 16 bits of the register. In effect this is expanding the amount of space used, but the value of each variable remains the same when loaded. The more significant bits are set to zero or one when loaded, depending on whether the value is positive or negative. For more detail about how numbers are stored in memory, look up 2's complement (or look for my post on it later).
This example showed how to load from the data section using labels, but it is also possible to provide an address instead. An address is just a number that refers to the start of a region in memory. As an analogy, you can think of each byte in memory as a mailbox, and an address as the number on that mailbox. When mail is delivered, the postman needs to know where to deliver it - addresses serve that purpose in both real life and in main memory.
Here we allocate blank space in the data section using the .space directive on line 17. This directive takes a number that determines the size of the region - in this case we are asking for 128 bytes. That space may or may not be zero-initialized, depending on what system you are running your code on. Lines 3 through 5 load the address of that space into $a0 and prints the hexadecimal (base-16) value of that address using syscall 34. This is just another way of representing binary data. Hexadecimal is often used when dealing with addresses because it is easier to read for programmers that are familiar with it. If you are unfamiliar with hexadecimal, I will have another post that explains how it works.
There is an important distinction between loading the address of a variable and loading its value. When the MIPS assembler builds your program, it replaces every label in your data section with the address where it will be stored. A load address instruction just copies this address into the specified register and never actually goes to main memory. However, load word, load half-word, and load byte instructions copy the data stored at the specified address into a register, which actually does refer to main memory. This distinction often causes confusion - a lot of bugs can be blamed on using la instead of lw or vice-versa.
Now let's look at providing addresses to load instructions:
This time, we load the address of some_space into $t0 and use that address to load the data stored there. On line 5, we use lw to grab the first four bytes of this region, then later print it in hex. The second argument to lw is the address that we're loading from, plus some offset. This offset is placed to the left of the parentheses, in this case 0. The inclusion of an offset might not be all that useful now, but there are multiple occasions where it is.
If you run this code, it will produce an error that looks like this:
What's the problem? Well, when we specify an address to load word, that address must be a multiple of 4. The reason for this is a bit esoteric (I will cover it in a more theory-driven post), but it is still a requirement of the system. Likewise, when using load half-word, the address must be a multiple of 2. For load byte, there is no such requirement because all addresses are multiples of 1 (all integers are, for that matter).
If we want to adjust for this, we can provide the .align directive in our data section:
This directive ensures that the start address of the label immediately following it is aligned on a certain boundary. We give it the argument 2 which indicates that we want to align on a word boundary. To figure out what number to provide, just take the base 2 log of the multiple (4, in our case). Building and running the program will show that this resolves the error.
For every load instruction (besides load address) there is an equivalent store instruction. Stores take values stored in registers and copy them to main memory. If we want to modify the data stored at some_space, we will have to use these instructions.
This should be pretty self-explanatory - we're just loading values into registers and then copying the data in those registers to some region within some_space. Store word (sw) takes the whole register and saves it to memory. Store half-word (sh) stores the lower 16 bits, and store byte (sb) stores the lower 8 bits. The sign of the value is unimportant - that detail is handled entirely by the load instructions, which fill in the missing bits. You can load these values back to verify that the memory is indeed being written to and contains the correct values.
Strlen
A while ago I mentioned null-terminated strings and how they are stored in memory. Now that we know how to access that memory, let's look a little deeper into strings by writing a program that will calculate the length of a string.
We have a string defined in our data section called example_string. We load the address of that string into $t0. We then look at each byte one at a time by loading it from memory. When we find the null terminator, we exit the loop and print the number of nonzero characters seen. If our string is the following:
Then we will count 13 characters. If we were to include the null terminator in our count, we would instead have 14 - but usually the null terminator is only used to denote the end and is not included in the string length.
No comments:
Post a Comment