==============================================================================
C-Scene Issue #2
A stack implementation in C. (Advanced datatypes)
Wendall Marvel
==============================================================================
A stack is a filo(first in last out) queue, with two operations that
can be performed on it, push, which puts a value on the stack, and
pop, which grabs the last value pushed. A pointer points at the spot on the
stack where the last value pushed is held. On Intel x86 based chips, the
sp (stack pointer, esp in protected mode) is used for this purpose.
The internal stack grows downward, so in memory, it looks like this:
We'll start with an empty stack:
top of memory somewhere up here
| | <- sp (pointing outside the stack)
junk data | bottom of stack |
bottom of memory somewhere down here
Now, we push a value, say, al, and say al's value is 0xF0
First, sp gets decremented by the size of al (in this case one byte)
(remember, our stack grows down)
junk | bottom of stack | <- sp (now pointing at valid stack space)
then, the value gets put on the stack:
F0 | bottom of stack | <- sp
ok, lets try pushing ebx, assumming ebx has a value of 0xFFDD01A3
F0 | bottom of stack | <- sp (stack before the push)
first, sp gets decremented by 4 (the size of a value held in eax)
F0 | bottom of stack |
junk | |
junk | |
junk | |
junk | | <- sp
then, the value in eax gets put on the stack:
F0 | bottom of stack |
FF | |
DD | |
01 | |
A3 | | <- sp
Note: although it looks a bit backwards, your box really keeps
the value in memory with the least significant byte lower in memory
than the most significant byte, ie, what you read as 0xAABBCCDD
from left to right, is held in memory as DD CC BB AA from lowest addressed
byte to highest. (I may be telling you things you already know :))
ok, lets try a pop, say, pop eax (we have to pop the same size we last
pushed, or our stack will get all screwed up):
first, the value at sp gets read and put in the register:
F0 | bottom of stack |
FF | |
DD | |
01 | |
A3 | | <- sp
EAX == 0xFFDD01A3
then, sp gets incremented by the size of eax (4 bytes, since eax is a
doubleword register)
F0 | bottom of stack | <- sp
FF | |
DD | |
01 | |
A3 | |
note that the values on the stack didn't change, they're still there.
locals are allocated on the stack by decrementing sp by the size of all locals
added together, so, if we now allocated a local long, our local would have
an initial value of 0xFFDD01A3, not 0. this is what caused your friend's error
the other day.
Stack before local allocation:
F0 | bottom of stack | <- sp
FF | |
DD | |
01 | |
A3 | |
Stack after local allocation(by subtracting 4, the size of a long, from sp):
F0 | bottom of stack |
FF | |
DD | |
01 | |
A3 | | <- sp
ok, enough of my babbling, lets get to the code. :)
/*
a simulation of the internal stack, along with a demonstration of how
the stack is used to pass arguments and allocate local variables.
*/
#include <stdio.h>
#include <stdlib.h>
/*Size of our stack, 2k is more than reasonable for what we're doing*/
#define STACKSIZE 2048
/*defines for our lil fake assembly language.. */
#define add(a,b) (a=a+b)
#define sub(a,b) (a=a-b)
#define mov(a,b) (a=b)
#define xor(a,b) (a=a^b)
#define call(a) (a())
#define push(a) (pus((void *)&a,sizeof(a)))
#define pop(a) (po((void *)&a,sizeof(a)))
#define ret return
/*defines so we can call my unionized fake registers by some sensible name :)*/
#define EAX fakeregs.e.eax
#define EBX fakeregs.e.ebx
#define ECX fakeregs.e.ecx
#define EDX fakeregs.e.edx
#define AX fakeregs.w.ax
#define BX fakeregs.w.bx
#define CX fakeregs.w.cx
#define DX fakeregs.w.dx
#define AH fakeregs.b.ah
#define AL fakeregs.b.al
#define BH fakeregs.b.bh
#define BL fakeregs.b.bl
#define DH fakeregs.b.dh
#define DL fakeregs.b.dl
/*
structures to simulate our registers, set up so that a mov into eax
appropriately changes ax and ah, al at the same time, just like your
real registers. We do this through packed structures put in a union,
with our own placeholders set in appropriate places in the structures
ie, all the structures are really the same size, so the union is the
same size as any single structure. we just place ax, etc in the right
spots (ax is the low order word of eax, ah is high byte and al is low
byte of ax)
*/
struct dwregs
{
unsigned long eax;
unsigned long ebx;
unsigned long ecx;
unsigned long edx;
} __attribute__ ((__packed__));
/*
members with names beginning with h (ie, hax) are just placeholders
to keep alignment straight, so that if we set EAX then AX, AH, AL, will
be set appropriately,
*/
struct wregs
{
unsigned short ax; /*low order word of eax*/
unsigned short hax;/*pad, not used,high order word of eax in struct dwregs*/
unsigned short bx;
unsigned short hbx;/*pad, not used, etc..*/
unsigned short cx;
unsigned short hcx;
unsigned short dx;
unsigned short hdx;
} __attribute__ ((__packed__));
struct bregs
{
unsigned char al; /*low order byte of ax*/
unsigned char ah; /*high order byte of ax*/
unsigned char hal; /*pad, not used, low order byte of hax in struct wregs*/
unsigned char hah; /*pad, not used, high order byte of hax in struct wregs*/
unsigned char bl;
unsigned char bh;
unsigned char hbl;
unsigned char hbh;
unsigned char cl;
unsigned char ch;
unsigned char hcl;
unsigned char hch;
unsigned char dl;
unsigned char dh;
unsigned char hdl;
unsigned char hdh;
} __attribute__ ((__packed__));
/*define for our register union, which makes it all work almost real-like ;)*/
union regs
{
struct dwregs e;
struct wregs w;
struct bregs b;
} __attribute__ ((__packed__));
union regs fakeregs;
/*
your internal stack doesn't have any other pointers except sp, it keeps track
of stack overflows all by itself(processor generates the error), however,
we need a way to detect stack overflow/underflow (a push or pop one too many
times), so I have the pointers stack_base and stack_end.
because stack grows down, stack_base really points above stack_end in mem
*/
char *stack_base, *stack_end;
/*
our stack pointer, sp, directly corresponds to internal sp register.
bp(base pointer) corresponds to bp register, but we only use it to save sp.
*/
char *sp, *bp = NULL;
/*string is just here so we'll have an argument to pass*/
char *string = "Hello, World\n";
/*error functions*/
void overflow(void)
{
printf("Stack Overflow!!\n");
free(stack_end);
exit(0);
}
void underflow(void)
{
printf("Stack Underflow!!\n");
free(stack_end);
exit(0);
}
stackerr()
{
printf("Unknown Stack Error!!\n");
free(stack_end);
exit(0);
}
/*
for the push and pop routines, I use macros to simulate the assembly
instructions (push <arg>, pop <arg>). The instructions determine how
much to add/sub to sp by the size of the registers, so our macros
look like #define push(what) (pus(&what,sizeof(what)))
*/
/*our push routine.. decrement, put the value there*/
pus(char *what, int size)
{
if((sp-size)<stack_end) overflow(); /*pushed one too many times?*/
sp-=size;
switch(size)
{
case 1:
*sp = *what;
break;
case 2:
*((short *)sp) = *((short *)what);
break;
case 4:
*((long *)sp) = *((long *)what);
break;
default:
stackerr();
break;
}
}
/*our pop routine.. get the value, increment*/
po(char *what, int size)
{
if((sp+size)-1>stack_base) underflow(); /*popped one to many times?*/
switch(size)
{
case 1:
*what = *sp;
break;
case 2:
*((short *)what) = *((short *)sp);
break;
case 4:
*((long *)what) = *((long *)sp);
break;
default:
stackerr();
break;
}
sp+=size;
}
void funcall(void)
{
push(bp); /*bp is a char *, size is 4 bytes*/
mov(bp,sp);/*save our current sp*/
/*let's make some space for local variables, say, 2 longs, and a char*/
sub(sp,9);
/*we'll see how our locals look uninitialized*/
printf("Uninitialized:\n");
printf("local1 (char) = %c, local2 (long) = %d, local3 (long) = %d\n",
*sp, *((long *)(sp+1)), *((long *)(sp+5)));
/*sometimes locals happen to be 0 uninitialized, sometimes they dont.*/
/*you can never be sure though*/
/*and, initialized*/
mov(*sp, 'c');
mov(*((long *)sp+1),1000000);
mov(*((long *)sp+5),2000000);
printf("Initialized:\n");
printf("local1 (char) = %c, local2 (long) = %d, local3 (long) = %d\n",
*sp, *((long *)(sp+1)), *((long *)(sp+5)));
/*ok, our arg should be at bp+4, lets check*/
printf("%s",*((long *)(bp+4)));
add(sp,9); /*clear the stack of our locals*/
mov(sp,bp);
pop(bp);
ret;
}
void asmstuff(void)
{
push(bp);
mov(bp,sp);
/*ok, push our args*/
push(string);
call(funcall);
/*in real life, a return address would have gotten pushed onto the stack */
/*by the call instruction, but our fake call instruction doesn't.*/
/*just something to remember if you ever code/have coded in real asm.*/
add(sp,4); /*clear args from stack*/
mov(sp,bp);/*restore sp*/
pop(bp);/*restore bp*/
ret;/*that's it, we're done. :)*/
}
int main()
{
int x;
/*stack initialization*/
stack_end =(char *)malloc(STACKSIZE);
if(stack_end == NULL)
{
printf("Error allocating stack\n\n");
return(0);
}
stack_base = stack_end + STACKSIZE;
sp = stack_base + 1;
/*
our empty stack is now set up...
looks something like this
<- sp (pointing one byte above bottom)
junk | bottom of stack | <- stack_base points here
...
junk | end of stack | <- stack_end points here
remember that the stack grows down, and the bottom of the stack is really
higher in memory than the top of the stack...
*/
/* Just making sure I did it right :) */
#ifdef 0
printf("Union alignment check!!\n");
fakeregs.e.eax = 0xAABBCCDD;
if(fakeregs.w.hax == 0xAABB && AX == 0xCCDD && AH ==
0xCC && AL == 0xDD)
printf("Alignment checked good!!\n");
else printf("Alignment check failed.\n");
#endif
mov(AX,4);
mov(BX,5);
printf("AX = %d, BX = %d, before push/pops\n",AX,BX);
push(AX);
push(BX);
/*
right now, our stack looks like this:
00 | bottom of stack | <- stack_base still pointing here, always will
04 | | (low order byte ax)
00 | | (high order byte bx)
05 | | <- sp
....
junk | end of stack space| <- stack end still points here, always will
*/
pop(AX);
pop(BX);
printf("AX = %d, BX = %d, after push/pops\n",AX,BX);
/*
did this really only to put junk in the stack so I could show you the perils
of uninitialized locals. :)
*/
for(x=0;x<2;x++)
{
mov(EAX,1234576);
printf("pushing EAX, value %d\n",EAX);
push(EAX);
mov(EBX,3454826);
printf("pushing EBX, value %d\n",EBX);
push(EBX);
mov(ECX,2456290);
printf("pushing ECX, value %d\n",ECX);
push(ECX);
mov(EDX,2083450);
printf("pushing EDX, value %d\n",EDX);
push(EDX);
}
printf("Popping values off stack into EAX:\n");
for(x = 0;x < 8; x++)
{
pop(EAX);
printf("%d\n",EAX);
}
asmstuff();
free(stack_end);
return(0);
}
/*
I didn't comment the code as much this time, because I thought with the big
long explanation of how the stack works at the top the code would be
fairly easy to follow. :)
also note that the internal stack on some architechtures grows up, not down.
The stack on an x86 grows down, why I did it that way.
*/
C Scene Official Web Site :
http://cscene.oftheinter.net
C Scene Official Email :
cscene@mindless.com
This page is Copyright © 1997 By
C Scene. All Rights Reserved