Last In, First Out via the Stack

One problem with assembly language is that it's tough knowing where to put things. There are only so many registers to go around. Having variables in a data segment is helpful, but it isn't the whole story. People who come to assembly from higher-level languages such as Pascal and Basic find this particularly jarring, since they're used to being able to create new variables at any time as needed.

The x86 CPUs contain the machinery to create and manage a vital storage area called the stack. The name is appropriate, and for a usable metaphor I can go back to my high school days, when I was a dishwasher for Resurrection Hospital on Chicago's Northwest Side.

Five Hundred Plates an Hour

What I did most of the time was pull clean plates from a moving conveyor belt of little prongs that emerged endlessly from the steaming dragon's mouth of a 180° dishwashing machine. This was hot work, but it was a lot less slimy than stuffing the dirty plates into the other end of the machine.

When you pull 500 plates an hour out of a dishwashing machine, you had better have some place efficient to stash them. Obviously, you could simply stack them on a table, but stacked ceramic plates in any place habituated by rowdy teenage boys is asking for fragments. What the hospital had instead was an army of little wheeled stainless steel cabinets equipped with one or more spring-loaded circular plungers accessed from the top. When you had a handful of plates, you pushed them down into the plunger. The plunger's spring was adjusted such that the weight of the added plates pushed the whole stack of plates down just enough to make the new top plate flush with the top of the cabinet.

Each plunger held about 50 plates. We rolled one up next to the dragon's mouth, filled it with plates, and then rolled it back into the kitchen where the clean plates were used at the next meal shift to set patients' trays.

It's instructive to follow the path of the first plate out of the dishwashing machine on a given shift. That plate got into the plunger first and was subsequently shoved down into the bottom of the plunger by the remaining 49 plates that the cabinet could hold. After the cabinet was rolled into the kitchen, the kitchen girls pulled plates out of the cabinet one by one as they set trays. The first plate out of the cabinet was the last plate in. The last plate out of the cabinet had been the first plate to go in.

The x86 stack is like that. We call it a last in, first out, or LIFO stack.

An Upside-Down Segment

Two of the x86 registers team up to create and maintain the stack. Like everything else in 86-land, the stack must exist within a segment. The SS (Stack Segment) register holds the segment address of the segment chosen to be the stack segment, and the SP (Stack Pointer) register points to locations within the stack segment. As with all other segments in real mode, the stack segment may be as much as 65,536 bytes long, but it may be any length less than that as well. You'll find in practice that the stack rarely needs to be larger than a thousand bytes or so unless you're doing some really peculiar things.

The stack segment begins at SS:0, but the truly odd thing about it is that all the stack action happens at the opposite end of the stack segment. When a stack segment is set up, the SS register points to the base or beginning of the stack segment, and SP is set to point to the end of the stack segment. To store something in the stack segment (which we usually call "pushing something onto the stack"), we move SP "down the stack" (that is, closer to SS) and then copy the item to the memory location pointed to by SS:SP.

This takes some getting used to. Figure 8.1 provides the big picture of the stack segment and the two pointers that give it life. In real mode flat model, SS is set to the base of the stack segment by DOS when the program is loaded and begins running. (And all the other segment registers are set to the same address.) In real mode segmented model, you set SS from the address of the segment that you define within the program in two steps, first using NASM's SEGMENT directive:

Figure 8.1: The big picture of the real mode stack.

SEGMENT stack stack

Then you need a couple of MOV instructions to get the address of segment stack into SS:

mov	ax,stack	;	Move	segment	address	of stack segment into AX
mov	ss,ax	;	Copy	address	from AX	into SS

Defining a stack segment just provides a starting point address for that segment. No room is actually reserved for the stack by the SEGMENT directive. That requires a new directive that we haven't discussed:

resb 64 ; Reserve 64 bytes for the program stack

RESB means "REServe Byte." And it means just that: It tells the assembler to set aside 64 bytes starting at the beginning of the stack segment and not to let anything else (such as memory variables) be defined in that reserved space. You can use RESB to reserve as much stack as you think you'll need; 64 bytes is enough for simple experimentation. If you're writing a more ambitious program, you may be better off looking at what it does and actually estimating a worst-case demand for stack space.

Note that you don't need to use RESB to reserve stack space if you're working in real mode flat model. The stack in that model exists at the very highest addresses of the single segment the program lives in. The space isn't reserved in the strictest sense, and you have to be careful not to let your code or data get so high in memory that it collides with your stack. This is called a stack crash and you're not likely to see one in your own programs until you get a lot further along in your assembly experience.

SP is set to the far (that is, the high, address-wise) end of the stack segment. (See Figure 8.1, where an arrow indicates the initial value of SP.) Again, if you're working in real mode flat model, DOS does it when your program is loaded—as you can see if you load EAT.COM with DEBUG and display the registers with the R command. SP will have a value something like 0FFFEH—in any case, something fairly high rather than close to 0000H.

And if you're working in real mode segmented model, you have to set SP yourself. This is done by first

indicating the initial address to be contained in SP:

resb 64	; Reserve 64 bytes for the program stack
stacktop:	;	It's significant that this label points to
	; the *last* of the reserved 64 bytes, and
	;	not the first!

Note that the label stacktop: is immediately after the RESB 64 directive. The label stacktop: represents an address at the very end of the block of reserved memory locations set aside by RESB. Although the position of the two lines on the source code listing suggests that stacktop: points beyond the block of memory set aside by RESB, that's not the case. The stacktop: label resolves to the offset of the last byte in that block of 64 bytes.

You load the address represented by the stacktop: label into SP when the program begins, typically right after you set up the segment registers:

mov sp,stacktop

; Point SP to the top of the stack

After that's set up, you have valid values in both SS and SP, and you can begin using the stack.

Pushing Data

You can place data onto the stack in numerous ways, but the most straightforward way involves a trio of related machine instructions, PUSH, PUSHF, and PUSHA. The three are similar in how they work, and differ as to what they push onto the stack. PUSHF pushes the Flags register onto the stack. PUSHA pushes all eight of the 16-bit general-purpose registers. PUSH pushes a 16-bit register or memory value that is specified by you in your source code, like so:

PUSHF	; Push the Flags register
PUSHA	; Push AX, CX, DX, BX, SP, BP, SI, and DI, in that order, all at on
PUSHAD	; Push EAX, ECX, EDX, EBX, ESP, ESP, EBP, ESI, and EDI, all at once
PUSH AX	; Push the AX register
PUSH [BX] ; Push the word stored in memory at DS:BX
PUSH DI	; Push the DI register
PUSH ES	; Push the ES register

Note that PUSHF takes no operands. You'll generate an assembler error if you try to hand it an operand;

PUSHF pushes the flags and that's all it is capable of doing.

PUSH and PUSHF work this way: First SP is decremented by one word (two bytes) so that it points to an empty area of the stack segment that is two bytes long. Then whatever is to be pushed onto the stack is written to memory in the stack segment at the offset address in SP. Voila! The data is safe on the stack, and SP has crawled two bytes closer to SS. We call the word of memory pointed to by SP the top of the stack.

PUSHA works the same way, except that it pushes eight 16-bit registers at once, thus using 16 bytes of stack space at one swoop. One thing to remember is that PUSHA is a newer instruction that doesn't exist on the 8086 and 8088. It first appeared with the 286.

PUSHAD was added with the 386, and it pushes all eight 32-bit general-purpose registers onto the stack in one blow.

All memory between SP's initial position and its current position (the top of the stack) contains real data that was explicitly pushed on the stack and will presumably be fetched from the stack (we say popped from the stack) later on. In real mode segmented model, the stack exists in a separate segment, and memory between SS and SP is considered free and available and is used to store new data that is to be pushed onto the stack. This is not the case in real mode flat model, where the stack shares the same segment that everything else in the program is using.

What can and cannot be pushed onto the stack is complicated and depends on what CPU you're using. None of the x86 CPUs can push 8-bit registers onto the stack. You can't push AL or BH or any other of the 8-bit registers. Segment registers and 32-bit extended general-purpose registers can be pushed in real mode,

assuming you have a 386 or later CPU. Similarly, immediate data can be pushed onto the stack, but only if you have a 286 or later CPU. Keeping track of all this used to be a problem, but you're unlikely to be running code on CPUs earlier than the 386 these days.

Your morbid curiosity may be wondering what happens when SP runs out of room in its downward crawl and collides with SS. Nothing good, certainly—it depends heavily on how your program is laid out—but I would lay money on your program crashing hard and possibly taking the system down with it. (If you're working in a DOS box under Windows NT you at least won't crash the operating system. All bets are off for Windows 9x!)

Stack crashes are serious business, at least in part because there is only one stack in action at a time in real mode. It's a little hard to explain (especially at this stage in our discussion), but this means that the stack you set up for your own program must be large enough to support as well the needs of DOS and any interruptdriven code (typically in the BIOS) that may be active while your program is running. Even if you don't fully understand how someone else may be using your program's stack at the same time you are, give those other guys some extra room—and keep an eye on the proximity of SS and SP while you trace a program in DEBUG.

POP Goes the Opcode

In general, what gets pushed must get popped, or you can end up in any of several different kinds of trouble. Getting a word of data off the stack is done with another trio of instructions, POP, POPF, andPOPA. As you might expect, POP is the general-purpose one-at-a-time popper, while POPF is dedicated to popping the flags off of the stack. POPA pops 16 bytes off the stack into the eight general-purpose 16-bit registers. POPAD is the flip side of PUSHAD and pops the top 32 bytes off the stack into the eight general-purpose 32-bit registers.

POPF	;	Pop	the	top	of	the stack into	Flags	into AX, CX, DX, BX, SP,
POPA	;	Pop	the	top	16	bytes from the	stack

;BP, SI, and DI

POPAD		; Pop the top 32 bytes into EAX, ECX, EDX, EBX, ESP, ESP, EBP,
POP SI		;	ESI, and EDI
		; Pop the top of the stack into SI
POP	CS	; Pop		the	top	of the stack into CS
POP	[BX] ;		Pop	the	top	of the stack into memory at DS:BX

As with PUSH, POP only operates on word-sized operands. Don't try to pop data from the stack into an 8-bit register such as AH or CL.

POP works pretty much the way PUSH does, but in reverse: First the word of data at SS:SP is copied from the stack and placed in POP's operand, whatever you specified that to be. Then, SP is incremented (rather than decremented) by two bytes, so that in effect it moves two bytes up the stack, away from SS.

It's significant that SP is decremented before placing a word on the stack at push time, but incremented after removing a word from the stack at pop time. Certain other CPUs work in the opposite manner, which is fine—just don't get confused. Unless the stack is empty, SP points to real data, not empty space.

Ordinarily, you don't have to remember that fact, as PUSH and POP handle it all for you and you don't have to manually keep track of what SP is pointing to. If you decide to manipulate the stack pointer directly, it helps to know the sequence of events behind PUSH and POP—and that's an advanced topic that I won't be going into in this book.

Figure 8.2 shows the stack's operation in a little more detail. The values of the four "X" registers at some hypothetical point in a program's execution are shown at the top of the figure. AX is pushed first on the stack.

Figure 8.2: How the stack works.

Its least significant byte is at SS:SP, and its most significant byte is at SS:SP+1. (Remember that both bytes are pushed onto the stack at once, as a unit!)

Each time one of the registers is pushed onto the stack, SP is decremented two bytes down toward SS. The first three columns show AX, BX, and CX being pushed onto the stack, respectively. But note what happens in the fourth column, when the instruction POP DX is executed. The stack pointer is incremented by two bytes and moves away from SS. DX now contains a copy of the contents of CX. In effect, CX was pushed onto the stack, and then immediately popped off into DX.

That's a roundabout way to copy the value of CX into DX. MOV DX,CX is lots faster and more straightforward. However, MOV will not operate on the Flags register. If you want to load a copy of Flags into a register, you must first push the Flags register onto the stack with PUSHF, then pop the flags word off the stack into the register of your choice with POP. Getting the Flags register into BX is done like this:

PUSHF ; Push the flags register onto the stack..

POP BX ; ..and pop it immediately into BX

Storage for the Short Term

The stack should be considered a place to stash things for the short term. Items stored on the stack have no names, and in general must be taken off the stack in the reverse order that they were put on. Last in, first out, remember. LIFO!

One excellent use of the stack allows the all-too-few registers to do multiple duty. If you need a register to temporarily hold some value to be operated on by the CPU and all the registers are in use, push one of the busy registers onto the stack. Its value will remain safe on the stack while you use the register for other things. When you're finished using the register, pop its old value off the stack—and you've gained the advantages of an additional register without really having one. (The cost, of course, is the time you spend moving that register's value onto and off of the stack. It's not something you want to do in the middle of an often-repeated loop!)