50 Serialisation — values in memory as an agreed sequence of bytes
What to know first
Looking back
Chapter 48 gave four reasons not to send a struct out with a single fwrite, and the cure: write the fields one at a time in a fixed order. If the cure is that simple, why does serialisation get a chapter of its own?
A. Because the cure is simple but the promises it has to keep are many. The function that writes seven bytes of fields is ten lines long; the party at the other end of those bytes is a program someone else wrote, or a later version of this one, or now and then someone who means harm and crafts the input by hand. The hard part is not how to write the bytes but what the bytes promise. This chapter is about that promise — what must be decided, what structure keeps it, and what went wrong when it was not kept.
The need for this chapter, and its context
By the end of this chapter
The questions this chapter answers
- There is a version number; why the tags as well? Why not read according to the version number alone?
- There is a saying: “be conservative in what you send, liberal in what you accept”. Should the reader not be liberal?
50.1 What serialisation is — sending a value outside#
Serialisation turns a value in memory into a sequence of bytes agreed with the outside world. The reverse, reading the bytes and rebuilding the value, is deserialisation. “Marshalling” and “encoding” are used for the same job.
A value in memory is already made of bytes. It still has to be converted, because those bytes are a promise made by this program, this compiler and this machine only. The C standard promises little about the shape of a struct.
| Promised | Not promised |
|---|---|
| Member addresses increase in declaration order (C23 6.7.3.2p17) | How many bytes of padding sit between members |
| There is no padding before the first member (same clause) | The value of padding bytes — unspecified each time a value is stored (6.2.6.1p6) |
| A pointer to a struct points to its first member | The size of int, long and pointers; the byte order |
Table 50.1 — What the standard does and does not promise about a struct in memory
Everything in the right-hand column is up to the implementation. So “send out my machine’s memory as it is” means promising the implementation’s private arrangements to the outside world. Serialisation breaks that link — the bytes that go out are decided by a format, not by the implementation.
50.1.1 Four kinds of reader#
List who receives the bytes, and it becomes clear why serialisation cannot be avoided.
| Reader | Example | What may differ |
|---|---|---|
| Another machine | a server across the network, a sensor, a phone | byte order, type sizes, alignment, language |
| Another process | a different program on the same machine | compiler, compiler options, address space |
| A later version of us | today’s version reads the file saved yesterday | members added to or removed from the struct |
| A hostile party | a hand-made file, a forged packet | everything — it has no reason to follow the rules |
Table 50.2 — Who receives the bytes, and how they may differ from us
The third row is the one people forget. Saving to a file is serialisation too — it is a message to your future self. And the fourth row covers the other three. With only readers who keep to the format, serialisation is a question of correctness; with even one reader who does not, it becomes a question of security.
50.1.2 Pointers cannot leave the process#
One row has to be added to the table of problems with writing a struct out whole in chapter 48. A struct with a pointer in it is even worse to write whole. A pointer’s value means something only in this process’s address space. In another process, or in the same program started again on another day, that number points at nothing (chapter 10).
So serialisation turns references into numbers. Instead of “the next node is at address 0x7ffd…” it writes “the third record of this file”, or “byte 120 of this sequence”. A number means something outside as well. The reader turns the number back into a pointer, and checking that the number is in range at that moment is the reader’s job. Skip that check and an out-of-range number is followed past the end — the kind the “Security” section below calls “reading past the end”, which the cursor blocks.
50.2 Where serialisation can be avoided, and the price#
Serialisation costs something: the time to copy values one at a time, and people’s time to define a format and keep to it. So asking whether it can be avoided is fair. The answer is “in narrow places, yes — and when you avoid it, know the price”.
| Where | How it is avoided | The price |
|---|---|---|
| Inside one process (between threads) | pass the value as it is — there is nothing to serialise | synchronisation (Part XII) |
| Between processes on one machine | put a struct whose memory layout has been made the format in shared memory | the build must check that both sides use the same layout |
| Large data that is mostly read | a “zero-copy format”: accessors that read the bytes in place without copying them | the format is hard to change; it is easy to skip validating the input |
| Data people read and edit | a text format (JSON and the like) — chapter 110 | size and parsing cost |
Table 50.3 — Ways of avoiding serialisation, and what they cost
50.2.1 Making the memory layout the format#
To do the second row honestly, the memory layout itself has to become the format. That means checking for yourself everything the standard does not promise (the right-hand column of the first table in this chapter). Use fixed-width types only, put the widest members first so that no padding creeps in, and nail the result down with static_assert.
examples-en/serialization/wire.c
/* Skipping serialisation honestly: when the in-memory layout *is* the format.
Fixed-width members, widest first, no hidden padding, offsets nailed down by
static_assert --- so a different compiler or option stops the build instead of
silently writing different bytes. Byte order is still the machine's: check it too. */
#include <stdbit.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
struct wire_header { /* shared between two processes on the same machine */
uint64_t sequence;
uint32_t length;
uint16_t kind;
uint8_t flags;
uint8_t version;
};
static_assert(sizeof(struct wire_header) == 16, "layout changed");
static_assert(offsetof(struct wire_header, length) == 8);
static_assert(offsetof(struct wire_header, kind) == 12);
static_assert(offsetof(struct wire_header, flags) == 14);
static_assert(offsetof(struct wire_header, version) == 15);
static_assert(__STDC_ENDIAN_NATIVE__ == __STDC_ENDIAN_LITTLE__,
"this format is little endian; a big-endian build must convert");
struct careless { /* the same members in a careless order */
uint8_t flags;
uint64_t sequence;
uint16_t kind;
uint32_t length;
uint8_t version;
};
int main(void)
{
printf("wire_header: %zu bytes, no padding (8 + 4 + 2 + 1 + 1)\n",
sizeof(struct wire_header));
printf("careless : %zu bytes for the same 16 bytes of members\n",
sizeof(struct careless));
printf(" offsets: flags %zu, sequence %zu, kind %zu, length %zu, version %zu\n",
offsetof(struct careless, flags), offsetof(struct careless, sequence),
offsetof(struct careless, kind), offsetof(struct careless, length),
offsetof(struct careless, version));
return 0;
}
Output
wire_header: 16 bytes, no padding (8 + 4 + 2 + 1 + 1)
careless : 32 bytes for the same 16 bytes of members
offsets: flags 0, sequence 8, kind 16, length 20, version 24
The six static_assert lines are the point of the example. If another compiler or another option changes the layout, the build stops instead of the program quietly writing different bytes. The last static_assert pins down the byte order too — C23′s <stdbit.h> provides __STDC_ENDIAN_NATIVE__, so “is this machine little endian?” is asked at compile time (chapter 53).
careless, with the same members in any old order, spends 32 bytes on 16 bytes’ worth of members. The moment the layout becomes the format, the order of the members becomes part of the format.
A common misconception. “I checked the size with static_assert, so the bytes are now the same everywhere”
50.2.2 Zero-copy formats — reading without copying#
The “zero-copy format” in the third row of the table of ways to avoid serialisation does not move the bytes into values. It has accessor functions that work out a place inside the bytes and read straight from there: “the four bytes from byte 120, read little endian, are the score”. That helps when a large file must be opened and only a few of its fields read. FlatBuffers and Cap’n Proto are known as formats that took this path — this book only names them.
The price is plain. With no copying step, no validating step appears by itself either. Unless every accessor checks “is this place inside the bytes?”, one forged offset reads outside them. Whatever is saved on copying has to be spent on tighter checking.
50.3 Techniques — cursors, sticky errors, fixed widths#
The encode in chapter 48 wrote into a large array, adding offsets as it went. It was short because it trusted the array to be big enough. Serialisation code in practice turns that trust into structure.
50.3.1 Cursors — a struct that carries the room left#
Give the writing side and the reading side a cursor each. A cursor ties together the start of the buffer, its size and the current position. Every put_… and get_… function takes a cursor and checks the room left first.
examples-en/serialization/cursor.c
/* A writing cursor and a reading cursor with a sticky error flag.
Every put/get checks the room left; once a check fails the cursor turns
"bad" and every later call does nothing. The caller checks once, at the end. */
#include <stdint.h>
#include <stdio.h>
#include <string.h>
struct wcur { unsigned char *p; size_t cap, len; bool bad; };
struct rcur { const unsigned char *p; size_t len, pos; bool bad; };
static void put_bytes(struct wcur *w, const void *src, size_t n)
{
if (w->bad || n > w->cap - w->len) { w->bad = true; return; }
memcpy(w->p + w->len, src, n);
w->len += n;
}
static void put_u8(struct wcur *w, uint8_t v) { put_bytes(w, &v, 1); }
static void put_u16le(struct wcur *w, uint16_t v)
{
unsigned char b[2] = { (unsigned char)v, (unsigned char)(v >> 8) };
put_bytes(w, b, 2);
}
static void put_u32le(struct wcur *w, uint32_t v)
{
unsigned char b[4] = { (unsigned char)v, (unsigned char)(v >> 8),
(unsigned char)(v >> 16), (unsigned char)(v >> 24) };
put_bytes(w, b, 4);
}
static const unsigned char *take(struct rcur *r, size_t n)
{
if (r->bad || n > r->len - r->pos) { r->bad = true; return nullptr; }
const unsigned char *at = r->p + r->pos;
r->pos += n;
return at;
}
static uint8_t get_u8(struct rcur *r)
{ const unsigned char *b = take(r, 1); return b ? b[0] : 0; }
static uint16_t get_u16le(struct rcur *r)
{ const unsigned char *b = take(r, 2); return b ? (uint16_t)(b[0] | b[1] << 8) : 0; }
static uint32_t get_u32le(struct rcur *r)
{
const unsigned char *b = take(r, 4);
return b ? (uint32_t)b[0] | (uint32_t)b[1] << 8
| (uint32_t)b[2] << 16 | (uint32_t)b[3] << 24 : 0;
}
struct player { uint32_t id; uint16_t level; uint8_t name_len; char name[32]; };
static void encode(struct wcur *w, const struct player *pl)
{
put_u32le(w, pl->id);
put_u16le(w, pl->level);
put_u8(w, pl->name_len); /* the length goes first */
put_bytes(w, pl->name, pl->name_len);
}
static bool decode(struct rcur *r, struct player *pl)
{
pl->id = get_u32le(r);
pl->level = get_u16le(r);
pl->name_len = get_u8(r);
if (pl->name_len >= sizeof pl->name) r->bad = true; /* the format's own limit */
const unsigned char *s = take(r, r->bad ? 0 : pl->name_len);
if (r->bad) return false; /* one check, after all the reads */
memcpy(pl->name, s, pl->name_len);
pl->name[pl->name_len] = '\0';
return true;
}
int main(void)
{
struct player in = { .id = 0x01020304, .level = 7, .name_len = 5, .name = "alice" };
unsigned char buf[64];
struct wcur w = { .p = buf, .cap = sizeof buf };
encode(&w, &in);
printf("encoded %zu bytes:", w.len);
for (size_t i = 0; i < w.len; i++) printf(" %02X", buf[i]);
printf("\n (sizeof(struct player) is %zu ---"
" the bytes are the format, not the struct)\n\n",
sizeof(struct player));
struct player out;
struct rcur r = { .p = buf, .len = w.len };
printf("whole message : %s", decode(&r, &out) ? "ok" : "rejected");
printf(" -> id %08X, level %u, name \"%s\"\n",
(unsigned)out.id, out.level, out.name);
r = (struct rcur){ .p = buf, .len = w.len - 2 }; /* cut short */
printf("two bytes short : %s\n", decode(&r, &out) ? "ok" : "rejected");
unsigned char lie[64];
memcpy(lie, buf, w.len);
lie[6] = 200; /* the length lies */
r = (struct rcur){ .p = lie, .len = w.len };
printf("length says 200 : %s\n", decode(&r, &out) ? "ok" : "rejected");
unsigned char tiny[8];
w = (struct wcur){ .p = tiny, .cap = sizeof tiny };
encode(&w, &in);
printf("8-byte buffer : writer is %s after %zu bytes\n",
w.bad ? "bad" : "fine", w.len);
return 0;
}
Output
encoded 12 bytes: 04 03 02 01 07 00 05 61 6C 69 63 65
(sizeof(struct player) is 40 --- the bytes are the format, not the struct)
whole message : ok -> id 01020304, level 7, name "alice"
two bytes short : rejected
length says 200 : rejected
8-byte buffer : writer is bad after 7 bytes
The cursor in cursor.c rests on three ideas.
- All the range checks are in two functions. Only
put_bytesandtakelook at the range.put_u32leandget_u16lejust call them. Write the range check in every function separately and one day one of them is missing. - The error is sticky. Once the range is exceeded the cursor’s
badis set, and every later call does nothing and returns 0. Sodecodedoes not check after each field; it looks atr->badonce, at the end. Fewer places where a check can be forgotten is the point of the design (a sticky error). - Compare by subtraction, not addition. The range check is
n > w->cap - w->len, notw->len + n > w->cap.lenhas been kept from exceedingcap, so the subtraction cannot wrap; the addition can wrap whennis very large, become a small number — and pass the check.
The last three lines of the output are what the cursor stopped: a message two bytes short, a message whose length claims 200, and a buffer of only 8 bytes. All three stopped before reading or writing past the end.
50.3.2 Fixed widths and shifts#
Fields are written as fixed-width types (chapter 27). Byte order is written with shifts — (unsigned char)(v >> 8) is “the second byte of v” whatever the machine’s endianness. Shifts and masks are covered properly in chapter 53 all that is used here is “take one byte out, and put one byte back in its place”.
The reading side widens the byte to uint32_t before shifting it. b[3] << 24 shifts b[3] after it has been promoted to int, so when b[3] is 0x80 or more it runs into the sign bit and overflows (chapter 30). That is why it is written (uint32_t)b[3] << 24.
50.3.3 Variable-length integers — small numbers, few bytes#
Fixed widths are simple but wasteful: “length 3” takes four bytes. So many formats use variable-length integers (varints). Each byte carries seven bits of the value in its low bits, and its top bit says “another byte follows”. The low seven-bit group comes first. The LEB128 of DWARF debugging information and the varint of Protocol Buffers have this shape.1
examples-en/serialization/varint.c
/* Variable-length integers (base-128, "LEB128"/protobuf style) and zigzag.
Seven bits of payload per byte, low group first; the top bit says
"another byte follows". Small numbers take few bytes. */
#include <stdint.h>
#include <stdio.h>
static size_t put_varint(unsigned char *out, uint64_t v)
{
size_t n = 0;
do {
unsigned char b = v & 0x7F;
v >>= 7;
out[n++] = b | (v ? 0x80 : 0); /* more to come? set the top bit */
} while (v);
return n;
}
/* Returns the number of bytes used, or 0 if the input is cut short or too long. */
static size_t get_varint(const unsigned char *in, size_t len, uint64_t *v)
{
uint64_t x = 0;
for (size_t i = 0; i < len && i < 10; i++) { /* 64 bits need at most 10 */
uint64_t part = in[i] & 0x7F;
if (i == 9 && part > 1) return 0; /* would not fit in 64 bits */
x |= part << (7 * i);
if (!(in[i] & 0x80)) { *v = x; return i + 1; }
}
return 0;
}
/* zigzag: 0,-1,1,-2,2 ... -> 0,1,2,3,4 ... so small negatives stay small */
/* no right shift of a negative value: that is implementation-defined */
static uint64_t zigzag(int64_t n)
{ uint64_t u = (uint64_t)n; return (u << 1) ^ (0 - (u >> 63)); }
static int64_t unzigzag(uint64_t u) { return (int64_t)(u >> 1) ^ -(int64_t)(u & 1); }
static void show(const char *label, uint64_t v)
{
unsigned char b[10];
size_t n = put_varint(b, v);
printf(" %-22s ->", label);
for (size_t i = 0; i < n; i++) printf(" %02X", b[i]);
printf(" (%zu byte%s)\n", n, n == 1 ? "" : "s");
}
int main(void)
{
puts("[varint]");
show("1", 1);
show("127", 127);
show("128", 128);
show("150", 150);
show("300", 300);
show("UINT32_MAX", UINT32_MAX);
show("-1 as uint64_t", (uint64_t)-1);
puts("\n[zigzag, then varint]");
for (int64_t n = -2; n <= 2; n++) {
char label[32];
snprintf(label, sizeof label, "%lld -> %llu", (long long)n,
(unsigned long long)zigzag(n));
show(label, zigzag(n));
}
puts("\n[reading back]");
unsigned char good[] = { 0xAC, 0x02 };
unsigned char cut[] = { 0xAC }; /* "more follows", then nothing */
unsigned char runaway[11] = { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x01 };
uint64_t v = 0;
size_t n = get_varint(good, sizeof good, &v);
printf(" AC 02 -> %llu (%zu bytes)\n", (unsigned long long)v, n);
printf(" AC -> %s\n",
get_varint(cut, sizeof cut, &v) ? "ok" : "rejected: cut short");
printf(" FF x10, 01 -> %s\n",
get_varint(runaway, sizeof runaway, &v) ? "ok" : "rejected: too long");
printf(" unzigzag(3) -> %lld\n", (long long)unzigzag(3));
return 0;
}
Output
[varint]
1 -> 01 (1 byte)
127 -> 7F (1 byte)
128 -> 80 01 (2 bytes)
150 -> 96 01 (2 bytes)
300 -> AC 02 (2 bytes)
UINT32_MAX -> FF FF FF FF 0F (5 bytes)
-1 as uint64_t -> FF FF FF FF FF FF FF FF FF 01 (10 bytes)
[zigzag, then varint]
-2 -> 3 -> 03 (1 byte)
-1 -> 1 -> 01 (1 byte)
0 -> 0 -> 00 (1 byte)
1 -> 2 -> 02 (1 byte)
2 -> 4 -> 04 (1 byte)
[reading back]
AC 02 -> 300 (2 bytes)
AC -> rejected: cut short
FF x10, 01 -> rejected: too long
unzigzag(3) -> -2
Up to 127 takes one byte; from 128 on, two. But -1 taken as an unsigned 64-bit value needs ten bytes — all its bits are 1. So values that are often negative get a zigzag step first. Mapping 0, −1, 1, −2, 2 to 0, 1, 2, 3, 4 makes numbers that are small in magnitude short, whatever their sign.
The example’s zigzag does not shift a negative number right; it converts to unsigned first and takes out the top bit. Shifting a negative value right is implementation-defined (chapter 29). And get_varint on the reading side stops at ten bytes. It does not let an input that keeps “another byte follows” switched on run the loop for ever or shift past 64 bits. Variable length means the reader does not know the length in advance, so the reader has to set the limit.
50.3.4 Tag, length, value — skipping what you do not know#
Formats change from version to version. Members are added and, one day, removed. The classic way to make an old reader survive a file from a new version is tag-length-value (TLV). Every field carries “what it is” (the tag), “how many bytes” (the length) and the value. With the length there, an unknown tag can be skipped by that many bytes.
examples-en/serialization/tlv.c
/* A small file format: magic, version, then tag-length-value fields.
A reader built for version 1 meets a file written by version 2 and
skips the field it has never heard of --- because every field says how long it is. */
#include <stdint.h>
#include <stdio.h>
#include <string.h>
enum { TAG_NAME = 1, TAG_SCORE = 2, TAG_COLOUR = 3 /* added in version 2 */ };
enum { MAX_FIELD = 64 }; /* the format promises: no field is longer */
static const unsigned char magic[4] = { 'P', 'C', 'B', 0x1A };
static size_t put_field(unsigned char *out, uint8_t tag, const void *v, uint8_t len)
{
out[0] = tag; out[1] = len;
memcpy(out + 2, v, len);
return 2u + len;
}
static size_t write_v2(unsigned char *out)
{
size_t n = 0;
memcpy(out, magic, 4); n += 4;
out[n++] = 2; /* version */
n += put_field(out + n, TAG_NAME, "alice", 5);
n += put_field(out + n, TAG_COLOUR, "\xFF\x80\x00", 3); /* new in v2 */
unsigned char score[4] = { 0x39, 0x05, 0, 0 }; /* 1337, little endian */
n += put_field(out + n, TAG_SCORE, score, 4);
return n;
}
/* The version-1 reader: knows NAME and SCORE only. */
static int read_v1(const unsigned char *in, size_t len)
{
if (len < 5 || memcmp(in, magic, 4) != 0) { puts(" not our file"); return 0; }
unsigned version = in[4];
printf(" version %u file\n", version);
size_t pos = 5;
while (pos < len) {
if (len - pos < 2) { puts(" rejected: field header cut short"); return 0; }
unsigned tag = in[pos], flen = in[pos + 1];
if (flen > MAX_FIELD)
{ printf(" rejected: field of %u bytes\n", flen); return 0; }
if (flen > len - pos - 2)
{ puts(" rejected: field runs past the end"); return 0; }
const unsigned char *v = in + pos + 2;
switch (tag) {
case TAG_NAME:
printf(" name = %.*s\n", (int)flen, (const char *)v);
break;
case TAG_SCORE:
if (flen != 4) { puts(" rejected: score is not 4 bytes"); return 0; }
printf(" score = %u\n", (unsigned)(v[0] | v[1] << 8
| (uint32_t)v[2] << 16 | (uint32_t)v[3] << 24));
break;
default:
printf(" (skipped unknown tag %u, %u bytes)\n", tag, flen);
}
pos += 2u + flen;
}
return 1;
}
int main(void)
{
unsigned char file[128];
size_t n = write_v2(file);
printf("[a version-2 file, %zu bytes, read by a version-1 reader]\n", n);
read_v1(file, n);
puts("\n[the same file with the last field's length raised to 9]");
file[n - 5] = 9;
read_v1(file, n);
puts("\n[a field that claims 200 bytes]");
file[6] = 200;
read_v1(file, n);
return 0;
}
Output
[a version-2 file, 23 bytes, read by a version-1 reader]
version 2 file
name = alice
(skipped unknown tag 3, 3 bytes)
score = 1337
[the same file with the last field's length raised to 9]
version 2 file
name = alice
(skipped unknown tag 3, 3 bytes)
rejected: field runs past the end
[a field that claims 200 bytes]
version 2 file
rejected: field of 200 bytes
Version 2 added a “colour” field, and the version-1 reader skipped it and still read the name and score correctly. The two experiments after it show the other side of the same structure. Having a length means the length can lie. So the reader checks it twice — against the limit the format sets (MAX_FIELD) and against the bytes that are left.
Q. There is a version number; why the tags as well? Why not read according to the version number alone?
A. They do different jobs. A version number is for a change of meaning — if the unit of a field changed from milliseconds to microseconds, an old reader should not read that file. Tags are for additions — a new field is something an old reader can do without, so it can be skipped. So the usual design has both, with the version split into “major” and “minor”: a different major version means the reader refuses the file, a different minor version means it skips the tags it does not know. The example’s version-1 reader only printed the version number — in practice it should check the major version.
50.3.5 Sending floating-point values#
Shifts cannot be used on floating-point values. The usual way is to memcpy the float into a uint32_t and send the integer — reading the same bits as another type, within the contract (chapters 49 and 57). The reader does the reverse. This rests on the assumption that both sides use the same floating-point format. In C23, an implementation that follows IEC 60559 (IEEE 754) binary floating point defines __STDC_IEC_60559_BFP__ (chapter 54). The honest thing is to write “IEEE 754 binary32, little endian” in the format’s documentation and make builds without that macro stop.
50.4 Packing and padding — do not fit the struct to the format#
Chapter 48 showed __attribute__((packed)) and #pragma pack. Neither is standard; both remove padding so that a struct fits a format. One more thing has to be said, about the alignment of packed members.
A member of a packed struct may be misaligned. When it is read by name, the compiler knows it is misaligned and emits careful instructions; but take the member’s address and pass it on, and the receiver knows nothing of that. A function that receives a uint32_t * trusts it to be aligned and reads it — on a machine strict about alignment it stops there, and on one that is not it is still outside the contract (chapter 38). GCC and Clang warn about this with -Waddress-of-packed-member (GCC has it on by default since version 9).
Counter-example. Laying a packed struct “over” a packet to read it
struct __attribute__((packed)) hdr { uint8_t kind; uint32_t len; };
const struct hdr *h = (const struct hdr *)buf; /* lay it over the bytes received */
if (h->len > room) ...Three things are wrong at once. Reading buf as another type falls foul of the effective type rules (chapter 57), the byte order is still this machine’s, and h->len has been read before anyone looked at whether the packet is shorter than sizeof(struct hdr). Read the fields one at a time through a cursor and all three problems go away together. “Lay a struct over the packet” is the commonest way C code parses formats, but it is not a way that can be written honestly in standard C.
So this book’s advice is simple: read and write formats as bytes. Keep the struct in whatever shape suits it in memory, and move between the two with a cursor. Leave packed for memory that really has that shape, such as hardware registers whose byte layout is fixed from outside (chapter 114).
50.5 Byte-order conversion — three ways#
There are three ways to change byte order.
| Method | Where it works | Character |
|---|---|---|
| Shifts, one byte at a time | anywhere in standard C | never asks the machine’s endianness. This book’s advice |
memcpy + a byte-reversing built-in | GCC/Clang __builtin_bswap32, MSVC _byteswap_ulong | __STDC_ENDIAN_NATIVE__ decides whether to reverse |
htonl, ntohl and friends | POSIX and Windows socket APIs | network order (big endian) only, 16 and 32 bits only. Not standard C |
Table 50.4 — Three ways to change byte order
C23′s <stdbit.h> gives only three macros for asking about byte order — __STDC_ENDIAN_LITTLE__, __STDC_ENDIAN_BIG__ and __STDC_ENDIAN_NATIVE__ (7.18.2). There is no function for changing it. And the standard records that an order that is neither little nor big may exist — then __STDC_ENDIAN_NATIVE__ differs from both. Write “if not little, then big” and you miss that case.
Is the code that assembles a value byte by byte with shifts slow, then? The machine instructions it compiles to can be counted.
examples-en/serialization/bswap/load.c
/* Two ways to read a 32-bit big-endian value from bytes.
Neither gives a result that depends on the machine's byte order; (2) handles only
little- and big-endian machines and stops compiling on any other. */
#include <stdint.h>
#include <string.h>
/* (1) shifts: portable C, nothing outside the standard */
uint32_t get_u32be_shift(const unsigned char *p)
{
return (uint32_t)p[0] << 24 | (uint32_t)p[1] << 16
| (uint32_t)p[2] << 8 | (uint32_t)p[3];
}
/* (2) memcpy into a uint32_t, then reverse the bytes if this machine is little endian.
__builtin_bswap32 is a GCC/Clang extension; MSVC spells it _byteswap_ulong. */
#include <stdbit.h>
uint32_t get_u32be_bswap(const unsigned char *p)
{
uint32_t v;
memcpy(&v, p, sizeof v);
#if __STDC_ENDIAN_NATIVE__ == __STDC_ENDIAN_LITTLE__
v = __builtin_bswap32(v);
#elif __STDC_ENDIAN_NATIVE__ != __STDC_ENDIAN_BIG__
#error "byte order is neither little nor big endian"
#endif
return v;
}
/* little endian by shifts --- on a little-endian machine this is a plain load */
uint32_t get_u32le_shift(const unsigned char *p)
{
return (uint32_t)p[0] | (uint32_t)p[1] << 8
| (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24;
}
Output
-O0 get_u32be_shift 27 instructions
-O0 get_u32be_bswap 12 instructions (uses bswap)
-O0 get_u32le_shift 26 instructions
-O2 get_u32be_shift 3 instructions (uses bswap)
-O2 get_u32be_bswap 3 instructions (uses bswap)
-O2 get_u32le_shift 2 instructions
-O2 -march=x86-64-v3 get_u32be_shift 2 instructions (uses movbe)
-O2 -march=x86-64-v3 get_u32be_bswap 2 instructions (uses movbe)
-O2 -march=x86-64-v3 get_u32le_shift 2 instructions
Platform note. What was counted on this machine
Without optimisation (-O0) the shift versions are twenty-odd instructions. At -O2 both compilers turn get_u32be_shift, the big-endian reader, into one load and a byte reversal, three instructions — the same as the version written by hand with __builtin_bswap32. Aim at a machine with the MOVBE instruction (load and reverse in one), as -march=x86-64-v3 does, and it is two. get_u32le_shift, which reads little endian on a little-endian machine, is just a load.
The conclusion is “write the shifts and leave the rest to the compiler”: you lose no portability and get the same machine code. But that holds with optimisation on — do not judge format code by the speed of a debug build.
50.6 Buffer structures and their optimisation#
Serialised bytes gather somewhere before they leave. The shape of that “somewhere” often decides the speed.
50.6.1 Gather, then send once#
Call send or write for every field, and the number of bytes is the same but the number of calls is the number of fields. Each such call usually crosses into the operating system’s kernel (chapter 10) and costs far more than moving a few bytes.
examples-en/serialization/batch.c
/* Writing field by field versus gathering into one buffer first.
`sink` stands in for whatever is expensive per call --- send() on a socket,
write() on a file, a USB transfer. It only counts. */
#include <stdint.h>
#include <stdio.h>
#include <string.h>
static unsigned long calls, bytes;
static void sink(const void *p, size_t n) { (void)p; calls++; bytes += n; }
struct point { int32_t x, y; uint16_t id; };
static void put_le(unsigned char *b, uint32_t v, int n)
{ for (int i = 0; i < n; i++) b[i] = (unsigned char)(v >> (8 * i)); }
/* (1) every field goes out on its own */
static void send_each(const struct point *pts, size_t count)
{
unsigned char b[4];
for (size_t i = 0; i < count; i++) {
put_le(b, (uint32_t)pts[i].x, 4); sink(b, 4);
put_le(b, (uint32_t)pts[i].y, 4); sink(b, 4);
put_le(b, pts[i].id, 2); sink(b, 2);
}
}
/* (2) fill a buffer, send it when it is full, and once more at the end */
static void send_batched(const struct point *pts, size_t count)
{
unsigned char buf[4096];
size_t used = 0;
for (size_t i = 0; i < count; i++) {
if (sizeof buf - used < 10) { sink(buf, used); used = 0; }
put_le(buf + used, (uint32_t)pts[i].x, 4);
put_le(buf + used + 4, (uint32_t)pts[i].y, 4);
put_le(buf + used + 8, pts[i].id, 2);
used += 10;
}
if (used) sink(buf, used);
}
int main(void)
{
static struct point pts[10000];
for (size_t i = 0; i < 10000; i++)
pts[i] = (struct point){ (int32_t)i, -(int32_t)i, (uint16_t)i };
send_each(pts, 10000);
unsigned long each = calls;
printf("field by field : %6lu calls, %lu bytes\n", calls, bytes);
calls = bytes = 0;
send_batched(pts, 10000);
printf("4 KiB buffer : %6lu calls, %lu bytes\n", calls, bytes);
printf("\nsame bytes, one call where there were %lu.\n", each / calls);
puts("If one call costs a trip into the kernel, that is where the time goes.");
puts("stdio's FILE does this for you; a raw socket does not.");
return 0;
}
Output
field by field : 30000 calls, 100000 bytes
4 KiB buffer : 25 calls, 100000 bytes
same bytes, one call where there were 1200.
If one call costs a trip into the kernel, that is where the time goes.
stdio's FILE does this for you; a raw socket does not.
The same 100,000 bytes, sent in 30,000 pieces or in 25. Standard I/O through a FILE does this already — fwrite gathers into an internal buffer and sends it when it is full (chapter 78). Where there is no such layer, as with a socket, you gather yourself.
50.6.2 A growing buffer#
When the size of the output is not known in advance, use a growing buffer. When it runs out, double the capacity — grow it one byte at a time and realloc copies every time, making the whole thing quadratic; double it and the copying per byte averages out to a constant. The capacity calculation checks for overflow (ckd_mul, chapter 96). And remember that when realloc fails the old buffer stays as it was (chapter 57) — p = realloc(p, n) loses the old buffer on failure.
Better still if the size can be known in advance: go round twice — first with a cursor that only counts and writes nothing, then into a buffer of exactly the right size. Give the cursor struct a “count only” mode and the same encode function does both jobs.
50.6.3 Ring buffers and double buffering#
On the receiving side bytes arrive in pieces. A network does not keep message boundaries — one receive may give half a message, or three and a half. So the receiver piles bytes into a ring buffer and interprets a message only when all of it has arrived. Make the capacity a power of two, and “at the end, go back to the start” becomes one mask (i & (cap - 1)) instead of a remainder.
Where a writer and a reader run at the same time, as with video or sound, use double buffering: fill one buffer while the other is sent, then swap. POSIX writev, which sends several scattered pieces in one call without copying them together, is a tool of the same kind (not standard C).
50.6.4 Leftovers in a reused buffer#
Reusing a buffer is a good optimisation with one trap. If the previous message was 100 bytes and this one is 60, bytes 61 to 100 of the buffer still hold the previous message. Get the length wrong and send 100 bytes, and the tail of the previous message goes out too. It is the same kind of accident as the “padding that leaked” in chapter 48 — bytes you never sent go out. Decide the length to send only from what was written this time (the cursor’s len).
50.7 Principles for designing a format#
The techniques for handling bytes are enough as they stand. The hard part is deciding the format, because a format that has gone out cannot be called back.
| Principle | Why |
|---|---|
| A magic number at the very start | recognises the wrong file early. Mix in bytes that text conversion would mangle, as the first eight bytes of PNG do, and transfer accidents are recognised too |
| A version number, with major and minor | major for a change of meaning, minor for an added field (the Q&A above) |
| Fix the byte order in the documentation | little endian is common for formats designed today, and big endian is the convention for network protocols. Either way, writing it down is the principle |
| Fixed widths, or variable lengths with a limit | int, long, size_t and pointers never appear in a format |
| A limit on every length, count and depth | the reader can budget its resources in advance. A format without limits is an attack surface |
| Make the unknown skippable | tag, length, value. An old reader does not die on a new file |
| Exactly one canonical encoding | the same value is the same bytes — signing, hashing and comparing become possible. A varint reader must refuse “needlessly long” encodings |
| Tell integrity from authenticity | a CRC (cyclic redundancy check) finds damage done by accident. It cannot find a change made on purpose — that is the job of a MAC (message authentication code) or a signature |
| Publish test vectors | put “this value is these bytes” pairs in the documentation, and two implementations that disagree are caught from the start |
| Ask first whether text would do | being readable and editable by people is worth a lot (the Q&A in chapter 48) |
Table 50.5 — Principles for designing a binary format
Q. There is a saying: “be conservative in what you send, liberal in what you accept”. Should the reader not be liberal?
A. That is the “robustness principle” of the early Internet IP and TCP specifications (RFC 760, 1980; RFC 793, 1981), and for a long time it was taken as a virtue. But once many implementations accept liberally, nobody notices when a sender is wrong, and the format becomes not the document but “whatever the most liberal implementation accepts”. That gap produces differences between parsers, and the differences become attacks — when two implementations read the same bytes differently, the one that checks and the one that uses see different things. So format design today leans towards being strict in what you accept too — RFC 9413 (2023) from the Internet Architecture Board (IAB) concludes that over-applying the principle makes implementations drift apart and entrenches errors, and recommends fixing the specification and writing the error handling into it rather than quietly accepting faulty input. If leniency is needed, write into the format what it is lenient about — skip unknown tags, but refuse a tag whose length is wrong.
50.8 Security — every byte from outside was written by the other side#
Deserialisation code has one first rule: assume the attacker chose every byte of the input. The lengths, the counts, the offsets, the version number. The accidents below all happened where that one assumption was broken.
| Kind | What was trusted | What stops it |
|---|---|---|
| Trusting a length | “as many bytes follow as the length field says” | the cursor compares with the bytes left |
| Overflow in a size calculation | “width × height × 4 will not overflow” | ckd_mul, limits |
| Allocating on a count | “a billion items means room for a billion” | bound the count by the bytes left, first |
| Nesting depth | “lists inside lists only go a few levels deep” | a depth limit, or an explicit stack instead of recursion |
| A table size that assumes valid input | “for a valid code, a table this big is enough” | count the size needed before writing |
| Confusion of representations | “these bytes have only one meaning” | one canonical encoding, strict parsing |
| Double fetch | “the value in shared memory stays as it was after I checked it” | copy once and validate the copy |
| Bytes never sent | “the buffer holds only what I wrote” | send only the length written; fill with zeros |
Table 50.6 — Kinds of accident in deserialisation
Three of those kinds — overflow in a size calculation, allocating on a count and nesting depth — in one example:
examples-en/serialization/hostile.c
/* Three lies a hostile input can tell, and the checks that refuse them.
Nothing here overflows: the unchecked versions are only computed and printed. */
#include <stdckdint.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
/* (1) A header says width x height x 4 bytes. In 32 bits, the product wraps. */
static void image_size(uint32_t w, uint32_t h)
{
uint32_t naive = w * h * 4u; /* unsigned: wraps, no UB --- and no warning */
size_t checked;
bool over = ckd_mul(&checked, (size_t)w, (size_t)h)
|| ckd_mul(&checked, checked, (size_t)4);
printf(" %10u x %-10u naive 32-bit size %10u",
(unsigned)w, (unsigned)h, (unsigned)naive);
if (over) puts(" checked: refused (does not fit in size_t)");
else if (checked > 256u << 20)
printf(" checked: %zu, refused (over the 256 MiB limit)\n", checked);
else printf(" checked: %zu, accepted\n", checked);
}
/* (2) A count says "a billion items follow" but the input holds a few bytes.
Compare the claim with what is actually there *before* allocating. */
static void read_items(uint32_t claimed, size_t bytes_left, size_t item_size)
{
printf(" claims %10u items, %3zu bytes left: ", (unsigned)claimed, bytes_left);
if (claimed > bytes_left / item_size) { puts("refused before malloc"); return; }
void *p = malloc((size_t)claimed * item_size);
puts(p ? "allocated" : "allocation failed");
free(p);
}
/* (3) Nesting: 0x01 opens a list, 0x02 closes it. A recursive reader needs a depth limit,
or a long run of 0x01 bytes uses up the stack. */
enum { MAX_DEPTH = 32 };
static const unsigned char *parse_list(const unsigned char *p,
const unsigned char *end, int depth, bool *ok)
{
if (depth > MAX_DEPTH) { *ok = false; return end; }
while (p < end && *ok) {
if (*p == 0x01) p = parse_list(p + 1, end, depth + 1, ok);
else if (*p == 0x02) return p + 1;
else p++;
}
return p;
}
int main(void)
{
puts("[1] sizes from a header");
image_size(640, 480);
image_size(65536, 16385);
image_size(0x40000000u, 4);
image_size(UINT32_MAX, UINT32_MAX);
puts("\n[2] counts from a header (8-byte items)");
read_items(3, 24, 8);
read_items(1000000000u, 24, 8);
puts("\n[3] nesting depth");
static unsigned char deep[100000];
for (size_t i = 0; i < sizeof deep; i++) deep[i] = 0x01;
unsigned char fine[] = { 0x01, 0x01, 0x07, 0x02, 0x02 };
bool ok = true;
parse_list(fine, fine + sizeof fine, 0, &ok);
printf(" 5 bytes, depth 2 : %s\n", ok ? "accepted" : "refused");
ok = true;
parse_list(deep, deep + sizeof deep, 0, &ok);
printf(" 100000 opens in a row : %s at depth %d\n",
ok ? "accepted" : "refused", MAX_DEPTH + 1);
return 0;
}
Output
[1] sizes from a header
640 x 480 naive 32-bit size 1228800 checked: 1228800, accepted
65536 x 16385 naive 32-bit size 262144 checked: 4295229440, refused (over the 256 MiB limit)
1073741824 x 4 naive 32-bit size 0 checked: 17179869184, refused (over the 256 MiB limit)
4294967295 x 4294967295 naive 32-bit size 4 checked: refused (does not fit in size_t)
[2] counts from a header (8-byte items)
claims 3 items, 24 bytes left: allocated
claims 1000000000 items, 24 bytes left: refused before malloc
[3] nesting depth
5 bytes, depth 2 : accepted
100000 opens in a row : refused at depth 33
The first group is size calculation. 65536 × 16385 × 4 multiplied in 32 bits wraps to 262144. Unsigned overflow is not undefined behaviour (UB) but a defined remainder, so the compiler does not warn either (chapter 29). Allocate that small number and write the original size, and it is a heap overflow. Multiply in size_t with ckd_mul and compare with the limit the format sets (256 MiB here), and both the product that wraps and the size that does not wrap but exceeds the limit are stopped.
The second group is counts. Believe “a billion items” and allocate first, and one 24-byte input can make you reserve gigabytes. Before allocating, check “can that many items fit in the bytes that are left?”.
The third group is depth. Give a recursive parser 100,000 “open a list” bytes in a row and the stack runs out. With a depth limit it stops at the 33rd level.
50.8.1 Accidents that happened#
In practice. zlib — the length field in a header (CVE-2022-37434)
zlib is the compression library found in nearly everything — gzip, PNG, HTTP compression and more. Its inflate (inflate.c), up to 1.2.12, overflowed or over-read a heap buffer when the “extra field” of a gzip header was large. Only applications that call inflateGetHeader to receive the header information were affected.2
The length field in a header is a value the sender wrote. On one path, comparing it with the size of the receiver’s buffer was left out. The “trusting a length” kind of accident turns up even in one of the oldest and most reviewed C libraries.
In practice. Stagefright and FORCEDENTRY — one multiplication
In 2015 Android’s media library libstagefright reached remote code execution through an unchecked multiplication while parsing the “atoms” of an MP4 file (CVE-2015-1538, SampleTable::setSampleToChunkParams, Android before 5.1.1 LMY48I). The code is C++, but what overflowed is the same integer multiplication as in C.
FORCEDENTRY in 2021 (CVE-2021-30860) was more elaborate. iMessage hands files whose names end in .gif to an image library, and that library guessed the format from the contents, not the extension. So a PDF that was a GIF in name only went to the PDF parser. Its JBIG2 decoder added up the sizes of the symbol dictionaries it referred to in a 32-bit numSyms, which wrapped and reserved a small buffer; later writes went past its end. Google Project Zero called it “one of the most technically sophisticated exploits we’ve ever seen”.3
Both teach the same thing: a size computed from the input is input. The result of the multiplications and additions was chosen by the attacker too.
In practice. libwebp — “if the input is valid” (CVE-2023-4863)
WebP’s lossless format uses Huffman codes. libwebp reserved memory for its Huffman tables in fixed sizes computed in advance. Those sizes were exactly right: a “valid, complete code” could never exceed them. But a forged invalid code wrote past the end while the table was being built, before the final consistency check rejected it. OSS-Fuzz had run on it for a long time without finding it: the condition needed several valid tables of maximum size followed by one particular invalid table. The fix added a step that counts the size needed before writing.4
The table-size calculation was not wrong. It rested on the assumption that the input is valid, and the check came after that assumption had been broken. Validation has to come before writing.
In practice. OpenSSL’s ASN.1 — different bytes for the same value (CVE-2016-2108)
In practice. Double fetch — a value that changes after it was checked
wire.c above).Heartbleed, the classic accident of trusting a length, was in chapters 43–44, and Cloudbleed, where a generated parser ran past the end, in chapter 57.
50.8.2 Structures that prevent them#
What prevents accidents is structure, not care. Every accident above happened in code written by experienced people.
| Structure | The kinds it stops |
|---|---|
| Every read goes through the cursor (the range check is in one function) | trusting a length, reading past the end |
Size calculations with ckd_mul and ckd_add, plus limits | overflow in a size calculation, huge allocations |
| Bound counts by the bytes left, first | allocating on a count |
| Depth and repetition limits | nesting depth, endless loops |
| Count the size needed before writing | the “valid input” assumption |
| Strict parsing, one canonical encoding | confusion of representations |
| Copy once, then validate | double fetch |
| Fuzzing (tools such as libFuzzer and AFL) and test builds with sanitizers always on | inputs nobody thought of — though, as libwebp shows, fuzzing misses conditions that are hard enough to reach |
Table 50.7 — Structures that guard deserialisation
Fuzzing feeds a parser endless inputs, changed at random or guided by the paths they take. Run with a sanitizer such as ASan (chapter 57), it stops at the moment an overflow happens. It is the cheapest insurance anyone writing a format parser can buy.
50.9 Summary#
| Topic | The point |
|---|---|
| What it is | values in memory turned into bytes agreed with the outside. The memory layout is the implementation’s promise; the format is a promise to the outside |
| Avoiding it | only where you hold the build on both sides. Nail the layout down with static_assert, and the byte order too |
| Techniques | cursors (the range check in one place), sticky errors, fixed widths and shifts, varints and zigzag, tag-length-value |
| Packing and padding | read formats as bytes rather than fitting a struct to them. Never pass the address of a packed member |
| Endianness | write shifts and leave the rest to optimisation. C23 only has macros that ask about byte order, no function that changes it |
| Buffers | gather and send once, double when growing, ring buffers, send only the length written |
| Format design | magic, version, byte order, limits, skipping, one canonical form, test vectors. Be strict in what you accept too |
| Security | the attacker chose every byte of the input. Validate before writing into memory, check sizes for overflow, limit depth and counts |
Table 50.8 — Serialisation — one line each
Serialisation was “values going outside”. The next chapter asks how to lay the same data out inside. Should structs be lined up in an array, or should each field get an array of its own — a choice that, through the cache, can change a program’s speed several times over.
Notes
- Protocol Buffers documentation, “Encoding” (protobuf.dev): 150 is
96 01, and because the wire type gives the length, unknown fields can be skipped. ↩ - CVE-2022-37434 record (published 2022-08-05). ↩
- I. Beer and S. Groß, “A deep dive into an NSO zero-click iMessage exploit”, Google Project Zero, 2021-12-15. Fixed in iOS 14.8 (2021-09-13). ↩
- CVE-2023-4863 record; B. Hawkes, “The WebP 0day” (blog.isosceles.com, 2023-09-21). Fix commit
902bc919. ↩ - CVE-2016-2108 record. ↩
- P. Wang, J. Krinke, K. Lu, G. Li and S. Dodier-Lazaro, “How Double-Fetch Situations turn into Double-Fetch Vulnerabilities: A Study of Double Fetches in the Linux Kernel”, USENIX Security 2017. ↩