The memory table

Why this supplement

This table is my way of explaining variables and pointers to those who have not understood C. Rather than explaining * and & all over again, we write memory down, row by row, and read each expression in the table.

I realised that this was a gap in every C course, including the ones this course is drawn from. They say what a pointer is, and draw it with arrows. But an arrow hides what needs to be understood: a pointer is a variable like any other, stored at an address, and its contents are a number, the address of another variable. Since this course is mine, I can add it.

If chapter 2 seemed clear to you, this supplement is a quick read. If it left you puzzled, start here, then read it again.

Writing memory down

To follow a program that handles pointers, arrows drawn on the board quickly become unreadable. Instead, you can write memory down in a table, one row per variable, with four columns:

To keep things simple, we count addresses from the first variable, which is at address 0, and we store the following ones one after the other, in the order of their declaration. Real addresses are large and change on every run, and the compiler does not always store variables in this order, but that changes nothing in the reasoning: only the gaps between addresses matter. We take the sizes of a 64-bit PC running Linux: char 1 byte, int 4, pointer 8. A pointer starts at an address that is a multiple of 8, which may leave unused bytes before it (alignment, chapter 3).

Then three rules are enough:

• x: find the row named x, and read its * column;
• &x: find the row named x, and read its & column;
• *p: read the contents of p, which is an address, then find the row that has this address in the & column. *p is that row: you read its contents, or write into it.

A pointer, and a pointer to a pointer

int a = 42;
int b = 7;
int *p = &a;
int **pp = &p;

p contains 0, the address of a; pp contains 8, the address of p. Expressions are then read in the table:

An assignment modifies a single cell of the * column: the one designated by what is on the left of the =.

• *p = 5;: p contains 0, we write 5 in the row at address 0. a is 5.
• p = &b;: we write 4, the address of b, in row p. a and b do not change.
• **pp = 9;: pp contains 8, row p; p now contains 4, row b. We write 9 in b.

An array

int t[3] = {10, 20, 30};
int *q = &t[1];

The array takes up three consecutive rows, one per cell. And t is t[0]: the name of the array sits on the row of its first cell, at the same address. So t is the address of that row, &t[0], and *t is t[0] itself. t has no row of its own: it is not a variable that would contain an address, it is another name for the start of the block. That is what distinguishes an array from a pointer: q has its own row, and you can write into it; t has none, and t = q; is rejected.

Only one thing still separates t from t[0]: the size. sizeof t[0] is 4, the size of a cell; sizeof t is 12, the size of the whole block.

Pointer arithmetic is read on the & column: adding 1 to an int * means moving forward one int row, so 4 bytes.

A joke, to finish, which is also a good check. For t an array of integers and i an integer, t[i] is just another way of writing *(t + i): the row at address t + i × 4. Now an addition reads both ways: t + i is i + t. So:

t[i] == *(t + i) == *(i + t) == i[t]

And i[t] compiles, without a single warning, even with -pedantic:

int t[3] = {10, 20, 30};
int i = 2;

printf("%d %d %d %d\n", t[i], *(t + i), *(i + t), i[t]);

30 30 30 30

For the compiler, 2[t] is cell 2 of t. Never write that in a real program; but if you understand why it works, you have understood square brackets.

Passing by address

The table shows why echanger(&x, &y) works and echanger_faux(x, y) does not (chapter 2). At the call, the parameters receive new rows, which contain copies of what was passed. We add them at the end, for the duration of the call:

int x = 0, y = 42;
echanger(&x, &y);   /* void echanger(int *a, int *b) { int c = *a; *a = *b; *b = c; } */

• int c = *a;: a contains 0, row x; c receives 0.
• *a = *b;: b contains 4, row y, which is 42; we write 42 in the row at address 0, x.
• *b = c;: we write 0 in the row at address 4, y.

On return, rows a, b and c disappear, but it is into x and y that we wrote. With echanger_faux(int a, int b), rows a and b would have contained 0 and 42, copies of the values: the function would have swapped them with each other, without ever touching rows 0 and 4.

A string

char s[6] = "salut";
char *c = s + 2;

A char fits in one byte: each row moves forward by 1.

*c is 'l', c[1] is 'u', and c + 1 is 3: for a char *, moving forward one cell means moving forward one byte. printf("%s", c) reads from row 2 up to the '\0', and prints lut.

The size, not the type

Look at the last column of the table: “type (size)”. Of the two, it is the size that does everything. It is the size that gives the address of the next row, that says how far p + 1 moves, that says how many bytes are read behind *p. The type, for its part, is an illusion: it only exists in the source file, for the compiler. In memory, no row carries a label “int” or “float”. There are only bytes, and the program does not know what they represent.

The same bytes

This program copies the bytes of one variable into another, with memcpy, without any conversion, then reads them with another type:

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

/* afficher(p, n) prints the n bytes that start at address p */
void afficher(const void *p, size_t n)
{
    const unsigned char *o = p;
    for (size_t i = 0; i < n; i++)
        printf("%02x ", o[i]);
    printf("\n");
}

int main(void)
{
    int i = 1078530011;
    float f;
    memcpy(&f, &i, sizeof f);        /* copy the 4 bytes, without conversion */

    afficher(&i, sizeof i);
    afficher(&f, sizeof f);
    printf("en int   : %d\n", i);
    printf("en float : %f\n", f);

    int moins_un = -1;
    unsigned int u;
    memcpy(&u, &moins_un, sizeof u);
    afficher(&moins_un, sizeof moins_un);
    printf("en int : %d, en unsigned : %u\n", moins_un, u);

    char mot[4] = {'C', 'a', 'f', 'e'};
    int n;
    memcpy(&n, mot, sizeof n);
    afficher(mot, sizeof mot);
    printf("en int : %d\n", n);
    return 0;
}

db 0f 49 40
db 0f 49 40
en int   : 1078530011
en float : 3.141593
ff ff ff ff
en int : -1, en unsigned : 4294967295
43 61 66 65
en int : 1701208387

The same four bytes db 0f 49 40 are 1078530011 if read as an int, and π if read as a float. ff ff ff ff is −1 or 4,294,967,295. And the word “Cafe” is also an integer. None of these readings is the “real” one: they are four bytes, and it is the type chosen at the moment of reading them that decides what they mean.

In the memory table, you could therefore write the * column in bytes, and it would be correct for all readings at once. We write 42 or 's' there for convenience: that is already a reading.

What the compiler does with the type

The type serves the compiler, during compilation, and nothing else. From it the compiler derives:

• the size: how many bytes to reserve for the variable, and how far to move for p + 1 or t[i];
• the reading: which processor instruction to use, an integer or floating-point addition, a signed or unsigned comparison;
• checks: it rejects some assignments between different types.

Once the program is compiled, nothing of the type remains. The machine code says “read 4 bytes at such an address, add them as integers”. The processor never checks that those bytes were stored as integers.

The sizes to know

If only the size matters, you still need to know it. Yet the C standard does not fix it: it only gives minimums, and each machine chooses. This choice, called the data model, is summed up by the types that are 32 or 64 bits wide: ILP32 (int, long, pointer on 32 bits), LP64 (long, pointer on 64 bits), LLP64 (long long, pointer on 64 bits).

• 32-bit: 32-bit x86 PCs, and 32-bit ARM processors (Raspberry Pi running a 32-bit system, most ARM Cortex-M microcontrollers, older phones).
• 64-bit Linux, macOS: x86-64 PCs running Linux or macOS, and 64-bit ARM (AArch64): Macs with Apple silicon, recent Raspberry Pis running a 64-bit system, today's phones, ARM servers. This is the machine of this course.
• 64-bit Windows: Windows on x86-64 as well as on ARM64. long stays at 4 bytes there, so as not to break old programs: it is the only difference with Linux, and it is enough to crash a program that stores a pointer in a long.
• Arduino Uno: an 8-bit microcontroller. int is only 2 bytes there, and does not go beyond 32,767; double is just another name for float (with avr-gcc, the Arduino's compiler, by default).

What changes nowhere: sizeof(char) is 1 by definition, and it is the unit of sizeof. What the standard guarantees: a short and an int have at least 16 bits, a long at least 32, a long long at least 64, and char ≤ short ≤ int ≤ long ≤ long long. Nothing more.

One last trap: a plain char may be signed or not, depending on the machine. It is on x86 (from −128 to 127), it is not on ARM under Linux (from 0 to 255), except at Apple where it is. A program that stores −1 in a char and compares it with −1 works on a PC, and fails on a Raspberry Pi. So for a byte, write unsigned char (or signed char), never a plain char.

All of this can be checked in one line. On the machine of this course (x86-64, Linux):

#include <stdio.h>
#include <stddef.h>

int main(void)
{
    printf("char %zu short %zu int %zu long %zu long long %zu pointeur %zu size_t %zu float %zu double %zu long double %zu\n",
           sizeof(char), sizeof(short), sizeof(int), sizeof(long), sizeof(long long),
           sizeof(void *), sizeof(size_t), sizeof(float), sizeof(double), sizeof(long double));
    printf("char signe : %d\n", (char)-1 < 0);
    return 0;
}

char 1 short 2 int 4 long 8 long long 8 pointeur 8 size_t 8 float 4 double 8 long double 16
char signe : 1

(long double varies even more than the others: 16 bytes here, 12 on 32-bit x86, 8 on Windows and on Macs with Apple silicon. It is rarely used.)

Two rules follow from this:

• in code, you never write a size in digits: you write sizeof. malloc(n * sizeof *p) is correct everywhere; malloc(n * 4) is only correct where an int is 4 bytes;
• when the size really matters, for a file format, a network protocol, a hardware register, you use the types of stdint.h, whose size is in their name: int8_t, uint16_t, int32_t, uint64_t… A uint32_t is 32 bits on every machine. And to store an address in an integer, there is uintptr_t, not long.

Rigid and permissive at once

C is said to be very permissive. It is also said to be rigid about types. Both are true, and that is what surprises people:

#include <stdio.h>

int main(void)
{
    double d = 3.99;
    int i = d;          /* permissive: truncated to 3, without a word */
    int *p = &i;
    double *q = p;      /* rigid: incompatible pointer types */

    printf("%d %p\n", i, (void *)q);
    return 0;
}

$ gcc -std=c11 -Wall -Wextra -Werror rigide.c
rigide.c:8:17: error: initialization of 'double *' from incompatible pointer type 'int *' [-Werror=incompatible-pointer-types]

Turning 3.99 into 3, and losing information, bothers nobody: even -Wall -Wextra says nothing, you have to add -Wconversion. But storing the address of an int in a pointer to double, which loses nothing at all, is rejected.

And this rigidity stops at void *, the “untyped” pointer: you can store any address in it, and take it out into any pointer, without conversion or warning, even with -Wconversion -Werror:

int i = 3;
void *v = &i;
double *q = v;      /* accepted without a word */

The check is on the labels the programmer wrote, not on the bytes. As soon as the label is removed, there is nothing left to check.

We get along very well without it

In chapter 2, echanger only swapped ints. So would we need one function per type? No: to swap two variables, it is enough to know where they are and how many bytes they take up.

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

/* echanger(a, b, taille) swaps the two blocks of taille bytes pointed to by a and b */
void echanger(void *a, void *b, size_t taille)
{
    unsigned char c[taille];
    memcpy(c, a, taille);
    memcpy(a, b, taille);
    memcpy(b, c, taille);
}

struct point { double x, y; };

int main(void)
{
    int i = 1, j = 2;
    double x = 1.5, y = 2.5;
    struct point p = {0, 0}, q = {3, 4};
    char s[8] = "bonjour", t[8] = "au revo";

    echanger(&i, &j, sizeof i);
    echanger(&x, &y, sizeof x);
    echanger(&p, &q, sizeof p);
    echanger(s, t, sizeof s);
    printf("%d %d | %g %g | (%g, %g) (%g, %g) | %s %s\n",
           i, j, x, y, p.x, p.y, q.x, q.y, s, t);
    return 0;
}

2 1 | 2.5 1.5 | (3, 4) (0, 0) | au revo bonjour

A single function swaps integers, floats, structures and strings. It knows none of these types: it receives two addresses and a size, and moves bytes. (The array c is a variable-length array, on the stack: it is fine for ordinary variables, not for blocks of several megabytes.)

The standard library is written this way. Look at the signatures of its most used functions: not a single type, only void * addresses and size_t sizes.

void  *malloc(size_t taille);
void  *memcpy(void *dest, const void *src, size_t n);
void   qsort(void *base, size_t nombre, size_t taille,
             int (*comparer)(const void *, const void *));
size_t fwrite(const void *p, size_t taille, size_t nombre, FILE *f);

malloc does not know what will be stored in the block, only its size. qsort sorts an array of anything: it only needs to know where it starts, how many cells it has, and the size of a cell; the only thing it cannot do, comparing two cells, is passed to it as a function. fwrite writes bytes into a file, whatever they are.

The limit of the illusion

There is a way of rereading bytes with another type that seems more direct than memcpy:

int i = 1078530011;
float f = *(float *)&i;     /* do not do this */

It compiles, and often prints 3.141593. But the standard forbids it: it is undefined behaviour. The compiler is allowed to assume that an int * and a float * never designate the same bytes (this is the strict aliasing rule), and to optimise accordingly: with optimisation, the resulting program may no longer do what you wrote. It is the only place where the type, which no longer exists at run time, takes its revenge during compilation.

Two ways of doing it are safe, and they are enough:

• copy the bytes with memcpy, as above. With optimisation (-O2), the compiler recognises it and calls no function: the copy becomes a single instruction;
• read the bytes one by one with an unsigned char *, like afficher. A character pointer is allowed to designate anything: it is the official way of seeing memory as a sequence of bytes.