notes

Personal notes
git clone git://git.laack.co/notes.git
Log | Files | Refs

Stack.md (1943B)


      1 # Stack
      2 
      3 CS202 L14 / CS303 Ch 1
      4 
      5 **Definition:** This is a data structure that uses the lifo approach where you add to the top and remove from the top of the struct.
      6 
      7 push: add to stack
      8 
      9 peek: get top element. This can also be implemented by doing pop then pushing the result. 
     10 
     11 pop: remove from top
     12 
     13 This can be implemented as a [SinglyLinkedList](SinglyLinkedList.md)
     14 
     15 See [Queue](Queue.md) for information about the fifo implementation.
     16 
     17 ---
     18 
     19 # ASM Stack
     20 
     21 **Source:** Performance Aware Programming 
     22 
     23 "The Stack" in ASM
     24 
     25 The stack is a region of memory allocated to the task of storing relatively small amounts of scoped variables. Additionally, the stack grows downwards in terms of memory addresses.
     26 
     27 In 8086, somewhere early on in the program there will be an instruction like `mov sp 40000` which will set the stack pointer to the logical bottom of the stack (note, this grows by decrementing the address).
     28 
     29 Then to push to the stack we may do something like this:
     30 
     31 ```asm
     32 sub sp, -2
     33 mov [sp], ax
     34 ```
     35 
     36 And to pop from the stack we may:
     37 
     38 ```asm
     39 mov ax, [sp]
     40 add sp, 2
     41 ```
     42 
     43 This is one way, bad but illustrative, to do this. The other way is as follows:
     44 
     45 ```asm
     46 push ax
     47 ```
     48 
     49 ```asm
     50 pop ax
     51 ```
     52 
     53 This is often used with functions, and either the function or calling code could push / pop.
     54 
     55 To store the IP register so functions may return from where they're called from we can do this:
     56 
     57 ```asm
     58 call interesting_function
     59 ```
     60 
     61 This will push the IP to the stack and then jump.
     62 
     63 To pop the IP register we may use:
     64 
     65 ```asm
     66 ret
     67 ```
     68 
     69 ## Calling Conventions
     70 
     71 Pushing registers to the stack introduces the concept of "calling conventions" which dictate who performs what operations.
     72 
     73 There are also conventions about how to pass parameters and how to return parameters. These are arbitrarily defined, but must be agreed upon.
     74 
     75 This is also where the idea of an "ABI" comes from. Executables and shared libraries have to adhere to these conventions.