Arrays and Structs

Created

Arrays

1D Arrays

In C: An array is a sequence of elements where each element is just a variable. All elements will have the same type, called the element type. The number of elements is fixed at the type of the array creation.

  • Access through an integer index: 0 is the first element and 1 is the second.
  • The subscript operator a[i] refers to the element at index i in array a.

The program must be able to determine the array element's address. For an array, the program just needs to know the base element (the address of the first element). After that, all the elements are at a fixed offset from the base address. Thus, the address of any element can be computed from the base address.

  • Address of an element = base address + offset.

At the machiene level, addresses correspond to bytes, so to compute the correct element offset, the array index must be multiplied by the element size in bytes.

Example C program

#include <stdio.h>

int main(void) {
  int arr[3] = { 1, 2, 3 };
  printf("%p\n%p\n%p\n", &arr[0], &arr[1], &arr[2]);
  return 0;
}

Output:

$ gcc arrptr.c 
$ ./a.out 
0x7ffc822662fc 
0x7ffc82266300 
0x7ffc82266304
  • Note that sizeof(int) = 4 and the array elements have addresses which differ by 4.

In x86-64 Assembly, arrays are straightforward if the elements are 1, 2, 4, or 8 bytes in size as it allows indexed/scaled addressing.

  • Any general purpose reigster can store an address (base address or element pointer) or be used as an index.

Pointer Arithmetic

The array/pointer duality: If a is the name fo the array, a can be considered to be the pointer to the first element of the array (the base address).

Pointer identities a[i] is the same thing as *(a+i).

  • Implies that &a[i] means the same thing as (a + i)

In general,

  • p points to an array element
  • p+i points to the element i positions past the one p points to
  • p-i points to the elmenet i positions before the one p points to

Pointer difference Say p and q are pointers, i is an integer, and p+i=q, then it is also true that q-p=i.

ptrdiff_t is a signed type that represents the difference between pointer values.

  • It must be a signed type since the difference could be negative.
  • The type of the pointer affects the result of pointer difference
  • C langauges standared only guarantees pointer difference is meaningful when comparing pointeres from the same chunk of memory (array , malloc'ed buffer, etc.)

Accessing array elements Example

C We want to write a C function to compute the sum of an array of uint32_t elements:

C function prototype: uint32_t sum_elts(uint32_t arr[], unsigned len);

  • Recall that in C, an array parameter is really a pointer to the first element of the argument array

First C approach (indexed version):

uint32_t sum_elts(uint32_t arr[], unsigned len) {
  uint32_t sum = 0;
  for (unsigned i = 0; i < len; i++) {

    sum += arr[i];
  }

return sum; }

Second C approach (element pointer version):

uint32_t sum_elts(uint32_t arr[], unsigned len) {
	uint32_t *p = arr, *end = arr + len;
	uint32_t sum = 0;
	while (p < end) {
		sum += *p;
		p++;
	}
	return sum;
}

Assembly First assembly approach (indexed version):

sum_elts:
    movl $0, %eax // keeps track of sum
    movl $0, %r10d // keeps track of current index

.LsumLoop:
    cmpl %esi, %r10d // is index < n
    jae .sumLoopDone 
    addl (%rdi,%r10,4), %eax
    incl %r10d
    jmp .LsumLoop

.LsumLoopDone:
    ret
  • Initially, %rdi is the base address, and %esi is the number of elements.
  • movl $0, %eax initializes sum in %eax
  • movl $0, %r10d initializes %r10d as index.
  • cmpl %esi, %r10d sees if index < n
    • jae .LsumLoopDone says if it is not, we are done with the loop.
  • addl (%rdi,%r10,4), %eax adds arr[index to sum. Note that %rdi is the base element, %r10 is the index, and the 4 is the scaling factor.
  • incl %r10d increments the index
  • jmp .LsumLoop continues the loop
  • ret ends the program and sum will be %eax

Second assembly apporach (element pointer):

sum_elts:
    movl $0, %eax // keeps track of sum
    leaq (%rdi,%rsi,4), %r10  // sets %r10 as address past the last element

.LsumLoop:
    cmpq %r10, %rdi // has %rdi past the last element
    jae .LsumLoopDone
    
    addl (%rdi), %eax
    addq $4, %rdi // increment the pointer
    jmp .LsumLoop

.LsumLoopDone:
    ret
  • addq $4, %rdi advances to next element.

So what approach should I use?

  • If element size is 1, 2, 4, or 8, then either approach is fine
  • Otherwise, the element pointer approach may be preferable (since indexed/scaled addressing can’t be used as easily)

Multidimensional Arrays

Multidimensional arrays in C are laid out in row-major order - Example 2D array: int grid[3][4] would have 3 rows and 4 columns.

In memory, the elements within each row are sequential in memory. Smaller row indexes are in the lower addresses.

Accessing elements of multidimensional array: A typical loop to iterate over elements of a 2D array:

for (int i = 0; i < NROWS; i++) {
  for (int j = 0; j < NCOLS; j++) {
    /* do something with arr[i][j] */
  }
}

Strategy to access elements:

  • Each iteration of outer loop computes address of first element of row (arr[i][0])
  • The inner loop can then treat arr[i] as a one-dimensional array
  • Various optimizations are possible. For example, loop above accesses elements sequentially in memory, could treat the 2-D array as a 1-D array with NROWS × NCOLS elements

Structs

A struct (a.k.a. “record”) is a heterogenous data type consisting of an arbitrary number of fields with arbitrary types.

To access a filed within a struct instance, you need to know

  • the base address of the struct instance
  • the offset of the field being acessed.

Accessing a field is similar to accessing an array element, except that each field has a specific constant offset known at compile time

Field Alignment

#include <stdio.h>

struct Player {
  int x, y;
  char symbol;
  short health;
};

int main(void) {
  printf("%lu\n", sizeof(struct Player));
  return 0;
}

Would print out

$ gcc structlayout.c 
$ ./a.out  
12
  • It is 12 because the ints are both 4 bytes. char is 1 byte, and then short is 2 bytes, but the compiler must ensure that the memory accesses are properly alligned.
    • e.g., a 4 byte int variable must have its sotrage allocated at an address that is a multiple of 4, so the compiler may add padding bytes.

The compiler may also add padding at the end of the struct to guarantee alignment of all fields.

  • For example, if the struct type has fileds requiring 8 bytes, the struct must be a multiple of 8.

Accessing Structs

Assuming you have the base address of a struct instance in a register, the field ias at a fixed offset from the base address. Specify the offset when making the memory reference.

In C:

struct Player {
  int x, // offset 0
      y; // offset 4 because x takes up 4 bytes
  char symbol; 
  short health;
};

void move_player(struct Player *p, int dx, int dy) {
  p->x += dx;
  p->y += dy;
}

In assembly:

/* Note that first three arguments are in %rdi, %rsi, and %rdx */

#define PLAYER_X_OFFSET 0
#define PLAYER_Y_OFFSET 4

move_player:
    addl %esi, PLAYER_X_OFFSET(%rdi)  /* p->x += dx */
    addl %edx, PLAYER_Y_OFFSET(%rdi)  /* p->y += dy */
    ret
  • Using #define to be an easy reference.

Linked from Computer System Fundamentals