Procedure: Stack Operations Stack Operations
Procedure: Stack Operations Stack Operations
•   Stack Operations
                                                •   Defining and Using Procedures
                                                •   Stack frames,, p
                                                                   parameters and local variables
Procedure                                       •   Recursion
                                                •   Related directives
Computer
   p     Organization
           g z        and Assemblyy Languages
                                       g g
Yung-Yu Chuang
                                                Stacks
                                                • LIFO (Last-In, First-Out) data structure.
                                                • push/pop
                                                       h/    operations
                                                                     i
                                                • You probably have had experiences on
                                                  implementing it in high-level languages.
                            Stack operations    • Here,, we concentrate on runtime stack,,
                                                  directly supported by hardware in the CPU.
                                                  It is essential for calling
                                                                            g and returning
                                                                                          g from
                                                  procedures.
                                                                                                    4
Runtime stack                                                    PUSH and POP instructions
• Managed by the CPU, using two registers                        • PUSH syntax:
   – SS (stack
        ( t k segment) t)                                           – PUSH r/m16
   – ESP (stack pointer) * : point to the top of the stack          – PUSH r/m32
     usually
          ll modified
                difi d by
                       b CALL,
                          CALL RETRET, PUSH and   d POP             – PUSH imm32
                                                                 • POP syntax:
                                                                        y
                      SS                                            – POP r/m16
                    ESP              stack                                 /
                                                                    – POP r/m32
                                     segment
                            memory
* SP in Real-address mode
                                                             5                                                        6
                                                                          0FF0                      0FF0
      0FEC                                 0FEC
                                                                          0FF4                ESP   0FF4
      0FF0                                 0FF0                                                            00000002
                                                                    ESP   0FF8                      0FF8
      0FF4                                 0FF4                                  00000001                  00000001
                            PUSH 0A5h                                     0FFC                      0FFC
      0FF8                                 0FF8                                  000000A5                  000000A5
                                                                          1000                      1000
      0FFC                           ESP   0FFC                                  00000006                  00000006
                                                  000000A5
ESP   1000                                 1000
               00000006                           00000006                PUSH 01h                  PUSH 02h
                                                             7                                                        8
POP operation                                                    When to use stacks
• Copies value at stack[ESP] into a register or variable.        •   Temporary save area for registers
• Adds n to ESP,
            ESP where n is either 2 or 44, depending on          •   T save return address
                                                                     To               dd   ffor CALL
  the attribute of the operand receiving the data
                                                                 •   To pass arguments
      0FEC                                0FEC                   •   Local variables
      0FF0                                0FF0                   •   Applications which have LIFO nature
                                                                                                  nature, such as
ESP   0FF4                                0FF4                       reversing a string
             00000002
      0FF8
             00000001
                                    ESP   0FF8
                                                 00000001
      0FFC                                0FFC
             000000A5                            000000A5
      1000                                1000
             00000006                            00000006
                          POP EAX
                                          EAX=00000002
                                                            9                                                               10
                                                      15                                                           16
                                                              Creating Procedures
                                                              • Large problems can be divided into smaller
                                                                tasks to make them more manageable
                                                              • A procedure is the ASM equivalent of a Java or
                                                                C++ function
                                                              • Following is an assembly language procedure
    Defining and using procedures                               named sample:
                                                                       sample PROC
                                                                          .
                                                                          .
                                                                           et
                                                                          ret
                                                                       sample ENDP
                                                                A named
                                                                      d block
                                                                        bl k off statements
                                                                                  t t    t th
                                                                                            thatt ends
                                                                                                    d with
                                                                                                       ith a return.
                                                                                                               t
                                                                                                                       18
21 22
                                                                                                   Stack
                                                                            .
                                                                            ret
                                                                         Sub3 ENDP
                                                           23                                                         24
Local and global labels                                            Procedure parameters (1 of 3)
A local label is visible only to statements inside the same
procedure. A g
p              global label is visible everywhere.
                                           y
                                                                   • A good procedure might be usable in many
                                                                     different programs
                                                                     diff
        main PROC
           jmp L2                ; error!                          • Parameters help to make procedures flexible
        L1::                     ; global label                      because parameter values can change at
           exit                                                      runtime
        main ENDP
                                                                   • General registers can be used to pass
        sub2 PROC                                                    parameters
        L2:                      ; local label
           jmp L1                ; ok
           ret
        sub2 ENDP
                                                              25                                                          26
                                                  Stack frame
                                                  • Also known as an activation record
                                                  • Area
                                                    A     off the
                                                               h stack k set aside
                                                                                id ffor a procedure's
                                                                                               d '
                                                    return address, passed parameters, saved
                                                    registers,
                                                       i t      and
                                                                  d llocall variables
                                                                               i bl
    Stack frames, parameters and                  • Created by the following steps:
            local variables                          – Calling procedure pushes arguments on the stack
                                                       and calls the procedure.
                                                     – The subroutine is called,
                                                                         called causing the return
                                                       address to be pushed on the stack.
                                                     – The called procedure pushes EBP on the stack, and
                                                       sets
                                                          t EBP to
                                                                 t ESP
                                                                    ESP.
                                                     – If local variables are needed, a constant is
                                                       subtracted from ESP to make room on the stack.
                                                     – The registers needed to be saved are pushed.
                                                                                                           32
Stack frame                                             Explicit access to stack parameters
 ESP                      ESP                           • A procedure can explicitly access stack
               saved
             registers
                                                          parameters
                                                                 t   using
                                                                       i constant
                                                                               t t offsets
                                                                                      ff t ffrom EBP.
                                                                                                  EBP
                          EBP           ebp                – Example: [ebp + 8]
               local                                    • EBP is often called the base pointer or frame
   [EBP-4]
   [EBP 4]
             variables                                    pointer because it holds the base address of the
                                                          p
                                        ebp
 EBP
                ebp
                                                          stack frame.
   [EBP+4]
              ret addr                                  • EBP does not change value during the
   [EBP+8]                                                procedure.
             parameters                 ebp
                                                        • EBP must be restored to its original value when
                                                          ap
                                                           procedure returns.
                                                   33                                                            34
Parameters                                              Parameters
• Two types: register parameters and stack                   call by value             call by reference
  parameters.
  parameters                                            i t sum=AddTwo(a,
                                                        int     AddT (    b)
                                                                          b); int
                                                                              i t sum=AddTwo(&a,
                                                                                      AddT (&    &b);
                                                                                                 &b)
• Stack parameters are more convenient than                            .date
  register
     i t parameters.
                 t                                                     a DWORD     5
                                                                       b DWORD     6
p
pushad                     p
                           push   TYPE array
                                           y
mov esi,OFFSET array       push   LENGTHOF array        push b                     push OFFSET b
mov ecx,LENGTHOF array     push   OFFSET array          push a                     push OFFSET a
mov ebx,TYPE array         call   DumpMem               call
                                                          ll AddTwo
                                                               dd                  call
                                                                                     ll AddTwo
                                                                                         dd
call DumpMem
popad                                                                        ESP                           ESP
                                                                  5                       offset(a)
   register parameters          stack parameters
                                                                  6                       offset(b)
                                                                                                ( )
                                                   35                                                            36
Stack frame example                                             Stack frame example
   .data                                                        AddTwo PROC
   sum DWORD ?                                                     push ebp
   .code                                                           mov ebp,esp        ; base of stack frame
      push 6
      p                    ;   second argument
                                        g                          mov eax,[ebp + 12] ; second argument (6)
      push 5               ;   first argument                      add eax,[ebp + 8] ; first argument (5)
      call AddTwo          ;   EAX = sum                           pop
                                                                   p p ebp
                                                                         p
      mov sum,eax          ;   save the sum
                                                                   ret 8              ; clean up the stack
   AddTwo PROC                                                  AddTwo ENDP          ; EAX contains the sum
      push ebp                                      EBP                                                         EBP
                                      ebp
                                                                                                   ebp
      mov ebp,esp                                               Who should be responsible to
                                    rett addr
                                          dd    [EBP+4]
      .                                                         remove arguments? It depends     ret addr   [EBP+4]
      .                                5        [EBP+8]         on the language model.              5       [EBP+8]
                                       6        [EBP+12]
                                                                                                    6       [EBP+12]
                       ESP                                 37                                                          38
                                                           39                                                          40
Passing arguments by reference                                           Passing 8-bit and 16-bit arguments
ArrayFill can reference an array without                                 • When passing stack arguments, it is best to
knowing the array
            array'ss name:                                                 push 32-bit
                                                                                32 bit operands to keep ESP aligned on a
                                                                           doubleword boundary.
 ArrayFill
      y     PROC
                                                             EBP         Uppercase PROC               push   ‘x’ ; error
    push ebp                                 ebp
    mov ebp,esp                                                              push ebp                 Call   Uppercase
                                           ret addr     [EBP+4]              mov ebp, esp
    pushad
        h d                                                                  mov al, [ebp+8]
    mov esi,[ebp+12]                        count        [EBP+8]
                                                                             cmp al, ‘a’
                                                                                                      .data
    mov ecx
          ecx,[ebp+8]
              [ebp+8]                 offset(array)
                                       ff t(      )      [EBP+12]            jb   L1
                                                                                                      charVal BYTE ‘x’
    .                                                                        cmp al, ‘z’
                                                                                                      .code
    .                                                                        ja   L1
                                                                                                               , charVal
                                                                                                      movzx eax,
                                                                             subb al,
                                                                                   l 32
                                                                                                      push eax
                                                                         L1: pop ebp
                                                                                                      Call Uppercase
                                                                             ret 4
                                                                         Uppercase ENDP
                                                                    41                                                               42
                                              …
  .                              [EBP+8]
                                                      45                                                            46
                                                    51                                                            52
MASM-generated code                                       Non-Doubleword Local Variables
BubbleSort PROC
                                                          • Local variables can be different sizes
   LOCAL temp:DWORD,
            p      , SwapFlag:BYTE
                        p   g
   . . .                                                  • How are they created in the stack by LOCAL
   ret                                                      directive:
B bbl S t ENDP
BubbleSort
                                                             – 8-bit: assigned to next available byte
  MASM generates the following code:                         – 16-bit: assigned to next even (word) boundary
BubbleSort PROC                                              – 32-bit: assigned to next doubleword boundary
   push ebp
   mov ebp
         ebp,esp
             esp
   add esp,0FFFFFFF8h ; add -8 to ESP
   . . .
   mov esp,ebp
   pop ebp
   ret
BubbleSort ENDP                                      53                                                        54
                                                          Sub3 PROC
mov   eax,
         , temp
              p                 mov   eax,
                                         , [
                                           [ebp-4]
                                              p ]           LOCAL array3[300]:WORD ; 300 bytes
mov   bl, SwapFlag              mov   bl, [ebp-5]         660+8(ret addr)+saved registers…
                                                     55                                                        56
                                                                      Recursion
                                                                      • The process created when . . .
                                                                        – A procedure
                                                                                  d    calls
                                                                                         ll it
                                                                                             itself
                                                                                                 lf
                                                                        – Procedure A calls procedure B, which in turn
                                                                          calls procedure A
                                                                      • Using a graph in which each node is a
                  Recursion                                             procedure
                                                                             d     and
                                                                                     d eachh edge
                                                                                              dg is
                                                                                                  i a procedure
                                                                                                           d    call,
                                                                                                                  ll
                                                                        recursion forms a cycle:
E B
                                                                                             D            C
                                                                                                                           58
                                              …
   jmp
   j p L2
L1:dec eax
   push eax                                 ebp
   call Factorial                       rett Factorial
                                             F t i l
ReturnFact:                                  11
   mov
    o   eb
        ebx,[ebp+8]
           ,[ebp 8]
   mul ebx                                  ebp
      ; address of variable:
      INVOKE Sub2,ADDR byteVal                                  push val1
                                                                push
                                                                   h val2
                                                                       l2
      ; register name, integer expression:                      call AddTwo
      INVOKE Sub3,eax,(10 * 20)
69 70
78
                                       INCLUDE Irvine32.inc
• EXTERN sub1@0:PROC
                                       PromptForIntegers PROTO,
                                          ptrPrompt:PTR BYTE,        ; prompt string
• PUBLIC count
         count, SYM1                      ptrArray:PTR
                                           t A     PTR DWORD
                                                       DWORD,        ; points
                                                                         i t tto th
                                                                                 the array
                                          arraySize:DWORD            ; size of the array
  SYM1=10
  .data
   d t                                 ArraySum PROTO,
  count DWORD 0                           ptrArray:PTR DWORD,        ; points to the array
                                          count:DWORD                ; size of the array
Main.asm
TITLE Integer Summation Program
INCLUDE sum.inc
.code
 code
main PROC
   call Clrscr
   INVOKE PromptForIntegers,
      ADDR prompt1,
      ADDR array,
           array
      Count
      ...
      call Crlf
      INVOKE ExitProcess,0
main ENDP
END main
                                  83