I was thinking about stacks recently... i always seem to use them and yet i do not know how they work (i am working to rectify this). I have searched google with the keywords stack + work + computer i managed to get a "wiki" but it does not explain how the hardware deals with the stack. My question is: How is the stack implemented in hardware and/or software? Any information or google keywords would be very welcome, DENC

All this time i thought they were the same thing

Any information or keywords on either kind would be welcome,
DENC

Edit: Smiley didn't work

[Edited by - Nice Coder on September 4, 2004 1:37:00 AM]

the "call stack", if i remember correctly, is a memory address that is stored by a special register in the CPU. this address is used to allocate memory and pass arguments to functions. it's the same in basic functionality as the data structure stack, where the current address(pointer, element) is percieved of as the top and elements can be "pushed" on top of it or "popped" off the top. this idea works well for fast linear memory storage, that's why the "stack" was first designed and supported by CPU's (as opposed to lists).

though i use stacks in assembly and used them in college in theoretical programs, i have yet to find them helpfull in game programming. not to say they have no use, but i was interested in what you were using them for?

Thank you for the replies,
I am mainly interested in the hardware that implements the stack because i do not know about that yet. (i am interested in nearly everything anything i do not know).

The main thing which made me think of the hardware of it is because i could not think of a way to implement the stack.

I am also interested in many other things in "modern" cpu's (like the cache), because it is not known to me how things like that work, and it bugs me to no end [lol].

Any keywords or information would be welcome,
DENC

How is a stack implemented in hardware?

Usually by having a register dedicated to being a pointer. A "stack pointer". Commonly called "SP", like program counters/execution pointers are called "PC"/"EP", respectively.

To 'push' a value; write the value to the address pointed at by the stack pointer, and then increment or decrement the pointer.
(*SP) = V; SP--;

To 'pop' a value; decrement or increment the pointer (the opposite of what you did to 'push'), and then read the value at the address pointed to by the stack pointer.
SP++; V = (*SP);

Most hardware stacks grow downwards; pushing a value decrements the stack pointer, moving from higher to lower memory as more items are added. IIRC, this was the practice in small and/or embedded systems where you'd have a moderate-sized chunk of memory at the low end of the address range, and a small chunk at the high end of the address range; the stack pointer would be initialized to point at the very top of the address space, and the stack would grow downwards. The program and data would be stored in the low end of the address range.

For example, on a 16-bit system, you might have an 8K ram chunk from 0x0000 to 0x2000, and a 1K ram chunk from 0xFC00 to 0xFFFF. SP would get initialized to 0xFFFF (for one-byte stack words), EP would get initialized to 0x0000, and execution would begin.

This explanation is mainly x86 (Intel, AMD cpu) based, but here you go:

The hardware implementation of a stack is that the current place in the stack is stored by an special register (called the esp register, or extended stack pointer register).
Say the operating system allocates an area of memory from 0x0 to 0x1000, and puts the value 0x1000 into the esp register. Why 0x1000? The wierd thing is that on the x86 cpu, the stack grows downwards.
There are two opcodes for messing with the stack. 'PUSH' pushes a value onto the stack. It works like this:

- Minus the esp by the sizeof(value) - generally speaking 4 bytes/32bits
- Place the value at the new esp

'POP' pops a value from the stack to a value:

- Place the value at esp in value
- Plus the esp by the sizeof(value)

It's not a very dynamic data structure, you must have an area of allocated memory that nothing else will touch, otherwise there'll be trouble.

The CPU, when it comes across the call instruction, pushes eip (the extended instruction pointer register, the memory address of the current opcode) onto the stack, and any parameters that go with the function, and at the RET instruction, pops (usually) 4 bytes into the eip register so it can continue executing at the previous place.

This may be a bit advanced for you, so I suggest checking out the appendix of the NASM manual.

Quote:Original post by Nice Coder
Thank you for the replies,
I am mainly interested in the hardware that implements the stack because i do not know about that yet. (i am interested in nearly everything anything i do not know).

The main thing which made me think of the hardware of it is because i could not think of a way to implement the stack.

while you don't implement the hardware stack in any laguage, you use it in assembly and machine language. its a very simple concept here. there is one register (sp, for Stack Pointer) which contains a memory address of the top of the stack. calling "push" increments the address and places the value there, calling "pop" decrements the address. these are CPU instructions but you can manually manipulate the address as well.

the same could be done using just an array and a pointer. the pointer would stop at it's first position, incrementing based on calls to push and storing the value, while pop just decrements the pointer. there is no need to erase values above the pointer, just assume that these values are garbage and will overwritten with any call to push.

after your through with a pointer, an array, and two function calls you may want to try to encapsulate this in a class. that part should come very easy if you know C++.

like i said though, i haven't found any really effective uses of a stack. i DID have an interview for a job where i was required to write one though. so, if being the nerd who gets the job counts: they can be helpfull.