Arrays, matrices and strings in C

Almost every program works on many data of the same type: the samples of a signal, a class’s marks, the pixels of an image, the characters of a message. The array is the structure that holds them in consecutive memory cells, reached by an index. In this lesson we cover one- and multi-dimensional arrays, how to pass them to functions, character strings and the dangers of going out of bounds.

Arrays

#define N 5
int marks[N] = {28, 30, 24, 27, 30};      /* N consecutive integers in memory */

int sum = 0;
for (int i = 0; i < N; i++) {
    sum += marks[i];
}
printf("Average: %.2f\n", (double)sum / N);   /* Average: 27.80 */

• The size must be known and does not change: an array cannot grow (that is what the dynamic memory of the lesson on pointers is for).
• Indices run from 0 to N - 1.
• The elements sit in contiguous cells: the address of marks[i] is that of marks[0] plus i times the size of an int. That is why reaching any element takes the same time, .
• Using a constant (#define N 5) instead of repeating the number 5 everywhere avoids forgetting one when the size changes.

Going out of bounds

C does not check that the index is valid. Writing marks[5] in an array of 5 elements gives no error: it reads or writes the next cell, which belongs to another variable. The result is unpredictable behaviour, which may show up much later in a distant part of the program. It is the cause of buffer overflows, the most exploited security vulnerability in history: an attacker writes past the end of an array and overwrites the return address on the stack, getting their own code executed. The 1988 Morris worm and countless later attacks used exactly this.

The rules of defence: always keep the size next to the array, check indices that come from outside, compile during development with -fsanitize=address, which reports out-of-bounds accesses.

Arrays and functions

An array passed to a function is not copied: the function receives the address of the first element. That is why it must also receive the size, and why it can change the caller’s array.

/* returns the index of the largest value */
int index_of_max(const int v[], int n)
{
    int imax = 0;
    for (int i = 1; i < n; i++) {
        if (v[i] > v[imax]) imax = i;
    }
    return imax;
}

const declares that the function does not change the array: the compiler checks it, and anyone reading the prototype knows at once.

Matrices

A two-dimensional array is an array of rows, stored one after another (row-major order):

double m[3][4];           /* 3 rows, 4 columns */
m[1][2] = 5.0;            /* row 1, column 2 */

/* matrix-vector product: y = A x */
void mat_vec(int r, int c, const double a[r][c], const double x[c], double y[r])
{
    for (int i = 0; i < r; i++) {
        y[i] = 0.0;
        for (int j = 0; j < c; j++) {
            y[i] += a[i][j] * x[j];
        }
    }
}

Walking a matrix row by row (with the column index in the inner loop) is much faster than walking it by columns, because contiguous cells are read and the cache works well: with large matrices the difference can be tenfold.

Strings

In C a string is an array of char ended by the null character '\0' (the number 0). The string "ciao" takes 5 bytes: ‘c’, ‘i’, ‘a’, ‘o’, ‘\0’. The terminator is how functions know where the string ends.

#include <stdio.h>
#include <string.h>

int main(void)
{
    char name[20] = "Ada";               /* room for 19 characters plus the terminator */
    printf("%s has %zu letters\n", name, strlen(name));    /* Ada has 3 letters */

    char greeting[40];
    snprintf(greeting, sizeof greeting, "Hello, %s!", name);   /* never beyond the size */
    printf("%s\n", greeting);

    if (strcmp(name, "Ada") == 0) {      /* strings are compared with strcmp, not == */
        printf("Same name\n");
    }
    return 0;
}

The functions of <string.h> (strlen, strcpy, strcat, strcmp) all rely on the terminator. If it is missing, or the destination is too small, the array bounds are exceeded: strcpy and gets are the historic causes of many buffer overflows. The versions that take the size, such as snprintf, should be preferred. == between two strings compares addresses, not content: for content you need strcmp, which returns 0 if they are equal.

An electronics example: the moving average

To smooth a sensor reading you average the last samples, kept in an array used as a circular buffer: the new sample replaces the oldest, and the index wraps to 0 after the last cell.

#define N 8
static int buffer[N];
static int pos = 0;
static long sum = 0;

int moving_average(int sample)
{
    sum -= buffer[pos];         /* remove the oldest sample */
    buffer[pos] = sample;
    sum += sample;
    pos = (pos + 1) % N;        /* circular index */
    return (int)(sum / N);
}

Keeping the sum up to date, each new sample costs a few operations whatever is: instead of . It is a low-pass FIR filter, like those of the lesson on the Z transform.