» CS 352 Lecture 29 – Functions Cont’d

CS 352 Lecture 29 – Functions Cont’d

November 16, 2016 by Chris Johnson. Filed under cs352, fall 2016, lectures.

Dear students,

We try as hard as we can to use registers for our calculations, but we cannot always avoid going to memory. Today we will look at how variables inside functions are allocated, accessed, and freed through a few more examples.

Unlike registers and globals, stack and heap variables don’t have names. We must access them through pointers. We access stack variables through sp, which points to the last allocated element on the stack. sp is the pointer, [sp] is the value.

To allocate local (stack) storage, we simply move sp downward. Many systems organize the stack in an upsidedown manner. If we need an int, we drop sp by 4. If we need two ints, we drop it by 8. To free local storage, we restore the sp to its original value. We probably do not wipe the memory, which is why sometimes returning a reference to a local variable works. The memory is still there, but it is liable to be overwritten by the next function call.

When you declare a bunch of local variables, like inside a loop, one might fear that the allocation will be expensive. Like in this code:

for (int i = 0; i < 100; ++i) {
  int square = i * i;
}

But few compilers will actually allocate and deallocate square again and again. Rather, the compiler will statically determine its storage needs and allocate storage once at the beginning of the function:

sub sp, sp, #4

To access our local variables, we can use sp as a foothold and push off from there:

sub sp, sp, #16
ldr r0, [sp]       // last allocated
ldr r1, [sp, #4]   // last allocated
ldr r2, [sp, #8]   // last allocated
ldr r3, [sp, #12]  // last allocated

When memory needs to live longer than the function, we turn to the heap. We will use malloc to manage that kind of storage. We get back from malloc a pointer that we can use as a foothold much like we do sp.

We will use both the stack and the heap to solve these problems:

encode a secret message
compute a histogram of an int array

Here’s your TODO list:

Start the Armoir homework, which is due before December 16. The specification has been placed in the template repository, but the grading script has not.

See you next class!

Sincerely,

P.S. Here’s the code we wrote together…

encode.s

.text
.global encode

encode:
  push {lr}

  sub sp, sp, #28   // make some room on the stack

  // A's encoding
  mov r1, #68
  str r1, [sp]

  // B's encoding
  mov r1, #90
  str r1, [sp, #1]

  // C's encoding
  mov r1, #81
  str r1, [sp, #2]

  // D's encoding
  mov r1, #65
  str r1, [sp, #3]

  // E's encoding
  mov r1, #74
  str r1, [sp, #3]

  // F's encoding
  mov r1, #92
  str r1, [sp, #4]

  // for (int i = 0; str[i] != '
'; ++i) {
  //   char old_letter = str[i];
  //   int serial = old_letter - 'A';
  //   str[i] = map[serial];
  // }

  mov r1, #0          // i = 0
  b check

loop:
  sub r2, r2, #65     // serial = old_letter - 'A'
  ldrb r3, [sp, r2, lsl #0]   // new_letter = map[serial]6
  strb r3, [r0, r1, lsl #0]   // str[i] = new_letter

  add r1, r1, #1      // ++i

check:
  ldrb r2, [r0, r1, lsl #0]   // r2 = r0[r1]
  cmp r2, #0
  bne loop

  add sp, sp, #28     // make some room on the stack
  pop {lr}
  mov pc, lr

encode.c

#include <stdio.h>

void encode(char *message);

int main(int argc, char **argv) {
  char message[] = {'D', 'E', 'A', 'D', 'B', 'E', 'E', 'F', '
'};
  encode(message);
  printf("%s\n", message);
  return 0;
}