There are a lot of other addressing modes supported by the Pentium but now you have the basic idea you can look them up for yourself.
Most of them aren’t used that often – except for one very special addressing mode – stack addressing.
As well as the need to address data, a program also has to address instructions. In normal operation the program counter or PC register just steps its way through your program one instruction at a time. However occasionally you need to perform a test and a jump to another location in the program depending on the outcome of the test i.e. you need If statements. When this happens the value in the PC register changes in a different way and isn't updated by simply having one added to it.
For example, if you want to do different things according to whether or not a value is positive or negative you would first test the value. In Pentium assembler you would use the CMP (i.e. CoMPare) instruction:
which compares the contents of the EAX register with the immediate value 0. After this you could use a conditional jump instruction, such as JGE (Jump if Greater or Equal), to make the next instruction depend on the result of the compare. For example:
will make the instruction starting at the address given by “positive” to be the next to be carried out if EAX was positive - we compared it to 0 and the jump occurs if the result was Greater than or Equal.
You can guess how this is achieved – if the jump is taken then the address specified by “positive” is loaded into the program counter. That is when the assembler converts this to machine code it replaces positive with the address of the location to take the next instruction from if the test works out to be true.
Now this is all very good but this isn’t the only “jump” instruction that programmers need.
Soon after computers were invented programmers invented the subroutine. This is a block of code that you can jump to and when it is finished it will return to the instruction following the jump. This allows programmers to write code that performs standard tasks, e.g. adding two numbers together, and use it from anywhere – but how does it get back?
How does it remember where it was called from?
The simple subroutine involves a call and a return
If you assume that it is only called once then it could just store the return address in a fixed memory location but there is no reason why a subroutine shouldn't call another subroutine and so one.
Each subroutine call needs to store its own return address and when it has finished it needs to return to the correct location. Sounds like a nightmare of bookkeeping but it turns out to have a very simple solution – the stack.
The stack – working its way down from the top
If you add another register to the processor, the “stack pointer”, or ESP in the case of the Pentium, then you can implement subroutines very easily.
The stack pointer is a pure address register, it is never used for data and it is associated with a very simple set of instructions. In general all you can do to the stack register is load it with an address and use it to store and retrieve data values.
The memory area that the stack pointer points at is, not unreasonably, called the stack.
To store a value on the stack use the command:
This decrements the ESP register by 4 (i.e. four byte locations) and then stores the value stored at loc in the stack location pointed at.
To retrieve a value from the stack you would use:
which loads the value pointed at by the stack pointer into loc and then increments the stack pointer by 4.
You can see that the stack works like an automatic memory device that retrieves items in the reverse order to that in which they were stored. If you think about it you should be able to see that is just what we want for the subroutine call and return. When a subroutine is called the program counter is automatically pushed onto the stack and when a return to the location is required a POP gets the return address and stores it in the PC.
Most processors have a CALL sub command which is the equivalent of:
PUSH PC JMP sub
and a RET instruction which is just:
This isn’t quite the full story but it is close enough for you to see how it works.
The stack is so useful a concept that it has been used as the basis for complete processors using nothing but stack access to the memory. That is, stack addressing is really all you need to make the computer principle work.
The power of the stack has worked its way not only into the design of processors but computer languages as well. There are languages that do nothing but POP and PUSH a stack structure – Forth being the best known. Even mainstream languages such as Algol, Pascal and C/C++ make heavy use of the stack. When a subroutine or procedure is started its return address and all of the parameters passed to it are pushed onto the stack. When it creates new variables they are pushed onto the stack and when the subroutine finishes it pops the stack clean, except for any return value it might leave.
You should be able to see that this description means that the stack is used to pass parameters to and from a subroutine, to create local variables and to implement recursion.
Don’t get carried away however. Remember that the stack is … just so much memory with a special addressing mode.
The merge sort is an under-appreciated algorithm - yet it is neat, clever and it still has its uses. With the rise of big data, parallel methods and online processing, you can even argue that it is gr [ ... ]