Representing Information

13 · Representing Information¶

The question¶

What is a number to this machine, and when does that answer bite?

Most of the time it does not bite at all, which is the difficulty. A machine word behaves enough like an integer that a programmer can go years without meeting the difference, and then meet it in production. So this chapter is organised around the places the representation leaks — where two things that look identical in C turn out not to be, and the reason is always that one of them made a promise the other did not.

The material¶

Two rules make every struct¶

ch00 measured two structs with the same three members in different orders and found one larger than the other. A table can say that. It cannot say where the extra bytes went:

Two rules produce every gap in that picture:

1. A member starts at a multiple of its own alignment — the spacing the hardware wants a value of that width to sit at. A four-byte integer may begin at offset zero, four, eight — not at one. Many machines load a word faster when it does not straddle two of them, and some refuse outright.

2. A struct’s size is a multiple of its own alignment, which is the largest of its members’. Otherwise the second element of an array of them would start somewhere illegal.

And one prohibition that turns those rules into your problem rather than the compiler’s: C does not permit members to be reordered ISO/IEC JTC1/SC22/WG14 (2018). The order you wrote is the order you get, and the padding follows from it. Every other language with a struct-like type had this same choice to make, and several of them chose differently.

On a single struct this is an oddity. On an array of a few million — a particle system, a packet buffer, a page-table cache — it is the difference between fitting in a level of cache and not, which is ch25’s subject and the first place this dry rule becomes a duration.

A comparison that is not a comparison¶

Here are two functions. They differ by one word.

int sysfs_signed_grows(int x) { return x + 1 > x; }

int sysfs_unsigned_grows(unsigned x) { return x + 1 > x; }

Both ask whether adding one to a number makes it bigger. This is what the compiler did with the signed one:

sysfs_signed_grows compiled for riscv64 at -O2 — the xv6 target’s instruction set, 2 instructions.

0000000000000000 <sysfs_signed_grows>:
   0:	li	a0,1
   2:	ret

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · -O2 -Wall -Wextra -march=rv64gc -mabi=lp64d -c · 2026-09-17 · Source: bench/results/signedness-riscv64.json, code hash d4dace135c463c55.

It does not add. It does not compare. It returns yes without looking at the argument, because as far as the compiler is concerned there is no argument for which the answer could be anything else.

And the unsigned one:

sysfs_unsigned_grows compiled for riscv64 at -O2 — the xv6 target’s instruction set, 3 instructions.

0000000000000004 <sysfs_unsigned_grows>:
   4:	addi	a0,a0,1
   6:	snez	a0,a0
   a:	ret

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · -O2 -Wall -Wextra -march=rv64gc -mabi=lp64d -c · 2026-09-17 · Source: bench/results/signedness-riscv64.json, code hash d4dace135c463c55.

That one does the work.

The difference is not that unsigned arithmetic is slower. It is that the two types make different promises. Unsigned overflow is defined: it wraps, and the largest unsigned value plus one really is zero, so the comparison can be false and the compiler must ask. Signed overflow is undefined ISO/IEC JTC1/SC22/WG14 (2018) — the standard declines to say what happens — so a compiler is entitled to assume it never occurs, and from that assumption x + 1 > x follows for every x that exists as far as it is concerned.

Undefined behaviour is not a runtime hazard; it is a licence the optimiser holds. Stay uneasy about that for the rest of the book. The danger is not that your program will crash when it overflows. The danger is that a branch you wrote to check for overflow will be deleted, because the compiler reasoned that the condition could not arise.

A division that is not a division¶

The same pair again, dividing instead of adding:

int sysfs_signed_quarter(int x) { return x / 4; }

unsigned sysfs_unsigned_quarter(unsigned x) { return x / 4; }

Unsigned first, because it is the one that behaves:

sysfs_unsigned_quarter compiled for riscv64 at -O2 — the xv6 target’s instruction set, 2 instructions.

000000000000001c <sysfs_unsigned_quarter>:
  1c:	srliw	a0,a0,0x2
  20:	ret

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · -O2 -Wall -Wextra -march=rv64gc -mabi=lp64d -c · 2026-09-17 · Source: bench/results/signedness-riscv64.json, code hash d4dace135c463c55.

One shift. Dividing an unsigned number by a power of two is a right shift, exactly, with no edge cases.

Signed:

sysfs_signed_quarter compiled for riscv64 at -O2 — the xv6 target’s instruction set, 5 instructions.

000000000000000c <sysfs_signed_quarter>:
   c:	sraiw	a5,a0,0x1f
  10:	srliw	a5,a5,0x1e
  14:	addw	a0,a0,a5
  16:	sraiw	a0,a0,0x2
  1a:	ret

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · -O2 -Wall -Wextra -march=rv64gc -mabi=lp64d -c · 2026-09-17 · Source: bench/results/signedness-riscv64.json, code hash d4dace135c463c55.

Several instructions, and the extra ones are not arithmetic — they are a correction. An arithmetic right shift rounds towards negative infinity; C requires integer division to round towards zero ISO/IEC JTC1/SC22/WG14 (2018). For positive numbers those agree. For negative ones they differ by one, so the compiler adds a bias before shifting, and the bias has to be computed from the sign bit — the top bit, which says whether the value is negative — because it only applies to negatives.

Nobody wrote that correction. It is the cost of a promise C made about rounding, paid on every signed division by a constant, by a programmer who thought they were writing a shift.

Neither of these functions is wrong, and neither compiler decision is a bug. The machine code you get is a consequence of the type you chose, and the type is a claim about what values are possible. Make a weaker claim and you get more instructions; make a stronger one and the optimiser will use it, including in ways you did not intend.

Byte order, seen rather than described¶

A number wider than a byte has to be laid out in memory somehow, and there are two sensible answers. Both of this book’s machines choose little-endian: the lowest-addressed byte holds the least significant part. ch00’s probe asks the machine rather than asserting it, which is why the fact appears in its output and not in a footnote here.

It matters in exactly three places, and outside them you can forget it: when bytes cross a machine boundary (a file, a network, a device register), when you alias a value through a pointer of a different width, and when you are reading a memory dump by eye and the digits appear to be backwards. The first kind is the one that bites: a device register or a file written by another machine is bytes somebody else laid out, and nothing warns you when their order is not yours.

The operations worth writing once¶

sysfs/lib/bits.c holds the bit manipulations later chapters reuse. They are written out the long way rather than calling a builtin, because this is the chapter where a machine word stops being an abstraction, and a loop you wrote teaches that better than an intrinsic you called:

unsigned sysfs_popcount(unsigned long word) {
  unsigned set = 0;
  while (word) {
    /* Clearing the lowest set bit each time, so this runs once per set bit rather than once per
     * bit in the word. Worth knowing as a shape: `x & (x - 1)` is the single most reused
     * bit-twiddling identity in this book. */
    word &= word - 1;
    set++;
  }
  return set;
}

word &= word - 1 clears the lowest set bit. It is worth learning as a shape rather than deriving each time, and it is the single most reused identity in this book.

One function in that file is about overflow rather than bits:

unsigned long sysfs_round_up_pow2(unsigned long value) {
  if (value == 0) {
    return 0;
  }
  unsigned long result = 1;
  while (result < value) {
    /* The overflow check has to come before the shift, not after: once the top bit shifts out
     * there is nothing left to notice it by. Returning 0 says "no such power of two fits",
     * which a caller can test; wrapping silently to 0 would say the same thing by accident. */
    if (result > (~0UL >> 1)) {
      return 0;
    }
    result <<= 1;
  }
  return result;
}

The overflow check runs before the shift. Afterwards there is nothing left to notice it by — the bit has gone, and the value is zero, and zero is indistinguishable from a legitimate answer. That ordering is the same lesson ch24 draws about checking for a condition while the evidence still exists. It arrives several chapters early because arithmetic is where it bites first.

What we measured¶

xv6 and host present the same C implementation — the same sizes, alignments and byte order — and ch00’s table measured it by booting the kernel and asking it. It is not repeated here, because a figure printed twice is a figure that can disagree with itself.

What this chapter adds is the machine code above. Those listings are not timings, and nothing in this chapter is. They are what one compiler emitted for one source file at one optimisation level, regenerated by CI on every push so that a compiler which changes its mind breaks the build rather than the argument.

Counting instructions is not measuring cost. A function with more instructions in it can be faster than one with fewer, and ch27 shows a case where that happens for reasons entirely outside the count. The listings establish something weaker and more useful: the two functions in each pair are not the same program, whatever the source looked like.

What this cannot tell you¶

Whether any of it is slow. Signed division emits a correction; whether that correction costs a measurable amount depends on the core, on what else is in flight, and on whether the result was needed immediately. ch26 is where that gets a number, on a machine that can produce one.

What another compiler does. Every listing here is one version of gcc. A different compiler may fold differently, and the standard permits both. The claims about what C says are claims about the standard ISO/IEC JTC1/SC22/WG14 (2018) and are stable; the claims about what the machine code looks like are claims about a toolchain and are stamped accordingly.

What undefined behaviour will do to you. This chapter shows one consequence — a comparison compiled away — because it is visible in a disassembly. The full set is not enumerable, and anyone who tells you the rule is “it does whatever the hardware does” has the wrong model: the hardware never sees the code that was deleted.

Floating point. It is absent from this chapter and from the xv6 target generally, and that is a decision rather than an oversight: xv6 does not save floating-point registers across a context switch, so a user program that uses them is quietly wrong the moment it is descheduled. That is a perfectly reasonable thing for a teaching kernel to decide — it makes ch21’s context switch small enough to read in one sitting — and it means floating point arrives in Part V, on a machine whose kernel does save those registers.

Problems¶

Three, and none of their answers is anywhere in this repository.

13.1 — Two operations the library does not have. tests/representing_information/bitops.c asks for a byte-order swap and the index of the lowest set bit. Neither is in sysfs/lib/bits.c, so there is nothing to copy. The test checks properties rather than cases: swapping twice must give back what you started with, and the bit you name must be set with nothing set below it. A property holds for every input, so it cannot be satisfied by memorising.

python3 -m pytest tests/representing_information/test_problem_1_bitops.py

13.2 — Pack the struct. Five members, declared in an order that wastes space. Give the order that wastes least. The test compiles your arrangement and compares it against the best that arrangement of those types can do — it does not tell you the number, and the two rules at the top of this chapter are enough to work it out.

python3 -m pytest tests/representing_information/test_problem_2_reorder.py

13.3 — Find the input that makes it wrong. A bounds check that looks correct and is not. Find one triple of values where it says a read fits and the read would run off the end.

Nothing in it is undefined: the type is unsigned, so the machine does exactly what it was told, and the result is still wrong. That is the uncomfortable half of this chapter — undefined behaviour is dramatic and rare, and defined behaviour that does not match your intention is quiet and everywhere.

python3 -m pytest tests/representing_information/test_problem_3_break_it.py

Where to go next¶

The C standard ISO/IEC JTC1/SC22/WG14 (2018) is the document that decides which of this chapter’s surprises are the compiler’s fault and which are yours. It is not readable end to end, and it is not meant to be — but looking up one behaviour you thought you knew is a formative afternoon, and the freely available committee draft is fine for that.

The RISC-V unprivileged specification RISC-V International (n.d.) defines what the shift and division instructions above actually do, including the cases C calls undefined. Reading the two documents against each other is how you learn that “undefined behaviour” describes a language, not a machine: the hardware always does something specific, and knowing what does not make the C legal.

The psABI RISC-V International (n.d.) fixes the sizes and alignments this chapter’s structs are laid out by.

ch05 did the same thing to the other half of C — the part that is really about addresses — and is worth rereading now that a type has been shown deciding what the machine does.

ch14 stops treating the listings as evidence for a point about C and starts reading them as the subject.