CS 208 s20 — Data Structure Representation: Arrays

Here is a video lecture for the material outlined below. It covers CSPP section 3.8 (p. 255–265). It contains sections on

1. the Sora (0:00)
2. compilation overview (0:38)
3. linking (4:52
4. warmup exercise (11:15)
5. array basics (13:03)
6. example array expressions (17:11)
7. array access in assembly (28:39)
8. for loop/array access exercise (31:15)
9. arrays and functions (33:26)
10. 2D arrays (42:00)
11. end notes (52:17)

The Panopto viewer has table of contents entries for these sections. Link to the Panopto viewer: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=ca2b2f65-5029-4466-810c-abb80107011c

If %rsp is 0x100 and the current stack frame consists of a local array of 4 ints, where is the return address for the current function call stored?¹

• We will start by zooming out a little from assembly to look briefly at the whole compilation process
• Let's say out code is in two files: p1.c and p2.c
• We compile our program with the command: gcc -Og p1.c p2.c -o p
  • this produces a binary file p containing the resulting machine code
  • we can run the program with the command: ./p

• compilation consists of 3 primary phases:
  1. translating source code (e.g., C code) to assembly (still in human-readable text form at this point)
  2. translating assembly to binary object files (each source file is assembled separately)
  3. linking object files (and any standard library files) together into the final executable

• T A[N] means an array of N elements of type T
• contiguously allocated region—how big in terms of N?²
• A is a pointer (T*) to the start of the array

• arrays declared as local variables are allocated in the current stack frame

char* foo() {
    char string[32]; ...;
    return string;
}

void bar() {
    int nums[6];
    ...
}

int main() {
    char *str = foo(); // after foo returns, its stack frame (containing str) is popped off
                       // the string is still there for now...
    bar(); // stack-allocated nums will use the same memory as string from foo
    ... using str ... // program can still use str (refers to valid memory address), but its
                      // contents have been reused in the meantime
}

• the above code is broken, future function calls will overwrite string (draw stack frame)
• an array is passed to a function as a pointer—this means the size gets lost!

int foo(int arr[], unsigned int size) {
    ... arr[size - 1] ...
}

• arr is really an int* (%rdi can only fit 8 bytes)
• without an explicite size parameter, no way to determine the length of the array

• T A[R][C]
  • 2D array to data type T
  • R rows, C columns
  • What's the array's total size? R*C*sizeof(T)
• single contigious block of memory
• stored in row-major order
  • all elements in row 0, followed by all elements in row 1, etc.
  • address of row i is A + i*(C * sizeof(T))

int sea[4][5] = 
  {{ 9, 8, 1, 9, 5},
   { 9, 8, 1, 0, 5},
   { 9, 8, 1, 0, 3},
   { 9, 8, 1, 1, 5}}

https://docs.google.com/spreadsheets/d/17HGr47X1Q8EqkFmZ4Fv8Y54mO8o-wIPaabQBf_bORZ8/edit?usp=sharing

int* get_sea_zip(int index) {
    return sea[index];
}

get_sea_zip:
        leaq    (%rdi,%rdi,4), %rax  # 5 * index
        leaq    sea(,%rax,4), %rax   # sea + 20 * index
        ret
sea:
        .long   9
        .long   8
        .long   1
        .long   9
        .long   5
        ...

• A[i][j] to access an individual element of a nested array
  • the address works out to A + i*(C*sizeof(T)) + j*sizeof(T) == A + (i*C + j)*sizeof(T)

int get_sea_digit (int index, int digit) {
    return sea[index][digit];
}

get_sea_digit:
        leaq (%rdi,%rdi,4), %rax  # 5 * index
        addl %rax, %rsi           # 5 * index + digit
        movl sea(,%rsi,4), %eax   # *(sea + 4 * (5 * index + digit))

1. CSPP practice problems 3.36 (p. 256) and 3.37 (p. 258)
2. Keep working on Lab 2! The handin script has proved too unstable, so we'll do submissions via Moodle from here on out. For lab 2, upload your solutions.txt to the lab 2 assignment on Moodle.